Pemilihan Pemimpin dari Suar Keacakan dan Strategi Lainnya

Pemilihan pemimpin dalam pengaturan blockchain bertujuan untuk memilih peserta yang akan menentukan blok selanjutnya yang akan ditambahkan ke blockchain. Biasanya, satu validator dipilih per slot dari kumpulan validator dan berhak untuk memperpanjang rantai dengan blok baru di slot tersebut. (Kami berasumsi bahwa validator menyimpan waktu yang akurat dan menyepakati nomor slot saat ini.) Dalam artikel ini, kami mengeksplorasi strategi untuk pemilihan pemimpin secara acak dalam protokol konsensus. (Untuk informasi lebih lanjut tentang keacakan secara umum, lihat artikel kami sebelumnya, Keacakan Publik dan Suar Keacakan, Di mana kami melihat ke dalam protokol yang berdiri sendiri untuk menghasilkan keacakan yang dapat diverifikasi dan tidak dapat diprediksi secara publik.) 

Mengapa pemilihan pemimpin itu penting

Memilih pemimpin yang jujur ​​dan aktif sangat penting untuk pertumbuhan rantai yang sehat. Validator jahat seharusnya tidak dapat membiaskan proses pemilihan pemimpin untuk menjadikan diri mereka pemimpin lebih sering. Jika tidak, produksi blok dapat jatuh ke tangan pihak yang dapat menyensor transaksi atau menghentikan blockchain sama sekali. Dalam protokol konsensus gaya rantai terpanjang, pemimpin yang menghasilkan blok yang tidak valid (atau tidak ada blok sama sekali) dapat menyebabkan rantai bercabang untuk sementara. Dalam protokol konsensus gaya BFT, pemimpin yang buruk memicu subprotokol perubahan tampilan yang akan menimbulkan overhead komunikasi. 

Alternatif pemilihan panitia

Pemilihan komite adalah masalah yang terkait, di mana tujuannya adalah untuk memilih subset acak yang seragam dari validator dengan ukuran tetap k. Fungsionalitas ini berguna dengan sendirinya karena subkomite sering diperlukan dalam pengaturan blockchain untuk mengurangi ukuran set validator untuk membuat konsensus berjalan lebih cepat (di antara banyak contoh adalah penyortiran Algorand dan Pemilihan komite Ethereum). Tetapi pemilihan panitia juga berguna untuk pemilihan pemimpin, memungkinkan validator untuk menghindari menjalankan kembali protokol pemilihan pemimpin jika pemimpin terpilih tidak hadir. Jika, alih-alih seorang pemimpin, sebuah komite dipilih dengan urutan tetap, anggota komite kedua dapat menjadi pemimpin jika yang pertama tidak ada. 

Sifat protokol pemilu yang baik

Dalam protokol pemilihan pemimpin, pemimpin harus tidak bisa ditebak. Jika seorang penyerang mengetahui siapa pemimpin yang akan datang, itu mungkin meluncurkan serangan Denial of Service (DoS) pada mereka untuk mencegah mereka menerbitkan blok. Penyerang kemudian dapat menjatuhkan pemimpin berikutnya dan seterusnya, membuat blockchain terhenti. Ketidakpastian juga dapat diperkuat untuk memastikan validator sendiri tidak mengetahui kapan akan memimpin, yang mungkin penting untuk pencegahan penyuapan.

Proses pemilihan pemimpin harus memiliki tiga sifat berikut:

• Keadilan: setiap validator yang jujur ​​memiliki probabilitas 1/N untuk dipilih dari satu set N validator (gagasan santai tentang keadilan teori permainan memungkinkan membangun pemilihan pemimpin bahkan di hadapan mayoritas jahat meskipun dengan batas bawah yang tidak konstan pada jumlah putaran).
• Ketidakpastian: musuh tidak mempelajari pemimpin berikutnya sampai beberapa waktu T sebelum pemimpin mengumumkan blok berikutnya.
• Keunikan: tepat satu pemimpin dipilih di setiap slot.

Pemilihan pemimpin rahasia

