Zero-knowledge, Succinct, Non-interactive ARguments of Knowledge (zk-SNARKs) adalah primitif kriptografi yang kuat yang mengizinkan satu pihak, pemberi pernyataan, untuk meyakinkan pihak lain, pemverifikasi, bahwa pernyataan yang diberikan adalah benar tanpa mengungkapkan hal lain selain keabsahan pernyataan tersebut. Mereka telah mendapatkan perhatian yang luas karena aplikasinya dalam komputasi pribadi yang dapat diverifikasi, memberikan bukti kebenaran eksekusi program komputer dan membantu skala blockchain. Kami pikir SNARK akan memiliki dampak yang signifikan dalam membentuk dunia kita, seperti yang kami jelaskan dalam tulisan kami. SNARK bertindak sebagai payung untuk berbagai jenis sistem pembuktian, menggunakan skema komitmen polinomial yang berbeda (PCS), skema aritmatika, bukti oracle interaktif (IOP) atau bukti yang dapat dicek secara probabilistik (PCP). Namun, ide dan konsep dasarnya sudah ada sejak pertengahan tahun 1980-an. Perkembangannya secara signifikan dipercepat setelah diperkenalkannya Bitcoin dan Ethereum, yang terbukti menjadi kasus penggunaan yang menarik dan kuat karena Anda dapat menskalakannya dengan menggunakan bukti Zero-Knowledge (umumnya disebut Bukti Validitas untuk kasus penggunaan ini). SNARK adalah alat penting untuk skalabilitas blockchain. Seperti yang dijelaskan oleh Ben-Sasson, beberapa tahun terakhir ini telah terjadi ledakan bukti kriptografi. Setiap sistem bukti menawarkan kelebihan dan kekurangan dan dirancang dengan mempertimbangkan tradeoff tertentu. Kemajuan dalam perangkat keras, algoritme yang lebih baik, argumen baru, dan gadget menghasilkan kinerja yang lebih baik dan lahirnya sistem baru. Banyak di antaranya digunakan dalam produksi, dan kami terus mendorong batas-batasnya. Apakah kita akan memiliki sistem bukti umum untuk semua aplikasi atau beberapa sistem yang cocok untuk kebutuhan yang berbeda? Kami berpikir bahwa tidak mungkin satu sistem bukti akan mengatur semuanya karena:

1. Keragaman aplikasi.
2. Jenis kendala yang kami miliki (terkait memori, waktu verifikasi, waktu pembuktian).
3. Kebutuhan akan ketahanan (jika satu sistem bukti rusak, kita masih memiliki sistem bukti yang lain).

Meskipun sistem bukti banyak berubah, semuanya menawarkan properti yang signifikan: bukti dapat diverifikasi dengan cepat. Memiliki lapisan yang memverifikasi bukti dan dapat dengan mudah diadaptasi untuk menangani sistem bukti baru akan menyelesaikan kesulitan yang terkait dengan perubahan lapisan dasar, seperti Ethereum. Untuk memberikan gambaran umum mengenai berbagai karakteristik SNARK yang berbeda:

• Asumsi kriptografi: fungsi hash yang tahan terhadap tabrakan, masalah log diskrit pada kurva elips, pengetahuan tentang eksponen.
• Penyiapan transparan vs penyiapan tepercaya.
• Waktu yang tepat: linear vs superlinear.
• Waktu pemeriksa: waktu konstan, logaritmik, sublinear, linier.
• Ukuran bukti.
• Kemudahan pengulangan.
• Skema aritmatika.
• Polinomial univariat vs polinomial multivariat.

Artikel ini akan membahas asal-usul SNARK, beberapa blok bangunan fundamental, dan kebangkitan (dan kejatuhan) sistem bukti yang berbeda. Tulisan ini tidak bermaksud untuk menjadi analisis yang lengkap tentang sistem pembuktian. Kami fokus pada hal-hal yang berdampak pada kami. Tentu saja, perkembangan ini hanya mungkin terjadi berkat kerja keras dan gagasan hebat dari para pionir di bidang ini.

