Jak Bitcoin opiera się komputerom kwantowym? Porównanie trzech schematów podpisów opartych na siatkach

Autor: Zespół Blockstream

Tłumaczenie: Saoirse, Foresight News

Instytut Badawczy Blockstream opublikował pełny raport dotyczący podpisów opartych na siatkach w Bitcoinie. Niniejszy artykuł podsumowuje treść badania, kluczowe odkrycia oraz związane z nimi zalecenia, a pełny raport można znaleźć tutaj.

Podpis cyfrowy jest kluczowym mechanizmem autoryzacji transakcji w Bitcoinie, a obecnie funkcję tę pełnią podpisy Schnorra i ECDSA, które mają bardzo niskie koszty. W 1994 roku Shor udowodnił, że wystarczająco potężny komputer kwantowy może złamać te dwa rodzaje podpisów. Choć wciąż toczy się szeroka dyskusja na temat tego, kiedy takie maszyny mogą się pojawić, musimy opracować wykonalny plan wdrożenia podpisów odpornych na kwanty, zanim problem stanie się rzeczywistością.

Schematy podpisów opartych na siatkach są popularnymi kandydatami do zastąpienia obecnych podpisów. Badania nad kryptografią opartą na siatkach trwają od ponad wieku, a jej zastosowania kryptograficzne rozwijają się od blisko trzydziestu lat. W kontekście kryptografii odpornych na kwanty, podpisy oparte na siatkach mają wiele zalet: całkowity rozmiar klucza publicznego i podpisu może być mniejszy niż 1,6 kilobajta, a ich struktura algebraiczna ma potencjał do wspierania podpisów wielopodpisowych, podpisów progowych oraz prostych dowodów w przyszłości.

Raport bada trzy schematy: Dilithium, Falcon i Hawk. Dla czytelników, którzy nie znają kryptografii opartej na siatkach, przedstawiamy myśli projektowe każdego schematu, w pełni opisujemy proces algorytmu oraz analizujemy je pod kątem bezpieczeństwa, wydajności i rzeczywistego wdrożenia (np. pochodne kluczy portfela). Które z tych schematów mogą być naprawdę wdrożone na łańcuchu Bitcoin?

Kryteria oceny

Bitcoin ma swoje ograniczenia przy wyborze schematu podpisu, a ta ocena opiera się na czterech kluczowych standardach:

• Koszt na łańcuchu: Jednym z najważniejszych wskaźników jest całkowity rozmiar klucza publicznego i podpisu. Gdy wydawane są środki, klucz publiczny i podpis są rejestrowane na łańcuchu, a pełne węzły muszą pobrać i przechować każdy bajt. Koszt weryfikacji jest również kluczowy: każdy podpis musi być weryfikowany przez węzły w całej sieci, a wolna prędkość weryfikacji może obciążyć całą sieć.
• Złożoność implementacji: Kluczowe jest, czy schemat można bezpiecznie zaimplementować. Jeśli projekt wymaga obliczeń zmiennoprzecinkowych lub precyzyjnego próbkowania Gaussa, błąd w implementacji lub atak boczny, taki jak analiza czasowa, może ujawnić klucz. Aby zapewnić płynne przejście, złożoność implementacji jest czynnikiem, którego nie można zignorować.
• Ryzyko wdrożenia: W rzeczywistości integracja Bitcoin napotyka różne przeszkody: wybór funkcji haszującej na poziomie konsensusu (większość kandydatów używa SHAKE, podczas gdy Bitcoin korzysta z SHA-256), powtarzalność wyników podpisów między platformami oraz to, czy program podpisujący jest dostosowany do ograniczeń pamięci portfeli sprzętowych.
• Potencjał rozwoju: Większość portfeli Bitcoin korzysta z mechanizmu deterministycznego BIP-32: za pomocą jednego głównego klucza publicznego, bez kontaktu z kluczem prywatnym, można wygenerować nieskończoną liczbę kluczy publicznych. Obecnie standaryzowane schematy podpisów odpornych na kwanty nie obsługują tej cechy natywnie, dlatego badamy koszty związane z dodaniem tej zdolności; jednocześnie badamy różne niestandardowe warianty schematów, które mogą przynieść większe korzyści.

Jaką klasę bezpieczeństwa wybrać?

Przed porównaniem rozmiarów należy określić docelowy poziom bezpieczeństwa, co nie jest tak proste, jak się wydaje. NIST klasyfikuje poziomy bezpieczeństwa na 1-5; im wyższy poziom, tym silniejsze bezpieczeństwo, ale odpowiadające mu klucze i rozmiar podpisu będą również większe.

