Keacakan Publik dan Suar Keacakan

Keacakan publik merupakan komponen penting dari banyak protokol keamanan dunia nyata. Dalam beberapa aplikasi, seperti permainan judi dan multipemain, keacakan menambah kesenangan. Dalam aplikasi lain, keacakan menyediakan cara yang adil untuk mengalokasikan sumber daya yang tidak dapat dibagi, mulai dari kartu hijau, penugasan hakim pengadilan sirkuit hingga kasus, hingga penyemaian dalam turnamen olahraga. Ini juga digunakan untuk mengalokasikan negatif sumber daya, seperti audit pajak atau pemeriksaan keamanan sekunder di bandara.

Secara tradisional, kami mengandalkan otoritas tepercaya untuk menghasilkan keacakan untuk protokol ini, tetapi di dunia web3, kami harus melakukan yang lebih baik. Dalam posting ini, kami akan mengeksplorasi pendekatan untuk membangun keacakan yang dapat diverifikasi secara publik melalui suar keacakan terdistribusi dan kemudian mendiskusikan beberapa aplikasi on-chain. (Bagian II, yang akan datang, secara khusus akan fokus pada pemilihan pemimpin, sambil memberikan penilaian tentang pendekatan pemilihan pemimpin alternatif.) 

Properti yang diinginkan

Menghasilkan angka acak adalah tugas yang sangat halus. Misalnya, banyak kunci kriptografi yang bocor karena mengandalkan generator nomor acak yang rusak (di mana dinding Cloudflare lampu lava akan berfungsi sebagai mitigasi kreatif). Itu hanya keacakan pribadi, namun, di mana hanya satu pihak yang perlu membuat dan menggunakannya.

Keacakan publik, sebaliknya, adalah proses multipartai, yang menambah banyak kesulitan. Protokol yang baik untuk menghasilkan keacakan publik akan memiliki properti keamanan berikut:

• tidak biasa: Tidak ada penyerang, atau koalisi penyerang, yang dapat membiaskan output. 
• Handal: Tidak ada penyerang yang dapat mencegah protokol menghasilkan keluaran.
• Diverifikasi: Siapa saja dapat dengan mudah memverifikasi keluaran protokol, dan akan melihat keluaran yang sama seperti orang lain.
• Unpredictable: Jika protokol menghasilkan output pada waktu T₁, tidak ada yang bisa memprediksi apa pun tentang output sebelum beberapa waktu T₀<T₁, idealnya dengan T₀ sangat dekat dengan T₁.

Unbiasability adalah properti yang lebih lemah daripada unpredictability karena protokol apa pun yang tidak dapat diprediksi harus unbiasable. Ilmuwan komputer akan mengatakan ketidakbiasaan mengurangi untuk ketidakpastian, karena jika Anda bisa bias, Anda bisa memprediksi. Tetapi kadang-kadang kita ingin mempertimbangkannya secara terpisah karena mereka mungkin bergantung pada asumsi yang berbeda – misalnya, mayoritas yang tidak jujur ​​mungkin memprediksi hasilnya, tetapi tidak membiaskannya.

Selain sifat-sifat ini, protokol harus efisien untuk dijalankan dan menghasilkan sejumlah besar bit acak. (Dalam praktiknya, seringkali cukup bagi aplikasi untuk menghasilkan 128 bit acak, menggunakannya untuk menyemai generator nomor pseudorandom [PNRG] untuk menghasilkan lebih banyak bit sesuai kebutuhan. Namun, ketidakpastian harus berlaku untuk setiap bit individu dari output agar dapat digunakan untuk hal tersebut. aplikasi sebagai lotere atau alokasi sumber daya.) Protokol idealnya juga harus efisien dalam hal biaya komunikasi dan komputasi.

