Keamanan dan Kinerja SNARK

SNARK (Succinct Non-interactive Argument of Knowledge) adalah alat kriptografi yang membuka kemungkinan baru yang menarik dalam desain sistem, terutama dalam pengaturan terdesentralisasi. SNARK memungkinkan data diproses oleh entitas yang tidak dipercaya, yang kemudian dapat membuktikan bahwa data tersebut valid dan telah diproses dengan benar. Cara yang naif untuk membuktikannya adalah dengan mempublikasikan data, memungkinkan siapa saja yang ingin memeriksa validitasnya dan memprosesnya secara langsung. 

SNARK mencapai efek yang sama, tetapi dengan biaya yang lebih baiks ke validator. Misalnya, dalam rollup yang dapat diverifikasi lapisan-dua (L2), layanan rollup memproses transaksi blockchain. Layanan secara berkala memposting saldo akun penggunanya ke blockchain layer-one. Setiap kali memposting pembaruan ke saldo, itu menambahkan bukti SNARK bahwa ia mengetahui urutan transaksi valid yang mengubah saldo akun lama menjadi yang diperbarui. Dengan cara ini, validator blockchain tidak perlu bekerja keras untuk memeriksa validitas transaksi (misalnya, memeriksa tanda tangan digital untuk setiap transaksi) atau secara eksplisit memproses transaksi untuk menghitung saldo yang diperbarui.  

My sebelumnya pasca berfokus pada kinerja SNARK Provers – penentu utama penerapan SNARK. Meskipun menjalankan SNARK Prover bisa menjadi komputasi intensif, sejauh mungkin tidak mungkin untuk menghasilkan bukti untuk perhitungan skala besar, verifikasi SNARK biasanya jauh lebih murah daripada memeriksa dan memproses data secara langsung. Namun, biaya verifikasi SNARK sangat bervariasi. Posting ini membongkar biaya-biaya ini dan membandingkan properti keamanan dari SNARK yang berbeda. 

Secara khusus, saya menjelaskan bahwa dalam SNARK praktis dengan keamanan pasca-kuantum yang masuk akal (PQ-SNARK), ada ketegangan yang signifikan antara biaya keamanan dan verifikasi. Selain itu, dalam beberapa kasus, ketegangan ini saat ini sedang diselesaikan dengan mengutamakan biaya verifikasi daripada keamanan.

Agar SNARK menyadari potensinya, sistem yang digunakan harus aman dan pengguna harus yakin dengan keamanannya. Saya menyimpulkan posting dengan mengusulkan tindakan sederhana yang dapat dilakukan komunitas web3 untuk membantu memastikan properti ini bertahan untuk jangka panjang. 

Langkah-langkah keamanan kuantitatif 

Sebuah SNARK aman jika secara komputasi tidak layak untuk menghasilkan bukti yang meyakinkan dari pernyataan yang salah. Misalnya, dalam konteks rollup L2, penyerang yang ingin mencuri dana saya ingin membuktikan pernyataan palsu dalam formulir: “Saya mengetahui transaksi yang ditandatangani secara digital yang mentransfer semua aset Justin ke akun saya sendiri.” 

Tingkat keamanan SNARK diukur dengan jumlah pekerjaan yang harus dilakukan untuk menemukan bukti yang meyakinkan dari pernyataan palsu. Mirip dengan primitif kriptografi lainnya seperti tanda tangan digital, logaritma dari jumlah pekerjaan ini disebut sebagai "bit keamanan." Misalnya, keamanan 30 bit menyiratkan bahwa 2³⁰ 1 miliar "langkah kerja" diperlukan untuk menyerang SNARK. Ini secara inheren merupakan ukuran perkiraan keamanan dunia nyata karena gagasan tentang satu langkah kerja dapat bervariasi, dan pertimbangan praktis seperti persyaratan memori atau peluang untuk paralelisme tidak dipertimbangkan.

Dan yang kualitatif

Sedikit keamanan adalah kuantitatif ukuran keamanan SNARK. SNARK juga berbeda dalam kualitatif properti keamanan. 

Misalnya, beberapa SNARK memerlukan upacara penyiapan tepercaya untuk menghasilkan kunci pembuktian terstruktur. SNARK yang tidak memerlukan pengaturan tepercaya sama sekali disebut transparan. 

