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 kurang efisien. Untuk mengatasi masalah ini, STARKs mulai beralih ke penggunaan bidang 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. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan masalah ZK-EVM yang efisien.

Artikel ini akan membahas cara kerja teknologi ini, dengan fokus khusus pada solusi Circle STARKs yang kompatibel dengan bidang Mersenne31.

Pertanyaan Umum tentang Penggunaan Bidang Kecil

Saat membuat bukti berbasis hash, teknik penting adalah memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial pada titik acak. Ini sangat menyederhanakan proses pembuktian.

Namun, melakukan pengambilan sampel acak pada bidang kecil memiliki masalah keamanan. Misalnya, bidang Mersenne31 hanya memiliki sekitar 2 miliar titik sampel yang mungkin, yang dapat dilakukan oleh penyerang yang bertekad.

Ada dua solusi:

1. Melakukan pemeriksaan acak berkali-kali
2. Field yang diperluas

Pemeriksaan berulang kali sederhana dan efektif, tetapi ada masalah efisiensi. Bidang tambahan dapat memberikan lebih banyak pilihan titik pengambilan sampel, sehingga meningkatkan keamanan.

FRI Reguler

Langkah pertama dari protokol FRI adalah mengubah masalah komputasi menjadi persamaan polinomial. Kemudian membuktikan bahwa solusi polinomial yang diajukan memang merupakan polinomial yang valid, dan memiliki derajat maksimum tertentu.

FRI mencapai hal ini dengan secara bertahap menyederhanakan masalah pembuktian polinomial dengan derajat d menjadi masalah pembuktian dengan derajat d/2. Proses ini dapat diulang beberapa kali, setiap kali mengurangi ukuran masalah menjadi setengah.

Setiap langkah FRI mengurangi derajat polinomial dan ukuran kumpulan titik menjadi setengah. Yang pertama adalah kunci dari kerja FRI, sedangkan yang kedua membuat algoritma berjalan sangat cepat.

Circle FRI

Keunggulan Circle STARKs terletak pada kemampuannya untuk menemukan kelompok berukuran p yang memiliki sifat dua-ke-satu yang serupa. Kelompok ini terdiri dari titik-titik yang memenuhi syarat tertentu.

Mulai dari putaran kedua, pemetaan mengalami perubahan:

f_0(2x^2-1) = (F(x) + F(-x))/2

Pemetaan ini akan mengurangi ukuran kumpulan titik setengah setiap kali.

FFT Lingkaran

Grup Circle juga mendukung FFT, cara konstruksinya mirip dengan FRI. Namun objek yang diproses oleh Circle FFT bukanlah polinomial yang ketat, melainkan yang disebut ruang Riemann-Roch.

Sebagai pengembang, Anda hampir bisa mengabaikan hal ini. STARKs hanya memerlukan Anda untuk menyimpan polinomial sebagai himpunan nilai evaluasi. Satu-satunya tempat yang memerlukan FFT adalah untuk melakukan perpanjangan derajat rendah.

Perdagangan

Dalam Circle STARKs, karena tidak ada fungsi linier yang dapat dilalui melalui titik tunggal, diperlukan teknik yang berbeda untuk menggantikan metode pembagian tradisional.

Kami harus mengevaluasi pada dua titik untuk membuktikan, sehingga menambahkan satu titik virtual yang tidak perlu diperhatikan.

Polinomial Hilang

Dalam STARKs Circle, bentuk polinomial yang menghilang adalah:

Z_1(x,y) = y Z_2(x,y) = x Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

Urutan Terbalik

Urutan invers dalam STARKs lingkaran perlu disesuaikan untuk mencerminkan struktur lipatan khususnya. Secara khusus, setiap posisi kecuali posisi terakhir perlu dibalik, dan posisi terakhir akan menentukan apakah posisi lainnya perlu dibalik.

Efisiensi

Circle STARKs sangat efisien. Dibandingkan dengan SNARKs bidang besar, mereka dapat memanfaatkan ruang dalam pelacakan komputasi dengan lebih baik.

Binius lebih baik daripada Circle STARKs dalam beberapa hal, tetapi biayanya adalah konsep yang lebih rumit. Sebaliknya, Circle STARKs relatif sederhana dalam konsep.

Kesimpulan

Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan STARKs konvensional. Meskipun matematika di baliknya sangat kompleks, kompleksitas ini disembunyikan dengan baik.

Menggabungkan teknologi seperti Mersenne31, BabyBear, dan Binius, tampaknya kita semakin mendekati batas efisiensi lapisan dasar STARKs. Arah optimasi di masa depan mungkin termasuk:

1. Memaksimalkan efisiensi fungsi hash dan tanda tangan
2. Konstruksi rekursif untuk meningkatkan paralelisme
3. Optimalkan mesin virtual untuk meningkatkan pengalaman pengembangan