Uważamy, że Bitcoin powinien przyjąć co najmniej poziom 3 standardu bezpieczeństwa. Wyjścia Bitcoin mogą nie być wydawane przez dziesięciolecia, a jeśli postęp technologii analizy kryptograficznej obniży rzeczywisty poziom bezpieczeństwa schematu, aktywa zostaną zablokowane przez klucze, które straciły na wartości, narażając je na długoterminowe ryzyko. Kryptografia oparta na siatkach przeszła blisko trzydzieści lat publicznej analizy kryptograficznej, a badania nad przyjęciem krzywych eliptycznych przez Bitcoin trwają jeszcze dłużej. Jednak złożona struktura algebraiczna kryptografii opartej na siatkach wciąż ma wiele luk, które mogą być wykorzystane w przyszłych atakach, dlatego nie powinniśmy stawiać wszystkich naszych zakładów na bezpieczeństwo w odległej przyszłości.

Wiodące produkty również podjęły podobne decyzje. Protokół PQ3 Apple iMessage bezpośrednio porzuca parametry kryptografii opartej na siatkach poziomu 1, stosując wyłącznie parametry poziomu 3 i 5; Cloudflare w wdrożeniu TLS odpornym na kwanty korzysta z ML-KEM-768 (poziom 3), wskazując, że chociaż poziom 1 wydaje się obecnie bezpieczny, należy zarezerwować margines bezpieczeństwa na przyszłe analizy kryptograficzne. Czas bezpieczeństwa Bitcoin jest jeszcze dłuższy niż w przypadku tych dwóch produktów.

Podniesienie poziomu bezpieczeństwa wiąże się z kosztami. Na przykład, zwiększenie Dilithium z poziomu 2 do 3 zwiększa całkowity rozmiar o około 1,5 kilobajta. Raport porównuje zestawy parametrów na wszystkich poziomach bezpieczeństwa, a czytelnicy mogą sami ocenić kompromisy. Przypadek Hawk dowodzi, że konserwatywne rozważania dotyczące bezpieczeństwa nie są tylko teoretyczne.

Szczegóły kandydatów

Dilithium: Prosty schemat

Dilithium zostało znormalizowane przez NIST jako ML-DSA w standardzie FIPS 204, przenosząc paradygmat zobowiązania-wyzwania-odpowiedzi podpisu Schnorra na arytmetykę modułową.

Jego największą cechą jest prostota. Wszystkie operacje w Dilithium są operacjami całkowitymi: operacje na pierścieniu, mnożenie macierzy wektora, haszowanie, zaokrąglanie, bez obliczeń zmiennoprzecinkowych i nie wymaga próbkowania Gaussa. Łatwiej jest napisać bezpieczną i stałoczasową implementację. Jest to również najbardziej powszechnie wdrażany kandydat, już zintegrowany z OpenSSL, BoringSSL, AWS-LC oraz Apple CryptoKit.

Kosztem jest większy rozmiar. ML-DSA-65 o bezpieczeństwie poziomu 3 ma klucz publiczny o rozmiarze 1952 bajtów, podpis o rozmiarze 3309 bajtów, co daje łącznie 5261 bajtów, co stanowi około 55 razy większy rozmiar niż całkowity rozmiar klucza publicznego i prywatnego Bitcoin oraz podpisu, co czyni go największym wśród trzech schematów o tym samym poziomie bezpieczeństwa.

Dla Bitcoina najcenniejszym punktem Dilithium jest to, że jest to jedyny schemat, który zbliża się do realizacji pochodnych kluczy w stylu BIP-32. Klucz konstrukcji DilithiumRK, który można losowo zrekonstruować, może być generowany przez klucz rodzicielski wyłącznie na podstawie informacji publicznych. Raport analizuje trzy warianty, w tym nasz zaproponowany DilithiumRKS, w którym logika pochodzenia jest całkowicie umieszczona wewnątrz oprogramowania portfela, a na łańcuchu potrzebna jest tylko standardowa weryfikacja dla zwykłych podpisów ML-DSA. Jednak żaden z trzech wariantów nie osiągnął standardu uruchomienia: dwa z nich wymagają modyfikacji weryfikatora, a DilithiumRKS brakuje pełnego dowodu na niemożliwość sfałszowania; wszystkie schematy polegają na wspólnej macierzy w całej sieci, co, choć formalnie bezpieczne w założeniu Module-LWE, wiąże bezpieczeństwo wszystkich kluczy z tym samym przypadkiem. Uważamy, że obecnie pochodzenie kluczy publicznych opartych na Dilithium jest jedynie dowodem koncepcji i nie nadaje się do rzeczywistego wdrożenia.

