Pendahuluan

function getAbsolutelyRandomNumer() { return 4; // returns absolutely random number! } 

Seperti dalam kasus konsep sandi kriptografi yang benar-benar aman, protokol Random Beacon acak yang dapat diverifikasi secara publik (selanjutnya disebut PVRB) hanya berusaha sedekat mungkin dengan skema ideal. dalam jaringan nyata dalam bentuknya yang murni, itu tidak berlaku: perlu untuk menyetujui sepenuhnya pada satu bit, harus ada banyak putaran, dan semua pesan harus sangat cepat dan selalu disampaikan. Tentu saja, dalam jaringan nyata ini tidak demikian. Oleh karena itu, ketika mendesain PVRB untuk tugas-tugas spesifik dalam blockchain modern, selain ketidakmampuan untuk mengontrol keacakan dan kekuatan kriptografi yang dihasilkan, banyak masalah arsitektur dan teknis murni muncul.

Blockchain itu sendiri untuk PVRB pada dasarnya merupakan media komunikasi di mana pesan = transaksi. Ini memungkinkan Anda untuk mengabaikan sebagian masalah jaringan, pengiriman pesan, masalah middleware - semua risiko ini ditanggung oleh jaringan yang didesentralisasi, dan nilai utamanya untuk PVRB adalah ketidakmampuan untuk menarik atau merusak transaksi yang sudah dikirim - ini tidak memungkinkan peserta untuk menolak berpartisipasi dalam protokol, kecuali mereka memiliki serangan konsensus yang berhasil. Tingkat keamanan ini dapat diterima, jadi PVRB harus tahan terhadap kolusi di antara para peserta dengan cara yang persis sama dengan rantai blockchain utama. Juga, ini mengisyaratkan bahwa PVRB harus menjadi bagian dari konsensus, jika jaringan menyetujui rantai blok utama, biarkan ia setuju pada saat yang sama pada satu-satunya hasil acak yang jujur. Atau, PVRB hanyalah protokol mandiri yang diimplementasikan oleh kontrak pintar yang bekerja secara serempak sehubungan dengan blockchain dan blok. Kedua metode memiliki kelebihan dan kekurangan masing-masing, dan pilihan di antara keduanya sangat tidak penting.

Dua cara untuk mengimplementasikan PVRB

Mari kita jelaskan secara lebih rinci dua opsi untuk mengimplementasikan PVRB: versi mandiri, yang berfungsi menggunakan kontrak pintar yang independen dari blockchain, dan terintegrasi dengan konsensus, yang dibangun ke dalam protokol yang dengannya jaringan menyetujui rantai blok dan termasuk transaksi. Dalam semua kasus, saya akan mengingat mesin blockchain yang populer: Ethereum, EOS, dan semuanya mirip dengan mereka dalam cara menempatkan dan memproses kontrak pintar.

Kontrak mandiri

Dalam perwujudan ini, PVRB adalah kontrak pintar yang menerima transaksi produsen acak (selanjutnya RP), memprosesnya, menggabungkan hasilnya, dan, sebagai hasilnya, mencapai nilai yang dapat diperoleh setiap pengguna dari kontrak ini. Nilai ini mungkin tidak disimpan secara langsung dalam kontrak, tetapi hanya diwakili oleh data dari mana satu dan hanya satu nilai dari keacakan yang dihasilkan dapat ditentukan secara deterministik. Dalam skema ini, RP adalah pengguna blockchain, dan siapa saja dapat berpartisipasi dalam proses pembuatan.

Opsi kontrak mandiri baik:

• portabilitas (kontrak dapat diseret dari blockchain ke blockchain)
• kesederhanaan dalam implementasi dan pengujian (kontrak mudah untuk menulis dan menguji)
• kenyamanan dalam mengimplementasikan skema ekonomi (mudah untuk membuat token Anda sendiri, yang logikonya melayani tujuan PVRB)
• kemampuan untuk berjalan di blockchains yang ada

Ini juga memiliki kelemahan:

• keterbatasan kuat pada sumber daya dalam perhitungan, volume transaksi dan penyimpanan (dengan kata lain, cpu / mem / io)
• pembatasan operasi dalam kontrak (tidak semua instruksi tersedia, sulit untuk menghubungkan perpustakaan eksternal)
• ketidakmampuan untuk mengatur pengiriman pesan lebih cepat daripada transaksi termasuk dalam blockchain

Opsi ini cocok untuk menerapkan PVRB, yang harus dijalankan pada jaringan yang ada yang tidak mengandung kriptografi kompleks dan tidak memerlukan sejumlah besar interaksi.

Terintegrasi-konsensus

Dalam perwujudan ini, PVRB diimplementasikan dalam kode node blockchain, built-in, atau bekerja secara paralel dengan pertukaran pesan antara node blockchain. Hasil protokol ditulis langsung ke blok yang dihasilkan, dan pesan protokol dikirim melalui jaringan p2p antara node. Karena protokol menghasilkan angka-angka yang ditulis dalam blok, jaringan harus mencapai konsensus tentangnya. Ini berarti bahwa pesan PVRB, serta transaksi, harus divalidasi oleh node dan dimasukkan dalam blok sehingga setiap peserta jaringan dapat memverifikasi kepatuhan dengan protokol PVRB. Ini secara otomatis membawa kita pada keputusan yang jelas - jika jaringan menegosiasikan konsensus tentang blok dan transaksi di dalamnya, maka PVRB harus menjadi bagian dari konsensus, bukan protokol yang berdiri sendiri. Kalau tidak, suatu situasi dimungkinkan di mana blok tersebut valid dari sudut pandang konsensus, tetapi protokol PVRB tidak dihormati, dan dari sudut pandang PVRB blok tidak dapat diterima. Jadi jika opsi "terintegrasi konsensus" dipilih, PVRB menjadi bagian penting dari konsensus.

Menjelaskan implementasi PVRB pada tingkat konsensus pada jaringan, dalam hal apa pun Anda tidak dapat melewati masalah finalitas. Finalitas adalah mekanisme yang digunakan dalam konsensus deterministik, blok pengunci (dan rantai yang mengarah ke sana) yang final dan tidak akan pernah dibuang meskipun garpu paralel muncul. Misalnya, tidak ada mekanisme seperti itu dalam Bitcoin - jika Anda mempublikasikan rantai kompleksitas yang lebih besar, itu akan menggantikan mekanisme yang kurang kompleks, terlepas dari panjang rantai tersebut. Dan dalam EOS, misalnya, yang terakhir adalah yang disebut Blok Terakhir yang Tidak Dapat Dibalik, yang muncul rata-rata setiap 432 blok (12 * 21 + 12 * 15, pra-pemilihan + pra-komit). Proses ini pada dasarnya menunggu 2/3 dari tanda tangan produsen blok (selanjutnya disebut BP). Ketika garpu yang lebih tua dari LIB terakhir muncul, mereka hanya dibuang. Mekanisme ini memungkinkan Anda untuk menjamin bahwa transaksi termasuk dalam blockchain dan tidak akan pernah dipompa keluar, apa pun sumber daya yang dimiliki penyerang. Juga, blok terakhir adalah blok yang ditandatangani oleh 2/3 BP dalam Hyperledger, Tendermint dan konsensus berbasis pBFT lainnya. Juga, protokol untuk memastikan finalitas masuk akal untuk membuat add-on pada konsensus, karena dapat bekerja secara tidak serempak dengan produksi dan publikasi blok. Inilah artikel yang bagus tentang finalisasi Ethereum.

Finalitas sangat penting bagi pengguna yang, tanpa itu, mungkin menjadi korban serangan "pembelanjaan ganda" ketika BP "menahan" blok dan menerbitkannya setelah jaringan "melihat" transaksi yang baik. Jika tidak ada finalitas, maka garpu yang diterbitkan menggantikan blok dengan transaksi "baik" dengan yang lain, dari garpu "buruk", di mana dana yang sama ditransfer ke alamat penyerang. Dalam kasus PVRB, persyaratan untuk finalitas masih diperketat, karena pembangunan garpu untuk PVRB berarti bahwa penyerang dapat menyiapkan beberapa opsi untuk rumah acak untuk menerbitkan yang paling menguntungkan baginya, dan membatasi waktu serangan yang mungkin adalah solusi yang baik.

Oleh karena itu, pilihan terbaik adalah menggabungkan PVRB dan finalitas dalam satu protokol - maka blok yang difinalisasi = diselesaikan secara acak, dan inilah yang harus Anda dapatkan. Sekarang pemain akan menerima keacakan dijamin dalam N detik, dan mereka dapat yakin bahwa tidak mungkin untuk memutar kembali atau memutar ulang itu.

Opsi yang terintegrasi dengan konsensus baik:

• kemungkinan implementasi asinkron sehubungan dengan produksi blok - blok diproduksi seperti biasa, tetapi secara paralel dengan ini, protokol PVRB dapat bekerja, yang tidak membuat setiap blok acak
• kemampuan untuk mengimplementasikan kriptografi yang berat, tanpa batasan yang dikenakan pada kontrak yang cerdas
• kemampuan untuk mengatur pengiriman pesan lebih cepat daripada transaksi yang termasuk dalam blockchain, misalnya, bagian dari protokol dapat bekerja di antara node tanpa menyebarkan pesan melalui jaringan

Ini juga memiliki kelemahan:

• kesulitan dalam pengujian dan pengembangan - Anda harus meniru kesalahan jaringan, hilang node, garpu jaringan keras
• kesalahan implementasi memerlukan jaringan garpu keras

Kedua metode implementasi PVRB memiliki hak untuk hidup, tetapi implementasi kontrak pintar pada blockchain modern masih sangat terbatas dalam sumber daya komputasi, dan setiap transisi ke kriptografi serius seringkali tidak mungkin dilakukan. Kita akan memerlukan kriptografi serius, seperti yang akan ditunjukkan nanti. Meskipun masalah ini jelas bersifat sementara, kriptografi serius dalam kontrak diperlukan untuk menyelesaikan banyak masalah, dan secara bertahap muncul (misalnya, kontrak sistem untuk zkSNARKs di Ethereum)

Blockchain, yang menyediakan saluran pesan protokol yang transparan dan andal, melakukan ini karena suatu alasan. Setiap protokol yang didesentralisasi harus memperhitungkan kemungkinan serangan Sybil, tindakan apa pun dapat dilakukan oleh pasukan terkoordinasi dari banyak akun, oleh karena itu, ketika merancang, perlu memperhitungkan kemampuan penyerang untuk membuat jumlah peserta protokol yang sewenang-wenang bertindak dalam kolusi.

PVRB dan blok variabel.

Saya tidak berbohong ketika saya mengatakan bahwa sejauh ini tidak ada yang menerapkan PVRB yang baik, diverifikasi oleh banyak aplikasi perjudian, di blockchains. Di mana, kemudian, dari begitu banyak aplikasi perjudian di Ethereum dan EOS? Itu mengejutkan saya seperti halnya Anda, yah, dari mana Anda mendapatkan begitu banyak angka acak "persisten" dari dalam lingkungan yang sepenuhnya deterministik?

Cara favorit untuk mendapatkan acak di blockchain adalah dengan mengambil beberapa jenis informasi yang "tidak dapat diprediksi" dari blok tersebut, dan berdasarkan itu untuk melakukan secara acak - cukup cache satu atau lebih nilai. Artikel bagus tentang masalah skema semacam itu di sini . Anda dapat mengambil beberapa nilai "tak terduga" di blok, misalnya, hash blok, jumlah transaksi, kompleksitas jaringan, dan nilai-nilai lain yang tidak diketahui sebelumnya. Kemudian cache mereka, satu atau lebih, dan, secara teori, Anda harus mendapatkan acak nyata. Anda bahkan dapat menambahkan ke wihitepaper bahwa skema Anda adalah "post-quantum secure" (karena ada fungsi hash bukti-kuantum :)).

