Чи можна генерувати випадкові числа, якщо ми не довіряємо одне одному? Частина 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, що перший учасник знає 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, усі можуть обчислити Hх = 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) як суму 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. Справді, щоб обчислити це значення, їм потрібно знати все 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) таких доказів використовувати їх для цієї мети не вийде.

Замість того, щоб доводити, що pi(j) відповідає pi(j)G ми можемо у протоколі генерації полінома відвести дуже великий проміжок часу, під час якого всі учасники перевіряють отримані зашифровані pi(j), і якщо розшифроване повідомлення не відповідає публічному pi(j)G, вони публікують криптографічне доказ того, що отримане ними зашифроване повідомлення неправильне. Довести, що повідомлення НЕ відповідає pi(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

Якщо вибрана крива підтримує поєднання еліптичних кривих, такий доказ працює. В цьому випадку H0 – це не лише висновок генератора випадкових чисел, який може перевірити будь-який учасник, який знає Г, Х и p(0)G. H0 – це ще й підпис на повідомленні, яке використовувалося як seed, що підтверджує, що k и n учасників підписали це повідомлення. Таким чином, якщо seed – це хеш блоку в протоколі блокчейну, то H0 – це одночасно мульти-підпис на блоці, і дуже гарне довільне число.

На закінчення

Ця стаття – частина серії технічних статей у блозі БЛИЗЬКО. NEAR – це блокчейн протокол та платформа для розробки децентралізованих додатків з акцентом на простоту розробки та простоту використання для кінцевих користувачів.

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

Подивитися як виглядає розробка під NEAR, та поекспериментувати в онлайн-IDE можна тут.

Стежити за всіма новинами російською можна в групі у телеграмі і в групі на ВКонтакті, а англійською в офіційному твіттері.

До зустрічі!

Джерело: habr.com