Ці можна генераваць выпадковыя лікі, калі мы не давяраем адзін аднаму? Частка 2

Прывітанне, Хабр!

В першай частцы артыкулы мы абмеркавалі, навошта можа быць неабходна генераваць выпадковыя лікі ўдзельнікам, якія не давяраюць адзін аднаму, якія патрабаванні высоўваюцца да такіх генератараў выпадковых лікаў, і разгледзелі два падыходу да іх рэалізацыі.

У гэтай частцы артыкула мы падрабязна разгледзім яшчэ адзін падыход, які выкарыстоўвае парогавыя подпісы.

Трохі крыптаграфіі

Для таго, каб зразумець, як працуюць парогавыя подпісы, трэба разумець крыху базавай крыптаграфіі. Мы будзем выкарыстоўваць дзве канцэпцыі: скаляры, ці проста лікі, якія мы будзем пазначаць малымі літарамі (х, у) і кропкі на эліптычнай крывой, якія мы будзем абазначаць вялікімі літарамі.

Для разумення асноў парогавых подпісаў не трэба разумець, як працуюць эліптычныя крывыя, акрамя некалькіх базавых рэчаў:

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 як 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. Нажаль, памер такога доказу неверагодна вялікі, і улічваючы што неабходна апублікаваць О(нк) такіх доказаў, выкарыстоўваць іх для гэтай мэты не атрымаецца.

Замест таго, каб даказваць, што 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 нельга стварыць такі доказ, таму што ніхто не ведае значэнне р (0), неабходнае для стварэння доказы, і больш за тое, увесь генератар выпадковых лікаў заснаваны на тым, што ніхто не ведае гэта значэнне. Таму неабходна мець усе значэнні Hi і іх індывідуальныя доказы, каб даказаць карэктнасць H0.

Аднак, калі б на кропках на эліптычных крывых была б нейкая аперацыя, якая семантычна падобная з множаннем, доказ карэктнасці H0 было б трывіяльным, мы б проста пераканаліся, што

H0 × G = p(0)G × H

Калі абраная крывая падтрымлівае elliptic curve pairings, такі доказ працуе. У гэтым выпадку H0 - гэта не толькі выснова генератара выпадковых лікаў, які можа праверыць любы ўдзельнік, які ведае Г, Х и p(0)G. H0 – гэта яшчэ і подпіс на паведамленьні, якое выкарыстоўвалася як seed, якое пацьвярджае, што k и n удзельнікаў падпісалі гэтае паведамленне. Такім чынам, калі seed - гэта хэш блока ў пратаколе блокчейна, то H0 - гэта адначасова мульты-подпіс на блоку, і вельмі добры выпадковы лік.

У заключэнне

Гэты артыкул - частка серыі тэхнічных артыкулаў у блогу БЛЯЗЕ. NEAR - гэта блокчейн пратакол і платформа для распрацоўкі дэцэнтралізаваных прыкладанняў з акцэнтам на прастату распрацоўкі, і прастату выкарыстання для канчатковых карыстальнікаў.

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

Паглядзець як выглядае распрацоўка пад NEAR, і паэксперыментаваць у анлайн-IDE можна тут.

Сачыць за ўсімі навінамі на рускай можна ў групе ў тэлеграме і ў групе на Укантакце, а на англійскай у афіцыйным твітэры.

Да хуткіх сустрэч!

Крыніца: habr.com