Хэрэв бид бие биедээ итгэхгүй бол санамсаргүй тоо үүсгэх боломжтой юу? 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) // это очень быстро

Энэ функцийг Verfiable Delay Function буюу VDF гэж нэрлэдэг. Хэрэв эцсийн үр дүнг тооцоолоход тоо илчлэх үе шатнаас илүү хугацаа шаардагдах юм бол халдагч өөрийн дугаарыг харуулах эсвэл нуух үр нөлөөг урьдчилан таамаглах боломжгүй тул үр дүнд нөлөөлөх боломжоо алдах болно.

Сайн VDF боловсруулах нь маш хэцүү байдаг. Сүүлийн үед хэд хэдэн нээлт хийсэн, жишээ нь. энэ нь и энэ, Энэ нь VDF-ийг практикт илүү практик болгосон бөгөөд Ethereum 2.0 нь RANDAO-г VDF-тэй санамсаргүй тооны эх үүсвэр болгон урт хугацаанд ашиглахаар төлөвлөж байна. Энэ арга нь урьдчилан таамаглах боломжгүй, шударга бус байдгаас гадна сүлжээнд дор хаяж хоёр оролцогчтой бол амьдрах боломжтой гэсэн нэмэлт давуу талтай (энэ нь цөөн тооны оролцогчидтой харьцах үед ашигласан зөвшилцлийн протоколыг ашиглах боломжтой гэж үзвэл).

Энэ аргын хамгийн том сорилт бол VDF-ийг маш үнэтэй тусгай тоног төхөөрөмжтэй оролцогч хүртэл нээлтийн үе дуусахаас өмнө VDF-ийг тооцоолох боломжгүй байхаар тохируулах явдал юм. Хамгийн тохиромжтой нь алгоритм нь 10x гэх мэт аюулгүй байдлын мэдэгдэхүйц хязгаартай байх ёстой. Доорх зураг нь RANDAO баталгаажуулалтыг илчлэхийн тулд VDF-г илүү хурдан ажиллуулах боломжийг олгодог тусгай ASIC-тэй жүжигчний дайралтыг харуулж байна. Ийм оролцогч өөрийн дугаарыг ашиглан эцсийн үр дүнг тооцоолж, дараа нь тооцоолол дээр үндэслэн харуулах эсэхээ сонгох боломжтой.

Дээр дурдсан VDF гэр бүлийн хувьд зориулалтын ASIC-ийн гүйцэтгэл нь ердийн техник хангамжаас 100+ дахин өндөр байж болно. Хэрэв байршуулах үе шат 10 секунд үргэлжилдэг бол ийм ASIC дээр тооцоолсон VDF нь 100x аюулгүй байдлын маржинтай байхын тулд 10 секундээс илүү хугацаа шаардагдах бөгөөд ингэснээр барааны техник хангамж дээр тооцоолсон VDF нь 100x100 секунд = ~3 цаг болно.

Ethereum сан нь өөрийн олон нийтэд нээлттэй, үнэ төлбөргүй ASIC-уудыг бий болгосноор энэ асуудлыг шийдэхээр төлөвлөж байна. Нэгэнт ийм зүйл тохиолдвол бусад бүх протоколууд энэ технологийн давуу талыг ашиглах боломжтой боловч тэр хүртэл RANDAO+VDF арга нь өөрсдийн ASIC-г хөгжүүлэхэд хөрөнгө оруулалт хийх боломжгүй протоколуудад тийм ч ашигтай биш байх болно.

VDF-ийн талаар олон нийтлэл, видео болон бусад мэдээллийг цуглуулсан энэ сайт.

Бид устгах кодыг ашигладаг

Энэ хэсэгт бид санамсаргүй тоо үүсгэх протоколыг ашигладаг кодуудыг устгах. Энэ нь ⅓ хүртэлх халдагчдыг тэсвэрлэхийн зэрэгцээ амьдрах чадвартай байх ба ⅔ хүртэлх халдагчдыг урьдчилан таамаглах эсвэл үр дүнд нь нөлөөлөхөөс өмнө оршин тогтнох боломжийг олгодог.

Протоколын гол санаа нь дараах байдалтай байна. Энгийнээр хэлэхэд яг 100 оролцогч байна гэж бодъё. Орон нутгийн бүх оролцогчид хувийн түлхүүртэй бөгөөд бүх оролцогчдын нийтийн түлхүүрийг бүх оролцогчид мэддэг гэж үзье.

1. Оролцогч бүр орон нутгийн хэмжээнд урт утсыг гаргаж ирээд 67 хэсэгт хувааж, 100 хувьцаа авахын тулд устгах код үүсгэж, 67 нь мөрийг сэргээхэд хангалттай бөгөөд 100 хувьцаа бүрийг оролцогчдын аль нэгэнд оноож, шифрлэдэг. ижил оролцогчийн нийтийн түлхүүр. Дараа нь бүх кодлогдсон хувьцаанууд нийтлэгдэнэ.

