Бір-бірімізге сенбесек, кездейсоқ сандарды шығаруға болады ма? 1-бөлім

Эй Хабр!

Бұл мақалада мен бір-біріне сенбейтін қатысушылардың псевдокездейсоқ сандарды генерациялауы туралы айтатын боламын. Төменде көретініміздей, «дерлік» жақсы генераторды енгізу өте қарапайым, бірақ өте жақсы генераторды енгізу қиын.

Неліктен бір-біріне сенбейтін қатысушылар арасында кездейсоқ сандарды генерациялау қажет? Қолданбалардың бірі орталықтандырылмаған қолданбалар. Мысалы, қатысушыдан бәс тігуді қабылдайтын және 49% ықтималдықпен соманы екі есе арттыратын немесе 51% ықтималдықпен алып тастайтын қолданба кездейсоқ санды объективті түрде ала алатын болса ғана жұмыс істейді. Егер шабуылдаушы кездейсоқ сандар генераторының нәтижесіне әсер ете алса және тіпті қолданбада төлем алу мүмкіндігін сәл арттырса, ол оны оңай бұзады.

Бөлінген кездейсоқ сандарды генерациялау хаттамасын құрастырған кезде оның үш қасиеті болғанын қалаймыз:

1. Ол бейтарап болуы керек. Басқаша айтқанда, бірде-бір қатысушы кездейсоқ сандар генераторының нәтижесіне әсер етпеуі керек.

2. Ол күтпеген болуы керек. Басқаша айтқанда, ешбір қатысушы қандай санның жасалатынын (немесе оның қандай да бір қасиетін шығаратынын) ол жасалмас бұрын болжай алмайды.

3. Хаттама өміршең болуы керек, яғни қатысушылардың белгілі бір пайызы желіден ажыратылуына немесе хаттаманы әдейі тоқтатуға тырысуына төзімді болуы керек.

Бұл мақалада біз екі тәсілді қарастырамыз: RANDAO + VDF және өшіру кодтары тәсілі. Келесі бөлімде біз шекті қолтаңбаларға негізделген тәсілді егжей-тегжейлі қарастырамыз.

Бірақ алдымен өміршең, болжау мүмкін емес, бірақ біржақты қарапайым және жиі қолданылатын алгоритмді қарастырайық.

РАНДАО

RANDAO өте қарапайым, сондықтан кездейсоқтықты құру үшін жиі қолданылатын тәсіл. Барлық желі қатысушылары алдымен жергілікті түрде жалған кездейсоқ нөмірді таңдайды, содан кейін әрбір қатысушы таңдалған нөмірдің хэшін жібереді. Әрі қарай қатысушылар кезекпен таңдаған сандарын ашады және анықталған сандарға XOR операциясын орындайды және бұл операцияның нәтижесі хаттаманың нәтижесі болады.

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

Хаттама барысында қатысушылар екі рет ортақ шешімге (консенсус деп аталатын) келуі керек: таңдалған сандарды қашан ашуды бастау керек, сондықтан хэштерді қабылдауды тоқтату және таңдалған сандарды қабылдауды және алынған кездейсоқ сандарды есептеуді қашан тоқтату керек. саны. Бір-біріне сенбейтін қатысушылар арасында мұндай шешім қабылдаудың өзі оңай шаруа емес және біз оған келесі мақалаларда қайта ораламыз, осы мақалада біз осындай консенсус алгоритмі бізге қол жетімді деп есептейміз.

RANDAO жоғарыда сипатталған қасиеттердің қайсысына ие? Бұл болжау мүмкін емес, негізгі консенсус хаттамасымен бірдей өміршеңдікке ие, бірақ ол біржақты. Нақтырақ айтқанда, шабуылдаушы желіні бақылай алады және басқа қатысушылар олардың нөмірлерін ашқаннан кейін, олардың XOR мәнін есептей алады және нәтижеге әсер ету үшін өз нөмірін ашу немесе көрсетпеу туралы шешім қабылдай алады. Бұл шабуылдаушыға кездейсоқ сандар генераторының шығысын жалғыз анықтауға кедергі келтірсе де, оған 1 бит әсер береді. Ал егер шабуылдаушылар бірнеше қатысушыны басқарса, онда олар басқаратын биттердің саны олардың бақылауындағы қатысушылардың санына тең болады.