Agar SNARK yang tidak transparan aman, biasanya setidaknya satu peserta dalam upacara harus berperilaku jujur, artinya mereka membuat dan kemudian membuang “pintu jebakan” yang, jika digabungkan dengan pintu jebakan semua peserta lainnya, akan memudahkan untuk menemukan "bukti" SNARK yang meyakinkan dari setiap pernyataan palsu. Pengaturan tepercaya adalah makhluk menjalankan dengan ratusan atau ribuan peserta untuk membuat asumsi ini seringan mungkin. 

SNARK juga berbeda dalam kerentanannya terhadap serangan kuantum. Secara khusus, banyak SNARK (misalnya, Groth16, PlonK, Marlin, Anti peluru, Nova) bergantung pada asumsi bahwa logaritma diskrit sulit untuk dihitung (dan dalam beberapa kasus, asumsi tambahan juga). Menghitung logaritma diskrit adalah sesuatu yang dapat dilakukan komputer kuantum secara efisien. Oleh karena itu, SNARK ini tidak aman pasca-kuantum (non-PQ). 

Sementara upaya mendesak sedang dilakukan untuk beralih ke pasca-kuantum skema enkripsi, ini terutama didorong oleh kebutuhan untuk menjaga kerahasiaan pesan terenkripsi beberapa dekade ke depan. Musuh yang menyimpan pesan yang dicegat hari ini dan menunggu komputer kuantum tiba, katakanlah, lima puluh tahun, dapat menggunakan komputer untuk mendekripsi pesan berusia lima puluh tahun. Situasi dengan SNARK sangat berbeda. Penggunaan SNARK non-PQ hari ini seharusnya tidak membahayakan keamanan blockchain lima puluh tahun ke depan, bahkan jika komputer kuantum tiba pada saat itu. 

Komitmen polinomial

Semua SNARK menggunakan primitif kriptografi yang dikenal sebagai a skema komitmen polinomial, dan komponen ini sering menjadi penghambat kinerja. (Untuk detailnya, lihat my sebelumnya pasca.) Selain itu, transparansi SNARK dan keamanan pasca-kuantum yang masuk akal ditentukan semata-mata oleh skema komitmen polinomial yang digunakannya. 

Salah satu contoh yang menonjol adalah apa yang disebut Komitmen polinomial KZG, yang digunakan oleh PlonK, Marlin, dan banyak lagi. Komitmen KZG tidak transparan atau aman pasca-kuantum. Skema komitmen lainnya transparan tetapi tidak pasca-kuantum, termasuk Anti peluru, hyrax, dan Perahu nelayan. 

Skema lain masih transparan dan masuk akal pasca-kuantum. Ini termasuk GRATIS, Ringan, Liga++, Pengereman, dan Orion. Semua skema ini didasarkan pada kode koreksi kesalahan. Hashing adalah satu-satunya primitif kriptografi yang mereka gunakan. Mereka juga berbagi properti berikut: biaya verifikasi (diukur dengan jumlah evaluasi hash dan operasi lapangan) tumbuh secara linier dengan jumlah bit keamanan.

Secara kasar, satu "iterasi" dari komitmen polinomial pasca-kuantum ini hanya mencapai sejumlah kecil (katakanlah 2-4) bit keamanan. Jadi protokol harus diulang berkali-kali untuk "memperkuat" tingkat keamanan, dengan biaya verifikasi yang meningkat setiap pengulangan. Dengan demikian, untuk mengontrol biaya verifikasi di PQ-SNARK (dan karenanya biaya gas dalam aplikasi blockchain) perancang protokol diberi insentif untuk menjaga tingkat keamanan tetap rendah. 

Dengan langka pengecualian, ketegangan antara keamanan konkret dan biaya verifikasi ini tidak muncul dalam SNARK non-PQ (transparan dan non-transparan). Non-PQ-SNARK menggunakan grup kurva eliptik di mana logaritma diskrit dianggap sulit untuk dihitung, dan tingkat keamanannya ditentukan oleh grup yang digunakan. Ukuran grup kurva eliptik yang sesuai, dan karenanya biaya setiap operasi grup, tumbuh dengan tingkat keamanan yang diinginkan. Namun, jumlah unsur-unsur golongan dalam suatu pembuktian tidak tergantung pada pilihan golongan. 

