pengenalan
“Pembuatan angka acak terlalu penting untuk dibiarkan begitu saja.”
Robert Cavue, 1970
Artikel ini dikhususkan untuk penerapan praktis solusi menggunakan pembangkitan bilangan acak kolektif di lingkungan yang tidak tepercaya. Singkatnya, bagaimana dan mengapa random digunakan dalam blockchain, dan sedikit tentang bagaimana membedakan random “baik” dari “buruk”. Menghasilkan angka yang benar-benar acak adalah masalah yang sangat sulit, bahkan pada satu komputer, dan telah lama dipelajari oleh para kriptografer. Nah, dalam jaringan terdesentralisasi, pembuatan angka acak menjadi lebih kompleks dan penting.
Dalam jaringan di mana pesertanya tidak percaya satu sama lain, kemampuan untuk menghasilkan angka acak yang tidak dapat disangkal memungkinkan kita untuk secara efektif memecahkan banyak masalah kritis dan secara signifikan meningkatkan skema yang ada. Selain itu, perjudian dan lotere bukanlah tujuan nomor satu di sini, seperti yang mungkin terlihat pada awalnya bagi pembaca yang tidak berpengalaman.
Pembuatan angka acak
Komputer tidak dapat menghasilkan angka acak sendiri; mereka memerlukan bantuan dari luar untuk melakukannya. Komputer dapat memperoleh beberapa nilai acak, misalnya dari pergerakan mouse, jumlah memori yang digunakan, arus nyasar pada pin prosesor, dan banyak sumber lain yang disebut sumber entropi. Nilai-nilai ini sendiri tidak sepenuhnya acak, karena berada dalam kisaran tertentu atau memiliki pola perubahan yang dapat diprediksi. Untuk mengubah angka-angka tersebut menjadi angka yang benar-benar acak dalam rentang tertentu, transformasi kripto diterapkan padanya untuk menghasilkan nilai pseudo-acak yang terdistribusi secara merata dari nilai sumber entropi yang tidak terdistribusi secara merata. Nilai yang dihasilkan disebut pseudorandom karena tidak benar-benar acak, tetapi diturunkan secara deterministik dari entropi. Algoritme kriptografi yang baik, ketika mengenkripsi data, menghasilkan teks tersandi yang secara statistik tidak dapat dibedakan dari urutan acak, sehingga untuk menghasilkan keacakan, Anda dapat mengambil sumber entropi, yang hanya memberikan pengulangan nilai yang baik dan ketidakpastian bahkan dalam rentang kecil, yaitu sisa pekerjaannya adalah menyebarkan dan mencampur bit-bit. Nilai yang dihasilkan akan diambil alih oleh algoritma enkripsi.
Untuk melengkapi program pendidikan singkat, saya akan menambahkan bahwa menghasilkan nomor acak bahkan pada satu perangkat adalah salah satu pilar untuk memastikan keamanan data kami.Nomor pseudo-acak yang dihasilkan digunakan saat membuat koneksi aman di berbagai jaringan, untuk menghasilkan kunci kriptografi, untuk penyeimbangan beban, pemantauan integritas, dan untuk banyak aplikasi lainnya. Keamanan banyak protokol bergantung pada kemampuan untuk menghasilkan data acak yang dapat diandalkan dan tidak dapat diprediksi secara eksternal, menyimpannya, dan tidak mengungkapkannya hingga langkah protokol berikutnya, jika tidak, keamanan akan terganggu. Serangan terhadap generator nilai pseudorandom sangat berbahaya dan langsung mengancam semua perangkat lunak yang menggunakan pembangkitan keacakan.
Anda harus mengetahui semua ini jika Anda mengambil kursus dasar kriptografi, jadi mari kita lanjutkan tentang jaringan terdesentralisasi.
Acak di blockchain
Pertama-tama, saya akan berbicara tentang blockchain dengan dukungan untuk kontrak pintar; mereka adalah orang-orang yang dapat sepenuhnya memanfaatkan peluang yang diberikan oleh keacakan berkualitas tinggi dan tidak dapat disangkal. Selanjutnya, untuk singkatnya, saya akan menyebut teknologi ini “Beacon Acak yang Dapat Diverifikasi Secara Publik” atau PVRB. Karena blockchain adalah jaringan di mana informasi dapat diverifikasi oleh peserta mana pun, bagian penting dari namanya adalah “Dapat Diverifikasi Secara Publik”, yaitu. Siapa pun dapat menggunakan perhitungan untuk mendapatkan bukti bahwa angka yang dihasilkan yang diposting di blockchain memiliki properti berikut:
- Hasilnya harus memiliki distribusi yang seragam, yaitu didasarkan pada kriptografi yang terbukti kuat.
- Tidak mungkin untuk mengontrol bagian mana pun dari hasilnya. Akibatnya, hasilnya tidak dapat diprediksi sebelumnya.
- Anda tidak dapat menyabotase protokol pembangkitan dengan tidak berpartisipasi dalam protokol atau dengan membebani jaringan dengan pesan serangan
- Semua hal di atas harus tahan terhadap kolusi sejumlah peserta protokol yang tidak jujur (misalnya, 1/3 dari peserta).
Segala kemungkinan sekelompok kecil peserta yang berkolusi untuk menghasilkan acak genap/ganjil yang terkontrol adalah celah keamanan. Setiap kemampuan kelompok untuk menghentikan penerbitan acak adalah lubang keamanan. Secara umum, ada banyak masalah, dan tugas ini bukanlah tugas yang mudah...
Tampaknya penerapan PVRB yang paling penting adalah berbagai permainan, lotere, dan umumnya semua jenis perjudian di blockchain. Memang benar, ini adalah arah yang penting, namun keacakan dalam blockchain memiliki penerapan yang lebih penting. Mari kita lihat mereka.
Algoritma Konsensus
PVRB memainkan peran besar dalam mengatur konsensus jaringan. Transaksi dalam blockchain dilindungi oleh tanda tangan elektronik, sehingga “serangan terhadap suatu transaksi” selalu berupa penyertaan/pengecualian suatu transaksi dalam satu blok (atau beberapa blok). Dan tugas utama algoritma konsensus adalah menyepakati urutan transaksi-transaksi ini dan urutan blok-blok yang mencakup transaksi-transaksi ini. Selain itu, properti yang diperlukan untuk blockchain nyata adalah finalitas - kemampuan jaringan untuk menyetujui bahwa rantai hingga blok yang diselesaikan adalah final, dan tidak akan pernah dikecualikan karena munculnya garpu baru. Biasanya, untuk menyetujui bahwa suatu blok valid dan, yang paling penting, final, perlu untuk mengumpulkan tanda tangan dari mayoritas produsen blok (selanjutnya disebut BP - produsen blok), yang setidaknya memerlukan pengiriman rantai blok. kepada seluruh BP, dan mendistribusikan tanda tangan antar seluruh BP. Seiring bertambahnya jumlah BP, jumlah pesan yang diperlukan dalam jaringan bertambah secara eksponensial, oleh karena itu, algoritma konsensus yang memerlukan finalitas, yang digunakan misalnya dalam konsensus Hyperledger pBFT, tidak bekerja pada kecepatan yang diperlukan, mulai dari beberapa lusin BP, memerlukan sejumlah besar koneksi.
Jika terdapat PVRB yang tidak dapat disangkal dan jujur dalam jaringan, maka, bahkan dalam perkiraan yang paling sederhana, seseorang dapat memilih salah satu produsen blok berdasarkan PVRB tersebut dan menunjuknya sebagai “pemimpin” selama satu putaran protokol. Jika kita punya N produsen blok, di antaranya M: M > 1/2 N jujur, tidak menyensor transaksi dan tidak memutus rantai untuk melakukan serangan “pembelanjaan ganda”, maka menggunakan PVRB yang tidak tertandingi dan terdistribusi secara seragam akan memungkinkan pemilihan pemimpin yang jujur dengan kemungkinan M / N (M / N > 1/2). Jika setiap pemimpin diberi interval waktu masing-masing di mana ia dapat menghasilkan blok dan memvalidasi rantai, dan interval ini sama, maka rantai blok BP yang jujur akan lebih panjang daripada rantai yang dibentuk oleh BP jahat, dan konsensusnya algoritma bergantung pada panjang rantai, dan hanya akan membuang yang “buruk”. Prinsip mengalokasikan waktu yang sama untuk setiap BP pertama kali diterapkan di 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 stabil. Namun jaringan EOS kini harus menggunakan blok khusus (Last Irreversible Block), yang dikonfirmasi dengan tanda tangan 2/3 BP. Blok-blok ini berfungsi untuk memastikan finalitas (ketidakmungkinan percabangan rantai dimulai sebelum Blok Terakhir yang Tidak Dapat Dibalikkan).
Selain itu, dalam implementasi nyata, skema protokol lebih rumit - pemungutan suara untuk blok yang diusulkan dilakukan dalam beberapa tahap untuk menjaga jaringan jika ada blok yang hilang dan masalah dengan jaringan, namun meskipun demikian, algoritma konsensus yang menggunakan PVRB memerlukan pesan antar BP jauh lebih sedikit, yang membuatnya lebih cepat dibandingkan PVFT tradisional, atau berbagai modifikasinya.
Perwakilan paling menonjol dari algoritma tersebut: dari tim Cardano, yang dikatakan dapat dibuktikan secara matematis terhadap kolusi BP.
Di Ouroboros, PVRB digunakan untuk menentukan apa yang disebut "jadwal BP" - jadwal yang menurutnya setiap BP diberi slot waktunya sendiri untuk menerbitkan sebuah blok. Keuntungan besar menggunakan PVRB adalah “kesetaraan” BP yang lengkap (sesuai dengan ukuran neracanya). Integritas PVRB memastikan bahwa BP jahat tidak dapat mengontrol penjadwalan slot waktu, dan oleh karena itu tidak dapat memanipulasi rantai dengan menyiapkan dan menganalisis cabang-cabang rantai terlebih dahulu, dan untuk memilih cabang, cukup mengandalkan panjangnya saja. rantai, tanpa menggunakan cara rumit untuk menghitung “utilitas” BP dan “berat” bloknya.
Secara umum, dalam semua kasus di mana peserta acak perlu dipilih dalam jaringan terdesentralisasi, PVRB hampir selalu merupakan pilihan terbaik, bukan pilihan deterministik berdasarkan, misalnya, hash blok. Tanpa PVRB, kemampuan untuk mempengaruhi pilihan peserta akan mengarah pada serangan di mana penyerang dapat memilih dari beberapa masa depan untuk memilih peserta korup berikutnya atau beberapa sekaligus untuk memastikan bagian yang lebih besar dalam pengambilan keputusan. Penggunaan PVRB mendiskreditkan jenis serangan ini.
Penskalaan dan penyeimbangan beban
PVRB juga dapat memberikan manfaat besar dalam tugas-tugas seperti pengurangan beban dan penskalaan pembayaran. Untuk memulainya, masuk akal untuk membiasakan diri Rivesta “Tiket Lotere Elektronik sebagai Pembayaran Mikro”. Ide umumnya adalah bahwa alih-alih melakukan pembayaran 100 1c dari pembayar ke penerima, Anda dapat memainkan lotere yang jujur dengan hadiah 1$ = 100c, di mana pembayar memberikan bank satu dari 1 “tiket lotere” miliknya untuk setiap pembayaran. pembayaran 100c. Salah satu tiket ini memenangkan sebotol $1, dan tiket inilah yang dapat dicatat oleh penerima di blockchain. Yang paling penting adalah sisa 99 tiket ditransfer antara penerima dan pembayar tanpa partisipasi eksternal, melalui saluran pribadi dan dengan kecepatan berapa pun yang diinginkan. Penjelasan yang baik tentang protokol berdasarkan skema ini di jaringan Emercoin dapat dibaca .
Skema ini memiliki beberapa masalah, seperti penerima dapat berhenti melayani pembayar segera setelah menerima tiket pemenang, namun untuk banyak aplikasi khusus, seperti tagihan per menit atau langganan elektronik ke layanan, hal ini dapat diabaikan. Syarat utamanya tentu saja keadilan dalam pengundian, dan untuk pelaksanaannya mutlak diperlukan PVRB.
Pemilihan peserta acak juga sangat penting untuk protokol sharding, yang tujuannya adalah untuk menskalakan rantai blok secara horizontal, sehingga BP yang berbeda hanya dapat memproses cakupan transaksinya saja. Ini adalah tugas yang sangat sulit, terutama dalam hal keamanan saat menggabungkan pecahan. Pemilihan BP acak yang adil untuk tujuan menugaskan mereka yang bertanggung jawab atas pecahan tertentu, seperti dalam algoritma konsensus, juga merupakan tugas PVRB. Dalam sistem terpusat, pecahan ditetapkan oleh penyeimbang; yang hanya menghitung hash dari permintaan dan mengirimkannya ke pelaksana yang diperlukan. Dalam blockchain, kemampuan untuk mempengaruhi penugasan ini dapat menyebabkan serangan terhadap konsensus. Misalnya, isi transaksi dapat dikontrol oleh penyerang, dia dapat mengontrol transaksi mana yang masuk ke shard yang dia kendalikan dan memanipulasi rantai blok di dalamnya. Anda dapat membaca pembahasan masalah penggunaan angka acak untuk tugas sharding di Ethereum
Sharding adalah salah satu masalah paling ambisius dan serius di bidang blockchain; solusinya akan memungkinkan pembangunan jaringan terdesentralisasi dengan kinerja dan volume yang fantastis. PVRB hanyalah salah satu blok penting untuk menyelesaikannya.
Permainan, protokol ekonomi, arbitrase
Peran angka acak dalam industri game sulit untuk ditaksir terlalu tinggi. Penggunaan eksplisit di kasino online, dan penggunaan implisit ketika menghitung dampak tindakan pemain adalah masalah yang sangat sulit untuk jaringan terdesentralisasi, di mana tidak ada cara untuk mengandalkan sumber utama keacakan. Namun pemilihan acak juga dapat memecahkan banyak masalah ekonomi dan membantu membangun protokol yang lebih sederhana dan efisien. Misalkan dalam protokol kita terdapat perselisihan mengenai pembayaran untuk beberapa layanan murah, dan perselisihan ini jarang terjadi. Dalam hal ini, jika terdapat PVRB yang tidak dapat disengketakan, pelanggan dan penjual dapat sepakat untuk menyelesaikan perselisihan secara acak, namun dengan probabilitas tertentu. Misalnya, dengan probabilitas 60% klien menang, dan dengan probabilitas 40% penjual menang. Pendekatan ini, yang tidak masuk akal dari sudut pandang pertama, memungkinkan Anda untuk secara otomatis menyelesaikan perselisihan dengan tingkat kemenangan/kekalahan yang dapat diprediksi secara tepat, yang sesuai dengan kedua belah pihak tanpa partisipasi pihak ketiga dan membuang-buang waktu yang tidak perlu. Selain itu, rasio probabilitas dapat bersifat dinamis dan bergantung pada beberapa variabel global. Misalnya, jika suatu perusahaan berjalan dengan baik, memiliki jumlah perselisihan yang rendah dan profitabilitas yang tinggi, maka perusahaan secara otomatis dapat mengalihkan kemungkinan penyelesaian perselisihan ke arah berpusat pada pelanggan, misalnya 70/30 atau 80/20, dan sebaliknya, jika perselisihan memakan banyak uang dan bersifat curang atau tidak memadai, Anda dapat mengalihkan kemungkinannya ke arah lain.
Sejumlah besar protokol terdesentralisasi yang menarik, seperti pencatatan token yang dikurasi, pasar prediksi, kurva ikatan, dan banyak lainnya, merupakan permainan ekonomi di mana perilaku baik diberi imbalan dan perilaku buruk diberi sanksi. Mereka sering kali mengandung masalah keamanan yang mana perlindungannya bertentangan satu sama lain. Apa yang dilindungi dari serangan “paus” dengan miliaran token (“taruhan besar”) rentan terhadap serangan ribuan akun dengan saldo kecil (“saham sybil”), dan tindakan yang diambil terhadap satu serangan, seperti non- biaya linier yang dibuat untuk membuat bekerja dengan taruhan besar tidak menguntungkan biasanya didiskreditkan oleh serangan lain. Karena kita berbicara tentang permainan ekonomi, bobot statistik yang sesuai dapat dihitung terlebih dahulu, dan cukup mengganti komisi dengan yang diacak dengan distribusi yang sesuai. Komisi probabilistik seperti itu diimplementasikan dengan sangat sederhana jika blockchain memiliki sumber keacakan yang dapat diandalkan dan tidak memerlukan perhitungan yang rumit, sehingga menyulitkan paus dan sybil.
Pada saat yang sama, perlu diingat bahwa kontrol atas satu bit dalam keacakan ini memungkinkan Anda untuk menipu, mengurangi dan meningkatkan probabilitas hingga setengahnya, sehingga PVRB yang jujur adalah komponen terpenting dari protokol tersebut.
Di mana menemukan acak yang tepat?
Secara teori, pemilihan acak yang adil dalam jaringan terdesentralisasi membuat hampir semua protokol terbukti aman dari kolusi. Alasannya cukup sederhana - jika jaringan menyetujui satu bit 0 atau 1, dan kurang dari separuh partisipan tidak jujur, maka, dengan iterasi yang cukup, jaringan dijamin akan mencapai konsensus pada bit tersebut dengan probabilitas tetap. Hanya karena pengacakan yang jujur akan memilih 51 dari 100 peserta dengan persentase 51%. Tapi ini secara teori, karena... dalam jaringan nyata, untuk memastikan tingkat keamanan seperti dalam artikel, diperlukan banyak pesan antar host, kriptografi multi-pass yang kompleks, dan setiap komplikasi protokol segera menambah vektor serangan baru.
Itulah sebabnya kita belum melihat PVRB yang terbukti resisten dalam blockchain, yang telah digunakan dalam waktu yang cukup lama untuk diuji oleh aplikasi nyata, banyak audit, beban, dan tentu saja, serangan nyata, yang tanpanya sulit untuk disebut a produk benar-benar aman.
Namun, ada beberapa pendekatan yang menjanjikan, pendekatan tersebut berbeda dalam banyak detailnya, dan salah satunya pasti akan menyelesaikan masalah. Dengan sumber daya komputasi modern, teori kriptografi dapat dengan cerdik diterjemahkan ke dalam aplikasi praktis. Di masa depan, kami akan dengan senang hati berbicara tentang implementasi PVRB: sekarang ada beberapa implementasi, masing-masing memiliki serangkaian properti penting dan fitur implementasi, dan di balik masing-masing implementasi terdapat ide bagus. Tidak banyak tim yang terlibat dalam pengacakan, dan pengalaman masing-masing tim sangat penting bagi orang lain. Kami berharap informasi kami dapat memungkinkan tim lain untuk bergerak lebih cepat, dengan mempertimbangkan pengalaman pendahulunya.
Sumber: www.habr.com