Да ли је могуће генерисати насумичне бројеве ако не верујемо једни другима? Део 2

Хеј Хабр!

В први део У овом чланку смо расправљали о томе зашто би било потребно генерисати случајне бројеве за учеснике који не верују једни другима, који су захтеви постављени за такве генераторе случајних бројева и размотрили два приступа њиховој примени.

У овом делу чланка детаљније ћемо погледати још један приступ који користи потписе прага.

Мало криптографије

Да бисте разумели како функционишу потписи прага, морате разумети мало основне криптографије. Користићемо два концепта: скаларе или једноставно бројеве, које ћемо означавати малим словима (к, и) и тачке на елиптичној кривој, које ћемо означити великим словима.

Да бисте разумели основе граничних потписа, не морате да разумете како функционишу елиптичне криве, осим неколико основних ствари:

1. Тачке на елиптичној кривој се могу сабирати и множити скаларом (множење скаларом ћемо означити као xG, иако нотација Gx такође често коришћени у литератури). Резултат сабирања и множења скаларом је тачка на елиптичној кривој.

2. Знајући само поенту G а његов производ са скаларом xG не може се израчунати x.

Користићемо и концепт полинома п(к) степен стручне спреме k-1. Посебно ћемо користити следеће својство полинома: ако знамо вредност п(к) за сваки k различит x (и немамо више информација о п(к)), можемо израчунати п(к) за било кога другог x.

Занимљиво је да за било који полином п(к) и нека тачка на кривини Gзнајући значење п(к)Г за сваки k различита значења x, такође можемо израчунати п(к)Г за сваки x.

Ово је довољно информација да се копа у детаље о томе како функционишу гранични потписи и како их користити за генерисање случајних бројева.

Генератор случајних бројева на граничним потписима

Рецимо то n учесници желе да генеришу насумични број, а ми желимо да било ко учествује k било их је довољно да се генерише број, али тако да нападачи који контролишу k-1 или мање учесника није могло да предвиди или утиче на генерисани број.

Претпоставимо да постоји такав полином п(к) степен стручне спреме k-1 шта први учесник зна п (1), други зна п(2), и тако даље (n-тх зна п(н)). Такође претпостављамо да за неку унапред одређену тачку G сви знају п(к)Г за све вредности x. Позваћемо п(и) “приватна компонента” iучесника (јер само iтх учесник је познаје), и п(и)Г "јавна компонента" i-тх учесник (јер је сви учесници познају). Као што се сећате, знање п(и)Г није довољно за обнављање п(и).

Стварање таквог полинома тако да само i-Први учесник и нико други није знао његову приватну компоненту - ово је најсложенији и најзанимљивији део протокола, а ми ћемо га анализирати у наставку. За сада, претпоставимо да имамо такав полином и да сви учесници знају своје приватне компоненте.

Како можемо користити такав полином да генеришемо случајни број? За почетак нам је потребан неки низ који раније није коришћен као улаз за генератор. У случају блоцкцхаина, хеш последњег блока h је добар кандидат за такву линију. Нека учесници желе да креирају насумични број користећи h као семе. Учесници се прво претварају h до тачке на кривој користећи било коју унапред дефинисану функцију:

Х = скаларна тачка(х)

Затим сваки учесник i израчунава и објављује Хи = п(и)Х, шта могу јер знају п(и) и Х. Дисцлосуре Hне дозвољавам другим учесницима да обнове приватну компоненту iтх учесника, па се стога један скуп приватних компоненти може користити од блока до блока. Дакле, скупи алгоритам за генерисање полинома описан у наставку треба да се изврши само једном.

Када k учесници су обдуковани Хи = п(и)Х, свако може да израчуна Hк = п(к)Х за све x захваљујући својству полинома о којима смо говорили у прошлом одељку. У овом тренутку сви учесници калкулишу Х0 = п(0)Х, а ово је резултујући случајни број. Имајте на уму да нико не зна п(0), а самим тим и једини начин израчунавања п(0)Х – ово је интерполација п(к)Х, што је једино могуће када k вредности п(и)Х познат. Отварање било које мање количине п(и)Х не даје никакве информације о п(0)Х.

