Menjelajahi Circle STARKs

Dalam beberapa tahun terakhir, desain protokol STARKs cenderung menggunakan bidang yang lebih kecil. Implementasi STARKs yang paling awal menggunakan bidang 256-bit, melakukan operasi modulo pada angka besar, yang kompatibel dengan tanda tangan berbasis kurva elips. Namun, desain ini kurang efisien dan membuang daya komputasi saat memproses angka besar. Untuk mengatasi masalah ini, STARKs mulai menggunakan bidang yang lebih kecil: Goldilocks, Mersenne31, dan BabyBear.

Perubahan ini meningkatkan kecepatan pembuktian. Misalnya, Starkware dapat membuktikan 620.000 nilai hash Poseidon2 per detik di laptop M3. Selama Poseidon2 dipercaya sebagai fungsi hash, masalah pengembangan ZK-EVM yang efisien dapat diatasi. Lalu, bagaimana teknologi ini bekerja? Bagaimana membangun pembuktian di bidang kecil? Artikel ini akan membahas detail ini, dengan fokus khusus pada solusi Circle STARKs.

Pertanyaan Umum tentang Menggunakan Bidang Kecil

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

Misalnya, anggap kita ingin membuktikan bahwa polinomial A 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, kita dapat menyimpulkan A(r) = c, dan membuktikan Q = (A - c)/(X - r) adalah polinomial.

Untuk mencegah serangan, perlu memilih r setelah penyerang memberikan A. Dalam bidang 256-bit sangat sederhana: cukup pilih angka acak 256-bit. Tetapi dalam bidang kecil, nilai r yang dapat dipilih hanya sekitar 2 miliar, meskipun beban kerja penyerang sangat besar, mereka masih mungkin mencoba semua kemungkinan.

Ada dua solusi:

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

Pemeriksaan berkali-kali sederhana dan efektif, tetapi ada masalah efisiensi. Bidang perluasan mirip dengan bilangan jamak, tetapi berdasarkan bidang terbatas. Memperkenalkan nilai baru α yang memenuhi hubungan tertentu, seperti α^2=nilai tertentu. Ini menciptakan struktur matematika baru yang memungkinkan operasi yang lebih kompleks dilakukan pada bidang terbatas. Bidang perluasan hanya digunakan saat diperlukan kombinasi linier acak, sebagian besar operasi masih dilakukan pada bidang dasar.

FRI Reguler

Langkah pertama dalam membangun SNARK atau STARK adalah mengubah masalah komputasi menjadi persamaan polinomial P(X,Y,Z)=0. Solusi harus membuktikan bahwa nilai yang diajukan adalah polinomial yang wajar, dan derajatnya terbatas. Ini dicapai melalui penerapan kombinasi linier acak secara bertahap:

1. Misalkan ada nilai evaluasi dari polinomial A, perlu membuktikan derajat < 2^20
2. Pertimbangkan B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D adalah kombinasi linier acak dari B dan C: D=B+rC

B mengisolasi koefisien genap A, C mengisolasi koefisien ganjil. Diberikan B dan C, A dapat dipulihkan: A(x) = B(x^2) + xC(x^2). Jika derajat A < 2^20, derajat B dan C masing-masing adalah derajat A dan derajat A - 1. D sebagai kombinasi acak, derajat harus sama dengan derajat A.

FRI menyederhanakan verifikasi dengan mengurangi bukti polinomial derajat d menjadi bukti derajat d/2. Proses ini dapat diulang beberapa kali, setiap kali menyederhanakan masalah setengah. Jika output pada suatu tahap tidak sesuai dengan derajat yang diharapkan, maka putaran pemeriksaan tersebut akan gagal.

FRI setiap langkah mengurangi derajat polinomial dan ukuran kumpulan titik menjadi setengah. Yang pertama adalah kunci dari kerja FRI, yang kedua membuat algoritma berjalan sangat cepat: total biaya perhitungan adalah O(N) alih-alih O(N*log(N)).

Untuk mencapai pengurangan domain secara bertahap, gunakan pemetaan dua ke satu. Pemetaan ini memungkinkan ukuran dataset berkurang setengah dan dapat diulang. Dimulai dari subkelompok perkalian, setiap elemen x juga memiliki kelipatan 2x dalam himpunan. Mengkuadratkan himpunan S, himpunan baru S^2 mempertahankan atribut yang sama. Ini memungkinkan pengurangan ukuran dataset secara berkelanjutan hingga hanya tersisa satu nilai.

Modulus BabyBear memungkinkan subgrup perkalian maksimumnya mencakup semua nilai non-nol, dengan ukuran 2^k-1. Ini sangat cocok untuk teknologi di atas, yang dapat secara efektif mengurangi derajat polinomial melalui pemetaan berulang. Ukuran subgrup perkalian Mersenne31 adalah 2^31-1, yang hanya dapat dibagi 2 sekali, setelah itu teknik tersebut tidak dapat digunakan.

Domain Mersenne31 sangat cocok untuk perhitungan CPU/GPU 32-bit. Karakteristik modulusnya ( seperti 2^31-1) memungkinkan banyak perhitungan menggunakan operasi bit yang efisien: hasil yang melebihi modulus dapat dikurangi dengan pergeseran. Perkalian dapat diproses secara efisien menggunakan instruksi CPU tertentu. Operasi aritmatika Mersenne31 sekitar 1,3 kali lebih cepat dibandingkan BabyBear. Jika FRI dapat diimplementasikan di Mersenne31, akan secara signifikan meningkatkan efisiensi.