Pemilihan pemimpin rahasia adalah pemilihan yang tidak terduga T = 0. Dalam proses ini, pemimpin tidak diketahui siapa pun sampai ia menerbitkan blok tersebut. Ini menghilangkan jendela untuk serangan DoS sepenuhnya: sebelum pemimpin mengungkapkan dirinya, penyerang tidak tahu siapa yang harus diserang, menjadikan strategi terbaiknya sebagai tebakan acak. Dan setelah leader memublikasikan bloknya, sudah terlambat untuk menyerang karena leader sudah memenuhi tanggung jawabnya terhadap protokol. 

Gagasan "setelah pemimpin menerbitkan bloknya" sebenarnya adalah penyederhanaan, karena kami tidak memiliki siaran instan di dunia nyata. Penyerang dengan posisi jaringan yang kuat mungkin melihat pemimpin menyiarkan blok terlebih dahulu dan dapat dengan cepat merusak pemimpin, membuat blok yang berbeda, dan menjalankan siaran asli di depan. 

Meskipun ini adalah model penyerang yang sangat kuat, pertahanan telah diusulkan untuk melawannya. Algorand mengusulkan model penghapusan, di mana pemimpin sebenarnya dapat menghapus kunci yang diperlukan untuk menandatangani blok di slotnya sebelum menyiarkannya, jadi sudah sangat terlambat untuk menyerang pada saat pemimpin mengambil tindakan publik. Thaddeus Dryja, Quanquan C. Liu, dan, Neha Narula, tiga peneliti dari MIT Media Lab, diusulkan bahwa pemimpin menghitung VDF di bloknya sebelum menyiarkan, memastikan bahwa penyerang adaptif tidak dapat membangun blok valid alternatif pada waktunya agar diterima untuk slot yang diinginkan.

Metode pemilihan lainnya 

Proses pemilihan pemimpin yang paling sederhana adalah usul, di mana para pemimpin dipilih dalam urutan deterministik. Meskipun pendekatan ini dapat diprediksi dan rentan terhadap serangan DoS, pendekatan ini cocok untuk sistem yang memiliki izin di mana validator memiliki perlindungan DoS yang baik.

Seorang pemimpin juga dapat dipilih dengan menggunakan output dari eksternal suar keacakan, jika tersedia dan dipercaya agar aman. Sayangnya, sulit bagi peserta konsensus untuk menjalankan protokol suar keacakan terdistribusi (DRB) sendiri, karena ini biasanya menganggap gagasan siaran atau konsensus yang andal, yang pada gilirannya memerlukan pemilihan pemimpin lagi, memperkenalkan ketergantungan melingkar.

terbaru pemilihan pemimpin di Ethereum adalah studi kasus yang baik. Setiap pemimpin baru menghitung output Verifiable Randomness Function (VRF) (tanda tangan BLS pada nomor epoch) dan meng-XOR nilainya ke dalam campuran. Nilai campuran pada akhir zaman i mendefinisikan para pemimpin dan subkomite untuk durasi zaman i+2. Pemimpin dan jadwal mereka dapat diprediksi satu zaman sebelumnya (saat ini ~6.4 mnt). Protokol rentan terhadap serangan keadilan, karena pemimpin terakhir dapat memilih untuk mempublikasikan atau menahan kontribusi mereka pada campuran dan dengan demikian memengaruhi hasil pemilihan berikutnya sedikit pun. Jika yang terakhir  k pemimpin berkolusi, mereka mungkin memperkenalkan k  sedikit bias dan membuat pemilihan pengguna jahat lebih mungkin terjadi. Ethereum Foundation secara aktif mengerjakan teknik yang lebih maju untuk pemilihan pemimpin yang akan kita bahas di bawah ini.

pemilihan pemimpin berbasis VRF