Генератор изнад има сва својства која желимо: само нападачи контролишу k-1 учесник или мање нема информација или утицаја на закључак, док било који k учесници могу израчунати резултујући број и било који подскуп од k учесници ће увек доћи до истог резултата за исто семе.

Постоји један проблем који смо пажљиво избегли горе. Да би интерполација функционисала, важно је да вредност Hи који је објавио сваки учесник i заиста је било исто п(и)Х. Пошто нико осим i-тх учесник не зна п(и), нико осим i-учесник то не може да потврди Hi заправо израчунато исправно, и без икаквог криптографског доказа исправности Hи нападач може објавити било коју вредност као Здраво, и произвољно утичу на излаз генератора случајних бројева:

Различите вредности Х_1 које је послао први учесник доводе до различитих резултујућих Х_0

Постоје најмање два начина да се докаже тачност Hи, размотрићемо их након што анализирамо генерисање полинома.

Генерисање полинома

У последњем одељку претпоставили смо да имамо такав полином п(к) степен стручне спреме k-1 да је учесник i зна п(и), и нико други нема никакве информације о овој вредности. У следећем одељку ће нам то такође требати за неку унапред одређену тачку G сви су знали п(к)Г за све x.

У овом одељку ћемо претпоставити да сваки учесник локално има неки приватни кључ ки, тако да сви знају одговарајући јавни кључ Xi.

Један могући протокол генерисања полинома је следећи:

1. Сваки учесник i локално ствара произвољан полином пи(к) степен к-1. Затим шаљу сваког учесника j вредност pи(ј), шифровано јавним кључем Ксј. Само тако i-тх и j-тх учесник зна pи(ј). Учесник i такође јавно саопштава пи(ј)Г за све j из 1 до k инцлусиве.

2. Сви учесници користе одређени консензус да бирају k учесници чији ће се полиноми користити. Пошто су неки учесници можда ван мреже, не можемо да чекамо да сви n учесници ће објавити полиноме. Резултат овог корака је скуп Z који се састоји од најмање k полиноми креирани у кораку (1).

3. Учесници се постарају да вредности које познају pи(ј) одговара јавно објављеном пи(ј)Г. Након овог корака у Z само полиноми за које се приватно преносе pи(ј) одговара јавно објављеном пи(ј)Г.

4. Сваки учесник j израчунава своју приватну компоненту п(ј) као збир pи(ј) за све i в Z. Сваки учесник такође израчунава све вредности п(к)Г као збир пи(к)Г за све и в Z.

Имајте на уму да п(к) – то је заиста полином к-1, јер је збир појединца pи(к), од којих је сваки полином степена k-1. Затим, имајте на уму да док сваки учесник j зна п(ј), немају информација о п(к) за к = ј. Заиста, да би израчунали ову вредност, они морају да знају све пи(к), а све док учесник j не познаје бар један од изабраних полинома, немају довољно информација о п(к).

Ово је цео процес генерисања полинома који је био потребан у последњем одељку. Кораци 1, 2 и 4 изнад имају прилично очигледну имплементацију. Али корак 3 није тако тривијалан.

Конкретно, морамо бити у могућности да то докажемо шифровано pи(ј) заиста одговарају објављеним пи(ј)Г. Ако то не можемо да докажемо, нападач i уместо тога може послати смеће pи(ј) учеснику j, и учесник j неће моћи да добије праву вредност пи(ј), и неће моћи да израчуна своју приватну компоненту.

Постоји криптографски протокол који вам омогућава да креирате додатну поруку докази(ј), тако да сваки учесник има неку вредност e, као и доказ(ј) и pи(ј)Г, то може локално да провери e - то је заиста пи(ј), шифрован кључем учесника j. Нажалост, величина таквих доказа је невероватно велика, а с обзиром на то да је неопходно објавити О(нк) Такви докази се не могу користити у ову сврху.

