Hallo, Habr!
In In dit artikel hebben we besproken waarom het nodig kan zijn om willekeurige getallen te genereren voor deelnemers die elkaar niet vertrouwen, welke eisen er worden gesteld aan dergelijke willekeurige getallengenerators, en we hebben twee benaderingen voor hun implementatie bekeken.
In dit deel van het artikel zullen we een andere aanpak bespreken die gebruik maakt van drempelhandtekeningen.
Een beetje cryptografie
Om te begrijpen hoe drempelhandtekeningen werken, moet je een beetje basiscryptografie begrijpen. We zullen twee concepten gebruiken: scalairs, of gewoon getallen, die we zullen aanduiden met kleine letters (x, y) en punten op een elliptische curve, die we zullen aanduiden met hoofdletters.
Voor het begrijpen van de basisprincipes van drempelhandtekeningen is het niet nodig om te begrijpen hoe elliptische curves werken, behalve enkele basisdingen:
Punten op een elliptische curve kunnen worden opgeteld en vermenigvuldigd met een scalar (vermenigvuldigen met een scalar zullen we aanduiden als xG, hoewel de notatie Gx ook vaak in de literatuur wordt gebruikt). De uitkomst van de optelling en vermenigvuldiging met een scalar is een punt op de elliptische curve.
Alleen met het punt G en zijn vermenigvuldiging met een scalar xG kan niet worden berekend x.
We zullen ook het concept van een polynoom gebruiken p(x) van graad k-1. In het bijzonder zullen we het volgende kenmerk van polynomen gebruiken: als we de waarde kennen p(x) voor elke k verschillende x (en geen extra informatie hebben over p(x)), kunnen we berekenen p(x) voor elk ander x.
Het is interessant dat voor elke polynoom p(x) en een bepaald punt op de curve G, door de waarde te kennen p(x)G voor elke k van verschillende waarden x, kunnen we ook berekenen p(x)G voor elke x.
Deze informatie is voldoende om in detail te duiken in hoe drempelhandtekeningen werken en hoe ze kunnen worden gebruikt voor de generatie van willekeurige getallen.
Willekeurige getallengenerator op basis van drempelhandtekeningen
Stel dat n deelnemers een willekeurig getal willen genereren, en we willen dat deelname van enige k van hen voldoende is om een getal te genereren, maar dat kwaadwillenden die controle hebben over k-1 of minder deelnemers, het gegenereerde getal niet kunnen voorspellen of beïnvloeden.
Stel dat er zo'n polynoom bestaat p(x) van graad k-1, zodat de eerste deelnemer weet p(1), de tweede weet p(2), enzovoort (n-de weet p(n)). Laten we ook aannemen dat voor een bepaald vooraf bepaald punt G iedereen weet p(x)G voor alle waarden xWij zullen noemen p(i) “privécomponent” i-de deelnemer (omdat alleen i-de deelnemer deze kent), en p(i)G “publieke component” i-de deelnemer (omdat alle deelnemers deze kennen). Zoals je je herinnert, is kennis p(i)G niet genoeg om te herstellen p(i).
Het creëren van zo'n polynoom zodat alleen i-dedeelnemer en niemand anders zijn privécomponent kent – is het moeilijkste en interessantste deel van het protocol, en we zullen dit verderop behandelen. Laten we voorlopig aannemen dat we zo'n polynoom hebben, en dat alle deelnemers hun privécomponenten kennen.
Hoe kunnen we zo'n polynoom gebruiken om een willekeurig getal te genereren? Allereerst hebben we een bepaalde string nodig die eerder niet is gebruikt als invoer voor de generator. In het geval van de blockchain is de hash van het laatste blok h — een goede kandidaat voor zo'n string. Laten we aannemen dat de deelnemers een willekeurig getal willen creëren met behulp van h als seed. Eerst converteren de deelnemers h in een punt op de curve door een vooraf bepaalde functie te gebruiken:
H = scalarToPoint(h)
Vervolgens berekent elke deelnemer i en publiceert Hi = p(i)H, wat ze kunnen doen omdat ze kennen p(i) en H. Het onthullen Hi staat andere deelnemers niet toe om de privécomponent van de i-de deelnemer te herstellen, en daarom kan één set privécomponenten van blok naar blok worden gebruikt. Zo moet het dure algoritme voor het creëren van een polynoom, dat hieronder wordt beschreven, slechts één keer worden uitgevoerd.
Wanneer k de deelnemers zijn onthuld, Hi = p(i)H, kan iedereen berekenen Hx = p(x)H dankzij de eigenschap van polynomen die we in de vorige sectie hebben besproken. Op dit moment berekenen alle deelnemers x H0 = p(0)H, en dit is het resulterende willekeurige getal. Let op dat niemand weet p(0), en daarom is de enige manier om te berekenen p(0)H – dit is interpolatie p(x)H, wat alleen mogelijk is wanneer de waarden k p(i)H bekend zijn. Het onthullen van minder dan geeft geen informatie over bekend zijn. Het onthullen van minder dan p(0)H. De generator hierboven heeft alle eigenschappen die we willen: aanvallers die slechts
k- 1 deelnemers of minder controleren, hebben geen informatie of invloed op de uitvoer, terwijl elkedeelnemer het resulterende getal kan berekenen, en elk subset van k deelnemers zal altijd tot hetzelfde resultaat komen voor dezelfde seed. k deelnemers zullen altijd hetzelfde resultaat behalen voor dezelfde seed.
Er is één probleem dat we hierboven voorzichtig zijn omzeild. Om interpolatie te laten werken, is het belangrijk dat de waarde Hi die door elke deelnemer is gepubliceerd i werkelijk gelijk is aan p(i)H. Omdat niemand behalve i-de deelnemer weet p(i), weet niemand behalve i-dede deelnemer of Hi het werkelijk correct is berekend en zonder enige cryptografische bewijs van correctheid Hkan een aanvaller elke waarde publiceren als Hi, en willekeurig invloed uitoefenen op de uitvoer van de random number generator:
Verschillende waarden H_1, verzonden door de eerste deelnemer, leiden tot verschillende resulterende H_0
Er zijn minstens twee manieren om de correctheid te bewijzen Hi, die we zullen bespreken nadat we de generatie van het polynoombespreken.
Generatie van het polinoom
In de vorige sectie hebben we aangenomen dat we zo'n polinoom hebben p(x) van graad k-1 dat de deelnemer i weet p(i), en niemand anders heeft enige informatie over deze waarde. In de volgende sectie zullen we ook moeten zorgen dat voor een vooraf gedefinieerd punt G iedereen weet p(x)G dankzij de eigenschap van polynomen die we in de vorige sectie hebben besproken. Op dit moment berekenen alle deelnemers x.
In deze sectie veronderstellen we dat elke deelnemer lokaal een bepaalde privésleutel heeft xi, zodat de overeenkomstige publieke sleutel Xi algemeen bekend is.
Een mogelijk protocol voor de generatie van het polinoom is als volgt:
Elke deelnemer i creëert lokaal een willekeurig polinoom pi(x) van graad k-1. Ze verzenden vervolgens aan elke deelnemer j de waarde Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j), versleuteld met de publieke sleutel Xj. Zo weet alleen i-dede en j-de deelnemer Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j). De deelnemer i maakt ook publiekelijk bekend pi(j)G dankzij de eigenschap van polynomen die we in de vorige sectie hebben besproken. Op dit moment berekenen alle deelnemers j van 1 tot k inclusief.
Alle deelnemers gebruiken een soort consensus om te kiezen k de deelnemers wiens polynomen zullen worden gebruikt. Omdat sommige deelnemers offline kunnen zijn, kunnen we niet wachten tot iedereen n deelnemers hun polynomen publiceren. Het resultaat van deze stap is een verzameling Z die uit ten minste k polynomen bestaat, gemaakt in stap (1).
De deelnemers zorgen ervoor dat de waarden die ze kennen Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j) overeenkomen met publiekelijk aangekondigde pi(j)G. Na deze stap moeten er in Z alleen de polynomen overblijven waarvoor privé verzonden Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j) overeenkomen met publiekelijk aangekondigde pi(j)G.
Elke deelnemer j berekent zijn privécomponent p(j) als de som Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j) voor alle i in Z. Elke deelnemer berekent ook alle waarden p(x)G als de som pi(x)G voor alle i in Z.
Let op dat p(x) – dit is daadwerkelijk een polinoom van graad k-1, omdat dit de som is van afzonderlijke Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(x), waarvan elke een polinoom van graad k-1. Vervolgens, let op dat terwijl elke deelnemer j weet p(j), zij geen informatie hebben over p(x) voor x ≠ j. Inderdaad, om deze waarde te berekenen, moeten ze alles weten pi(x), en zolang de deelnemer j niet tenminste één van de gekozen polynomen weet, hebben zij niet genoeg informatie over p(x).
Dit is het gehele proces van het genereren van een polynoom, wat noodzakelijk was in het vorige gedeelte. Stappen 1, 2 en 4 hierboven hebben een vrij duidelijke uitvoering. Stap 3 is echter minder triviaal.
Specifiek moeten we in staat zijn te bewijzen dat de gecodeerde Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j) daadwerkelijk overeenkomen met de gepubliceerde pi(j)G. Als we dat niet kunnen bewijzen, kan een aanvaller i rommel in plaats van Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j) naar de deelnemer sturen j, en de deelnemer j kan de echte waarde niet verkrijgen pi(j), en zal zijn privécomponent niet kunnen berekenen..
Er is een cryptografisch protocol dat het mogelijk maakt een aanvullend bericht te creëren proofi(j), zodat elke deelnemer, met een bepaalde waarde e, en ook proofi(j) en Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j)G, lokaal kan verifiëren dat e dit daadwerkelijk pi(j), gecodeerd is met de sleutel van de deelnemer j. Helaas is de grootte van een dergelijk bewijs enorm groot, en gezien het feit dat er O(nk) van dergelijke bewijzen gepubliceerd moeten worden, kunnen ze niet voor dit doel gebruikt worden.
In plaats van te bewijzen dat pi(j) overeenkomt met Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j)G kunnen we in het protocol voor het genereren van de polynoom een zeer lange periode toewijzen, waarin alle deelnemers de ontvangen gecodeerde gegevens controleren pi(j), en als het gedecryptte bericht niet overeenkomt met de publieke Het commando geeft een lijst van onze huidige partities weer. In mijn geval één partitie van 30 GB en nog 20 GB in vrije ruimte, als ik dat zo mag zeggen.i(j)G, publiceren ze een cryptografisch bewijs dat aangeeft dat het ontvangene gecodeerde bericht ongeldig is. Bewijzen dat het bericht niet overeenkomt met pi(G) veel eenvoudiger is dan bewijzen dat het overeenkomt. Het is belangrijk op te merken dat dit vereist dat elke deelnemer ten minste één keer in het netwerk verschijnt tijdens de periode die is toegewezen voor het creëren van dergelijke bewijzen, en het leunt op de aanname dat als ze zo'n bewijs hebben gepubliceerd, het alle andere deelnemers binnen dezelfde tijd zal bereiken.
Als een deelnemer in deze periode niet online is verschenen en hij daadwerkelijk minstens één onjuiste component had, kan deze specifieke deelnemer niet deelnemen aan de verdere getallengeneratie. Het protocol zal echter nog steeds functioneren als er minstens k deelnemers zijn die ofwel alleen maar correcte componenten hebben ontvangen of ervoor hebben gezorgd dat bewijs van onjuistheid binnen de gestelde tijd is overgelegd.
Bewijzen van correctheid H_i
Het laatste deel dat we moeten bespreken is hoe we de correctheid van de gepubliceerde Hi, namelijk dat Hi = p(i)H, zonder onthulling p(i).
Laten we ons herinneren dat de waarden H, G, p(i)G publiek en voor iedereen bekend zijn. De operatie om te verkrijgen p(i) wanneer je weet p(i)G en G wordt de discrete logaritme genoemd, of dlog, en we willen bewijzen dat:
dlog(p(i)G, G) = dlog(Hi, H)
zonder onthulling p(i). Constructies voor dergelijke bewijzen bestaan, bijvoorbeeld.
Met zo'n constructie stuurt elke deelnemer samen met Hi een bewijs van correctheid volgens de constructie op.
Wanneer een willekeurig getal is gegenereerd, moet het vaak worden gebruikt door deelnemers die verschillen van degene die het heeft gegenereerd. Dergelijke deelnemers moeten samen met het getal alle Hi en bijbehorende bewijsstukken ontvangen.
Een nieuwsgierige lezer kan zich afvragen: omdat het eindresultaat willekeurige getal - dat is H0, en p(0)G - dit is publiek beschikbare informatie, waarom is er bewijs nodig voor elk afzonderlijk Hi, waarom niet gewoon bewijs sturen dat
dlog(p(0)G, G) = dlog(H0, H)
Het probleem is dat met behulp van het Schnorr Protocol zo'n bewijs niet kan worden gemaakt, omdat niemand de waarde kent p(0), die nodig is om het bewijs op te stellen, en bovendien is de gehele willekeurige getallengenerator gebaseerd op het feit dat niemand deze waarde kent. Daarom is het noodzakelijk om alle waarden Hi en hun individuele bewijzen te hebben om de correctheid te bewijzen. H0.
Als er echter een operatie op de punten van elliptische krommen zou zijn die semantisch lijkt op vermenigvuldiging, zou het bewijs van correctheid H0 triviaal zijn, we zouden gewoon controleren dat
H0 × G = p(0)G × H
Als de gekozen kromme elliptische kromme paringen ondersteunt, 0 is niet alleen de uitvoer van de willekeurige getallengenerator die elke deelnemer kan controleren die weet HG, H p(0)G. H en p(0)G. H0 – dit is ook een handtekening op het bericht dat als seed werd gebruikt, ter bevestiging dat k en n de deelnemers dit bericht hebben ondertekend. Dus, als seed – dit een hash van een blok in het blockchainprotocol is, dan H0 is het tegelijkertijd een multi-handtekening op het blok en een zeer goed willekeurig getal.
Ter conclusie
Dit artikel maakt deel uit van een serie technische artikelen in de blog . NEAR is een blockchainprotocol en platform voor de ontwikkeling van gedecentraliseerde applicaties, met de nadruk op eenvoud van ontwikkeling en gebruiksgemak voor eindgebruikers.
De protocolcode is open, onze implementatie is geschreven in Rust en kan worden gevonden .
Bekijk hoe ontwikkeling op NEAR eruit ziet en experimenteer in de online IDE .
Volg al het nieuws in het Russisch op en in , en in het Engels in de officiële .
Tot snel!
Bron: habr.com