Dasar-dasar

Seperti yang telah kami sebutkan, pembuktian tanpa pengetahuan bukanlah hal yang baru. Definisi, fondasi, teorema penting, dan bahkan protokol penting ditetapkan sejak pertengahan tahun 1980-an. Beberapa ide dan protokol utama yang kami gunakan untuk membangun SNARK modern diusulkan pada tahun 1990-an (protokol sumcheck) atau bahkan sebelum munculnya Bitcoin (GKR pada tahun 2007). Masalah utama dalam pengadopsiannya terkait dengan kurangnya usecase yang kuat (internet belum berkembang pada tahun 1990-an), dan jumlah daya komputasi yang dibutuhkan.

Bukti-bukti tanpa pengetahuan: asal-usulnya (1985/1989)

Bidang pembuktian zero-knowledge muncul dalam literatur akademis dengan adanya makalah dari Goldwasser, Micali dan Rackoff. Untuk pembahasan mengenai asal-usulnya, Anda dapat melihat video berikut ini. Makalah ini memperkenalkan gagasan kelengkapan, kesehatan, dan pengetahuan nol, memberikan konstruksi untuk residuositas kuadratik dan non-residuositas kuadratik.

Protokol Sumcheck (1992)

Protokol sumcheck diusulkan oleh Lund, Fortnow, Karloff, dan Nisan pada tahun 1992. Ini adalah salah satu blok bangunan yang paling penting untuk bukti interaktif yang ringkas. Ini membantu kita mengurangi klaim atas jumlah evaluasi polinomial multivariat menjadi evaluasi tunggal pada titik yang dipilih secara acak.

Goldwasser-Kalai-Rothblum (GKR) (2007)

Protokol GKR adalah protokol interaktif yang memiliki pembukti yang berjalan secara linier dalam jumlah gerbang sirkuit, sementara verifier berjalan secara sublinear dalam ukuran sirkuit. Dalam protokol, pembukti dan pemverifikasi menyetujui rangkaian aritmatika fan-in-two di atas bidang terbatas dengan kedalaman d, dengan lapisan d yang sesuai dengan lapisan input dan lapisan 0 sebagai lapisan output. Protokol dimulai dengan klaim mengenai output rangkaian, yang direduksi menjadi klaim atas nilai lapisan sebelumnya. Dengan menggunakan rekursi, kita dapat mengubahnya menjadi klaim atas input sirkuit, yang dapat diperiksa dengan mudah. Pengurangan ini dicapai melalui protokol sumcheck.

Skema komitmen polinomial KZG (2010)

Kate, Zaverucha, dan Goldberg memperkenalkan pada tahun 2010 sebuah skema komitmen untuk polinomial dengan menggunakan kelompok pasangan bilinear. Komitmen terdiri dari satu elemen grup, dan pembuat komitmen dapat secara efisien membuka komitmen untuk evaluasi polinomial yang benar. Selain itu, karena teknik batching, pembukaan dapat dilakukan untuk beberapa evaluasi. Komitmen KZG menjadi salah satu blok bangunan dasar untuk beberapa SNARK yang efisien, seperti Pinokio, Groth16, dan Plonk. Ini juga merupakan jantung dari EIP-4844. Untuk mendapatkan intuisi tentang teknik batching, Anda dapat melihat postingan kami di jembatan Mina-Ethereum.

SNARK praktis menggunakan kurva elips

