IOSG: Apakah daya penggerak untuk inovasi berterusan dalam bukti pengetahuan sifar?

Pengarang: LambdaClass

Terjemahan: mutourend; Yiping, IOSG Ventures

1 Pengenalan

Sifar pengetahuan, ringkas, bukti pengetahuan tidak interaktif (zk-SNARKs), adalah pembuktian kriptografi yang berkuasa. ketepatan sesuatu pernyataan tanpa mendedahkan sebarang maklumat di luar pernyataan itu. zk-SNARKs telah mendapat perhatian yang meluas kerana aplikasi mereka dalam pengiraan peribadi yang boleh disahkan, bukti ketepatan pelaksanaan program komputer dan sambungan rantaian blok. Kami percaya bahawa zk-SNARKs, seperti yang kami huraikan dalam artikel kami, akan mempunyai kesan yang besar dalam membentuk dunia. zk-SNARK merangkumi pelbagai jenis sistem bukti, menggunakan skema komitmen polinomial yang berbeza, skema aritmetik, bukti oracle interaktif atau bukti boleh diuji kebarangkalian. Tetapi idea dan konsep asas ini bermula pada pertengahan 1980-an. Pembangunan zk-SNARKs telah sangat dipercepatkan sejak pelancaran Bitcoin dan Ethereum kerana keupayaan mereka untuk menskala melalui penggunaan bukti pengetahuan sifar (sering dirujuk sebagai bukti kesahihan untuk kes penggunaan khusus ini). zk-SNARKs memainkan peranan penting dalam skalabiliti blockchain. Seperti yang dinyatakan oleh Ben-Sasson, beberapa tahun kebelakangan ini telah menyaksikan letupan bukti kriptografi Cambrian. Setiap sistem bukti mempunyai kelebihan dan kekurangan, dan direka bentuk dengan mengambil kira pertukaran tertentu. Kemajuan dalam perkakasan, algoritma, bukti baharu dan alatan terus meningkatkan prestasi dan membawa kepada penciptaan sistem baharu. Banyak sistem ini sudah digunakan dan kami terus menolak sempadan. Adakah kita akan mempunyai sistem bukti universal yang berfungsi untuk semua aplikasi, atau adakah terdapat beberapa sistem yang sesuai untuk keperluan yang berbeza? Kami fikir adalah sangat tidak mungkin satu sistem bukti akan menguasai semua sistem lain, atas sebab-sebab termasuk:

1) Kepelbagaian aplikasi.

2) Pelbagai jenis sekatan (mengenai ingatan, masa pengesahan, masa bukti).

3) Keperluan untuk keteguhan (jika satu sistem bukti rosak, terdapat sistem bukti lain).

Walaupun sistem pembuktian mungkin mengalami perubahan ketara, kesemuanya berkongsi satu ciri penting: pengesahan pantas. Kesukaran yang berkaitan dengan mengubah suai lapisan asas seperti Ethereum boleh diselesaikan dengan mempunyai lapisan yang mengesahkan bukti dan boleh menyesuaikan secara fleksibel kepada sistem bukti baharu. Artikel ini akan menggariskan secara ringkas pelbagai ciri SNARK:

1) Andaian kriptografi: fungsi cincang tahan perlanggaran, masalah logaritma diskret pada lengkung eliptik, pengetahuan tentang eksponen.

2) Tetapan telus vs dipercayai.

3) Panjang bukti: linear lwn superlinear.

4) Masa pengesah: masa malar, logaritma, sublinear, linear.

5) saiz kalis.

6) Mudah berulang.

7) Skema aritmetik.

8) Polinomial univariable vs polinomial multivariable.

Artikel ini akan meneroka asal usul SNARK, beberapa blok binaan asas, dan peningkatan (dan kejatuhan) sistem bukti yang berbeza. Artikel ini tidak bertujuan untuk menyediakan analisis lengkap sistem bukti. Sebaliknya, tumpukan hanya pada mereka yang memberi kesan kepada kita. Sudah tentu, perkembangan ini hanya mungkin melalui kerja dan idea hebat perintis dalam bidang ini.