Dalam PQ-SNARK, ukuran evaluasi hash tidak hanya tumbuh secara linier dengan tingkat keamanan yang diinginkan, begitu juga jumlah evaluasi yang disertakan dalam pembuktian dan dilakukan oleh verifikator. 

Biaya dan keamanan pemverifikasi konkret dalam SNARK yang diterapkan

Biaya verifikasi konkret dan tingkat keamanan SNARK yang digunakan sangat bervariasi. Berikut adalah beberapa contoh ilustrasi:

Biaya pemeriksa 

My sebelumnya pasca menyebutkan dua contoh biaya verifikasi konkret: PlonK biaya bukti bawah 300,000 bensin untuk memverifikasi di Ethereum, sementara bukti StarkWare menghabiskan sekitar 5 juta gas. Bukti StarkWare transparan dan masuk akal pasca-kuantum sedangkan bukti PlonK tidak. Namun, seperti yang dijelaskan selanjutnya, bukti StarkWare dijalankan pada tingkat keamanan yang jauh lebih rendah daripada bukti PlonK di Ethereum.

Keamanan beton

Satu-satunya kurva eliptik dengan prekompilasi Ethereum disebut altbn128, jadi ini adalah kurva semua SNARK non-PQ yang digunakan pada penggunaan Ethereum, termasuk Aztecdan zkSync's. Kurva ini — dan karenanya juga SNARK yang digunakan yang menggunakannya — pada awalnya diyakini menawarkan keamanan sekitar 128 bit. Tapi karena serangan yang ditingkatkan (runtime tepatnya adalah sulit untuk menentukan), kurva sekarang secara luas dianggap menawarkan keamanan 100 hingga 110 bit. 

Ada EIP bawah pertimbangan untuk memperkenalkan prakompilasi untuk kurva berbeda yang masih diyakini menawarkan keamanan hampir 128 bit. Kurva seperti itu adalah sudah digunakan di SNARK proyek non-Ethereum termasuk ZCash, Algorand, Dfinity, Filecoin, dan Aleo. 

Sebaliknya, menurut data on-chain, PQ-SNARK StarkWare (dalam apa yang disebut sistem SHARP, kependekan dari SHARed Prover) telah dikonfigurasi untuk menargetkan keamanan 80 bit. Tingkat keamanan ini berlaku di bawah dugaan tertentu tentang kesehatan statistik FRI (yang akan saya bahas nanti di posting ini). 

Istilah "keamanan 80 bit" tidak jelas dalam konteks ini, jadi izinkan saya membongkarnya. Secara kasar, itu berarti penyerang dapat menghasilkan bukti yang meyakinkan dari pernyataan yang salah dengan mengevaluasi fungsi hash⁸⁰ kali (yaitu KECCAK-256, fungsi hash yang digunakan oleh Ethereum). Lebih tepatnya, penyerang yang bersedia melakukan 2^k evaluasi hash dapat menghasilkan bukti yang meyakinkan dengan probabilitas kira-kira 2^k-80. Misalnya dengan 2⁷⁰ evaluasi hash, seseorang dapat menemukan "bukti" SNARK dari pernyataan yang salah dengan probabilitas sekitar 2^-10 = 1/1024. 

Gagasan ini lebih lemah dari apa yang dimaksud dengan istilah "keamanan 80 bit" dalam konteks lain. Misalnya, fungsi hash tahan benturan (CRHFs) yang dikonfigurasi untuk keamanan 80 bit akan menghasilkan keluaran 160-bit. Jika fungsi hash dirancang dengan baik, prosedur penemuan tabrakan tercepat adalah: Serangan ulang tahun, prosedur brute-force yang dapat menemukan tabrakan dengan sekitar 2^160/2 = 2⁸⁰ evaluasi hash. Namun, dengan 2^k evaluasi hash, serangan Ulang Tahun akan menemukan tabrakan dengan probabilitas hanya 2^2k-160. 

Misalnya, 2⁷⁰ evaluasi hash akan menghasilkan tabrakan dengan probabilitas 2^-20  1/1,000,000. Ini jauh lebih kecil daripada kemungkinan 1/1,000 penyerang memalsukan bukti PQ-SNARK yang dikonfigurasi untuk keamanan 80 bit. 

