Възможно ли е да генерираме произволни числа, ако нямаме доверие един на друг? Част 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 = scalarToPoint(h)

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

Когато k участниците бяха аутопсирани Hi = p(i)H, всеки може да изчисли Hх = p(x)H за всички x благодарение на свойството на полиномите, което обсъдихме в последния раздел. В този момент всички участници изчисляват H0 = p(0)H, и това е полученото произволно число. Моля, имайте предвид, че никой не знае p(0), и следователно единственият начин за изчисляване p(0)H – това е интерполация p(x)H, което е възможно само когато k стойности p(i)H известен. Отваряне на всяко по-малко количество p(i)H не предоставя никаква информация за р(0)Н.

Генераторът по-горе има всички свойства, които искаме: нападателите контролират само 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 локално създава произволен полином 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) като сума pi(j) за всички i в Z. Всеки участник също изчислява всички стойности p(x)G като сума pi(x)G за всички i в Z.

Моля, имайте предвид, че p(x) – това наистина е полином к-1, защото е сборът от индивида 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 вместо това може да изпрати боклук pi(j) към участник j, и участник j няма да може да получи истинското значение pi(j), и няма да може да изчисли неговия частен компонент.

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

Вместо да докаже това пи(j) соответствует pi(j)G можем да разпределим много голям период от време в протокола за генериране на полином, през който всички участници проверяват получените криптирани pi(j), и ако дешифрираното съобщение не отговаря на обществеността pi(j)G, те публикуват криптографско доказателство, че криптираното съобщение, което са получили, е неправилно. Докажете, че съобщението не соответствует пи (G) много по-лесно, отколкото да докажеш, че съвпада. Трябва да се отбележи, че това изисква всеки участник да се появи онлайн поне веднъж през времето, определено за създаване на такова доказателство, и разчита на предположението, че ако публикува такова доказателство, то ще достигне до всички останали участници за същото определено време.

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

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

Последната част, която остава да бъде обсъдена, е как да се докаже верността на публикуваното Hаз, а именно това 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). Съществуват например конструкции за такива доказателства Протокол Шнор.

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

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

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

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

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

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

H0 × G = p(0)G × H

Ако избраната крива поддържа сдвояване на елиптични криви, това доказателство работи. В такъв случай H0 не е само резултат от генератор на произволни числа, което може да се провери от всеки участник, който знае Г, Х и p(0)G. з0 също е подпис върху съобщението, което е използвано като семе, потвърждавайки това k и n участници подписаха това съобщение. По този начин, ако семе – тогава е хешът на блока в протокола на блокчейн H0 е както мултиподпис върху блок, така и много добро произволно число.

В заключение

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

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

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

Можете да следите всички новини на руски език на телеграм група и група във VKontakte, а на английски в официалния кикотене.

Ще се видим скоро!

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