2. Pengetahuan asas

Bukti sifar pengetahuan bukanlah perkara baharu. Definisi, asas, teorem penting, dan juga protokol penting telah dibangunkan bermula pada pertengahan 1980-an. Beberapa idea dan protokol utama yang digunakan untuk membina SNARK moden telah dicadangkan pada tahun 1990-an (protokol sumcheck), walaupun sebelum Bitcoin wujud (GKR pada tahun 2007). Masalah utama dengan menggunakannya adalah berkaitan dengan kekurangan kes penggunaan yang kuat (Internet tidak dibangunkan pada tahun 1990-an) dan kuasa pengkomputeran yang diperlukan.

1) Bukti sifar pengetahuan: asal usul (1985/1989).

Bidang bukti sifar pengetahuan muncul dalam kesusasteraan akademik dengan kertas "Kerumitan pengetahuan sistem bukti interaktif" oleh Goldwasser, Micali dan Rackoff. Untuk perbincangan tentang asal usul, anda boleh menonton video ZKP MOOC Kuliah 1 Januari 2023: Pengenalan dan Sejarah ZKP. Kertas kerja ini memperkenalkan konsep kesempurnaan, kebolehpercayaan dan pengetahuan sifar, dan menyediakan pembinaan kekandungan kuadratik dan bukan kekangan kuadratik.

2) Sumcheck Protocol (1992).

Protokol sumcheck telah dicadangkan oleh Lund, Fortnow, Karloff dan Nisan dalam kertas Kaedah Algebra 1992 untuk Sistem Bukti Interaktif. Ia adalah salah satu blok bangunan paling penting bagi bukti interaktif ringkas. Ia membantu kami mengurangkan keperluan menjumlahkan penilaian polinomial multivariat kepada penilaian tunggal mata yang dipilih secara rawak.

3) Goldwasser-Kalai-Rothblum (GKR) (2007).

Protokol GKR (lihat makalah Delegating Computation: Interactive Proofs for Muggles) ialah protokol interaktif di mana prover beroperasi secara linear dengan bilangan get dalam litar dan pengesah beroperasi secara sublinear dengan saiz litar. Dalam protokol, prover dan verifier mencapai persetujuan mengenai litar operasi kipas-dalam-dua medan terhingga dengan kedalaman d dd, di mana lapisan d dd sepadan dengan lapisan input dan lapisan 0 00 sepadan dengan lapisan output. Protokol bermula dengan pernyataan tentang output litar, yang dikurangkan kepada pernyataan tentang nilai lapisan sebelumnya. Menggunakan rekursi, ini boleh diubah menjadi pengisytiharan input litar, yang boleh disemak dengan mudah. Pengurangan ini dilaksanakan melalui protokol sumcheck.

4) Skim komitmen polinomial KZG (2010).

Kate, Zaverucha dan Goldberg memperkenalkan skim komitmen polinomial menggunakan kumpulan berpasangan dwilinear dalam Komitmen Bersaiz Malar kepada Polinomial dan Aplikasinya pada tahun 2010. Komitmen terdiri daripada satu elemen kumpulan, dan komitter dengan berkesan membuka komitmen kepada sebarang penilaian yang betul bagi polinomial. Di samping itu, terima kasih kepada teknologi batching, pelbagai penilaian boleh dibuka. Komitmen KZG menyediakan salah satu blok binaan asas untuk beberapa SNARK yang cekap, seperti Pinocchio, Groth16 dan Plonk. Ia juga merupakan teras EIP-4844. Untuk memahami teknologi batching secara intuitif, lihat jambatan Mina ke Ethereum ZK.

3. SNARK praktikal menggunakan lengkung eliptik