Falcon: Kompaktowy schemat

Falcon został wybrany przez NIST, a jego znormalizowana nazwa to FN-DSA, jest to najprostszy z trzech. Klucz publiczny i podpis Falcon-512 o bezpieczeństwie poziomu 1 mają łącznie 1563 bajty; Falcon-1024 o bezpieczeństwie poziomu 5 ma łącznie 3073 bajty. Falcon-1024, z wyższym marginesem bezpieczeństwa, ma nawet mniejszy rozmiar niż Dilithium o poziomie 3.

Falcon przyjmuje inną koncepcję niż Dilithium: oparty na siatkach NTRU model haszowania-podpisu. Prywatny klucz podpisującego to krótka baza siatki; wiadomość jest haszowana i mapowana na punkt w przestrzeni, a podpisujący wykorzystuje krótką bazę do znalezienia wektora blisko tego punktu. Punkt i ten bliski wektor tworzą podpis; weryfikacja polega na sprawdzeniu, czy wektor należy do tej siatki i czy jest wystarczająco blisko. Trudność implementacji polega na tym, aby znaleźć wektor, nie ujawniając informacji o bazie. Wczesne schematy GGH i NTRUSign bezpośrednio brały punkty z siatki, co ujawniało część informacji geometrycznych przy każdym podpisie. Falcon przyjmuje ramy GPV, aby próbować bliskich wektorów z rozkładu Gaussa, co pozwala udowodnić, że próbki są niezależne od bazy, eliminując ryzyko ujawnienia, ale znacznie zwiększa trudność implementacji próbników.

Próbnik jest słabym punktem Falcona na poziomie inżynieryjnym. Wymaga obliczeń w dziedzinie liczb zespolonych, co wymaga obliczeń zmiennoprzecinkowych. Różne procesory, kompilatory i opcje optymalizacji kompilacji mogą prowadzić do niespójnych wyników wyjściowych. To nie tylko problem zgodności, ale także zagrożenie dla bezpieczeństwa: dowód bezpieczeństwa GPV wymaga, aby podpisujący nigdy nie generował dwóch różnych krótkich wektorów dla tego samego streszczenia; jeśli podpis stanie się podpisem deterministycznym, różnice w zaokrągleniu zmiennoprzecinkowym w platformie mogą naruszyć ten warunek. Istnieje wykonalne rozwiązanie: deterministyczny Falcon może używać symulacji całkowitych zamiast sprzętowych zmiennoprzecinkowych, aby uzyskać całkowicie spójne podpisy na wszystkich platformach. Kosztem jest spadek prędkości podpisu o około 15 razy oraz spadek prędkości generowania kluczy o około 2 razy.

Co ważne, etap weryfikacji nie jest dotknięty: weryfikacja Falcona polega na operacjach całkowitych, wyniki są deterministyczne, a także jest najszybszym schematem weryfikacji spośród kandydatów. Ta asymetryczna cecha jest bardzo korzystna dla Bitcoina: podpisy są wykonywane przez portfel podczas wydawania transakcji raz, podczas gdy każdy podpis musi być weryfikowany przez wszystkie węzły w całej sieci. Spowolnienie podpisu o 15 razy to niskoczęstotliwościowy koszt, który przynosi korzyści w postaci międzyplatformowej powtarzalności i operacji całkowitych, co w naszej opinii jest rozsądny kompromis. Dlatego problem zmiennoprzecinkowy można rozwiązać za pomocą środków inżynieryjnych, a nie jako śmiertelna wada.

Dwie uwagi: z powodu ograniczeń strukturalnych, Falcon nie ma parametrów poziomu 3, można wybierać tylko poziom 1 lub 5. Biorąc pod uwagę margines bezpieczeństwa, zalecamy Falcon-1024. Drugą kwestią jest to, że podpisy zużywają dużą ilość pamięci: próbnik dla zestawu parametrów 1024 polega na drzewie wstępnie obliczonym, zajmującym około 90 kilobajtów pamięci. Portfele sprzętowe mogą dynamicznie odbudować to drzewo wzdłuż gałęzi, zmniejszając zajętość pamięci do 16 kilobajtów, ale czas podpisu podwaja się. Spowolnienie podpisu w urządzeniach sprzętowych to rzeczywisty koszt, ale nadal akceptowalny.