Қатысушылардан сандарды ретімен көрсетуді талап ету арқылы шабуылдаушылардың ықпалын айтарлықтай азайтуға болады. Сонда шабуылдаушы соңғы ашылған жағдайда ғана нәтижеге әсер ете алады. Әсер айтарлықтай аз болғанымен, алгоритм әлі де біржақты.

RANDAO+VDF

RANDAO-ны бейтарап етудің бір жолы мынада: барлық сандар ашылғаннан кейін және XOR есептелгеннен кейін оның нәтижесі функцияның кірісіне беріледі, оны есептеу өте ұзақ уақытты алады, бірақ оның дұрыстығын тексеруге мүмкіндік береді. есептеу өте жылдам.

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

Бұл функция Тексерілетін кешіктіру функциясы немесе VDF деп аталады. Егер түпкілікті нәтижені есептеу нөмірді ашу кезеңінен ұзағырақ болса, онда шабуылдаушы өз нөмірін көрсету немесе жасыру әсерін болжай алмайды, сондықтан ол нәтижеге әсер ету мүмкіндігін жоғалтады.

Жақсы VDF жасау өте қиын. Жақында бірнеше жетістіктер болды, мысалы. бұл и бұл, бұл VDF-ті іс жүзінде практикалық етті және Ethereum 2.0 ұзақ мерзімді перспективада VDF-мен RANDAO-ны кездейсоқ сандар көзі ретінде пайдалануды жоспарлап отыр. Бұл тәсіл болжау мүмкін емес және бейтарап болуымен қатар, желіде кем дегенде екі қатысушы болса, өміршең болуының қосымша артықшылығы бар (қолданылатын консенсус хаттамасы қатысушылардың соншалықты аз санымен жұмыс істегенде өміршең болады деп есептесек).

Бұл тәсілдің ең үлкен мәселесі - VDF-ті орнату, тіпті өте қымбат мамандандырылған жабдыққа ие қатысушы VDF-ті ашу кезеңінің соңына дейін есептей алмайды. Ең дұрысы, алгоритмде айтарлықтай қауіпсіздік маржасы болуы керек, айталық 10x. Төмендегі суретте RANDAO растауын ашуға бөлінген уақыттан жылдамырақ VDF іске қосуға мүмкіндік беретін мамандандырылған ASIC бар актердің шабуылы көрсетілген. Мұндай қатысушы әлі де өз нөмірін пайдаланып немесе пайдаланбай түпкілікті нәтижені есептей алады, содан кейін есептеу негізінде оны көрсету немесе көрсетпеуді таңдай алады.

Жоғарыда аталған VDF отбасы үшін арнайы ASIC өнімділігі кәдімгі жабдыққа қарағанда 100+ есе жоғары болуы мүмкін. Сонымен, егер орналастыру кезеңі 10 секундқа созылса, мұндай ASIC-те есептелген VDF 100x қауіпсіздік маржасына ие болу үшін 10 секундтан астам уақыт алуы керек, осылайша тауарлық жабдықта есептелген VDF 100x 100 секунд = ~3 сағатты алуы керек.

Ethereum Foundation бұл мәселені өзінің жалпыға қолжетімді, тегін ASIC құру арқылы шешуді жоспарлап отыр. Бұл орын алған соң, барлық басқа хаттамалар да осы технологияның артықшылығын пайдалана алады, бірақ оған дейін RANDAO+VDF тәсілі өздерінің ASIC-терін жасауға инвестиция сала алмайтын хаттамалар үшін өміршең болмайды.

VDF туралы көптеген мақалалар, бейнелер және басқа ақпарат жиналды бұл сайт.

Біз өшіру кодтарын қолданамыз

Бұл бөлімде біз кездейсоқ сандарды генерациялау протоколын қарастырамыз кодтарды өшіру. Ол өміршеңдігін сақтай отырып, ⅓ дейін шабуылдаушыларға шыдай алады және ⅔ дейін шабуылдаушыларға нәтижені болжауға немесе оған әсер етуге мүмкіндік береді.