Pembinaan praktikal SNARK yang pertama muncul pada tahun 2013. Pembinaan ini memerlukan langkah prapemprosesan untuk menjana bukti dan kunci pengesahan dan khusus program/litar. Kekunci ini boleh menjadi sangat besar dan bergantung pada parameter rahsia yang tidak diketahui oleh semua pihak jika tidak, bukti boleh dipalsukan. Mengubah kod kepada kod yang boleh dibuktikan memerlukan penyusunan kod ke dalam sistem kekangan polinomial. Pada mulanya, ini perlu dilakukan secara manual, yang memakan masa dan terdedah kepada ralat. Kemajuan dalam bidang cuba untuk menghapuskan beberapa masalah utama:

1) Mempunyai prover yang lebih cekap.

2) Kurangkan jumlah prapemprosesan.

3) Mempunyai persediaan yang universal dan bukannya khusus litar.

4) Elakkan tetapan yang dipercayai.

5) Bina cara untuk menerangkan litar menggunakan bahasa peringkat tinggi dan bukannya menulis kekangan polinomial secara manual.

Pada masa ini, penyelesaian praktikal SNARKs menggunakan lengkung eliptik ialah:

1) Pinocchio (2013)

2) Groth 16 (2016)

3) Kalis Peluru & IPA (2016)

, Sonicklin (2016)

4 2019)

5) Carian (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

8) Skim lipatan (2008/2021 Pinoc)

3.21 Pinoc)

Pinocchio ( Lihat karya Pinocchio: Pengiraan Boleh Disahkan Hampir Praktikal) ialah zk-SNARK praktikal dan boleh guna yang pertama. SNARK adalah berdasarkan program aritmetik kuadratik (QAP). Saiz bukti pada mulanya ialah 288 bait. Rantai alat Pinocchio menyediakan pengkompil daripada kod C kepada litar aritmetik dan terjemahan selanjutnya ke dalam QAP. Protokol memerlukan pengesah untuk menjana kunci khusus litar. Ia menggunakan gandingan lengkung eliptik untuk menyemak persamaan. Asimptotik penjanaan bukti dan tetapan kunci adalah linear tanpa gejala dengan saiz pengiraan, dan panjang pengesahan adalah linear dengan saiz input dan output awam.

3.2 Groth 16 (2016)

Kertas Groth 2016 Mengenai Saiz Argumen Bukan Interaktif Berpasangan memperkenalkan hujah pengetahuan baharu yang meningkatkan prestasi masalah yang diterangkan oleh R1CS. Ia mempunyai saiz pembuktian yang minimum (hanya tiga elemen kumpulan) dan pengesahan pantas yang melibatkan tiga gandingan. Ia juga melibatkan langkah prapemprosesan untuk mendapatkan rentetan rujukan berstruktur. Kelemahan utama ialah setiap program yang akan diperakui memerlukan persediaan dipercayai yang berbeza, yang menyusahkan. Groth16 telah digunakan dalam ZCash. Untuk butiran, sila rujuk juga blog Gambaran keseluruhan sistem bukti Groth 16.

3.3 Bulletproofs & IPA (2016)

Salah satu kelemahan KZG PCS ialah ia memerlukan persediaan yang dipercayai. Dalam kertas Argumen Sifar Pengetahuan Cekap 2016 untuk Litar Aritmetik dalam Kertas Tetapan Log Diskret oleh Bootle et al., sistem hujah pengetahuan sifar yang cekap untuk pembukaan komitmen Pedersen yang memenuhi perhubungan produk dalaman telah diperkenalkan. Sistem bukti produk dalaman mempunyai prover linear, dengan komunikasi dan interaksi logaritma, tetapi dengan pengesahan tempoh linear. Ia juga membangunkan skim komitmen polinomial yang tidak memerlukan persediaan yang dipercayai. Kedua-dua Halo 2 dan Kimchi menerima pakai idea menggunakan IPA PCS.

3.4 Sonic, Marlin, and Plonk (2019)

Sonic, Plonk, dan Marlin menyelesaikan masalah tetapan yang dipercayai untuk setiap program dalam Groth16 dengan memperkenalkan rentetan rujukan berstruktur yang biasa dan boleh dikemas kini. Marlin menyediakan sistem bukti berdasarkan R1CS, yang merupakan teras Aleo.

