Cicada memiliki properti privasi baru, meminimalkan asumsi kepercayaan, dan cukup efisien untuk digunakan di mainnet Ethereum.
**Ditulis oleh:**Michael Zhu
Disusun oleh: Lynn, MarsBit
Semua sistem pemungutan suara yang berfungsi dengan cara apa pun yang berarti bergantung pada integritas dan transparansi. Sepintas lalu, hal ini membuat blockchain menjadi platform yang ideal untuk membangun sistem ini – memang, banyak organisasi terdesentralisasi telah menggunakan pemungutan suara tanpa izin sebagai sarana untuk mengekspresikan niat kolektif, seringkali menggunakan kekayaan yang sangat besar atau mengutak-atik parameter protokol utama dalam kasus tersebut. Tapi pemungutan suara on-chain juga memiliki kelemahan: Privasi masih belum dijelajahi dan dikembangkan, yang tidak baik untuk sistem pemungutan suara Web3—di sebagian besar protokol pemungutan suara on-chain yang saat ini digunakan, surat suara dan hasil pemungutan suara sepenuhnya terbuka untuk umum. Tanpa privasi, hasil pemungutan suara dapat dengan mudah dimanipulasi dan insentif pemilih tidak selaras, berpotensi mengarah pada hasil yang tidak demokratis.
Itulah sebabnya kami merilis Cicada: pustaka Soliditas sumber terbuka baru yang memanfaatkan teka-teki timelock dan bukti tanpa pengetahuan untuk mengaktifkan pemungutan suara pribadi secara berantai. Dibandingkan dengan sistem yang ada, Cicada memiliki properti privasi baru, meminimalkan asumsi kepercayaan, dan cukup efisien untuk digunakan di mainnet Ethereum.
Dalam posting ini, kami mensurvei status privasi pemungutan suara dan memberikan deskripsi tingkat tinggi tentang cara kerja Cicada (bukti formal akan segera hadir). Kami juga mendorong pengembang untuk memeriksa repositori GitHub - Cicada dapat diubah dan diperluas dalam banyak cara untuk mendukung skema dan fitur pemungutan suara yang berbeda, dan kami berharap dapat bekerja sama dengan komunitas untuk mengeksplorasi kemungkinan ini.
Survei Singkat Polling Pribadi
Dalam sistem pemungutan suara apa pun (on-chain atau lainnya), ada banyak tingkat privasi berbeda yang perlu dipertimbangkan. Pengungkapan surat suara individu, penghitungan berjalan, dan identitas pemilih semuanya memengaruhi motivasi pemilih dengan cara yang berbeda. Properti privasi mana yang diperlukan tergantung pada konteks pemungutan suara. Beberapa yang sering muncul dalam kriptografi dan literatur ilmu sosial:
- Privasi Surat Suara: Surat suara rahasia, juga dikenal sebagai “surat suara Australia”, dikembangkan untuk sistem pemungutan suara dunia nyata sebagai cara untuk mempertahankan preferensi pemilih individu dan mengurangi penyuapan dan paksaan (diatur secara berantai, kami mungkin memerlukan properti yang lebih kuat daripada surat suara privasi - lihat “ketidakterimaan” di bawah). Privasi suara juga dapat mengurangi bias keinginan sosial — seseorang memiliki lebih sedikit tekanan untuk memilih berdasarkan pendapat orang lain tentang pilihan mereka.
- Privasi penghitungan yang sedang berlangsung: Banyak sistem pemungutan suara menyembunyikan penghitungan yang sedang berlangsung, atau berapa banyak suara yang telah diberikan untuk setiap opsi, saat pemilih masih memberikan suara, untuk menghindari pengaruh jumlah pemilih dan insentif pemilih. Kami telah melihat ini terjadi di dunia nyata; misalnya, senator AS yang memberikan suara belakangan lebih cenderung sejalan dengan partainya daripada senator yang memilih lebih awal. Dan on-chain: dalam pemungutan suara berbobot token, paus dapat membuai lawan mereka ke dalam rasa aman yang salah dengan membuat mereka tetap di depan (beberapa mungkin terlalu malas untuk memilih, dengan asumsi mereka tetap akan menang), dan kemudian memberikan suara mereka sendiri di menit terakhir Datang dan putuskan hasilnya.
- Anonimitas pemilih: Dalam banyak sistem pemungutan suara dunia nyata, suara Anda tidak bersifat publik, tetapi fakta bahwa Anda memberikan suara sering kali bersifat publik. Ini penting untuk mencegah penipuan pemilih, karena penerbitan catatan pemilih memungkinkan orang untuk memeriksa apakah orang lain telah memberikan suara atas nama mereka. Namun, secara on-chain, kami dapat mencegah penipuan pemilih sembari mempertahankan anonimitas menggunakan kriptografi primitif—misalnya, dengan Semaphore, Anda dapat membuktikan tanpa pengetahuan bahwa Anda adalah pemilih sah yang belum memberikan suara.
- Tidak Dapat Diterima: Pemilih individu memberikan “tanda terima” surat suara mereka untuk membuktikan bagaimana mereka memberikan suara kepada pihak ketiga, yang jika tidak dapat mengakibatkan penjualan tiket. Properti yang terkait erat tetapi lebih kuat adalah resistensi paksaan, yang mencegah seseorang memaksa pemilih untuk memilih dengan cara tertentu. Properti ini sangat menarik di lingkungan yang terdesentralisasi, di mana hak suara dapat dibuat likuid melalui pasar kontrak pintar. Sayangnya, mereka juga sulit diimplementasikan—pada kenyataannya, Juels et al.menunjukkan, tidak mungkin dalam lingkungan tanpa izin tanpa perangkat keras tepercaya.
Cicada berfokus pada privasi penghitungan suara yang sedang berlangsung, tetapi (seperti yang akan kita bahas nanti) ini dapat digabungkan dengan bukti keanggotaan kelompok tanpa pengetahuan untuk mencapai anonimitas pemilih dan privasi surat suara.
Memperkenalkan Cicada: Privasi Penghitungan Suara dari Masalah Timelock Homomorfik
Untuk mencapai privasi penghitungan suara yang sedang berlangsung, Cicada memanfaatkan primitif kriptografi yang (setahu kami) belum pernah digunakan secara on-chain sebelumnya.
Pertama, teka-teki pengunci waktu (Rivest, Shamir, Wagner, 1996) adalah teka-teki terenkripsi yang merangkum rahasia yang hanya dapat diungkapkan setelah beberapa waktu yang telah ditentukan berlalu — lebih khusus lagi, teka-teki itu dapat diulang dengan melakukan beberapa non- perhitungan paralel untuk mendekripsi. Teka-teki yang dikunci waktu berguna dalam konteks pemungutan suara untuk mencapai privasi dalam menjalankan statistik: pengguna dapat mengirimkan suara mereka sebagai teka-teki yang dikunci sehingga dirahasiakan selama proses pemungutan suara tetapi dapat diungkapkan setelah pemungutan suara. Tidak seperti kebanyakan struktur pemungutan suara swasta lainnya, ini memungkinkan privasi statistik untuk beroperasi tanpa bergantung pada lembaga statistik (seperti petugas pemilu yang menghitung kertas atau surat suara digital), enkripsi ambang batas (beberapa pihak tepercaya harus bekerja sama untuk mendekripsi pesan), atau pihak tepercaya lainnya: Siapa pun dapat memecahkan teka-teki timelock untuk memastikan hasilnya terungkap setelah pemungutan suara.
Kedua, teka-teki timelock isomorfik (Malavolta Thyagarajan, 2019) memiliki properti tambahan yang memungkinkan beberapa perhitungan pada nilai terenkripsi dengan pengetahuan tentang kunci rahasia, dekripsi teka-teki, atau penggunaan pintu belakang. Secara khusus, teka-teki timelock homomorfik linier memungkinkan kita menggabungkan teka-teki bersama untuk menghasilkan teka-teki baru yang merangkum jumlah nilai rahasia dari teka-teki asli.
Seperti yang ditunjukkan oleh penulis makalah, teka-teki timelock homomorfik linier adalah primitif yang sangat cocok untuk pemungutan suara pribadi: suara dapat dikodekan sebagai teka-teki, dan teka-teki tersebut dapat digabungkan secara homomorfik untuk mendapatkan Teka-Teki Penghitungan akhir yang disandikan. Artinya, hanya diperlukan satu perhitungan untuk mengungkapkan hasil akhir, daripada memecahkan teka-teki unik untuk setiap suara.
Struktur baru: efisiensi dan pengorbanan
Ada beberapa masalah yang perlu dipertimbangkan agar skema pemungutan suara menjadi praktis secara on-chain. Pertama, penyerang mungkin mencoba memanipulasi suara dengan memberikan surat suara yang tidak dikodekan dengan benar. Misalnya, kita mungkin ingin teka-teki timelock untuk setiap surat suara dikodekan sebagai nilai boolean: “1” untuk proposal yang dipilih, dan “0” untuk no. Seorang pendukung proposal yang bersemangat mungkin mencoba membuat kode seperti “100” untuk memperluas kekuatan pemungutan suara efektif mereka.
Kami dapat mencegah serangan ini dengan meminta pemilih menyerahkan bukti tanpa pengetahuan tentang validitas suara bersama dengan suara itu sendiri. Namun, bukti tanpa pengetahuan mahal secara komputasi—untuk menjaga biaya partisipasi pemilih serendah mungkin, bukti harus (1) dapat dihitung secara efisien di sisi klien dan (2) secara on-chain dapat diverifikasi secara efisien.
Untuk membuat pembuktian seefisien mungkin, kami menggunakan protokol sigma khusus—bukti tanpa pengetahuan yang dirancang untuk hubungan aljabar tertentu, bukan sistem pembuktian umum. Hal ini membuat waktu pembuktian menjadi sangat cepat: membuat bukti validitas surat suara dengan Python membutuhkan waktu 14 ms pada laptop siap pakai.
Meskipun validator untuk protokol sigma secara konseptual sederhana, ia membutuhkan eksponensial modular dalam jumlah yang cukup besar. Skema homomorfik linier Malavolta dan Thyagarajan menggunakan enkripsi Paillier, sehingga eksponensial ini akan melakukan modulo N^2 untuk beberapa RSA modulo N. Untuk ukuran N yang masuk akal, eksponensial sangat mahal (jutaan gas) pada sebagian besar rantai EVM. Untuk mengurangi biaya, Cicada menggunakan ElGamal Eksponensial - ElGamal Eksponensial masih memberikan homomorfisme aditif, tetapi bekerja pada moduli yang lebih kecil (N alih-alih N^2).
Salah satu kelemahan menggunakan ElGamal adalah bahwa langkah terakhir untuk mendekripsi hitungan memerlukan bruteforcing log diskrit (perhatikan bahwa ini dilakukan secara off-chain dan diverifikasi secara efektif secara on-chain). Oleh karena itu, ini hanya berfungsi jika jumlah suara akhir yang diharapkan cukup kecil (katakanlah kurang dari 2^32, atau sekitar 4,3 juta suara). Dalam skema berbasis Paillier asli, hitungan dapat didekripsi secara efisien terlepas dari ukurannya.
Memilih modulus N RSA juga melibatkan pertukaran. Implementasi kami menggunakan modulus 1024-bit untuk efisiensi gas. Meskipun ini jauh di atas modulus RSA terbesar yang pernah difaktorkan secara publik (829 bit), ini di bawah ukuran 2048 bit yang biasanya direkomendasikan untuk enkripsi atau penandatanganan RSA. Namun, aplikasi kami tidak memerlukan keamanan jangka panjang: setelah pemilihan selesai, tidak ada risiko jika N dipertimbangkan di masa mendatang. Masuk akal untuk menggunakan modulus yang relatif kecil, dengan asumsi bahwa penghitungan dan suara diumumkan setelah timelock berakhir. (Ini juga dapat dengan mudah diperbarui di masa mendatang jika algoritme dekomposisi meningkat.)
Anonimitas dan Kelayakan Pemilih
Seperti disebutkan di atas, Cicada menyediakan privasi penghitungan suara - properti teka-teki yang dikunci waktu yang menjaga kerahasiaan penghitungan suara selama pemungutan suara. Namun, setiap surat suara juga merupakan teka-teki timelock, dienkripsi di bawah parameter publik yang sama. Ini berarti bahwa sama seperti hitungan dapat didekripsi (dengan melakukan perhitungan yang diperlukan), demikian juga setiap suara. Dengan kata lain, Cicada menjamin privasi surat suara hanya selama pemungutan suara — jika pengamat yang penasaran ingin mendekripsi surat suara pemilih tertentu, mereka dapat melakukannya. Mendekripsi setiap surat suara sama mahalnya dengan mendekripsi penghitungan akhir, jadi secara naif dibutuhkan O(n) usaha untuk mendekripsi sepenuhnya surat suara dengan n pemilih. Tetapi semua suara ini dapat didekripsi secara paralel (dengan asumsi ada cukup mesin), mengambil waktu jam dinding yang sama dengan yang diperlukan untuk mendekripsi penghitungan akhir.
Untuk beberapa suara, ini mungkin tidak diinginkan. Meskipun kami senang menjalankan privasi penghitungan suara untuk sementara, kami mungkin menginginkan privasi pemungutan suara tanpa batas waktu. Untuk mencapai ini, kami dapat menggabungkan Cicada dengan protokol kelayakan pemilih anonim, yang dibuat dengan bukti keanggotaan kelompok tanpa pengetahuan. Dengan begitu, meskipun surat suara dideklasifikasi, yang terungkap hanyalah bahwa seseorang memilih seperti itu - dan kita sudah mengetahuinya dari hitungan.
Dalam repositori kami, kami menyertakan contoh kontrak yang menggunakan Semaphore untuk anonimisasi pemilih. Perhatikan, bagaimanapun, bahwa kontrak Cicada itu sendiri tidak membuat asumsi tentang bagaimana kelayakan pemilih ditentukan atau ditegakkan. Secara khusus, Anda dapat mengganti Semaphore dengan misalnya Semacaulk atau ZK Proof of State (seperti yang disarankan di sini dan di sini).
Otoritas Statistik
Salah satu prioritas pertama kami dalam merancang Cicada adalah untuk menghindari kebutuhan akan badan statistik: banyak struktur pemungutan suara swasta memerlukan badan statistik semi-tepercaya (atau komite yang didelegasikan, dikoordinasikan melalui penghitungan multi-partai yang aman) untuk menerima dan mengumpulkan suara. Dalam konteks blockchain, ini berarti bahwa skema ini tidak dapat dijalankan hanya dengan kontrak pintar, membutuhkan intervensi dan kepercayaan manusia.
Di sebagian besar struktur, otoritas penghitungan tidak dipercaya untuk integritas (mereka tidak dapat memanipulasi penghitungan suara), tetapi dipercaya untuk liveness - jika mereka offline, mereka tidak dapat menghitung hasil akhir, menunda pemungutan suara tanpa batas. Dalam beberapa struktur, mereka juga dipercaya untuk menjaga privasi—yaitu, mereka tahu bagaimana setiap individu memberikan suara, tetapi diharapkan untuk mempublikasikan hasil pemungutan suara tanpa mengungkapkan informasi ini.
Sementara otoritas statistik adalah asumsi yang masuk akal (dan perlu) dalam banyak skenario dunia nyata, mereka tidak ideal dalam lingkungan blockchain, di mana tujuan kami adalah untuk meminimalkan kepercayaan dan memastikan penolakan sensor.
Cicada menjelajahi salah satu dari banyak arah di bidang privasi voting on-chain dan melengkapi banyak penelitian yang dilakukan oleh kelompok lain. Seperti disebutkan di atas, Cicada terkait erat dengan teknologi keanggotaan grup anonim seperti semaphore, ZK proof-of-storage, dan rate-limit invalidators. Cicada juga dapat mengintegrasikan pemeriksa bukti optimis yang diusulkan oleh tim Nouns Vortex untuk mengurangi beban gas para pemilih.
Ada juga kesempatan untuk mengadaptasi Cicada untuk mendukung skema voting yang berbeda (misalnya voting token-weighted, voting kuadrat) - skema yang lebih kompleks mungkin terlalu mahal secara komputasi untuk mainnet Ethereum, tetapi mungkin praktis di L2. Dengan mengingat hal ini, kami menyambut kontribusi, garpu, dan saran Anda tentang ke mana harus membawa Cicada selanjutnya.
*Ucapan Terima Kasih: Cicada dikembangkan bersama dengan Joseph Bonneau. Terima kasih kepada Andrew Hall untuk informasi latar belakang tentang latar belakang sejarah privasi pemungutan suara. Terima kasih juga kepada Robert Hackett atas umpan baliknya pada artikel ini. Terima kasih khusus kepada Stephanie Zinn untuk penyuntingan. *
