Pendahuluan
"Pembuatan angka acak terlalu penting untuk dibiarkan kebetulan"
Robert Cavyu, 1970
Artikel ini dikhususkan untuk aplikasi praktis dari solusi menggunakan generasi kolektif nomor acak di lingkungan yang tidak terpercaya. Singkatnya - bagaimana dan mengapa acak digunakan dalam blockchains, dan sedikit tentang bagaimana membedakan "baik" acak dari "buruk". Menghasilkan angka yang benar-benar acak adalah masalah yang sangat sulit, bahkan pada komputer yang terpisah, dan telah lama dipelajari oleh cryptographers. Nah, dalam jaringan desentralisasi, pembangkitan angka acak bahkan lebih kompleks dan penting.
Dalam jaringan di mana peserta tidak saling percaya bahwa kemampuan untuk menghasilkan angka acak yang tidak dapat disangkal dapat secara efektif memecahkan banyak masalah penting dan secara signifikan meningkatkan skema yang ada. Selain itu, perjudian dan lotere di sini sama sekali bukan tujuan nomor satu, karena pembaca yang belum berpengalaman mungkin terlihat pada awalnya.
Pembuatan angka acak
Komputer tidak tahu bagaimana cara menghasilkan angka acak sendiri, untuk ini mereka membutuhkan bantuan dari luar. Komputer bisa mendapatkan beberapa nilai acak menggunakan, misalnya, gerakan mouse, jumlah memori yang digunakan, arus palsu pada kontak prosesor dan banyak sumber lain yang disebut sumber entropi. Nilai-nilai ini sendiri tidak sepenuhnya acak, karena berada dalam kisaran tertentu atau memiliki sifat perubahan yang dapat diprediksi. Untuk mengubah angka-angka tersebut menjadi angka yang benar-benar acak dalam rentang yang diberikan, transformasi kriptografi diterapkan pada mereka untuk memperoleh nilai pseudorandom yang terdistribusi secara seragam dari nilai-nilai sumber entropi yang tidak terdistribusi secara merata. Nilai yang diperoleh disebut pseudo-acak, karena tidak benar-benar acak, tetapi secara deterministik berasal dari entropi. Algoritme kriptografi yang baik, mengenkripsi data, menghasilkan cipherteks yang tidak boleh secara statistik tidak dapat dibedakan dari urutan acak, jadi untuk produksi pengacakan Anda dapat mengambil sumber entropi yang hanya menyediakan pengulangan yang baik dan nilai yang tidak dapat diprediksi bahkan dalam rentang kecil, sisa pekerjaan hamburan dan pencampuran bit dalam nilai yang dihasilkan akan diambil alih oleh algoritma enkripsi.
Untuk menyelesaikan program pendidikan singkat, saya akan menambahkan bahwa generasi nomor acak bahkan pada satu perangkat adalah salah satu pilar untuk memastikan keamanan data kami, nomor pseudorandom yang dihasilkan digunakan untuk membuat koneksi aman di berbagai jaringan, untuk menghasilkan kunci kriptografi, untuk menyeimbangkan beban, untuk mengontrol integritas, dan untuk lebih banyak kegunaan. Keamanan banyak protokol tergantung pada kemampuan untuk menghasilkan data acak yang andal dan tidak dapat diprediksi dari luar, menyimpannya, dan tidak membukanya sampai langkah protokol berikutnya, jika tidak keamanan akan dikompromikan. Serangan pada generator nilai pseudo-acak sangat berbahaya dan mengancam semua perangkat lunak yang menggunakan generasi acak sekaligus.
Anda harus mengetahui semua ini jika Anda telah mengambil kursus kriptografi dasar, jadi mari kita lanjutkan dengan jaringan desentralisasi.
Blockchain Acak
Pertama-tama, saya akan berbicara tentang blockchain dengan dukungan untuk kontrak pintar, merekalah yang dapat sepenuhnya menggunakan peluang yang disediakan oleh keacakan berkualitas tinggi yang tidak dapat disangkal. Lebih jauh, untuk singkatnya, saya akan menyebut teknologi ini " Beacon Acak yang Dapat Dip diverifikasi secara Publik " atau PVRB. Karena blockchains adalah jaringan di mana setiap peserta dapat memverifikasi informasi, bagian kunci dari namanya adalah “Dapat diverifikasi secara Publik”, yaitu siapa pun dengan bantuan perhitungan dapat memperoleh bukti bahwa jumlah yang dihasilkan, ditempatkan di blockchain, memiliki properti berikut:
- Hasilnya harus memiliki distribusi yang terbukti seragam, yaitu berdasarkan kriptografi yang terbukti kuat.
- Tidak mungkin untuk mengontrol bit dari hasilnya. Akibatnya, hasilnya tidak dapat diprediksi sebelumnya.
- Anda tidak dapat menyabotase protokol pembuatan dengan tidak berpartisipasi dalam protokol atau dengan membebani jaringan dengan pesan serangan
- Semua hal di atas harus tahan terhadap kolusi jumlah peserta tidak jujur yang diizinkan dalam protokol (misalnya, 1/3 dari peserta).
Setiap peluang bagi sekelompok kecil peserta konspirasi untuk menghasilkan bahkan genap / ganjil acak adalah lubang keamanan. Setiap peluang bagi kelompok untuk berhenti mengeluarkan rumah acak adalah lubang keamanan. Secara umum, ada banyak masalah, dan tugas ini tidak mudah ...
Tampaknya aplikasi yang paling penting untuk PVRB adalah berbagai permainan, lotere, dan umumnya segala jenis perjudian di blockchain. Memang, ini adalah arah yang penting, tetapi rumah acak di blockchains memiliki aplikasi dan lebih penting. Pertimbangkan mereka.
Algoritma konsensus
PVRB sangat penting untuk konsensus jaringan. Transaksi dalam blockchains dilindungi oleh tanda tangan elektronik, oleh karena itu, "serangan terhadap suatu transaksi" selalu merupakan penyertaan / pengecualian transaksi dalam suatu blok (atau dalam beberapa blok). Dan tugas utama dari algoritma konsensus adalah untuk menyepakati urutan transaksi ini dan urutan blok yang termasuk transaksi ini. Selain itu, properti yang diperlukan untuk blockchain nyata adalah finalitas - kemampuan jaringan untuk menyetujui bahwa rantai ke blok final adalah final, dan tidak akan pernah dikecualikan karena penampilan garpu baru. Biasanya, untuk menyetujui bahwa suatu blok valid dan, yang paling penting, final, Anda perlu mengumpulkan tanda tangan dari sebagian besar produsen blok (selanjutnya BP - produsen blok), yang mengharuskan setidaknya mengirimkan rantai blok ke semua BP dan mendistribusikan tanda tangan di antara semua BP. . Ketika jumlah BP bertambah, jumlah pesan yang diperlukan di jaringan tumbuh secara eksponensial, oleh karena itu, algoritma konsensus yang membutuhkan finalitas, seperti yang digunakan dalam konsensus pBFT Hyperledger, tidak bekerja pada kecepatan yang tepat, mulai dari beberapa lusin BP, membutuhkan sejumlah besar koneksi.
Jika jaringan memiliki PVRB yang tak terbantahkan dan jujur, maka, bahkan dalam perkiraan paling sederhana, dimungkinkan untuk memilih salah satu produsen blok berdasarkan itu dan menunjuknya "pemimpin" untuk satu putaran protokol. Jika kami memiliki produsen N block, yang M: M > 1/2 N jujur, jangan menyensor transaksi dan tidak membangun rantai garpu untuk melakukan serangan "pengeluaran ganda", maka menggunakan PVRB yang tidak terbantahkan yang didistribusikan secara merata akan memungkinkan Anda memilih pemimpin yang jujur. dengan probabilitas M / N (M / N > 1/2) . Jika setiap pemimpin diberi interval waktunya sendiri di mana ia dapat menghasilkan blok dan memvalidasi rantai, dan interval ini sama dalam waktu, maka rantai blok BP jujur akan lebih panjang daripada rantai yang dibentuk oleh BP jahat, dan algoritma konsensus bergantung pada panjang rantai, cukup buang yang "buruk". Prinsip ini mengalokasikan irisan waktu yang sama untuk setiap BP pertama kali diterapkan dalam Graphene (pendahulu EOS), dan memungkinkan sebagian besar blok ditutup dengan satu tanda tangan, yang sangat mengurangi beban jaringan dan memungkinkan konsensus ini bekerja dengan sangat cepat dan mantap. Namun, jaringan EOS sekarang harus menggunakan blok khusus (Last Irreversible Block), yang dikonfirmasi oleh 2/3 tanda tangan BP. Blok-blok ini digunakan untuk memastikan finalitas (ketidakmungkinan rantai garpu mulai lebih awal dari Blok Terakhir yang Tidak Dapat Dibalik).
Juga, dalam implementasi nyata, skema protokol lebih rumit - pemungutan suara untuk blok yang diusulkan dilakukan dalam beberapa tahap untuk mempertahankan jaringan jika terjadi blok skipping dan masalah jaringan, tetapi bahkan dengan pemikiran ini, algoritma konsensus PVRB memerlukan pesan yang jauh lebih sedikit di antara BP, yang memungkinkan Anda untuk membuatnya lebih cepat daripada PBFT tradisional, atau berbagai modifikasi.
Perwakilan paling menonjol dari algoritma semacam itu: Ouroboros dari tim Cardano, yang, seperti diumumkan, secara matematis terbukti memiliki resistensi terhadap kolusi di antara BP.
Dalam Ouroboros, PVRB digunakan untuk mendefinisikan apa yang disebut “jadwal BP” - jadwal yang dengannya masing-masing BP diberi slot waktu sendiri untuk menerbitkan blok. Keuntungan besar menggunakan PVRB adalah "hak setara" BP yang lengkap (sesuai dengan ukuran saldo mereka). Kejujuran PVRB memastikan bahwa BP jahat tidak dapat mengontrol jadwal slot waktu, dan oleh karena itu tidak dapat memanipulasi rantai dengan menyiapkan dan menganalisis garpu rantai terlebih dahulu, dan untuk memilih garpu, Anda dapat mengandalkan panjang rantai tanpa menggunakan cara rumit untuk menghitung "kegunaan" BP dan "Bobot" baloknya.
Secara umum, dalam semua kasus ketika peserta acak perlu dipilih dalam jaringan desentralisasi, PVRB hampir selalu merupakan pilihan terbaik, daripada pilihan deterministik berdasarkan, misalnya, blok hash. Tanpa PVRB, kemampuan untuk mempengaruhi pilihan peserta mengarah pada penampilan serangan di mana penyerang dapat, memilih dari beberapa opsi untuk masa depan, memilih peserta korup berikutnya atau beberapa sekaligus, untuk memberikan bagian yang lebih signifikan dalam keputusan. Menggunakan PVRB mendiskreditkan jenis serangan ini.
Penskalaan dan pemuatan muatan
PVRB juga dapat sangat bermanfaat dalam tugas-tugas untuk mengurangi beban kerja dan skala pembayaran. Sebagai permulaan, masuk akal untuk membaca artikel Rivest "Tiket Lotere Elektronik sebagai Pembayaran Mikro". Esensi umum adalah bahwa alih-alih melakukan 100 pembayaran 1c dari pembayar ke penerima, Anda dapat memainkan lotere jujur dengan hadiah $ 1 = 100c, di mana pembayar mentransfer salah satu dari 100 “tiket lotre” ke bank untuk setiap pembayaran dalam 1c. Salah satu tiket ini memenangkan bank $ 1, dan tiket inilah yang dapat diperbaiki penerima di blockchain. Yang paling penting, sisa 99 tiket ditransfer antara penerima dan pembayar tanpa partisipasi eksternal, melalui saluran pribadi dan pada kecepatan yang diinginkan. Deskripsi protokol yang baik berdasarkan skema ini di jaringan Emercoin dapat ditemukan di sini .
Skema ini memiliki beberapa masalah, misalnya, penerima dapat berhenti melayani pembayar segera setelah menerima tiket yang menang, tetapi untuk banyak aplikasi khusus, seperti penagihan per menit atau langganan elektronik ke layanan, mereka dapat diabaikan. Syarat utama, tentu saja, adalah kejujuran lotre, dan PVRB mutlak diperlukan untuk memegangnya.
Pilihan peserta acak juga sangat penting untuk protokol sharding, yang tujuannya adalah untuk secara horizontal skala rantai blok, memungkinkan BP berbeda untuk memproses hanya ruang lingkup transaksi mereka. Ini adalah tugas yang sangat sulit, terutama dalam hal keamanan ketika menggabungkan pecahan. Pilihan jujur BP acak untuk menetapkannya kepada mereka yang bertanggung jawab atas pecahan tertentu, seperti dalam algoritma konsensus, juga merupakan tugas PVRB. Dalam sistem terpusat, pecahan ditugaskan oleh penyeimbang, ia hanya menghitung hash dari permintaan dan mengirimkannya ke pelaksana yang diperlukan. Pada blockchains, kemampuan untuk memengaruhi penugasan ini dapat menyebabkan serangan pada konsensus. Misalnya, isi transaksi dapat dikontrol oleh penyerang, ia dapat mengontrol transaksi mana yang jatuh ke dalam beling yang ia kontrol dan memanipulasi rantai blok di dalamnya. Diskusi tentang masalah menggunakan angka acak untuk masalah sharding di Ethereum dapat ditemukan di sini.
Sharding adalah salah satu tugas paling ambisius dan serius di bidang blockchain, solusinya akan memungkinkan Anda untuk membangun jaringan terdesentralisasi dengan kinerja dan volume fantastis. PVRB hanyalah salah satu blok penting untuk menyelesaikannya.
Game, protokol ekonomi, arbitrasi
Peran angka acak dalam industri game sulit ditaksir terlalu tinggi. Penggunaan eksplisit di kasino online, dan tersirat dalam menghitung efek dari tindakan pemain, semuanya merupakan masalah yang sangat sulit untuk jaringan terdesentralisasi, di mana tidak ada cara untuk bergantung pada sumber pusat keacakan. Tapi, pilihan acak dapat menyelesaikan banyak masalah ekonomi dan membantu membangun protokol yang lebih sederhana dan lebih efisien. Misalkan dalam protokol kami ada perselisihan tentang pembayaran untuk beberapa layanan murah, dan perselisihan ini sangat jarang. Dalam hal ini, jika ada PVRB yang tidak dapat disangkal, pelanggan dan penjual dapat menyetujui resolusi perselisihan acak, tetapi dengan probabilitas yang diberikan. Misalnya, dengan probabilitas 60%, klien menang, dan dengan probabilitas 40%, penjual menang. Pendekatan absurd seperti itu, dari sudut pandang pertama, memungkinkan seseorang untuk secara otomatis menyelesaikan perselisihan dengan bagian yang dapat diprediksi secara akurat dari kemenangan / kerugian, yang cocok untuk kedua belah pihak tanpa keterlibatan pihak ketiga dan buang-buang waktu yang tidak perlu. Selain itu, rasio probabilitas dapat menjadi dinamis dan tergantung pada beberapa variabel global. Misalnya, jika suatu perusahaan baik-baik saja, ada sejumlah kecil perselisihan dan profitabilitas yang tinggi, perusahaan dapat secara otomatis menggeser kemungkinan penyelesaian perselisihan menjadi berorientasi pada klien, misalnya 70/30 atau 80/20, dan sebaliknya, jika perselisihan menghabiskan banyak uang dan curang atau tidak memadai, Anda dapat menggeser probabilitas ke arah lain.
Sejumlah besar protokol desentralisasi yang menarik, seperti token registered, pasar prediksi, kurva ikatan, dan banyak lainnya adalah permainan ekonomi yang menghargai perilaku baik dan buruk. Mereka sering menghadapi masalah keamanan, perlindungan yang saling bertentangan. Apa yang dilindungi dari serangan oleh "paus" dengan miliaran token ("pasak besar") rentan terhadap serangan oleh ribuan akun dengan saldo kecil ("pasak sybil"), dan tindakan diambil terhadap satu serangan, seperti komisi non-linear yang dibuat untuk untuk membuat steak besar tidak menguntungkan, mereka biasanya didiskreditkan oleh serangan lain. Karena ini adalah permainan ekonomi, bobot statistik yang sesuai dapat dihitung di muka, dan cukup ganti komisi dengan yang acak dengan distribusi yang sesuai. Komisi probabilistik semacam itu dilaksanakan dengan sangat sederhana jika blockchain memiliki sumber keacakan yang dapat diandalkan dan tidak memerlukan perhitungan yang rumit, membuat hidup sulit bagi paus dan sybil.
Penting untuk terus mengingat bahwa kontrol atas bit tunggal dalam pengacakan ini memungkinkan Anda untuk menipu, mengurangi dan menggandakan probabilitas, jadi PVRB yang jujur adalah komponen terpenting dari protokol tersebut.
Di mana menemukan acak yang benar?
Secara teori, pilihan acak yang jujur dalam jaringan desentralisasi menyediakan keamanan yang dapat dibuktikan dari hampir semua protokol terhadap kolusi. Alasannya cukup sederhana - jika jaringan menyetujui satu bit 0 atau 1, dan di antara peserta kurang dari setengahnya tidak jujur, maka, dengan jumlah iterasi yang memadai, jaringan dijamin untuk mencapai konsensus tentang bit ini dengan probabilitas tetap. Hanya karena acak yang jujur akan memilih 51 dari 100 peserta dalam 51% kasus. Tapi ini dalam teori, karena dalam jaringan nyata, untuk memastikan tingkat keamanan seperti dalam artikel, itu membutuhkan banyak pesan antara host, kompleks multi-pass kriptografi, dan setiap komplikasi protokol segera menambah vektor serangan baru.
Itu sebabnya kita belum melihat di blockchains PVRB terbukti yang akan menggunakan cukup waktu untuk diuji oleh aplikasi nyata, banyak audit, banyak, dan tentu saja, serangan nyata, yang tanpanya sulit untuk menyebut produk itu benar-benar aman.
Namun demikian, ada beberapa pendekatan yang menjanjikan sekaligus, mereka berbeda dalam banyak detail, dan beberapa dari mereka pasti akan menyelesaikan masalah. Dengan sumber daya komputasi modern, teori kriptografi mampu berubah menjadi aplikasi praktis. Di masa depan, kami akan senang berbicara tentang implementasi PVRB: ada beberapa di antaranya sekarang, masing-masing memiliki set properti dan fitur penting dalam implementasinya, dan masing-masing memiliki ide yang bagus. Tidak banyak tim yang terlibat secara acak, dan pengalaman masing-masing sangat penting bagi orang lain. Kami berharap bahwa informasi kami akan memungkinkan tim lain untuk bergerak lebih cepat, dengan mempertimbangkan pengalaman para pendahulu mereka.