Bir-birimizə güvənməsək, təsadüfi ədədlər yaratmaq mümkündürmü? 2-ci hissə

Hey Habr!

В birinci hissəsində Bu yazıda bir-birinə etibar etməyən iştirakçılar üçün təsadüfi ədədlərin yaradılmasının nə üçün lazım ola biləcəyini, belə təsadüfi ədəd generatorları üçün hansı tələblərin irəli sürüldüyünü müzakirə etdik və onların həyata keçirilməsinə iki yanaşma nəzərdən keçirdik.

Məqalənin bu hissəsində hədd imzalarından istifadə edən başqa bir yanaşmaya daha yaxından nəzər salacağıq.

Bir az kriptoqrafiya

Eşik imzalarının necə işlədiyini başa düşmək üçün bir az əsas kriptoqrafiyanı başa düşməlisiniz. Biz iki anlayışdan istifadə edəcəyik: skalerlər və ya kiçik hərflərlə işarə edəcəyimiz sadəcə ədədlər (x, y) və böyük hərflərlə işarələyəcəyimiz elliptik əyri üzərindəki nöqtələr.

Eşik imzalarının əsaslarını başa düşmək üçün bir neçə əsas şeydən başqa, elliptik əyrilərin necə işlədiyini başa düşməyə ehtiyac yoxdur:

1. Elliptik əyri üzərindəki nöqtələr əlavə oluna və skalara vurula bilər (biz skaler ilə vurmağı belə ifadə edəcəyik) xG, qeyd olmasına baxmayaraq Gx ədəbiyyatda da tez-tez istifadə olunur). Skayarla toplama və vurmanın nəticəsi elliptik əyri üzərindəki nöqtədir.

2. Yalnız məqamı bilmək G və onun skalyar ilə məhsulu xG hesablamaq mümkün deyil x.

Çoxhədli anlayışından da istifadə edəcəyik p (x) dərəcə k-1. Xüsusilə, çoxhədlilərin aşağıdakı xassəsindən istifadə edəcəyik: dəyərini bilsək p (x) hər hansı üçün k müxtəlif x (və bu barədə əlavə məlumatımız yoxdur p (x)), hesablaya bilərik p (x) başqası üçün x.

Maraqlıdır ki, istənilən polinom üçün p (x) və əyrinin bəzi nöqtəsi Gmənasını bilmək p(x)G hər hansı üçün k müxtəlif mənalar x, biz də hesablaya bilərik p(x)G hər hansı üçün x.

Bu, həddi imzaların necə işlədiyini və təsadüfi ədədlər yaratmaq üçün onlardan necə istifadə ediləcəyinin təfərrüatlarını öyrənmək üçün kifayət qədər məlumatdır.

Eşik imzalarında təsadüfi nömrə generatoru

Belə deyək n iştirakçılar təsadüfi nömrə yaratmaq istəyirlər və biz hər kəsin iştirakını istəyirik k Onları idarə edən təcavüzkarlar bir sıra yaratmaq üçün kifayət qədər idi, ancaq k-1 və ya daha az iştirakçı yaradılan rəqəmi proqnozlaşdıra və ya təsir edə bilmədi.

Tutaq ki, belə bir polinom var p (x) dərəcə k-1 birinci iştirakçının bildiyi şey p (1), ikincisi bilir p(2), və s (n-bilir p(n)). Bunu əvvəlcədən müəyyən edilmiş bir nöqtə üçün də güman edirik G hər kəs bilir p(x)G bütün dəyərlər üçün x. Zəng edəcəyik p(i) "özəl komponent" iinci iştirakçı (çünki yalnız ici iştirakçı onu tanıyır) və p(i)G "ictimai komponent" i--ci iştirakçı (çünki bütün iştirakçılar onu tanıyır). Yadınızdadırsa, bilik p(i)G bərpa etmək üçün kifayət deyil p(i).

Belə bir çoxhədli yaratmaq yalnız i-Birinci iştirakçı və başqa heç kim onun şəxsi komponentini bilmirdi - bu protokolun ən mürəkkəb və maraqlı hissəsidir və biz onu aşağıda təhlil edəcəyik. Hələlik, fərz edək ki, belə bir polinomumuz var və bütün iştirakçılar öz şəxsi komponentlərini bilirlər.