Хаттаманың негізгі идеясы келесідей. Қарапайымдылық үшін дәл 100 қатысушы бар деп есептейік. Сондай-ақ барлық қатысушылардың жергілікті түрде жеке кілті бар және барлық қатысушылардың ашық кілттері барлық қатысушыларға белгілі деп есептейік:

1. Әрбір қатысушы жергілікті түрде ұзын жолды ойлап табады, оны 67 бөлікке бөледі, жолды қалпына келтіру үшін кез келген 100 жеткілікті болатындай 67 үлесті алу үшін өшіру кодтарын жасайды, 100 акцияның әрқайсысын қатысушылардың біріне тағайындайды және оларды шифрлайды. сол қатысушының ашық кілті. Содан кейін барлық кодталған акциялар жарияланады.

2. Қатысушылар нақты 67 қатысушының кодталған жиынтықтары бойынша келісімге келу үшін консенсустың қандай да бір түрін пайдаланады.

3. Консенсусқа қол жеткізгеннен кейін әрбір қатысушы өзінің ашық кілтімен шифрланған 67 жиынның әрқайсысында кодталған үлестерді алады, осындай барлық акциялардың шифрын шешеді және шифры шешілген барлық акцияларды жариялайды.

4. 67 қатысушы (3) қадамды орындағаннан кейін, өшіру кодтарының қасиеттеріне байланысты барлық келісілген жиынтықтарды толығымен декодтауға және қайта құруға болады және соңғы нөмірді қатысушылар (1) тармақта бастаған бастапқы жолдардың XOR ретінде алуға болады. .

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

(1)-қадамда қатысушылардың бірі басқа қатысушыларға кейбір жол үшін дұрыс өшіру коды болып табылмайтын кодталған үлестерді жіберсе не болады? Қосымша өзгерістерсіз әртүрлі қатысушылар жолды мүлде қалпына келтіре алмайды немесе олар әртүрлі жолдарды қалпына келтіреді, бұл әртүрлі қатысушылардың басқа кездейсоқ санды алуына әкеледі. Бұған жол бермеу үшін келесі әрекеттерді орындауға болады: әрбір қатысушы кодталған акциялардан басқа Меркла ағашы барлық осындай бөліседі және әрбір қатысушыға кодталған үлестің өзін де, меркле ағашының түбірін де, үлесті меркле ағашына қосудың дәлелін де жібереді. (2) қадамдағы консенсуста қатысушылар жиынтықтар жиынтығы бойынша ғана келіспейді, сонымен қатар осындай ағаштардың белгілі бір тамырларының жиынтығы бойынша (егер кейбір қатысушы хаттамадан ауытқыса және әртүрлі қатысушыларға әртүрлі ағаш тамырларын жіберсе, және осындай екі түбір консенсус кезінде көрсетіледі, оның жолы нәтиже жиынына кірмейді). Консенсус нәтижесінде бізде 67 кодталған жолдар және меркле ағашының сәйкес түбірлері болады, сондықтан кем дегенде 67 қатысушы (тиісті жолдарды ұсынғандар бірдей емес), 67 жолдың әрқайсысы үшін өшіру кодының үлесі бар хабарлама және сәйкес ағашта олардың үлесі жойылғанының дәлелі.

(4) қадамда қатысушы белгілі бір жол үшін 67 соққыны шешіп, олардан бастапқы жолды қайта құруға тырысқанда, опциялардың бірі мүмкін:

1. Жол қалпына келтіріліп, егер ол қайтадан өшірілсе және Merkle тармағы жергілікті есептелген акциялар үшін есептелсе, түбір консенсусқа қол жеткізілгенмен сәйкес келеді.

2. Жол қалпына келтірілді, бірақ жергілікті есептелген түбір консенсусқа жеткенге сәйкес келмейді.

3. Жол қалпына келтірілмейді.

