Vitalik Buterin via Vitalik Buterin-bloggen
Dette er et speil av innlegget kl https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Utløseradvarsel: matematikk.
En av de viktigste kryptografiske primitivene bak ulike konstruksjoner, inkludert deterministiske terskelsignaturer, zk-SNARK-er og andre enklere former for null-kunnskapsbevis er den elliptiske kurveparingen. Elliptiske kurveparinger (eller "bilineære kart") er et nylig tillegg til en 30 år lang historie med bruk av elliptiske kurver for kryptografiske applikasjoner, inkludert kryptering og digitale signaturer; sammenkoblinger introduserer en form for "kryptert multiplikasjon", som i stor grad utvider hva elliptiske kurvebaserte protokoller kan gjøre. Hensikten med denne artikkelen vil være å gå inn i elliptiske kurveparinger i detalj, og forklare en generell oversikt over hvordan de fungerer.
Du forventes ikke å forstå alt her første gang du leser det, eller til og med tiende gang; dette er virkelig vanskelig. Men forhåpentligvis vil denne artikkelen gi deg i det minste en liten idé om hva som foregår under panseret.
Elliptiske kurver i seg selv er et ikke-trivielt emne å forstå, og denne artikkelen vil generelt anta at du vet hvordan de fungerer; hvis du ikke gjør det, anbefaler jeg denne artikkelen her som en primer: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Som en rask oppsummering involverer elliptisk kurvekryptografi matematiske objekter kalt "punkter" (disse er bokstavelige todimensjonale punkter med (�,�) koordinater), med spesielle formler for å addere og subtrahere dem (dvs. for å beregne koordinatene til �= �+�), og du kan også multiplisere et punkt med et heltall (dvs. �⋅�=�+�+…+�, selv om det er en mye raskere måte å beregne det på hvis � er stort).
Slik ser punkttillegg ut grafisk.
Det finnes et spesielt punkt kalt "punktet ved uendelig" (�), ekvivalent med null i punktaritmetikk; det er alltid slik at �+�=�. En kurve har også en "rekkefølge"; det finnes et tall � slik at �⋅�=� for enhver � (og selvfølgelig �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5, og så videre). Det er også noen vanlig enighet om "generatorpunkt" �, som på en eller annen måte forstås å representere tallet 1. Teoretisk sett kan et hvilket som helst punkt på en kurve (unntatt �) være �; alt som betyr noe er at � er standardisert.
Sammenkoblinger går et skritt videre ved at de lar deg sjekke visse typer mer kompliserte ligninger på elliptiske kurvepunkter – for eksempel hvis �=�⋅�,�=�⋅� og �=�⋅�, kan du sjekke om eller ikke �⋅�=�, med bare �,� og � som innganger. Dette kan virke som om de grunnleggende sikkerhetsgarantiene for elliptiske kurver blir brutt, ettersom informasjon om � lekker bare fra å kjenne P, men det viser seg at lekkasjen er svært begrenset - spesifikt avgjørelsesproblem med Diffie Hellman er enkelt, men det beregningsmessige Diffie Hellman-problemet (å vite � og � i eksemplet ovenfor, databehandling �=�⋅�⋅�) og diskret logaritmeproblem (å gjenopprette � fra �) forblir beregningsmessig umulig (i det minste hvis de var før).
En tredje måte å se på hva sammenkoblinger gjør, og en som kanskje er mest opplysende for de fleste brukstilfellene vi handler om, er at hvis du ser på elliptiske kurvepunkter som enveis krypterte tall (det vil si ���� ���(�)=�⋅�=�), mens tradisjonell elliptisk kurvematematikk lar deg sjekke lineær begrensninger på tallene (f.eks. hvis �=�⋅�,�=�⋅� og �=�⋅�, kryss av 5⋅�+7⋅�=11⋅� er virkelig sjekke at 5⋅�+7⋅�=11⋅�), lar sammenkoblinger deg sjekke kvadratisk begrensninger (f.eks. å sjekke �(�,�)⋅�(�,�⋅5)=1 er virkelig sjekker at �⋅�+5=0). Og å gå opp til kvadratisk er nok til å la oss jobbe med deterministiske terskelsignaturer, kvadratiske aritmetiske programmer og alt det andre gode.
Nå, hva er denne morsomme �(�,�)-operatøren som vi introduserte ovenfor? Dette er sammenkoblingen. Matematikere kaller det også noen ganger en bilineært kart; ordet "bilineær" her betyr i utgangspunktet at det tilfredsstiller begrensningene:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Merk at + og ⋅ kan være vilkårlige operatorer; når du lager fancy nye typer matematiske objekter, bryr ikke abstrakt algebra seg om hvordan + og ⋅ er definert, så lenge de er konsistente på vanlige måter, f.eks. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) og (�⋅�)+(�⋅�)=(�+�)⋅�.
Hvis �, �, � og � var enkle tall, da er det enkelt å lage en enkel sammenkobling: vi kan gjøre �(�,�)=2��. Da kan vi se:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Det er bilineært!
Imidlertid er slike enkle sammenkoblinger ikke egnet for kryptografi fordi objektene de jobber med er enkle heltall og er for enkle å analysere; heltall gjør det enkelt å dele, beregne logaritmer og gjøre forskjellige andre beregninger; enkle heltall har ikke noe begrep om en "offentlig nøkkel" eller en "enveis funksjon". I tillegg, med sammenkoblingen beskrevet ovenfor kan du gå bakover – ved å vite � og vite �(�,�), kan du ganske enkelt beregne en divisjon og en logaritme for å bestemme �. Vi vil ha matematiske objekter som er så nærme som mulig "svarte bokser", hvor du kan addere, subtrahere, multiplisere og dividere, men ikke gjør noe annet. Det er her elliptiske kurver og elliptiske kurver kommer inn.
Det viser seg at det er mulig å lage et bilineært kart over elliptiske kurvepunkter - det vil si å komme opp med en funksjon �(�,�) der inngangene � og � er elliptiske kurvepunkter, og hvor utgangen er det som kalles en (��)12-element (i det minste i det spesifikke tilfellet vi skal dekke her; spesifikasjonene varierer avhengig av detaljene i kurven, mer om dette senere), men regnestykket bak å gjøre det er ganske komplekst.
La oss først dekke hovedfelt og utvidelsesfelt. Den pene elliptiske kurven på bildet tidligere i dette innlegget ser bare slik ut hvis du antar at kurvelikningen er definert ved hjelp av vanlige reelle tall. Men hvis vi faktisk bruker vanlige reelle tall i kryptografi, kan du bruke logaritmer for å "gå bakover", og alt går i stykker; i tillegg kan mengden plass som trengs for å faktisk lagre og representere tallene vokse vilkårlig. Derfor bruker vi i stedet tall i a primærfelt.
Et primtallsfelt består av settet med tall 0,1,2…�−1, der � er primtall, og de ulike operasjonene er definert som følger:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
I utgangspunktet gjøres all matematikk modulo � (se her. for en introduksjon til modulær matematikk). Divisjon er et spesielt tilfelle; normalt er ikke 32 et heltall, og her ønsker vi kun å forholde oss til heltall, så vi prøver i stedet å finne tallet � slik at �⋅2=3, hvor ⋅ selvsagt refererer til modulær multiplikasjon som definert ovenfor. Takk til Fermats lille teorem, gjør eksponentieringstrikset vist ovenfor jobben, men det er også en raskere måte å gjøre det på, ved å bruke Utvidet euklidisk algoritme. Anta at �=7; her er noen 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 leker med denne typen matematikk, vil du legge merke til at den er helt konsistent og tilfredsstiller alle de vanlige reglene. De to siste eksemplene ovenfor viser hvordan (�/�)⋅�=�; du kan også se at (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, og alle andre algebraiske identiteter på videregående skole du kjenner og elsker fortsetter å holde sant også. I elliptiske kurver i virkeligheten beregnes punktene og ligningene vanligvis i prime felt.
La oss snakke om det utvidelsesfelt. Du har sikkert allerede sett et utvidelsesfelt før; det vanligste eksemplet du støter på i lærebøker i matematikk er feltet med komplekse tall, der feltet med reelle tall er "utvidet" med tilleggselementet −1=�. I utgangspunktet fungerer utvidelsesfelt ved å ta et eksisterende felt, deretter "oppfinne" et nytt element og definere forholdet mellom det elementet og eksisterende elementer (i dette tilfellet �2+1=0), og sørge for at denne ligningen ikke stemmer for et hvilket som helst tall som er i det opprinnelige feltet, og ser på settet med alle lineære kombinasjoner av elementer i det opprinnelige feltet og det nye elementet du nettopp har opprettet.
Vi kan gjøre utvidelser av prime felt også; for eksempel kan vi utvide primfeltet mod7 som vi beskrev ovenfor med �, og så kan vi gjøre:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Det siste resultatet kan være litt vanskelig å finne ut; det som skjedde der var at vi først dekomponerer produktet til 4�⋅2+4�⋅�, som gir 8�−4, og så fordi vi jobber i mod7 matte som blir �+3. For å dele gjør vi:
�/�:(�⋅�(�2−2)) % �
Legg merke til at eksponenten for Fermats lille teorem nå er �2 i stedet for �, men igjen hvis vi ønsker å være mer effektive, kan vi også i stedet utvide den utvidede euklidiske algoritmen til å gjøre jobben. Legg merke til at ��2−1=1 for enhver � i dette feltet, så vi kaller �2−1 for "rekkefølgen til den multiplikative gruppen i feltet".
Med reelle tall er Algebras grunnleggende teorem sikrer at den kvadratiske utvidelsen som vi kaller de komplekse tallene er "fullstendig" - du kan ikke utvide den ytterligere, fordi for enhver matematisk sammenheng (i det minste enhver matematisk sammenheng definert av en algebraisk formel) som du kan komme opp med mellom et nytt element � og de eksisterende komplekse tallene, er det mulig å komme opp med minst ett komplekst tall som allerede tilfredsstiller dette forholdet. Med prime felt har vi imidlertid ikke dette problemet, og derfor kan vi gå lenger og lage kubiske utvidelser (hvor det matematiske forholdet mellom et nytt element � og eksisterende feltelementer er en kubikkligning, så 1,� og �2 er alle lineært uavhengige av hverandre), utvidelser av høyere orden, utvidelser av utvidelser osv. Og det er denne typen superladede modulære komplekse tall som elliptiske kurvepar er bygget på.
For de som er interessert i å se den nøyaktige matematikken som er involvert i å gjøre alle disse operasjonene skrevet ut i kode, er prime felt og feltutvidelser implementert her: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Nå, over til elliptiske kurveparinger. En elliptisk kurveparing (eller rettere sagt, den spesifikke formen for sammenkobling vi skal utforske her; det finnes også andre typer sammenkoblinger, selv om deres logikk er ganske lik) er et kart �2×�1→��, der:
- �1 er en elliptisk kurve, der punktene tilfredsstiller en ligning av formen �2=�3+�, og hvor begge koordinatene er elementer av �� (dvs. de er enkle tall, bortsett fra at aritmetikk gjøres modulo et primtall)
- �2 er en elliptisk kurve, der punkter tilfredsstiller samme ligning som �1, bortsett fra der koordinatene er elementer av (��)12 (dvs. de er de overladede komplekse tallene vi snakket om ovenfor; vi definerer et nytt "magisk tall". ” �, som er definert av et 12. grads polynom som �12−18⋅�6+82=0)
- �� er typen objekt som resultatet av den elliptiske kurven går inn i. I kurvene vi ser på er �� (��)12 (samme overladede komplekse tall som brukes i �2)
Hovedegenskapen den må tilfredsstille er bilinearitet, som i denne sammenheng betyr at:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Det er to andre viktige kriterier:
- Effektiv beregnbarhet (f.eks. kan vi lage en enkel sammenkobling ved ganske enkelt å ta de diskrete logaritmene til alle punktene og multiplisere dem sammen, men dette er like beregningsmessig vanskelig som å bryte elliptisk kurvekryptografi i utgangspunktet, så det teller ikke)
- Ikke-degenerasjon (sikkert, du kan bare definere �(�,�)=1, men det er ikke en spesielt nyttig sammenkobling)
Så hvordan gjør vi dette?
Matematikken bak hvorfor sammenkoblingsfunksjoner fungerer er ganske vanskelig og involverer ganske mye avansert algebra som går utover det vi har sett så langt, men jeg skal gi en oversikt. Først av alt må vi definere begrepet en deler, i utgangspunktet en alternativ måte å representere funksjoner på elliptiske kurvepunkter. En divisor for en funksjon teller i utgangspunktet nullene og uendelighetene til funksjonen. For å se hva dette betyr, la oss gå gjennom noen eksempler. La oss fikse et punkt �=(��,��), og vurdere følgende funksjon:
�(�,�)=�−��
Divisor er [�]+[−�]−2⋅[�] (hakeparentesene brukes for å representere det faktum at vi refererer til tilstedeværelsen av punktet � i settet med nuller og uendeligheter av funksjonen, ikke selve punktet P; [�]+[�] er ikke det samme som [�+�]). Begrunnelsen er som følger:
- Funksjonen er lik null ved �, siden � is ��, så �−��=0
- Funksjonen er lik null ved −�, siden −� og � deler samme � koordinat
- Funksjonen går til uendelig som � går til uendelig, så vi sier at funksjonen er lik uendelig ved �. Det er en teknisk grunn til at denne uendeligheten må telles to ganger, så � blir lagt til med en "multiplikhet" på -2 (negativ fordi det er en uendelighet og ikke en null, to på grunn av denne dobbelttellingen).
Den tekniske årsaken er omtrent dette: fordi ligningen til kurven er �3=�2+�, går det til uendelig "1.5 ganger raskere" enn � gjør for at �2 skal holde tritt med �3; Derfor, hvis en lineær funksjon bare inkluderer �, er den representert som en uendelighet av multiplisitet 2, men hvis den inkluderer �, er den representert som en uendelig av multiplisitet 3.
Tenk nå på en "linjefunksjon":
��+��+�=0
Hvor �, � og � er nøye valgt slik at linjen går gjennom punktene � og �. På grunn av hvordan addisjon av elliptisk kurve fungerer (se diagrammet øverst), betyr dette også at den går gjennom −�−�. Og det går opp til uendelig avhengig av både � og �, så divisor blir [�]+[�]+[−�−�]−3⋅[�].
Vi vet at hver "rasjonell funksjon" (dvs. en funksjon definert kun ved å bruke et endelig antall +,−,⋅ og / operasjoner på koordinatene til punktet) tilsvarer entydig en divisor, opp til multiplikasjon med en konstant (dvs. hvis to funksjoner � og � har samme divisor, så �=�⋅� for en konstant �).
For alle to funksjoner � og �, er divisor av �⋅� lik divisor av � pluss divisor av � (i matematikkbøker vil du se (�⋅�)=(�)+(�)), så for eksempel hvis �(�,�)=��−�, så (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � og −� er "trippeltellert" for å gjøre rede for det faktum at �3 nærmer seg 0 på disse punktene "tre ganger så raskt" i en viss matematisk forstand.
Legg merke til at det er et teorem som sier at hvis du "fjerner hakeparentesene" fra en divisor av en funksjon, må punktene summeres til �([�]+[�]+[−�−�]−3⋅[ �] passer tydelig, som �+�−�−�−3⋅�=�), og enhver divisor som har denne egenskapen er divisor for en funksjon.
Nå er vi klare til å se på Tate-sammenkoblinger. Tenk på følgende funksjoner, definert via deres divisorer:
- (��)=�⋅[�]−�⋅[�], der � er rekkefølgen på �1, dvs. �⋅�=� for alle �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
La oss nå se på produktet ��⋅��⋅��. Divisor er:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�]⋅[
Som forenkler pent til:
�⋅[�+�]−�⋅[�]
Legg merke til at denne divisoren har nøyaktig samme format som divisoren for �� og �� ovenfor. Derfor ��⋅��⋅��=��+�.
Nå introduserer vi en prosedyre kalt «endelig eksponentiering»-trinnet, der vi tar resultatet av funksjonene våre ovenfor (��,��, etc.) og hever det til potensen �=(�12−1)/�, hvor �12−1 er rekkefølgen til den multiplikative gruppen i (��)12 (dvs. for noen �∈(��)12,�(�12−1)=1). Legg merke til at hvis du bruker denne eksponentieringen på et hvilket som helst resultat som har allerede blitt hevet til potensen �, får du en eksponentiering i potensen �12−1, så resultatet blir til 1. Derfor, etter endelig eksponentiering, kansellerer �� ut og vi får ���⋅���=( ��+�)�. Det er litt bilinearitet for deg.
Nå, hvis du vil lage en funksjon som er bilineær i begge argumentene, må du gå inn i skumlere matematikk, hvor du i stedet for å ta �� av en verdi direkte, tar �� av en deler, og det er der hele "Tate-parringen" kommer fra. For å bevise flere resultater må du forholde deg til forestillinger som "lineær ekvivalens" og "Weil gjensidighet", og kaninhullet fortsetter derfra. Du kan finne mer lesestoff om alt dette her. og her..
For en implementering av en modifisert versjon av Tate-paringen, kalt den optimale Ate-paringen, se her. Koden implementerer Millers algoritme, som er nødvendig for å faktisk beregne ��.
Merk at det faktum at sammenkoblinger som dette er mulig er litt av en blandet velsignelse: på den ene siden betyr det at alle protokollene vi kan gjøre med sammenkoblinger blir mulige, men det betyr også at vi må være mer forsiktige med hvilke elliptiske kurver vi bruker.
Hver elliptisk kurve har en verdi som kalles an embedding grad; i hovedsak, den minste � slik at ��−1 er et multiplum av � (hvor � er primtallet brukt for feltet og � er kurveordenen). I feltene ovenfor, �=12, og i feltene som brukes for tradisjonell ECC (dvs. der vi ikke bryr oss om sammenkoblinger), er innbyggingsgraden ofte ekstremt stor, til det punktet at sammenkoblinger er beregningsmessig umulig å beregne; Hvis vi imidlertid ikke er forsiktige, kan vi generere felt der �=4 eller til og med 1.
Hvis �=1, kan problemet med "diskret logaritme" for elliptiske kurver (i hovedsak gjenopprette � bare kjenne punktet �=�⋅�, problemet som du må løse for å "knekke" en elliptisk kurve privat nøkkel) reduseres inn i et lignende matematisk problem over ��, hvor problemet blir mye lettere (dette kalles MOV-angrep); bruk av kurver med en innebyggingsgrad på 12 eller høyere sikrer at denne reduksjonen enten er utilgjengelig, eller at det å løse det diskrete loggproblemet over paringsresultater er minst like vanskelig som å gjenopprette en privat nøkkel fra en offentlig nøkkel "på vanlig måte" (dvs. beregningsmessig umulig). Ikke bekymre deg; alle standard kurveparametere har blitt grundig kontrollert for dette problemet.
Følg med for en matematisk forklaring på hvordan zk-SNARK-er fungerer, kommer snart.
Spesiell takk til Christian Reitwiessner, Ariel Gabizon (fra Zcash) og Alfred Menezes for gjennomgang og rettelser.
- SEO-drevet innhold og PR-distribusjon. Bli forsterket i dag.
- PlatoData.Network Vertical Generative Ai. Styrk deg selv. Tilgang her.
- PlatoAiStream. Web3 Intelligence. Kunnskap forsterket. Tilgang her.
- PlatoESG. Karbon, CleanTech, Energi, Miljø, Solenergi, Avfallshåndtering. Tilgang her.
- PlatoHelse. Bioteknologisk og klinisk etterretning. Tilgang her.
- BlockOffsets. Modernisering av eierskap for miljøkompensasjon. Tilgang her.
- kilde: Platon Data Intelligence.