Menjelajahi Circle STARKs

Dalam beberapa tahun terakhir, tren desain protokol STARKs telah beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs yang paling awal menggunakan bidang 256-bit, tetapi desain ini kurang efisien. 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. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan tantangan ZK-EVM yang efisien.

Namun, penggunaan bidang kecil juga menghadirkan tantangan baru. Dalam bidang 256-bit, dapat memilih angka 256-bit acak sebagai parameter verifikasi. Sedangkan dalam bidang kecil 20-30 bit, nilai yang dapat dipilih terlalu sedikit, sehingga mudah untuk dieksploitasi oleh penyerang.

Untuk menyelesaikan masalah ini, ada dua solusi:

1. Melakukan pemeriksaan acak beberapa kali
2. Bidang Ekstensi

Pemeriksaan acak berkali-kali sederhana dan efektif, tetapi akan mengurangi efisiensi. Field ekstensi mirip dengan plural, memperkenalkan struktur matematika baru untuk menambah nilai yang dapat dipilih.

Circle STARKs telah menggunakan skema kolom yang cerdik. Ini membangun kelompok dengan sifat dua-ke-satu pada kelompok bilangan prima p, dengan ukuran p. Titik-titik dalam kelompok ini mengikuti aturan penjumlahan khusus, mirip dengan perkalian bilangan kompleks.

Circle STARKs menggunakan struktur grup khusus ini untuk mencapai algoritma FRI dan FFT yang efisien. Ini dapat beroperasi di bidang Mersenne31, memanfaatkan sepenuhnya keuntungan dari bilangan prima 31-bit.

Dibandingkan dengan STARKs biasa, Circle STARKs berbeda dalam hal-hal berikut:

• Menggunakan metode operasi bisnis khusus
• Menggunakan polinomial hilang yang berbeda
• Menyesuaikan urutan terbalik

Secara keseluruhan, Circle STARKs mempertahankan kesederhanaan konsep, sambil memberikan efisiensi yang luar biasa. Ini adalah solusi optimasi STARK yang menjanjikan, layak untuk diteliti dan diterapkan lebih lanjut.

Optimasi STARK di masa depan mungkin akan berfokus pada:

1. Mengoptimalkan fungsi hash dan primitive kriptografi dasar
2. Meningkatkan paralelisme dengan membangun secara rekursif
3. Meningkatkan aritmetika mesin virtual untuk mengoptimalkan pengalaman pengembangan