Plonk memperkenalkan skema aritmetik baharu (kemudian dipanggil Plonkish) dan menggunakan semakan produk besar untuk kekangan salinan. Plonkish juga membenarkan pengenalan pintu khusus untuk operasi tertentu, yang dipanggil pintu tersuai. Beberapa projek mempunyai versi tersuai Plonk, termasuk Aztec, ZK-Sync, Polygon ZKEVM, Kimchi Mina, Plonky2, Halo 2 dan Scroll, antara lain. Lihat blog Semua yang anda ingin tahu tentang Plonk.

3.5 Lookups (2018/2020)

Gabizon dan Williamson memperkenalkan plookups pada tahun 2020, menggunakan semakan produk besar untuk membuktikan bahawa nilai tertentu terkandung dalam jadual nilai pra-pengiraan. Walaupun hujah carian telah dicadangkan dalam Arya sebelum ini, pembinaannya memerlukan penentuan kepelbagaian carian, yang kurang cekap. Kertas PlonkUp menunjukkan cara untuk memperkenalkan hujah plookup ke dalam Plonk. Masalah dengan hujah carian ini ialah mereka memaksa prover untuk membayar keseluruhan jadual, tanpa mengira bilangan cariannya. Ini bermakna kos meja besar adalah besar, dan banyak usaha telah dilakukan untuk mengurangkan kos prover kepada bilangan carian yang digunakannya.

Haböck memperkenalkan LogUp, yang menggunakan derivatif logaritma untuk menukar cek produk kepada jumlah timbal balik. LogUp adalah penting untuk prestasi Polygon plonky2 ZKEVM (Melebihi Had: Menolak Sempadan ZK-EVM), yang memerlukan pembahagian keseluruhan jadual kepada berbilang modul STARK. Modul mesti dipautkan dengan betul dan carian merentas jadual diperlukan untuk menguatkuasakan operasi ini. Pelancaran LogUp-GKR memanfaatkan protokol GKR untuk meningkatkan prestasi LogUp. Caulk ialah hujah carian pertama di mana masa prover mempunyai hubungan sublinear dengan saiz jadualnya ialah ‍O (N log ⁡ N) dan storan ialah O (N), dengan N ialah saiz jadual. Beberapa penyelesaian lain diikuti, seperti Baloo, flookup, cq dan caulk+. Lasso mencadangkan beberapa penambahbaikan untuk mengelak daripada melakukan jadual apabila ia mempunyai struktur tertentu. Tambahan pula, prover Lasso hanya membayar untuk entri jadual yang diakses oleh operasi carian. Jolt menggunakan Lasso untuk membuktikan pelaksanaan mesin maya melalui carian.

3.6 Spartan (2019)

Spartan menyediakan IOP untuk litar yang diterangkan menggunakan R1CS, memanfaatkan sifat polinomial berbilang pembolehubah dan protokol sumcheck. Menggunakan skim komitmen polinomial yang sesuai, ia menghasilkan SNARK telus dengan prover tempoh linear.

3.7 HyperPlonk (2022)

HyperPlonk dibina atas idea Plonk menggunakan polinomial berbilang pembolehubah. Ia tidak bergantung pada quotient untuk menyemak penguatkuasaan kekangan, tetapi pada protokol sumcheck. Ia juga menyokong kekangan tahap tinggi tanpa menjejaskan masa berjalan prover. Memandangkan ia bergantung pada polinomial berbilang pembolehubah, tidak perlu melakukan FFT, dan skala masa larian prover secara linear dengan saiz litar. HyperPlonk memperkenalkan IOP pilihatur baharu yang sesuai untuk domain yang lebih kecil dan protokol pembukaan kelompok berasaskan sumcheck, yang mengurangkan beban kerja prover, saiz bukti dan masa pengesah.

3.8 Skim lipatan (2008/2021)

