Ditulis oleh: Kang Shuiyue, CEO Fox Tech; Meng Xuanji, Kepala Ilmuwan Fox Tech
Kata pengantar
Teknologi zero-knowledge proof dalam kriptografi banyak digunakan di dunia web3, termasuk penghitungan privasi, zkRollup, dll. Diantaranya, FOAKS yang digunakan oleh proyek Layer2 FOX adalah algoritma bukti tanpa pengetahuan. Di antara rangkaian aplikasi yang disebutkan di atas, terdapat dua atribut yang sangat penting untuk algoritma zero-knowledge proof, yaitu efisiensi dan interaktivitas algoritma.
Pentingnya efisiensi algoritme sudah terbukti dengan sendirinya. Algoritme yang efisien dapat secara signifikan mengurangi waktu berjalan sistem, sehingga mengurangi latensi klien dan secara signifikan meningkatkan pengalaman dan efisiensi pengguna. Ini juga merupakan alasan penting mengapa FOAKS berkomitmen untuk mencapai waktu bukti linier.
Di sisi lain, dari perspektif kriptografi, desain sistem pembuktian tanpa pengetahuan sering kali bergantung pada beberapa putaran interaksi antara pembukti dan pemverifikasi. Misalnya, dalam cerita tentang "gua tanpa pengetahuan" yang digunakan dalam banyak artikel sains populer yang memperkenalkan bukti tanpa pengetahuan, realisasi bukti tersebut bergantung pada berbagai putaran interaksi transfer informasi antara Alibaba (pemeriksa) dan reporter (verifikator). Namun kenyataannya, dalam banyak skenario aplikasi, mengandalkan interaksi akan membuat sistem tidak lagi tersedia, atau meningkatkan latensi secara signifikan. Sama seperti di sistem zkRollup, kami berharap pembukti (yaitu, folder di FOX) dapat menghitung nilai pembuktian yang benar secara lokal tanpa bergantung pada interaksi dengan pemverifikasi.
Dari perspektif ini, bagaimana mengubah protokol interaktif tanpa bukti pengetahuan menjadi protokol non-interaktif adalah pertanyaan yang sangat berarti. Pada artikel ini, kami akan memperkenalkan proses FOX menggunakan heuristik Fiat-Shamir klasik untuk menghasilkan tantangan dalam Brakedown untuk mengimplementasikan protokol non-interaktif.
Tantangan dalam bukti tanpa pengetahuan
Algoritme bukti tanpa pengetahuan menjadi sangat populer dengan penyebaran aplikasinya. Dalam beberapa tahun terakhir, berbagai algoritma termasuk FOAKS, Orion, zk-stark, dll. Logika pembuktian inti dari algoritma ini, serta protokol sigma awal dalam kriptografi, adalah bahwa pembukti (Prover) pertama-tama mengirimkan nilai tertentu ke pemverifikasi (Verifier), dan pemverifikasi menghasilkan tantangan (Challenge) melalui nomor acak lokal , dan mengirimkan ini Nilai tantangan yang dihasilkan secara acak dikirim ke pembukti, dan pembukti harus memiliki pengetahuan nyata untuk membuat respons yang lolos verifikasi dengan probabilitas tinggi. Misalnya, di gua tanpa pengetahuan, reporter melempar koin dan memberi tahu Alibaba apakah akan keluar dari kiri atau kanan. "Kiri dan kanan" di sini adalah tantangan bagi Alibaba pasti bisa keluar dari Go ke arah yang diperlukan, jika tidak, ada setengah kemungkinan gagal.
Di sini kami mencatat bahwa pembuatan Tantangan adalah langkah yang sangat penting. Ini memiliki dua persyaratan, acak dan tidak dapat diprediksi oleh pembuktian. Pertama, keacakan menjamin sifat probabilistiknya. Poin kedua, jika pembukti dapat memprediksi nilai tantangan, berarti keamanan protokol telah hancur. Pembukti dapat lolos verifikasi tanpa sepengetahuannya. Kita dapat melanjutkan analoginya keluar, dia akan melakukannya Bahkan jika tidak ada mantra, Anda dapat memasuki sisi itu terlebih dahulu, dan hasilnya akan tetap melewati kesepakatan.
Oleh karena itu, diperlukan suatu metode yang memungkinkan pembukti menghasilkan bilangan acak yang tidak dapat diprediksi secara lokal, dan pada saat yang sama dapat diverifikasi oleh verifikator, sehingga protokol non-interaktif dapat diimplementasikan.
Fungsi Hash
Nama fungsi hash mungkin sudah tidak asing lagi bagi kita. Baik itu masalah matematika untuk penambangan dalam protokol konsensus Bitcoin POW, mengompresi jumlah data, membuat kode verifikasi pesan, dll., fungsi hash ada di mana-mana. Dalam berbagai protokol yang disebutkan di atas, berbagai properti fungsi hash sebenarnya digunakan.
Secara khusus, properti fungsi hash aman mencakup poin-poin berikut:
Kompresibilitas: Fungsi hash deterministik dapat memampatkan pesan dengan panjang berapa pun menjadi panjang tetap.
Efisiensi: Dengan adanya masukan x, mudah untuk menghitung keluaran h(x).
Resistensi tumbukan: Dengan adanya masukan x1, sulit untuk mencari masukan lain x2, x1x2, h(x1) = h(x2).
Perhatikan bahwa jika fungsi hash memenuhi ketahanan tumbukan, fungsi tersebut harus memenuhi sifat satu arah, artinya, dengan keluaran y, sulit untuk menemukan x yang memenuhi h(x) = y. Dalam kriptografi, secara teori tidak mungkin membangun fungsi yang benar-benar memenuhi sifat satu arah, namun fungsi hash pada dasarnya dapat dianggap sebagai fungsi satu arah dalam aplikasi praktis.
Dengan cara ini, dapat ditemukan bahwa aplikasi yang disebutkan di atas sesuai dengan beberapa properti fungsi hash yang berbeda. Pada saat yang sama, kami mengatakan bahwa fungsi hash juga memainkan peran yang sangat penting dalam memberikan keacakan generator bilangan acak sempurna saat ini tidak dapat dibuat, tetapi fungsi hash juga dapat memainkan peran ini dalam praktiknya, yang menjadi dasar bagi teknik heuristik (Heuristik) Fiat-Shamir yang akan kami perkenalkan nanti.
Heuristik Fiat-Shamir
Faktanya, heuristik Fiat-Shamir menggunakan fungsi hash untuk melakukan hash pada skrip yang dibuat sebelumnya untuk mendapatkan nilai, yang digunakan sebagai nilai tantangan.
Karena fungsi hash H diperlakukan sebagai fungsi acak, tantangan dipilih secara acak dan seragam, tidak bergantung pada informasi dan komitmen publik pembuktinya. Analisis keamanan percaya bahwa Alice tidak dapat memprediksi keluaran H dan hanya dapat memperlakukannya sebagai ramalan. Dalam hal ini, kemungkinan Alice merespons dengan benar tanpa mengikuti protokol (terutama ketika dia tidak mengetahui rahasia yang diperlukan) berbanding terbalik dengan ukuran rentang H.
Gambar 1: Bukti non-interaktif menggunakan Fiat-Shamir Heuristic
FOAKS non-interaktif
Pada bagian ini, kami secara khusus mendemonstrasikan penerapan heuristik Fiat-Shamir dalam protokol FOAKS, yang terutama digunakan untuk menghasilkan bagian Brakedown dari tantangan untuk mencapai FOAKS non-interaktif.
Pertama-tama, kita melihat bahwa di antara langkah-langkah Brakedown untuk menghasilkan bukti, langkah-langkah yang perlu ditantang adalah "uji perkiraan" dan bagian pembuktian dari Merkle Tree (pembaca dapat merujuk ke artikel sebelumnya "Memahami Protokol Komitmen Polinomial Pengereman di FOAKS"). Untuk poin pertama, proses aslinya adalah pembuktian membutuhkan vektor acak yang dihasilkan oleh pemverifikasi di sini. Proses perhitungannya seperti terlihat pada gambar di bawah ini:
Gambar 2: Pemeriksaan Brakedown pada FOAKS bukti non-interaktif
Sekarang kita menggunakan fungsi hash dan membiarkan pembuktian menghasilkan vektor acak ini sendiri.
Misalkan γ0=H(C1,R, r0,r1). Sejalan dengan itu, pada perhitungan verifikasi verifikator, langkah penghitungan γ0 ini juga perlu ditambahkan. Berdasarkan struktur ini dapat diketahui bahwa sebelum menghasilkan komitmen, pembukti tidak dapat memprediksi nilai tantangan terlebih dahulu, sehingga tidak dapat “menipu” berdasarkan nilai tantangan terlebih dahulu, yaitu dihasilkan nilai komitmen palsu yang sesuai. Pada saat yang sama, menurut hash Keacakan keluaran fungsi, nilai tantangan ini juga memenuhi keacakan.
Untuk poin kedua, misalkan Î =H(C1,R, r0,r1,c1,y1,cγ0,yγ0).
Kami menggunakan kodesemu untuk memberikan fungsi pembuktian dan verifikasi dalam komitmen polinomial Brakedown non-interaktif yang dimodifikasi, yang juga merupakan fungsi yang digunakan dalam sistem FOAKS.
fungsi komputer. Berkomitmen(ϕ)：
Parse adalah matriks k × k. Pepatah secara lokal menghitung kode tensor yang mengkode C1,C2,C1 adalah matriks k × n,C2 adalah matriks n × n.
untuk saya ∈ [n] lakukan
Hitung akar pohon Merkle Roott=Merkle.Commit(C2[:,i])
Hitung akar pohon Merkle R=Merkle.Commit([Root0,......Rootn-1]), dan keluaran R sebagai komitmen.
fungsi komputer. Pepatah (ϕ, X, R)
Pepatah menghasilkan vektor acak γ0 ∈ Fk dengan menghitung: γ0 =H(C1,R, r0,r1)
Kedekatan:
Konsistensi:
Prover mengirimkan c1,y1,cγ0,yγ0 ke verifikator.
Prover menghitung vektor Î sebagai tantangan, di mana Î = H(C1,R, r0,r1,c1,y1,cγ0,yγ0)
untuk idx ∈ Î lakukan
Prover mengirimkan C1 [:,idx] dan bukti pohon Merkle dari Rootidx untuk C2 [:,idx] di bawah R ke verifikator
fungsi komputer. VERIFY_EVAL(ΠX,X,y= ϕ (X),R)
Kedekatan: ∀idx ∈ Î, Cγ0 [idx] == <γ0, C1[:,idx]> dan Ec(yγ0) == Cγ0
Konsistensi: ∀idx ∈ Î, C1 [idx] == <γ0, C1[:,idx]> dan Ec(y1) == C1
kamu==
∀idx ∈ Î, Ec ( C1[:,idx]) konsisten dengan ROOTidx, dan bukti pohon Merkle ROOTidx valid.
Output diterima jika semua kondisi di atas terpenuhi. Jika tidak, keluaran akan ditolak.
Kesimpulan
Banyak algoritme pembuktian tanpa pengetahuan mengandalkan interaksi antara pemver dan pemverifikasi pada awal desainnya. Namun, protokol pembuktian interaktif ini tidak cocok untuk digunakan dalam skenario aplikasi yang mengejar efisiensi tinggi dan memerlukan overhead komunikasi jaringan yang besar, seperti on-net. perlindungan privasi data rantai. dan zkRollup dan sebagainya. Melalui heuristik Fiat-Shamir (Heuristik), pembukti dapat secara lokal menghasilkan "tantangan" nomor acak tanpa merusak keamanan protokol, dan dapat diverifikasi oleh pembukti. Menurut metode ini, FOAKS juga menerapkan pembuktian non-interaktif dan menerapkannya pada sistem.
referensi
1.Fiat, Amos; Shamir, Adi (1987). "Cara Membuktikan Diri: Solusi Praktis untuk Masalah Identifikasi dan Tanda Tangan". Kemajuan dalam Kriptologi - CRYPTO' 86. Catatan Kuliah Ilmu Komputer. Pegas Berlin Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html