Apakah mungkin menghasilkan angka acak jika kita tidak percaya satu sama lain? Bagian 1

Hei Habr!

Pada artikel kali ini saya akan membahas tentang pembangkitan bilangan pseudo-acak oleh partisipan yang tidak saling percaya. Seperti yang akan kita lihat di bawah, mengimplementasikan generator yang “hampir” bagus cukup sederhana, namun membuat generator yang sangat bagus itu sulit.

Mengapa perlu menghasilkan angka acak di antara peserta yang tidak percaya satu sama lain? Salah satu area aplikasi adalah aplikasi terdesentralisasi. Misalnya, aplikasi yang menerima taruhan dari seorang peserta dan menggandakan jumlahnya dengan probabilitas 49% atau menghapus taruhan dengan probabilitas 51% hanya akan berfungsi jika aplikasi tersebut dapat menerima nomor acak secara tidak memihak. Jika seorang penyerang dapat mempengaruhi hasil dari generator nomor acak, dan bahkan sedikit meningkatkan peluangnya untuk menerima pembayaran dalam aplikasi, dia akan dengan mudah menghancurkannya.

Saat kami merancang protokol pembuatan nomor acak terdistribusi, kami ingin protokol tersebut memiliki tiga properti:

1. Dia harus tidak memihak. Dengan kata lain, tidak ada peserta yang boleh mempengaruhi hasil generator nomor acak dengan cara apa pun.

2. Dia pasti tidak bisa ditebak. Dengan kata lain, tidak ada peserta yang dapat memprediksi angka apa yang akan dihasilkan (atau menyimpulkan propertinya) sebelum angka tersebut dihasilkan.

3. Protokol tersebut harus dapat dijalankan, yaitu tahan terhadap kenyataan bahwa persentase tertentu peserta memutuskan sambungan dari jaringan atau dengan sengaja mencoba menghentikan protokol.

Pada artikel ini kita akan melihat dua pendekatan: RANDAO + VDF dan pendekatan kode penghapusan. Pada bagian selanjutnya, kita akan mengkaji secara rinci pendekatan berdasarkan tanda ambang batas.

Namun pertama-tama, mari kita lihat algoritma sederhana dan umum digunakan yang dapat dijalankan, tidak dapat diprediksi, namun bias.

RANDAO

RANDAO adalah pendekatan yang sangat sederhana dan oleh karena itu cukup umum digunakan untuk menghasilkan keacakan. Semua peserta jaringan terlebih dahulu memilih nomor pseudorandom secara lokal, kemudian setiap peserta mengirimkan hash dari nomor yang dipilih. Selanjutnya peserta secara bergiliran mengungkapkan nomor pilihannya dan melakukan operasi XOR pada nomor yang terungkap tersebut, dan hasil operasi tersebut menjadi hasil protokol.

Langkah mempublikasikan hash sebelum mengungkapkan nomor tersebut diperlukan agar penyerang tidak dapat memilih nomornya setelah ia melihat nomor peserta lainnya. Ini akan memungkinkan dia untuk menentukan sendiri output dari generator nomor acak.

Selama berlangsungnya protokol, peserta harus mengambil keputusan bersama (yang disebut konsensus) dua kali: kapan mulai mengungkapkan nomor yang dipilih, dan karena itu berhenti menerima hash, dan kapan harus berhenti menerima nomor yang dipilih dan menghitung hasil acak yang dihasilkan. nomor. Membuat keputusan antara peserta yang tidak percaya satu sama lain bukanlah tugas yang mudah, dan kami akan membahasnya kembali di artikel mendatang; dalam artikel ini kami akan berasumsi bahwa algoritma konsensus seperti itu tersedia bagi kami.

Manakah dari properti yang kami jelaskan di atas yang dimiliki RANDAO? Hal ini tidak dapat diprediksi, memiliki vitalitas yang sama dengan protokol konsensus yang mendasarinya, namun bersifat bias. Secara khusus, penyerang dapat mengamati jaringan, dan setelah peserta lain mengungkapkan nomor mereka, ia dapat menghitung XOR mereka, dan memutuskan apakah akan mengungkapkan nomornya atau tidak untuk mempengaruhi hasilnya. Meskipun hal ini mencegah penyerang untuk menentukan keluaran generator angka acak sendirian, hal ini tetap memberinya 1 sedikit pengaruh. Dan jika penyerang mengendalikan beberapa peserta, maka jumlah bit yang mereka kendalikan akan sama dengan jumlah peserta yang dikendalikannya.