Hawk: Schemat ogłoszony jako nieudany

Celem Hawk jest połączenie zalet dwóch innych schematów: podpis Hawk-512 ma tylko 555 bajtów, co czyni go mniejszym niż Falcon; wszystkie operacje na etapie podpisu są całkowite, a minimalne zużycie pamięci wynosi tylko 6 kilobajtów. Jest to również jedyny pozostały kandydat oparty na siatkach w trzeciej rundzie dodatkowego konkursu podpisów NIST, a raport poświęca mu dużą część.

Kosztem są założenia bezpieczeństwa. Nie opiera się na problemach NTRU i SIS, które zostały poddane analizie kryptograficznej przez dziesięciolecia, lecz na problemie izomorfizmu siatki oraz założeniu one-more-SVP, które mają stosunkowo krótką historię badań.

Tuż przed zakończeniem raportu, Straznickas i Weis z Anthropic odkryli strukturalną wadę w konstrukcji siatki Hawk: wymagana do odzyskania klucza rzeczywista wymiar SVP, który należy rozwiązać, jest tylko połową tego, co zaplanowali projektanci. Bezpieczeństwo odzyskiwania klucza dla zestawu parametrów kandydata zostało znacznie osłabione. Badacze przeprowadzili pełny atak na odzyskiwanie klucza dla parametrów wyzwania HAWK-256 używanych do analizy kryptograficznej; nawet w przypadku ataku, formalne propozycje HAWK-512 i HAWK-1024 wciąż nie mogą być złamane w rzeczywistości. Zespół Hawk potwierdził skuteczność ataku i wycofał schemat z procesu NIST; zespół stwierdził, że jeśli problem zostanie naprawiony przez podwojenie parametrów, to wspaniała zaleta rozmiaru Hawk całkowicie zniknie.

Raport nadal zawiera rozdział dotyczący Hawk, ponieważ atak dotyczy specyficznych cech algebraicznych danego pola, a nie całkowitego odrzucenia tego paradygmatu projektowego. Nie ma jeszcze pewności, czy ponowne zaprojektowanie może uniknąć tej luki. Incydent Hawk jasno potwierdza nasze przekonanie o konieczności zachowania konserwatywnego marginesu bezpieczeństwa: nawet jeśli schemat ma doskonały rozmiar, dobrą prędkość i przeszedł wiele rund standardyzacji, jeden artykuł może znacznie obniżyć jego przewidywany poziom bezpieczeństwa.

Tabela porównawcza schematów

Wszystkie schematy w powyższej tabeli (w tym SPHINCS+) są podpisami bezstanowymi: podpisujący nie musi rejestrować wcześniejszych podpisów. Podpisy haszujące, takie jak XMSS, mogą osiągnąć mniejsze rozmiary podpisów, ale wymagają utrzymania stanu podpisu; można zapoznać się z raportem na temat podpisów opartych na haszach w celu porównania.

Wdrożenie wciąż napotyka wiele przeszkód

Falcon nie ma dostępnych schematów pochodnych kluczy. Obecnie jedynym publicznie dostępnym schematem pochodnym w stylu BIP-32 dla Falcona, który przeprowadza losowe przekształcenie klucza podstawowego, znacznie zwiększa górny limit normy podpisu, a podpisy na łańcuchu zwiększają się do około 23,7 kilobajta. Ponadto parametry tego schematu nie spełniają własnych warunków bezpieczeństwa, a ich naprawa spowoduje dalszy wzrost rozmiaru. Obecnie nie ma wykonalnej implementacji pochodnych kluczy publicznych Falcona, co jest najcenniejszym problemem do rozwiązania, który przedstawia raport.

Standard Falcona nie został jeszcze sfinalizowany. Chociaż NIST wybrał Falcona, projekt FN-DSA nie został jeszcze formalnie opublikowany. Po zakończeniu standardyzacji przyniesie to audytowane implementacje, wektory testowe i wsparcie na poziomie sprzętowym. Szerokie wdrożenie może zmniejszyć ryzyko i trudności związane z integracją na poziomie konsensusu Bitcoin. Sugerujemy poczekać na oficjalne wydanie FN-DSA, ponieważ do tego czasu Falcon pozostaje w stanie zmiennym.