Nova memperkenalkan idea skema lipatan, iaitu kaedah baharu untuk melaksanakan pengiraan boleh pengesahan tambahan (IVC). Konsep IVC boleh dikesan kembali kepada Valiant, yang menunjukkan cara menggabungkan 2 bukti panjang k kk menjadi satu bukti panjang k kk. Ideanya ialah bukti rekursif boleh digunakan untuk membuktikan bahawa pelaksanaan daripada langkah i ii ke langkah i + 1 i+1i+1 adalah betul, dan untuk mengesahkan peralihan daripada langkah i − 1 i-1i−1 ke langkah i ii adalah betul, sekali gus membuktikan kes untuk sebarang pengiraan jangka panjang.

Nova boleh mengendalikan pengiraan seragam dengan baik kemudian dengan pengenalan Supernova, ia diperluaskan untuk mengendalikan pelbagai jenis litar. Nova menggunakan versi R1CS yang santai dan berfungsi pada lengkung elips yang mesra. Menggunakan kitaran lengkung mesra (cth., Lengkung Pasta) untuk melaksanakan IVC juga digunakan dalam Pickles, modul asas utama Mina, untuk mencapai keadaan ringkas. Walau bagaimanapun, idea melipat adalah berbeza daripada pengesahan SNARK rekursif. Idea akumulator lebih berkaitan dengan konsep bukti kumpulan. Halo memperkenalkan konsep pengumpulan sebagai alternatif kepada gabungan bukti rekursif. Protostar menyediakan penyelesaian IVC yang tidak seragam untuk Plonk, menyokong gerbang darjah tinggi dan carian vektor.

4. SNARK menggunakan fungsi cincang tahan perlanggaran

Pada masa yang sama dengan Pinocchio sedang dibangunkan, terdapat beberapa idea untuk menjana litar/skim aritmetik yang boleh membuktikan ketepatan pelaksanaan mesin maya. Walaupun aritmetik untuk membangunkan mesin maya mungkin lebih kompleks atau kurang cekap daripada menulis litar khusus untuk sesetengah atur cara, ia memberikan kelebihan bahawa mana-mana atur cara, tidak kira betapa kompleksnya, boleh dibuktikan dengan menunjukkan bahawa ia dilaksanakan dengan betul dalam mesin maya . Idea dalam TinyRAM kemudiannya diperhalusi dengan reka bentuk Cairo vm dan mesin maya seterusnya seperti zk-evms atau zkvms generik. Menggunakan fungsi cincang tahan perlanggaran menghapuskan keperluan untuk persediaan yang dipercayai atau penggunaan aritmetik lengkung eliptik, tetapi dengan kos pembuktian yang lebih panjang.

1) TinyRAM (2013)

Dalam SNARKs untuk C, SNARK berasaskan PCP dibangunkan untuk membuktikan ketepatan pelaksanaan program C, yang disusun ke dalam TinyRAM (Komputer Set Arahan Terkurang). Komputer menggunakan seni bina Harvard dengan memori capaian rawak boleh alamat peringkat bait. Mengambil kesempatan daripada bukan determinisme, saiz litar mempunyai hubungan kuasilinear dengan saiz pengiraan, dengan itu mengendalikan gelung berkaitan data sewenang-wenangnya, aliran kawalan dan akses memori dengan cekap.

2) STARKs (2018)

• STARKs telah dicadangkan oleh Ben Sasson et al. Saiz bukti yang dilaksanakannya ialah O(log2n), ia mempunyai pembukti dan pengesah yang cepat, tidak memerlukan persediaan yang dipercayai, dan dianggap selamat selepas kuantum. Ia pertama kali digunakan oleh Starkware/Starknet dengan mesin maya Kaherah. Komponen utamanya termasuk:

• Algebraic Intermediate Representation (AIR)

• dan protokol FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity).

STARK juga digunakan oleh projek lain (Polygon Miden, Risc0, Winterfell, Neptune), atau beberapa penyesuaian daripadanya (ZK-Sync's Boojum, Plonky2, Starky).

3) Ligero (2017)