Protokol yang berbeda dapat mencapai properti ini dalam kondisi yang berbeda. Misalnya, beberapa protokol mungkin tidak biasa oleh koalisi mana pun f₁ node jahat dan tidak dapat diprediksi oleh koalisi mana pun f₂<f₁ node berbahaya. Ada juga tingkat bias yang berbeda. Misalnya, dalam beberapa protokol, seorang peserta mungkin dapat membiaskan output dengan “satu bit” – yang berarti mereka dapat memilih antara satu dari dua kemungkinan output. Serangan lain mungkin memungkinkan mereka untuk memperbaiki output sepenuhnya. Biasanya, bagaimanapun, kami tidak ingin mentolerir bias (atau prediktabilitas) sama sekali.

Kriptografi ideal: Rsuar andomness

Kriptografer sering memulai dengan memikirkan solusi ideal untuk masalah mereka. Dalam kasus keacakan publik, a suar keacakan adalah layanan ideal yang secara teratur menghasilkan output acak yang memenuhi semua persyaratan keamanan yang diperlukan.

Suar keacakan yang diidealkan seperti itu, mirip dengan abstraksi kriptografi lainnya – seperti orakel acak atau model grup generik – tidak ada di dunia nyata. Tapi itu adalah tujuan yang berguna untuk diperjuangkan dan model yang berguna untuk alasan tentang protokol yang mengandalkan keacakan publik. 

Kita dapat mempertimbangkan beberapa perkiraan dari suar keacakan yang ideal.

• Suar terpusat: Pendekatan termudah untuk menghasilkan keacakan yang baik adalah melalui pihak ketiga yang terpusat dengan layanan seperti suar keacakan NIST or random.org, yang menghasilkan keacakan dari kebisingan atmosfer dan diakreditasi untuk digunakan dalam perjudian. Ketergantungan pada pihak ketiga ini benar-benar merusak filosofi desentralisasi. Memang, dalam contoh di atas kita harus percaya bahwa organisasi yang relevan menghasilkan keacakan dengan benar, tanpa bukti kriptografi.
• Tampilan keacakan fisik: Banyak lotere tradisional bergantung pada tampilan publik, yang mungkin termasuk, misalnya, seseorang meraih ke dalam wadah bola pingpong dengan nomor berbeda di atasnya. Sayangnya, ini seringkali mudah dimanipulasi. Contohnya, bola tertentu dapat ditempatkan di freezer dan pemilih dapat disuruh memilih yang dingin.
• suar alami: Ide umum adalah menggunakan fenomena alam acak seperti cuaca atau radiasi latar kosmik sebagai suar. Sayangnya, semua sumber yang diusulkan tidak memberikan konsensus yang kuat. Pengamat yang berbeda akan melihat nilai yang sedikit berbeda, yang memerlukan pengenalan kembali pihak tepercaya untuk melakukan pengukuran resmi, dengan semua kelemahan suar terpusat.
• Suar semi-terpusat: Pendekatan yang lebih baik adalah mendapatkan keacakan dari Header blok Bitcoin langsung atau dari harga penutupan saham, yang lebih mudah untuk diverifikasi secara publik dan lebih sulit untuk dikontrol sepenuhnya oleh satu pihak. Namun serangan halus masih ada pada keduanya keacakan blockchain bukti kerja dan keacakan harga saham. Dengan header blockchain, misalnya, penambang dapat memilih untuk menahan blok yang headernya menghasilkan nilai suar yang tidak mereka sukai. Atau mereka dapat memilih untuk memutuskan hubungan ketika dua blok bertabrakan ditemukan berdasarkan keluaran suar yang mereka sukai.

Suar keacakan terdesentralisasi (DRB)

Pendekatan alami untuk masalah beacon terpusat adalah merancang protokol kriptografi terdesentralisasi untuk menghasilkan keacakan publik. Masalah ini agak seperti merancang protokol konsensus terdesentralisasi, hanya lebih sulit. Tidak hanya semua peserta perlu menyetujui keluaran (keacakan), tetapi peserta jahat dalam protokol harus tidak mungkin untuk membiaskan atau memprediksi keluaran.

