Оё имконпазир аст, ки рақамҳои тасодуфиро тавлид кунем, агар мо ба ҳамдигар эътимод накунем? Қисми 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) Г "Ҷузъи ҷамъиятӣ" i-иштирокчии дуюм (зеро ҳамаи иштирокчиён ӯро мешиносанд). Тавре ки шумо дар ёд доред, дониш p(i) Г барои барқарор кардан кофӣ нест p(i).

Эҷоди чунин полиномия, то ки танҳо i-Иштирокчии аввал ва ҳеҷ каси дигар ҷузъи хусусии худро намедонист - ин қисми мураккабтарин ва ҷолибтарини протокол аст ва мо онро дар зер таҳлил хоҳем кард. Ҳоло, биёед фарз кунем, ки мо чунин полином дорем ва ҳамаи иштирокчиён ҷузъҳои хусусии худро медонанд.

Чӣ тавр мо метавонем чунин полиномияро барои тавлиди адади тасодуфӣ истифода барем? Барои оғоз кардан, ба мо як сатр лозим аст, ки қаблан ҳамчун вуруд ба генератор истифода нашуда буд. Дар мавриди blockchain, хэши блоки охирин h номзади хубе ба чунин сатр аст. Бигзор иштирокчиён мехоҳанд бо истифода аз рақами тасодуфӣ эҷод кунанд h мисли тухм. Иштирокчиён аввал табдил меёбанд h ба нуқтаи каҷ бо истифода аз ягон функсияи пешакӣ муайяншуда:

H = scalarToPoint(h)

Сипас ҳар як иштирокчӣ i хисоб мекунад ва нашр мекунад Салом = p(i)H, чи кор карда метавонанд, зеро медонанд p(i) ва H. Ифшои Hман ба дигар иштирокчиён имкон намедиҳам, ки ҷузъи хусусиро барқарор кунанд iиштирокчии уми, ва аз ин рӯ, як маҷмӯи ҷузъҳои хусусиро метавон аз блок ба блок истифода бурд. Ҳамин тариқ, алгоритми тавлиди полиномии гаронбаҳои дар поён тавсифшуда танҳо як маротиба иҷро карда мешавад.

Ҳангоми k иштирокчиёнро тафтиш карданд Салом = 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 иштирокчиён барои як тухми ҳамеша ба як натиҷа меоянд.

Як мушкилие ҳаст, ки мо дар боло бодиққат аз он канорагирӣ кардем. Барои интерполясия кор кардан муҳим аст, ки арзиши 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, А также исбот (j) и pi(j)G, метавонад онро ба таври маҳаллӣ тафтиш кунад e - ин дар ҳақиқат pi(j), бо калиди иштирокчӣ рамзгузорӣ шудааст j. Мутаассифона, андозаи чунин далелҳо бениҳоят калон аст ва бо назардошти он, ки бояд интишор карда шавад. О(nk) Чунин далелҳоро барои ин мақсад истифода бурдан мумкин нест.

Ба ҷои он ки исбот кунад пи(ҷ) мувофиқат мекунад pi(j)G мо метавонем дар протоколи тавлиди полиномӣ як муддати хеле тӯлонӣ ҷудо кунем, ки дар давоми он ҳамаи иштирокчиён рамзгузории гирифташударо тафтиш мекунанд. pi(j), ва агар паёми рамзкушошуда ба омма мувофиқат накунад pi(j)G, онҳо далели криптографиро нашр мекунанд, ки паёми рамзгузоришудаи онҳо нодуруст аст. Исбот кунед, ки паём не мувофиқат мекунад пи(Г) хеле осонтар аз исбот кардани он мувофиқат мекунад. Бояд қайд кард, ки ин аз ҳар як иштирокчӣ талаб мекунад, ки ҳадди аққал як маротиба дар давоми вақти ҷудошуда барои эҷоди чунин далелҳо дар интернет ҳозир шавад ва ба фарзия такя мекунад, ки агар онҳо чунин далелро нашр кунанд, он ба ҳамаи иштирокчиёни дигар дар ҳамон вақти ҷудошуда мерасад.

Агар иштирокчӣ дар ин муддат дар интернет пайдо нашавад ва ӯ ақаллан як ҷузъи нодуруст дошта бошад, он иштирокчии мушаххас дар тавлиди рақамҳои минбаъда иштирок карда наметавонад. Аммо, протокол, агар ҳадди аққал вуҷуд дошта бошад, кор мекунад k иштирокчиёне, ки ё навакак ҷузъҳои дурустро гирифтаанд ё тавонистанд дар давоми вақти ҷудошуда далели нодурустиро тарк кунанд.

Далелхои дурустии H_i

Қисми охирине, ки бояд баррасӣ шавад, ин аст, ки чӣ гуна дурустии нашршуда исбот карда шавад Hман, яъне Салом = p(i)H, бе кушода p(i).

Биёед дар хотир дорем, ки арзишҳо H, G, p(i)G оммавй ва ба хама маълум аст. Амалиётро қабул кунед p(i) донистан p(i) Г и G логарифми дискретӣ номида мешавад, ё длог, ва мо мехоҳем исбот кунем:

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

бидуни ифшо p(i). Сохтмонҳо барои чунин далелҳо мавҷуданд, масалан Протоколи Schnorr.

Бо ин тарҳ, ҳар як иштирокчӣ, дар баробари Hi аз руи лоиха далели дурустии онро мефиристад.

Вақте ки рақами тасодуфӣ тавлид мешавад, онро аксар вақт ба иштирокчиёни ғайр аз онҳое, ки онро тавлид кардаанд, истифода бурдан лозим аст. Чунин иштирокчиён дар баробари рақам бояд ҳамаро фиристанд Hi ва далелҳои марбут.

Хонандаи пуртаҷриба метавонад пурсад: зеро рақами тасодуфии ниҳоӣ H0, ва p(0)G - Ин маълумоти оммавӣ аст, чаро мо барои ҳар як шахс далел лозим аст Hман, чаро ба ҷои он далели ирсол накунед

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 иштироккунандагони ин хабар имзо карданд. Ҳамин тариқ, агар тухмӣ - он хэши блок дар протоколи blockchain аст, пас H0 аст, ҳам бисёрсоҳавӣ имзо дар як блок ва рақами тасодуфӣ хеле хуб.

Дар охир

Ин мақола як қисми силсилаи блогҳои техникӣ мебошад НАВ. NEAR як протокол ва платформаи blockchain барои таҳияи барномаҳои ғайримарказонидашуда бо таваҷҷӯҳ ба осонии таҳия ва осонии истифода барои корбарони ниҳоӣ мебошад.

Рамзи протокол кушода аст, татбиқи мо дар Rust навишта шудааст, онро ёфтан мумкин аст дар ин ҷо.

Шумо метавонед бубинед, ки таҳияи NEAR чӣ гуна аст ва дар IDE онлайн озмоиш кунед дар ин ҷо.

Шумо метавонед ҳама хабарҳоро бо забони русӣ дар ин ҷо пайгирӣ кунед гурӯҳи телеграмма ва дар гурӯҳ дар ВКонтакте, ва ба забони англисӣ дар расмӣ twitter.

То боз дид!

Манбаъ: will.com