Czy możliwe jest generowanie liczb losowych, jeśli nie mamy do siebie zaufania? Część 2

Hej Habra!

В część pierwsza W tym artykule omówiliśmy, dlaczego konieczne może być generowanie liczb losowych dla uczestników, którzy sobie nie ufają, jakie wymagania stawiane są takim generatorom liczb losowych oraz rozważaliśmy dwa podejścia do ich wdrożenia.

W tej części artykułu przyjrzymy się bliżej innemu podejściu, które wykorzystuje podpisy progowe.

Trochę kryptografii

Aby zrozumieć, jak działają podpisy progowe, musisz zrozumieć trochę podstaw kryptografii. Będziemy używać dwóch pojęć: skalarów, czyli po prostu liczb, które będziemy oznaczać małymi literami (x, y) i punkty na krzywej eliptycznej, które będziemy oznaczać dużymi literami.

Aby zrozumieć podstawy sygnatur progowych, nie musisz rozumieć, jak działają krzywe eliptyczne, poza kilkoma podstawowymi rzeczami:

1. Punkty na krzywej eliptycznej można dodawać i mnożyć przez skalar (mnożenie przez skalar będziemy oznaczać jako xG, chociaż oznaczenie Gx często spotykane w literaturze). Wynikiem dodawania i mnożenia przez skalar jest punkt na krzywej eliptycznej.

2. Znając tylko istotę G i jego iloczyn ze skalarem xG nie da się obliczyć x.

Będziemy także używać pojęcia wielomianu p(x) stopień k-1. W szczególności skorzystamy z następującej właściwości wielomianów: jeśli znamy wartość p(x) dla każdego k różny x (i nie mamy więcej informacji na temat p(x)), możemy obliczyć p(x) dla kogokolwiek innego x.

Co ciekawe, dla dowolnego wielomianu p(x) i jakiś punkt na krzywej Gznając znaczenie p(x)G dla każdego k różne znaczenia x, możemy również obliczyć p(x)G dla każdego x.

To wystarczająca informacja, aby zagłębić się w szczegóły działania podpisów progowych i sposobu ich wykorzystania do generowania liczb losowych.

Generator liczb losowych na podpisach progowych

Powiedzmy tak n uczestnicy chcą wygenerować losową liczbę, a my chcemy, aby każdy wziął udział k było ich wystarczająco dużo, aby wygenerować liczbę, ale tak, aby napastnicy kontrolujący k-1 lub mniej uczestników nie było w stanie przewidzieć ani wpłynąć na wygenerowaną liczbę.

Załóżmy, że istnieje taki wielomian p(x) stopień k-1 co wie pierwszy uczestnik p (1), drugi wie p(2), i tak dalej (n-to wie p(n)). Zakładamy to również dla pewnego z góry określonego punktu G każdy wie p(x)G dla wszystkich wartości x. Zadzwonimy Liczba Pi) „element prywatny” iuczestnik (bo tylko isetny uczestnik ją zna) i świnia „element publiczny” i--ta uczestniczka (ponieważ wszyscy uczestnicy ją znają). Jak pamiętacie, wiedza świnia nie wystarczy do przywrócenia Liczba Pi).

Tworzenie takiego wielomianu, aby tylko i-Trzeci uczestnik i nikt inny nie znał jego prywatnego komponentu - to najbardziej złożona i interesująca część protokołu, którą przeanalizujemy poniżej. Załóżmy na razie, że mamy taki wielomian i wszyscy uczestnicy znają swoje składowe prywatne.

Jak możemy użyć takiego wielomianu do wygenerowania liczby losowej? Na początek potrzebujemy łańcucha, który nie był wcześniej używany jako sygnał wejściowy do generatora. W przypadku blockchainu skrót ostatniego bloku h jest dobrym kandydatem na taką linię. Pozwól uczestnikom stworzyć losową liczbę za pomocą h jak ziarno. Uczestnicy dokonują konwersji jako pierwsi h do punktu na krzywej za pomocą dowolnej predefiniowanej funkcji:

H = skalarDoPoint(h)

Następnie każdy uczestnik i oblicza i publikuje Cześć = p(i)H, co mogą zrobić, bo wiedzą p(i) i H. Ujawnienie Hi nie pozwala innym uczestnikom na przywracanie komponentu prywatnego iuczestnika, dlatego w kolejnych blokach można używać jednego zestawu komponentów prywatnych. Zatem opisany poniżej kosztowny algorytm generowania wielomianów wystarczy wykonać tylko raz.

Kiedy k uczestnicy zostali poddani sekcji zwłok Cześć = p(i)H, każdy potrafi liczyć Hx = p(x)H dla wszystkich x dzięki właściwościom wielomianów, które omówiliśmy w ostatniej sekcji. W tym momencie wszyscy uczestnicy wykonują obliczenia H0 = p(0)H, i to jest wynikowa liczba losowa. Proszę pamiętać, że nikt nie wie p(0), i dlatego jest to jedyny sposób obliczenia p(0)H – to jest interpolacja p(x)H, co jest możliwe tylko wtedy, gdy k wartości p(i)H znany. Otwieram każdą mniejszą ilość p(i)H nie podaje żadnych informacji nt p(0)H.

