Menyelami 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, yang membuat protokol ini kompatibel dengan tanda tangan berbasis kurva eliptik. Namun, desain ini kurang efisien, memproses angka besar akan membuang banyak daya komputasi. Untuk mengatasi masalah ini, STARKs mulai beralih ke penggunaan bidang yang lebih kecil: pertama Goldilocks, lalu Mersenne31 dan BabyBear.

Perubahan ini secara signifikan meningkatkan kecepatan pembuktian. Misalnya, Starkware dapat membuktikan 620.000 nilai hash Poseidon2 per detik pada laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat memecahkan tantangan ZK-EVM yang efisien. Lalu, bagaimana teknologi ini bekerja? Bagaimana cara membangun pembuktian di bidang kecil? Artikel ini akan membahas detail ini, dengan fokus khusus pada solusi Circle STARKs.

Pertanyaan Umum tentang Penggunaan Bidang Kecil

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

Misalnya, anggaplah perlu menghasilkan sebuah 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. Kemudian, mundur A(r) = c, buktikan Q = (A - c)/(X - r) adalah sebuah polinomial.

Untuk mencegah serangan, perlu memilih r setelah penyerang memberikan A. Dalam protokol bidang besar, dapat memilih angka acak 256-bit sebagai r. Namun dalam STARKs bidang kecil, hanya sekitar 2 miliar nilai r yang dapat dipilih, penyerang dapat mencoba semua kemungkinan.

Masalah ini memiliki dua solusi:

1. Melakukan beberapa pemeriksaan acak
2. Field Ekstensi

Pemeriksaan acak yang sederhana dan efektif dilakukan berkali-kali, tetapi terdapat masalah efisiensi. Bidang tambahan mirip dengan bilangan kompleks, tetapi berdasarkan bidang terbatas. Memperkenalkan nilai baru α yang memenuhi α^2 = suatu nilai, menciptakan struktur matematika baru. Ini memungkinkan kita memiliki lebih banyak pilihan nilai, meningkatkan keamanan.

Regular FRI

Langkah pertama dari protokol FRI biasanya adalah aritmetisasi, mengubah masalah komputasi menjadi persamaan P(X,Y,Z)=0, di mana P adalah polinomial, X, Y, Z adalah parameter. Menyelesaikan persamaan berarti menyelesaikan masalah asli.

Untuk membuktikan kebenaran solusi, perlu dibuktikan bahwa nilai yang diajukan adalah polinomial yang wajar dan memiliki derajat maksimum. Gunakan teknik kombinasi linier acak:

• Misalkan ada nilai evaluasi dari polinomial A, perlu dibuktikan bahwa derajatnya < 2^20
• Pertimbangkan B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D adalah kombinasi linier acak dari B dan C: D = B + rC

Pada dasarnya, B mengisolasi koefisien genap, dan C mengisolasi koefisien ganjil. B dan C dapat memulihkan A. Jika derajat A < 2^20, derajat B dan C masing-masing adalah derajat A dan derajat A - 1. D sebagai kombinasi acak, derajatnya harus sama dengan derajat A.

FRI mengulangi proses penyederhanaan ini, setiap kali menyederhanakan masalah menjadi setengah. Desain ini secara efektif mendeteksi input yang tidak memenuhi syarat.

Circle FRI

Inilah kecerdikan Circle STARKs. Diberikan bilangan prima p, dapat ditemukan kelompok berukuran p, dengan sifat serupa dua lawan satu. Kelompok ini terdiri dari kumpulan titik yang memenuhi kondisi tertentu, seperti himpunan titik di mana x^2 mod p sama dengan nilai tertentu.

Poin-poin ini mengikuti aturan penjumlahan: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Bentuk ganda adalah: 2 * (x,y) = (2x^2 - 1, 2xy)

Kami fokus pada titik-titik di posisi ganjil di lingkaran, mengumpulkan semua titik ke dalam satu garis lurus: f0(x) = (F(x,y) + F(x,-y))/2

Kemudian lakukan kombinasi linier acak untuk mendapatkan polinomial satu dimensi P(x).

Mulai dari putaran kedua, pemetaan berubah menjadi: f0(2x^2-1) = (F(x) + F(-x))/2

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

FFT Lingkaran

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

Sebagai pengembang, Anda dapat mengabaikan hal ini. STARKs hanya perlu menyimpan polinomial sebagai kumpulan nilai evaluasi. FFT terutama digunakan untuk ekspansi tingkat rendah: diberikan N nilai, menghasilkan k*N nilai pada polinomial yang sama.

Pembagian

Dalam Circle STARKs, karena tidak adanya fungsi linier titik tunggal, teknik berbeda harus digunakan untuk menggantikan operasi komutatif tradisional. Dengan membuktikan pada dua evaluasi, tambahkan satu titik virtual.

Jika polinomial P sama dengan y1 pada x1 dan sama dengan y2 pada x2, pilih fungsi interpolasi L yang sama di kedua titik ini. Kemudian buktikan bahwa P-L sama dengan nol di kedua titik, dengan membagi L untuk mendapatkan hasil bagi Q yang merupakan polinomial.

Polinomial yang lenyap

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

Ini dapat diturunkan dari fungsi lipat: menggunakan kembali x → 2x^2 - 1.

Urutan bit terbalik

Urutan bit terbalik dalam Circle STARKs perlu disesuaikan: Balik semua bit kecuali bit terakhir, gunakan bit terakhir untuk menentukan apakah akan membalik bit lainnya.

Urutan terbalik lipat ukuran 16 adalah: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Efisiensi

Circle STARKs sangat efisien. Perhitungan biasanya melibatkan:

1. Aritmatika asli dari logika bisnis
2. Aritmetika asli kriptografi
3. Mencari parameter

Kunci efisiensi terletak pada memanfaatkan ruang pelacakan komputasi secara maksimal. Bidang angka prima 31-bit mengurangi pemborosan. Binius mencampur bidang ukuran berbeda dengan efisiensi yang lebih tinggi, tetapi konsepnya lebih kompleks.

Kesimpulan

Circle STARKs tidaklah rumit bagi pengembang. Memahami matematika di baliknya memerlukan waktu, tetapi kompleksitasnya sangat tersembunyi dengan baik. Ini juga merupakan cara untuk memahami FFT khusus lainnya.

Saat ini efisiensi lapisan dasar STARKs mendekati batas maksimum. Arah optimasi di masa depan mungkin termasuk:

• Memaksimalkan efisiensi fungsi hash dan primitf kriptografi dasar lainnya
• Konstruksi rekursif untuk meningkatkan paralelisme
• Mesin virtual aritmetika untuk meningkatkan pengalaman pengembangan