Judul asli: "Cara merancang skema rekursi bukti yang indah" Penulis asli: Lin Yanxi, CTO Fox Tech, kepala ilmuwan Fox Tech Kata Pengantar: Hampir semua masalah yang ditemui di trek zkRollup dan zkEVM, di antaranya adalah Mereka adalah pada dasarnya masalah algoritmik. Alasan utama mengapa akselerasi perangkat keras ZKP sering disebutkan adalah karena algoritma saat ini umumnya lambat. Untuk menghindari situasi yang memalukan seperti "algoritme saja tidak cukup, perangkat keras akan menggantikannya", kita harus menyelesaikan masalah secara algoritmik. Merancang skema bukti perulangan yang bagus adalah kunci untuk memecahkan masalah ini. Dengan terus berkembangnya kontrak pintar, semakin banyak aplikasi web3 yang keluar secara bertahap, dan volume transaksi Layer1 tradisional seperti Ethereum meningkat pesat dan kemacetan dapat terjadi kapan saja. Bagaimana mencapai efisiensi yang lebih tinggi sekaligus memastikan keamanan yang diberikan oleh Lapisan 1 telah menjadi masalah mendesak yang perlu dipecahkan. Untuk Ethereum, zkRollup menggunakan algoritme bukti tanpa pengetahuan sebagai komponen dasar untuk memindahkan penghitungan mahal yang awalnya perlu dilakukan pada lapisan luar rantai 1 dan memberikan bukti kebenaran eksekusi pada rantai. Lagu ini terutama mencakup proyek-proyek seperti StarkWare, zkSync, Scroll dan Fox Tech. Faktanya, dalam desain zkRollup, terdapat persyaratan efisiensi yang sangat tinggi: diharapkan nilai pembuktian yang dikirimkan cukup kecil, sehingga dapat mengurangi beban perhitungan Layer1. Untuk mendapatkan panjang pembuktian yang cukup kecil, berbagai proyek zkRollup meningkatkan algoritme dan desain arsitektur. Misalnya, Fox telah mengembangkan algoritme pembuktiannya sendiri, FOAKS, berdasarkan algoritme pembuktian tanpa pengetahuan terbaru untuk mendapatkan waktu pembuktian dan panjang pembuktian yang optimal. Selain itu, pada tahap verifikasi pembuktian, cara yang paling sepele adalah dengan menghasilkan bukti secara linier dan memverifikasinya secara berurutan. Untuk meningkatkan efisiensi, hal pertama yang dipikirkan semua orang adalah mengemas beberapa bukti menjadi satu bukti, yang biasa disebut dengan agregasi bukti (Proof Aggregation). Secara intuitif, memverifikasi bukti yang dihasilkan oleh zkEVM adalah proses linier, dan pemverifikasi (Verifier) ​​​​perlu memverifikasi setiap nilai bukti yang dihasilkan secara bergantian. Namun, efisiensi metode verifikasi ini relatif rendah, dan overhead komunikasi relatif besar. Untuk skenario zkRollup, overhead sisi verifikator yang lebih tinggi berarti lebih banyak penghitungan lapisan Layer1, yang juga akan menyebabkan biaya Gas lebih tinggi.Mari kita mulai dengan sebuah contoh: Alice ingin membuktikan kepada dunia bahwa dia pergi ke Fox Park dari tanggal 1 hingga 7 bulan ini. Untuk melakukan ini, dia dapat mengambil foto di taman dengan koran hari itu setiap hari dari tanggal 1 hingga tanggal 7, dan paket 7 foto ini akan menjadi buktinya. Gambar 1: Skema agregasi bukti umum. Dalam contoh di atas, memasukkan 7 foto langsung ke dalam amplop adalah agregasi bukti dalam arti intuitif, ini berhubungan dengan menghubungkan bukti-bukti yang berbeda dan memverifikasinya secara linier dalam urutan, yaitu, pertama Verifikasi bukti pertama, lalu bukti kedua, dan bukti berikutnya. Masalahnya, pendekatan ini tidak akan mengubah ukuran pembuktian maupun waktu pembuktian. Efeknya sama dengan pembuktian dan verifikasi satu per satu. Jika Anda ingin mencapai kompresi ruang tingkat logaritmik, Anda perlu menggunakan bukti rekursif (Proof Recursion) yang disebutkan di bawah. Skema pembuktian rekursif yang digunakan oleh Halo2 dan STARK Untuk lebih menjelaskan apa itu pembuktian rekursif, mari kita kembali ke contoh di atas. 7 foto Alice sebenarnya adalah 7 bukti. Sekarang pertimbangkan untuk menggabungkannya, sehingga Alice dapat mengambil foto di No. 1, mengambil foto dengan koran No. 2 di No. 2, dan mengambil foto No. 2 dan koran No. 3 di No. 3 .foto. Dengan analogi, Alice mengambil foto terakhir pada tanggal 7 dengan foto tanggal 6 dan koran pada tanggal 7. Ketika teman-teman lain melihat foto terakhir tanggal 7, mereka dapat memverifikasi bahwa antara tanggal 1 dan 7 Alice semua pergi ke taman. . Seperti yang Anda lihat, tujuh foto bukti sebelumnya telah dikompres menjadi satu. Teknik utama dalam proses ini adalah "foto yang berisi foto", yang setara dengan menyatukan foto sebelumnya ke foto berikutnya secara rekursif. Ini berbeda dengan menyatukan banyak foto lalu mengambil satu foto. Trik pembuktian rekursif zkRollup dapat mengurangi ukuran bukti secara signifikan. Secara khusus, setiap transaksi akan menghasilkan bukti. Kita asumsikan rangkaian perhitungan transaksi asli adalah C0, P0 adalah bukti kebenaran C0, V0 adalah proses perhitungan verifikasi P0, dan pembukti (Prover) juga mengubah V0 menjadi yang sesuai. rangkaian dilambangkan dengan C0'. Saat ini, untuk proses perhitungan pembuktian C1 dari transaksi lain, rangkaian C0' dan C1 dapat digabungkan dengan cara ini, setelah pembuktian kebenaran P1 dari rangkaian gabungan diverifikasi, hal ini setara dengan memverifikasi dua di atas pada saat yang sama. Kebenaran suatu transaksi tercapai, yaitu kompresi tercapai.Melihat kembali proses di atas, kita dapat menemukan bahwa prinsip kompresi adalah mengubah proses verifikasi menjadi sebuah rangkaian, dan kemudian menghasilkan "bukti pembuktian". Jadi dari sudut pandang ini, ini adalah operasi yang dapat dilakukan secara rekursif secara terus menerus , jadi disebut juga bukti rekursif. Gambar 2: Skema bukti rekursif yang digunakan oleh Halo2 dan Stark Skema Proof Recursion yang digunakan oleh Halo2 dan STARK dapat menghasilkan bukti secara paralel dan menggabungkan beberapa bukti, sehingga kebenaran dari beberapa eksekusi transaksi dapat diverifikasi sekaligus memverifikasi satu nilai bukti, yang mana dapat memampatkan overhead perhitungan dan sangat meningkatkan efisiensi sistem. Namun, optimasi tersebut masih berada pada tingkat di atas algoritma bukti tanpa pengetahuan tertentu. Untuk lebih meningkatkan efisiensi, kita memerlukan optimasi dan inovasi tingkat rendah. Algoritma FOAKS yang dirancang oleh Fox melakukan ini dengan menerapkan ide rekursif di dalam sebuah bukti . Sampai pada titik ini. Skema rekursi terbukti yang digunakan oleh FOAKS adalah proyek zkRollup berbasis zkEVM di Fox Tech. Dalam sistem pembuktiannya juga menggunakan teknik pembuktian rekursif, namun konotasinya berbeda dengan metode rekursif di atas. Perbedaan utamanya adalah Fox menggunakan ide rekursi di dalam pembuktiannya. Untuk mengungkapkan ide inti dari pembuktian rekursif yang digunakan oleh Fox, yaitu mereduksi permasalahan yang ingin dibuktikan secara terus menerus hingga permasalahan yang direduksi menjadi cukup sederhana, kita perlu memberikan contoh lain. Dalam contoh di atas, Alice mengambil foto untuk membuktikan bahwa dia pergi ke Fox Park pada hari tertentu, jadi Bob mengajukan saran yang berbeda. Dia percaya bahwa masalah pembuktian bahwa Alice pergi ke taman dapat direduksi menjadi pembuktian bahwa ponsel Alice telepon pergi ke taman. Dan pembuktian masalah ini dapat direduksi menjadi pembuktian bahwa telepon seluler Alice berada dalam lingkup taman. Jadi, untuk membuktikan bahwa Alice pernah ke taman, dia hanya perlu mengirimkan lokasinya menggunakan ponselnya saat dia berada di taman. Dengan cara ini, ukuran bukti berubah dari foto asli (data berdimensi sangat tinggi) menjadi data 3 dimensi (lintang, bujur, dan waktu), sehingga secara efektif menghemat biaya. Contoh ini tidak sepenuhnya tepat, karena beberapa orang mungkin mempertanyakan bahwa fakta bahwa ponsel Alice pernah ke Fox Park tidak berarti bahwa Alice sendiri pernah ke sana, namun dalam situasi sebenarnya, proses reduksi ini sangat ketat secara matematis.Secara khusus, penggunaan bukti rekursif Fox adalah rekursi pada tingkat rangkaian. Saat melakukan pembuktian tanpa pengetahuan, kita akan menuliskan soal yang ingin dibuktikan ke dalam rangkaian, dan kemudian menghitung beberapa persamaan yang perlu dipenuhi melalui rangkaian tersebut. Alih-alih menunjukkan bahwa persamaan-persamaan tersebut terpenuhi, kita menuliskan persamaan-persamaan tersebut ke dalam rangkaian-rangkaian lagi, dan seterusnya, hingga akhirnya persamaan untuk membuktikan bahwa persamaan-persamaan tersebut terpenuhi menjadi cukup sederhana sehingga kita dapat dengan mudah membuktikannya secara langsung. Dari proses ini kita dapat melihat bahwa melakukan hal tersebut lebih dekat dengan arti “rekursi”. Perlu disebutkan bahwa tidak semua algoritma dapat menggunakan teknik rekursif ini. Diasumsikan bahwa setiap rekursi akan mengubah bukti dengan kompleksitas O(n) menjadi bukti O(f(n)), dan perhitungannya bersifat rekursif. proses itu sendiri Kompleksitasnya adalah O(g(n)). Setelah satu rekursi, total kompleksitas komputasi menjadi O1(n)=O(f(n))+O(g(n)). (n )=O(f(f(n)))+O(g(n))+O(g(f(n))), setelah tiga kali menjadi O3(n)=O(f(f( f(n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),..., dan seterusnya. Oleh karena itu, hanya jika f dan g adalah dua fungsi yang sesuai dengan karakteristik algoritma yang memenuhi Ok(n) untuk k tertentu. Gambar 3: Skema pembuktian rekursif yang digunakan oleh ZK-FOAKS. Kesimpulan Kompleksitas pembuktian selalu menjadi yang paling penting dalam aplikasi pembuktian tanpa pengetahuan. Salah satu kuncinya adalah kompleksitas pembuktian akan menjadi semakin penting karena hal-hal yang harus dibuktikan menjadi semakin kompleks, terutama dalam skenario aplikasi ZK raksasa seperti zkEVM, kompleksitas pembuktian akan menjadi semakin penting. dampak besar pada kinerja dan kinerja produk. Pengalaman pengguna memiliki dampak yang menentukan. Di antara banyak metode untuk mengurangi kompleksitas pembuktian akhir, optimalisasi algoritme inti adalah yang paling penting. Fox merancang skema pembuktian rekursif yang cerdik berdasarkan algoritme paling mutakhir, dan menggunakan teknologi ini untuk menciptakan solusi yang mutakhir. paling cocok untuk zkEVM. Algoritma ZK-FOAKS diharapkan menjadi pemimpin kinerja di dunia zkRollup. Referensi https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Artikel ini berasal dari kiriman dan tidak mewakili pandangan BlockBeats