Powyższy generator ma wszystkie pożądane przez nas właściwości: tylko atakujący kontrolujący k-1 lub mniej uczestników nie ma żadnych informacji ani wpływu na wnioski, podczas gdy w ogóle k uczestnicy mogą obliczyć wynikową liczbę i dowolny podzbiór k uczestnicy zawsze uzyskają ten sam wynik dla tego samego materiału siewnego.

Jest jeden problem, którego starannie uniknęliśmy powyżej. Aby interpolacja działała, ważne jest, aby wartość Hi, który został opublikowany przez każdego uczestnika i naprawdę było tak samo p(i)H. Ponieważ nikt poza i-ty uczestnik nie wie Liczba Pi), nikt oprócz i-Uczestnik nie może tego zweryfikować Hi faktycznie obliczone poprawnie i bez żadnego kryptograficznego dowodu poprawności HOsoba atakująca może opublikować dowolną wartość jako Cześć, i dowolnie wpływać na wyjście generatora liczb losowych:

Różne wartości H_1 przesłane przez pierwszego uczestnika prowadzą do różnych wynikowych H_0

Istnieją co najmniej dwa sposoby udowodnienia poprawności Hi, rozważymy je po przeanalizowaniu generowania wielomianu.

Generacja wielomianu

W ostatniej części założyliśmy, że mamy taki wielomian p(x) stopień k-1, że uczestnik i wie Liczba Pi)i nikt inny nie ma żadnych informacji na temat tej wartości. W następnej sekcji będziemy go również potrzebować dla pewnego z góry określonego punktu G wszyscy wiedzieli p(x)G dla wszystkich x.

W tej sekcji założymy, że każdy uczestnik lokalnie ma jakiś klucz prywatny xi, tak, aby każdy znał odpowiedni klucz publiczny Xi.

Jeden z możliwych protokołów generowania wielomianów jest następujący:

1. Każdy uczestnik i lokalnie tworzy dowolny wielomian pi(x) stopień k-1. Następnie wysyłają każdego uczestnika j значение pi(j), zaszyfrowany kluczem publicznym Xj. Tylko w ten sposób i-ый и j-ый uczestnik wie pja(j). Uczestnik i ogłasza także publicznie pi(j)G dla wszystkich j od 1 do k włącznie.

2. Wszyscy uczestnicy dokonują pewnego konsensusu przy wyborze k uczestników, których wielomiany zostaną użyte. Ponieważ niektórzy uczestnicy mogą być offline, nie możemy czekać, aż wszyscy n uczestnicy będą publikować wielomiany. Wynikiem tego kroku jest zbiór Z składający się z co najmniej k wielomiany utworzone w kroku (1).

3. Uczestnicy upewniają się, że znają wartości pi(j) odpowiadają publicznie ogłoszonym pi(j)G. Po tym wejściu Z tylko wielomiany, dla których przesyłane są prywatnie pi(j) odpowiadają publicznie ogłoszonym pi(j)G.

4. Każdy uczestnik j oblicza swój komponent prywatny p(j) jako suma pi(j) dla wszystkich i в Z. Każdy uczestnik oblicza również wszystkie wartości p(x)G jako suma pi(x)G dla wszystkich i в Z.

Uwaga! p(x) – to naprawdę wielomian k-1, ponieważ jest to suma jednostki pi(x), z których każdy jest wielomianem stopnia k-1. Następnie zwróć uwagę, że podczas gdy każdy uczestnik j wie p(j), nie mają o nich żadnych informacji p(x) dla x ≠ j. Rzeczywiście, aby obliczyć tę wartość, muszą wiedzieć wszystko szkatułka), i tak długo, jak uczestnik j nie zna przynajmniej jednego z wybranych wielomianów, o którym nie ma wystarczających informacji p(x).

To jest cały proces generowania wielomianu, który był potrzebny w ostatniej sekcji. Kroki 1, 2 i 4 powyżej mają dość oczywistą implementację. Ale krok 3 nie jest taki trywialny.

W szczególności musimy być w stanie udowodnić, że są one zaszyfrowane pi(j) rzeczywiście odpowiadają opublikowanym pi(j)G. Jeśli nie możemy tego udowodnić, atakujący i zamiast tego mogą wysyłać śmieci pi(j) do uczestnika ji uczestnik j nie będzie w stanie uzyskać prawdziwej wartości pi(j), i nie będzie w stanie obliczyć jego składnika prywatnego.