Wariant Falcon-WS: ten wariant luzuje wewnętrzne parametry, polegając na odrzuceniu próbkowania jako rekompensacie, zmniejszając całkowity rozmiar do 1114 bajtów dla poziomu 1 i 2387 bajtów dla poziomu 5, co w porównaniu do oryginalnego Falcona jeszcze bardziej zmniejsza rozmiar. Ten kierunek ma wartość badawczą, ale nie zostanie uwzględniony w oficjalnym standardzie, wymaga dalszej analizy kryptograficznej. Już przeprowadzono badania, które wykazały, że dowód na silną niemożliwość sfałszowania jego pochodnych ma luki (zwykła niemożliwość sfałszowania nie jest dotknięta).

Czy w przyszłości pojawią się lepsze schematy? Poza powyższymi schematami, seria Fiat-Shamir, która sięga 2013 roku, wprowadza BLISS, a najnowsze osiągnięcia zaprezentowane na konferencji CRYPTO 2025 przez Gärtnera, oparte na dojrzałych założeniach, mogą dorównywać rozmiarom Falcona. Głównym powodem trudności inżynieryjnych w realizacji tej serii jest problem bezpieczeństwa implementacji: BLISS został kiedyś złamany przez atak boczny z powodu próbkowania Gaussa w czasie nie stałym; późniejsze schematy nie rozwiązały tego problemu, a najnowsze osiągnięcia również wskazują na wyższy poziom trudności w ochronie próbkowania. Dopóki te problemy nie zostaną rozwiązane, takie schematy mają jedynie teoretyczną atrakcyjność i nie nadają się do wdrożenia.

Podpisy oparte na siatkach i podpisy haszujące mogą się uzupełniać. Podpisy oparte na siatkach mogą być składnikami mieszanych schematów. Na przykład w SHRINCS, bezstanowa ścieżka odzyskiwania obecnie korzysta z podpisów SPHINCS+ o rozmiarze kilku KB; zastąpienie ich podpisami Falcon (lub Falcon-WS) zmniejsza rozmiar, przyspiesza weryfikację, a niskoczęstotliwościowe koszty ścieżki odzyskiwania znacznie się zmniejszają, nie wpływając na codzienną ścieżkę użytkowania.

Wnioski z badań

Kolejność zalet i wad kandydatów opartych na siatkach jest bardzo wyraźna: Hawk wycofał się z rywalizacji po ataku zespołu Anthropic; Dilithium ma najniższy poziom trudności implementacji i jest jedynym schematem, który ma podstawy badawcze dotyczące pochodnych kluczy, ale jego rozmiar nie jest przyjazny dla kosztów na łańcuchu Bitcoin; Falcon łączy kompaktowy rozmiar, szybką weryfikację i dojrzałe założenia bezpieczeństwa; jego główną słabością - obliczenia zmiennoprzecinkowe na etapie podpisu - ma już wykonalne rozwiązania inżynieryjne. Jeśli teraz musimy wybrać schemat podpisów opartych na siatkach dla Bitcoina, wybierzemy Falcon-1024.

Na chwilę obecną nasze zdanie pozostaje zgodne z raportem na temat podpisów opartych na haszach: krótko-terminowa konserwatywna ścieżka to nadal podpisy oparte na haszach, które mają najbardziej dojrzałe założenia bezpieczeństwa, najmniejsze ryzyko i nadają się jako rozwiązanie przejściowe. Po oficjalnym zatwierdzeniu FN-DSA, z stabilnymi normami, audytowanym kodem i wsparciem portfeli sprzętowych, Falcon przyniesie znaczące korzyści w porównaniu do czysto haszowanych podpisów; można również zastosować mieszane wdrożenie, aby obie klasy systemów podpisów wzajemnie się uzupełniały.

Niniejsza treść ma charakter wyłącznie informacyjny i nie stanowi porady finansowej, inwestycyjnej, prawnej ani podatkowej. Wszelkie wydarzenia, nagrody, promocje online lub powiązane informacje, o których tu mowa, nie powinny być traktowane jako rekomendacja, zachęta ani zaproszenie do kupna, sprzedaży, wymiany lub innego rodzaju obrotu aktywami kryptograficznymi. Aktywa kryptograficzne charakteryzują się dużą zmiennością i mogą prowadzić do strat. Dostępność usług, produktów i powiązanych wydarzeń WEEX może się różnić w zależności od regionu. Użytkownik jest odpowiedzialny za upewnienie się, że jego udział jest zgodny z obowiązującymi lokalnymi przepisami i regulacjami.