Бір-бірімізге сенбесек, кездейсоқ сандарды шығаруға болады ма? 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 тұқым сияқты. Қатысушылар алдымен түрленеді h кез келген алдын ала анықталған функцияны пайдаланып қисықтағы нүктеге:

H = скалярлық нүкте(сағ)

Содан кейін әрбір қатысушы i есептеп шығарады және жариялайды Hi = p(i)H, олар не істей алады, өйткені олар біледі p(i) және H. Ақпаратты ашу Hбасқа қатысушыларға жеке құрамдас бөлікті қалпына келтіруге рұқсат бермеймін ith қатысушы, сондықтан жеке құрамдастардың бір жинағын блоктан блокқа дейін пайдалануға болады. Осылайша, төменде сипатталған қымбат полиномды генерациялау алгоритмі тек бір рет орындалуы керек.

Қашан 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 қатысушылар бір тұқым үшін әрқашан бірдей нәтижеге келеді.

Жоғарыда біз мұқият аулақ болған бір мәселе бар. Интерполяция жұмыс істеуі үшін мәннің болуы маңызды 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 сома ретінде барлық i үшін pi(x)G в 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, сонымен қатар дәлелдеу(j) и pi(j)G, мұны жергілікті түрде тексере алады e - бұл шынымен pi(j), қатысушының кілтімен шифрланған j. Өкінішке орай, мұндай дәлелдемелердің көлемі өте үлкен және оны жариялау қажет екенін ескере отырып, О(nk) Мұндай дәлелдемелерді бұл мақсатта пайдалану мүмкін емес.

Мұны дәлелдеудің орнына pi(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). Мысалы, мұндай дәлелдер үшін конструкциялар бар Schnorr протоколы.

Осы дизайнмен бірге әрбір қатысушы Hi жобаға сәйкес дұрыстығын дәлелдеуді жібереді.

Кездейсоқ сан жасалғаннан кейін оны жасағандардан басқа қатысушылар жиі пайдалануы керек. Мұндай қатысушылар нөмірмен бірге барлығын жіберуі керек Hi және соған байланысты дәлелдемелер.

Ізденімпаз оқырман сұрауы мүмкін: соңғы кездейсоқ сан болғандықтан H0, және p(0)G – Бұл жалпыға ортақ ақпарат, неге бізге әр адамға дәлел керек Hi, неге оның орнына дәлелді жібермеске?

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

Мәселе мынада, мұндай дәлелді Schnorr протоколы арқылы жасау мүмкін емес, себебі ешкім мәнді білмейді p (0), дәлелдеуді жасау үшін қажет және одан да көп кездейсоқ сандар генераторы бұл мәнді ешкім білмейтініне негізделген. Сондықтан барлық құндылықтарға ие болу керек Hi және олардың дұрыстығын дәлелдейтін жеке дәлелдемелер H0.

Алайда, эллиптикалық қисықтардың нүктелерімен мағыналық жағынан көбейтуге ұқсас кейбір амалдар болса, дұрыстығын дәлелдеу. H0 тривиальды болар еді, біз бұған көз жеткізер едік

H0 × G = p(0)G × H

Таңдалған қисық қолдаса эллиптикалық қисық жұптар, бұл дәлел жұмыс істейді. Бұл жағдайда H0 кездейсоқ сандар генераторының шығысы ғана емес, оны білетін кез келген қатысушы тексере алады Г, Х и p(0)G. Х0 - бұл тұқым ретінде пайдаланылған хабарламадағы қолтаңба, мұны растайды k и n қатысушылар осы хабарламаға қол қойды. Осылайша, егер тұқым – блокчейн протоколындағы блоктың хэші болып табылады, содан кейін H0 блоктағы көп қолтаңба және өте жақсы кездейсоқ сан болып табылады.

Қорытындылай келе

Бұл мақала техникалық блогтар сериясының бөлігі болып табылады NEAR. NEAR - бұл блокчейн протоколы және орталықтандырылмаған қосымшаларды әзірлеуге арналған платформа және әзірлеудің қарапайымдылығына және түпкі пайдаланушылар үшін пайдаланудың қарапайымдылығына баса назар аударады.

Протокол коды ашық, біздің іске асыру Rust тілінде жазылған, оны табуға болады осында.

NEAR үшін әзірлеменің қандай болатынын көруге және онлайн IDE-де тәжірибе жасауға болады осында.

Барлық жаңалықтарды орыс тілінде бақылай аласыздар телеграм тобы мен ВКонтакте желісіндегі топ, ал ағылшын тілінде ресми түрде twitter.

Көріскенше!

Ақпарат көзі: www.habr.com