Crypto Gloss

STARKs: Komputasi yang Dapat Diverifikasi secara Skalabel, Transparan, dan Aman Pasca-Kuantum

Penulis Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael
Tahun 2018
Proyek StarkWare
Lisensi Creative Commons BY 4.0
Sumber Resmi eprint.iacr.org/2018/046
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.

“Scalable, transparent, and post-quantum secure computational integrity” adalah paper IACR Cryptology ePrint 2018 (dipresentasikan di CRYPTO 2019) oleh Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, dan Michael Riabzev yang memperkenalkan STARK — Scalable Transparent ARguments of Knowledge. Ini adalah fondasi kriptografis untuk produk StarkWare: StarkEx (mesin proof khusus aplikasi) dan Starknet (ZK-Rollup tujuan umum untuk Ethereum). Dibandingkan SNARK, STARK menawarkan: tidak ada trusted setup, post-quantum security, dan waktu verifikasi polilogatimik — dengan trade-off ukuran proof yang lebih besar.

Publikasi dan Konteks

Pada 2018, zk-SNARK (digunakan oleh Zcash dan kemudian Tornado Cash) adalah sistem zero-knowledge proof yang dominan, tetapi memerlukan trusted setup ceremony: komputasi multi-pihak yang menghasilkan parameter CRS (Common Reference String). Jika upacara dikompromikan, penyerang dapat memalsukan proof. STARK menghilangkan ini dengan hanya menggunakan fungsi hash sebagai asumsi kriptografisnya.

Tiga Properti Utama STARK

  • Transparent: Tidak ada trusted setup. Random coin publik; dapat diverifikasi oleh siapa pun. Tidak ada “toxic waste” dari upacara setup.
  • Post-quantum secure: Mengasumsikan keamanan fungsi hash (SHA-3, Poseidon). Aman terhadap komputer kuantum — tidak bergantung pada keamanan discrete log atau masalah pairing yang dapat dipatahkan oleh kuantum.
  • Scalable: Waktu verifikasi O(log² N) untuk komputasi berukuran N — polilogatimik. Prover: O(N log N). Ini berarti semakin besar komputasi, semakin besar keuntungan relatif dari verifikasi STARK vs. mengulang komputasi.

Cara Kerja STARK

Ide tingkat tinggi:

  1. Prover ingin meyakinkan verifier bahwa mereka menghitung F(x) = y dengan benar, di mana F adalah komputasi kompleks
  2. Prover mengkodekan trace eksekusi (setiap langkah perantara) sebagai polinomial atas finite field
  3. Prover menggunakan FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) — protokol berbasis hash untuk membuktikan bahwa polinomial trace berderajat rendah (artinya, sesuai dengan trace eksekusi yang valid)
  4. Verifier memeriksa proof FRI dengan mengkueri titik-titik acak dan memverifikasi hash konsistensi — tidak diperlukan pairing kriptografis

FRI: Inti Efisiensi STARK

FRI (Fast RS IOPP) adalah inti efisiensi STARK. Ini mereduksi masalah pemeriksaan evaluasi polinomial menjadi serangkaian operasi folding berbasis hash:

  • Waktu prover: O(N log N) di mana N adalah panjang trace
  • Waktu verifier: O(log² N) — polilogatimik
  • Ukuran proof: O(log² N) elemen field

Trade-off: Ukuran Proof Lebih Besar

Kelemahan STARK: ukuran proof jauh lebih besar dari SNARK. SNARK proof ~200–800 byte; STARK proof ~40–200 KB. Ini mahal untuk verifikasi on-chain. Starknet mengatasi ini dengan menggunakan STARK untuk batch besar transaksi (di mana biaya per transaksi menjadi dapat diterima) dan dengan proof SNARK rekursif (SHARP: SNARK-wrapped STARK) untuk mengurangi ukuran proof akhir yang diposting ke Ethereum.

Starknet dan StarkEx

  • StarkEx: Mesin scaling khusus aplikasi berbasis STARK (digunakan oleh dYdX v3, Immutable X, Sorare)
  • Starknet: ZK-Rollup tujuan umum; smart contract ditulis dalam Cairo; setiap batch transaksi dibuktikan dengan STARK

Istilah Terkait

Referensi

  • Ben-Sasson, E. et al. (2018). Scalable, transparent, and post-quantum secure computational integrity. CRYPTO 2019. eprint.iacr.org/2018/046