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

Hey Habr!

Bu yazıda mən bir-birinə güvənməyən iştirakçılar tərəfindən psevdo-təsadüfi nömrələr yaratmasından danışacağam. Aşağıda görəcəyimiz kimi, "demək olar ki," yaxşı bir generatoru həyata keçirmək olduqca sadədir, lakin çox yaxşı bir generator çətindir.

Bir-birinə güvənməyən iştirakçılar arasında təsadüfi nömrələr yaratmaq nəyə lazımdır? Bir tətbiq sahəsi mərkəzləşdirilməmiş tətbiqlərdir. Məsələn, iştirakçıdan mərc qəbul edən və ya 49% ehtimalla məbləği ikiqat artıran, ya da 51% ehtimalla götürən proqram yalnız qərəzsiz təsadüfi nömrə ala bildiyi halda işləyəcək. Təcavüzkar təsadüfi ədədlər generatorunun nəticələrinə təsir edə bilsə və hətta tətbiqdə ödəniş almaq şansını bir qədər artırsa, onu asanlıqla məhv edəcək.

Paylanmış təsadüfi ədədlər yaratmaq protokolunu tərtib edərkən, onun üç xüsusiyyətə sahib olmasını istəyirik:

1. O, qərəzsiz olmalıdır. Başqa sözlə, heç bir iştirakçı təsadüfi ədədlər generatorunun nəticəsinə heç bir şəkildə təsir etməməlidir.

2. O, gözlənilməz olmalıdır. Başqa sözlə, heç bir iştirakçı hansı nömrənin yaradılacağını (və ya onun xassələrindən hər hansı birinin nəticə çıxaracağını) onun yaradılmadan əvvəl proqnozlaşdıra bilməməlidir.

3. Protokol canlı olmalıdır, yəni iştirakçıların müəyyən faizinin şəbəkədən ayrılmasına və ya qəsdən protokolu dayandırmağa cəhd etməsinə davamlı olmalıdır.

Bu yazıda iki yanaşmaya baxacağıq: RANDAO + VDF və silmə kodları yanaşması. Növbəti hissədə hədd imzalarına əsaslanan yanaşmanı ətraflı nəzərdən keçirəcəyik.

Ancaq əvvəlcə həyat qabiliyyətli, gözlənilməz, lakin qərəzli olan sadə və çox istifadə olunan alqoritmə baxaq.

RANDAO

RANDAO çox sadə və buna görə də təsadüfilik yaratmaq üçün çox istifadə olunan bir yanaşmadır. Bütün şəbəkə iştirakçıları əvvəlcə yerli olaraq psevdor-təsadüfi nömrə seçirlər, sonra hər bir iştirakçı seçilmiş nömrənin hashini göndərir. Sonra iştirakçılar növbə ilə seçdikləri nömrələri açır və aşkar edilmiş nömrələr üzərində XOR əməliyyatı həyata keçirirlər və bu əməliyyatın nəticəsi protokolun nəticəsi olur.

Rəqəmləri aşkar etməzdən əvvəl hashlərin dərc edilməsi addımı lazımdır ki, təcavüzkar digər iştirakçıların nömrələrini gördükdən sonra öz nömrəsini seçə bilməsin. Bu, ona təsadüfi ədədlər generatorunun çıxışını faktiki olaraq təkbaşına müəyyən etməyə imkan verəcəkdi.

Protokolun gedişində iştirakçılar iki dəfə ümumi bir qərara (konsensus deyilən) gəlməlidirlər: seçilmiş nömrələri nə vaxt aşkar etməyə başlamaq və buna görə də hashləri qəbul etməyi dayandırmaq və seçilmiş nömrələri qəbul etməyi və nəticədə təsadüfi hesablamanı nə vaxt dayandırmaq lazımdır. nömrə. Bir-birinə güvənməyən iştirakçılar arasında belə qərarlar qəbul etmək özlüyündə asan məsələ deyil və biz buna gələcək məqalələrdə qayıdacağıq, bu yazıda belə bir konsensus alqoritminin bizim üçün mövcud olduğunu güman edəcəyik.

RANDAO yuxarıda təsvir etdiyimiz xassələrdən hansına malikdir? Bu gözlənilməzdir, əsas konsensus protokolu ilə eyni canlılığa malikdir, lakin qərəzlidir. Konkret olaraq, təcavüzkar şəbəkəni müşahidə edə bilər və digər iştirakçılar onların nömrələrini açıqladıqdan sonra onların XOR-unu hesablaya və nəticəyə təsir etmək üçün nömrəsini açıb-açmamağa qərar verə bilər. Bu, təcavüzkarın təsadüfi ədədlər generatorunun çıxışını təkbaşına müəyyən etməsinə mane olsa da, yenə də ona 1 bit təsir bağışlayır. Təcavüzkarlar bir neçə iştirakçıya nəzarət edirlərsə, nəzarət etdikləri bitlərin sayı onların nəzarəti altında olan iştirakçıların sayına bərabər olacaqdır.

