Sortowanie kryptograficzne w łańcuchach blokowych: znaczenie VRF

Kiedy krypto może być graczem systemowym

Gdy czytam i rozumiem coraz więcej na temat technologii blockchain w ramach mojej pracy naukowej w Witnet, zaczynam zdawać sobie sprawę z znaczenia protokołów i schematów kryptograficznych dla ich projektów. To niesamowite, jak niewielka decyzja projektowa może wpłynąć na sposób interakcji użytkowników z systemem i potencjalnie z niego skorzystać.

W tym poście chciałbym podzielić się niektórymi wewnętrznymi badaniami, które przeprowadziliśmy w Witnet, oraz tym, w jaki sposób zdaliśmy sobie sprawę, że nasze założenia kryptograficzne nie były wystarczająco mocne do naszych początkowych celów.

PoE jako część Protokołów Blockchain

Dowody uprawnień (PoE) stają się coraz bardziej popularne w technologii Blockchain. W rzeczywistości dokumenty PoE pozwalają nam decydować, kto jest odpowiedzialny za wykonanie akcji. Kiedy kwalifikacje są odkrywane przez każdego uczestnika indywidualnie, zwykle nazywamy go kryptograficznym schematem sortowania, tj. Umiejętnością odkrycia, czy sam jesteś zwycięzcą „loterii”.

Istnieje kilka właściwości, które sortowanie kryptograficzne musi wypełnić. Po pierwsze, węzły indywidualnie powinny być w stanie ustalić, czy są uprawnione do wykonania określonej akcji. Po drugie, kwalifikowalność powinna być weryfikowalna kryptograficznie przez innych użytkowników. Po trzecie, sortowanie kryptograficzne jest powiązane z pojedynczą tożsamością, tzn. Elementy równorzędne muszą się upewnić, że dowód został wygenerowany przez element równorzędny, który go żąda. Dodatkowo chciałoby się również, aby dowód był nierozróżnialny od przypadkowego.

Zauważyliśmy kilka schematów sortowania kryptograficznego proponowanych jako część projektu blockchain, od dobrze znanego Dowodu Pracy w Bitcoin po nowe propozycje, takie jak np. Algorand, Filecoin lub Witnet. W tym poście skupię się na sortowaniu kryptograficznym opisanym w Witnet i jego możliwych ulepszeniach. Mam nadzieję, że zamieszczone tutaj informacje są pomocne dla innych łańcuchów bloków o tym samym celu.

Sortowanie kryptograficzne na podstawie podpisów cyfrowych

Zazwyczaj schematy sortowania kryptograficznego opierają swoje uprawnienia na szczęściu zdobycia losowej liczby, która spada poniżej określonej wartości docelowej. Trudność zależy oczywiście od wartości docelowej; im wyższa wartość, tym większe szanse, że rówieśnicy będą musieli się kwalifikować. Wartość docelowa może być różna dla różnych partnerów, być może w zależności od tego, jak dobrze zachowali się w poprzednich zadaniach. Właśnie takie podejście opisuje Witnet. Sortowanie kryptograficzne w Witnet jest zdefiniowane jako:

Sortowanie kryptograficzne w Witnet

Gdzie <> oznacza podpis nad klawiszem M, a I odnosi się do wpływu peera i w czasie t. Wpływ dotyczy reputacji węzła, tj. Tego, jak dobrze zachowywał się w poprzednich zadaniach. Zasadniczo, jeśli wartość skrótu podpisu zadania, które peer chce wykonać, spadnie poniżej wartości docelowej, wówczas staje się uprawniona do wykonania zadania. Obserwujemy, w jaki sposób każdy uczestnik może indywidualnie ustalić swój podział bez interakcji z jakimkolwiek innym uczestnikiem w sieci. Losowa wartość jest commont dla wszystkich peerów (może to być skrót poprzedniego bloku).

Aby zweryfikować kwalifikowalność węzła, pozostałe węzły najpierw sprawdzają, czy podpis został wygenerowany z odpowiednimi parametrami (wartość losowa związana z bieżącą epoką i zadaniem, dla którego węzeł wybiera). Następnie mieszają podpis, aby zobaczyć, czy spadnie poniżej wartości docelowej. Jeśli tak, sprawdzana jest kwalifikacja partnera do zadania.

Sortowania kryptograficzne oparte na podpisach cyfrowych (tj. Podpisie danej wiadomości) wypełniają wyżej zdefiniowane instrukcje: są generowane przez danego partnera, są weryfikowalne za pomocą klucza publicznego, a ich wyniki wydają się losowe bez klucza publicznego.

Ale schematy sortowania kryptograficznego oparte na podpisie cyfrowym mają tendencję do spełnienia (jak w Witnet) kolejnego wymogu, o którym nie wspomniałem: każdy uczestnik powinien mieć jedną szansę na przesłanie wiadomości wejściowej. W przeciwnym razie rówieśnicy mogą po prostu uruchomić loterię tyle razy, ile chcą, dopóki nie zostaną zakwalifikowani. Pytanie, które zadaliśmy sobie w Witnet, brzmiało: czy podpisy cyfrowe wypełniają tę właściwość?

