Jelajahi Circle STARKs

Dalam beberapa tahun terakhir, tren desain protokol STARKs adalah beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs yang paling awal menggunakan bidang 256-bit, tetapi desain ini memiliki efisiensi yang rendah. Untuk meningkatkan efisiensi, STARKs mulai menggunakan bidang yang lebih kecil, seperti Goldilocks, Mersenne31, dan BabyBear.

Menggunakan field kecil dapat secara signifikan meningkatkan kecepatan pembuktian. Misalnya, Starkware dapat membuktikan 620.000 hash Poseidon2 per detik di laptop M3. Namun, field kecil juga membawa tantangan baru, yaitu bagaimana menjamin keamanan dalam ruang pilihan yang terbatas.

Artikel ini akan membahas Circle STARKs, yaitu sebuah skema baru yang kompatibel dengan bidang Mersenne31. Circle STARKs menyelesaikan masalah keamanan yang dihadapi oleh bidang kecil dengan melakukan operasi pada kelompok titik di lingkaran.

Circle FRI

Gagasan inti dari Circle FRI adalah mendefinisikan sekelompok titik dengan ukuran p di atas lingkaran, yang memiliki sifat pemetaan dua-ke-satu. Titik-titik dalam kelompok memenuhi x^2 + y^2 = 1 (mod p).

Proses pemetaan Circle FRI adalah sebagai berikut:

1. Pertama, kumpulkan semua titik ke sumbu x.
2. Melakukan kombinasi linier acak untuk mendapatkan polinomial satu dimensi P(x)
3. Mulai dari putaran kedua menggunakan pemetaan f_0(2x^2-1) = (F(x) + F(-x))/2

Proses ini mengurangi ukuran kumpulan titik setengah setiap kali, mirip dengan FRI konvensional.

FFT Lingkaran

Circle群 juga mendukung FFT, konstruksinya mirip dengan Circle FRI. Perbedaannya adalah Circle FFT tidak memproses polinomial dalam arti yang ketat, melainkan ruang Riemann-Roch.

Koefisien keluaran Circle FFT spesifik untuk dasar Circle FFT: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, ...}

Sebagai pengembang, Anda dapat mengabaikan rincian matematika ini, cukup simpan polinomial sebagai kumpulan nilai evaluasi.

Detail Teknis Lainnya

• Evaluasi operasi komersial dalam STARKs Lingkaran perlu dilakukan di dua titik.
• Cara konstruksi polinomial yang hilang berbeda
• Menggunakan urutan bit terbalik yang dimodifikasi untuk menyesuaikan struktur lipatan Circle STARKs

Efisiensi

Circle STARKs sangat efisien pada bidang bilangan prima 31.

• Memanfaatkan ruang komputasi secara maksimal
• Cocok untuk logika bisnis dan perhitungan kriptografi
• Mendukung operasi tabel pencarian yang efisien

Jika dibandingkan, solusi Binius sedikit lebih unggul dalam efisiensi, tetapi konsepnya lebih kompleks.

Ringkasan

STARKs Lingkaran tidak lebih kompleks bagi pengembang dibandingkan dengan STARKs konvensional. Ini menawarkan solusi yang elegan untuk STARKs bidang kecil, diharapkan dapat mendorong teknologi STARKs menuju efisiensi yang lebih tinggi.

Arah optimasi STARKs di masa depan mungkin termasuk:

• Mengoptimalkan fungsi hash dan primitive kriptografi dasar
• Meningkatkan paralelisme dengan konstruksi rekursif
• Meningkatkan aritmetika mesin virtual untuk meningkatkan pengalaman pengembang