İştirakçılardan nömrələri ardıcıllıqla açıqlamalarını tələb etməklə təcavüzkarların təsirini xeyli azaltmaq olar. Sonra təcavüzkar nəticəyə yalnız sonuncu dəfə açıldığı təqdirdə təsir göstərə biləcək. Təsir əhəmiyyətli dərəcədə az olsa da, alqoritm hələ də qərəzlidir.

RANDAO+VDF

RANDAO-nu qərəzsizləşdirməyin bir yolu belədir: bütün rəqəmlər aşkar edildikdən və XOR hesablandıqdan sonra onun nəticəsi funksiyanın girişinə verilir, onun hesablanması çox uzun vaxt aparır, lakin parametrin düzgünlüyünü yoxlamağa imkan verir. çox tez hesablama.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Bu funksiya Doğrulana bilən gecikmə funksiyası və ya VDF adlanır. Əgər yekun nəticənin hesablanması nömrənin açıqlanması mərhələsindən daha uzun çəkirsə, o zaman təcavüzkar öz nömrəsini göstərməyin və ya gizlətməyin effektini proqnozlaşdıra bilməyəcək və buna görə də nəticəyə təsir etmək imkanını itirəcək.

Yaxşı VDF-lərin hazırlanması olduqca çətindir. Bu yaxınlarda bir neçə irəliləyiş oldu, məsələn. bu и bu, bu, VDF-ni praktikada daha praktik hala gətirdi və Ethereum 2.0 uzun müddətdə VDF ilə RANDAO-nu təsadüfi nömrə mənbəyi kimi istifadə etməyi planlaşdırır. Bu yanaşmanın gözlənilməz və qərəzsiz olması ilə yanaşı, şəbəkədə ən azı iki iştirakçının olması halında (istifadə olunan konsensus protokolunun belə az sayda iştirakçı ilə işləyərkən məqsədəuyğun olduğunu fərz etsək) onun həyat qabiliyyətli olmasının əlavə üstünlüyü var.

Bu yanaşmanın ən böyük problemi VDF-ni elə qurmaqdır ki, hətta çox bahalı ixtisaslaşdırılmış avadanlıqa malik olan iştirakçı da kəşf mərhələsinin sonuna qədər VDF-ni hesablaya bilməyəcək. İdeal olaraq, alqoritmin hətta əhəmiyyətli təhlükəsizlik marjası olmalıdır, məsələn, 10x. Aşağıdakı şəkildə VDF-ni RANDAO təsdiqini aşkar etmək üçün ayrılan vaxtdan daha sürətli işə salmağa imkan verən ixtisaslaşmış ASIC-ə malik olan aktyorun hücumu göstərilir. Belə bir iştirakçı yenə də öz nömrəsindən istifadə edib-etməməklə yekun nəticəni hesablaya bilər, sonra isə hesablama əsasında onu göstərib-göstərməməyi seçə bilər.

Yuxarıda qeyd olunan VDF ailəsi üçün xüsusi ASIC-in performansı adi aparatdan 100+ dəfə yüksək ola bilər. Beləliklə, yerləşdirmə mərhələsi 10 saniyə davam edərsə, belə bir ASIC-də hesablanan VDF 100x təhlükəsizlik marjasına sahib olmaq üçün 10 saniyədən çox çəkməlidir və beləliklə, əmtəə avadanlıqlarında hesablanan eyni VDF 100x 100 saniyə = ~3 saat çəkməlidir.

Ethereum Fondu bu problemi özünün açıq, pulsuz ASIC-lərini yaratmaqla həll etməyi planlaşdırır. Bu baş verdikdən sonra bütün digər protokollar da bu texnologiyadan yararlana bilər, lakin o vaxta qədər RANDAO+VDF yanaşması öz ASIC-lərini inkişaf etdirməyə sərmayə qoya bilməyən protokollar üçün uyğun olmayacaq.

VDF haqqında çoxlu məqalələr, videolar və digər məlumatlar toplanmışdır bu sayt.

Biz silmə kodlarından istifadə edirik

Bu bölmədə biz istifadə edən təsadüfi ədəd yaratma protokoluna baxacağıq kodların silinməsi. O, həyat qabiliyyətini saxlayaraq ⅓-ə qədər hücumçuya dözə bilər və nəticəni proqnozlaşdıra və ya təsir etmədən əvvəl ⅔-ə qədər təcavüzkarın mövcud olmasına imkan verir.

