Cześć, Habr!
W W artykule omówiliśmy, dlaczego generowanie liczb losowych może być konieczne dla uczestników, którzy sobie nie ufają, jakie wymagania są stawiane takim generatorom losowym oraz rozważyliśmy dwa podejścia do ich implementacji.
W tej części artykułu szczegółowo przyjrzymy się jeszcze jednemu podejściu, które wykorzystuje podpisy progu.
Trochę kryptografii
Aby zrozumieć, jak działają podpisy progu, trzeba znać trochę podstawowej kryptografii. Będziemy używać dwóch koncepcji: skalarów, czyli po prostu liczb, które będziemy oznaczać małymi literami (x, y) oraz punktów na krzywej eliptycznej, które będziemy oznaczać wielkimi literami.
Do zrozumienia podstaw podpisów progowych nie trzeba znać, jak działają krzywe eliptyczne, poza kilkoma podstawowymi rzeczami:
Punkty na krzywej eliptycznej można dodawać i mnożyć przez skalar (mnożenie przez skalar będziemy oznaczać jako xG, chociaż notacja Gx również często występuje w literaturze). Wynik dodawania i mnożenia przez skalar to punkt na krzywej eliptycznej.
Znając tylko punkt G i jego iloczyn ze skalarem xG nie można obliczyć x.
Będziemy również korzystać z koncepcji wielomianu p(x) o stopniu k-1. W szczególności będziemy używać następującej właściwości wielomianów: jeśli znamy wartość p(x) dla dowolnych k różnych x (i nie mamy więcej żadnych informacji o p(x)), możemy obliczyć p(x) dla dowolnego innego x.
Ciekawe, że dla dowolnego wielomianu p(x) i pewnego punktu na krzywej G, znając wartość p(x)G dla dowolnych k różnych wartości x, można także obliczyć p(x)G dla dowolnego x.
Te informacje wystarczą, aby zagłębić się w szczegóły działania podpisów progowych i ich wykorzystania do generowania liczb losowych.
Generator liczb losowych oparty na podpisach progowych
Załóżmy, że n uczestnicy chcą wygenerować liczbę losową, a my chcemy, aby udział dowolnych k z nich był wystarczający do wygenerowania liczby, ale aby intruzi, którzy kontrolują k-1 lub mniej uczestników, nie mogli przewidzieć ani wpłynąć na wygenerowaną liczbę.
Załóżmy, że istnieje taki wielomian p(x) o stopniu k-1, że pierwszy uczestnik zna p(1), drugi zna p(2), i tak dalej (n-ty zna p(n)). Załóżmy również, że dla pewnego wcześniej określonego punktu G wszyscy znają p(x)G dla wszystkich wartości x. Będziemy nazywać p(i) „prywatnym komponentem” i-go uczestnika (bo tylko i-y uczestnik zna go), i p(i)G „publicznym komponentem” i-go uczestnika (bo wszyscy uczestnicy go znają). Jak pamiętacie, wiedza p(i)G nie wystarcza do odtworzenia p(i).
Stworzenie takiego wielomianu w taki sposób, aby tylko i--y uczestnik znał swoją prywatną komponentę – to najtrudniejsza i najciekawsza część protokołu, i omówimy to poniżej. Na razie przyjmijmy, że taki wielomian istnieje, a wszyscy uczestnicy znają swoje prywatne komponenty.
Jak możemy wykorzystać taki wielomian do wygenerowania liczby losowej? Na początek potrzebujemy jakiegoś ciągu, który wcześniej nie był używany jako wejście dla generatora. W przypadku blockchaina hash ostatniego bloku h – dobry kandydat na taki ciąg. Niech uczestnicy chcą stworzyć liczbę losową, korzystając h jako nasion. Najpierw uczestnicy konwertują h na punkt na krzywej, korzystając z dowolnej z góry określonej funkcji:
H = scalarToPoint(h)
Następnie każdy uczestnik i oblicza i publikuje Hi = p(i)H, co mogą zrobić, ponieważ znają p(i) i H. Ujawnienie Hi nie pozwala innym uczestnikom odtworzyć prywatnej komponenty i-go uczestnika, i dlatego jeden zestaw prywatnych komponentów można używać od bloku do bloku. W ten sposób drogi algorytm tworzenia wielomianu, opisany poniżej, należy wykonać tylko raz.
Kiedy k uczestnicy ujawnili Hi = p(i)H, wszyscy mogą obliczyć Hx = p(x)H dla wszystkich x dzięki właściwościom wielomianów, które omówiliśmy w poprzedniej sekcji. W tym momencie wszyscy uczestnicy obliczają H0 = p(0)H, i to jest wynikowa liczba losowa. Zauważ, że nikt nie zna p(0), a zatem jedynym sposobem na obliczenie p(0)H – jest interpolacja p(x)H, co jest możliwe tylko wtedy, gdy k wartości p(i)H są znane. Ujawnienie jakiejkolwiek mniejszej liczby p(i)H nie daje żadnych informacji o p(0)H.
Generator powyżej ma wszystkie właściwości, których chcemy: napastnicy, kontrolujący tylko k-1 uczestników, lub mniej, nie mają żadnych informacji ani wpływu na wynik, podczas gdy jakiekolwiek k uczestników mogą obliczyć wynikową liczbę, a dowolny podzbiór z k uczestników zawsze dojdzie do tego samego wyniku dla tego samego nasiona.
Jest jeden problem, który subtelnie pominęliśmy powyżej. Aby interpolacja działała, ważne jest, aby wartość Hi opublikowana przez każdego uczestnika i rzeczywiście była równa p(i)H. Ponieważ nikt oprócz i-go uczestnika nie wie p(i), nikt oprócz i--go uczestnika nie może zweryfikować, że Cześć rzeczywiście zostało policzone poprawnie, a bez jakiegoś kryptograficznego dowodu poprawności Hi haker może opublikować dowolną wartość jako Cześć, i dowolnie wpływać na wynik generatora liczb losowych:
Różne wartości H_1 przesyłane przez pierwszego uczestnika prowadzą do różnych wynikowych H_0
Istnieją co najmniej dwa sposoby udowodnienia poprawności Hi, omówimy je po omówieniu generacji wielomianu.
Generacja wielomianu
W poprzedniej sekcji przyjęliśmy, że mamy taki wielomian p(x) o stopniu k-1, że uczestnik i wie p(i), a nikt inny nie ma żadnej informacji o tej wartości. W następnej sekcji będziemy również musieli, aby dla pewnego z góry ustalonego punktu G wszyscy wiedzieli p(x)G dla wszystkich x.
W tej sekcji będziemy zakładać, że każdy uczestnik ma lokalnie pewien prywatny klucz xi, taki, że wszystkim znany jest odpowiadający mu klucz publiczny Xi.
Jeden z możliwych protokołów generowania wielomianu jest następujący:
Każdy uczestnik i lokalnie tworzy losowy wielomian pi(x) stopnia k-1. Następnie wysyłają każdemu uczestnikowi j wartość pi(j), zaszyfrowane kluczem publicznym Xj. W ten sposób tylko i-y i j-y uczestnik wie pi(j). Uczestnik i również publicznie ogłasza pi(j)G dla wszystkich j od 1 do k łącznie.
Wszyscy uczestnicy korzystają z pewnego konsensusu, aby wybrać k uczestników, których wielomiany będą używane. Ponieważ niektórzy uczestnicy mogą być offline, nie możemy czekać, aż wszyscy n uczestnicy opublikują wielomiany. Wynikiem tego kroku jest zbiór Z składający się z co najmniej k wielomianów utworzonych w kroku (1).
Uczestnicy upewniają się, że znane im wartości pi(j) odpowiadają publicznie ogłoszonym pi(j)G. Po tym kroku w Z powinny pozostać tylko wielomiany, dla których prywatnie przekazane pi(j) odpowiadają publicznie ogłoszonym pi(j)G.
Każdy uczestnik j oblicza swoją prywatną komponentę p(j) jako sumę pi(j) dla wszystkich i do Z. Każdy uczestnik także oblicza wszystkie wartości p(x)G jako sumę pi(x)G dla wszystkich i do Z.
Zauważ, że p(x) – to rzeczywiście wielomian stopnia k-1, ponieważ jest to suma poszczególnych pi(x), z których każda jest wielomianem stopnia k-1. Następnie zwróć uwagę, że chociaż każdy uczestnik j wie p(j), nie mają żadnych informacji o p(x) do x ≠ j. Rzeczywiście, aby obliczyć tę wartość, muszą znać wszystkie pi(x), i dopóki uczestnik j nie zna przynajmniej jednego z wybranych wielomianów, nie mają wystarczających informacji o p(x).
To cały proces generowania wielomianu, który był niezbędny w poprzedniej sekcji. Kroki 1, 2 i 4 powyżej mają dość oczywistą realizację. Natomiast krok 3 nie jest taki trywialny.
Konkretnie, musimy być w stanie udowodnić, że zaszyfrowane pi(j) rzeczywiście odpowiadają opublikowanym pi(j)G. Jeśli nie możemy tego udowodnić, napastnik i może wysłać śmieci zamiast pi(j) uczestnikowi j, a uczestnik j nie będzie w stanie uzyskać rzeczywistej wartości pi(j), i nie będzie mógł obliczyć swojego prywatnego komponentu.
Istnieje protokół kryptograficzny, który pozwala na stworzenie dodatkowej wiadomości proofi(j), tak że każdy uczestnik, mając pewną wartość e, a także proofi(j) i pi(j)G, może lokalnie upewnić się, że e – to rzeczywiście pi(j), zaszyfrowany kluczem uczestnika j. Niestety, rozmiar takiego dowodu jest niesamowicie duży i biorąc pod uwagę, że trzeba opublikować O(nk) takich dowodów, nie da się ich wykorzystać do tego celu.
Zamiast udowadniać, że pi(j) -the node, and the other — pi(j)G możemy w protokole generowania wielomianu poświęcić bardzo długi czas, podczas którego wszyscy uczestnicy sprawdzają otrzymane zaszyfrowane pi(j), i jeśli odszyfrowana wiadomość nie odpowiada publicznemu pi(j)G, publikują kryptograficzny dowód tego, że otrzymana przez nich zaszyfrowana wiadomość jest nieprawidłowa. Udowodnienie, że wiadomość nie -the node, and the other — pi(G) jest znacznie prostsze niż udowodnienie, że odpowiada. Należy zauważyć, że to wymaga, aby każdy uczestnik pojawił się w sieci przynajmniej raz w czasie przeznaczonym na tworzenie takich dowodów i polega na założeniu, że jeśli opublikowali taki dowód, dotrze on do wszystkich pozostałych uczestników w tym samym czasie.
Jeśli uczestnik nie pojawi się w sieci w tym czasie, a na pewno miał przynajmniej jeden nieprawidłowy komponent, to ten konkretny uczestnik nie będzie mógł uczestniczyć w dalszej generacji liczb. Protokół jednak nadal będzie działać, jeśli przynajmniej k uczestników, którzy albo właśnie otrzymali poprawne komponenty, albo zdążyli pozostawić dowody niepoprawności w wyznaczonym czasie.
Dowody poprawności H_i
Ostatnia część, którą trzeba omówić, to jak udowodnić poprawność opublikowanych Hi, a mianowicie że Hi = p(i)H, bez ujawniania p(i).
Przypomnijmy, że wartości H, G, p(i)G są publiczne i znane wszystkim. Operacja otrzymywania p(i) znając p(i)G i G nazywana jest dyskretnym logarytmem, lub dlog, i chcemy udowodnić, że:
dlog(p(i)G, G) = dlog(Hi, H)
bez ujawniania p(i). Konstrukcje dla takich dowodów istnieją, na przykład.
Z taką konstrukcją każdy uczestnik wspólnie z Cześć wysyła dowód poprawności zgodnie z konstrukcją.
Kiedy losowa liczba jest generowana, często musi być używana przez uczestników innych niż ci, którzy ją wygenerowali. Takim uczestnikom wraz z liczbą należy wysłać wszystkie Cześć i towarzyszące dowody.
Dociekliwy czytelnik może zapytać: dlaczego końcowa losowa liczba to H0, a p(0)G – to publiczna informacja, dlaczego potrzebny jest dowód dla każdego pojedynczego Hi, dlaczego zamiast tego nie wysłać dowodu, że
dlog(p(0)G, G) = dlog(H0, H)
Problem polega na tym, że za pomocą Schnorr Protocol nie można stworzyć takiego dowodu, ponieważ nikt nie zna wartości p(0), niezbędnej do stworzenia dowodu, a co więcej, cały generator losowych liczb oparty jest na tym, że nikt nie zna tej wartości. Dlatego należy mieć wszystkie wartości Cześć i ich indywidualne dowody, aby udowodnić poprawność. H0.
Jednak, gdyby na punktach na krzywych eliptycznych istniała jakaś operacja, która semantycznie przypominałaby mnożenie, dowód poprawności H0 byłby trywialny, po prostu upewnilibyśmy się, że
H0 × G = p(0)G × H
Jeśli wybrana krzywa wspiera , taki dowód działa. W takim przypadku H0 – to nie tylko wynik generatora losowych liczb, który może sprawdzić każdy uczestnik, który zna G, H i p(0)G. H0 – to także podpis na wiadomości, która została użyta jako seed, potwierdzająca, że k i n uczestnicy podpisali tę wiadomość. Tak więc, jeśli seed – to hash bloku w protokole blockchain, to H0 – to jednocześnie multi-podpis na bloku, i bardzo dobry losowy numer.
Na zakończenie
Ten artykuł jest częścią serii artykułów technicznych na blogu . NEAR – to protokół blockchain i platforma do tworzenia zdecentralizowanych aplikacji, z naciskiem na prostotę rozwoju i łatwość użytkowania dla końcowych użytkowników.
Kod protokołu jest otwarty, nasza implementacja jest napisana w Rust, można ją znaleźć .
Można zobaczyć, jak wygląda rozwój na platformie NEAR oraz wypróbować w online-IDE .
Śledzić wszystkie wiadomości w języku rosyjskim można w i w , a po angielsku na oficjalnym .
Do zobaczenia wkrótce!
Źródło: habr.com
