Adakah mungkin untuk menjana nombor rawak jika kita tidak mempercayai satu sama lain? Bahagian 1

Hai Habr!

Dalam artikel ini saya akan bercakap tentang penjanaan nombor pseudo-rawak oleh peserta yang tidak mempercayai antara satu sama lain. Seperti yang akan kita lihat di bawah, melaksanakan penjana "hampir" yang baik adalah agak mudah, tetapi yang sangat baik adalah sukar.

Mengapakah perlu menjana nombor rawak di kalangan peserta yang tidak mempercayai satu sama lain? Satu kawasan permohonan ialah aplikasi terdesentralisasi. Sebagai contoh, permohonan yang menerima pertaruhan daripada peserta dan sama ada menggandakan jumlah dengan kebarangkalian 49% atau mengambil dengan kebarangkalian 51% hanya akan berfungsi jika ia boleh menerima nombor rawak secara tidak berat sebelah. Jika penyerang boleh mempengaruhi hasil penjana nombor rawak, dan malah meningkatkan sedikit peluangnya untuk menerima pembayaran dalam permohonan itu, dia akan memusnahkannya dengan mudah.

Apabila kami mereka bentuk protokol penjanaan nombor rawak teragih, kami mahu ia mempunyai tiga sifat:

1. Dia mesti tidak berat sebelah. Dalam erti kata lain, tiada peserta harus dalam apa-apa cara mempengaruhi keputusan penjana nombor rawak.

2. Dia mesti tidak dapat diramalkan. Dalam erti kata lain, tiada peserta sepatutnya dapat meramalkan nombor yang akan dijana (atau membuat kesimpulan mana-mana sifatnya) sebelum ia dijana.

3. Protokol mesti berdaya maju, iaitu, tahan terhadap fakta bahawa peratusan tertentu peserta memutuskan sambungan dari rangkaian atau sengaja cuba menghentikan protokol.

Dalam artikel ini kita akan melihat dua pendekatan: RANDAO + VDF dan pendekatan kod pemadaman. Dalam bahagian seterusnya, kami akan meneliti secara terperinci pendekatan berdasarkan tandatangan ambang.

Tetapi pertama, mari kita lihat algoritma yang mudah dan biasa digunakan yang berdaya maju, tidak dapat diramalkan, tetapi berat sebelah.

RANDAO

RANDAO ialah pendekatan yang sangat mudah dan oleh itu agak biasa digunakan untuk menjana rawak. Semua peserta rangkaian mula-mula memilih nombor pseudorandom secara tempatan, kemudian setiap peserta menghantar cincang nombor yang dipilih. Seterusnya, para peserta bergilir-gilir mendedahkan nombor pilihan mereka dan melakukan operasi XOR pada nombor yang didedahkan, dan keputusan operasi ini menjadi hasil protokol.

Langkah menerbitkan cincang sebelum mendedahkan nombor adalah perlu supaya penyerang tidak boleh memilih nombornya selepas dia melihat nombor peserta lain. Ini akan membolehkan dia untuk secara hampir bersendirian menentukan output penjana nombor rawak.

Semasa menjalankan protokol, peserta perlu membuat keputusan bersama (konsensus yang dipanggil) dua kali: bila mula mendedahkan nombor yang dipilih, dan oleh itu berhenti menerima cincang, dan bila berhenti menerima nombor yang dipilih dan mengira rawak yang terhasil. nombor. Membuat keputusan sedemikian antara peserta yang tidak mempercayai satu sama lain bukanlah satu tugas yang mudah, dan kami akan kembali kepadanya dalam artikel akan datang; dalam artikel ini kami akan menganggap bahawa algoritma konsensus sedemikian tersedia untuk kami.

Antara sifat yang kami huraikan di atas, yang manakah mempunyai RANDAO? Ia tidak dapat diramalkan, mempunyai daya hidup yang sama seperti protokol konsensus asas, tetapi ia berat sebelah. Khususnya, penyerang boleh memerhati rangkaian, dan selepas peserta lain mendedahkan nombor mereka, dia boleh mengira XOR mereka, dan memutuskan sama ada untuk mendedahkan nombornya atau tidak untuk mempengaruhi keputusan. Walaupun ini menghalang penyerang daripada menentukan sendiri output penjana nombor rawak, ia masih memberinya 1 sedikit pengaruh. Dan jika penyerang mengawal beberapa peserta, maka bilangan bit yang mereka kawal akan sama dengan bilangan peserta di bawah kawalan mereka.