Protokolun əsas ideyası aşağıdakı kimidir. Sadəlik üçün fərz edək ki, tam 100 iştirakçı var. Fərz edək ki, bütün iştirakçıların yerli olaraq bəzi gizli açarları var və bütün iştirakçıların açıq açarları bütün iştirakçılara məlumdur:

1. Hər bir iştirakçı yerli olaraq uzun bir sətir tapır, onu 67 hissəyə bölür, 100 paylaşım əldə etmək üçün silmə kodları yaradır ki, sətri bərpa etmək üçün istənilən 67 ədəd kifayətdir, 100 paylaşımın hər birini iştirakçılardan birinə təyin edir və onları şifrələyir. eyni iştirakçının açıq açarı. Bütün kodlanmış paylaşımlar daha sonra dərc olunur.

2. İştirakçılar xüsusi 67 iştirakçıdan kodlanmış dəstlər üzrə razılığa gəlmək üçün bir növ konsensusdan istifadə edirlər.

3. Konsensus əldə edildikdən sonra hər bir iştirakçı öz açıq açarı ilə şifrələnmiş 67 dəstdən hər birində kodlanmış səhmləri götürür, bütün bu cür paylaşımların şifrəsini açır və bütün belə şifrələnmiş paylaşımları dərc edir.

4. 67 iştirakçı (3) addımını tamamladıqdan sonra, bütün razılaşdırılmış dəstlər silmə kodlarının xüsusiyyətlərinə görə tamamilə deşifrə edilə və yenidən qurula bilər və yekun nömrə iştirakçıların (1) ilə başladıqları ilkin sıraların XOR kimi əldə edilə bilər. .

Bu protokolun qərəzsiz və gözlənilməz olduğunu göstərmək olar. Nəticə olan təsadüfi nömrə konsensus əldə edildikdən sonra müəyyən edilir, lakin iştirakçıların ⅔ hissəsi açıq açarı ilə şifrələnmiş hissələrin şifrəsini açana qədər heç kimə məlum deyil. Beləliklə, təsadüfi nömrə onu yenidən qurmaq üçün kifayət qədər məlumat dərc edilməzdən əvvəl müəyyən edilir.

Əgər (1) addımda iştirakçılardan biri bəzi sətir üçün düzgün silmə kodu olmayan digər iştirakçılara kodlaşdırılmış paylaşımlar göndərsə nə olar? Əlavə dəyişikliklər edilmədən müxtəlif iştirakçılar ya sətri ümumiyyətlə bərpa edə bilməyəcəklər, ya da müxtəlif sətirləri bərpa edəcəklər ki, bu da müxtəlif iştirakçıların fərqli təsadüfi nömrə alması ilə nəticələnəcək. Bunun qarşısını almaq üçün aşağıdakıları edə bilərsiniz: hər bir iştirakçı kodlanmış paylaşımlara əlavə olaraq, həmçinin hesablayır Merkla ağacı bütün bu cür paylaşımlar və hər bir iştirakçıya həm kodlanmış payın özünü, həm də merkle ağacının kökünü və payın merkle ağacına daxil edilməsinin sübutunu göndərir. (2-ci addımda) konsensusda iştirakçılar yalnız dəstlər toplusunda deyil, bu cür ağacların spesifik kökləri toplusunda da razılığa gəlirlər (əgər bəzi iştirakçı protokoldan kənara çıxarsa və fərqli iştirakçılara müxtəlif merkle ağacı kökləri göndəribsə, və iki belə kök konsensus zamanı göstərilir, onun sırası nəticə dəstinə daxil edilmir). Konsensus nəticəsində biz 67 kodlanmış sətir və merkle ağacının müvafiq köklərinə sahib olacağıq ki, 67 sətirin hər biri üçün ən azı 67 iştirakçı (müvafiq sətirləri təklif edənlər eyni deyil) olsun. silmə kodunun payı olan bir mesaj və onların payının müvafiq ağacda baş verməsinin sübutu.

(4) addımda iştirakçı müəyyən sim üçün 67 vuruşu deşifrə etdikdə və onlardan orijinal simi yenidən qurmağa çalışdıqda, variantlardan biri mümkündür:

1. Sətir bərpa edilir və əgər o, yenidən silinmə ilə kodlaşdırılarsa və Merkle ağacı yerli olaraq hesablanmış paylaşımlar üçün hesablanırsa, kök konsensusun əldə edildiyi ilə üst-üstə düşür.

2. Sıra bərpa edildi, lakin yerli olaraq hesablanmış kök konsensusun əldə olunduğu ilə uyğun gəlmir.

3. Sıra bərpa edilmir.

