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

Еј Хабр!

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

Во овој дел од статијата, ќе разгледаме подетално друг пристап кој користи праг потписи.

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

За да разберете како функционираат потписите на прагот, треба да разберете малку основна криптографија. Ќе користиме два концепта: скалари, или едноставно броеви, кои ќе ги означиме со мали букви (x, y) и точки на елиптичната крива, кои ќе ги означиме со големи букви.

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

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

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

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

Интересно е што за секој полином p (x) и некоја точка на кривата Gзнаејќи го значењето p(x)G за се ` k различни значења x, можеме и да пресметаме p(x)G за се ` x.

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

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

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

Да претпоставиме дека постои таков полином p (x) степени k-1 што знае првиот учесник стр (1), вториот знае p (2), и така натаму (n-ти знае p(n)). Исто така, претпоставуваме дека за некоја однапред одредена точка G секој знае p(x)G за сите вредности x. Ќе се јавиме p(i) „приватна компонента“ iти учесник (затоа што само iја познава тиот учесник), и p(i)G „јавна компонента“ i-ти учесничка (бидејќи ја знаат сите учесници). Како што се сеќавате, знаење p(i)G не е доволно за обновување p(i).

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

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

H = скаларенДоточка(h)

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

Кога k на учесниците им е извршена обдукција Здраво = p(i)H, секој може да пресмета Hx = p(x)H за сите x благодарение на својството на полиномите за кое разговаравме во последниот дел. Во овој момент сите учесници пресметуваат H0 = p(0)H, и ова е добиениот случаен број. Ве молиме имајте предвид дека никој не знае p (0), и затоа единствениот начин да се пресмета p(0)H - ова е интерполација p(x)H, што е можно само кога k вредности p(i)H познат. Отворање на која било помала количина p(i)H не дава никакви информации за p(0)H.

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

Има еден проблем што внимателно го избегнавме погоре. За да функционира интерполацијата, важно е вредноста Hi кој беше објавен од секој учесник i навистина беше исто p(i)H. Бидејќи никој освен i-ти учесник не знае p(i), никој освен i-учесникот не може да го потврди тоа Hi всушност правилно пресметан и без никаков криптографски доказ за исправност Hјас напаѓачот може да објави каква било вредност како Здраво, и произволно влијае на излезот од генератор на случаен број:

Различните вредности на H_1 испратени од првиот учесник водат до различен резултат H_0

Постојат најмалку два начини да се докаже исправноста Hi, ќе ги разгледаме откако ќе го анализираме генерирањето на полиномот.

Полиномна генерација

Во последниот дел претпоставивме дека имаме таков полином p (x) степени k-1 дека учесникот i знае p(i), и никој друг нема информации за оваа вредност. Во следниот дел ќе ни треба и тоа за некоја однапред одредена точка G сите знаеја p(x)G за сите x.

Во овој дел ќе претпоставиме дека секој учесник локално има некој приватен клуч xi, така што секој го знае соодветниот јавен клуч Xi.

Еден можен протокол за генерирање на полиноми е како што следува:

1. Секој учесник i локално создава произволен полином пи(х) степен k-1. Тие потоа го испраќаат секој учесник j вредност pi(j), шифрирана со јавен клуч Xj. Само така i-ти и j-ти учесникот знае pi(j). Учесник i исто така јавно објавува пи (ј) Г за сите j од 1 да k инклузивна.

2. Сите учесници користат одреден консензус за да изберат k учесници чии полиноми ќе се користат. Бидејќи некои учесници можеби се офлајн, не можеме да чекаме сите n учесниците ќе објавуваат полиноми. Резултатот од овој чекор е збир Z кој се состои од најмалку k полиноми создадени во чекор (1).

3. Учесниците се грижат за вредностите што ги знаат pi(j) одговара на јавно објавеното пи (ј) Г. По овој чекор во Z само полиноми за кои приватно се пренесуваат pi(j) одговара на јавно објавеното пи (ј) Г.

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

Имајте на ум дека p(x) - навистина е полином k-1, бидејќи тоа е збир на поединецот pi(x), од кои секој е полином со степен k-1. Потоа, забележете дека додека секој учесник j знае p(j), немаат информации за p (x) за x ≠ j. Навистина, за да се пресмета оваа вредност, тие треба да знаат сè пи (х), а се додека учесникот j не знае барем еден од избраните полиноми, нема доволно информации за p(x).

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

Поточно, ние треба да можеме да докажеме дека е шифрирана pi(j) навистина одговара на објавените пи (ј) Г. Ако не можеме да го докажеме, напаѓачот i наместо тоа може да испрати ѓубре pi(j) на учесникот j, и учесник j нема да може да го добие вистинското значење пи (j), и нема да може да ја пресмета нејзината приватна компонента.

Постои криптографски протокол кој ви овозможува да креирате дополнителна порака доказi(j), така што секој учесник има одредена вредност e, како и доказ (j) и pi(j)G, може локално да го потврди тоа e - навистина е пи (j), шифрирана со клучот на учесникот j. За жал, големината на таквите докази е неверојатно голема, а со оглед на тоа дека е неопходно да се објават O(nk) Таквите докази не можат да се користат за оваа цел.

Наместо тоа да се докаже пи (j) соответствует pi(j)G можеме да одвоиме многу голем временски период во протоколот за генерирање на полином, при што сите учесници го проверуваат применото шифрирана пи (j), а доколку дешифрираната порака не одговара на јавноста pi(j)G, тие објавуваат криптографски доказ дека шифрираната порака што ја примиле е неточна. Докажете дека пораката Нема соответствует пи (G) многу полесно отколку да се докаже дека се совпаѓа. Треба да се напомене дека ова бара од секој учесник да се појави на интернет барем еднаш во текот на времето определено за создавање на такви докази и се потпира на претпоставката дека доколку објават таков доказ, тој ќе стигне до сите други учесници во истото предвидено време.

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

Доказите за точноста на H_i

Последниот дел што останува да се дискутира е како да се докаже исправноста на објавеното Hјас, имено тоа Здраво = p(i)H, без отворање p(i).

Да се ​​потсетиме дека вредностите H, G, p(i)G јавна и позната на сите. Прими операција p(i) знаејќи p(i)G и G наречен дискретен логаритам, или длог, и сакаме да докажеме дека:

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

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

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

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

Истражувачкиот читател може да праша: бидејќи конечниот случаен број е H0, т.е p(0)G - Ова се информации од јавен карактер, зошто ни треба доказ за секој поединец Hјас, зошто да не испратам доказ дека наместо тоа

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

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

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

H0 G = p(0)G × H

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

Во заклучок

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

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

Можете да видите како изгледа развојот за NEAR и да експериментирате во онлајн IDE тука.

Можете да ги следите сите вести на руски на телеграма група и група на VKontakte, и на англиски јазик во службеното твитер.

Се гледаме наскоро!

Извор: www.habr.com