Är det möjligt att generera slumptal om vi inte litar på varandra? Del 2

Hej Habr!

В den första delen I den här artikeln diskuterade vi varför det kan vara nödvändigt att generera slumptal för deltagare som inte litar på varandra, vilka krav som ställs för sådana slumptalsgeneratorer och övervägde två sätt att implementera dem.

I den här delen av artikeln kommer vi att titta närmare på ett annat tillvägagångssätt som använder tröskelsignaturer.

Lite kryptografi

För att förstå hur tröskelsignaturer fungerar måste du förstå lite grundläggande kryptografi. Vi kommer att använda två begrepp: skalärer, eller helt enkelt siffror, som vi kommer att beteckna med små bokstäver (x, y) och punkter på den elliptiska kurvan, som vi kommer att beteckna med versaler.

För att förstå grunderna för tröskelsignaturer behöver du inte förstå hur elliptiska kurvor fungerar, förutom några grundläggande saker:

1. Punkter på en elliptisk kurva kan adderas och multipliceras med en skalär (vi kommer att beteckna multiplikation med en skalär som xG, även om notationen Gx används också ofta i litteraturen). Resultatet av addition och multiplikation med en skalär är en punkt på en elliptisk kurva.

2. Vet bara poängen G och dess produkt med en skalär xG kan inte beräknas x.

Vi kommer också att använda begreppet polynom p(x) grader k-1. I synnerhet kommer vi att använda följande egenskap hos polynom: om vi vet värdet p(x) för alla k annorlunda x (och vi har ingen mer information om p(x)), kan vi beräkna p(x) för någon annan x.

Det är intressant att för vilket polynom som helst p(x) och någon punkt på kurvan Gveta innebörden p(x)G för alla k olika betydelser x, kan vi också beräkna p(x)G för alla x.

Detta är tillräckligt med information för att gräva i detaljerna om hur tröskelsignaturer fungerar och hur man använder dem för att generera slumpmässiga tal.

Slumptalsgenerator på tröskelsignaturer

Låt oss säga det n deltagare vill generera ett slumpmässigt antal, och vi vill att alla ska delta k det fanns tillräckligt med dem för att generera ett antal, men så att angriparna som kontrollerar k-1 eller färre deltagare kunde inte förutsäga eller påverka antalet genererade.

Anta att det finns ett sådant polynom p(x) grader k-1 vad den första deltagaren vet p (1), den andra vet p(2), och så vidare (n-det vet p(n)). Vi antar också att för någon förutbestämd punkt G alla vet p(x)G för alla värden x. Vi ringer pi) "privat komponent" ideltagare (eftersom endast iden e deltagaren känner henne), och gris "offentlig komponent" i-e deltagare (eftersom alla deltagare känner henne). Som du minns, kunskap gris inte tillräckligt för att återställa pi).

Att skapa ett sådant polynom så att bara i-Den första deltagaren och ingen annan kände till hans privata komponent - detta är den mest komplexa och intressanta delen av protokollet, och vi kommer att analysera det nedan. För nu, låt oss anta att vi har ett sådant polynom och att alla deltagare känner till sina privata komponenter.

Hur kan vi använda ett sådant polynom för att generera ett slumptal? Till att börja med behöver vi någon sträng som inte tidigare har använts som input till generatorn. I fallet med en blockchain, hashen för det sista blocket h är en bra kandidat för en sådan linje. Låt deltagarna vilja skapa ett slumptal med hjälp av h som frö. Deltagarna konverterar först h till en punkt på kurvan med valfri fördefinierad funktion:

H = scalarToPoint(h)

Sedan varje deltagare i beräknar och publicerar Hej = p(i)H, vad kan de göra för att de vet p(i) och H. Avslöjande HJag tillåter inte andra deltagare att återställa den privata komponenten ideltagare, och därför kan en uppsättning privata komponenter användas från block till block. Således behöver den dyra polynomgenereringsalgoritmen som beskrivs nedan bara exekveras en gång.