Təsadüfi bir ədəd yaratmaq üçün belə bir polinomdan necə istifadə edə bilərik? Başlamaq üçün bizə əvvəllər generatora giriş kimi istifadə edilməmiş bir sıra lazımdır. Blockchain vəziyyətində, sonuncu blokun hashı h belə bir xətt üçün yaxşı namizəddir. İştirakçılardan istifadə edərək təsadüfi bir nömrə yaratmağa icazə verin h toxum kimi. İştirakçılar əvvəlcə çevrilir h hər hansı əvvəlcədən təyin edilmiş funksiyadan istifadə edərək əyrinin bir nöqtəsinə:

H = skalerToPoint(h)

Sonra hər bir iştirakçı i hesablayır və dərc edir Salam = p(i)H, bildikləri üçün nə edə bilərlər p(i) və H. Açıqlama Hdigər iştirakçılara şəxsi komponenti bərpa etməyə icazə vermirəm ici iştirakçıdır və buna görə də bir blokdan bloka özəl komponentlər dəsti istifadə edilə bilər. Beləliklə, aşağıda təsvir olunan bahalı çoxhədli generasiya alqoritmini yalnız bir dəfə yerinə yetirmək lazımdır.

Zaman k iştirakçılar yarıldı Salam = p(i)H, hər kəs hesablaya bilər Hx = p(x)H hamı üçün x son bölmədə müzakirə etdiyimiz çoxhədlilərin xüsusiyyəti sayəsində. Bu anda bütün iştirakçılar hesablayırlar H0 = p(0)H, və bu təsadüfi rəqəmdir. Nəzərə alın ki, heç kim bilmir p(0), və buna görə də hesablamağın yeganə yolu p(0)H - bu interpolyasiyadır p(x)H, bu yalnız zaman mümkündür k dəyərlər p(i)H məlumdur. İstənilən kiçik miqdarların açılması p(i)H haqqında heç bir məlumat vermir p(0)H.

Yuxarıdakı generator istədiyimiz bütün xüsusiyyətlərə malikdir: yalnız nəzarət edən təcavüzkarlar k-1 və ya daha az iştirakçının nəticəyə heç bir məlumatı və ya təsiri yoxdur k iştirakçılar nəticədə sayı hesablaya bilər, və hər hansı bir alt k iştirakçılar həmişə eyni toxum üçün eyni nəticəyə gələcəklər.

Yuxarıda diqqətlə qaçdığımız bir problem var. İnterpolasiyanın işləməsi üçün dəyərin olması vacibdir Hi hər bir iştirakçı tərəfindən dərc edilmişdir i həqiqətən də eyni idi p(i)H. Çünki başqa heç kim i-ci iştirakçı bilmir p(i), başqa heç kim i-ci iştirakçı bunu təsdiq edə bilməz Hi həqiqətən düzgün hesablanmış və heç bir kriptoqrafik düzgünlüyün sübutu olmadan HMən təcavüzkar istənilən dəyəri dərc edə bilər Salam, və təsadüfi ədədlər generatorunun çıxışına özbaşına təsir edir:

Birinci iştirakçı tərəfindən göndərilən H_1-in fərqli dəyərləri fərqli nəticələnən H_0-a səbəb olur

Düzgünlüyünü sübut etməyin ən azı iki yolu var Hi, çoxhədlinin nəslini təhlil etdikdən sonra onları nəzərdən keçirəcəyik.

Polinom nəsil

Son hissədə belə bir çoxhədlinin olduğunu fərz etdik p (x) dərəcə k-1 iştirakçı i bilir p(i), və başqa heç kimin bu dəyər haqqında məlumatı yoxdur. Növbəti hissədə əvvəlcədən müəyyən edilmiş bir nöqtə üçün də buna ehtiyacımız olacaq G hamı bilirdi p(x)G hamı üçün x.

Bu bölmədə hər bir iştirakçının yerli olaraq bəzi şəxsi açarı olduğunu güman edəcəyik xi, belə ki, hər kəs müvafiq açıq açarı bilir Xi.

Mümkün polinom generasiya protokolu aşağıdakı kimidir:

1. Hər bir iştirakçı i lokal olaraq ixtiyari çoxhədli yaradır pi(x) dərəcə k-1. Sonra hər bir iştirakçını göndərirlər j dəyər pi(j), açıq açarla şifrələnmişdir Xj. Yalnız beləliklə i-th и j-th iştirakçı bilir pi(j). İştirakçı i da ictimaiyyətə elan edir pi(j)G hamı üçün j etibarən 1 üzrə k daxildir.

2. Bütün iştirakçılar seçim etmək üçün müəyyən konsensusdan istifadə edirlər k polinomları istifadə olunacaq iştirakçılar. Bəzi iştirakçılar oflayn ola bildiyi üçün hamıya qədər gözləyə bilmərik n iştirakçılar polinomları dərc edəcəklər. Bu addımın nəticəsi bir dəstdir Z ən azı ibarətdir k (1) addımında yaradılmış polinomlar.

3. İştirakçılar bildikləri dəyərlərə əmin olurlar pi(j) ictimaiyyətə açıqlananlara uyğun gəlir pi(j)G. Bu addımdan sonra Z yalnız özəl olaraq ötürülən polinomlar pi(j) ictimaiyyətə açıqlananlara uyğun gəlir pi(j)G.

4. Hər bir iştirakçı j onun özəl komponentini hesablayır p(j) cəmi kimi pi(j) hamı üçün i в Z. Hər bir iştirakçı bütün dəyərləri hesablayır p(x)G cəmi kimi hamı üçün pi(x)G i в Z.

Qeyd edin ki, p(x) – həqiqətən çoxhədlidir k-1, çünki fərdin cəmidir pi(x), hər biri dərəcə çoxhədlidir k-1. Sonra, hər bir iştirakçı zamanı qeyd edin j bilir p(j), haqqında heç bir məlumatı yoxdur p (x) uğrunda x ≠ j. Həqiqətən, bu dəyəri hesablamaq üçün hər şeyi bilməlidirlər pi(x), və iştirakçı olduğu müddətcə j seçilmiş çoxhədlilərdən heç olmasa birini bilmir, onlar haqqında kifayət qədər məlumat yoxdur p(x).

Bu, son bölmədə lazım olan bütün çoxhədli generasiya prosesidir. Yuxarıdakı 1, 2 və 4-cü addımlar kifayət qədər aydın icraya malikdir. Ancaq 3-cü addım o qədər də əhəmiyyətsiz deyil.

Konkret olaraq, şifrəli olduğunu sübut etməyi bacarmalıyıq pi(j) həqiqətən nəşr olunanlara uyğundur pi(j)G. Sübut edə bilməsək, hücum edən i əvəzinə zibil göndərə bilər pi(j) iştirakçıya j, və iştirakçı j real dəyəri əldə edə bilməyəcək pi(j), və onun şəxsi komponentini hesablaya bilməyəcək.

Əlavə mesaj yaratmağa imkan verən kriptoqrafik protokol var sübuti(j), elə ki, hər hansı bir iştirakçı müəyyən dəyərə malik olsun e, həmçinin sübut(j) и pi(j)G, bunu yerli olaraq yoxlaya bilər e - həqiqətən də pi(j), iştirakçının açarı ilə şifrələnir j. Təəssüf ki, bu cür sübutların ölçüsü inanılmaz dərəcədə böyükdür və dərc etmək lazım olduğunu nəzərə alsaq O(nk) Belə dəlillərdən bu məqsədlə istifadə edilə bilməz.

Bunu sübut etmək əvəzinə pi(j) uyğun gəlir pi(j)G polinom generasiya protokolunda çox uzun müddət ayıra bilərik, bu müddət ərzində bütün iştirakçılar qəbul edilmiş şifrələnmiş məlumatları yoxlayırlar. pi(j), və şifrəsi açılmış mesaj ictimaiyyətə uyğun gəlmirsə pi(j)G, onlar aldıqları şifrələnmiş mesajın səhv olduğuna dair kriptoqrafik sübut dərc edirlər. Mesaj olduğunu sübut edin heç bir uyğun gəlir pi(G) uyğun olduğunu sübut etməkdən daha asandır. Qeyd etmək lazımdır ki, bu, hər bir iştirakçının belə sübut yaratmaq üçün ayrılmış vaxt ərzində ən azı bir dəfə internetdə görünməsini tələb edir və belə bir sübutu dərc etsələr, bu, eyni ayrılmış vaxtda bütün digər iştirakçılara çatacağı ehtimalına əsaslanır.