Pengaruh penyerang boleh dikurangkan dengan banyaknya dengan menghendaki peserta mendedahkan nombor mengikut urutan. Kemudian penyerang akan dapat mempengaruhi keputusan hanya jika ia dibuka terakhir. Walaupun pengaruhnya kurang ketara, algoritma masih berat sebelah.

RANDAO+VDF

Satu cara untuk menjadikan RANDAO tidak berat sebelah ialah ini: selepas semua nombor didedahkan dan XOR dikira, hasilnya dimasukkan ke dalam input fungsi, yang mengambil masa yang sangat lama untuk mengira, tetapi membolehkan anda menyemak ketepatan pengiraan sangat cepat.

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

Fungsi ini dipanggil Verifiable Delay Function, atau VDF. Jika pengiraan keputusan akhir mengambil masa lebih lama daripada peringkat pendedahan nombor, maka penyerang tidak akan dapat meramalkan kesan menunjukkan atau menyembunyikan nombornya, dan oleh itu dia akan kehilangan peluang untuk mempengaruhi keputusan.

Membangunkan VDF yang baik adalah amat sukar. Terdapat beberapa kejayaan baru-baru ini, mis. ini и ini, yang menjadikan VDF lebih praktikal dalam amalan, dan Ethereum 2.0 merancang untuk menggunakan RANDAO dengan VDF sebagai sumber nombor rawak dalam jangka panjang. Selain daripada fakta bahawa pendekatan ini tidak dapat diramalkan dan tidak berat sebelah, ia mempunyai faedah tambahan untuk berdaya maju jika sekurang-kurangnya dua peserta tersedia di rangkaian (dengan mengandaikan protokol konsensus yang digunakan berdaya maju apabila berurusan dengan bilangan peserta yang begitu kecil).

Cabaran terbesar pendekatan ini ialah menyediakan VDF supaya peserta yang mempunyai perkakasan khusus yang sangat mahal tidak akan dapat mengira VDF sebelum fasa penemuan tamat. Sebaik-baiknya, algoritma sepatutnya mempunyai margin keselamatan yang ketara, katakan 10x. Rajah di bawah menunjukkan serangan oleh pelakon yang mempunyai ASIC khusus yang membolehkannya menjalankan VDF lebih cepat daripada masa yang diperuntukkan untuk mendedahkan pengesahan RANDAO. Peserta sedemikian masih boleh mengira keputusan akhir menggunakan atau tidak menggunakan nombornya, dan kemudian, berdasarkan pengiraan, pilih sama ada untuk menunjukkannya atau tidak.

Bagi keluarga VDF yang dinyatakan di atas, prestasi ASIC khusus boleh 100+ kali lebih tinggi daripada perkakasan konvensional. Jadi jika fasa penggunaan berlangsung selama 10 saat, maka VDF yang dikira pada ASIC sedemikian mesti mengambil masa lebih daripada 100 saat untuk mempunyai margin keselamatan 10x, dan dengan itu VDF yang sama yang dikira pada perkakasan komoditi mesti mengambil masa 100x 100 saat = ~3 jam.

Yayasan Ethereum merancang untuk menyelesaikan masalah ini dengan mencipta ASIC percuma yang tersedia untuk umum. Sebaik sahaja ini berlaku, semua protokol lain juga boleh memanfaatkan teknologi ini, tetapi sehingga itu pendekatan RANDAO+VDF tidak akan berdaya maju untuk protokol yang tidak boleh melabur dalam membangunkan ASIC mereka sendiri.

Banyak artikel, video dan maklumat lain tentang VDF telah dikumpulkan pada laman web ini.

Kami menggunakan kod pemadaman

Dalam bahagian ini, kita akan melihat protokol penjanaan nombor rawak yang menggunakan memadam kod. Ia boleh bertolak ansur sehingga ⅓ penyerang sambil kekal berdaya maju, dan membenarkan sehingga ⅔ penyerang wujud sebelum mereka boleh meramalkan atau mempengaruhi keputusan.

Idea utama protokol adalah seperti berikut. Untuk lebih mudah, andaikan terdapat 100 orang peserta. Marilah kita juga menganggap bahawa semua peserta secara tempatan mempunyai beberapa kunci peribadi, dan kunci awam semua peserta diketahui oleh semua peserta:

1. Setiap peserta secara tempatan menghasilkan rentetan yang panjang, memecahkannya kepada 67 bahagian, mencipta kod pemadaman untuk mendapatkan 100 perkongsian supaya mana-mana 67 cukup untuk memulihkan rentetan, memberikan setiap 100 bahagian kepada salah seorang peserta dan menyulitkannya dengan kunci awam peserta yang sama. Semua bahagian yang dikodkan kemudiannya diterbitkan.

2. Peserta menggunakan beberapa jenis konsensus untuk mencapai persetujuan mengenai set berkod daripada 67 peserta tertentu.

3. Setelah konsensus dicapai, setiap peserta mengambil bahagian yang dikodkan dalam setiap satu daripada 67 set yang disulitkan dengan kunci awam mereka, menyahsulit semua saham tersebut dan menerbitkan semua saham yang dinyahsulit tersebut.

4. Apabila 67 peserta telah melengkapkan langkah (3), semua set yang dipersetujui boleh dinyahkod sepenuhnya dan dibina semula kerana sifat kod pemadaman, dan nombor akhir boleh diperolehi sebagai XOR bagi baris awal yang peserta mulakan dengan (1) .

Protokol ini boleh ditunjukkan sebagai tidak berat sebelah dan tidak dapat diramalkan. Nombor rawak yang terhasil ditentukan selepas konsensus dicapai, tetapi tidak diketahui sesiapa sehingga ⅔ daripada peserta menyahkod bahagian yang disulitkan dengan kunci awam mereka. Oleh itu, nombor rawak ditentukan sebelum maklumat yang mencukupi untuk membina semula ia diterbitkan.

Apakah yang berlaku jika dalam langkah (1) salah seorang peserta menghantar bahagian yang dikodkan kepada peserta lain yang bukan kod pemadaman yang betul untuk beberapa rentetan? Tanpa perubahan tambahan, peserta yang berbeza sama ada tidak akan dapat memulihkan rentetan sama sekali, atau mereka akan memulihkan rentetan yang berbeza, yang akan menyebabkan peserta berbeza menerima nombor rawak yang berbeza. Untuk mengelakkan ini, anda boleh melakukan perkara berikut: setiap peserta, sebagai tambahan kepada saham yang dikodkan, juga mengira Pokok Merkla semua saham tersebut, dan menghantar setiap peserta kedua-dua bahagian yang dikodkan itu sendiri dan akar pokok merkle, dan bukti kemasukan bahagian dalam pokok merkle. Dalam konsensus dalam langkah (2), para peserta kemudiannya bukan sahaja bersetuju pada satu set set, tetapi pada satu set akar tertentu pokok tersebut (jika sesetengah peserta menyimpang dari protokol, dan menghantar akar pokok merkle yang berbeza kepada peserta yang berbeza, dan dua punca sedemikian ditunjukkan semasa konsensus, barisnya tidak termasuk dalam set hasil). Hasil daripada konsensus, kami akan mempunyai 67 baris yang dikodkan dan akar yang sepadan bagi pokok merkle supaya terdapat sekurang-kurangnya 67 peserta (tidak semestinya yang sama yang mencadangkan baris yang sepadan), yang bagi setiap 67 baris mempunyai mesej dengan bahagian kod pemadaman, dan bukti kejadian bahagian mereka dalam pokok yang sepadan pudar.

Apabila dalam langkah (4) peserta menguraikan 67 denyutan untuk rentetan tertentu dan cuba membina semula rentetan asal daripadanya, salah satu pilihan adalah mungkin:

1. Rentetan itu dipulihkan, dan jika ia kemudiannya dikodkan padam sekali lagi, dan pokok Merkle dikira untuk bahagian yang dikira secara tempatan, akarnya bertepatan dengan yang mana konsensus dicapai.

2. Baris dipulihkan, tetapi akar yang dikira secara tempatan tidak sepadan dengan yang telah dicapai konsensus.

3. Baris tidak dipulihkan.

Adalah mudah untuk menunjukkan bahawa jika pilihan (1) berlaku untuk sekurang-kurangnya seorang peserta di atas, maka pilihan (1) berlaku untuk semua peserta, dan sebaliknya, jika pilihan (2) atau (3) berlaku untuk sekurang-kurangnya seorang peserta, maka untuk semua peserta pilihan (2) atau (3) akan berlaku. Oleh itu, untuk setiap baris dalam set, sama ada semua peserta akan berjaya memulihkannya, atau semua peserta akan gagal memulihkannya. Nombor rawak yang terhasil kemudiannya ialah XOR daripada hanya baris yang peserta dapat pulihkan.

