Pengenalan
"Penjanaan nombor rawak terlalu penting untuk dibiarkan begitu sahaja."
Robert Cavue, 1970
Artikel ini ditumpukan kepada aplikasi praktikal penyelesaian menggunakan penjanaan nombor rawak kolektif dalam persekitaran yang tidak dipercayai. Ringkasnya, bagaimana dan mengapa rawak digunakan dalam rantaian blok, dan sedikit tentang cara membezakan rawak "baik" daripada "buruk". Menjana nombor yang benar-benar rawak adalah masalah yang sangat sukar, walaupun pada satu komputer, dan telah lama dikaji oleh kriptografi. Nah, dalam rangkaian terdesentralisasi, penjanaan nombor rawak adalah lebih kompleks dan penting.
Dalam rangkaian di mana peserta tidak mempercayai satu sama lain, keupayaan untuk menjana nombor rawak yang tidak dapat dipertikaikan membolehkan kami menyelesaikan banyak masalah kritikal dengan berkesan dan meningkatkan skim sedia ada dengan ketara. Lebih-lebih lagi, perjudian dan loteri bukanlah matlamat nombor satu di sini, kerana ia mungkin kelihatan pada mulanya kepada pembaca yang tidak berpengalaman.
Penjanaan nombor rawak
Komputer tidak boleh menjana sendiri nombor rawak; mereka memerlukan bantuan luar untuk berbuat demikian. Komputer boleh memperoleh beberapa nilai rawak daripada, contohnya, pergerakan tetikus, jumlah memori yang digunakan, arus sesat pada pin pemproses, dan banyak sumber lain yang dipanggil sumber entropi. Nilai-nilai ini sendiri tidak sepenuhnya rawak, kerana ia berada dalam julat tertentu atau mempunyai corak perubahan yang boleh diramal. Untuk menukar nombor sedemikian menjadi nombor rawak yang benar-benar rawak dalam julat tertentu, transformasi kripto digunakan untuk menghasilkan nilai rawak pseudo yang diedarkan secara seragam daripada nilai yang tidak sekata bagi sumber entropi. Nilai yang terhasil dipanggil pseudorandom kerana ia tidak benar-benar rawak, tetapi secara deterministik berasal daripada entropi. Mana-mana algoritma kriptografi yang baik, apabila menyulitkan data, menghasilkan teks sifir yang tidak boleh dibezakan secara statistik daripada urutan rawak, jadi untuk menghasilkan rawak anda boleh mengambil sumber entropi, yang hanya memberikan kebolehulangan yang baik dan tidak dapat diramalkan nilai walaupun dalam julat kecil, selebihnya kerja adalah menyebarkan dan mencampurkan bit dalam Nilai yang terhasil akan diambil alih oleh algoritma penyulitan.
Untuk melengkapkan program pendidikan ringkas, saya akan menambah bahawa menjana nombor rawak walaupun pada satu peranti adalah salah satu tonggak memastikan keselamatan data kami. Nombor pseudo-rawak yang dijana digunakan semasa mewujudkan sambungan selamat dalam pelbagai rangkaian, untuk menjana kunci kriptografi, untuk pengimbangan beban, pemantauan integriti, dan untuk banyak lagi aplikasi. Keselamatan banyak protokol bergantung pada keupayaan untuk menjana rawak yang boleh dipercayai, luaran yang tidak dapat diramalkan, menyimpannya, dan tidak mendedahkannya sehingga langkah seterusnya protokol, jika tidak keselamatan akan terjejas. Serangan ke atas penjana nilai pseudorandom amat berbahaya dan serta-merta mengancam semua perisian yang menggunakan penjanaan rawak.
Anda harus tahu semua ini jika anda mengambil kursus asas dalam kriptografi, jadi mari kita teruskan tentang rangkaian terdesentralisasi.
Rawak dalam blockchain
Pertama sekali, saya akan bercakap tentang rantaian blok dengan sokongan untuk kontrak pintar; mereka adalah orang yang boleh memanfaatkan sepenuhnya peluang yang disediakan oleh rawak yang berkualiti tinggi dan tidak dapat dinafikan. Selanjutnya, untuk ringkasnya, saya akan memanggil teknologi ini "Suar Rawak Boleh Disahkan Secara Awamβ atau PVRB. Memandangkan rantaian blok ialah rangkaian di mana maklumat boleh disahkan oleh mana-mana peserta, bahagian utama nama itu ialah "Boleh Disahkan Secara Awam", i.e. Sesiapa sahaja boleh menggunakan pengiraan untuk mendapatkan bukti bahawa nombor yang terhasil yang disiarkan pada blockchain mempunyai sifat berikut:
- Hasilnya mesti mempunyai pengedaran seragam yang terbukti, iaitu berdasarkan kriptografi yang terbukti kukuh.
- Ia tidak mungkin untuk mengawal mana-mana bit hasil. Akibatnya, hasilnya tidak dapat diramalkan terlebih dahulu.
- Anda tidak boleh mensabotaj protokol penjanaan dengan tidak mengambil bahagian dalam protokol atau dengan membebankan rangkaian dengan mesej serangan
- Semua perkara di atas mestilah tahan terhadap pakatan sulit bilangan peserta protokol yang tidak jujur ββyang dibenarkan (contohnya, 1/3 daripada peserta).
Sebarang kemungkinan kumpulan kecil peserta yang bersekongkol untuk menghasilkan rawak genap/ganjil terkawal adalah lubang keselamatan. Sebarang keupayaan kumpulan untuk menghentikan pengeluaran rawak adalah lubang keselamatan. Secara amnya, terdapat banyak masalah, dan tugas ini bukanlah sesuatu yang mudah...
Nampaknya aplikasi yang paling penting untuk PVRB ialah pelbagai permainan, loteri, dan secara amnya apa-apa jenis perjudian di blockchain. Memang, ini adalah hala tuju yang penting, tetapi rawak dalam rantaian blok mempunyai aplikasi yang lebih penting. Mari lihat mereka.
Algoritma Konsensus
PVRB memainkan peranan yang besar dalam mengatur konsensus rangkaian. Transaksi dalam rantaian blok dilindungi oleh tandatangan elektronik, jadi "serangan ke atas transaksi" sentiasa kemasukan/pengecualian transaksi dalam blok (atau beberapa blok). Dan tugas utama algoritma konsensus adalah untuk bersetuju dengan susunan transaksi ini dan susunan blok yang termasuk transaksi ini. Selain itu, sifat yang diperlukan untuk rantaian blok sebenar adalah kemuktamadan - keupayaan rangkaian untuk bersetuju bahawa rantaian sehingga blok yang dimuktamadkan adalah muktamad, dan tidak akan dikecualikan kerana kemunculan garpu baharu. Biasanya, untuk bersetuju bahawa blok adalah sah dan, yang paling penting, muktamad, adalah perlu untuk mengumpul tandatangan daripada majoriti pengeluar blok (selepas ini dirujuk sebagai BP - blok-pengeluar), yang memerlukan sekurang-kurangnya penghantaran rantaian blok kepada semua BP, dan mengedarkan tandatangan antara semua BP . Apabila bilangan BP bertambah, bilangan mesej yang diperlukan dalam rangkaian berkembang secara eksponen, oleh itu, algoritma konsensus yang memerlukan kemuktamadan, digunakan sebagai contoh dalam konsensus Hyperledger pBFT, tidak berfungsi pada kelajuan yang diperlukan, bermula dari beberapa dozen BP, yang memerlukan sejumlah besar sambungan.
Sekiranya terdapat PVRB yang tidak dapat dinafikan dan jujur ββdalam rangkaian, maka, walaupun dalam anggaran yang paling mudah, seseorang boleh memilih salah satu pengeluar blok berdasarkannya dan melantiknya sebagai "pemimpin" semasa satu pusingan protokol. Jika kita ada N pengeluar blok, yang mana M: M > 1/2 N jujur, jangan menapis urus niaga dan jangan putus rantai untuk melakukan serangan "berbelanja dua kali", kemudian menggunakan PVRB yang diedarkan secara seragam akan membolehkan memilih pemimpin yang jujur ββdengan kebarangkalian M / N (M / N > 1/2). Jika setiap pemimpin diberikan selang masa sendiri di mana dia boleh menghasilkan blok dan mengesahkan rantai, dan selang masa ini sama, maka rantai blok BP yang jujur ββakan lebih panjang daripada rantai yang dibentuk oleh BP yang berniat jahat, dan konsensus algoritma bergantung pada panjang rantai. hanya akan membuang yang "buruk". Prinsip memperuntukkan kepingan masa yang sama kepada setiap BP ini mula-mula digunakan dalam Graphene (pendahulu EOS), dan membenarkan kebanyakan blok ditutup dengan satu tandatangan, yang mengurangkan beban rangkaian dengan banyak dan membolehkan konsensus ini berfungsi dengan sangat cepat dan secara berterusan. Walau bagaimanapun, rangkaian EOS kini perlu menggunakan blok khas (Blok Tidak Boleh Balik Terakhir), yang disahkan oleh tandatangan 2/3 BP. Blok ini berfungsi untuk memastikan muktamad (kemustahilan garpu rantai bermula sebelum Blok Tidak Boleh Terbalik Terakhir).
Juga, dalam pelaksanaan sebenar, skema protokol adalah lebih rumit - mengundi untuk blok yang dicadangkan dijalankan dalam beberapa peringkat untuk mengekalkan rangkaian sekiranya blok hilang dan masalah dengan rangkaian, tetapi walaupun mengambil kira ini, algoritma konsensus menggunakan PVRB memerlukan mesej yang jauh lebih sedikit antara BP, yang memungkinkan untuk menjadikannya lebih pantas daripada PVFT tradisional, atau pelbagai pengubahsuaiannya.
Wakil yang paling menonjol bagi algoritma tersebut: daripada pasukan Cardano, yang dikatakan boleh dibuktikan secara matematik terhadap pakatan sulit BP.
Di Ouroboros, PVRB digunakan untuk mentakrifkan apa yang dipanggil "jadual BP" - jadual yang mengikutnya setiap BP diberikan slot masanya sendiri untuk menerbitkan blok. Kelebihan besar menggunakan PVRB ialah "kesamaan" lengkap BP (mengikut saiz kunci kira-kira mereka). Integriti PVRB memastikan bahawa BP yang berniat jahat tidak dapat mengawal penjadualan slot masa, dan oleh itu tidak boleh memanipulasi rantaian dengan menyediakan dan menganalisis garpu rantai terlebih dahulu, dan untuk memilih garpu, cukup hanya bergantung pada panjang rantaian, tanpa menggunakan cara rumit untuk mengira "utiliti" BP dan "berat" bloknya.
Secara umum, dalam semua kes di mana peserta rawak perlu dipilih dalam rangkaian terdesentralisasi, PVRB hampir selalu menjadi pilihan terbaik, dan bukannya pilihan deterministik berdasarkan, sebagai contoh, cincangan blok. Tanpa PVRB, keupayaan untuk mempengaruhi pilihan peserta membawa kepada serangan di mana penyerang boleh memilih daripada berbilang masa hadapan untuk memilih peserta rasuah seterusnya atau beberapa sekali gus untuk memastikan bahagian yang lebih besar dalam keputusan. Penggunaan PVRB mendiskreditkan jenis serangan ini.
Penskalaan dan pengimbangan beban
PVRB juga boleh memberi manfaat besar dalam tugas seperti pengurangan beban dan penskalaan pembayaran. Sebagai permulaan, masuk akal untuk membiasakan diri Rivesta "Tiket Loteri Elektronik sebagai Pembayaran Mikro". Idea umum ialah daripada membuat pembayaran 100 1c daripada pembayar kepada penerima, anda boleh bermain loteri jujur ββdengan hadiah 1$ = 100c, di mana pembayar memberikan bank satu daripada 1 "tiket loteri"nya untuk setiap bayaran 100c. Salah satu tiket ini memenangi balang $1, dan tiket inilah yang boleh direkodkan oleh penerima dalam rantaian blok. Perkara yang paling penting ialah baki 99 tiket dipindahkan antara penerima dan pembayar tanpa sebarang penyertaan luar, melalui saluran peribadi dan pada sebarang kelajuan yang dikehendaki. Penerangan yang baik tentang protokol berdasarkan skema ini pada rangkaian Emercoin boleh dibaca .
Skim ini mempunyai beberapa masalah, seperti penerima mungkin berhenti berkhidmat kepada pembayar serta-merta selepas menerima tiket yang menang, tetapi untuk banyak aplikasi khas, seperti pengebilan seminit atau langganan elektronik kepada perkhidmatan, ini boleh diabaikan. Keperluan utama, sudah tentu, adalah keadilan loteri, dan untuk pelaksanaannya, PVRB amat diperlukan.
Pilihan peserta rawak juga amat penting untuk protokol sharding, yang tujuannya adalah untuk menskalakan rantaian blok secara mendatar, membenarkan BP yang berbeza untuk memproses hanya skop transaksi mereka. Ini adalah tugas yang sangat sukar, terutamanya dari segi keselamatan apabila menggabungkan serpihan. Pemilihan saksama BP rawak untuk tujuan menetapkan mereka yang bertanggungjawab untuk serpihan tertentu, seperti dalam algoritma konsensus, juga merupakan tugas PVRB. Dalam sistem berpusat, serpihan diberikan oleh pengimbang; ia hanya mengira cincang daripada permintaan dan menghantarnya kepada pelaksana yang diperlukan. Dalam rantaian blok, keupayaan untuk mempengaruhi tugasan ini boleh membawa kepada serangan terhadap konsensus. Sebagai contoh, kandungan transaksi boleh dikawal oleh penyerang, dia boleh mengawal transaksi mana yang pergi ke serpihan yang dia kawal dan memanipulasi rantaian blok di dalamnya. Anda boleh membaca perbincangan tentang masalah menggunakan nombor rawak untuk tugasan sharding dalam Ethereum
Sharding adalah salah satu masalah yang paling bercita-cita tinggi dan serius dalam bidang blockchain; penyelesaiannya akan membolehkan membina rangkaian terdesentralisasi dengan prestasi dan volum yang hebat. PVRB hanyalah satu daripada blok penting untuk menyelesaikannya.
Permainan, protokol ekonomi, timbang tara
Peranan nombor rawak dalam industri permainan sukar untuk dipandang tinggi. Penggunaan eksplisit dalam kasino dalam talian, dan penggunaan tersirat apabila mengira kesan tindakan pemain semuanya merupakan masalah yang amat sukar untuk rangkaian terdesentralisasi, di mana tiada cara untuk bergantung pada sumber pusat rawak. Tetapi pemilihan rawak juga boleh menyelesaikan banyak masalah ekonomi dan membantu membina protokol yang lebih mudah dan cekap. Katakan dalam protokol kami terdapat pertikaian tentang pembayaran untuk beberapa perkhidmatan yang murah, dan pertikaian ini jarang berlaku. Dalam kes ini, jika terdapat PVRB yang tidak dipertikaikan, pelanggan dan penjual boleh bersetuju untuk menyelesaikan pertikaian secara rawak, tetapi dengan kebarangkalian tertentu. Contohnya, dengan kebarangkalian 60% pelanggan menang, dan dengan kebarangkalian 40% penjual menang. Pendekatan ini, yang tidak masuk akal dari sudut pandangan pertama, membolehkan anda menyelesaikan pertikaian secara automatik dengan bahagian kemenangan/kerugian yang boleh diramal dengan tepat, yang sesuai dengan kedua-dua pihak tanpa sebarang penyertaan pihak ketiga dan pembaziran masa yang tidak perlu. Selain itu, nisbah kebarangkalian boleh menjadi dinamik dan bergantung pada beberapa pembolehubah global. Sebagai contoh, jika syarikat menunjukkan prestasi yang baik, mempunyai bilangan pertikaian yang rendah dan keuntungan yang tinggi, syarikat secara automatik boleh mengalihkan kebarangkalian menyelesaikan pertikaian ke arah mengutamakan pelanggan, contohnya 70/30 atau 80/20, dan sebaliknya, jika pertikaian mengambil banyak wang dan adalah penipuan atau tidak mencukupi, anda boleh mengalihkan kebarangkalian ke arah lain.
Sebilangan besar protokol terdesentralisasi yang menarik, seperti pendaftaran susun token, pasaran ramalan, lengkung ikatan dan banyak lagi, adalah permainan ekonomi di mana tingkah laku yang baik diberi ganjaran dan tingkah laku yang buruk dihukum. Mereka sering mengandungi masalah keselamatan yang mana perlindungan bercanggah antara satu sama lain. Perkara yang dilindungi daripada serangan oleh "paus" dengan berbilion-bilion token ("paruh besar") terdedah kepada serangan oleh beribu-ribu akaun dengan baki kecil ("paruh sybil"), dan langkah-langkah yang diambil terhadap serangan tunggal, seperti bukan- yuran linear yang dibuat untuk membuat kerja dengan kepentingan yang besar tidak menguntungkan biasanya didiskreditkan oleh serangan lain. Memandangkan kita bercakap tentang permainan ekonomi, berat statistik yang sepadan boleh dikira terlebih dahulu, dan hanya menggantikan komisen dengan yang rawak dengan pengedaran yang sesuai. Komisen kebarangkalian sedemikian dilaksanakan dengan sangat mudah jika rantaian blok mempunyai sumber rawak yang boleh dipercayai dan tidak memerlukan sebarang pengiraan yang rumit, menjadikan kehidupan sukar bagi kedua-dua paus dan sybil.
Pada masa yang sama, adalah perlu untuk terus mengingati bahawa kawalan ke atas satu bit dalam rawak ini membolehkan anda menipu, mengurangkan dan meningkatkan kebarangkalian sebanyak separuh, jadi PVRB yang jujur ββadalah komponen terpenting dalam protokol tersebut.
Di mana untuk mencari rawak yang betul?
Secara teori, pemilihan rawak yang adil dalam rangkaian terdesentralisasi menjadikan hampir mana-mana protokol terbukti selamat daripada pakatan sulit. Rasionalnya agak mudah - jika rangkaian bersetuju dengan 0 atau 1 bit tunggal, dan kurang daripada separuh peserta tidak jujur, maka, dengan lelaran yang mencukupi, rangkaian dijamin mencapai kata sepakat pada bit itu dengan kebarangkalian tetap. Semata-mata kerana rawak yang jujur ββakan memilih 51 daripada 100 peserta 51% daripada masa itu. Tetapi ini secara teori, kerana... dalam rangkaian sebenar, untuk memastikan tahap keselamatan seperti dalam artikel, banyak mesej antara hos, kriptografi berbilang laluan yang kompleks diperlukan, dan sebarang komplikasi protokol serta-merta menambah vektor serangan baharu.
Itulah sebabnya kami masih belum melihat PVRB tahan terbukti dalam blockchain, yang akan digunakan untuk masa yang cukup untuk diuji oleh aplikasi sebenar, pelbagai audit, beban, dan sudah tentu, serangan sebenar, tanpanya sukar untuk memanggil produk benar-benar selamat.
Walau bagaimanapun, terdapat beberapa pendekatan yang menjanjikan, mereka berbeza dalam banyak butiran, dan salah satunya pasti akan menyelesaikan masalah. Dengan sumber pengkomputeran moden, teori kriptografi boleh diterjemahkan dengan agak bijak ke dalam aplikasi praktikal. Pada masa hadapan, kami berbesar hati untuk bercakap tentang pelaksanaan PVRB: kini terdapat beberapa daripadanya, masing-masing mempunyai set sifat penting dan ciri pelaksanaannya sendiri, dan di belakang setiap satu terdapat idea yang baik. Tidak banyak pasukan yang terlibat dalam rawak, dan pengalaman setiap daripada mereka amat penting untuk semua orang. Kami berharap maklumat kami akan membolehkan pasukan lain bergerak lebih pantas, dengan mengambil kira pengalaman pendahulu mereka.
Sumber: www.habr.com