Crypto Gloss

Nova: Folding Scheme untuk Recursive SNARK yang Lebih Cepat dan Sederhana

Penulis Kothapalli, Abhiram; Setty, Srinath; Tzialla, Ioanna
Tahun 2021
Proyek Nova (Microsoft Research)
Lisensi MIT
Sumber Resmi eprint.iacr.org/2021/370.pdf
Disclaimer: Halaman ini merupakan ringkasan dan analisis edukatif dari whitepaper atau makalah teknis resmi. Konten ini disajikan untuk tujuan pendidikan semata dan bukan merupakan saran investasi atau keuangan. Selalu baca dokumen asli dan lakukan riset mandiri sebelum mengambil keputusan keuangan apa pun.

“Nova: Recursive Zero-Knowledge Arguments from Folding Schemes” (2021, CRYPTO 2022) oleh Abhiram Kothapalli, Srinath Setty, dan Ioanna Tzialla (Microsoft Research) memperkenalkan folding scheme — teknik untuk mengomposisi ZK proof secara rekursif yang jauh lebih sederhana dan efisien dari pendekatan rekursif sebelumnya. Alih-alih memverifikasi SNARK sebelumnya di dalam SNARK saat ini (yang memerlukan sirkuit besar), Nova melipat (folds) dua instance constraint yang sama menjadi satu instance “relaxed” — akumulasi yang murah tanpa verifikasi SNARK di tengah proses.

Masalah yang Dipecahkan

Incremental Verifiable Computation (IVC) memerlukan prover untuk menghasilkan proof bahwa:

  1. Langkah N dihitung dengan benar
  2. Ada proof valid untuk langkah 0 hingga N-1

Metode sebelumnya (Halo, Halo2) memerlukan proof untuk langkah N berisi verifikasi SNARK dari langkah N-1 — mahal karena verifier SNARK adalah sirkuit besar. Pendekatan SNARK-in-SNARK ini membutuhkan ribuan gate kriptografis hanya untuk memverifikasi satu proof sebelumnya.

Cara Kerja Folding Scheme

Wawasan kunci Nova: alih-alih memverifikasi instance sebelumnya, lipat dua instance R1CS menjadi satu instance “relaxed R1CS”.

R1CS standar: Az ⊙ Bz = Cz (perkalian elemen-per-elemen)

Relaxed R1CS: Az ⊙ Bz = u·Cz + E (memungkinkan accumulated error term E)

Melipat dua instance menggabungkannya menjadi satu instance relaxed dengan overhead minimal — tanpa verifikasi SNARK selama folding. Hanya di akhir accumulator dikonversi menjadi SNARK proof final.

Successor: HyperNova dan SuperNova

  • HyperNova (2023): Menggunakan multilinear polynomial IOPs (sumcheck) alih-alih R1CS untuk fleksibilitas lebih besar
  • SuperNova (2022): Memperluas Nova ke banyak sirkuit berbeda (bukan hanya pengulangan sirkuit yang sama) — memungkinkan ZK VM di mana setiap instruksi adalah sirkuit berbeda

Dampak pada zkVM

Skema berbasis Nova digunakan dalam:

  • RISC Zero: Nova/HyperNova untuk komposisi proof rekursif dalam zkVM berbasis RISC-V
  • Lita (Jolt): Menggunakan pendekatan lookup argument + folding yang terinspirasi Nova
  • Nexus zkVM: Dibangun di atas folding scheme untuk IVC
  • ProtoGalaxy: Generalisasi dari Nova ke beberapa instance secara bersamaan

Mengapa Nova Penting

Nova membuktikan bahwa rekursi SNARK yang efisien tidak harus mahal. Sebelum Nova, sistem rekursif (Halo2) memerlukan menit per proof. Nova-style folding memungkinkan proof rekursif dalam hitungan detik di hardware biasa, membuka jalan bagi zkVM praktis yang dapat membuktikan komputasi arbitrer secara incremental.

Istilah Terkait

Referensi

  • Kothapalli, A.; Setty, S.; Tzialla, I. (2021). Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. eprint.iacr.org/2021/370.pdf