Problem: nieunikalny wynik dla ECDSA

Zanim udzielę odpowiedzi na poprzednie pytanie, pozwólcie, że krótko przedstawię działanie kryptografii krzywej eliptycznej.

Krótko mówiąc, Elliptic Curve Cryptography (ECC) to kryptosystem klucza publicznego, w którym każdy uczestnik posiada parę kluczy prywatny-publiczny. Klucz prywatny jest znany tylko właścicielowi, a klucz publiczny jest znany każdemu uczestnikowi. Uczestnicy komunikacji muszą najpierw zgodzić się co do krzywej ECC
zamierzają wykorzystać. Krzywa jest tylko zbiorem punktów określonych równaniem,
np. y ^ 2 = x ^ 3 + ax + b. Krzywa jest definiowana, między innymi, przez punkt generatora, dzięki któremu możemy dotrzeć do dowolnego innego punktu na krzywej. Aby zbudować taki system, ECC konstruuje następującą arytmetykę:

  • jeśli P jest punktem na krzywej, -P jest jego odbiciem nad osią x
  • jeżeli dwa punkty P i Q są różne, to wynikiem dodania P i Q jest
    obliczone przez narysowanie linii przecinającej P i Q, która przecina się w a
    trzeci punkt -R na krzywej. R oblicza się biorąc odbicie -R
    w odniesieniu do osi x.
  • P + P oblicza się, rysując linię styczną do krzywej w punkcie P, który
    znowu przecina się w trzecim punkcie krzywej -2P. 2P to po prostu
    odbicie nad osią x
Przykład dodawania krzywej eliptycznej

Zauważ, że za pomocą tej arytmetyki możemy już dodawać punkty, a tym samym pomnożyć punkty za pomocą eskalarów (5P to tylko 2P + 2P + P). Para klucz prywatny-publiczny jest tworzona przez wybranie najpierw losowej liczby całkowitej, która będzie nam służyć kluczem prywatnym. Klucz publiczny to tylko pomnożenie liczby całkowitej z punktem generatora. Bezpieczeństwo systemu zależy od trudności lub pobrania liczby całkowitej, która pochodzi z punktu klucza publicznego. To jest, biorąc pod uwagę klucz publiczny Q, problem ze znalezieniem liczby całkowitej k, która zwielokrotniła generator do osiągnięcia Q, jest równoważna Problemowi Logarytmu Dyskretnego.

Przy takim systemie można już wykonać kilka podejść kryptograficznych. Jedną z nich jest możliwość generowania podpisów cyfrowych. Ogólny obraz generowania sygnałów ECDSA można zobaczyć na poniższym zdjęciu

Generowanie podpisu ECDSA

Zasadniczo komunikat wejściowy m jest najpierw mieszany. Później wybiera się liczbę losową u, która po pomnożeniu przez punkt generatora G odwzorowuje na punkt na krzywej, którego współrzędna x wynosi 0. Jeśli warunek ten nie jest spełniony, wartość u jest wybierana ponownie. Jeśli tak, to odwrotność u mnoży się przez (e + dr), aż wartość będzie niezerowa. Podpis jest krotką (r, s).

W rzeczywistości nie musimy w pełni rozumieć algorytmu, aby zdać sobie sprawę, że podpis (r, s) silnie zależy od wartości losowej u wybranej w linii 5. Oznacza to, że wartość podpisu będzie zależeć od wartości losowej, a zatem dana wiadomość może być odwzorowana na kilka różnych podpisów.

Jest to już sprzeczne z tym, co idealnie opisaliśmy dla sortowania kryptograficznego. Jeśli uprawnienia peera będą zależeć od skrótu podpisu, który może przyjmować różne wartości w zależności od wybranej losowej wartości, możemy spodziewać się, że peery będą stale obliczać podpisy, dopóki nie znajdą takiego, dla którego skrót jest wystarczająco niski, a zatem stać się uprawnionym. Co ciekawe, zastosowany schemat kryptograficzny daje rówieśnikom możliwość gry w system.

Rozwiązanie: VRF jako sortowanie kryptograficzne

Pomimo wspomnianego problemu nie chcielibyśmy rezygnować ze wszystkich zalet, jakie podpisy cyfrowe oferują naszemu programowi. Dlatego musimy dodać właściwość unikalności do naszej sortowania kryptograficznego, tak jakby była to „wersja klucza publicznego HMAC z kluczem”. Sprawdzone funkcje losowe (VRF) wydają się załatwić sprawę (w rzeczywistości są używane w Algorand). VRF zostały po raz pierwszy wprowadzone przez Silvio Micali w [1]. VRF generują dwa wyjścia: tak zwaną „unikalną sygnaturę” β i dowód π. Oprócz tego, że były kryptosystemem klucza publicznego, mają następujące właściwości:

  • Odporność na kolizję, tzn. Trudno jest znaleźć dwa wejścia, które odwzorowują to samo wyjście.
  • Pseudolosowość, tj. Wynik jest nie do odróżnienia od losowej przez każdego, kto nie zna tajnego klucza.
  • Zaufana wyjątkowość, która wymaga, aby przy danym kluczu publicznym wejście VRF m odpowiadało unikalnemu wyjściu β.