Göstərmək asandır ki, əgər variant (1) yuxarıdakı ən azı bir iştirakçı üçün baş veribsə, onda (1) variant bütün iştirakçılar üçün baş verib və əksinə, əgər variant (2) və ya (3) ən azı bir iştirakçı üçün baş veribsə, onda bütün iştirakçılar üçün (2) və ya (3) variantı baş verəcəkdir. Beləliklə, setdəki hər bir sıra üçün ya bütün iştirakçılar onu uğurla bərpa edəcək, ya da bütün iştirakçılar onu bərpa edə bilməyəcəklər. Nəticədə ortaya çıxan təsadüfi nömrə yalnız iştirakçıların bərpa edə bildiyi sətirlərin XOR-u olur.

İmza həddi

Təsadüfiliyə başqa bir yanaşma BLS hədd imzaları adlanandan istifadə etməkdir. Həddi imzalara əsaslanan təsadüfi ədəd generatoru yuxarıda təsvir edilən silmə koduna əsaslanan alqoritmlə eyni zəmanətlərə malikdir, lakin hər bir yaradılan nömrə üçün şəbəkə üzərindən göndərilən mesajların əhəmiyyətli dərəcədə aşağı asimptotik sayına malikdir.

BLS imzaları birdən çox iştirakçıya mesaj üçün bir ümumi imza yaratmağa imkan verən dizayndır. Bu imzalar çox vaxt birdən çox imzanın göndərilməsini tələb etmədən yer və bant genişliyinə qənaət etmək üçün istifadə olunur. 

Blockchain protokollarında BLS imzaları üçün ümumi tətbiq, təsadüfi nömrələr yaratmaqla yanaşı, BFT protokollarında blok imzalanmasıdır. Tutaq ki, 100 iştirakçı blok yaradır və onlardan 67-si imzalasa, blok yekun sayılır. Onların hamısı BLS imzasının öz hissələrini təqdim edə və bəzi konsensus alqoritmindən istifadə edərək onlardan 67-ni razılaşdıra və sonra onları bir BLS imzasına birləşdirə bilərlər. Yekun imzanı yaratmaq üçün hər hansı 67 (və ya daha çox) hissədən istifadə edilə bilər, bu, hansı 67 imzanın birləşdirildiyindən asılı olacaq və buna görə də dəyişə bilər, baxmayaraq ki, 67 iştirakçının fərqli seçimləri fərqli imza yaradacaq, hər hansı belə imza etibarlı olacaq blok üçün imza. Qalan iştirakçılar bundan sonra şəbəkə üzərindən 67 imza əvəzinə hər blok üçün yalnız bir imza qəbul edib yoxlamalıdırlar ki, bu da şəbəkədəki yükü əhəmiyyətli dərəcədə azaldır.

Belə çıxır ki, iştirakçıların istifadə etdiyi şəxsi açarlar müəyyən bir şəkildə yaradılırsa, o zaman hansı 67 imzanın (yaxud daha çox, lakin az olmamaq şərti ilə) cəmlənməsindən asılı olmayaraq, əldə edilən imza eyni olacaq. Bu təsadüfilik mənbəyi kimi istifadə edilə bilər: iştirakçılar əvvəlcə imzalayacaqları bəzi mesajla razılaşırlar (bu RANDAO-nun çıxışı və ya sadəcə sonuncu blokun hashı ola bilər, hər dəfə dəyişdiyi müddətcə bunun heç bir əhəmiyyəti yoxdur. və ardıcıldır) və bunun üçün BLS imzası yaradın. 67 iştirakçı öz hissələrini təmin edənə qədər nəslin nəticəsi gözlənilməz olacaq və bundan sonra nəticə əvvəlcədən müəyyən edilmişdir və heç bir iştirakçının hərəkətlərindən asılı ola bilməz.

Təsadüfiliyə bu yanaşma, onlayn iştirakçıların ən azı ⅔ hissəsi protokola əməl etdikcə etibarlıdır və iştirakçıların ən azı ⅓ hissəsi protokola əməl etdikcə qərəzsiz və gözlənilməzdir. Qeyd etmək vacibdir ki, iştirakçıların ⅓-dən çox, lakin ⅔-dən azına nəzarət edən təcavüzkar protokolu dayandıra bilər, lakin onun çıxışını proqnozlaşdıra və ya təsir edə bilməz.

Eşik imzalarının özü çox maraqlı mövzudur. Məqalənin ikinci hissəsində onların necə işlədiyini və həddi imzaların təsadüfi nömrə generatoru kimi istifadə oluna bilməsi üçün iştirakçı açarlarının necə dəqiq yaradılmasının lazım olduğunu ətraflı təhlil edəcəyik.

Nəticədə

Bu məqalə texniki blog məqalələri seriyasının birincisidir 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