Уместо да то докажем пи(ј) одговара pи(ј)Г можемо доделити веома велики временски период у протоколу генерисања полинома, током којег сви учесници проверавају примљене шифроване пи(ј), а ако дешифрована порука не одговара јавности pи(ј)Г, објављују криптографски доказ да је шифрована порука коју су примили нетачна. Докажите да је порука не одговара пи(Г) много лакше него доказати да се поклапа. Треба напоменути да ово захтева да се сваки учесник појави на мрежи најмање једном током времена предвиђеног за креирање таквог доказа, и ослања се на претпоставку да ће, ако објави такав доказ, стићи до свих осталих учесника у истом додељеном времену.

Ако се учесник није појавио на мрежи током овог временског периода и имао је бар једну погрешну компоненту, тада тај одређени учесник неће моћи да учествује у даљем генерисању бројева. Протокол ће, међутим, и даље функционисати ако постоји барем k учесници који су или само добили исправне компоненте или су успели да оставе доказ о нетачности у предвиђеном времену.

Докази исправности Х_и

Последњи део о коме остаје да се разговара је како доказати тачност објављеног Hја, наиме то Хи = п(и)Х, без отварања п(и).

Подсетимо се да су вредности Х, Г, п(и)Г јавно и свима познато. Операција пријема п(и) знајући п(и)Г и G назива се дискретни логаритам, или длог, и желимо да докажемо да:

длог(п(и)Г, Г) = длог(Хi, H)

без обелодањивања п(и). Конструкције за такве доказе постоје, на пример Сцхнорр Протоцол.

Са овим дизајном, сваки учесник, заједно са Hi шаље доказ о исправности према пројекту.

Једном када се генерише насумични број, често га морају користити учесници који нису они који су га генерисали. Такви учесници, заједно са бројем, морају послати све Hi и повезани докази.

Радознали читалац може питати: пошто је коначни случајни број H0, и п(0)Г – Ово је јавна информација, зашто нам треба доказ за сваког појединца Hја, зашто не послати доказ да уместо тога

длог(п(0)Г, Г) = длог(Х0, H)

Проблем је у томе што се такав доказ не може креирати коришћењем Шноровог протокола јер нико не зна вредност п (0), неопходно за креирање доказа, и штавише, цео генератор случајних бројева је заснован на чињеници да нико не зна ову вредност. Зато је неопходно имати све вредности Hi и њихове појединачне доказе који доказују тачност H0.

Међутим, ако је постојала нека операција на тачкама на елиптичним кривинама која је семантички слична множењу, доказ исправности H0 било би тривијално, једноставно бисмо се у то уверили

HКСНУМКС × G = п(0)Г × Х

Ако изабрана крива подржава упаривања елиптичких кривих, овај доказ ради. У овом случају H0 није само излаз генератора случајних бројева, који може да провери сваки учесник који зна Г, Х и п(0)Г. Х0 је такође потпис на поруци која је коришћена као семе, што потврђује то k и n учесници су потписали ову поруку. Дакле, ако семе - је хеш блока у блокчеин протоколу, дакле H0 је и вишеструки потпис на блоку и веома добар случајни број.

У закључку

Овај чланак је део серије техничких блогова NEAR. НЕАР је блокчејн протокол и платформа за развој децентрализованих апликација са нагласком на лакоћу развоја и лакоћу коришћења за крајње кориснике.

Код протокола је отворен, наша имплементација је написана у Русту, може се наћи овде.

Можете видети како изгледа развој за НЕАР и експериментисати у онлајн ИДЕ-у овде.

Све вести на руском можете пратити на телеграм група и група на ВКонтакте, а на енглеском у службеном твиттер.

Видимо се ускоро!

Извор: ввв.хабр.цом