Ostatnie stwierdzenie jest dość ważne. Oznacza to, że β będzie zawsze unikalne dla danego komunikatu wejściowego i klucza publicznego, podczas gdy dowód może być losowy. Tak więc peery nie mogą wygenerować kilku podpisów, dopóki nie osiągną wystarczająco niskiej wartości, ponieważ dla tego samego wejścia zawsze będą miały tę samą wartość. Oznacza to, że uruchamiają loterię tylko raz na komunikat wejściowy.

Przykład VRF

Pytanie oczywiście dotyczy tego, jak skonstruować te schematy. Postępujemy zgodnie ze schematem zaproponowanym w [2], który opisuje konstrukcje VRF zarówno dla RSA, jak i ECC. Ze względu na zwięzłość pomijamy opis konstrukcji RSA. W rzeczywistości ECC oferuje zalety schematów kryptograficznych pod względem wielkości klucza i podpisu w porównaniu z RSA, aby osiągnąć ten sam poziom bezpieczeństwa.

Algorytm weryfikacji podpisu ECC-VRF można zobaczyć poniżej. ECVRF_hash_to_curve to funkcja mieszająca liczbę całkowitą do punktu na krzywej. Przeciwnie, ECVRF_hash_points jest funkcją, która łączy kilka punktów na krzywej do liczby całkowitej. Za pomocą tych dwóch funkcji pomocniczych możemy skonstruować następujący schemat generowania sygnatur:

Generacja odporna na ECC-VRF

Dane wyjściowe β są następnie mieszane, aby sprawdzić, czy skrót znajduje się poniżej wartości docelowej, podczas gdy weryfikator π jest używany przez weryfikatora, aby sprawdzić, czy dane wyjściowe rzeczywiście zostały obliczone z powiązanym kluczem publicznym i dla danego komunikatu w następujący sposób:

Weryfikacja ECC-VRF

Jeśli spojrzymy na algorytm, i tylko wtedy, gdy c 'jest równe c, dowód jest weryfikowany. Porównując krok 15 z weryfikacji i krok 4 z generowania podpisu, widzimy, że równość będzie obowiązywać, dopóki u = Gt i v = Ht. Czy weryfikator może to sprawdzić bez znajomości tajnego klucza k? Poniżej wykazujemy poprawność równości:

  • Wartość u = Qc + Gs = Qc + G (t-kc) = Qc + Gt-Gkc = Qc + Gt -Qc = Gt
  • Wartość v = βc + Hs = βc + H (t-kc) = βc + Ht-Hkc = βc + Ht-βc = Ht

Można zweryfikować, czy równość obowiązuje bez konieczności poznania tajnej wartości k.

Wnioski

W tym poście podzieliłem się, dlaczego schematy sortowania kryptograficznego oparte na podpisie cyfrowym mogą stanowić dużą zachętę dla rówieśników do grania w system, zwłaszcza gdy od nich zależy kwalifikowalność do zadania. W przypadku Witnet zarówno zadania wyszukiwania, jak i żądania danych zależą od wyniku sortowania, a zatem nie możemy stanowić takiej zachęty dla rówieśników. Możemy dojść do sytuacji, w której wynagrodzenie za żądanie danych jest wystarczająco wysokie, aby zachęcić partnerów do ciągłego generowania dla niego podpisów, dopóki skrót nie będzie wystarczająco niski, wykonując w ten sposób rodzaj Dowodu pracy niewystarczający dla żądań danych. W rzeczywistości, jeśli węzły przełożą wszystkie zasoby na hojne żądanie danych, reszta zostanie zapomniana, a wydajność systemu zostanie poważnie ograniczona.

Weryfikowalne funkcje losowe wydają się rozwiązać problem opisany powyżej. Rzeczywiście zachowują wszystkie zalety podpisów cyfrowych, z dodatkowym faktem: „podpis” jest unikalny dla danego klucza publicznego i wiadomości. Dodatkowo VRF generują dowód, dzięki któremu weryfikator może sprawdzić ważność transakcji. Dlatego VRF wydaje się właściwym podejściem do systemów takich jak Witnet.

Bibliografia

  • https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
  • https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/Verifiable_Random_Functions.pdf
  • https://filecoin.io/filecoin.pdf
  • https://witnet.io/static/witnet-whitepaper.pdf
  • https://eprint.iacr.org/2017/099.pdf
  • https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03