Autor: Gwiazda Li

Ten artykuł służy wyłącznie do celów uczenia się i wymiany informacji w branży i nie stanowi żadnego odniesienia inwestycyjnego. Jeśli chcesz zacytować, proszę podać źródło. W celu przedruku skontaktuj się z zespołem IOSG w celu uzyskania instrukcji dotyczących autoryzacji i przedruku. Specjalne podziękowania dla autora Star Li za treść!

Technologia dowodu wiedzy zerowej jest coraz częściej stosowana w zabezpieczeniach prywatności, obliczeniach, konsensusie itp. Poszukując większej liczby lepszych scenariuszy zastosowań, wiele osób stopniowo odkrywało, że wąskim gardłem jest wydajność oparta na wiedzy zerowej. Zespół Trapdoor Tech rozpoczął dogłębne badania nad technologią dowodu zerowej wiedzy w 2019 roku i bada wydajne rozwiązania akceleracyjne odporne na wiedzę zerową. GPU lub FPGA to popularne platformy akceleracyjne dostępne obecnie na rynku. Artykuł rozpoczyna się od obliczenia MSM i analizuje zalety i wady obliczeń dowodu z wiedzą zerową przyspieszanych przez FPGA i GPU.

TL;DR

ZKP to technologia z szerokimi perspektywami na przyszłość. Coraz więcej aplikacji zaczyna wykorzystywać technologię wiedzy zerowej. Algorytmów ZKP jest jednak wiele i różne projekty wykorzystują różne algorytmy ZKP. Jednocześnie wydajność obliczeniowa dowodu ZKP jest stosunkowo słaba. W tym artykule szczegółowo przeanalizowano algorytm MSM, algorytm dodawania punktów krzywej eliptycznej, algorytm mnożenia Montgomery'ego itp. oraz porównano różnicę wydajności między GPU i FPGA w dodawaniu punktów krzywej BLS12_381. Ogólnie rzecz biorąc, jeśli chodzi o obliczenia dowódowe ZKP, krótkoterminowe zalety GPU są stosunkowo oczywiste, takie jak wysoka przepustowość, wysoka wydajność kosztowa, programowalność itp. FPGA ma pewne zalety pod względem zużycia energii. W dłuższej perspektywie mogą pojawić się chipy FPGA odpowiednie do obliczeń ZKP lub chipy ASIC dostosowane do ZKP.

Algorytm ZKP jest złożony

ZKP to zbiorcza nazwa technologii zero-knowledge proof (Zero Knowledge Proof). Istnieją dwie główne kategorie: zk-SNARK i zk-STARK. Obecnie powszechnymi algorytmami dla zk-SNARK są Groth16, PLONK, PLOOKUP, Marlin i Halo/Halo2. Iteracja algorytmu zk-SNARK przebiega głównie w dwóch kierunkach: 1/czy wymagana jest zaufana konfiguracja 2/wydajność struktury obwodu. Zaletą algorytmu zk-STARK jest to, że nie wymaga on zaufanej konfiguracji, ale wielkość obliczeń weryfikacyjnych jest logarytmicznie liniowa.

Pod względem zastosowania algorytmu zk-SNARK/zk-STARK algorytmy dowodu o wiedzy zerowej stosowane w różnych projektach są stosunkowo rozproszone. W zastosowaniu algorytmu zk-SNARK, ponieważ algorytm PLONK/Halo2 jest uniwersalny (nie jest wymagana żadna zaufana konfiguracja), zastosowań może być coraz więcej.

PLONK to wysiłek obliczeniowy

Weźmy na przykład algorytm PLONK, aby przeanalizować kwotę obliczeniową dowodu PLONK.

Kwota obliczeniowa części dowódowej PLONK składa się z czterech części:

1/ MSM - Wielokrotne mnożenie skalarne. MSM jest często używany do obliczania zobowiązań wielomianowych.

2/ Obliczenie NTT – wielomian przekształca wartość punktową i reprezentację współczynnika.

3/ Obliczenia wielomianowe - Dodawanie, odejmowanie, mnożenie i dzielenie wielomianów. Ocena wielomianowa (Ocena) i tak dalej.

4/ Synteza obwodów - Synteza obwodów. Ta część obliczeń jest związana z rozmiarem/złożonością obwodu.

Ogólnie rzecz biorąc, wielkość obliczeń części Synteza obwodów opiera się na ocenie i logice pętli, stopień równoległości jest stosunkowo niski i jest bardziej odpowiedni do obliczeń procesora. Ogólnie rzecz biorąc, przyspieszenie dowodu z wiedzą zerową ogólnie odnosi się do przyspieszenia obliczeń pierwszych trzech części. Wśród nich MSM ma stosunkowo największą liczbę obliczeń, a następnie NTT.

Co to jest MSM?

MSM (Multiple Scalar Multiplication) odnosi się do danego ciągu punktów i skalarów na krzywej eliptycznej i oblicza punkt odpowiadający wynikowi dodania tych punktów.

Na przykład, biorąc pod uwagę szereg punktów na krzywej eliptycznej:

Biorąc pod uwagę ustalony zbiór punktów krzywej eliptycznej z jednej określonej krzywej:

[G_1, G_2, G_3, ..., G_n]

I losowe współczynniki:

oraz losowo wybrane elementy skończonego pola z określonego pola skalarnego:

[s_1, s_2, s_3, ..., s_n]

MSM to obliczenie pozwalające uzyskać punkt krzywej eliptycznej Q:

Q = \suma_{i=1}^{n}s_i*G_i

W branży zazwyczaj stosuje się algorytm Pippengera do optymalizacji obliczeń MSM. Przyjrzyjmy się dokładniej schematowi procesu algorytmu Pippengera:

Proces obliczeniowy algorytmu Pippengera dzieli się na dwa etapy:

1/Scalar jest podzielony na Windows. Jeśli Skalar ma 256 bitów, a Okno ma 8 bitów, wówczas cały Skalar jest podzielony na 256/8 = 32 Okna. Każda warstwa okna korzysta z „wiader” do tymczasowego przechowywania wyników pośrednich. GW_x to punkt skumulowanego wyniku na jednej warstwie. Obliczanie GW_x jest również stosunkowo proste. Każdy skalar w warstwie jest po kolei przemierzany, a wartość warstwy skalarnej jest używana jako indeks, a odpowiedni G_x jest dodawany do odpowiedniego bitu Buckets. W rzeczywistości zasada jest stosunkowo prosta. Jeśli współczynniki dodania dwóch punktów są takie same, najpierw dodaj dwa punkty, a następnie wykonaj dodawanie skalarne. Nie ma potrzeby wykonywania dwóch dodawania skalarnego dla dwóch punktów, a następnie dodawania je w górę.

2/ Punkty obliczone przez każde Okno są sumowane poprzez podwójne dodawanie w celu uzyskania wyniku końcowego.

Algorytm Pippengera posiada również wiele algorytmów optymalizacji deformacji. W każdym razie podstawowym obliczeniem algorytmu MSM jest dodanie punktów na krzywej eliptycznej. Różne algorytmy optymalizacji odpowiadają różnym liczbom dodawania punktów.

Dodanie punktu krzywej eliptycznej (Dodaj punkt)

Na tej stronie możesz zapoznać się z różnymi algorytmami dodawania punktów na krzywych eliptycznych w „krótkiej formie Weierstrassa”.

http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl

Zakładając, że współrzędne rzutowe dwóch punktów wynoszą odpowiednio (x1, y1, z1) i (x2, y2, z2), wynik dodania punktów (x3, y3, z3) można obliczyć za pomocą następującego wzoru obliczeniowego.

Powodem szczegółowego przedstawienia procesu obliczeń jest pokazanie, że cały proces obliczeń składa się głównie z operacji na liczbach całkowitych. Szerokość bitowa liczby całkowitej zależy od parametrów krzywej eliptycznej. Podaj szerokości bitowe niektórych typowych krzywych eliptycznych:

BN256 - 256 bitów BLS12_381 - 381 bitów BLS12_377 - 377 bitów

Należy w szczególności zauważyć, że te operacje na liczbach całkowitych są operacjami na polu modulo. Dodawanie modułowe/odejmowanie modułowe jest stosunkowo proste. Skupmy się na zasadzie i implementacji mnożenia modułowego.

Mnożenie modułowe (Modular Muliplication)

Biorąc pod uwagę dwie wartości w domenie modułowej: x i y. Obliczenia mnożenia modułowego odnoszą się do x*y mod p. Należy zauważyć, że szerokość bitowa tych liczb całkowitych jest szerokością krzywej eliptycznej. Klasycznym algorytmem mnożenia modułowego jest mnożenie Montgomery'ego. Przed wykonaniem mnożenia Montgomery'ego mnożną należy przekonwertować na reprezentację Montgomery'ego:

Wzór na mnożenie Montgomery'ego jest następujący:

Istnieje wiele algorytmów implementacji mnożenia Montgomery'ego: CIOS (Coarsely Integrated Operand Scanning), FIOS (Finely Integrated Operand Scanning) i FIPS (Finely Integrated Product Scanning) itp. W tym artykule nie opisano szczegółów implementacji różnych algorytmów, a zainteresowani czytelnicy mogą przestudiować go samodzielnie.

Aby porównać różnice w wydajności pomiędzy FPGA i GPU, wybierana jest najbardziej podstawowa metoda implementacji algorytmu:

Mówiąc najprościej, modułowy algorytm mnożenia można dalej podzielić na dwa obliczenia: mnożenie dużych liczb i dodawanie dużych liczb. Po zrozumieniu logiki obliczeń MSM możesz wybrać wydajność mnożenia modułowego (przepustowość), aby porównać wydajność FPGA i GPU.

Obserwuj i myśl

Przy takim projekcie FPGA można oszacować, że cały VU9P może zapewnić przepustowość w punktach krzywej eliptycznej BLS12_381. Dodanie jednego punktu (metoda add_mix) wymaga około 12 mnożeń modułowych. Zegar systemowy FPGA wynosi 450M.

W ramach tego samego algorytmu mnożenia modułowego/dodawania modulo, przy użyciu tego samego algorytmu dodawania punktów, Troughput dodawania punktów Nvidii 3090 (biorąc pod uwagę współczynniki transmisji danych) przekracza 500M/s. Oczywiście całe obliczenia obejmują różne algorytmy. Mogą istnieć pewne algorytmy odpowiednie dla FPGA i niektóre algorytmy odpowiednie dla GPU. Powodem zastosowania tego samego porównania algorytmów jest porównanie podstawowych możliwości obliczeniowych FPGA i GPU.

Bazując na powyższych wynikach, podsumujmy porównanie GPU i FPGA pod względem wydajności ZKP:

Streszczać

Coraz więcej aplikacji zaczyna wykorzystywać technologię wiedzy zerowej. Algorytmów ZKP jest jednak wiele i różne projekty wykorzystują różne algorytmy ZKP. Sądząc po naszym praktycznym doświadczeniu inżynierskim, FPGA jest opcją, ale obecnie GPU jest opłacalną opcją. FPGA preferuje obliczenia deterministyczne i ma zalety w zakresie opóźnień i zużycia energii. Procesor graficzny jest wysoce programowalny, ma stosunkowo dojrzałą platformę obliczeniową o wysokiej wydajności, ma krótki cykl iteracji rozwoju i preferuje scenariusze dotyczące przepustowości.