Protokol yang dirancang untuk mensimulasikan suar keacakan disebut suar keacakan terdistribusi (DRB). (Nama lain termasuk "membalik koin terdistribusi.") Masalahnya telah dipelajari selama beberapa dekade, dengan hasil kemustahilan yang terkenal terbukti pada 1980-an, tetapi minat telah dihidupkan kembali di era blockchain. DRB dapat digunakan untuk menyediakan keacakan on-chain, yang akan menjadi bahan utama untuk aplikasi on-chain yang adil, aman, dan transparan.

Pendekatan klasik: Protokol komit-ungkap

Protokol dua putaran yang sangat sederhana sudah cukup untuk DRB dalam kasus optimis. Di babak 1, setiap peserta i menghasilkan nilai acak r_i dan menerbitkan komitmen kriptografi c_i=Melakukan(r_i). Dalam aplikasi ini, komitmen dapat berupa fungsi hash seperti SHA-256. Setelah komitmen masing-masing peserta dipublikasikan, mereka terkunci pada pilihan mereka r_i, tetapi komitmen tidak mengungkapkan informasi apa pun tentang kontribusi peserta lain. Di babak 2, setiap peserta “membuka komitmennya” dengan mempublikasikan r_i. Semua nilai acak kemudian digabungkan, misalnya dengan meng-XOR nilai tersebut atau (lebih disukai) menggabungkannya dengan hashing.

Protokol ini sederhana dan menghasilkan keluaran suar acak selama salah satu peserta memilih r_i secara acak. Sayangnya, ia menderita cacat klasik: ketika semua kecuali satu dari peserta telah mengungkapkan nilai acak mereka, peserta terakhir dapat menghitung keluaran suar diduga. Jika mereka tidak menyukainya, mereka dapat menolak untuk mempublikasikan nilainya, membatalkan protokol. Mengabaikan kontribusi peserta yang salah tidak menyelesaikan masalah, karena itu masih memberi penyerang pilihan antara dua keluaran suar (satu dihitung dengan kontribusinya dan satu tanpa).

Blockchains menawarkan solusi alami untuk masalah ini: setiap peserta dapat diminta untuk menaruh sejumlah dana di escrow yang disita jika mereka tidak mengungkapkan kontribusi acak mereka. Ini persis pendekatan yang diambil oleh klasik RANDAO suar di Ethereum. Kelemahan dari pendekatan ini adalah bahwa output masih bisa bias, yang mungkin bermanfaat secara finansial bagi penyerang jika uang di escrow kurang dari jumlah uang yang menumpang pada hasil beacon. Keamanan yang lebih baik terhadap serangan bias membutuhkan lebih banyak koin di escrow.

Protokol komit-ungkap-pemulihan

Alih-alih mencoba memaksa semua pihak untuk mengungkapkan kontribusi acak mereka, beberapa protokol menyertakan mekanisme pemulihan sehingga meskipun sebagian kecil peserta putus, sisanya dapat menyelesaikan protokol. Sangat penting bahwa protokol menghasilkan hasil yang sama dalam kedua kasus tersebut, sehingga para pihak tidak dapat membiaskan hasil dengan memilih apakah akan keluar atau tidak.

Salah satu pendekatan untuk mencapai ini adalah meminta setiap peserta memberikan bagian rahasianya kepada yang lain, sehingga mayoritas dari mereka dapat merekonstruksinya, dengan menggunakan, misalnya, Berbagi rahasia Shamir. Properti penting, bagaimanapun, adalah bahwa yang lain dapat memverifikasi bahwa rahasia yang dikomit telah dibagikan dengan benar, membutuhkan penggunaan primitif yang lebih kuat yang disebut berbagi rahasia yang dapat diverifikasi secara publik (PVSS).

Beberapa mekanisme pemulihan lain dimungkinkan, tetapi semuanya memiliki batasan yang sama. Jika ada N peserta, dan kami ingin ketahanan jika ada kelompok hingga f node keluar, maka itu harus menjadi kasus bahwa setiap grup Nf peserta dapat menghitung hasil akhir. Tapi itu juga berarti koalisi jahat Nf peserta dapat memprediksi hasilnya terlebih dahulu dengan mensimulasikan mekanisme pemulihan secara pribadi. Ini juga dapat terjadi selama putaran pertama protokol, di mana selama waktu itu koalisi semacam itu dapat mengubah pilihan keacakan mereka sendiri dan membiaskan hasilnya. 