Pendekatan lain, dipelopori oleh Algorand, Adalah pemilihan pemimpin berbasis VRF, yang melibatkan setiap validator secara pribadi menghitung output VRF dan memeriksa apakah output berada di bawah ambang batas. Prosedur ini sudah menyaring sebagian besar validator, karena ambang dipilih sedemikian rupa sehingga tidak mungkin jatuh di bawahnya. Beberapa validator yang tersisa mengungkapkan output VRF mereka, dan yang memiliki nilai VRF terendah akan dipilih. Pendekatan ini mencapai ketidakpastian yang sempurna (atau kerahasiaan), tetapi tidak menjamin keunikan. Beberapa validator mungkin tidak menerima pesan dari semua pemimpin potensial dan mungkin menganggap pemimpin yang salah memenangkan pemilihan, menyebabkan validator ini bercabang dari rantai utama. 

Evaluasi VRF diunggulkan secara berkala dengan keluaran suar keacakan untuk membuatnya kurang dapat diprediksi oleh validator sendiri untuk melihat slot mana yang akan mereka pimpin. Properti ini mencegah penyerang yang diam-diam mengkompromikan validator untuk mempelajari slot saat validator akan menjadi pemimpin dan meluncurkan serangan saat validator akan mengumumkan pemblokiran. Pendekatan ini juga membantu mencegah serangan suap, di mana validator membuktikan kepada pihak eksternal bahwa ia akan menjadi pemimpin dalam slot tertentu dan menerima suap sebagai imbalan untuk menyelesaikan beberapa tugas sebagai pemimpin (misalnya memblokir transaksi).

Pendekatan seperti itu, di mana jumlah pemimpin yang dipilih adalah variabel acak, disebut Pemilihan Pemimpin Probabilistik (PLE). PLE dapat mengakibatkan tidak ada pemimpin yang terpilih untuk slot tertentu. Ini sama dengan memilih pemimpin yang jahat atau offline di mana slot pada akhirnya akan dilewati, mengurangi efisiensi protokol konsensus.

Tetapi peringatan terbesar dengan PLE adalah bahwa banyak pemimpin dapat dipilih, memerlukan semacam prosedur pemutusan ikatan. Ikatan menimbulkan risiko pada konsensus, karena validator dengan input yang menang dapat melaporkannya hanya ke separuh jaringan, yang berpotensi menyebabkan ketidaksepakatan pada pemimpin yang dipilih. Selain itu, proses untuk menyelesaikan ikatan dapat memakan waktu dan komunikasi ekstra, sehingga mengganggu efisiensi. Dfinity, dibahas lebih detail di postingan pertama dari seri ini, menggunakan suar keacakan berbasis VRF untuk memilih satu pemimpin; Namun, itu mengorbankan ketidakpastian untuk melakukannya. Idealnya, setiap proses pemilihan pemimpin harus menghindari ikatan sama sekali dan tetap tidak dapat diprediksi, yang membawa kita ke cawan suci area penelitian ini – Pemilihan Pemimpin Rahasia Tunggal.

Pemilihan Pemimpin Rahasia Tunggal 

Tujuan dari Pemilihan Pemimpin Rahasia Tunggal (SSLE) adalah memilih pemimpin unik dari serangkaian validator dengan tetap menjaga keadilan dan ketidakpastian. Protocol Labs mempresentasikan gagasan tersebut sebagai a permasalahan penelitian, dan Dan Boneh, ilmuwan komputer Stanford dan penasihat riset kripto a16z, bersama Saba Eskandarian, Lucjan Hanzlik, dan Nicola Greco, kemudian menawarkan definisi formal SSLE. Properti keunikan ini menghindari risiko konsensus dan biaya efisiensi yang timbul dari prosedur tie-breaking. Konkretnya, Sarah Azouvi, dari Protocol Labs, dan Danielle Cappelletti, dari Politecnico di Torino, Menunjukkan bahwa ketika SSLE digunakan dibandingkan dengan PLE dalam protokol rantai terpanjang, blok dapat diselesaikan secara signifikan lebih cepat (25 persen lebih cepat dengan musuh yang mengendalikan sepertiga saham). Dengan demikian, mengembangkan protokol SSLE praktis merupakan masalah penting.