Istnieje protokół kryptograficzny, który pozwala na utworzenie dodatkowej wiadomości dowódi(j), tak że każdy uczestnik mający jakąś wartość e, oraz dowód(j) и pi(j)G, mogę to sprawdzić lokalnie e - to naprawdę pi(j), szyfrowane kluczem uczestnika j. Niestety rozmiar takiego materiału dowodowego jest niewiarygodnie duży, a biorąc pod uwagę konieczność jego publikacji O(nk) Dowód taki nie może zostać wykorzystany w tym celu.

Zamiast to udowadniać pi(j) odpowiada pi(j)G możemy przeznaczyć w protokole generowania wielomianów bardzo duży okres czasu, podczas którego wszyscy uczestnicy sprawdzają otrzymany zaszyfrowany pi(j), i jeśli odszyfrowana wiadomość nie jest dostępna publicznie pi(j)G, publikują kryptograficzny dowód na to, że otrzymana zaszyfrowana wiadomość jest nieprawidłowa. Udowodnij, że wiadomość nie odpowiada świnia) znacznie łatwiejsze niż udowodnienie, że pasuje. Należy zauważyć, że wymaga to od każdego uczestnika przynajmniej jednego pojawienia się w Internecie w czasie wyznaczonym na utworzenie takiego dowodu i opiera się na założeniu, że jeśli opublikuje taki dowód, dotrze on do wszystkich pozostałych uczestników w tym samym wyznaczonym czasie.

Jeżeli w tym czasie uczestnik nie pojawił się online, a chociaż jeden jego element był błędny, to dany uczestnik nie będzie mógł brać udziału w dalszym generowaniu numeru. Protokół będzie jednak nadal działał, jeśli przynajmniej istnieje k uczestników, którzy albo właśnie otrzymali właściwe komponenty, albo zdołali w wyznaczonym czasie zostawić dowód nieprawidłowości.

Dowody poprawności H_i

Ostatnią częścią, która pozostaje do omówienia, jest sposób udowodnienia poprawności opublikowanej publikacji Hja, mianowicie to Cześć = p(i)H, bez otwierania Liczba Pi).

Pamiętajmy, że wartości H, G, p(i)G publiczne i znane wszystkim. Odbierz operację Liczba Pi) porozumiewawczy świnia и G zwany logarytmem dyskretnym, lub dlog, i chcemy to udowodnić:

dlog(p(i)G, G) = dlog(Hi, H)

bez ujawnienia Liczba Pi). Istnieją na przykład konstrukcje takich dowodów Protokół Schnorra.

Dzięki temu projektowi każdy uczestnik wraz z Hi przesyła dowód poprawności wykonania zgodnie z projektem.

Po wygenerowaniu liczby losowej często muszą z niej skorzystać uczestnicy inni niż ci, którzy ją wygenerowali. Uczestnicy tacy wraz z numerem muszą wysłać całość Hi i powiązane dowody.

Dociekliwy czytelnik może zapytać: skoro ostateczna liczba losowa to H0 i p(0)G – To jest informacja publiczna, po co nam dowód na każdą osobę Hzamiast tego może wysłać dowód

dlog(p(0)G, G) = dlog(H0, H)

Problem w tym, że takiego dowodu nie można utworzyć przy użyciu protokołu Schnorra, ponieważ nikt nie zna jego wartości p (0), niezbędny do stworzenia dowodu, a co więcej, cały generator liczb losowych opiera się na tym, że nikt nie zna tej wartości. Dlatego konieczne jest posiadanie wszystkich wartości Hi oraz ich indywidualne dowody potwierdzające prawidłowość H0.

Gdyby jednak na punktach krzywych eliptycznych istniała jakaś operacja semantycznie podobna do mnożenia, dowodem poprawności H0 byłoby trywialne, po prostu się o to upewniliśmy

H0 × G = p(0)G × H

Jeśli wybrana krzywa obsługuje parowanie krzywych eliptycznych, ten dowód działa. W tym przypadku H0 to nie tylko wynik generatora liczb losowych, który może zweryfikować każdy, kto się na tym zna G, H и p(0)G. H0 to także podpis w wiadomości, który został użyty jako materiał siewny, potwierdzający to k и n uczestnicy podpisali tę wiadomość. Zatem jeśli nasionko - jest zatem skrótem bloku w protokole blockchain H0 jest zarówno wielokrotnym podpisem w bloku, jak i bardzo dobrą liczbą losową.

Na zakończenie

Ten artykuł jest częścią serii blogów technicznych BLISKO. NEAR to protokół i platforma blockchain do tworzenia zdecentralizowanych aplikacji, z naciskiem na łatwość programowania i łatwość użytkowania dla użytkowników końcowych.

Kod protokołu jest otwarty, nasza implementacja jest napisana w Rust, można ją znaleźć tutaj.

Możesz zobaczyć, jak wygląda rozwój NEAR i poeksperymentować w internetowym środowisku IDE tutaj.

Wszystkie aktualności w języku rosyjskim można śledzić pod adresem grupa telegramów i grupa na VKontakteoraz w języku angielskim w wersji oficjalnej świergot.

Do zobaczenia wkrótce!

Źródło: www.habr.com