Dengan kata lain, ini berarti koalisi apa pun dari Nf node harus menyertakan setidaknya satu node jujur. Dengan aljabar sederhana, Nf > f, sehingga f < T/2, dan protokol ini secara inheren membutuhkan mayoritas yang jujur. Ini adalah perbedaan yang signifikan dengan model keamanan asli dari commit-reveal, yang hanya membutuhkan f<T (setidaknya satu peserta yang jujur).

Protokol-protokol ini seringkali juga memerlukan biaya komunikasi yang signifikan untuk berbagi informasi PVSS ekstra antara semua node di setiap menjalankan protokol. Komunitas peneliti telah melakukan banyak pekerjaan pada masalah ini dalam beberapa tahun terakhir, dengan proposal penelitian termasuk: Bagikan Rand, Mengikis, DetikRand, HERB, atau Elang laut, tetapi tampaknya tidak ada yang melihat penerapan di dunia nyata.

Protokol berbasis fungsi acak yang dapat diverifikasi

Menyadari bahwa sekelompok Nf peserta dapat menghitung nilai suar acak dalam protokol di atas mengarah ke pendekatan yang lebih sederhana: berbagi kunci rahasia jangka panjang antara N pihak dan minta mereka menggunakannya untuk mengevaluasi fungsi acak yang dapat diverifikasi (VRF). Kunci rahasia dibagikan melalui a t-keluar-N skema ambang batas, sehingga setiap t peserta dapat menghitung VRF (tetapi koalisi yang lebih kecil tidak bisa). Untuk t=Nf, ini memberikan ketahanan yang sama untuk f node berbahaya sebagai protokol commit-reveal-recover yang dibahas di atas.

DFINITY memelopori pendekatan ini sebagai bagian dari protokol konsensus mereka menggunakan tanda tangan ambang batas BLS (yang berfungsi sebagai VRF). mandiri penipuan randomness beacon pada dasarnya menggunakan pendekatan yang sama, dengan satu set peserta ambang batas-BLS-menandatangani counter di setiap putaran. Itu Liga Entropi adalah instance open source dari drand yang menghasilkan keacakan setiap 30 detik menggunakan 16 node yang berpartisipasi (per September 2022), dijalankan oleh gabungan perusahaan dan grup riset universitas. 

Kelemahan dari pendekatan ini adalah bahwa inisialisasi kunci ambang relatif kompleks, seperti konfigurasi ulang kunci ketika node bergabung atau pergi. Namun, dalam kasus umum, protokolnya sangat efisien. 

Seperti dijelaskan di atas, hanya dengan menandatangani nilai penghitung tidak menambah keacakan baru per putaran, jadi jika jumlah kunci peserta yang cukup dikompromikan, maka protokol akan dapat diprediksi di setiap putaran berikutnya.

Rantai Tautan VRF menggabungkan pendekatan ini (menggunakan NSEC5 VRF) dengan sumber keacakan eksternal yang ditentukan oleh pihak yang meminta keacakan, biasanya header blockchain baru-baru ini dalam praktiknya. Data ini kemudian diumpankan melalui VRF yang dijalankan oleh salah satu pihak atau diambangkan ke grup.

Ethereum Rantai Suar saat ini menggunakan VRF berbasis BLS: pengusul setiap putaran menambahkan nilai VRF mereka ke dalam campuran. Ini menghemat putaran komunikasi dibandingkan dengan paradigma commit-reveal (dengan asumsi kunci publik BLS jangka panjang terdaftar satu kali), meskipun desain ini mewarisi beberapa peringatan dari pendekatan commit-reveal termasuk kemungkinan untuk membiaskan output beacon dengan menahan output .

Protokol berbasis fungsi penundaan yang dapat diverifikasi

