Blockstream osiągnął nowy kamień milowy w rozwoju Bitcoina, certyfikując i weryfikując nową funkcję kryptograficzną dla Bitcoina: Safegcd.
W świecie, w którym bezpieczeństwo i wydajność mają kluczowe znaczenie dla sukcesu kryptowalut, Blockstream, jedna z najbardziej innowacyjnych firm w technologii blockchain, podjęła gigantyczny krok w celu wzmocnienia infrastruktury Bitcoin. Pamiętajmy, że bezpieczeństwo Bitcoina w dużej mierze zależy od algorytmów podpisu cyfrowego takich jak ECDSA, które gwarantują autentyczność i integralność transakcji. Jednakże algorytmy te stoją przed ciągłym wyzwaniem, jakim jest zrównoważenie szybkości i bezpieczeństwa, zwłaszcza jeśli chodzi o złożone operacje matematyczne, takie jak odwrotności modułowe.
Blockstream sprostał temu wyzwaniu, opracowując i wdrażając nowy algorytm o nazwie „bezpiecznycd«. Algorytm ten, łączący szybkość i bezpieczeństwo, przeszedł rygorystyczną weryfikację formalną w celu zapewnienia jego poprawności. Rezultatem jest znaczący postęp, który nie tylko poprawia wydajność operacji podpisywania i weryfikacji Bitcoina, ale także zapewnia silną matematyczną gwarancję jego prawidłowego działania. W tym artykule zbadamy, w jaki sposób Blockstream osiągnął ten kamień milowy i jakie ma to konsekwencje dla przyszłości Bitcoina.
Ogromne wyzwanie dla bezpieczeństwa Bitcoina
Sercem algorytmów podpisu cyfrowego i wyprowadzania klucza jest operacja matematyczna znana jako rewers modułowy. Operacja ta jest stosunkowo kosztowna pod względem zasobów obliczeniowych, co czyni ją wąskim gardłem dla wydajności Bitcoina. Ale jest to również niezbędne dla jego bezpieczeństwa, co czyni go szczególnie ważnym, jeśli chodzi o jego dobre wdrożenie.
Doprowadziło to do dwóch głównych metod obliczania odwrotności modułowych: zastosowania techniki zwanej „drabinką wykładniczą” (bardzo powolna) i rozszerzonego algorytmu GCD Euklidesa (szybkiego, ale trudnego do uzyskania stałej w czasie). Obecnie biblioteka libsecp256k1, utworzona i używana przez Bitcoin Core, zawsze wybiera drabinę wykładniczą, gdy jest skonfigurowana do użytku w Bitcoin Core. Chociaż metoda ta jest bezpieczna, jest notorycznie powolna, co ogranicza wydajność portfela.
Rozwiązanie Blockstream: Safegcd
Aby rozwiązać ten problem, Blockstream postanowił stworzyć implementację GCD, która zapewniłaby bezpieczeństwo Bitcoina na tym etapie, ale także umożliwiłaby poprawę wydajności sieci. W ten sposób w 2021 roku Blockstream wdrożył nowy modułowy algorytm odwrotny o nazwie „safegcd”. Algorytm ten, opracowany przez Daniela J. Bernsteina i Bo-Yin Yang, oferuje alternatywę, która jest zarówno szybka, jak i stała w czasie. Safegcd działa poprzez powtarzanie prostych obliczeń, aż do osiągnięcia warunku zakończenia. Aby mieć pewność, że algorytm jest stały w czasie, można go iterować określoną liczbę razy, nawet jeśli warunek zakończenia zostanie osiągnięty wcześniej.
Kluczem do zapewnienia stałej wartości Safegcd w czasie jest określenie, ile iteracji jest niezbędnych dla wszystkich możliwych 256-bitowych wejść (rozmiar wejść w przypadku secp256k1). Początkowo szacowano, że potrzebnych będzie 741 iteracji, ale Pieter Wuille, inżynier w Blockstream, opracował metodę zmniejszenia tej liczby do 724 iteracji. Później Wuille i Gregory Maxwell odkryli wariant algorytmu, który wymaga jedynie 590 iteracji. Optymalizacja ta poprawiłaby wydajność podpisów ECDSA o 25% i weryfikacji podpisów o 15% w porównaniu z drabiną wykładniczą.
Weryfikacja formalna: zapewnienie poprawności
Jednak pomimo poprawy wydajności, wdrożenie nowatorskiego algorytmu, takiego jaksafegcd, niesie ze sobą ryzyko. Jeśli wystąpi błąd w obliczeniu niezbędnych iteracji, algorytm może nie zakończyć się poprawnie, co skutkuje nieprawidłowymi wartościami i ostatecznie niepowodzeniem weryfikacji podpisu. Byłoby to druzgocące dla bezpieczeństwa Bitcoina.
Aby ograniczyć to ryzyko, firma Blockstream Research przeprowadziła formalną weryfikację algorytmu Safegcd przy użyciu kreatora testów Coq. Coq to narzędzie oparte na teorii typów zależnych, które łączy system dedukcji matematycznej z funkcjonalnym językiem programowania. Umożliwia to testowanie przez refleksję, czyli metodę łączącą wykonanie programu funkcjonalnego z dedukcją matematyczną w celu sprawdzenia poprawności algorytmu.
Weryfikacja formalna polegała na zaimplementowaniu algorytmu obliczeń kadłuba wypukłego w programie Coq i wykazaniu poprawności tego obliczenia. Wynikiem jest twierdzenie gwarantujące, że algorytm Safegcd zakończy się po 590 iteracjach. Weryfikację tę przeprowadzono na sprzęcie konsumenckim w ciągu 2,5 dnia, co wykazało wykonalność tej techniki.
Implementacja w libseCP256k1
La wdrożenie z Safegcd w libseCP256k1 był wspólnym wysiłkiem. Peter Dettman, programista, który zaimplementował algorytm, ściśle współpracował z zespołem Blockstream nad zintegrowaniem Safegcd z biblioteką. Proces obejmował dodanie funkcji ctz (liczenie zer końcowych) w celu optymalizacji operacji bitowych, wdrożenie algorytmu Safegcd w oddzielnych modułach, dodanie obszernych testów i refaktoryzację kodu w celu przygotowania do przejścia na SafeGCD.
Dodatkowo wprowadzono dodatkowe optymalizacje w celu poprawy wydajności w systemach 32- i 64-bitowych. Optymalizacje te są kluczowe, ponieważ Bitcoin często działa na bardzo słabym sprzęcie, takim jak urządzenia mobilne i systemy wbudowane, gdzie wydajność jest kluczowa.
W ten sposób wdrożenie i formalna weryfikacja algorytmusafegcd przez Blockstream stanowi znaczący kamień milowy w bezpieczeństwie i wydajności Bitcoina. To rozwinięcie nie tylko poprawia wydajność operacji podpisywania i weryfikacji, ale także zapewnia matematyczną gwarancję, że algorytm działa poprawnie.
Ponadto formalna weryfikacja Safegcd pokazuje, że w praktyce możliwa jest weryfikacja złożonego i krytycznego oprogramowania, co otwiera drzwi do weryfikacji innych funkcji zaimplementowanych w libsecp256k1 i może prowadzić do większego bezpieczeństwa i niezawodności w sieci Bitcoin.