Perbedaan ini secara drastis dapat mengubah daya tarik melakukan serangan. Sebagai ilustrasi, bayangkan seorang penyerang memiliki anggaran sebesar $100K, yang dapat membeli 2⁷⁰ evaluasi hash. Dan seandainya penyerang berhasil, bayarannya adalah $200 juta. Nilai yang diharapkan dari serangan terhadap PQ-SNARK yang dikonfigurasi untuk keamanan 80 bit adalah (1/1,000) * $200 juta, atau $200K – dua kali lipat biayanya. Jika probabilitas keberhasilan hanya 1/1,000,000, seperti halnya CRHF, nilai serangan yang diharapkan hanya $200. 

Kedua gagasan tentang "keamanan 80 bit" juga berbeda secara dramatis dalam ketahanannya terhadap serangan independen. Misalnya, 1,000 pihak independen masing-masing menyerang PQ-SNARK dengan melakukan 2⁷⁰ evaluasi hash. Karena masing-masing berhasil dengan probabilitas sekitar 1/1,000, setidaknya salah satu dari mereka sangat mungkin berhasil. Ini tidak akan terjadi jika masing-masing berhasil dengan probabilitas hanya 1/1,000,000.

Grup kurva eliptik yang dirancang dengan baik diharapkan berperilaku serupa dengan CRHF, dengan serangan seperti ulang tahun seperti Algoritma rho Pollard menjadi yang paling dikenal. Ini berarti bahwa dalam grup yang menawarkan keamanan 128 bit, 2^k operasi grup harus menghasilkan solusi untuk sebuah instance dari masalah logaritma diskrit dengan probabilitas hanya 2^2k-256. Misalnya, 2⁷⁰ operasi grup akan menemukan logaritma diskrit dengan hanya probabilitas astronomis kecil 2^-116. Selain itu, setiap operasi kelompok lebih lambat dari evaluasi CRHF. 

Berapa banyak evaluasi hash yang layak hari ini?

Pada Januari 2020, biaya komputasi hanya 2⁶⁴ Evaluasi SHA-1 menggunakan GPU adalah $45,000. Ini menempatkan biaya 2⁷⁰ Evaluasi SHA-1 pada GPU dengan harga beberapa juta dolar (mungkin lebih rendah setelah penggabungan Ethereum, karena transisi dari proof of work mining yang didominasi GPU kemungkinan akan menurunkan permintaan untuk komputasi GPU, menurunkan biayanya). 

Dengan pembatalan validitas yang telah menyimpan ratusan juta dolar dana pengguna, menemukan bukti yang meyakinkan dari pernyataan palsu dapat menghasilkan keuntungan jutaan dolar. Mengonfigurasi PQ-SNARK pada keamanan 80 bit di bawah dugaan agresif menyisakan ruang gerak di bawah 10 bit antara serangan yang menguntungkan dan keamanan dugaan PQ-SNARK.

Sebagai titik data lainnya, tingkat hash jaringan Bitcoin saat ini sekitar 2⁶⁴  evaluasi hash per detik, artinya penambang bitcoin secara keseluruhan melakukan 2⁸⁰ Evaluasi SHA-256 setiap 18 jam. Tentu saja, angka yang menakjubkan ini disebabkan oleh investasi besar di ASIC untuk penambangan bitcoin. 

Dengan asumsi enam blok bitcoin dibuat per jam, dan diberi hadiah blok saat ini sebesar 6.25 Bitcoin per blok, 2 . ini⁸⁰ Evaluasi SHA-256 mungkin memakan biaya kurang dari $22,000 * 18 * 6 * 6.25 $15 juta. Jika tidak, penambangan bitcoin tidak akan menguntungkan dengan harga saat ini. 

Tindakan yang diusulkan untuk ekosistem yang sehat

Inti dari penggunaan SNARK dalam rollup adalah untuk mencapai skalabilitas blockchain tanpa pengguna harus mempercayai layanan rollup secara membabi buta. Karena layanan rollup menulis kontrak pintar yang berfungsi sebagai pemverifikasi SNARK, publik harus dapat memeriksa kontrak dan mengonfirmasi bahwa itu memang memverifikasi bukti SNARK dari pernyataan yang sesuai. Pengawasan publik terhadap kontrak pintar mungkin juga diperlukan untuk memastikan bahwa layanan rollup tidak dapat menyensor penggunanya sendiri. Metode yang diusulkan untuk ketahanan sensor memerlukan kontrak pintar rollup untuk memungkinkan pengguna memaksa penarikan dana mereka jika layanan rollup gagal memproses transaksi mereka. 

