Ä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å metoder för deras implementering.

I den här delen av artikeln ska vi titta närmare på en annan metod som använder tröskelsignaturer.

Lite kryptografi

För att förstå hur tröskelsignaturer fungerar behöver 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 gemener (x, y) och punkter på den elliptiska kurvan, vilka vi kommer att beteckna med versaler.

För att förstå grunderna i 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 betecknar 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 polynombegreppet p(x) grader k-1. Vi kommer särskilt att använda följande polynomegenskap: om vi känner till värdet p(x) för vilken som helst k annorlunda x (och vi har ingen ytterligare information om p(x)), kan vi beräkna p(x) för alla andra x.

Det är intressant att för vilket polynom som helst p(x) och någon punkt på kurvan G, medveten om betydelsen p(x)G för vilken som helst k olika betydelser x, kan du också beräkna p(x)G för vilken som helst x.

Denna information räcker för att gräva i detaljerna om hur tröskelsignaturer fungerar och hur man använder dem för att generera slumptal.

Slumptalsgenerator för tröskelsignaturer

Låt oss anta att n deltagarna vill generera ett slumptal, och vi vill att alla ska delta k av dem var tillräckliga 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 det genererade talet.

Låt oss 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-th vet p(n)). Låt oss också anta att för någon förutbestämd punkt G alla vet p(x)G för alla värden x. Vi kommer att ringa pi) "privat komponent" i-te deltagaren (eftersom endast i-e deltagaren känner henne), och gris "offentlig komponent" i-e deltagaren (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 endast i-den:e 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 den nedan. Låt oss för tillfället anta att vi har ett sådant polynom, och alla deltagare känner till sina privata komponenter.

Hur kan vi använda ett sådant polynom för att generera ett slumptal? Först behöver vi en sträng som inte har använts som indata till generatorn tidigare. När det gäller en blockkedja, hashen för det sista blocket h — är en bra kandidat för en sådan linje. Låt deltagarna vilja generera ett slumptal med hjälp av h som frö. Först konverterar deltagarna h till en punkt på kurvan med hjälp av en fördefinierad funktion:

H = skalärTillPunkt(h)

Sedan varje deltagare i beräknar och publicerar Hi = p(i)H, vad de kan göra eftersom de vet p(i) och H. Avslöjande Hi tillåter inte andra deltagare att återställa den privata komponenten i-te deltagaren, 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 utföras en gång.

När k deltagarna exponerades Hi = p(i)H, alla kan lista ut det Hx = p(x)H för alla x tack vare polynomegenskapen som vi diskuterade i föregående avsnitt. Vid denna tidpunkt beräknar alla deltagare H0 = p(0)H, och detta är det resulterande slumpmässiga talet. Observera att ingen vet p(0), och därför det enda sättet att räkna p(0)H – detta är en interpolering p(x)H, vilket bara är möjligt när k värden p(i)H är kända. Öppning av mindre kvantiteter p(i)H ger ingen information om p(0)H.

Generatorn ovan har alla egenskaper vi vill ha: angripare som endast kontrollerar k-1 eller färre deltagare har ingen information eller inflytande på resultatet, medan alla k deltagarna kan beräkna det resulterande talet och vilken delmängd som helst av k Deltagarna kommer alltid att komma fram 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 jämnt p(i)H. Eftersom ingen annan i-deltagaren vet inte pi), ingen annan än i-deltagaren kan inte verifiera att Hi den beräknades faktiskt korrekt, och utan kryptografiskt bevis på korrektheten Hen angripare kan publicera vilket värde som helst som Hej, och godtyckligt påverka utdata från slumptalsgeneratorn:

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

Det finns minst två sätt att bevisa riktigheten Hi, vi kommer att betrakta dem efter att vi har analyserat polynomets generering.

Polynomgenerering

I förra avsnittet antog vi att vi har ett sådant polynom p(x) grader k-1 vilken deltagare i vet pi), och ingen annan har någon information om denna betydelse. I nästa avsnitt behöver vi också det för en förutbestämd punkt G alla visste p(x)G för alla x.

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

Ett möjligt protokoll för polynomgenerering är följande:

1. Varje deltagare i skapar lokalt ett godtyckligt polynom pi(x) av graden k-1. Sedan skickar de den till varje deltagare j betyder pi(j), krypterad med den publika nyckeln Xj. Så bara i-th и j-th deltagaren vet pi(j). Deltagare i tillkännager även offentligt pi(j)G för alla j från 1 до k inkluderande.