Dalam pendekatan yang paling umum, yang akan kita sebut berbasis acak (digunakan dalam kertas SSLE asli dan Proposal Ethereum SSLE), setiap validator mendaftarkan a duta paus yang terlihat acak, namun mereka dapat membuktikan milik mereka. Nonce kemudian dikompilasi menjadi daftar. Daftar diacak sedemikian rupa sehingga nonce menjadi tidak terhubung dari validator yang mengirimkannya; yaitu, mengingat daftar yang dikocok, tidak ada musuh yang dapat mengetahui validator mana yang mengajukan nonce. Indeks daftar kemudian dipilih menurut publik suar keacakan, dan pemimpin mengungkapkan dirinya dengan membuktikan bahwa angka pada indeks daftar yang diacak itu adalah milik mereka. 

Karena hanya satu indeks yang dipilih, protokol berbasis pengacakan selalu menghasilkan a unik pemimpin. Karena suar acak dibangun untuk menghasilkan nilai acak yang seragam, protokolnya juga demikian adil: setiap validator memiliki kesempatan yang sama untuk terpilih. Selain itu, jika pengocokan dilakukan dengan benar (yaitu, secara acak secara seragam) dan nonces menjadi tidak dapat ditautkan ke identitas validator, protokol ini juga mencapai tidak dapat diprediksi.

Pengacakan diperlukan karena sementara hanya memilih indeks dari daftar yang tidak diacak berdasarkan suar acak sudah akan memberikan keunikan dan keadilan, ketidakpastian lebih sulit untuk dicapai: Jika musuh mengetahui validator mana yang mengirimkan nonce mana, ia tahu siapa yang mengirimkan nonce pada yang dipilih indeks dan dapat mengidentifikasi pemimpin. 

Dua pendekatan berikut mengocok daftar dengan cara yang berbeda. Yang lebih sederhana adalah Proposal Ethereum SSLE, di mana n validator mengirimkan nonces mereka melalui Tor untuk memutuskan tautan identitas validator dari nonces mereka. Setelah semua validator terdaftar, daftar diacak menggunakan suar keacakan publik, dan validator menjadi pemimpin dalam urutan daftar yang diacak. Meskipun skema ini praktis – pemilihan harus dijalankan hanya sekali per n slot – ketergantungan pada Tor ini mungkin tidak diinginkan (seperti halnya mengandalkan keamanan protokol luar). Selain itu, ini tidak sepenuhnya tidak dapat diprediksi: setelah yang pertama n-1 pemimpin mengungkapkan diri mereka, final nth pemimpin diketahui.

Alih-alih menggunakan Tor, kertas SSLE asli memiliki setiap register validator untuk pemilihan secara berurutan dengan menambahkan nonce ke daftar, mengocok daftar, dan pengacakan ulang nonce. Pengacakan ulang ini berarti bahwa setiap nonce dipetakan ke string baru yang tidak dapat ditautkan sedemikian rupa sehingga validator pemiliknya masih dapat membuktikan kepemilikan nonce yang diacak ulang. Pengacakan ulang membuatnya sehingga musuh tidak dapat mengetahui posisi mana yang berakhir dengan nonce tertentu setelah pengacakan, dengan asumsi setidaknya satu pengacak jujur.

Sementara pendekatan pengocokan berurutan dari kertas SSLE asli menghindari ketergantungan pada Tor dan mencapai properti formal SSLE, itu mahal: setiap kali validator baru mendaftar, mereka harus memposting seluruh daftar yang diacak ke blockchain, mengacak ulang semua nonces, dan memberikan bukti bahwa mereka melakukannya dengan jujur, yang menghasilkan jumlah komunikasi linier per validator. Dengan kumpulan validator yang tidak berubah, ini harus dilakukan (diamortisasi) sekali per pemilihan, karena pemimpin mendaftar ulang setelah mereka mengungkapkan bukti untuk kesalahan tersebut. Makalah ini memberikan tradeoff efisiensi-prediktabilitas yang dapat disesuaikan: kami hanya dapat mengocok sebagian kecil dari daftar, mengurangi biaya, jika kami bersedia mengizinkan sejumlah kecil prediktabilitas. Mencapai keseimbangan yang baik antara efisiensi dan keamanan merupakan tantangan, dan akibatnya, protokol SSLE belum digunakan secara luas dalam praktiknya. 