Pengaruh penyerang dapat sangat dikurangi dengan mengharuskan peserta mengungkapkan angka-angkanya secara berurutan. Kemudian penyerang akan dapat mempengaruhi hasilnya hanya jika dibuka terakhir kali. Meskipun pengaruhnya jauh lebih kecil, algoritmenya masih bias.

RANDAO+VDF

Salah satu cara untuk membuat RANDAO tidak bias adalah dengan cara ini: setelah semua angka terungkap dan XOR dihitung, hasilnya dimasukkan ke dalam input suatu fungsi, yang membutuhkan waktu sangat lama untuk menghitungnya, namun memungkinkan Anda memeriksa kebenarannya. perhitungan dengan sangat cepat.

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

Fungsi ini disebut Fungsi Penundaan yang Dapat Diverifikasi, atau VDF. Jika penghitungan hasil akhir memakan waktu lebih lama dari tahap pengungkapan angka, maka penyerang tidak akan dapat memprediksi efek menampilkan atau menyembunyikan nomornya, dan oleh karena itu ia akan kehilangan kesempatan untuk mempengaruhi hasil.

Mengembangkan VDF yang baik sangatlah sulit. Ada beberapa terobosan baru-baru ini, misalnya. ini и ini, yang membuat VDF lebih praktis dalam praktiknya, dan Ethereum 2.0 berencana menggunakan RANDAO dengan VDF sebagai sumber nomor acak dalam jangka panjang. Terlepas dari kenyataan bahwa pendekatan ini tidak dapat diprediksi dan tidak memihak, pendekatan ini mempunyai manfaat tambahan karena pendekatan ini dapat dilaksanakan jika setidaknya ada dua peserta yang tersedia di jaringan (dengan asumsi protokol konsensus yang digunakan dapat dijalankan ketika menangani sejumlah kecil peserta).

Tantangan terbesar dari pendekatan ini adalah menyiapkan VDF sedemikian rupa sehingga peserta dengan perangkat keras khusus yang sangat mahal pun tidak akan dapat menghitung VDF sebelum akhir fase penemuan. Idealnya, algoritme tersebut harus memiliki margin keamanan yang signifikan, katakanlah 10x. Gambar di bawah menunjukkan serangan oleh aktor yang memiliki ASIC khusus yang memungkinkan dia menjalankan VDF lebih cepat dari waktu yang dialokasikan untuk mengungkapkan konfirmasi RANDAO. Peserta tersebut tetap dapat menghitung hasil akhir dengan menggunakan atau tidak menggunakan nomornya, kemudian berdasarkan perhitungan tersebut, memilih untuk menampilkannya atau tidak.

Untuk keluarga VDF yang disebutkan di atas, kinerja ASIC khusus bisa 100+ kali lebih tinggi dibandingkan perangkat keras konvensional. Jadi jika fase penerapan berlangsung selama 10 detik, maka VDF yang dihitung pada ASIC tersebut harus memerlukan waktu lebih dari 100 detik untuk mendapatkan margin keamanan 10x, sehingga VDF yang sama yang dihitung pada perangkat keras komoditas harus memerlukan waktu 100x 100 detik = ~3 jam.

Ethereum Foundation berencana untuk memecahkan masalah ini dengan membuat ASIC gratis yang tersedia untuk umum. Jika hal ini terjadi, semua protokol lain juga dapat memanfaatkan teknologi ini, namun hingga saat itu, pendekatan RANDAO+VDF tidak akan dapat diterapkan untuk protokol yang tidak dapat berinvestasi dalam mengembangkan ASIC mereka sendiri.

Banyak artikel, video dan informasi lainnya tentang VDF telah dikumpulkan situs ini.

Kami menggunakan kode penghapusan

Pada bagian ini, kita akan melihat protokol pembuatan angka acak yang digunakan menghapus kode. Ia dapat menoleransi hingga ⅓ penyerang namun tetap dapat bertahan, dan memungkinkan hingga ⅔ penyerang ada sebelum mereka dapat memprediksi atau mempengaruhi hasilnya.

Ide utama dari protokol ini adalah sebagai berikut. Untuk mempermudah, asumsikan ada tepat 100 peserta. Mari kita asumsikan juga bahwa semua partisipan secara lokal mempunyai beberapa kunci privat, dan kunci publik dari semua partisipan diketahui oleh semua partisipan:

1. Masing-masing peserta secara lokal membuat string yang panjang, memecahnya menjadi 67 bagian, membuat kode penghapusan untuk mendapatkan 100 bagian sehingga 67 bagian mana pun cukup untuk memulihkan string, menugaskan masing-masing dari 100 bagian tersebut ke salah satu peserta, dan mengenkripsinya dengan kunci publik peserta yang sama. Semua saham yang dikodekan kemudian diterbitkan.

2. Peserta menggunakan semacam konsensus untuk mencapai kesepakatan mengenai kumpulan kode dari 67 peserta tertentu.

3. Setelah konsensus tercapai, setiap peserta mengambil bagian yang dikodekan di masing-masing dari 67 set yang dienkripsi dengan kunci publik mereka, mendekripsi semua bagian tersebut, dan menerbitkan semua bagian yang didekripsi tersebut.

4. Setelah 67 peserta menyelesaikan langkah (3), semua set yang disepakati dapat sepenuhnya didekodekan dan direkonstruksi karena sifat kode penghapusan, dan angka akhir dapat diperoleh sebagai XOR dari baris awal yang dimulai oleh peserta di (1) .

Protokol ini terbukti tidak memihak dan tidak dapat diprediksi. Nomor acak yang dihasilkan ditentukan setelah konsensus tercapai, namun tidak diketahui siapa pun sampai ⅔ peserta memecahkan kode bagian yang dienkripsi dengan kunci publik mereka. Dengan demikian, nomor acak ditentukan sebelum informasi yang cukup untuk merekonstruksinya dipublikasikan.

Apa yang terjadi jika pada langkah (1) salah satu peserta mengirimkan bagian yang dikodekan ke peserta lain yang bukan kode penghapusan yang benar untuk beberapa string? Tanpa perubahan tambahan, peserta yang berbeda tidak akan dapat memulihkan string sama sekali, atau mereka akan memulihkan string yang berbeda, sehingga peserta yang berbeda akan menerima nomor acak yang berbeda. Untuk mencegah hal ini, Anda dapat melakukan hal berikut: setiap peserta, selain bagian yang dikodekan, juga menghitung Pohon Merkla semua bagian tersebut, dan mengirimkan kepada setiap peserta baik bagian yang dikodekan itu sendiri maupun akar pohon merkle, dan bukti pencantuman bagian tersebut dalam pohon merkle. Pada konsensus pada langkah (2), para peserta kemudian tidak hanya menyepakati satu set set, namun pada satu set akar spesifik dari pohon tersebut (jika ada peserta yang menyimpang dari protokol, dan mengirimkan akar pohon merkle yang berbeda ke peserta yang berbeda, dan dua akar tersebut ditampilkan selama konsensus, barisnya tidak termasuk dalam kumpulan hasil). Sebagai hasil dari konsensus tersebut, kita akan memiliki 67 baris yang dikodekan dan akar pohon merkle yang bersesuaian sedemikian rupa sehingga setidaknya ada 67 peserta (tidak harus sama dengan yang mengusulkan baris yang sesuai), yang untuk masing-masing dari 67 baris tersebut memiliki pesan dengan bagian kode penghapusan, dan bukti kemunculan bagiannya di pohon terkait memudar.

Ketika pada langkah (4) peserta menguraikan 67 ketukan untuk string tertentu dan mencoba merekonstruksi string asli darinya, salah satu opsi yang mungkin:

1. String dipulihkan, dan jika kemudian dikodekan kembali dengan penghapusan, dan pohon Merkle dihitung untuk bagian yang dihitung secara lokal, akarnya bertepatan dengan akar yang menjadi dasar konsensus dicapai.

2. Baris tersebut dipulihkan, tetapi akar yang dihitung secara lokal tidak sesuai dengan akar yang dicapai konsensus.

3. Baris tersebut tidak dipulihkan.

Mudah untuk ditunjukkan bahwa jika pilihan (1) terjadi pada paling sedikit satu peserta di atas, maka pilihan (1) terjadi pada semua peserta, dan sebaliknya, jika pilihan (2) atau (3) terjadi pada paling sedikit satu peserta, maka untuk semua peserta opsi (2) atau (3) akan terjadi. Jadi, untuk setiap baris dalam set, semua peserta akan berhasil memulihkannya, atau semua peserta akan gagal memulihkannya. Nomor acak yang dihasilkan kemudian merupakan XOR dari hanya baris yang dapat dipulihkan oleh peserta.