2. Alla deltagare använder någon form av 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 minst k polynom skapade i steg (1).

3. Deltagarna är övertygade om att de värderingar de känner till pi(j) motsvarar offentligt tillkännagivna pi(j)G. Efter detta steg i Z endast polynom för vilka privat överförda pi(j) motsvarar offentligt tillkännagivna pi(j)G.

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

Observera att p(x) – detta är verkligen ett gradpolynom k-1, eftersom det är summan av individen pi(x), som vart och ett är ett polynom av grad k-1. Lägg sedan märke till 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 behöver de faktiskt veta allt pi(x), och medan deltagaren j känner inte till minst ett av de valda polynomen, har de inte tillräcklig information om p(x).

Detta är hela processen för att generera polynomet som behövdes i förra avsnittet. Steg 1, 2 och 4 ovan har en ganska uppenbar implementering. Men steg 3 är inte så trivialt.

Mer specifikt behöver vi kunna bevisa att krypterad pi(j) motsvarar de publicerade pi(j)G. Om vi ​​inte kan bevisa det, angriparen i kan skicka skräp istället pi(j) deltagare joch deltagare j kommer inte att kunna förstå den verkliga innebörden pi(j), och kommer inte att kunna beräkna dess privata komponent.

Det finns ett kryptografiskt protokoll som låter dig skapa ett ytterligare meddelande bevisi(j), så att varje deltagare, som har något värde e, samt bevis(j) и pi(j)G, kan lokalt verifiera att e - det är verkligen pi(j), krypterad med deltagarens nyckel j. Tyvärr är omfattningen av sådana bevis otroligt stor, och med tanke på att de behöver publiceras O (nk) sådan bevisning kan inte användas för detta ändamål.

Istället för att bevisa att pi(j) motsvarar pi(j)G kan vi allokera en mycket stor tidsperiod i polynomgenereringsprotokollet, under vilken alla deltagare kontrollerar den mottagna krypterade pi(j), och om det dekrypterade meddelandet inte matchar det offentliga pi(j)G, de publicerar ett kryptografiskt bevis på att det krypterade meddelandet de mottagit är felaktigt. Bevisa att meddelandet ingen motsvarar gris) mycket enklare än att bevisa att det stämmer överens. Det bör noteras att detta kräver att varje deltagare dyker upp online minst en gång under den avsatta tiden för att skapa sådana bevis, och bygger på antagandet att om de publicerar ett sådant bevis kommer det att nå alla andra deltagare inom samma avsatta tid.

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

Bevis på riktigheten av H_i

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

Låt oss komma ihåg att värderingarna H, G, p(i)G offentlig och känd för alla. Mottagningsoperation pi) menande gris и G kallas diskret logaritm, eller dlog, 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 bevis på korrekthet enligt konstruktionen.

När ett slumptal väl har genererats behöver det ofta användas av andra deltagare än de som genererade det. Sådana deltagare måste skicka all information tillsammans med numret. Hi och stödjande bevis.

En nyfiken läsare kanske frågar: 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 istället för att

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

Problemet är att man inte kan skapa ett sådant bevis med Schnorr-protokollet eftersom ingen känner till värdet. p(0), vilket är 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.

Om det emellertid fanns någon operation på punkter på elliptiska kurvor som semantiskt liknade multiplikation, skulle beviset för korrekthet H0 det vore trivialt, vi skulle helt enkelt se till att

H0 × G = p(0)G × H

Om den valda kurvan stöder elliptiska kurvpar, sådana bevis fungerar. I det här fallet H0 är inte bara utdata från en slumptalsgenerator som kan verifieras av vilken deltagare som helst som vet G, H и p(0)G. H0 är också signaturen på meddelandet som användes som frö, vilket bekräftar att k и n deltagarna undertecknade detta meddelande. Så, om frö – detta är hashen för ett block i blockkedjeprotokollet, då H0 – det är både en multisignatur på blocket och ett mycket bra slumptal.

Sammanfattningsvis

Den här artikeln är en del av en teknisk bloggserie NEAR. NEAR är ett blockkedjeprotokoll och en plattform för att utveckla decentraliserade applikationer med fokus 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