2. Оролцогчид тодорхой 67 оролцогчоос кодлогдсон багц дээр тохиролцоонд хүрэхийн тулд зарим төрлийн зөвшилцлийг ашигладаг.

3. Зөвшилцөлд хүрсний дараа оролцогч бүр өөрийн нийтийн түлхүүрээр шифрлэгдсэн 67 багц тус бүрийн кодлогдсон хувьцааг авч, бүх ийм хувьцааны шифрийг тайлж, нийтлэнэ.

4. 67 оролцогч (3) алхмыг дуусгасны дараа арилгах кодын шинж чанаруудын улмаас тохиролцсон бүх багцыг бүрэн тайлж, дахин бүтээх боломжтой бөгөөд эцсийн тоог оролцогчдын (1)-д эхлүүлсэн эхний мөрүүдийн XOR хэлбэрээр авах боломжтой. .

Энэ протокол нь нэг талыг барьсан, урьдчилан таамаглах боломжгүй гэдгийг харуулж болно. Үүссэн санамсаргүй тоог зөвшилцөлд хүрсний дараа тодорхойлох боловч оролцогчдын ⅔ нь нийтийн түлхүүрээр шифрлэгдсэн хэсгүүдийг тайлах хүртэл хэнд ч мэдэгдэхгүй. Тиймээс санамсаргүй тоог сэргээн босгоход хангалттай мэдээлэл нийтлэхээс өмнө тодорхойлно.

Хэрэв (1) алхамд оролцогчдын нэг нь бусад оролцогчдод зарим нэг мөрийн устгах код биш кодлогдсон хувьцаа илгээсэн бол яах вэ? Нэмэлт өөрчлөлт оруулахгүй бол өөр оролцогчид мөрийг огт сэргээх боломжгүй, эсвэл өөр өөр оролцогчид өөр санамсаргүй тоо хүлээн авахад хүргэдэг. Үүнээс урьдчилан сэргийлэхийн тулд та дараахь зүйлийг хийж болно: оролцогч бүр кодлогдсон хувьцаанаас гадна тооцоолдог. Меркла мод бүх ийм хувьцаа, мөн оролцогч бүр кодлогдсон хувьцааны өөрөө болон merkle модны үндсийг хоёуланг нь илгээж, мөн хувьцааг merkle модонд оруулсан нотлох баримтыг илгээнэ. (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 оролцогчид өөрсдийн хэсгийг өгөх хүртэл үр дүн нь урьдчилан таамаглах боломжгүй бөгөөд үүний дараа гаралт нь аль хэдийн тодорхойлогдсон бөгөөд аль ч оролцогчийн үйлдлээс хамаарах боломжгүй юм.

Санамсаргүй байдлын энэхүү арга нь онлайн оролцогчдын дор хаяж XNUMX нь протоколыг дагаж мөрдвөл үр дүнтэй бөгөөд оролцогчдын дор хаяж ⅓ нь протоколыг дагаж мөрдвөл шударга, урьдчилан таамаглах боломжгүй юм. Оролцогчдын ⅓-аас илүү, харин ⅔-аас бага хувийг эзэлдэг халдагч протоколыг зогсоож болох боловч түүний гаралтыг урьдчилан таамаглах эсвэл нөлөөлж чадахгүй гэдгийг анхаарах нь чухал юм.

Босго гарын үсэг нь өөрөө маш сонирхолтой сэдэв юм. Өгүүллийн хоёр дахь хэсэгт бид тэдгээр нь хэрхэн ажилладаг, босго гарын үсгийг санамсаргүй тоо үүсгэгч болгон ашиглахын тулд оролцогчийн түлхүүрүүдийг яг хэрхэн үүсгэх шаардлагатайг нарийвчлан шинжлэх болно.

Эцэст нь хэлэхэд

Энэ нийтлэл нь техникийн цуврал нийтлэлүүдийн эхнийх нь юм НЭГ. NEAR нь төвлөрсөн бус программуудыг хөгжүүлэхэд зориулагдсан блокчейн протокол ба платформ бөгөөд эцсийн хэрэглэгчдэд хялбар хөгжүүлэлт, ашиглахад хялбар байдлыг чухалчилдаг.

Протоколын код нь нээлттэй, бидний хэрэгжилт Rust дээр бичигдсэн, үүнийг олж болно энд.

Та NEAR-д зориулсан хөгжүүлэлт ямар байгааг харж, онлайн IDE дээр туршиж үзэх боломжтой энд.

Та бүх мэдээг орос хэл дээр үзэх боломжтой телеграм групп болон дотор ВКонтакте дахь бүлэг, албан ёсны англи хэл дээр twitter.

Удахгүй уулзацгаая!

Эх сурвалж: www.habr.com