Tetapi bahkan hash aman pasca-kuantum tidak cukup, sayangnya. Rahasianya terletak pada persyaratan untuk PVRB, saya mengingatnya dari artikel sebelumnya:

1. Hasilnya harus memiliki distribusi yang terbukti seragam, yaitu berdasarkan kriptografi yang terbukti kuat.
2. Tidak mungkin untuk mengontrol bit dari hasilnya. Akibatnya, hasilnya tidak dapat diprediksi sebelumnya.
3. Anda tidak dapat menyabotase protokol pembuatan dengan tidak berpartisipasi dalam protokol atau dengan membebani jaringan dengan pesan serangan
4. Semua hal di atas harus tahan terhadap kolusi jumlah peserta tidak jujur ​​yang diizinkan dalam protokol (misalnya, 1/3 dari peserta).

Dalam hal ini, hanya persyaratan 1 yang dipenuhi, dan 2. tidak terpenuhi. Memukul nilai yang tidak terduga dari blok, kami mendapatkan distribusi yang seragam dan keacakan yang baik. Tetapi BP setidaknya memiliki kemampuan untuk "menerbitkan blok atau tidak." Dengan demikian, BP setidaknya dapat memilih dari dua pilihan untuk keacakan: "milik kita" dan yang akan berubah jika orang lain membuat blok. BP dapat "memata-matai" terlebih dahulu apa yang terjadi jika menerbitkan blok, dan hanya memutuskan untuk melakukannya atau tidak. Jadi, bermain misalnya "odd-even" atau "red / black" dalam roulette, ia dapat menerbitkan blok hanya jika ia melihat kemenangan. Ini juga membuat strategi tidak beroperasi untuk menggunakan, misalnya, hash blok dari masa depan. Dalam hal ini, mereka mengatakan bahwa "acak akan digunakan, yang diperoleh dengan hashing data saat ini dan hash dari blok masa depan dengan tinggi, misalnya, N + 42, di mana N adalah tinggi blok saat ini. Ini sedikit memperkuat skema, tetapi masih memungkinkan BP, meskipun di masa depan, untuk memilih, menahan blok atau menerbitkan.