Mengingat sifat protokol ini yang canggih, paradigma pengawasan publik ini membebani para ahli untuk secara terbuka dan terus terang membahas keamanan kontrak yang diterapkan. 

Tetapi dengan PQ-SNARK, mungkin sulit bahkan bagi para ahli untuk memastikan tingkat keamanan protokol yang disebarkan karena alasan yang sama bahwa kinerja keamanan dan verifier berada dalam ketegangan untuk SNARK ini: tingkat keamanan (dan biaya verifier) ​​bergantung pada parameter internal dari SNARK. Dan setidaknya untuk StarkWare kontrak pintar, parameter ini, called logBlowupFactor, proofOfWorkBits, dan n_Queries, tidak secara langsung ditentukan dalam kode kontrak pintar melainkan diteruskan ke kontrak pintar sebagai data publik. Sejauh yang saya tahu, cara termudah untuk mengidentifikasi parameter ini dari informasi on-chain adalah melalui proses empat langkah: 

1. lihat kontrak pintar yang sesuai pada penjelajah blok seperti Etherscan, 
2. klik pada transaksi "verifikasi bukti" yang sesuai, 
3. memecahkan kode data input transaksi, dan
4. cari tahu caranya menafsirkan data input yang didekodekan untuk mempelajari parameter SNARK kunci yang bersama-sama menentukan tingkat keamanan. 

Langkah terakhir ini membutuhkan menemukan kode Soliditas yang sesuai yang mengimplementasikan transaksi, yang mungkin merupakan tugas yang membingungkan. (Ketika saya sedang mempersiapkan pembicaraan pada rollup musim panas ini, Etherscan dapat mendekode data input yang relevan ke transaksi verifier SHARP sesuai Langkah 2 di atas. Tapi itu tampaknya tidak lagi berfungsi.)

Proposal 1: Pengawasan 

Dengan mengingat hal ini, saran pertama saya kepada komunitas web3 adalah membuatnya jauh lebih mudah untuk meneliti tingkat keamanan SNARK pasca-kuantum yang diterapkan. Ini kemungkinan melibatkan perangkat yang lebih baik untuk memahami data on-chain dan peningkatan transparansi oleh proyek itu sendiri dalam membuat parameter ini diketahui. 

Proposal 2: Norma yang lebih kuat

Keamanan 80 bit terlalu rendah, terutama versi lemah di mana 2⁷⁰ evaluasi hash cukup untuk berhasil menyerang dengan probabilitas sekitar 1/1000 — terlebih lagi mengingat sejarah panjang serangan mengejutkan pada kriptografi primitif. Salah satunya, yang disebutkan di atas, adalah serangan yang lebih baik pada kurva eliptik ramah pasangan seperti altbn128. Contoh yang lebih terkenal adalah SHA-1, yang distandarisasi pada keamanan 80 bit tetapi akhirnya terbukti hanya mencapai sekitar 60 bit. Dengan mengingat sejarah ini, perancang PQ-SNARK harus membiarkan diri mereka lebih dari 10 bit ruang gerak ketika mengonfigurasi tingkat keamanan, terutama jika analisis keamanan melibatkan dugaan kuat tentang keamanan statistik dari protokol yang relatif baru seperti FRI.

Bahkan untuk PQ-SNARK, tingkat keamanan yang sesuai selalu dapat dicapai, hanya dengan meningkatkan biaya verifikasi. Misalnya, meningkatkan keamanan verifier SHARP dari 80 menjadi 128 bit (di bawah dugaan tentang kesehatan statistik FRI) akan meningkatkan biaya gas kira-kira dua kali lipat, dari sedikit di atas 5 juta menjadi sedikit di atas 10 juta. Tanpa dugaan tentang FRI, biaya gas akan meningkat dua faktor lagi, menjadi lebih dari 20 juta. 

Saran saya selanjutnya adalah komunitas web3 harus mengembangkan norma yang lebih kuat seputar tingkat keamanan yang sesuai untuk SNARK yang digunakan. Rekomendasi pribadi saya setidaknya 100 bit, dan setidaknya 128 jika keamanan SNARK didasarkan pada asumsi non-standar. Saya bukan yang pertama membuat proposal seperti itu.

