Terokai sebab sebenar di sebalik kemunculan inovasi abadi dalam bukti pengetahuan sifar

Ditulis oleh: LambdaClass s (zk-SNARKs) ialah sejenis Primitif kriptografi yang kuat yang membolehkan pembukti meyakinkan pengesah tentang ketepatan pernyataan tanpa mendedahkan sebarang maklumat di luar penyataan. 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 sejak pertengahan 1980-an.

Pembangunan zk-SNARKs telah dipercepatkan dengan pesat sejak pelancaran Bitcoin dan Ethereum kerana keupayaan mereka untuk membuat skala 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 diterangkan oleh Ben-Sasson, beberapa tahun kebelakangan ini telah menyaksikan letupan Kambrium dalam bukti kriptografi. 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 yang ketara, mereka masih berkongsi sifat penting: pengesahan bukti yang cepat. Kesukaran yang berkaitan dengan menukar lapisan asas seperti Ethereum diselesaikan dalam lapisan yang boleh mengesahkan bukti dan mudah menyesuaikan diri dengan sistem bukti baharu. Artikel ini akan memberikan gambaran ringkas tentang pelbagai ciri SNARK.

1) Andaian kriptografi: fungsi cincang tahan perlanggaran, masalah logaritma diskret pada lengkung elips, 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: Origins (1985/1989).

Bidang pembuktian pengetahuan sifar muncul dalam kesusasteraan akademik dengan kertas "Kerumitan pengetahuan sistem pembuktian interaktif" oleh Goldwasser, Micali dan Rackoff. Untuk perbincangan tentang asal usul, tonton video Januari 2023 ZKP MOOC Kuliah 1: Pengenalan dan Sejarah ZKP. Kertas kerja ini memperkenalkan konsep ploidi, 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 penjumlahan penilaian polinomial multivariat kepada penilaian tunggal mata yang dipilih secara rawak.

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

Protokol GKR (lihat kertas Delegating Computation: Interactive Proofs for Muggles) ialah protokol interaktif di mana prover beroperasi secara linear dengan bilangan get dalam litar dan verifier beroperasi secara sublinear dengan saiz litar. Dalam protokol, prover dan verifier bersetuju 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 bilinear pada tahun 2010 Komitmen Bersaiz Malar kepada Polinomial dan Aplikasinya. Komitmen terdiri daripada elemen kumpulan tunggal, dan komitter secara berkesan membuka komitmen kepada sebarang penilaian yang betul bagi polinomial. Tambahan pula, 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 generik 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)

4) Sonic, Marlin, dan Plonk (2019)

5) Carian (2018/2020)

6) Spartan (2019) (2019)

8) Skim lipatan (2008/2021)

3.1 Pinocchio (2013)

Pinocchio (lihat karya Pinocchio: Nearly Practical Verifiable Computation) ialah zk-SNARK praktikal dan boleh digunakan 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 kepada QAP. Protokol memerlukan pengesah untuk menjana kunci khusus litar. Ia menggunakan gandingan lengkung eliptik untuk menyemak persamaan. Asymptotic asymptotic untuk penjanaan bukti dan skala tetapan kunci secara linear dengan saiz pengiraan, dan skala tempoh pengesahan secara linear dengan saiz input dan output awam.

3.2 Groth 16 (2016)

Kertas Groth 2016 On the Size of Pairing-based Non-interactive Arguments 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. Argumen Sifar Pengetahuan Cekap 2016 Bootle et al. untuk Litar Aritmetik dalam kertas Tetapan Log Diskret memperkenalkan sistem hujah pengetahuan sifar yang cekap untuk pembukaan komitmen Pedersen yang memenuhi perhubungan produk dalaman. 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 mengguna pakai idea IPA PCS.

3.4 Sonic, Marlin, and Plonk (2019)

Sonic, Plonk, dan Marlin menyelesaikan masalah tetapan kepercayaan 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 2020, menggunakan semakan produk besar untuk membuktikan bahawa nilai terkandung dalam jadual nilai prakiraan. Walaupun hujah carian sebelum ini dicadangkan dalam Arya, 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. Pengenalan LogUp-GKR memanfaatkan protokol GKR untuk meningkatkan prestasi LogUp. Caulk ialah hujah carian pertama yang masa provernya mempunyai hubungan sublinear dengan saiz jadual, dengan masa prapemprosesan O ( N log ⁡ N ) dan penyimpanan O ( N ), di mana N ialah saiz jadual. Beberapa skim 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 memanfaatkan 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 hasil bagi untuk menyemak penguatkuasaan kekangan, sebaliknya bergantung 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 kerja prover, saiz bukti dan masa pengesah.

3.8 Skim lipatan (2008/2021)

Nova memperkenalkan idea skema lipatan, yang merupakan cara 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 pembangunan Pinocchio, 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 kepada TinyRAM (Komputer Set Arahan Terkurang). Komputer menggunakan seni bina Harvard dengan memori capaian rawak boleh alamat peringkat bait. Memanfaatkan bukan determinisme, skala saiz litar secara kuasilinear dengan saiz pengiraan, membolehkan pengendalian yang cekap bagi gelung berkaitan data sewenang-wenangnya, aliran kawalan dan akses memori.

2) STARKs (2018)

STARKs telah dicadangkan oleh Ben Sasson et al. Pelaksanaannya mempunyai saiz bukti O(log2n), 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 kepada perkembangan baru. Contohnya, aritmetik plonkish menyediakan cara mudah untuk memasukkan get tersuai dan hujah carian; FRI menunjukkan prestasi cemerlang sebagai PCS, mendahului Plonky. Begitu juga, menggunakan semakan produk besar dalam AIR (menghasilkan AIR rawak dengan argumen 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 overhed sifar untuk mewakili jenis data (manakala banyak sistem bukti menggunakan sekurang-kurangnya elemen medan 32-bit untuk mewakili satu bit) dan berfungsi pada domain binari. Binius commit adalah berdasarkan 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 sambil menangkap aritmetik R1CS, Plonkish dan AIR tanpa sebarang overhed. Menggabungkan CCS dengan Spartan IOP menghasilkan SuperSpartan, yang menyokong kekangan tahap tinggi tanpa memerlukan prover untuk 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 Terokai sebab sebenar di sebalik kemunculan inovasi abadi dalam bukti pengetahuan sifar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!