Akhirnya, arah baru yang menjanjikan adalah menggunakan kriptografi berbasis waktu, khususnya fungsi penundaan yang dapat diverifikasi (VDF). Pendekatan ini menjanjikan untuk memberikan efisiensi dan ketahanan komunikasi yang baik dengan ketahanan terhadap N-1 node berbahaya. 

Kembali ke protokol commit-reveal asli, komitmen tradisional dapat diganti dengan komitmen waktunya untuk menghilangkan masalah peserta yang menolak untuk mengungkapkan kontribusi acak mereka. Komitmen berjangka waktu dapat dibuka secara efisien oleh pembuat asli, atau oleh siapa saja yang bersedia menghitung fungsi lambat (pada dasarnya VDF). Jadi, jika ada peserta yang keluar dari protokol commit-reveal, komitmen mereka masih dapat dibuka oleh orang lain. Sangat penting bahwa waktu minimum untuk membuka komitmen cukup lama sehingga tidak dapat dilakukan selama putaran pertama (fase komit) protokol, jika tidak, peserta jahat dapat membuka komitmen orang lain dengan cukup cepat untuk mengubah kontribusi mereka sendiri dan membiaskan hasilnya .

Protokol satu putaran yang bahkan lebih elegan dimungkinkan dengan VDF modern: batalkan komitmen sepenuhnya. Setiap peserta cukup mempublikasikan kontribusi acak mereka r_i, dan hasil akhir merupakan gabungan dari kontribusi masing-masing peserta, yang dijalankan melalui VDF. Penundaan waktu dalam menghitung VDF memastikan bahwa tidak seorang pun dapat memilih komitmen mereka dengan cara yang membiaskan hasil akhir. Pendekatan ini diusulkan sebagai UNICORN oleh Arjen Lenstra dan Benjamin Wesolowski pada tahun 2015, dan memang merupakan aplikasi motivasi utama dalam pengembangan VDF.

Pendekatan ini telah melihat beberapa penerapan praktis. Chia mengimplementasikan versi ini sebagai bagian dari protokol konsensusnya, menggunakan VDF yang dikuadratkan berulang-ulang dalam grup kelas. Starkware dilaksanakan suar berbasis VDF bukti konsep menggunakan VDF berbasis SNARK. Ethereum juga rencana untuk menggunakan pendekatan ini, membangun ASIC khusus untuk menghitung VDF guna menghasilkan keacakan pada lapisan konsensus.

***

Keacakan publik adalah komponen penting dari banyak protokol, tetapi kami masih kekurangan DRB standar yang memberikan keamanan tinggi. Ruang desainnya besar dan banyak hibrida dan kombinasi dari pendekatan di atas dimungkinkan. Misalnya, dimungkinkan untuk menggabungkan protokol berbasis VRF dengan protokol berbasis VDF, yang menambahkan entropi baru, misalnya, seperti yang diusulkan oleh RandRunner. Beacon Chain Ethereum saat ini menggunakan VRF, meskipun mungkin akan menambahkan VDF di masa mendatang untuk menghilangkan kemungkinan bias dari serangan block withholding.

Ini juga merupakan pertanyaan terbuka ketika protokol mayoritas jujur ​​dapat diterima. Untuk kelompok peserta yang relatif kecil dan terverifikasi – seperti League of Entropy – asumsi mayoritas yang jujur ​​adalah masuk akal. Di sisi lain, protokol yang hanya membutuhkan satu peserta yang jujur ​​memiliki keuntungan yang melekat – lebih banyak peserta hanya dapat meningkatkan keamanan. Ini berarti protokol ini berpotensi dapat digunakan dengan partisipasi terbuka dan tanpa izin.

Pada Bagian II, kita akan membahas penerapan spesifik pemilihan pemimpin secara acak dalam protokol konsensus, yang memiliki tujuan desain yang sedikit berbeda dan sebagai hasilnya telah terlihat lebih banyak protokol dan pendekatan yang diusulkan.

***