Di sini, saya bersedia mengkategorikan sebagai "asumsi standar" keamanan tanpa syarat di model oracle acak, jika oracle acak dalam SNARK yang digunakan dibuat dengan fungsi hash standar seperti KECCAK-256. Model oracle acak adalah pengaturan ideal yang dimaksudkan untuk menangkap perilaku fungsi hash kriptografi yang dirancang dengan baik. Ini sering digunakan untuk menganalisis keamanan PQ-SNARK. 

Contoh asumsi non-standar adalah dugaan (dijelaskan di bawah) mengenai kesehatan kuantitatif protokol seperti FRI, baik dalam pengaturan interaktif atau sebagai protokol non-interaktif dalam model oracle acak.

Perancang SNARK berinovasi dalam banyak cara yang menarik, beberapa di antaranya mungkin mendorong amplop dalam hal keamanan – misalnya, dengan menggunakan fungsi hash ramah SNARK yang belum mengalami kriptanalisis sebanyak fungsi hash standar. Saya tidak menyerukan diakhirinya upaya semacam itu – jauh dari itu. Tetapi primitif ini harus dipakai pada tingkat keamanan yang melebihi serangan yang diketahui dan layak dilakukan lebih dari 10 bit. 

Rollup menggunakan SNARK biasanya digambarkan sebagai mewarisi keamanan L1 mereka. Tapi ini adalah kasus yang sulit untuk dibuat jika mereka dikonfigurasi pada tingkat keamanan yang jauh lebih rendah daripada primitif kriptografi yang digunakan oleh L1. Saat SNARK melihat peningkatan adopsi, kita harus memastikan bahwa kita menerapkannya dengan cara yang konsisten dengan cara kita membicarakannya. Selama SNARK dianalisis dengan hati-hati, dikonfigurasi dengan tepat, dan diimplementasikan dengan benar, SNARK seaman apapun kriptografi primitif yang digunakan saat ini. 

Selain: Menyelam lebih dalam ke keamanan PQ-SNARK

Keamanan 80 bit dalam PQ-SNARK StarkWare diperhitungkan sebagai berikut. PQ-SNARK ini menggunakan skema komitmen polinomial yang disebut GRATIS, dan pemverifikasi SHARP StarkWare menjalankan FRI pada keamanan 48 bit berdasarkan dugaan. Secara kasar, dugaannya adalah bahwa serangan sederhana pada tingkat kesehatan FRI sudah optimal. Dalam serangan ini, pembukti kecurangan, dengan sedikit usaha, menghasilkan “bukti FRI” yang lolos dari pemeriksaan yang dipilih secara acak oleh verifikator dengan probabilitas 2^-48. 

StarkWare menggabungkan FRI dengan teknik yang disebut "grinding". Ini membutuhkan pembuktian yang jujur ​​untuk menghasilkan bukti kerja 32-bit sebelum menghasilkan bukti FRI. Manfaat dari grinding adalah secara drastis meningkatkan pekerjaan yang dibutuhkan oleh seorang cheater proof untuk melakukan serangan sederhana pada FRI yang disebutkan di atas, menjadi sekitar 2³² evaluasi hash. 

Sejak (dalam harapan) 2⁴⁸ upaya serangan sederhana diperlukan sebelum salah satu dari mereka berhasil, jumlah total pekerjaan yang harus dilakukan oleh pembukti curang untuk memalsukan bukti FRI kira-kira 2⁴⁸ * 2³² = 2⁸⁰ evaluasi hash.

Akhirnya, mari kita bongkar bagaimana keamanan 48 bit untuk FRI muncul. Pemverifikasi FRI membuat "kueri" ke polinomial yang dikomit. Biaya verifikasi FRI tumbuh secara linier dengan jumlah kueri. Misalnya, 36 kueri pemverifikasi FRI kira-kira 4 kali lebih mahal dari 9 kueri. Tetapi lebih banyak pertanyaan berarti lebih banyak keamanan. Jumlah "bit keamanan per kueri" tergantung pada parameter lain dari FRI, yang disebut laju kode. 

Secara khusus, FRI menggunakan sesuatu yang disebut kode tarif Reed-Solomon r, Di mana r selalu merupakan angka antara 0 dan 1. Biaya pembuat FRI berbanding terbalik dengan r, jadi tingkat 1/16 mengarah ke sebuah peribahasa yang sekitar empat kali lebih lambat dan lebih banyak ruang daripada tingkat . 