När k deltagare obducerades Hej = p(i)H, alla kan räkna Hx = p(x)H för alla x tack vare egenskapen hos polynom som vi diskuterade i förra avsnittet. I detta ögonblick räknar alla deltagare H0 = p(0)H, och detta är det resulterande slumptalet. Observera att ingen vet p(0), och därför det enda sättet att beräkna p(0)H – detta är interpolation p(x)H, vilket bara är möjligt när k värden p(i)H känd. Öppna valfri mindre kvantitet p(i)H lämnar ingen information om p(0)H.

Generatorn ovan har alla egenskaper vi vill ha: angripare som endast kontrollerar k-1 deltagare eller mindre har ingen information eller inflytande på slutsatsen, medan någon k deltagare kan beräkna det resulterande antalet, och vilken delmängd som helst av k deltagare kommer alltid till samma resultat för samma frö.

Det finns ett problem som vi noggrant undvek ovan. För att interpolering ska fungera är det viktigt att värdet Hi som publicerades av varje deltagare i det var verkligen samma sak p(i)H. Eftersom ingen utom i-deltagaren vet inte pi), ingen utom i-deltagaren kan inte verifiera det Hi faktiskt beräknat korrekt, och utan något kryptografiskt bevis på riktighet Hjag en angripare kan publicera vilket värde som helst som Hej, och godtyckligt påverka utsignalen från slumptalsgeneratorn:

Olika värden på H_1 skickade av den första deltagaren leder till olika resulterande H_0

Det finns åtminstone två sätt att bevisa riktighet Hi, vi kommer att överväga dem efter att vi analyserat genereringen av polynomet.

Polynomgenerering

I det sista avsnittet antog vi att vi har ett sådant polynom p(x) grader k-1 att deltagaren i vet pi), och ingen annan har någon information om detta värde. I nästa avsnitt kommer vi också att behöva det för någon förutbestämd punkt G alla visste p(x)G för alla x.

I det här avsnittet kommer vi att anta att varje deltagare lokalt har någon privat nyckel xi, så att alla känner till motsvarande publika nyckel Xi.

Ett möjligt polynomgenereringsprotokoll är följande:

1. Varje deltagare i skapar lokalt ett godtyckligt polynom pi(x) grad k-1. De skickar sedan varje deltagare j betyder pi(j), krypterad med publik nyckel Xj. Endast alltså i-th и j-th deltagaren vet pI j). Deltagare i meddelar också offentligt pi(j)G för alla j från 1 до k inkluderande.

2. Alla deltagare använder viss konsensus för att välja k deltagare vars polynom kommer att användas. Eftersom vissa deltagare kan vara offline kan vi inte vänta tills alla n deltagarna kommer att publicera polynom. Resultatet av detta steg är en uppsättning Z bestående av åtminstone k polynom skapade i steg (1).

3. Deltagarna ser till att de värderingar de känner till pi(j) motsvarar offentligt tillkännagiven pi(j)G. Efter detta steg in Z endast polynom för vilka sänds privat pi(j) motsvarar offentligt tillkännagiven pi(j)G.

4. Varje deltagare j beräknar sin privata komponent p(j) som en summa pi(j) för alla i в Z. Varje deltagare räknar också ut alla värden p(x)G som en summa pi(x)G för alla i в Z.

Observera att p(x) – det är verkligen ett polynom k-1, eftersom det är summan av individen pi(x), som vart och ett är ett gradpolynom k-1. Observera sedan att medan varje deltagare j vet p(j), de har ingen information om p(x) för x ≠ j. För att beräkna detta värde måste de faktiskt veta allt pi(x), och så länge som deltagaren j inte känner till minst ett av de valda polynomen, de har inte tillräcklig information om p(x).

Detta är hela polynomgenereringsprocessen som behövdes i det sista avsnittet. Steg 1, 2 och 4 ovan har en ganska uppenbar implementering. Men steg 3 är inte så trivialt.

Specifikt måste vi kunna bevisa det krypterade pi(j) verkligen motsvarar de publicerade pi(j)G. Om vi ​​inte kan bevisa det, angriparen i får skicka sopor istället pi(j) till deltagare j, och deltagare j kommer inte att kunna få den verkliga meningen pi(j), och kommer inte att kunna beräkna sin privata komponent.