Tanda tangan ambang batas

Pendekatan lain terhadap keacakan adalah dengan menggunakan apa yang disebut tanda ambang batas BLS. Generator nomor acak berdasarkan tanda ambang batas memiliki jaminan yang persis sama dengan algoritma berbasis kode penghapusan yang dijelaskan di atas, namun memiliki jumlah pesan asimtotik yang jauh lebih rendah yang dikirim melalui jaringan untuk setiap nomor yang dihasilkan.

Tanda tangan BLS adalah desain yang memungkinkan banyak peserta membuat satu tanda tangan umum untuk sebuah pesan. Tanda tangan ini sering digunakan untuk menghemat ruang dan bandwidth dengan tidak memerlukan banyak tanda tangan untuk dikirim. 

Penerapan umum untuk tanda tangan BLS dalam protokol blockchain, selain menghasilkan nomor acak, adalah penandatanganan blok dalam protokol BFT. Katakanlah 100 peserta membuat blok, dan sebuah blok dianggap final jika 67 peserta menandatanganinya. Mereka semua dapat mengirimkan bagian mereka dari tanda tangan BLS dan menggunakan beberapa algoritma konsensus untuk menyetujui 67 bagian dari tanda tangan tersebut dan kemudian menggabungkannya menjadi satu tanda tangan BLS. 67 (atau lebih) bagian apa pun dapat digunakan untuk membuat tanda tangan akhir, yang akan bergantung pada 67 tanda tangan mana yang digabungkan dan oleh karena itu dapat bervariasi, meskipun pilihan yang berbeda dari 67 peserta akan menghasilkan tanda tangan yang berbeda, tanda tangan tersebut akan sah tanda tangan untuk blok tersebut. Peserta yang tersisa kemudian hanya perlu menerima dan memverifikasi satu tanda tangan per blok, bukan 67, melalui jaringan, yang secara signifikan mengurangi beban pada jaringan.

Ternyata jika kunci privat yang digunakan peserta dibuat dengan cara tertentu, maka tidak peduli 67 tanda tangan mana (atau lebih, tapi tidak kurang) yang dikumpulkan, tanda tangan yang dihasilkan akan tetap sama. Hal ini dapat digunakan sebagai sumber keacakan: peserta terlebih dahulu menyepakati beberapa pesan yang akan mereka tandatangani (ini bisa berupa output dari RANDAO atau hanya hash dari blok terakhir, tidak masalah asalkan berubah setiap saat. dan konsisten) dan buat tanda tangan BLS untuknya. Hasil dari pembangkitan tersebut tidak dapat diprediksi sampai 67 peserta memberikan bagiannya, dan setelah itu keluarannya sudah ditentukan sebelumnya dan tidak dapat bergantung pada tindakan peserta manapun.

Pendekatan keacakan ini dapat dilakukan selama setidaknya ⅔ peserta daring mengikuti protokol, dan tidak memihak serta tidak dapat diprediksi selama setidaknya ⅓ peserta mengikuti protokol. Penting untuk dicatat bahwa penyerang yang mengendalikan lebih dari ⅓ tetapi kurang dari ⅔ peserta dapat menghentikan protokol, namun tidak dapat memprediksi atau mempengaruhi keluarannya.

Tanda tangan ambang batas sendiri merupakan topik yang sangat menarik. Di bagian kedua artikel, kami akan menganalisis secara rinci cara kerjanya, dan bagaimana tepatnya kunci peserta perlu dibuat agar tanda tangan ambang batas dapat digunakan sebagai penghasil angka acak.

Sebagai kesimpulan

Artikel ini adalah yang pertama dari serangkaian artikel blog teknis NEAR. NEAR adalah protokol dan platform blockchain untuk mengembangkan aplikasi terdesentralisasi dengan penekanan pada kemudahan pengembangan dan kemudahan penggunaan bagi pengguna akhir.

Kode protokol terbuka, implementasi kami ditulis dalam Rust, dapat ditemukan di sini.

Anda dapat melihat seperti apa pengembangan NEAR dan bereksperimen di IDE online di sini.

Anda dapat mengikuti semua berita dalam bahasa Rusia di grup telegram и в grup di VKontakte, dan dalam bahasa Inggris secara resmi Indonesia.

Sampai berjumpa lagi!

Sumber: www.habr.com