Konstruksi praktis pertama untuk SNARK muncul pada tahun 2013. Ini memerlukan langkah preprocessing untuk menghasilkan kunci pembuktian dan verifikasi, dan bersifat spesifik untuk program/sirkuit. Kunci-kunci ini bisa sangat besar, dan bergantung pada parameter rahasia yang harus tetap tidak diketahui oleh para pihak; jika tidak, mereka dapat memalsukan bukti. Mengubah kode menjadi sesuatu yang dapat dibuktikan membutuhkan kompilasi kode ke dalam sistem batasan polinomial. Pada awalnya, hal ini harus dilakukan dengan cara manual, yang memakan waktu dan rentan terhadap kesalahan. Kemajuan di bidang ini mencoba menghilangkan sebagian masalah utama:

1. Memiliki pembuktian yang lebih efisien.
2. Kurangi jumlah prapemrosesan.
3. Memiliki pengaturan yang universal daripada pengaturan khusus sirkuit.
4. Hindari pengaturan yang tidak tepercaya.
5. Mengembangkan cara untuk mendeskripsikan sirkuit menggunakan bahasa tingkat tinggi, alih-alih menulis batasan polinomial secara manual.

Pinokio (2013)

Pinokio adalah zk-SNARK pertama yang praktis dan dapat digunakan. SNARK didasarkan pada program aritmatika kuadratik (QAP). Ukuran bukti pada awalnya adalah 288 byte. Toolchain Pinocchio menyediakan kompiler dari kode C ke sirkuit aritmatika, yang selanjutnya ditransformasikan menjadi QAP. Protokol mengharuskan verifikator menghasilkan kunci, yang khusus untuk sirkuit. Ini menggunakan pasangan kurva elips untuk memeriksa persamaan. Asimtotik untuk pembuatan bukti dan pengaturan kunci adalah linier dalam ukuran komputasi, dan waktu verifikasi adalah linier dalam ukuran input dan output publik.

Groth 16 (2016)

Groth memperkenalkan argumen pengetahuan baru dengan peningkatan kinerja untuk masalah yang dijelaskan oleh R1CS. Ini memiliki ukuran bukti terkecil (hanya tiga elemen grup) dan verifikasi cepat yang melibatkan tiga pasangan. Ini juga melibatkan langkah prapemrosesan untuk mendapatkan string referensi terstruktur. Kelemahan utamanya adalah memerlukan pengaturan tepercaya yang berbeda untuk setiap program yang ingin kita buktikan, dan ini merepotkan. Groth16 digunakan di ZCash.

Antipeluru & IPA (2016)

Salah satu titik lemah dari KZG PCS adalah, bahwa ia memerlukan pengaturan yang terpercaya. Bootle dkk. memperkenalkan sebuah sistem argumen nol-pengetahuan yang efisien untuk membuka komitmen Pedersen yang memenuhi relasi inner product. Argumen inner product memiliki pembuktian linier, dengan komunikasi dan interaksi logaritmik, tetapi dengan verifikasi waktu linier. Mereka juga mengembangkan skema komitmen polinomial yang tidak memerlukan pengaturan tepercaya. PC yang menggunakan ide ini digunakan oleh Halo 2 dan Kimchi.

Sonic, Marlin, dan Plonk (2019)

Sonic, Plonk, dan Marlin memecahkan masalah pengaturan tepercaya per program yang kami miliki di Groth16, dengan memperkenalkan string referensi terstruktur yang universal dan dapat diperbarui. Marlin menyediakan sistem pembuktian berdasarkan R1CS dan merupakan inti dari Aleo.

Plonk memperkenalkan skema aritmatika baru (kemudian disebut Plonkish) dan penggunaan cek grand-product untuk batasan penyalinan. Plonkish juga mengizinkan pengenalan gerbang khusus untuk operasi tertentu, yang disebut gerbang khusus. Beberapa proyek telah menyesuaikan versi Plonk, termasuk Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2, dan Scroll, dan masih banyak lagi.

Pencarian (2018/2020)