Tandatangan ambang

Satu lagi pendekatan untuk rawak ialah menggunakan apa yang dipanggil tandatangan ambang BLS. Penjana nombor rawak berdasarkan tandatangan ambang mempunyai jaminan yang sama seperti algoritma berasaskan kod pemadaman yang diterangkan di atas, tetapi mempunyai bilangan mesej asimptotik yang jauh lebih rendah yang dihantar melalui rangkaian untuk setiap nombor yang dijana.

Tandatangan BLS ialah reka bentuk yang membolehkan berbilang peserta membuat satu tandatangan biasa untuk mesej. Tandatangan ini sering digunakan untuk menjimatkan ruang dan lebar jalur dengan tidak memerlukan beberapa tandatangan untuk dihantar. 

Aplikasi biasa untuk tandatangan BLS dalam protokol blockchain, selain menjana nombor rawak, ialah menandatangani blok dalam protokol BFT. Katakan 100 peserta membuat blok dan satu blok dianggap muktamad jika 67 daripada mereka menandatanganinya. Mereka semua boleh menyerahkan bahagian tandatangan BLS mereka dan menggunakan beberapa algoritma konsensus untuk bersetuju dengan 67 daripadanya dan kemudian menggabungkannya menjadi satu tandatangan BLS. Mana-mana 67 (atau lebih) bahagian boleh digunakan untuk mencipta tandatangan akhir, yang bergantung pada 67 tandatangan yang digabungkan dan oleh itu mungkin berbeza-beza, walaupun pilihan yang berbeza oleh 67 peserta akan mencipta tandatangan yang berbeza , mana-mana tandatangan sedemikian akan menjadi sah tandatangan untuk blok tersebut. Peserta yang tinggal kemudian hanya perlu menerima dan mengesahkan hanya satu tandatangan bagi setiap blok, bukannya 67, melalui rangkaian, yang mengurangkan beban pada rangkaian dengan ketara.

Ternyata jika kunci persendirian yang digunakan oleh peserta dijana dengan cara tertentu, maka tidak kira 67 tandatangan (atau lebih, tetapi tidak kurang) diagregatkan, tandatangan yang terhasil adalah sama. Ini boleh digunakan sebagai sumber rawak: peserta mula-mula bersetuju dengan beberapa mesej yang akan mereka tandatangani (ini mungkin keluaran RANDAO atau hanya cincangan blok terakhir, ia tidak begitu penting selagi ia berubah setiap kali dan konsisten) dan cipta tandatangan BLS untuknya. Hasil penjanaan tidak dapat diramalkan sehingga 67 peserta menyediakan bahagian mereka, dan selepas itu output sudah ditetapkan dan tidak boleh bergantung kepada tindakan mana-mana peserta.

Pendekatan kepada rawak ini berdaya maju selagi sekurang-kurangnya ⅔ daripada peserta dalam talian kedua-duanya mengikut protokol, dan tidak berat sebelah dan tidak dapat diramalkan selagi sekurang-kurangnya ⅓ peserta mengikuti protokol. Adalah penting untuk ambil perhatian bahawa penyerang yang mengawal lebih daripada ⅓ tetapi kurang daripada ⅔ peserta boleh menghentikan protokol, tetapi tidak boleh meramal atau mempengaruhi outputnya.

Tandatangan ambang itu sendiri adalah topik yang sangat menarik. Dalam bahagian kedua artikel, kami akan menganalisis secara terperinci cara ia berfungsi, dan bagaimana sebenarnya ia perlu untuk menjana kunci peserta supaya tandatangan ambang boleh digunakan sebagai penjana nombor rawak.

Kesimpulannya

Artikel ini adalah yang pertama dalam siri artikel blog teknikal NEAR. NEAR ialah protokol dan platform blockchain untuk membangunkan aplikasi terdesentralisasi dengan penekanan pada kemudahan pembangunan dan kemudahan penggunaan untuk pengguna akhir.

Kod protokol dibuka, pelaksanaan kami ditulis dalam Rust, ia boleh didapati di sini.

Anda boleh melihat rupa pembangunan untuk NEAR dan mencuba dalam IDE dalam talian di sini.

Anda boleh mengikuti semua berita dalam bahasa Rusia di kumpulan telegram dan kumpulan di VKontakte, dan dalam bahasa Inggeris dalam rasmi twitter.

Jumpa lagi!

Sumber: www.habr.com