BP lunak dalam hal ini rumit, tetapi tidak banyak. Hanya saja ketika memvalidasi dan memasukkan transaksi dalam blok, pemeriksaan cepat dilakukan untuk melihat apakah akan ada keuntungan, dan, mungkin, pemilihan satu parameter transaksi untuk mendapatkan probabilitas tinggi untuk menang. Pada saat yang sama, menangkap BP cerdas, untuk manipulasi semacam itu hampir tidak mungkin, setiap kali Anda dapat menggunakan alamat baru, dan memenangkan sedikit, tanpa menimbulkan kecurigaan.

Jadi metode yang menggunakan informasi dari blok tidak cocok untuk peran implementasi universal PVRB. Dalam versi terbatas, dengan batasan ukuran taruhan, batasan jumlah pemain dan / atau registrasi KYC (untuk mencegah satu pemain menggunakan banyak alamat), skema ini dapat bekerja untuk permainan kecil, tetapi tidak lebih.

PVRB dan komit-ungkapkan.

Oke, terima kasih untuk hashing dan paling tidak ketidakpastian relatif dari hash blok dan variabel lainnya. Jika Anda memecahkan masalah penambang yang beroperasi di depan, Anda harus mendapatkan sesuatu yang lebih cocok. Mari kita tambahkan pengguna ke skema ini - meskipun mereka juga mempengaruhi keacakan: setiap orang dukungan teknis akan memberi tahu Anda bahwa hal yang paling acak dalam sistem TI adalah tindakan pengguna :)

