Menjelajahi Circle STARKs

Dalam beberapa tahun terakhir, tren desain protokol STARKs beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs awal menggunakan bidang 256-bit, yang kompatibel dengan tanda tangan kurva elips, tetapi kurang efisien. Untuk meningkatkan efisiensi, STARKs mulai menggunakan 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 Poseidon2 dipercaya sebagai fungsi hash, tantangan untuk ZK-EVM yang efisien dapat diselesaikan. Artikel ini akan membahas cara kerja teknologi ini, dengan fokus khusus pada solusi Circle STARKs.

Pertanyaan Umum tentang Penggunaan Bidang Kecil

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

Misalnya, sistem bukti mungkin meminta generasi komitmen polinomial A, yang memenuhi A^3(x) + x - A(ωx) = x^N. Protokol dapat meminta pemilihan koordinat acak r dan membuktikan A(r) + r - A(ωr) = r^N.

Untuk mencegah serangan, perlu memilih r setelah penyerang memberikan A. Dalam bidang 256-bit ini sangat mudah, tetapi dalam bidang kecil hanya ada sekitar 2 miliar pilihan r, penyerang mungkin dapat membobol.

Ada dua solusi:

1. Melakukan pemeriksaan acak berkali-kali
2. Field Ekstensi

Pemeriksaan berkali-kali sederhana dan efektif, tetapi mungkin perlu menambah jumlah putaran untuk meningkatkan keamanan. Domain yang diperluas mirip dengan bilangan kompleks, tetapi berdasarkan domain terbatas. Dengan memperkenalkan nilai baru α, menciptakan struktur matematis yang lebih kompleks, memberikan lebih banyak pilihan.

FRI Reguler

Langkah pertama dari protokol FRI adalah mengubah masalah komputasi menjadi persamaan polinomial P(X,Y,Z)=0. Kemudian membuktikan bahwa nilai yang diajukan adalah polinomial yang masuk akal dan memiliki derajat yang terbatas.

FRI menyederhanakan verifikasi dengan mengubah masalah membuktikan derajat polinomial menjadi d menjadi masalah membuktikan derajat d/2. Proses ini dapat diulang beberapa kali, dengan setiap kali menyederhanakan masalah setengah.

Circle FRI

Kehebatan STARKs Lingkaran terletak pada fakta bahwa, untuk bilangan prima p, dapat ditemukan kelompok berukuran p yang memiliki sifat mirip dengan dua-ke-satu. Kelompok ini terdiri dari titik-titik yang memenuhi kondisi tertentu, seperti himpunan titik di mana x^2 mod p sama dengan nilai tertentu.

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

Bentuk ganda adalah: 2*(x,y) = (2x^2 - 1, 2xy)

Pemetaan Circle FRI berubah mulai dari putaran kedua: f0(2x^2-1) = (F(x) + F(-x))/2

Pemetaan ini mengurangi ukuran himpunan menjadi setengah setiap kali, x mewakili dua titik: (x,y) dan (x,-y). (x → 2x^2 - 1) adalah hukum penggandaan titik.

FFT Lingkaran

Circle group juga mendukung FFT, cara konstruksinya mirip dengan FRI. Namun, objek yang diproses oleh Circle FFT adalah ruang Riemann-Roch, bukan polinomial yang ketat.

Koefisien FFT Lingkaran adalah basis tertentu: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, ...}

Pengembang hampir dapat mengabaikan ini, cukup simpan polinomial sebagai himpunan nilai evaluasi. FFT terutama digunakan untuk ekstensi tingkat rendah.

Pembagian

Dalam STARK grup circle, karena tidak ada fungsi linier titik tunggal, perlu menggunakan teknik berbeda untuk menggantikan operasi komutatif tradisional. Biasanya perlu dievaluasi di dua titik untuk membuktikan, menambahkan satu titik virtual.

Polinom yang menghilang

Polinomial hilang dalam Circle STARK adalah: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Balik urutan bit

Dalam STARKs Lingkaran, urutan bit terbalik perlu disesuaikan untuk mencerminkan struktur lipatan, yaitu membalik setiap bit kecuali bit terakhir, menggunakan bit terakhir untuk menentukan apakah bit lainnya dibalik.

Efisiensi

Circle STARKs sangat efisien, perhitungan biasanya melibatkan:

1. Aritmatika asli dari logika bisnis
2. Aritmetika asli kriptografi ( seperti hash Poseidon )
3. Temukan parameter

Ukuran bidang 2^31 mengurangi pemborosan ruang. Binius lebih unggul dalam ukuran bidang campuran, tetapi konsepnya lebih kompleks.

Kesimpulan

Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan STARKs. Memahami matematikanya memerlukan waktu, tetapi kompleksitasnya disembunyikan dengan baik.

Dengan menggabungkan teknologi Mersenne31, BabyBear, dan bidang biner, efisiensi lapisan dasar STARKs mendekati batas maksimum. Arah optimasi masa depan mungkin termasuk:

• Memaksimalkan efisiensi aritmatika dari fungsi hash dan sejenisnya
• Konstruksi rekursif untuk meningkatkan paralelisasi
• Mesin virtual aritmetik untuk meningkatkan pengalaman pengembang