Ditulis oleh: Kelas Lambda
Penyusun: Bai Ding, Faust, Nickqiao
Artikel asli berbahasa Inggris diterbitkan pada 17 Februari 2024
Bukti tanpa pengetahuan (ZK Proofs) adalah primitif kriptografi yang kuat yang memungkinkan satu pihak (pemeriksa) meyakinkan pihak lain (verifikator) bahwa pernyataan tertentu adalah benar dan valid tanpa mengungkapkan informasi pribadi apa pun. Dalam beberapa tahun terakhir, ZK telah mendapatkan perhatian luas di bidang komputasi pribadi yang dapat diverifikasi, memberikan bukti validitas untuk program komputer, dan blockchain, dan telah memberikan dampak positif yang signifikan terhadap perkembangan dunia.
Meskipun ZK adalah teknologi baru, ide dan konsep dasarnya sudah ada sejak tahun 1980an. Setelah digabungkan dengan blockchain seperti Bitcoin dan Ethereum, perkembangan teknologi ZK telah dipercepat secara signifikan, karena blockchain dapat melakukan verifikasi validitas melalui SNARK dan STARK, sehingga sangat meningkatkan skalabilitas, yang menjadikan ZK di wilayah Blockchain menjadi topik hangat.
Seperti yang dikatakan oleh pendiri Starkware Eli Ben-Sasson, dalam beberapa tahun terakhir kita telah menyaksikan "ledakan Kambrium" sistem bukti kriptografi, masing-masing memiliki kelebihan dan kekurangan serta trade-off yang unik dalam desainnya. Kemajuan perangkat keras, algoritme yang lebih baik, argumen baru, dan alat periferal semuanya telah mendorong peningkatan kinerja sistem ZK dan lahirnya sistem baru. Banyak sistem pembuktian telah diadopsi dalam aplikasi praktis, dan masyarakat masih memperluas batasan ZK.
Hal ini juga mendorong orang untuk memikirkan secara mendalam sebuah pertanyaan: Apakah ada sistem pembuktian ZK universal yang cocok untuk semua aplikasi? Menurut kami hal ini tidak mungkin terjadi karena tiga alasan:
keragaman aplikasi;
Jenis batasan yang berbeda (termasuk memori, waktu verifikasi, waktu pembuktian);
Perlunya ketahanan (jika satu sistem bukti disusupi oleh peretas, kita masih dapat beralih ke sistem lain sebagai jaminan).
Berdasarkan alasan di atas, ZK membuktikan bahwa sistem harus beragam. Namun meskipun ada banyak jenis sistem pembuktian, pasti ada satu kesamaan yang signifikan: Bukti ZK dapat diverifikasi dengan cepat, dan memiliki lapisan verifikasi yang dapat dengan mudah diadaptasi ke sistem pembuktian baru untuk menyelesaikan lapisan yang mendasarinya (seperti Ethereum) yang terkait. kesulitan.
Di bidang ZK, zk-SNARK sering disebutkan. Ini adalah bentuk penerapan pembuktian tanpa pengetahuan dengan menggunakan alat matematika kompleks seperti pasangan bilinear dan rangkaian aritmatika untuk mencapai pembuktian tanpa pengetahuan yang efisien. Ciri khas zk-SNARK adalah proses pembuktiannya sederhana dan non-interaktif. Hanya diperlukan satu komunikasi antara pembukti dan pemverifikasi tanpa banyak interaksi. Selain itu, ukuran bukti zk-SNARK sangat pendek dan efisiensi verifikasinya tinggi, sehingga cocok untuk digunakan di lingkungan dengan sumber daya terbatas.
Dan zk-STARK adalah bentuk umum lainnya yang dirancang untuk mengatasi beberapa keterbatasan zk-SNARK. zk-STARK tidak bergantung pada pengaturan tepercaya dan menggunakan sistem konstruksi matematika yang lebih transparan, seperti komitmen polinomial dan operasi lapangan terbatas, tabrakan hash, dll., untuk menghasilkan dan memverifikasi bukti. zk-STARK lebih skalabel dibandingkan zk-SNARK, cocok untuk penghitungan skala besar, dan pembuatan bukti lebih cepat, namun ukuran buktinya sendiri biasanya lebih besar.
Dapat dikatakan bahwa zk-SNARK dan zk-STARK keduanya merupakan bentuk yang umum digunakan dalam pembuktian tanpa pengetahuan, namun keduanya berbeda dalam hal transparansi, skalabilitas, ukuran pembuktian, dll.
Secara keseluruhan, sistem bukti ZK biasanya terdiri dari dua bagian: PIOP (Polynomial Interactive Oracle) dan PCS (Polynomial Commitment Scheme). Solusi PIOP yang umum mencakup PLONKish, GKR, dll., sedangkan solusi PCS yang umum mencakup FRI, KZG, IPA, dll. Misalnya, Halo2 versi Zcash menggunakan implementasi Plonkish+IPA sebagai solusi berbasis FRI.
Jika kita membahas lebih detail, berbagai jenis sistem pembuktian menggunakan skema komitmen polinomial (PCS), skema aritmatika, bukti oracle interaktif (IOP) atau bukti yang dapat diperiksa probabilistik (PCP) yang berbeda.
Selain itu, sistem pembuktian ZK yang berbeda sering kali berbeda dalam indikator berikut:
Asumsi kriptografi: fungsi hash tahan benturan, masalah logaritma diskrit pada kurva elips, pengetahuan eksponensial
Pengaturan transparan vs pengaturan tepercaya
Waktu yang dihabiskan untuk menghasilkan bukti: linier vs superlinier
Konsumsi waktu pembuktian verifikasi: waktu konstan, waktu logaritmik, sublinier, linier
Buktikan ukurannya
Kesederhanaan rekursi
skema aritmatika
Polinomial univariat vs multivariat
Di bawah ini kami akan membahas secara singkat asal usul teknologi ZK, mengeksplorasi landasan dasarnya, dan menguraikan naik turunnya berbagai sistem pembuktian ZK. Pada saat yang sama, artikel ini tidak memberikan analisis rinci tentang sistem pembuktian itu sendiri, tetapi berfokus pada mereka yang memiliki dampak besar di lapangan. Bagaimanapun, perkembangan industri apa pun hanya mungkin terjadi melalui ide-ide hebat dari para pionir dan implementasinya.
Sejarah perkembangan zk-SNARK
Asal: 1980an dan 1990an
Seperti yang kami sebutkan, bukti tanpa pengetahuan bukanlah konsep baru. Definisi, landasan, teorema penting, dan bahkan protokol penting terkait telah muncul sejak pertengahan 1980an. Ini pertama kali muncul di Goldwasser dan Micali (pendiri Algorand) dan Rackoff makalah "Kompleksitas Pengetahuan Sistem Pembuktian Interaktif".
Ide-ide utama dan protokol yang kami gunakan untuk membangun teknologi ZK-SNARK saat ini dikembangkan pada tahun 1990an. Misalnya, protokol Sumcheck menyederhanakan deklarasi jumlah evaluasi polinomial multivariat ke titik-titik yang dipilih secara acak pada kurva elips meletakkan dasar penting bagi teknologi ZK.
Oleh karena itu, munculnya ide ZK sebenarnya mendahului munculnya Bitcoin. Namun, secara umum terdapat kekurangan kasus penggunaan yang sesuai untuk ZK, dan orang-orang tidak dapat menyediakan daya komputasi yang kuat yang diperlukan untuk memenuhi sistem bukti ZK. Bagaimanapun, Internet dan peralatan perangkat keras belum dikembangkan pada tahun 1990-an.
Perjanjian GKR (2007)
GKR (Goldwasser-Kalai-Rothblum) adalah protokol interaktif. Waktu berjalan pemver berhubungan secara linear dengan jumlah gerbang logika di sirkuit, sedangkan waktu yang dibutuhkan pemverifikasi berhubungan secara sublinear dengan ukuran sirkuit. Dalam protokol GKR, pembukti dan pemverifikasi harus menyepakati hasil rangkaian aritmatika dua masukan yang berjalan pada medan berhingga. Rangkaian tersebut memiliki kedalaman d, dengan lapisan ke-d sebagai lapisan masukan dan lapisan ke-0 lapisan keluaran. Protokol dimulai dengan pernyataan tentang keluaran rangkaian, yang direduksi dengan rekursi menjadi pernyataan pada lapisan sebelumnya. Terakhir, kita dapat mengubah klaim tentang keluaran menjadi klaim tentang parameter masukan rangkaian, yang dapat diverifikasi dengan mudah. Dapat dikatakan bahwa protokol GKR sangat disederhanakan berdasarkan protokol Sumcheck yang disebutkan sebelumnya.
Skema Komitmen Polinomial KZG (2010)
Pada tahun 2010, tiga ahli di bidang ZK - Kate dari lembaga penelitian Jerman MPI-SWS, Zaverucha dari perusahaan kriptografi Kanada Certicom Research, dan Goldberg dari Universitas Waterloo bersama-sama menerbitkan makalah "Komitmen Ukuran Konstan terhadap Polinomial dan Penerapannya ". Makalah ini mengusulkan skema komitmen polinomial menggunakan kelompok pasangan bilinear yang diberi nama KZG.
Janji tersebut terdiri dari satu elemen grup, dan pengirim dapat secara efisien mengungkapkan evaluasi polinomial yang benar, dan dengan bantuan teknik pemrosesan batch, evaluasi beberapa polinomial dapat diungkapkan. KZG berjanji untuk menjadi salah satu blok bangunan dasar dari beberapa sistem bukti ZK yang terkenal (seperti halo2 yang digunakan oleh tim Ethereum PES), dan juga memainkan peran inti dalam EIP-4844 Ethereum. Untuk memahami konsep teknologi pemrosesan batch secara lebih intuitif, Anda dapat merujuk ke artikel tentang jembatan Mina-Ethereum Jembatan Mina-Ethereum.
Referensi: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
Sistem ZK-SNARK praktis berdasarkan kurva elips (2013)
Konstruksi praktis pertama ZK-SNARK muncul pada tahun 2013, memerlukan langkah pra-pemrosesan untuk menghasilkan kunci bukti dan verifikasi, dan spesifik untuk program atau sirkuit dan tidak dapat digeneralisasikan. Ukuran kunci ini bisa sangat besar dan bergantung pada parameter rahasia itu sendiri; jika kerahasiaan ini dikompromikan, penyerang dapat memalsukan buktinya. Dalam sistem ZK-SNARK yang praktis ini, mengubah kode menjadi bentuk yang dapat dibuktikan memerlukan kompilasi kode ke dalam kumpulan batasan polinomial matematis.
Awalnya, proses di atas harus dilakukan secara manual, sehingga memakan waktu dan rawan kesalahan. Perubahan teknologi selanjutnya ke arah ini terutama mencoba memecahkan masalah inti berikut:
Berikan bukti yang lebih efisien
Kurangi jumlah pra-pemrosesan
Mengaktifkan pengaturan umum, bukan khusus sirkuit
Hindari pengaturan tepercaya
Kembangkan metode untuk mendeskripsikan rangkaian menggunakan bahasa tingkat tinggi daripada menulis batasan polinomial secara manual
Perjanjian Pinokio (2013)
Protokol Pinocchio adalah sistem zk-SNARK pertama yang dapat digunakan secara praktis, berdasarkan pada Quadratic Arithmetic Program (QAP), dengan ukuran bukti awal 288 byte. Rantai alat Pinokio menyediakan kompiler yang mengkompilasi C menjadi rangkaian aritmatika, yang selanjutnya dapat diubah menjadi QAP. Protokol Pinokio mengharuskan pemverifikasi untuk menghasilkan kunci, yang tidak bersifat universal tetapi spesifik sirkuit. Hal ini membuktikan bahwa kompleksitas waktu asimtotik dari pembuatan sistem dan pengaturan kunci berskala linear dengan ukuran komputasi, dan waktu verifikasi berskala linear dengan ukuran input dan output publik.
Groth16 (2016)
Groth memperkenalkan algoritma ZK baru dengan kinerja lebih tinggi dalam memproses R1CS. R1CS adalah Sistem Batasan Peringkat-1, sistem batasan orde pertama, yang merupakan bentuk batasan polinomial di zk-SNARK. Bukti Gorth adalah yang terkecil dalam ukuran data (hanya berisi tiga elemen grup) dan cepat untuk diverifikasi, hanya memerlukan tiga operasi pemasangan dan langkah prapemrosesan untuk menyusun string referensi. Namun kelemahan utama Gorth adalah setiap program yang perlu dibuktikan memerlukan pengaturan tepercaya yang berbeda, yang cukup merepotkan dalam aplikasi praktis.
Kemudian, Groth16 digunakan di ZCash, yang merupakan proyek blockchain privasi yang relatif terkenal (pendiri Starkware Eli berpartisipasi di dalamnya).
Antipeluru dan IPA (2016)
Salah satu kelemahan utama skema komitmen polinomial KZG yang disebutkan sebelumnya adalah memerlukan pengaturan yang tepercaya. Bootle et al. mengusulkan sistem bukti tanpa pengetahuan yang efisien yang menganalisis pembukaan komitmen Pedersen yang memenuhi hubungan produk intrinsik. Hasil kali dalam membuktikan bahwa pembuktian dengan kompleksitas linier memakan waktu. Jumlah interaksi antara pembukti dan pemverifikasi adalah logaritmik, tetapi waktu verifikasinya linier. Selain itu, Bootle dkk juga mengembangkan skema komitmen polinomial yang tidak memerlukan pengaturan tepercaya. Ide-ide ini kemudian diadopsi antara lain oleh Halo2 dan Kimchi.
Sonic, Marlin dan Plonk (2019)
Sonic, Plonk, dan Marlin mengatasi kebutuhan pengaturan kepercayaan di setiap program dalam algoritma Groth16 dengan memperkenalkan string referensi terstruktur universal dan dapat diperbarui yang memungkinkan pengaturan kepercayaan hanya perlu diatur satu kali. Diantaranya, Marlin menyediakan sistem pembuktian berdasarkan R1CS dan telah menjadi teknologi inti Aleo.
Dan Plonk memperkenalkan skema aritmatika baru (yang kemudian disebut Plonkish) dan penggunaan produk besar untuk memeriksa batasan replikasi. Plonkish juga memungkinkan pengenalan gerbang logika sirkuit khusus untuk operasi tertentu, yang disebut "gerbang khusus". Banyak proyek blockchain terkenal telah menggunakan versi Plonk yang disesuaikan, termasuk Aztec, zkSync, Polygon zkEVM, Mina, tim Ethereum PSE, Scroll, dll.
Spartan (2019)
Spartan menyediakan IOP untuk sirkuit yang dijelaskan menggunakan R1CS, memanfaatkan fitur polinomial multivariat dan protokol pemeriksaan penjumlahan. Dengan menggunakan skema komitmen polinomial yang sesuai, ia menerapkan sistem zk-SNARK yang transparan dan menghasilkan bukti dengan kompleksitas waktu linier.
Pencarian (2020)
Gabizon dan Williamson mengusulkan plookup dalam makalah mereka tahun 2020, menggunakan produk utama untuk membuktikan bahwa suatu nilai terdapat dalam tabel kebenaran yang telah dihitung sebelumnya, menunjukkan cara memasukkan parameter plookup ke dalam algoritma Plonk.
Namun, argumen pencarian ini memiliki masalah yang sama. Pembuktian perlu mengeluarkan biaya yang besar untuk membuat tabel kebenaran yang lengkap, jadi pekerjaan sebelumnya seputar Pencarian telah didedikasikan untuk mengurangi biaya pembuktian.
Haböck kemudian memperkenalkan LogUp di makalahnya, yang menggunakan turunan logaritmik untuk mengubah pemeriksaan produk besar menjadi jumlah timbal balik. LogUp sangat penting untuk peningkatan kinerja Polygon zkEVM, karena memerlukan pemisahan seluruh tabel kebenaran menjadi beberapa modul STARK. Modul-modul ini harus ditautkan dengan benar, dan pencarian lintas tabel menerapkan hal ini. Sejak itu, pengenalan LogUp-GKR telah meningkatkan kinerja LogUp melalui protokol GKR.
Caulk merupakan solusi pertama yang membuat waktu pembuktian memiliki hubungan sub-linear dengan ukuran tabel kebenarannya. Kompleksitas waktu preprocessingnya adalah O(NlogN) dan kompleksitas ruang penyimpanannya adalah O(N), dimana N adalah nilai kebenarannya. . Solusi lain menyusul, seperti Baloo, flookup, cq dan dempul+. Selain itu, Lasso mengusulkan beberapa perbaikan yang menghindari penerapan tabel kebenaran ketika tabel tersebut memiliki struktur tertentu.
HyperPlonk (2022)
HyperPlonk diusulkan dalam makalah "HyperPlonk: Plonk dengan Linear-Time Prover dan High-Degree Custom Gates". HyperPlonk didasarkan pada ide Plonk, menggunakan polinomial multivariabel. Ia tidak menggunakan pembagian untuk memeriksa penerapan batasan, namun bergantung pada protokol pemeriksaan penjumlahan. Pada saat yang sama, ini juga mendukung batasan tingkat tinggi tanpa mempengaruhi waktu pembuatan bukti.
Karena penggunaan polinomial multivariabel, tidak perlu melakukan Fast Fourier Transform (FFT), yang membuktikan bahwa waktu pembangkitan berskala linier dengan ukuran rangkaian. HyperPlonk juga memperkenalkan IOP permutasi baru yang cocok untuk bidang kecil dan mengadopsi protokol berbasis pemeriksaan jumlah yang mengurangi beban kerja pembukti, ukuran bukti, dan waktu verifikasi.
Sistem Bukti ZK Menggunakan Fungsi Hash Anti Tabrakan
Pada saat yang sama dengan diusulkannya Pinokio pada tahun 2013, terdapat beberapa proposal untuk menghasilkan rangkaian/skema aritmatika yang dapat membuktikan bahwa eksekusi instruksi mesin virtual sudah benar. Meskipun mengembangkan skema aritmatika untuk mesin virtual lebih kompleks atau kurang efisien dibandingkan menulis sirkuit khusus untuk beberapa program, hal ini memiliki keuntungan penting: betapapun rumitnya program tersebut, Anda hanya perlu membuktikan bahwa program tersebut dijalankan dengan benar di mesin virtual.
Beberapa ide di TinyRAM kemudian disempurnakan dalam desain mesin virtual Kairo, antara lain zk-evm dan zkvm umum. Menggunakan fungsi hash tahan benturan dalam sistem pembuktian menghilangkan kebutuhan akan pengaturan tepercaya atau operasi kurva elips, namun dengan mengorbankan waktu pembuktian yang lebih lama.
RAM Kecil (2013)
Dalam "SNARKs for C", mereka mengembangkan sistem pembuktian berbasis PCP untuk membuktikan bahwa hasil eksekusi program yang ditulis dalam bahasa C sudah benar. Program ini dikompilasi ke dalam TinyRAM, VM yang disederhanakan. VM memiliki memori akses acak beralamat tingkat byte, ukuran sirkuit tumbuh secara quasi-linear dengan skala komputasi, dan dapat secara efisien menangani operasi seperti loop, aliran kontrol, dan akses memori.
Diantaranya, PCP mengacu pada Bukti yang Dapat Diperiksa Secara Probabilistik, yaitu bukti yang dapat diperiksa secara probabilistik. Verifikator hanya perlu membaca bagian bukti yang dipilih secara acak untuk memeriksa keabsahan bukti dengan tingkat kepercayaan yang tinggi. Berbeda dengan sistem pembuktian tradisional yang mengharuskan verifikator memeriksa seluruh bukti, PCP hanya memerlukan keacakan terbatas untuk mencapai verifikasi yang efisien.
Cahaya（2017）
Ligero memperkenalkan sistem pembuktian yang memungkinkan pembuktian ukuran O(√￣n), dimana n adalah ukuran rangkaian. Ini mengatur koefisien polinomial dalam bentuk matriks. Brakedown dibangun di atas Ligero dan memperkenalkan konsep skema komitmen polinomial bebas domain.
STARK (2018)
STARKs (Argumen Pengetahuan Transparan yang Dapat Diskalakan) diusulkan oleh Eli Ben-Sasson dkk pada tahun 2018. Mereka mencapai kompleksitas pembuktian 𝑂(log²𝑛), memiliki kecepatan verifikasi yang cepat, tidak memerlukan penyiapan tepercaya, dan diperkirakan aman pasca-kuantum. Mereka digunakan oleh Starkware/Starknet dengan mesin virtual Kairo. Inovasi utamanya mencakup Algebraic Intermediate Representation (AIR) dan protokol Fast Reed-Solomon Interactive Oracle Proximity Proof (FRI). Selain itu, STARK juga digunakan oleh banyak proyek blockchain terkenal (seperti Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync, dll.).
arah pengembangan baru
Penggunaan sistem pembuktian yang berbeda dalam aplikasi praktis menunjukkan keunggulan metode yang berbeda dan mendorong pengembangan ZK. Misalnya, skema aritmatika Plonkish menyediakan cara sederhana untuk memasukkan gerbang logika khusus dan argumen pencarian FRI telah menunjukkan kinerja yang sangat baik sebagai PCS, yang mengarah pada lahirnya Plonky. Pada saat yang sama, penggunaan pemeriksaan produk besar di AIR (membawa AIR acak yang telah diproses sebelumnya) meningkatkan kinerjanya dan menyederhanakan parameter akses memori. zk-STARK menjadi semakin populer karena efisiensi pembangkitannya yang lebih baik dan diperkenalkannya lebih banyak fungsi hash yang ramah ZK.
Skema Komitmen Polinomial Baru (2023)
Dengan munculnya SNARK efisien berdasarkan polinomial multivariat (seperti Spartan atau HyperPlonk), terdapat peningkatan minat terhadap skema komitmen baru yang sesuai untuk polinomial tersebut. Binius, Zeromorph, dan Basefold semuanya mengusulkan cara baru untuk berkomitmen pada polinomial multilinear. Binius memiliki keuntungan karena tidak memiliki overhead dalam merepresentasikan tipe data (sedangkan banyak sistem pembuktian lainnya menggunakan setidaknya elemen bidang 32-bit untuk merepresentasikan bit individual) dan bekerja pada domain biner. Skema komitmen ini menggunakan brakedown, yang dirancang untuk bersifat agnostik domain. Basefold menggeneralisasi FRI di luar Reed-Solomon, memungkinkan skema komitmen polinomial (PCS) yang tidak bergantung pada domain.
Independensi domain adalah properti dari skema komitmen polinomial, artinya dalam skema komitmen polinomial, proses komitmen tidak bergantung pada properti spesifik dari domain tertentu. Artinya, komitmen dapat dibuat terhadap polinomial struktur aljabar apa pun, seperti bidang berhingga, kurva elips, atau bahkan cincin bilangan bulat.
Sistem Pengekangan yang Dapat Disesuaikan (2023)
CCS menggeneralisasi R1CS sambil menangkap aritmatika R1CS, Plonkish, dan AIR tanpa overhead tambahan. Penggunaan CCS yang dikombinasikan dengan IOP Spartan menghasilkan SuperSpartan, yang mendukung batasan berdimensi tinggi tanpa harus menanggung biaya kriptografi yang sebanding dengan urutan batasan. Secara khusus, SuperSpartan menyediakan SNARK bukti waktu linier untuk AIR.
Meringkaskan
Artikel ini mengulas kemajuan teknologi ZK sejak pertengahan tahun 1980-an. Kemajuan dalam ilmu komputer, matematika, dan perangkat keras, ditambah dengan diperkenalkannya blockchain, telah menyebabkan munculnya sistem bukti ZK baru yang lebih efisien, membuka jalan bagi banyak aplikasi yang berpotensi mengubah masyarakat.
Para peneliti dan insinyur telah mengusulkan perbaikan pada sistem ZK berdasarkan kebutuhan, dengan fokus pada aspek-aspek seperti ukuran pembuktian, penggunaan memori, transparansi, keamanan anti-kuantum, waktu pembuktian, dan waktu verifikasi. Meskipun ZK selalu memiliki dua kategori utama solusi implementasi arus utama (SNARK dan STARK), batasan antara keduanya secara bertahap menjadi kabur, dan keunggulan sistem pembuktian yang berbeda digabungkan, seperti menggabungkan skema aritmatika yang berbeda dengan skema komitmen polinomial baru.
Kita dapat berharap bahwa sistem bukti ZK yang baru akan terus bermunculan dan kinerjanya akan terus meningkat. Untuk aplikasi yang menggunakan sistem pembuktian ini, jika mereka tidak dapat mengikuti perkembangan berulang teknologi terkini dan terus merekonstruksi serta menerapkan algoritme terbaru, posisi terdepan saat ini hanya akan bersifat sementara.
