Vitalik Buterin via Vitalik Buterin blog
Dette er et spejl af posten kl https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Udløser advarsel: matematik.
En af de vigtigste kryptografiske primitiver bag forskellige konstruktioner, herunder deterministiske tærskelsignaturer, zk-SNARK'er og andre enklere former for nul-vidensbeviser er den elliptiske kurveparring. Elliptiske kurveparringer (eller "bilineære kort") er en nylig tilføjelse til en 30-årig historie med at bruge elliptiske kurver til kryptografiske applikationer, herunder kryptering og digitale signaturer; parringer introducerer en form for "krypteret multiplikation", hvilket i høj grad udvider, hvad elliptiske kurvebaserede protokoller kan gøre. Formålet med denne artikel vil være at gå ind i elliptiske kurveparringer i detaljer og forklare en generel oversigt over, hvordan de fungerer.
Du forventes ikke at forstå alt her første gang du læser det, eller endda tiende gang; det her er virkelig svært. Men forhåbentlig vil denne artikel give dig i det mindste en lille idé om, hvad der foregår under motorhjelmen.
Elliptiske kurver i sig selv er meget et ikke-trivielt emne at forstå, og denne artikel vil generelt antage, at du ved, hvordan de virker; hvis du ikke gør det, anbefaler jeg denne artikel her som en primer: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Som en hurtig opsummering involverer elliptisk kurvekryptografi matematiske objekter kaldet "punkter" (disse er bogstavelige todimensionelle punkter med (�,�) koordinater), med specielle formler til at addere og subtrahere dem (dvs. til at beregne koordinaterne for �= �+�), og du kan også gange et punkt med et heltal (dvs. �⋅�=�+�+…+�, selvom der er en meget hurtigere måde at beregne det på, hvis � er stort).
Her er hvordan punkttilsætning ser ud grafisk.
Der findes et særligt punkt kaldet "punktet ved uendelig" (�), svarende til nul i punktaritmetik; det er altid sådan, at �+�=�. Desuden har en kurve en "ordrer"; der findes et tal � sådan at �⋅�=� for enhver � (og selvfølgelig �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5, og så videre). Der er også nogle almindeligt anerkendte "generatorpunkt" �, som i en eller anden forstand skal repræsentere tallet 1. Teoretisk set kan ethvert punkt på en kurve (undtagen �) være �; alt, der betyder noget, er, at � er standardiseret.
Parringer går et skridt videre, idet de giver dig mulighed for at kontrollere visse former for mere komplicerede ligninger på elliptiske kurvepunkter - for eksempel, hvis �=�⋅�,�=�⋅� og �=�⋅�, kan du kontrollere, om eller ikke �⋅�=�, med kun �,� og � som input. Dette kan se ud som om, at de grundlæggende sikkerhedsgarantier for elliptiske kurver er ved at blive brudt, da information om � lækker ud fra kun at kende P, men det viser sig, at lækagen er meget indesluttet - specifikt beslutningsmæssigt Diffie Hellman-problem er let, men det beregningsmæssige Diffie Hellman-problem (ved at kende � og � i ovenstående eksempel, computing �=�⋅�⋅�) og diskret logaritmeproblem (gendannelse � fra �) forbliver beregningsmæssigt umulige (i hvert fald hvis de var før).
En tredje måde at se på, hvad parringer gør, og en der måske er mest oplysende for de fleste af de use cases, vi handler om, er, at hvis du ser elliptiske kurvepunkter som envejs krypterede tal (det vil sige ���� ���(�)=�⋅�=�), hvorimod traditionel elliptisk kurve-matematik lader dig kontrollere lineær begrænsninger på tallene (f.eks. hvis �=�⋅�,�=�⋅� og �=�⋅�, markering af 5⋅�+7⋅�=11⋅� er virkelig kontrollere, at 5⋅�+7⋅�=11⋅�), giver parringer dig mulighed for at kontrollere kvadratisk begrænsninger (f.eks. kontrol af �(�,�)⋅�(�,�⋅5)=1 er virkelig kontrollere, at �⋅�+5=0). Og at gå op til kvadratisk er nok til at lade os arbejde med deterministiske tærskelsignaturer, kvadratiske aritmetiske programmer og alt det andet gode.
Hvad er nu denne sjove �(�,�)-operator, som vi introducerede ovenfor? Dette er parringen. Matematikere kalder det også nogle gange en bilineært kort; ordet "bilineær" betyder her grundlæggende, at det opfylder begrænsningerne:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Bemærk at + og ⋅ kan være vilkårlige operatorer; når du skaber smarte nye slags matematiske objekter, er abstrakt algebra ligeglad med, hvordan + og ⋅ er definerede, så længe de er konsistente på de sædvanlige måder, f.eks. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) og (�⋅�)+(�⋅�)=(�+�)⋅�.
Hvis �, �, � og � var enkle numre, så er det nemt at lave en simpel parring: vi kan gøre �(�,�)=2��. Så kan vi se:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Det er bilineært!
Sådanne simple parringer er imidlertid ikke egnede til kryptografi, fordi de objekter, de arbejder på, er simple heltal og er for nemme at analysere; heltal gør det nemt at dividere, beregne logaritmer og lave forskellige andre beregninger; simple heltal har intet begreb om en "offentlig nøgle" eller en "envejsfunktion". Derudover kan du med den ovenfor beskrevne parring gå baglæns – ved at kende � og kende �(�,�), kan du blot beregne en division og en logaritme for at bestemme �. Vi ønsker matematiske objekter, der er så tæt som muligt på "sorte bokse", hvor man kan addere, subtrahere, gange og dividere, men gør ikke andet. Det er her elliptiske kurver og elliptiske kurver kommer ind.
Det viser sig, at det er muligt at lave et bilineært kort over elliptiske kurvepunkter - det vil sige at komme med en funktion �(�,�), hvor input � og � er elliptiske kurvepunkter, og hvor outputtet er det, der kaldes en (��)12-element (i det mindste i det specifikke tilfælde, vi vil dække her; detaljerne varierer afhængigt af detaljerne i kurven, mere om dette senere), men matematikken bag at gøre det er ret kompleks.
Lad os først dække primære felter og udvidelsesfelter. Den smukke elliptiske kurve på billedet tidligere i dette indlæg ser kun sådan ud, hvis du antager, at kurveligningen er defineret ved hjælp af regulære reelle tal. Men hvis vi faktisk bruger regulære reelle tal i kryptografi, så kan du bruge logaritmer til at "gå baglæns", og alt går i stykker; derudover kan mængden af plads, der er nødvendig for faktisk at gemme og repræsentere tallene, vokse vilkårligt. Derfor bruger vi i stedet tal i a prime felt.
Et primtalsfelt består af mængden af tal 0,1,2…�−1, hvor � er primtal, og de forskellige operationer er defineret som følger:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
Dybest set udføres al matematik modulo � (se link. for en introduktion til modulær matematik). Division er et særligt tilfælde; normalt er 32 ikke et heltal, og her vil vi kun beskæftige os med heltal, så vi forsøger i stedet at finde tallet � sådan at �⋅2=3, hvor ⋅ naturligvis refererer til modulær multiplikation som defineret ovenfor. Tak til Fermats lille sætning, gør eksponentieringstricket vist ovenfor jobbet, men der er også en hurtigere måde at gøre det på ved at bruge Udvidet euklidisk algoritme. Antag �=7; her er et par eksempler:
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
Hvis du leger med denne form for matematik, vil du bemærke, at den er helt konsistent og opfylder alle de sædvanlige regler. De sidste to eksempler ovenfor viser, hvordan (�/�)⋅�=�; du kan også se, at (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, og alle de andre algebraiske gymnasieidentiteter, du kender og elsker, fortsætter også at holde stik. I elliptiske kurver i virkeligheden beregnes punkterne og ligningerne normalt i prime felter.
Lad os tale om det udvidelsesfelter. Du har sikkert allerede set et udvidelsesfelt før; det mest almindelige eksempel, du støder på i matematiklærebøger, er feltet med komplekse tal, hvor feltet med reelle tal er "udvidet" med det ekstra element −1=�. Grundlæggende fungerer udvidelsesfelter ved at tage et eksisterende felt, derefter "opfinde" et nyt element og definere forholdet mellem dette element og eksisterende elementer (i dette tilfælde �2+1=0), og sikre sig, at denne ligning ikke holder stik for ethvert tal, der er i det oprindelige felt, og ser på sættet af alle lineære kombinationer af elementer i det oprindelige felt og det nye element, som du lige har oprettet.
Vi kan også lave udvidelser af primære felter; for eksempel kan vi udvide primefeltet mod7, som vi beskrev ovenfor med �, og så kan vi gøre:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Det sidste resultat kan være lidt svært at finde ud af; det der skete der var, at vi først dekomponerede produktet til 4�⋅2+4�⋅�, hvilket giver 8�−4, og så fordi vi arbejder i mod7 matematik, bliver det �+3. For at dele gør vi:
�/�:(�⋅�(�2−2)) % �
Bemærk, at eksponenten for Fermats lille sætning nu er �2 i stedet for �, selvom vi igen, hvis vi vil være mere effektive, også i stedet kan udvide den udvidede euklidiske algoritme til at udføre opgaven. Bemærk, at ��2−1=1 for enhver � i dette felt, så vi kalder �2−1 for "rækkefølgen af den multiplikative gruppe i feltet".
Med reelle tal er Algebras grundlæggende sætning sikrer, at den kvadratiske forlængelse, som vi kalder de komplekse tal, er "komplet" - du kan ikke udvide den yderligere, for for enhver matematisk sammenhæng (i det mindste enhver matematisk sammenhæng defineret af en algebraisk formel), som du kan finde på mellem et nyt element � og de eksisterende komplekse tal, er det muligt at komme op med mindst ét komplekst tal, der allerede opfylder dette forhold. Med prime felter har vi imidlertid ikke dette problem, og så vi kan gå længere og lave kubiske udvidelser (hvor den matematiske sammenhæng mellem et nyt element � og eksisterende feltelementer er en kubisk ligning, så 1,� og �2 er alle lineært uafhængige af hinanden), udvidelser af højere orden, udvidelser af udvidelser osv. Og det er den slags superladede modulære komplekse tal, elliptiske kurveparringer er bygget på.
For dem, der er interesseret i at se den nøjagtige matematik involveret i at få alle disse operationer skrevet ud i kode, implementeres prime felter og feltudvidelser her: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Nu til elliptiske kurveparringer. En elliptisk kurveparring (eller rettere, den specifikke form for parring, vi vil udforske her; der er også andre typer parringer, selvom deres logik er ret ens) er et kort �2×�1→��, hvor:
- �1 er en elliptisk kurve, hvor punkter opfylder en ligning på formen �2=�3+�, og hvor begge koordinater er elementer af �� (dvs. de er simple tal, undtagen aritmetik udføres alt modulo et eller andet primtal)
- �2 er en elliptisk kurve, hvor punkter opfylder den samme ligning som �1, undtagen hvor koordinaterne er elementer af (��)12 (dvs. de er de overladede komplekse tal, vi talte om ovenfor; vi definerer et nyt "magisk tal" ” �, som er defineret af et 12. grads polynomium som �12−18⋅�6+82=0)
- �� er den type objekt, som resultatet af den elliptiske kurve går ind i. I kurverne, som vi ser på, er �� (��)12 (det samme overladede komplekse tal som brugt i �2)
Den vigtigste egenskab, som den skal opfylde, er bilinearitet, hvilket i denne sammenhæng betyder, at:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Der er to andre vigtige kriterier:
- Effektiv beregningsevne (f.eks. kan vi lave en nem parring ved blot at tage de diskrete logaritmer af alle punkter og gange dem sammen, men dette er lige så regnemæssigt svært som at bryde elliptisk kurvekryptografi i første omgang, så det tæller ikke)
- Ikke-degeneration (sikkert, du kunne bare definere �(�,�)=1, men det er ikke en særlig nyttig parring)
Så hvordan gør vi det?
Matematikken bag, hvorfor parringsfunktioner virker, er ret besværlig og involverer en del avanceret algebra, der går ud over, hvad vi hidtil har set, men jeg vil give en oversigt. Først og fremmest skal vi definere begrebet en divider, dybest set en alternativ måde at repræsentere funktioner på elliptiske kurvepunkter. En divisor af en funktion tæller grundlæggende funktionens nuller og uendeligheder. For at se, hvad dette betyder, lad os gennemgå et par eksempler. Lad os rette et punkt �=(��,��), og overveje følgende funktion:
�(�,�)=�−��
Divisor er [�]+[−�]−2⋅[�] (kantede parenteser bruges til at repræsentere det faktum, at vi henviser til tilstedeværelsen af punktet � i sættet af nuller og uendeligheder af funktionen, ikke selve punktet P; [�]+[�] er ikke det samme som [�+�]). Begrundelsen er som følger:
- Funktionen er lig med nul ved �, da � is ��, så �−��=0
- Funktionen er lig med nul ved −�, da −� og � deler den samme � koordinat
- Funktionen går til uendelig som � går til uendelig, så vi siger, at funktionen er lig med uendelig ved �. Der er en teknisk grund til, at denne uendelighed skal tælles to gange, så � bliver tilføjet med en "multiplikitet" på -2 (negativ, fordi det er en uendelighed og ikke et nul, to på grund af denne dobbelttælling).
Den tekniske årsag er groft sagt denne: fordi kurvens ligning er �3=�2+�, går det til uendeligt "1.5 gange hurtigere" end � gør, for at �2 kan følge med �3; Derfor, hvis en lineær funktion kun inkluderer �, er den repræsenteret som en uendelighed af multiplicitet 2, men hvis den inkluderer �, er den repræsenteret som en uendelig af multiplicitet 3.
Overvej nu en "linjefunktion":
��+��+�=0
Hvor �, � og � er nøje udvalgt, så linjen passerer gennem punkterne � og �. På grund af hvordan elliptisk kurveaddition fungerer (se diagrammet øverst), betyder det også, at den passerer gennem −�−�. Og det går op til uendeligt afhængigt af både � og �, så divisor bliver [�]+[�]+[−�−�]−3⋅[�].
Vi ved, at enhver "rationel funktion" (dvs. en funktion defineret kun ved hjælp af et endeligt antal +,−,⋅ og / operationer på punktets koordinater) entydigt svarer til en divisor, op til multiplikation med en konstant (dvs. hvis to funktioner � og � har samme divisor, så �=�⋅� for en konstant �).
For alle to funktioner � og � er divisor af �⋅� lig med divisor af � plus divisor af � (i matematiklærebøger vil du se (�⋅�)=(�)+(�)), så for eksempel hvis �(�,�)=��−�, så (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � og −� "tælles tre gange" for at tage højde for det faktum, at �3 nærmer sig 0 på disse punkter "tre gange så hurtigt" i en vis matematisk forstand.
Bemærk, at der er en sætning, der siger, at hvis du "fjerner firkantede parenteser" fra en divisor af en funktion, skal punkterne summeres til �([�]+[�]+[−�−�]−3⋅[ �] passer tydeligt, som �+�−�−�−3⋅�=�), og enhver divisor, der har denne egenskab, er divisor af en funktion.
Nu er vi klar til at se på Tate-parringer. Overvej følgende funktioner, defineret via deres divisorer:
- (��)=�⋅[�]−�⋅[�], hvor � er rækkefølgen af �1, dvs. �⋅�=� for enhver �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Lad os nu se på produktet ��⋅��⋅��. Divisor er:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅�
Hvilket forenkler pænt til:
�⋅[�+�]−�⋅[�]
Bemærk, at denne divisor er af nøjagtig samme format som divisoren for �� og �� ovenfor. Derfor ��⋅��⋅��=��+�.
Nu introducerer vi en procedure kaldet det "endelige eksponentieringstrin", hvor vi tager resultatet af vores funktioner ovenfor (��,�� osv.) og hæver det til potensen �=(�12−1)/�, hvor �12−1 er rækkefølgen af den multiplikative gruppe i (��)12 (dvs. for enhver �∈(��)12,�(�12−1)=1). Bemærk, at hvis du anvender denne eksponentiering på ethvert resultat, der har allerede blevet hævet til potensen �, får du en eksponentiering til �12−1, så resultatet bliver til 1. Derfor annullerer �� efter endelig eksponentiering, og vi får ���⋅���=( ��+�)�. Der er noget bilinearitet for dig.
Hvis du nu vil lave en funktion, der er bilineær i begge argumenter, skal du gå ind i mere uhyggelig matematik, hvor du i stedet for at tage �� af en værdi direkte, tager �� af en divider, og det er her den fulde "Tate-parring" kommer fra. For at bevise nogle flere resultater skal du forholde dig til begreber som "lineær ækvivalens" og "Weil reciprocity", og kaninhullet fortsætter derfra. Du kan finde mere læsestof om alt dette link. , link..
For en implementering af en modificeret version af Tate-parringen, kaldet den optimale Ate-paring, se her. Koden implementerer Millers algoritme, som er nødvendig for rent faktisk at beregne ��.
Bemærk, at det faktum, at parringer som denne er mulige, er noget af en blandet velsignelse: på den ene side betyder det, at alle de protokoller, vi kan lave med parringer, bliver mulige, men det betyder også, at vi skal være mere forsigtige med, hvilke elliptiske kurver vi bruger.
Hver elliptisk kurve har en værdi kaldet an indlejringsgrad; i det væsentlige, den mindste � sådan at ��−1 er et multiplum af � (hvor � er det primtal, der bruges til feltet, og � er kurverækkefølgen). I felterne ovenfor, �=12, og i felterne brugt til traditionel ECC (dvs. hvor vi er ligeglade med parringer), er indlejringsgraden ofte ekstremt stor, til det punkt, at parringer er beregningsmæssigt umulige at beregne; Men hvis vi ikke er forsigtige, kan vi generere felter, hvor �=4 eller endda 1.
Hvis �=1, så kan problemet med "diskret logaritme" for elliptiske kurver (i det væsentlige, at komme sig � kun kende punktet �=�⋅�, problemet, som du skal løse for at "knække" en elliptisk kurve privat nøgle) reduceres ind i et lignende matematisk problem over ��, hvor problemet bliver meget lettere (dette kaldes MOV angreb); Brug af kurver med en indlejringsgrad på 12 eller højere sikrer, at denne reduktion enten er utilgængelig, eller at løsning af det diskrete logproblem over parringsresultater er mindst lige så svært som at gendanne en privat nøgle fra en offentlig nøgle "på den normale måde" (dvs. beregningsmæssigt umuligt). Vær ikke urolig; alle standardkurveparametre er blevet grundigt kontrolleret for dette problem.
Hold øje med en matematisk forklaring på, hvordan zk-SNARK'er fungerer, som kommer snart.
Særlig tak til Christian Reitwiessner, Ariel Gabizon (fra Zcash) og Alfred Menezes for gennemgang og rettelser.
- SEO Powered Content & PR Distribution. Bliv forstærket i dag.
- PlatoData.Network Vertical Generative Ai. Styrk dig selv. Adgang her.
- PlatoAiStream. Web3 intelligens. Viden forstærket. Adgang her.
- PlatoESG. Kulstof, CleanTech, Energi, Miljø, Solenergi, Affaldshåndtering. Adgang her.
- PlatoHealth. Bioteknologiske og kliniske forsøgs intelligens. Adgang her.
- BlockOffsets. Modernisering af miljømæssig offset-ejerskab. Adgang her.
- Kilde: Platon Data Intelligence.