Skema naif, ketika pengguna hanya mengirim angka acak, dan hasilnya dihitung sebagai, misalnya, hash dari jumlah mereka, tidak cocok. Dalam hal ini, pemain terakhir dapat memilih kontrol acaknya sendiri tentang apa hasilnya nanti. Oleh karena itu, pola commit-express yang sangat banyak digunakan digunakan. Peserta pertama-tama mengirim hash dari acak (komit) mereka, dan kemudian membuka acak sendiri. Fase "pengungkapan" dimulai hanya setelah komit yang diperlukan telah dikumpulkan, sehingga para peserta dapat mengirim secara acak dari mana mereka mengirim hash sebelumnya. Sekarang kita membutakan semua ini dengan parameter blok, dan itu lebih baik daripada yang diambil dari masa depan (Anda dapat mengetahui keacakan hanya di salah satu blok masa depan), dan voila - acak sudah siap! Sekarang, setiap pemain memengaruhi keacakan, dan dapat "mengalahkan" BP jahat dengan memblokirnya dengan acaknya sendiri, yang sebelumnya tidak diketahui, acak ... Anda juga dapat menambahkan perlindungan terhadap sabotase protokol dengan tidak membukanya pada tahap pengungkapan - hanya membutuhkan penerapan jumlah tertentu pada transaksi - setoran asuransi, yang akan dikembalikan hanya selama prosedur pengungkapan. Dalam hal ini, melakukan komit dan tidak melakukan mengungkapkan akan merugikan.