Əgər iştirakçı bu müddət ərzində onlayn görünməyibsə və onun ən azı bir səhv komponenti varsa, o zaman həmin iştirakçı növbəti nömrələrin yaradılmasında iştirak edə bilməyəcək. Bununla belə, heç olmasa protokol varsa, hələ də işləyəcək k ya yenicə düzgün komponentləri alan, ya da ayrılmış vaxt ərzində yanlışlıq sübutunu tərk etməyi bacaran iştirakçılar.

H_i-nin düzgünlüyünün sübutları

Müzakirə edilməli olan son hissə nəşrin düzgünlüyünü necə sübut etməkdir Hmən, yəni Salam = p(i)H, açmadan p(i).

Unutmayaq ki, dəyərlər H, G, p(i)G ictimai və hamıya məlumdur. Qəbul əməliyyatı p(i) bilmək p(i)G и G diskret loqarifm adlanır və ya dlog, və biz bunu sübut etmək istəyirik:

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

açıqlamadan p(i). Məsələn, belə sübutlar üçün konstruksiyalar mövcuddur Schnorr Protokolu.

Bu dizaynla hər bir iştirakçı ilə birlikdə Hi dizayna uyğun olaraq düzgünlüyünün sübutunu göndərir.

Təsadüfi bir nömrə yaradıldıqdan sonra, onu yaradanlardan başqa iştirakçılar tərəfindən istifadə edilməlidir. Belə iştirakçılar nömrə ilə birlikdə hamısını göndərməlidir Hi və əlaqəli sübutlar.

Maraqlı oxucu soruşa bilər: çünki son təsadüfi nömrədir H0, və p(0)G - Bu ictimai məlumatdır, niyə hər bir fərd üçün sübut lazımdır Hi, niyə bunun əvəzinə sübut göndərmirəm

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

Problem ondadır ki, Schnorr Protokolundan istifadə edərək belə bir sübut yaradıla bilməz, çünki heç kim dəyəri bilmir p (0), sübut yaratmaq üçün lazımdır və daha çox, bütün təsadüfi ədəd generatoru heç kimin bu dəyəri bilməməsinə əsaslanır. Ona görə də bütün dəyərlərə sahib olmaq lazımdır Hi və düzgünlüyünü sübut etmək üçün onların fərdi sübutları H0.

Bununla belə, elliptik əyrilər üzərində semantik olaraq vurmağa oxşar olan bəzi əməliyyatlar olsaydı, düzgünlüyün sübutu H0 əhəmiyyətsiz olardı, sadəcə olaraq buna əmin olardıq

H0 × G = p(0)G × H

Seçilmiş əyri dəstəkləyirsə elliptik əyri cütləşmələr, bu sübut işləyir. Bu halda H0 yalnız təsadüfi ədəd generatorunun çıxışı deyil, onu bilən hər hansı bir iştirakçı yoxlaya bilər G, H и p(0)G. H0 həm də toxum kimi istifadə edilən mesajda bunu təsdiqləyən imzadır k и n iştirakçılar bu mesajı imzaladılar. Beləliklə, əgər toxum - o zaman blokçeyn protokolunda blokun hashıdır H0 həm blokda çox imza, həm də çox yaxşı təsadüfi nömrədir.

Nəticədə

Bu məqalə texniki bloq seriyasının bir hissəsidir NEAR. NEAR, inkişaf asanlığına və son istifadəçilər üçün istifadənin asanlığına diqqət yetirməklə, mərkəzləşdirilməmiş tətbiqləri inkişaf etdirmək üçün blokçeyn protokolu və platformadır.

Protokol kodu açıqdır, tətbiqimiz Rustda yazılıb, onu tapmaq olar burada.

Onlayn IDE-də NEAR üçün inkişafın necə göründüyünü və sınaqdan keçirə bilərsiniz burada.

Bütün xəbərləri rus dilində izləyə bilərsiniz telegram qrupu və VKontakte-də qrup, və rəsmi olaraq ingilis dilində twitter.

Tezliklə görüşərik!

Mənbə: www.habr.com