Gabizon dan Williamson memperkenalkan plookup pada tahun 2020, menggunakan pemeriksaan produk utama untuk membuktikan bahwa suatu nilai termasuk dalam tabel nilai yang telah dihitung sebelumnya. Meskipun argumen pencarian sebelumnya disajikan di Arya, konstruksi ini membutuhkan penentuan kelipatan untuk pencarian, yang membuat konstruksi ini kurang efisien. Makalah PlonkUp menunjukkan bagaimana cara memperkenalkan argumen plookup ke dalam Plonk. Masalah dengan argumen pencarian ini adalah bahwa argumen ini memaksa pembuktian untuk membayar harga untuk seluruh tabel, terlepas dari jumlah pencariannya. Hal ini menyiratkan biaya yang cukup besar untuk tabel yang besar, dan banyak upaya telah dicurahkan untuk mengurangi biaya pembuktian menjadi jumlah pencarian yang digunakannya.
Haböck memperkenalkan LogUp, yang menggunakan turunan logaritmik untuk mengubah cek hasil kali menjadi jumlah timbal balik. LogUp sangat penting untuk kinerja di Polygon ZKEVM, di mana mereka perlu membagi seluruh tabel menjadi beberapa modul STARK. Modul-modul ini harus ditautkan dengan benar, dan pencarian lintas tabel menerapkan hal ini. Pengenalan LogUp-GKR menggunakan protokol GKR untuk meningkatkan kinerja LogUp. Caulk adalah skema pertama dengan waktu pembuktian yang sublinear dalam ukuran tabel dengan menggunakan waktu preprocessing O(NlogN) dan penyimpanan O(N), di mana N adalah ukuran tabel. Beberapa skema lain menyusul, seperti Baloo, flookup, cq dan caulk+. Lasso menyajikan beberapa perbaikan, menghindari melakukan komitmen pada tabel jika memiliki struktur tertentu. Selain itu, peribahasa Lasso hanya membayar entri tabel yang diakses oleh operasi pencarian. Jolt memanfaatkan Lasso untuk membuktikan eksekusi mesin virtual melalui pencarian.

Spartan (2019)

Spartan menyediakan IOP untuk sirkuit yang dideskripsikan menggunakan R1CS, dengan memanfaatkan sifat polinomial multivariat dan protokol sumcheck. Dengan menggunakan skema komitmen polinomial yang sesuai, ini menghasilkan SNARK yang transparan dengan pembuktian waktu yang linier.

HyperPlonk (2022)

HyperPlonk dibangun berdasarkan ide-ide Plonk menggunakan polinomial multivariat. Alih-alih menggunakan kuosien untuk memeriksa penegakan batasan, ia mengandalkan protokol sumcheck. Ini juga mendukung batasan tingkat tinggi tanpa merusak waktu berjalannya prover. Karena mengandalkan polinomial multivariat, maka tidak perlu melakukan FFT, dan waktu berjalannya prover linier dalam ukuran rangkaian. HyperPlonk memperkenalkan IOP permutasi baru yang cocok untuk bidang yang lebih kecil dan protokol pembukaan batch berbasis pemeriksaan jumlah, yang mengurangi pekerjaan pembukti, ukuran bukti, dan waktu pemeriksa.

Skema pelipatan (2008/2021)

Nova memperkenalkan ide skema pelipatan, yang merupakan pendekatan baru untuk mencapai komputasi yang dapat diverifikasi secara bertahap (IVC). Konsep IVC berawal dari Valiant yang menunjukkan bagaimana cara menggabungkan dua bukti dengan panjang k menjadi satu bukti dengan panjang k. Idenya adalah bahwa kita dapat membuktikan komputasi yang berjalan lama dengan membuktikan secara rekursif bahwa eksekusi dari langkah i ke langkah I+1+1 adalah benar dan memverifikasi sebuah bukti yang menunjukkan bahwa transisi dari langkah i