Itu adalah upaya yang baik, dan skema seperti itu juga ada dalam permainan DApps, tetapi sayangnya, ini sekali lagi tidak cukup. Sekarang, tidak hanya penambang, tetapi setiap peserta dalam protokol dapat memengaruhi hasilnya. Masih mungkin untuk mengontrol nilai itu sendiri, dengan tingkat variabilitas yang lebih rendah, dan untuk uang, tetapi, seperti dalam kasus penambang, jika hasil undian lebih berharga daripada biaya partisipasi dalam protokol PVRB, maka produsen acak (RP) dapat memutuskan apakah akan mengungkapkan dan masih dapat memilih dari setidaknya dua opsi acak.
Tetapi ada kesempatan untuk menghukum mereka yang melakukan dan tidak mengungkapkan, dan skema ini masih berguna. Kesederhanaannya adalah keuntungan utama - protokol yang lebih serius membutuhkan komputasi yang jauh lebih kuat.

PVRB dan tanda tangan deterministik.

Ada cara lain untuk mendapatkan RP untuk memberikan nomor pseudo-acak yang tidak dapat memengaruhi jika dilengkapi dengan "prototipe" —ini adalah tanda tangan deterministik. Tanda tangan seperti itu, misalnya, RSA, dan bukan ECS. Jika RP memiliki sepasang kunci: RSA dan ECC, dan ia menandatangani beberapa nilai dengan kunci pribadinya, maka dalam kasus RSA ia akan mendapatkan SATU DAN SATU-SATUNYA satu tanda tangan, dan dalam kasus ECS ia dapat menghasilkan sejumlah tanda tangan valid yang berbeda. Hal ini disebabkan oleh fakta bahwa ketika membuat tanda tangan ECS, nomor acak digunakan, dipilih oleh penandatangan, dan dapat dipilih sesuai keinginan, memberikan kesempatan kepada penanda tangan untuk memilih satu dari beberapa tanda tangan. Dalam kasus RSA: “satu nilai input” + “satu pasangan kunci” = “satu tanda tangan”. Tidak mungkin untuk memprediksi seperti apa tanda tangan RP lainnya, sehingga PVRB dengan tanda tangan deterministik dapat diatur dengan menggabungkan tanda tangan RSA dari beberapa peserta yang menandatangani nilai yang sama. Misalnya - acak sebelumnya. Dalam skema ini, banyak sumber daya disimpan, karena tanda tangan adalah konfirmasi kebenaran perilaku protokol dan sumber keacakan.

