Menjelajahi Circle STARKs

Circle STARKs adalah sistem bukti STARK baru yang memanfaatkan sifat khusus kelompok lingkaran untuk membangun bukti yang efisien. Artikel ini akan membahas cara kerja Circle STARKs dan kelebihannya.

Latar Belakang

Dalam beberapa tahun terakhir, desain protokol STARK cenderung menggunakan bidang matematika yang lebih kecil, seperti Goldilocks, Mersenne31, dan BabyBear. Perubahan ini secara signifikan meningkatkan kecepatan pembuktian, misalnya Starkware dapat membuktikan 620.000 hash Poseidon2 per detik di laptop M3.

Namun, penggunaan bidang kecil juga membawa beberapa tantangan, yaitu bagaimana memastikan keamanan dalam ruang acak yang terbatas. Circle STARKs menyelesaikan masalah ini melalui desain yang cerdik.

Prinsip inti Circle STARKs

Pemikiran inti dari Circle STARKs adalah memanfaatkan sifat pemetaan dua-ke-satu dari kelompok lingkaran. Diberikan sebuah bilangan prima p, kita dapat menemukan sebuah kelompok berukuran p, yang memiliki sifat dua-ke-satu yang serupa. Kelompok ini terdiri dari semua titik yang memenuhi x^2 + y^2 = 1 mod p yaitu (x,y).

Poin-poin ini mengikuti aturan penjumlahan: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Bentuk dua kali lipat adalah: 2(x,y) = (2x^2 - 1, 2xy)

Dengan menggunakan pemetaan ini, kita dapat membangun sistem pembuktian yang mirip dengan FRI, tetapi bekerja di bidang yang lebih kecil.

FFT Lingkaran

Lingkaran grup juga mendukung operasi FFT, tetapi objek yang diproses bukanlah polinomial dalam arti yang ketat, melainkan yang disebut ruang Riemann-Roch. Ini berarti kami menganggap setiap kelipatan dari x^2 + y^2 - 1 sebagai nol.

Ini menyebabkan koefisien yang dihasilkan oleh Circle FFT berbeda dari FFT konvensional, melainkan berdasarkan basis tertentu {1, y, x, xy, 2x^2 - 1, ...}. Namun sebagai pengembang, kita hampir bisa mengabaikan hal ini dan cukup menangani polinomial sebagai kumpulan nilai evaluasi.

Teknik Khusus Circle STARKs

Perdagangan

Karena kelompok lingkaran tidak memiliki fungsi linier yang dapat dilalui oleh satu titik, Circle STARKs menggunakan teknik operasi pembagian yang berbeda. Kami membuktikannya dengan melakukan evaluasi di dua titik, sehingga menambahkan satu titik virtual yang tidak perlu diperhatikan.

polin hilang

Bentuk polinomial hilang dalam STARKs Lingkaran adalah:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Urutan Terbalik

Untuk menyesuaikan struktur lipatan khusus Circle STARKs, kita perlu menyesuaikan urutan bit invers. Metode spesifiknya adalah membalik setiap bit kecuali yang terakhir, dan menggunakan bit terakhir untuk menentukan apakah akan membalik bit lainnya.

Efisiensi Circle STARKs

Circle STARKs bekerja pada bidang bilangan prima 31, lebih efisien dibandingkan STARKs bidang besar. Ini memanfaatkan ruang bidang dengan baik, mengurangi pemborosan ruang kosong. Meskipun solusi seperti Binius lebih unggul dalam beberapa aspek, konsep Circle STARKs lebih sederhana.

Kesimpulan

Circle STARKs menyediakan varian STARK yang sederhana namun efisien bagi para pengembang. Ini dengan baik menyeimbangkan efisiensi dan kemudahan penggunaan, merupakan langkah penting dalam perkembangan teknologi STARK. Di masa depan, optimasi STARK mungkin akan terfokus pada arah berikut:

1. Memaksimalkan efisiensi aritmatika dari fungsi hash dan primitive kriptografi dasar lainnya
2. Meningkatkan paralelisasi melalui konstruksi rekursif
3. Meningkatkan aritmetika mesin virtual untuk mengoptimalkan pengalaman pengembang

Kehadiran Circle STARKs memberikan kami jendela untuk memahami dan mengeksplorasi lebih banyak teknologi FFT khusus, mendorong perkembangan teknologi STARK ke arah yang lebih efisien dan praktis.