Verifier SHARP telah menjalankan FRI dengan code rate 1/16 dan dengan 12 query verifier.

StarkWare menduga bahwa setiap kueri pemverifikasi FRI menambahkan log₂(1 /r) sedikit keamanan. Di bawah dugaan ini, 12 kueri verifier menghasilkan 12 * log₂(16) = 48 bit keamanan.

Namun, analisis saat ini hanya menetapkan bahwa setiap kueri verifier menambahkan sedikit lebih sedikit dari log₂(1/r^1/2) sedikit keamanan. Jadi 12 kueri pemverifikasi FRI hanya menghasilkan kurang dari 12 * log₂(4) = 24 bit keamanan "dapat dibuktikan". 

Proposal untuk mengurangi ketegangan antara keamanan dan kinerja

PQ-SNARK praktis memiliki biaya verifier yang tumbuh secara linier dengan jumlah bit keamanan yang diinginkan. Salah satu teknik yang menjanjikan untuk mengurangi ketegangan ini adalah komposisi SNARK — yang saya jelaskan di posting saya sebelumnya sebagai sarana untuk menyelesaikan ketegangan antara biaya pembuktian dan pemverifikasi, tetapi juga dapat mengatasi keamanan. 

Dua contoh 

Poligon Hermez adalah menyusun PQ-SNARK dengan PlonK. Idenya adalah bahwa pembuktian terlebih dahulu menghasilkan bukti PQ-SNARK . Jika PQ-SNARK dikonfigurasi untuk memiliki proofer yang cepat dan tingkat keamanan yang memadai, maka akan menjadi besar. Jadi, si pemver tidak mengirimkan ke pemverifikasi. Sebaliknya, ia menggunakan PlonK untuk membuktikan bahwa ia mengetahui . 

Ini berarti menerapkan PlonK ke sirkuit yang menggunakan sebagai input dan memeriksa bahwa verifier PQ-SNARK akan menerima . Karena PQ-SNARK memiliki biaya verifikasi polilogaritmik, PlonK diterapkan ke sirkuit kecil, dan karenanya Prover PlonK cepat. Karena bukti PlonK kecil dan murah untuk diverifikasi, biaya verifikasi rendah. 

Sayangnya, penggunaan PlonK merusak transparansi dan keamanan pasca-kuantum. Sebagai gantinya, seseorang dapat mempertimbangkan untuk menggunakan PQ-SNARK itu sendiri sebagai pengganti PlonK untuk membuktikan pengetahuan tentang (sebenarnya PQ-SNARK yang digunakan oleh Polygon dibuat sendiri dengan cara ini). 

Dalam aplikasi kedua dari PQ-SNARK ini, untuk membuktikan pengetahuan tentang , sistem dapat dikonfigurasi untuk mencapai keamanan yang memadai dengan bukti berukuran cukup, misalnya, dengan memilih tingkat kode yang sangat kecil untuk digunakan di FRI. Poin kuncinya adalah, meskipun laju kode kecil ini buruk untuk waktu penyelidik, penerapan kedua PQ-SNARK hanya diterapkan pada sirkuit kecil, sehingga total waktu penyelidik harus tetap kecil.

Pemahaman teoretis kami tentang keamanan SNARK yang tersusun meninggalkan banyak hal yang diinginkan. Namun, tidak ada serangan yang diketahui lebih cepat daripada menyerang salah satu SNARK konstituen satu per satu. Misalnya, jika menyusun PQ-SNARK dengan PlonK, kita tidak tahu serangan yang lebih baik daripada menyerang PQ-SNARK (yaitu, menemukan bukti PQ-SNARK dari pernyataan palsu), atau menyerang PlonK (yaitu, temukan bukti PlonK dari pernyataan palsu “Saya tahu bukti PQ-SNARK yang akan diterima oleh verifikator.”)

Menyusun SNARK dengan cara ini adalah cara yang semakin populer untuk meningkatkan kinerja. Saya berharap perancang protokol juga menggunakannya untuk meningkatkan keamanan.

***

Justin Thaler adalah Associate Professor di Universitas Georgetown. Sebelum bergabung dengan Georgetown, ia menghabiskan dua tahun sebagai Research Scientist di Yahoo Labs di New York, sebelum itu ia menjadi Research Fellow di Institut Simons untuk Teori Komputasi di UC Berkeley. 

Editor: Tim Sullivan @tim_org

***

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.