Mudahnya, pendekatan pengocokan berurutan ini juga dapat digunakan untuk memecahkan masalah pemilihan komite, dengan menggunakan suar acak untuk memilih k indeks yang berbeda dari daftar sebagai anggota komite. Ini adalah pencapaian yang bagus, karena masalahnya tidak mudah diselesaikan dengan pendekatan berbasis VRF, karena menjalankan protokol berbasis VRF probabilistik k kali dapat memilih ukuran komite yang bervariasi tergantung pada keacakan. 

Pendekatan lain untuk SSLE

Pendekatan berbasis acak lainnya adalah Amankan SSLE secara adaptif dari DDH. Konstruksi ini sedikit lebih rumit tetapi mencapai gagasan keamanan yang lebih kuat, melindungi dari serangan musuh adaptif dalam model penghapusan Algorand. Musuh ini adaptif karena dapat memilih validator mana yang akan dikorupsi selama protokol, berlawanan dengan sebelum protokol dimulai. 

Tantangan lebih lanjut dalam SSLE adalah memilih setiap validator dengan probabilitas yang sebanding dengan taruhannya, bukan secara acak. Protokol berbasis pengocokan dapat secara naif mencapai hal ini dengan mengizinkan setiap validator mendaftarkan beberapa nonce: satu nonce untuk setiap unit pasak yang mereka pegang. Namun, biaya pengocokan meningkat secara linier dengan jumlah unit taruhan S, menjadi sangat mahal bahkan untuk distribusi pasak yang realistis. Elegan SSLE berbasis MPC pendekatan memiliki kompleksitas yang meningkat hanya dengan log S, dan itu juga menghindari kebutuhan akan pengaturan tepercaya atau suar keacakan. Namun, dibandingkan dengan pendekatan berbasis pengocokan, ini membutuhkan lebih banyak putaran komunikasi (logaritmik dalam jumlah peserta) per pemimpin terpilih

***

Kami telah merangkum analisis kami dalam tabel praktis ini.

	Keadilan	Ketidakpastian/ Kerahasiaan*	Keunikan
Sistem kompetisi bulat	✓	✗	✓
Suar keacakan yang ideal	✓	✗	✓
Pemilihan pemimpin Ethereum (saat ini)	✗	✗	✓
Pemilihan pemimpin berbasis VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Suar round-robin sepenuhnya dapat diprediksi, tetapi di suar lainnya ✗ berarti bahwa gagasan itu dicapai sampai tingkat terbatas tertentu: mercusuar keacakan ideal tidak dapat diprediksi tetapi musuh mempelajari output pada saat yang sama dengan pemimpin terpilih, maka pemimpin terpilih dapat diserang sebelum mengumumkan blok; Suar Etherum tidak dapat diprediksi hingga ~6 mnt dan dapat sedikit bias untuk merusak keadilan; Algorand memilih banyak pemimpin dengan probabilitas kecil.

SSLE adalah arah yang menjanjikan, mencapai keadilan, ketidakpastian, dan keunikan. Dua tantangan utama yang dihadapi pengadopsiannya adalah efisiensi dan kemampuan untuk mengakomodasi distribusi pasak yang tidak seragam. Selain itu, pendekatan SSLE berbasis pengacakan yang kami soroti mengasumsikan adanya suar acak yang tidak bias, yang tidak mudah dicapai dalam praktiknya. Karena SSLE baru saja didefinisikan secara formal, kami kemungkinan akan melihat protokol yang lebih baik untuk mengatasi tantangannya dalam waktu dekat. 

***

Miranda Kristus adalah seorang mahasiswa PhD dalam Ilmu Komputer di Universitas Columbia, di mana dia adalah anggota Theory Group dan Presidential Fellow. Dia juga magang penelitian di a16z crypto.

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.