-1-1 hingga langkah i benar. Nova menangani komputasi seragam dengan baik; kemudian diperluas untuk menangani berbagai jenis sirkuit dengan diperkenalkannya Supernova. Nova menggunakan versi R1CS yang santai dan bekerja pada kurva elips yang bersahabat. Bekerja dengan siklus kurva yang bersahabat (misalnya, kurva Pasta) untuk mencapai IVC juga digunakan dalam Pickles, blok bangunan utama Mina untuk mencapai kondisi yang ringkas. Namun, ide pelipatan berbeda dengan verifikasi SNARK rekursif. Ide akumulator lebih terkait dengan konsep bukti batching. Halo memperkenalkan gagasan akumulasi sebagai sebuah alternatif untuk komposisi bukti rekursif. Protostar menyediakan skema IVC yang tidak seragam untuk Plonk yang mendukung gerbang tingkat tinggi dan pencarian vektor.

Menggunakan fungsi hash yang tahan tabrakan

Sekitar waktu yang sama saat Pinocchio dikembangkan, ada beberapa ide untuk menghasilkan sirkuit/skema aritmatika yang dapat membuktikan kebenaran eksekusi mesin virtual. Meskipun mengembangkan aritmatika mesin virtual bisa jadi lebih rumit atau kurang efisien daripada menulis sirkuit khusus untuk beberapa program, mesin virtual menawarkan keuntungan bahwa program apa pun, betapapun rumitnya, dapat dibuktikan dengan menunjukkan bahwa program tersebut dieksekusi dengan benar di mesin virtual. Ide-ide dalam TinyRAM kemudian ditingkatkan dengan desain Cairo vm, dan mesin virtual berikutnya (seperti zk-evms atau zkvms untuk keperluan umum). Penggunaan fungsi hash yang tahan tabrakan menghilangkan kebutuhan akan pengaturan yang terpercaya atau penggunaan operasi kurva elips, dengan mengorbankan pembuktian yang lebih lama.

TinyRAM (2013)

Dalam SNARK untuk C, mereka mengembangkan SNARK berdasarkan PCP untuk membuktikan kebenaran eksekusi program C, yang dikompilasi ke TinyRAM, sebuah komputer dengan set instruksi yang diperkecil. Komputer menggunakan arsitektur Harvard dengan memori akses acak yang dapat dialamatkan pada tingkat byte. Memanfaatkan nondeterminisme, ukuran sirkuit quasilinear dalam ukuran komputasi, secara efisien menangani loop yang berubah-ubah dan bergantung pada data, aliran kontrol, dan akses memori.

STARKs (2018)

STARK diperkenalkan oleh Ben Sasson dkk. pada tahun 2018. Mereka mencapai O(log2n)(log2)

ukuran bukti, dengan pembuktian dan verifier yang cepat, tidak memerlukan pengaturan tepercaya, dan diduga aman pasca-kuantum. Mereka pertama kali digunakan oleh Starkware/Starknet, bersama dengan vm Kairo. Di antara perkenalan utamanya adalah representasi menengah aljabar (AIR) dan protokol FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Ini juga digunakan oleh proyek lain (Polygon Miden, Risc0, Winterfell, Neptunus) atau telah diadaptasi dari beberapa komponen (Boojum dari zkSync, Plonky2, Starky).

Ligero (2017)

Ligero memperkenalkan sistem pembuktian yang menghasilkan bukti yang ukurannya

O(√n), di mana n adalah ukuran sirkuit. Ini mengatur koefisien polinomial dalam bentuk matriks dan menggunakan kode linier.
Brakedown dibangun di atas Ligero dan memperkenalkan ide skema komitmen polinomial agnostik lapangan.

Beberapa perkembangan baru

Penggunaan sistem pembuktian yang berbeda dalam produksi menunjukkan keunggulan masing-masing pendekatan, dan menghasilkan perkembangan baru. Sebagai contoh, aritmatika plonkish menawarkan cara sederhana untuk memasukkan gerbang khusus dan argumen pencarian; FRI telah menunjukkan kinerja yang luar biasa sebagai PCS, yang mengarah ke Plonky. Demikian pula, penggunaan pemeriksaan produk utama di AIR (yang mengarah ke AIR acak dengan prapemrosesan) meningkatkan kinerjanya dan menyederhanakan argumen akses memori. Komitmen berdasarkan fungsi hash telah mendapatkan popularitas, berdasarkan kecepatan fungsi hash dalam perangkat keras atau pengenalan fungsi hash baru yang ramah SNARK.