Circle FRI

Keunggulan Circle STARKs terletak pada, dengan diberikan bilangan prima p, dapat ditemukan kelompok berukuran p, yang memiliki sifat serupa 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.

Titik-titik ini mengikuti hukum penjumlahan: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Bentuk ganda: 2*(x,y) = (2x^2 - 1, 2xy)

Kami fokus pada titik-titik pada posisi ganjil di lingkaran. Pertama, kita akan mengonsolidasikan semua titik menjadi satu garis lurus: f0(x) = (F(x,y) + F(x,-y))/2

Kemudian lakukan kombinasi linier acak, menghasilkan 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 kumpulan setengah setiap saat. Setiap x mewakili dua titik: (x,y) dan (x,-y). (x → 2x^2 - 1) adalah hukum penggandaan titik. Kami mengubah koordinat x dari dua titik yang berlawanan di lingkaran menjadi koordinat x dari titik setelah penggandaan.

FFT Lingkaran

Circle group juga mendukung FFT, cara konstruksinya mirip dengan FRI. Perbedaan kunci adalah Circle FFT tidak memproses polinomial yang ketat, tetapi ruang Riemann-Roch: polinomial modulo lingkaran (x^2 + y^2 - 1 = 0).

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

Pengembang hampir dapat mengabaikan hal ini. STARKs hanya perlu menyimpan polinomial sebagai kumpulan nilai evaluasi. FFT hanya digunakan untuk perpanjangan derajat rendah: diberikan N nilai, menghasilkan k*N nilai pada polinomial yang sama.

Operasi Bisnis

Operasi umum STARK adalah melakukan operasi pembagian pada titik tertentu. Misalnya, membuktikan P(x)=y dapat dilakukan melalui langkah-langkah berikut:

1. Hitung rasio: Q = (P - y)/(X - x)
2. Buktikan Q adalah polinomial dan bukan pecahan

Dalam grup lingkaran STARK, karena tidak ada fungsi linier melalui titik tunggal, diperlukan keterampilan yang berbeda. Fungsi tangen dapat dibangun, tetapi memiliki multiplicity 2 pada titik tersebut. Oleh karena itu, perlu dievaluasi di dua titik untuk membuktikannya.

Jika P sama dengan y1 di x1, dan sama dengan y2 di x2, kita memilih fungsi interpolasi L agar sama di kedua titik ini. Kemudian buktikan bahwa P-L sama dengan nol di kedua titik ini, dengan membagi L dengan L untuk membuktikan bahwa hasil bagi Q adalah polinom.

Polinomial Hilang

Polinomial yang coba dibuktikan dalam STARK biasanya berbentuk C(P(x), P(next(x))) = Z(x) · H(x), Z(x) selalu sama dengan nol di domain evaluasi asli.

Dalam STARK berbentuk lingkaran, fungsi yang sesuai adalah: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Urutan Terbalik

Evaluasi polinomial dalam STARKs biasanya diatur dalam urutan bit terbalik. Dalam circle STARKs, struktur lipat sedikit berbeda:

• Langkah Pertama:(x,y) dengan (x,-y) dipasangkan
• Langkah kedua: x dipasangkan dengan -x
• Langkah selanjutnya: mencocokkan p dan q, sehingga Q^i(p) = -Q^i(q)

Untuk menyesuaikan urutan terbalik, perlu membalik setiap posisi kecuali posisi terakhir, menggunakan posisi terakhir untuk menentukan apakah posisi lainnya dibalik.

Efisiensi

Circle STARKs sangat efisien. Perhitungan biasanya melibatkan:

1. Aritmatika asli: digunakan untuk logika bisnis
2. Aritmetika Asli: digunakan untuk kriptografi ( seperti hash Poseidon )
3. Mencari Parameter: Metode Perhitungan Umum yang Efisien

Kunci efisiensi terletak pada pemanfaatan ruang pelacakan komputer secara maksimal. Di sini ukuran bidang adalah 2^31, sehingga pemborosan ruang tidak besar. Hash seperti Poseidon memanfaatkan setiap bit dari setiap angka dalam bidang mana pun.

Binius mencapai pengemasan bit yang lebih efisien dengan menggabungkan berbagai ukuran bidang, tetapi biayanya adalah konsep yang lebih kompleks. Circle STARKs secara konseptual relatif sederhana.

Kesimpulan

Circle STARKs tidak lebih rumit bagi pengembang dibandingkan dengan STARKs. Perbedaan utama dalam implementasinya dengan FRI konvensional terletak pada tiga masalah yang disebutkan di atas. Meskipun matematika di baliknya kompleks, kompleksitas ini disembunyikan dengan baik.

Memahami Circle FRI dan FFT dapat menjadi jalan untuk memahami FFT khusus lainnya, seperti FFT bidang biner dan FFT kurva elips.

Dengan menggabungkan teknologi seperti Mersenne31, BabyBear, dan Binius, kami semakin mendekati batas efisiensi lapisan dasar STARKs. Optimasi di masa depan mungkin akan fokus pada:

1. Memaksimalkan efisiensi aritmatika dari fungsi hash dan tanda tangan.
2. Membangun rekursif untuk mengaktifkan lebih banyak paralelisasi
3. Mesin virtual aritmetika untuk meningkatkan pengalaman pengembang