Joseph Bonneau adalah Mitra Riset di a16z crypto. Penelitiannya berfokus pada kriptografi terapan dan keamanan blockchain. Dia telah mengajar kursus cryptocurrency di University of Melbourne, NYU, Stanford, dan Princeton, dan menerima gelar PhD dalam ilmu komputer dari University of Cambridge dan gelar BS/MS dari Stanford.

Valeria Nikolaenko adalah Mitra Riset di a16z crypto. Penelitiannya berfokus pada kriptografi dan keamanan blockchain. Dia juga telah mengerjakan topik-topik seperti serangan jarak jauh dalam protokol konsensus PoS, skema tanda tangan, keamanan pasca-kuantum, dan komputasi multi-partai. Dia memegang gelar PhD dalam Kriptografi dari Universitas Stanford di bawah bimbingan Profesor Dan Boneh, dan bekerja di blockchain Diem sebagai bagian dari tim peneliti inti.

***

Editor: Tim Sullivan

***

Pandangan yang diungkapkan di sini adalah pandangan individu AH Capital Management, LLC (“a16z”) yang dikutip dan bukan pandangan a16z atau afiliasinya. Informasi tertentu yang terkandung di sini telah diperoleh dari sumber pihak ketiga, termasuk dari perusahaan portofolio dana yang dikelola oleh a16z. Meskipun diambil dari sumber yang dipercaya dapat dipercaya, a16z belum memverifikasi informasi tersebut secara independen dan tidak membuat pernyataan tentang keakuratan informasi yang bertahan lama atau kesesuaiannya untuk situasi tertentu. Selain itu, konten ini mungkin termasuk iklan pihak ketiga; a16z belum meninjau iklan tersebut dan tidak mendukung konten iklan apa pun yang terkandung di dalamnya.

Konten ini disediakan untuk tujuan informasi saja, dan tidak boleh diandalkan sebagai nasihat hukum, bisnis, investasi, atau pajak. Anda harus berkonsultasi dengan penasihat Anda sendiri mengenai hal-hal itu. Referensi ke sekuritas atau aset digital apa pun hanya untuk tujuan ilustrasi, dan bukan merupakan rekomendasi investasi atau penawaran untuk menyediakan layanan konsultasi investasi. Selanjutnya, konten ini tidak ditujukan atau dimaksudkan untuk digunakan oleh investor atau calon investor mana pun, dan dalam keadaan apa pun tidak dapat diandalkan saat membuat keputusan untuk berinvestasi dalam dana yang dikelola oleh a16z. (Penawaran untuk berinvestasi dalam dana a16z hanya akan dilakukan dengan memorandum penempatan pribadi, perjanjian berlangganan, dan dokumentasi lain yang relevan dari dana tersebut dan harus dibaca secara keseluruhan.) Setiap investasi atau perusahaan portofolio yang disebutkan, dirujuk, atau dijelaskan tidak mewakili semua investasi dalam kendaraan yang dikelola oleh a16z, dan tidak ada jaminan bahwa investasi tersebut akan menguntungkan atau bahwa investasi lain yang dilakukan di masa depan akan memiliki karakteristik atau hasil yang serupa. Daftar investasi yang dilakukan oleh dana yang dikelola oleh Andreessen Horowitz (tidak termasuk investasi yang penerbitnya tidak memberikan izin kepada a16z untuk mengungkapkan secara publik serta investasi yang tidak diumumkan dalam aset digital yang diperdagangkan secara publik) tersedia di https://a16z.com/investments /.

Bagan dan grafik yang disediakan di dalamnya hanya untuk tujuan informasi dan tidak boleh diandalkan saat membuat keputusan investasi apa pun. Kinerja masa lalu tidak menunjukkan hasil di masa depan. Konten berbicara hanya pada tanggal yang ditunjukkan. Setiap proyeksi, perkiraan, prakiraan, target, prospek, dan/atau pendapat yang diungkapkan dalam materi ini dapat berubah tanpa pemberitahuan dan mungkin berbeda atau bertentangan dengan pendapat yang diungkapkan oleh orang lain. Silakan lihat https://a16z.com/disclosures untuk informasi penting tambahan.