Егер (1) нұсқа жоғарыда кем дегенде бір қатысушы үшін орындалса, онда (1) нұсқа барлық қатысушылар үшін орындалғанын және керісінше, егер (2) немесе (3) опция кем дегенде бір қатысушы үшін орын алса, онда көрсету оңай. барлық қатысушылар үшін (2) немесе (3) опция орындалады. Осылайша, жиынтықтағы әрбір жол үшін не барлық қатысушылар оны сәтті қалпына келтіреді, не барлық қатысушылар оны қалпына келтіре алмайды. Алынған кездейсоқ сан қатысушылар қалпына келтіре алған жолдардың ғана XOR мәні болып табылады.

Шекті қолдар

Кездейсоқтыққа тағы бір тәсіл - BLS шектік қолтаңбалары деп аталатындарды пайдалану. Шекті қолтаңбаларға негізделген кездейсоқ сандар генераторы жоғарыда сипатталған өшіру кодына негізделген алгоритмімен бірдей кепілдіктерге ие, бірақ әрбір жасалған сан үшін желі арқылы жіберілетін хабарламалардың асимптотикалық саны айтарлықтай төмен.

BLS қолтаңбалары бірнеше қатысушыларға хабар үшін бір ортақ қолтаңба жасауға мүмкіндік беретін дизайн. Бұл қолтаңбалар көп қолтаңбаны жіберуді талап етпей, кеңістік пен өткізу қабілеттілігін үнемдеу үшін жиі пайдаланылады. 

Блокчейн протоколдарындағы BLS қолтаңбаларына арналған жалпы қолданба кездейсоқ сандарды генерациялаудан басқа, BFT хаттамаларында блокқа қол қою болып табылады. Айталық, 100 қатысушы блоктар жасайды және олардың 67-сі қол қойған жағдайда блок түпкілікті болып саналады. Олардың барлығы BLS қолтаңбасының бөліктерін жібере алады және олардың 67-сі бойынша келісу үшін кейбір консенсус алгоритмін қолдана алады, содан кейін оларды бір BLS қолтаңбасына біріктіреді. Қорытынды қолтаңбаны жасау үшін кез келген 67 (немесе одан да көп) бөліктер пайдаланылуы мүмкін, ол 67 қолдың біріктірілгеніне байланысты болады, сондықтан әр түрлі болуы мүмкін, дегенмен 67 қатысушының әртүрлі таңдауы басқа қолтаңбаны жасайды , кез келген осындай қолтаңба жарамды болады. блокқа қол қою. Қалған қатысушылар желі арқылы 67 емес, бір блокта тек бір ғана қолтаңбаны алып, тексеруі керек, бұл желідегі жүктемені айтарлықтай азайтады.

Қатысушылар пайдаланатын жеке кілттер белгілі бір жолмен жасалса, онда қандай 67 қол (немесе көп, бірақ кем емес) біріктірілгеніне қарамастан, алынған қолтаңба бірдей болады. Бұл кездейсоқтық көзі ретінде пайдаланылуы мүмкін: қатысушылар алдымен қол қоятын кейбір хабарламаға келіседі (бұл RANDAO шығысы немесе соңғы блоктың хэші болуы мүмкін, ол әр уақытта өзгеретін болса, бұл маңызды емес. және сәйкес) және ол үшін BLS қолтаңбасын жасаңыз. 67 қатысушы өз бөліктерін ұсынбайынша, генерацияның нәтижесі болжамсыз болады, содан кейін нәтиже алдын ала анықталған және кез келген қатысушының әрекетіне байланысты болмайды.

Кездейсоқтыққа қатысты бұл тәсіл желідегі қатысушылардың кем дегенде ⅔ бөлігі хаттаманы орындаған кезде өміршең болып табылады және қатысушылардың кем дегенде ⅓ бөлігі хаттаманы ұстанған кезде бейтарап және болжауға болмайды. Қатысушылардың ⅓ астам, бірақ ⅔ аз бөлігін басқаратын шабуылдаушы хаттаманы тоқтата алатынын, бірақ оның шығуын болжай алмайтынын немесе оған әсер ете алмайтынын ескеру маңызды.

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

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

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

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

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

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

Көріскенше!

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