Det finns ett kryptografiskt protokoll som låter dig skapa ett extra meddelande bevisi(j), så att varje deltagare, har något värde e, samt proofi(j) и pi(j)G, kan lokalt verifiera det e - det är verkligen pi(j), krypterad med deltagarens nyckel j. Tyvärr är storleken på sådana bevis otroligt stor, och med tanke på att det är nödvändigt att publicera O (nk) Sådana bevis kan inte användas för detta ändamål.

Istället för att bevisa det pi(j) motsvarar pi(j)G vi kan allokera en mycket lång tidsperiod i polynomgenereringsprotokollet, under vilken alla deltagare kontrollerar det mottagna krypterade pi(j), och om det dekrypterade meddelandet inte motsvarar allmänheten pi(j)G, de publicerar ett kryptografiskt bevis på att det krypterade meddelandet de fick är felaktigt. Bevisa att meddelandet ingen motsvarar gris) mycket lättare än att bevisa att det stämmer. Det bör noteras att detta kräver att varje deltagare dyker upp online minst en gång under den tid som tilldelats för att skapa sådana bevis, och förlitar sig på antagandet att om de publicerar ett sådant bevis kommer det att nå alla andra deltagare inom samma tilldelade tid.

Om en deltagare inte dök upp online under denna tidsperiod, och han hade minst en felaktig komponent, kommer den specifika deltagaren inte att kunna delta i ytterligare nummergenerering. Protokollet kommer dock fortfarande att fungera om det finns åtminstone k deltagare som antingen precis fått rätt komponenter eller lyckats lämna bevis på felaktigheter inom utsatt tid.

Bevis på riktigheten av H_i

Den sista delen som återstår att diskutera är hur man bevisar riktigheten av publicerade Hjag, nämligen det Hej = p(i)H, utan öppning pi).

Låt oss komma ihåg att värdena H, G, p(i)G offentliga och kända för alla. Ta emot operation pi) menande gris и G kallas diskret logaritm, eller hund, och vi vill bevisa att:

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

utan avslöjande pi). Konstruktioner för sådana bevis finns till exempel Schnorr-protokollet.

Med denna design, varje deltagare, tillsammans med Hi skickar ett korrekthetsbevis enligt designen.

När ett slumptal väl har genererats behöver det ofta användas av andra deltagare än de som genererat det. Sådana deltagare, tillsammans med numret, måste skicka alla Hi och relaterade bevis.

En nyfiken läsare kan fråga: eftersom det slutliga slumptalet är H0, och p(0)G – Detta är offentlig information, varför behöver vi bevis för varje individ Hjag, varför inte skicka bevis på det istället

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

Problemet är att ett sådant bevis inte kan skapas med hjälp av Schnorr-protokollet eftersom ingen vet värdet p (0), nödvändigt för att skapa beviset, och dessutom är hela slumptalsgeneratorn baserad på det faktum att ingen känner till detta värde. Därför är det nödvändigt att ha alla värden Hi och deras individuella bevis för att bevisa riktigheten H0.

Men om det fanns någon operation på punkter på elliptiska kurvor som är semantiskt lik multiplikation, beviset på korrekthet H0 skulle vara trivialt, det skulle vi helt enkelt se till

H0 × G = p(0)G × H

Om den valda kurvan stöder elliptiska kurvpar, detta bevis fungerar. I detta fall H0 är inte bara resultatet av en slumptalsgenerator, som kan verifieras av alla deltagare som vet G,H и p(0)G. H0 är också en signatur på meddelandet som användes som frö, vilket bekräftar det k и n deltagare undertecknade detta meddelande. Alltså om frö - är hash för blocket i blockchain-protokollet, alltså H0 är både en multisignatur på ett block och ett mycket bra slumptal.

Sammanfattningsvis

Den här artikeln är en del av en teknisk bloggserie NEAR. NEAR är ett blockchain-protokoll och plattform för att utveckla decentraliserade applikationer med tonvikt på enkel utveckling och användarvänlighet för slutanvändare.

Protokollkoden är öppen, vår implementering är skriven i Rust, den kan hittas här.

Du kan se hur utvecklingen för NEAR ser ut och experimentera i online-IDE här.

Du kan följa alla nyheter på ryska på telegramgrupp och grupp på VKontakte, och på engelska i det officiella Twitter.

Ses snart!

Källa: will.com