• Ligero memperkenalkan sistem bukti yang saiz buktinya ialah O (root n), di mana n ialah saiz litar. Ia menyusun pekali polinomial ke dalam bentuk matriks dan menggunakan kod linear.

• Brakedown dibina di atas Ligero dan memperkenalkan idea skim komitmen polinomial bebas domain.

5 Beberapa perkembangan baru dalam ZKP

Menggunakan sistem bukti yang berbeza dalam pengeluaran menunjukkan kelebihan setiap kaedah dan membawa perkembangan baru. Contohnya, aritmetik plonkish menyediakan cara mudah untuk memasukkan get tersuai dan hujah carian; FRI kerana PCS menunjukkan prestasi cemerlang, mendahului Plonky. Begitu juga, menggunakan semakan produk besar dalam AIR (menghasilkan AIR rawak dengan prapemprosesan) meningkatkan prestasinya dan memudahkan hujah akses memori. Janji berdasarkan fungsi cincang telah diterima - sama ada berdasarkan kelajuan fungsi cincang dalam perkakasan atau pengenalan fungsi cincang mesra SNARK baharu.

1) Skim Komitmen Polinomial Baharu (2023)

Dengan kemunculan SNARK yang cekap berdasarkan polinomial multivariate (seperti Spartan atau HyperPlonk), terdapat peningkatan minat terhadap skim komitmen baharu yang sesuai untuk polinomial tersebut. Binius, Zeromorph dan Basefold semuanya mencadangkan bentuk baharu khusus untuk polinomial berbilang linear. Binius mempunyai kelebihan untuk mewakili jenis data dengan overhed sifar (manakala banyak sistem bukti menggunakan sekurang-kurangnya elemen medan 32-bit untuk mewakili satu bit) dan berfungsi pada medan binari. Binius berjanji untuk didasarkan pada Brakedown dan direka bentuk untuk menjadi domain-agnostik. Basefold menyamaratakan FRI kepada kod di luar Reed-Solomon, menghasilkan PCS bebas domain.

2) Sistem Kekangan Boleh Disesuaikan (CCS) (2023)

CCS menyamaratakan R1CS, menangkap aritmetik R1CS, Plonkish dan AIR secara serentak tanpa sebarang overhed. Menggabungkan CCS dengan Spartan IOP menghasilkan SuperSpartan, yang menyokong kekangan tahap tinggi tanpa memerlukan prover menanggung kos kriptografi yang berskala dengan tahap kekangan. Khususnya, SuperSpartan menjana SNARK untuk AIR dengan prover masa linear.

6. Kesimpulan

Artikel ini menerangkan kemajuan SNARK sejak diperkenalkan pada pertengahan 1980-an. Kemajuan dalam sains komputer, matematik dan perkakasan, ditambah pula dengan pengenalan rantaian blok, telah melahirkan SNARK baharu yang lebih cekap, membuka pintu kepada banyak aplikasi yang boleh mengubah masyarakat kita. Penyelidik dan jurutera mencadangkan penambahbaikan dan pelarasan kepada SNARK berdasarkan keperluan mereka, memfokuskan pada saiz bukti, penggunaan memori, tetapan ketelusan, keselamatan pasca-kuantum, masa prover dan masa pengesah.

Walaupun pada mulanya terdapat dua garisan utama (SNARK dan STARK), sempadan antara keduanya telah mula pudar, cuba menggabungkan kelebihan sistem bukti yang berbeza. Contohnya, menggabungkan skema aritmetik yang berbeza dengan skim komitmen polinomial baharu. Sistem pembuktian baharu boleh dijangka akan terus muncul dan prestasi akan bertambah baik, dan akan menjadi sukar bagi sesetengah sistem yang memerlukan sedikit masa untuk menyesuaikan diri untuk mengikuti perkembangan ini, melainkan alatan itu boleh digunakan dengan mudah tanpa mengubah beberapa infrastruktur teras .

Atas ialah kandungan terperinci IOSG: Apakah daya penggerak untuk inovasi berterusan dalam bukti pengetahuan sifar?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!