Възможно ли е да генерираме случайни числа, ако не си доверяваме един на друг? Част 2

Здравей, Хабр!

В първата част В статията обсъдихме защо може да бъде необходимо да се генерират случайни числа за участници, които не се доверяват един на друг, какви изисквания се поставят пред такива генератори на случайни числа и разгледахме два подхода за тяхната реализация.

В тази част на статията ще разгледаме по-подробно още един подход, който използва порогови подписи.

Малко криптография

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

За да разберете основите на пороговите подписи, не е необходимо да знаете как работят елиптичните криви, освен няколко основни неща:

1. Точките на елиптичната крива могат да се събират и умножават по скалар (умножението по скалар ще обозначаваме като xG, макар че notationen 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, че първият участник знае p(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 като seed. Първо участниците конвертират h в точка на кривата, използвайки всяка предварително определена функция:

H = scalarToPoint(h)

След това всеки участник i изчислява и публикува Hi = p(i)H, което те могат да направят, защото знаят p(i) и H. Разкритие Hi не позволява на останалите участници да възстановят приватната компонента i-ия участник, и следователно един набор от приватни компоненти може да се използва от блок на блок. По този начин, скъпият алгоритъм за създаване на полином, описан по-долу, трябва да се изпълнява само веднъж.

Когато k участниците разкриха Hi = 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 участници винаги ще достигне до същия резултат за един и същ seed.

Има един проблем, който внимателно избегнахме по-горе. За да работи интерполацията, е важно стойността Hi, публикувана от всеки участник i в действителност да е равна p(i)H. Тъй като никой освен i-ия участник не знае p(i), никой освен i--ия участник не може да провери, че Hi в действителност е било изчислено правилно, и без криптографско доказателство за правилността Hi, злонамерен участник може да публикува произволна стойност като Здравейте, и произволно да влияе на изхода на генератора на случайни числа:

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

Има най-малко два начина да се докаже правилността Hi, които ще разгледаме след като обсъдим генерацията на полином.

Генерация на полиноми

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

В тази част ще приемем, че всеки участник локално притежава някакъв частен ключ xi, така че на всички е известен съответстващият публичен ключ Xi.

Един възможен протокол за генериране на полиноми е следният:

1. Всеки участник i локално създава произволен полином pi(x) от степен k-1. След това те изпращат на всеки участник j стойността pi(j), криптиран с публичния ключ Xj. По този начин само i-ия и j-ия участник знае pi(j). Участникът i също публично обявява pi(j)G за всички. j от 1 до k включително.

2. Всички участници използват някакъв консенсус, за да изберат k участниците, чиито полиноми ще бъдат използвани. Тъй като някои участници могат да бъдат офлайн, не можем да чакаме всички n участници да публикуват полиномите. Резултатът от тази стъпка е множество Z състоящо се от поне k полиноми, създадени на стъпка (1).

3. Участниците се уверяват, че известните им стойности pi(j) съответстват на публично обявените pi(j)G. След тази стъпка трябва да останат само полиноми, за които частно предадените Z изчисляват своята частна компонента pi(j) съответстват на публично обявените pi(j)G.

4. Всеки участник j p(j) като сума i(j) за всички p. Всеки участник също изчислява всички стойности i в Zpi(x)G за всички i p(x)G i(j) за всички p(x) – в Z.

Обърнете внимание, че това наистина е полином от степен k-1, защото това е сума на отделните i(x), всеки от които е полином от степен pi(x), все от които – полиноми от степен k-1. Следва да обърнете внимание, че докато всеки участник j знае p(j), те нямат никаква информация за p(x) за x ≠ j. Наистина, за да изчислят тази стойност, трябва да знаят всички pi(x), и докато участникът j не знае поне един от избраните полиномии, нямат достатъчно информация за p(x).

Това е целият процес на генериране на полином, който беше необходим в предишната част. Стъпки 1, 2 и 4 по-горе имат достатъчно очевидно изпълнение. Но стъпка 3 не е толкова тривиална.

Конкретно, ние трябва да можем да доказваме, че криптираните pi(j) действително съответстват на публикуваните pi(j)G. Ако не можем да го докажем, злонамерен участник може да изпрати боклук вместо i i(j) на участника p, и участникът jняма да може да получи действителната стойност j pi(j), и няма да може да изчисли своята лична компонента. Има криптографски протокол, който позволява да се създаде допълнително съобщение.

proof i(j), така че всеки участник, притежаващ известно значениеe, както и proofi(j) i(j)G, може локално да се увери, че и p– това действително е e криптирано с ключа на участника и няма да може да изчисли своята лична компонента. j. За съжаление, размерът на такова доказателство е невероятно голям, и като се има предвид, че е необходимо да се публикуват O(nk) такива доказателства, не може да се използват за тази цел. Вместо да доказваме, че

pi(j) i(j)G, можем в протокола за генериране на полином да отведем много голям интервал от време, в който всички участници проверяват получените криптирани отговаря на pи ако декриптираното съобщение не съответства на публичния и няма да може да изчисли своята лична компонента. i(j)G, те публикуват криптографско доказателство, че полученото от тях криптирано съобщение е невярно. По-лесно е да се докаже, че съобщението ppi(G) не отговаря на отколкото да се докаже, че съответства. Следва да се отбележи, че това изисква всеки участник да се появи в мрежата поне веднъж в периода, отведен за създаването на такива доказателства, и се основава на предположението, че ако те са публикували такова доказателство, то ще достигне до всички останали участници в този същия отведен време. Ако участникът не се е появил в мрежата по време на този период, и той наистина е имал поне една некоректна компонента, то този конкретен участник няма да може да участва в по-нататъшната генерация на числа. Протоколът, обаче, все още ще функционира, ако има поне

Ако участникът не се е появявал в мрежата през този период от време и действително е имал поне един некоректен компонент, то този конкретен участник няма да може да участва в по-нататъшната генерация на числа. Протоколът, обаче, ще продължи да функционира, ако има поне k участници, които или току-що получиха коректни компоненти, или успяха да оставят доказателство за некоректност в отведеното време.

Доказателства за коректността H_i

Последната част, която остава да обсъдим, е как да докажем коректността на публикуваните Hi, а именно че Hi = p(i)H, без разкриване p(i).

Да си припомним, че стойностите H, G, p(i)G са публични и известни на всички. Операцията на получаване p(i) знаейки p(i)G и G се нарича дискретен логаритъм, или dlog, и ние искаме да докажем, че:

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

без разкриване p(i). Конструкции за такива доказателства съществуват, например Schnorr Protocol.

С такава конструкция, всеки участник заедно с Hi изпраща доказателство за коректност съгласно конструкцията.

Когато случайното число е генерирано, често трябва да бъде използвано от участници, различни от тези, които са го генерирали. На тези участници заедно със числото е необходимо да се изпратят всички Hi и свързани доказателства.

Любопитният читател може да попита: тъй като финалното случайно число е H0, и p(0)G – това е публична информация, защо е нужно доказателство за всяко отделно Hi, защо вместо това не изпратим доказателство, че

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

Проблемът е, че с помощта на Schnorr Protocol не може да се създаде такова доказателство, тъй като никой не знае стойността на p(0), необходима за създаването на доказателството, и повече от това, целият генератор на случайни числа се основава на факта, че никой не знае тази стойност. Затова е необходимо да имате всички стойности Hi и техните индивидуални доказателства, за да докажете коректността. H0.

Въпреки това, ако на точките на еллиптичните криви имаше операция, която семантически е сходна с умножение, доказателството за коректността H0 беще тривиално, просто щяхме да се уверим, че

H0 × G = p(0)G × H

Ако избраната крива поддържа elliptic curve pairings, такова доказателство работи. В този случай H0 – това е не само изходът от генератора на случайни числа, който може да провери всеки участник, който знае G, H и p(0)G. H0 – това също е подпис на съобщение, което е било използвано като seed, потвърдително, че k и n участниците са подписали това съобщение. Така че, ако seed – това е хеш блок в протокола на блокчейна, тогава H0 – това е едновременно много-подпис на блока и много добро случайно число.

В заключение

Тази статия е част от серия технически статии в блога. NEAR. NEAR е блокчейн протокол и платформа за разработка на децентрализирани приложения с акцент върху простотата на разработката и леснотата на използване за крайните потребители.

Кодът на протокола е открит, нашата реализация е написана на Rust и може да бъде намерена тук.

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

Следете всички новини на руски език в групата в Telegram и в групата във ВКонтакте, а на английски в официалния Twitter.

До скоро!

Източник: habr.com