Namun, bahkan dengan tanda tangan deterministik, skema tersebut masih rentan terhadap masalah "aktor terakhir". Peserta terakhir masih dapat memutuskan apakah akan menerbitkan tanda tangannya atau tidak, dengan demikian mengendalikan hasilnya. Anda dapat memperbaiki skema, menambahkan hash blok ke dalamnya, membuat putaran sehingga hasilnya tidak dapat diprediksi sebelumnya, tetapi semua metode ini, bahkan dengan mempertimbangkan banyak perbaikan, masih menyisakan masalah yang belum terselesaikan dari pengaruh satu peserta pada hasil kolektif dalam lingkungan yang tidak dipercaya dan hanya dapat bekerja dalam kondisi keterbatasan ekonomi dan waktu. Selain itu, ukuran kunci RSA (1024 dan 2048 bit) cukup besar, dan ukuran untuk transaksi blockchain merupakan parameter yang sangat penting. Tampaknya dengan cara sederhana itu tidak akan berhasil, kita melangkah lebih jauh.

PVRB dan skema berbagi rahasia

Dalam kriptografi, ada skema yang memungkinkan jaringan untuk menyepakati satu dan hanya satu nilai PVRB, sementara skema semacam itu tahan terhadap tindakan jahat dari sebagian peserta. Satu protokol yang bermanfaat untuk diketahui adalah skema berbagi rahasia Shamir. Ini berfungsi untuk membagi rahasia (misalnya kunci rahasia) menjadi beberapa bagian, dan untuk mendistribusikan bagian-bagian ini kepada N peserta. Rahasianya didistribusikan sedemikian rupa sehingga bagian M dari N cukup untuk pemulihannya, sementara itu dapat berupa bagian M. Jika dengan jari, kemudian memiliki grafik fungsi yang tidak diketahui, peserta bertukar poin pada grafik, dan setelah menerima poin M, seluruh fungsi dapat dipulihkan.
Penjelasan yang baik diberikan di wiki dan bermain dengannya praktis kehilangan protokol di kepala Anda berguna di halaman demo .

Jika skema FSSS (Fiat-Shamir Secret Sharing) berlaku dalam bentuk murni, itu akan menjadi PVRB yang tidak dapat digunakan. Dalam versi paling sederhana, protokolnya mungkin terlihat seperti ini:

• Setiap peserta menghasilkan acak mereka sendiri dan membagikan saham dari itu kepada peserta lain
• M shares, , ,
• random- PVRB

, , threshold- . , RP , , “last actor”.

, PVRB secret sharing - , , . , , , . - EOS — share : . , proof- , . , verify , block-producer , , verify . , (0.5 ).

— - . proof-, — off-chain , — PVRB.

PVRB threshold signatures

secret sharing, , “threshold”. M N, N, “threshold” . “last actor”, , , . , .

threshold- PVRB — threshold-. threshold-, longread Dash.

BLS (BLS Boneh-Lynn-Shacham, ), — , , BLS , , . . , BLS , , M N , , publicly verifiable, , M- .

threshold BLS signatures BLS - ( ), threshold- . BLS , threshold- “last-actor”, , , , .

, PVRB , BLS threshold signatures, . , DFinity ( , , verifiable secret sharing), Keep.network ( random beacon yellowpaper , -, ).

PVRB

, , PVRB , . , , . PVRB , : CPU, memory, storage, I/O. PVRB — , , . , RP, , proof- , .

, PVRB:

• . PVRB unbiasable, . ,
• “last actor” . PVRB , , RP .
• . PVRB , , RP , ,
• . RP “ , ”. p2p , ,
• . PVRB on-chain , . -,
• liveness . PVRB , RP
• trusted setup . PVRB setup , . . - — ,
• . , , , ..

threshold BLS — , , , threshold. , , , , , , , realtime, , , threshold . , threshold-, , (slashing) , . , BLS , , EOS Ethereum — . — WebAssembly EVM, . (), . , 1024 2048 bit RSA, 4-8 , Bitcoin Ethereum.

— , . , Go geth, Rust Parity, C++ EOS. JavaScript , JavaScript , WebAssembly, -.

Kesimpulan

, , , , , . , , setup- , whitepaper- , - “ , ”.

, PVRB Haya , threshold BLS signatures, PVRB , - . , : secret sharing random_seed, threshold BLS , . , , , , , , — , , . — , , governance .

PVRB, , , , , , , , , , - . , , .

, , , , :)