Skema komitmen polinomial baru (2023)

Dengan munculnya SNARK yang efisien berdasarkan polinomial multivariat, seperti Spartan atau HyperPlonk, telah terjadi peningkatan minat terhadap skema komitmen baru yang sesuai untuk polinomial semacam ini. Binius, Zeromorph, dan Basefold semuanya mengusulkan bentuk baru untuk melakukan polinomial multilinear. Binius menawarkan keuntungan karena tidak memiliki overhead untuk merepresentasikan tipe data (sedangkan banyak sistem pembuktian menggunakan setidaknya elemen field 32-bit untuk merepresentasikan bit tunggal) dan bekerja pada field biner. Komitmen ini mengadaptasi brakedown, yang dirancang untuk tidak bergantung pada kondisi lapangan. Basefold menggeneralisasi FRI ke kode selain Reed-Solomon, yang mengarah ke PCS yang bersifat field-agnostic.

Sistem Kendala yang Dapat Disesuaikan (2023)

CCS menggeneralisasi R1CS sambil menangkap aritmatika R1CS, Plonkish, dan AIR tanpa overhead. Menggunakan CCS dengan Spartan IOP menghasilkan SuperSpartan, yang mendukung batasan tingkat tinggi tanpa harus mengeluarkan biaya kriptografi yang berskala dengan tingkat batasan. Secara khusus, SuperSpartan menghasilkan SNARK untuk AIR dengan pembuktian waktu linier.

Kesimpulan

Tulisan ini menjelaskan kemajuan SNARK sejak diperkenalkan pada pertengahan tahun 1980-an. Kemajuan dalam ilmu komputer, matematika, dan perangkat keras, bersama dengan pengenalan blockchain, telah menghasilkan SNARK yang baru dan lebih efisien, membuka pintu bagi banyak aplikasi yang dapat mengubah masyarakat kita. Para peneliti dan insinyur telah mengusulkan peningkatan dan adaptasi pada SNARK sesuai dengan kebutuhan mereka, dengan fokus pada ukuran bukti, penggunaan memori, pengaturan transparan, keamanan pasca-kuantum, waktu pembuktian, dan waktu verifier. Meskipun pada awalnya terdapat dua jalur utama (SNARK vs STARK), batas antara keduanya telah mulai memudar, dengan mencoba menggabungkan keuntungan dari sistem bukti yang berbeda. Misalnya, menggabungkan skema aritmatika yang berbeda dengan skema komitmen polinomial yang baru. Kita dapat berharap bahwa sistem bukti baru akan terus meningkat, dengan peningkatan kinerja, dan akan sulit bagi beberapa sistem yang membutuhkan waktu untuk beradaptasi untuk mengikuti perkembangan ini kecuali jika kita dapat dengan mudah menggunakan alat ini tanpa harus mengubah beberapa infrastruktur inti.

Penafian: Penafian

1. Artikel ini dicetak ulang dari[lambdaclass], Semua hak cipta adalah milik penulis asli[LambdaClass]. Jika ada keberatan dengan pencetakan ulang ini, silakan hubungi tim Gate Learn, dan mereka akan segera menanganinya.
2. Penafian Tanggung Jawab: Pandangan dan pendapat yang diungkapkan dalam artikel ini semata-mata merupakan pandangan dan pendapat penulis dan bukan merupakan saran investasi.
3. Penerjemahan artikel ke dalam bahasa lain dilakukan oleh tim Gate Learn. Kecuali disebutkan, menyalin, mendistribusikan, atau menjiplak artikel terjemahan dilarang.