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

Perubahan ini meningkatkan kecepatan pembuktian. Misalnya, Starkware dapat membuktikan 620.000 nilai hash Poseidon2 per detik pada laptop M3. Selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan tantangan dalam mengembangkan ZK-EVM yang efisien. Lalu, bagaimana teknologi ini bekerja? Bagaimana pembuktian ini dibangun di atas bidang yang lebih kecil? Artikel ini akan membahas detail tersebut, dengan fokus khusus pada skema Circle STARKs.

Masalah Umum Menggunakan Bidang Matematika yang Lebih Kecil

Dalam membuat bukti berbasis hash, trik penting adalah membuktikan hasil evaluasi polinomial di titik acak untuk secara tidak langsung memverifikasi sifat polinomial tersebut. Ini dapat sangat menyederhanakan proses pembuktian.

Misalnya, anggaplah diperlukan untuk menghasilkan komitmen polinomial A, yang harus 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 untuk mendapatkan A(r) = c, membuktikan Q = (A - c)/(X - r) adalah sebuah polinomial.

Untuk mencegah serangan, perlu memilih r setelah penyerang memberikan A. Dalam protokol berbasis kurva elips, dapat memilih angka acak 256 bit. Namun, dalam STARKs dengan bidang lebih kecil, hanya ada sekitar 2 miliar nilai r yang dapat dipilih, penyerang mungkin dapat membobolnya melalui pencarian brute force.

Ada dua solusi:

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

Pemeriksaan acak yang dilakukan berkali-kali sederhana dan efektif, tetapi ada masalah efisiensi. Domain perluasan mirip dengan bilangan kompleks, tetapi berbasis pada domain terbatas. Memperkenalkan nilai baru α, menyatakan α^2=nilai tertentu. Dengan cara ini, operasi yang lebih kompleks dapat dilakukan di domain terbatas. Domain perluasan hanya digunakan dalam skenario seperti protokol FRI, sebagian besar operasi matematika masih dilakukan di bidang dasar.

FRI Reguler

Saat membangun SNARK atau STARK, langkah pertama adalah aritmetisasi, mengubah masalah komputasi menjadi persamaan polinomial. Untuk membuktikan bahwa ada solusi, perlu membuktikan bahwa nilai yang diajukan adalah polinomial yang valid dan memiliki derajat maksimum. Untuk ini, digunakan teknik kombinasi linear acak yang diterapkan 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

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

FRI menyederhanakan proses verifikasi dengan mengubah masalah pembuktian polinomial derajat d menjadi masalah pembuktian derajat d/2. Proses ini dapat diulang berkali-kali, setiap kali menyederhanakan masalah setengah.

Untuk mencapai pengurangan bertahap dari domain, gunakan pemetaan dua-ke-satu. Pemetaan ini memungkinkan ukuran dataset berkurang setengah, dan bersifat dapat diulang. Dimulai dari subkelompok perkalian, lakukan operasi kuadrat pada himpunan S, himpunan baru S^2 mempertahankan sifat yang sama. Ini memungkinkan pengurangan ukuran dataset secara berkelanjutan, sampai akhirnya hanya tersisa satu nilai.

Modulus BabyBear membuat grup perkalian maksimumnya mencakup semua nilai non-zero, dengan ukuran grup sebesar 2k-1. Grup dengan ukuran 2^k dapat dipilih, kemudian metode FRI diterapkan untuk secara bertahap mengurangi derajat polinomial menjadi 15. Modulus Mersenne31 membuat ukuran grup perkalian sebesar 2^31-1, hanya dapat dibagi dengan 2 sekali, setelah itu teknik di atas tidak dapat digunakan.

Domain Mersenne31 cocok untuk perhitungan CPU/GPU 32-bit. Karakteristik modulusnya memungkinkan banyak operasi diselesaikan dengan operasi bit yang efisien. Di domain Mersenne31, operasi aritmatika sekitar 1,3 kali lebih cepat dibandingkan dengan domain BabyBear. Jika FRI dapat diimplementasikan di domain Mersenne31, akan secara signifikan meningkatkan efisiensi komputasi.

Circle FRI

Keunikan STARKs Lingkaran terletak pada fakta bahwa, untuk bilangan prima p, dapat ditemukan kelompok berukuran p yang memiliki sifat mirip satu terhadap dua. 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 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. Pertama, kami mengkonsolidasikan semua titik ke dalam satu garis lurus: f0(x) = (F(x,y) + F(x,-y))/2

Kemudian lakukan kombinasi linier acak, dapatkan polinomial satu dimensi P(x).

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

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

FFT Lingkaran

Group Circle juga mendukung FFT, cara konstruksinya mirip dengan FRI. Objek yang diproses oleh Circle FFT adalah ruang Riemann-Roch: polinomial modulo lingkaran (x^2 + y^2 - 1 = 0).

Koefisien keluaran 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 digunakan untuk pengembangan rendah: diberikan N nilai, menghasilkan k*N nilai pada polinomial yang sama.

Operasi Bisnis

Dalam protokol STARK, operasi umum adalah melakukan perhitungan pada titik tertentu. Misalnya, membuktikan P(x)=y:

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

Dalam grup lingkaran STARK, karena tidak ada fungsi linier pada titik tunggal, diperlukan teknik berbeda untuk menggantikan metode operasi komersial tradisional. Dengan membuktikan melalui evaluasi di dua titik, menambahkan satu titik virtual yang tidak perlu diperhatikan.

Jika polinomial P sama dengan y1 di x1 dan sama dengan y2 di x2, pilih fungsi interpolasi L yang sama dengan y1 di x1 dan sama dengan y2 di x2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Kemudian buktikan bahwa P - L sama dengan nol di kedua titik ini, dengan membagi L dengan L untuk membuktikan bahwa hasil bagi Q adalah polinomial.

Polinomial Hilang

Dalam STARK, persamaan polinomial biasanya berbentuk C(P(x), P(next(x))) = Z(x) · H(x), Z(x) adalah nol di seluruh domain evaluasi.

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

Polinomial yang menghilang dapat diturunkan dari fungsi lipat: STARK biasa menggunakan kembali x → x^2, STARK melingkar menggunakan kembali x → 2x^2 - 1.

Urutan Terbalik

Dalam STARKs, evaluasi polinomial biasanya diatur dalam urutan bit terbalik. Misalnya, saat n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Pengurutan ini membuat nilai grup awal dalam proses evaluasi FRI berdekatan dalam urutan, menghemat ruang.

Dalam circle STARKs, struktur lipatan sedikit berbeda. Untuk menyesuaikan urutan bit yang terbalik agar mencerminkan struktur ini, perlu membalik setiap bit kecuali bit terakhir, dan menggunakan bit terakhir untuk menentukan apakah bit lainnya harus dibalik.

Urutan inversi lipat dengan ukuran 16: {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: digunakan untuk logika bisnis
2. Aritmetika Asli: Digunakan untuk Kriptografi
3. Mencari Parameter: Metode Perhitungan Umum yang Efisien

Kunci efisiensi terletak pada pemanfaatan ruang pelacakan komputasi secara maksimal. Ukuran bidang Circle STARKs adalah 2^31, yang mengurangi pemborosan ruang.

Binius lebih baik daripada Circle STARKs, memungkinkan penggabungan bidang ukuran yang berbeda, mencapai pengemasan bit yang lebih efisien. Namun, biayanya adalah konsep yang lebih kompleks, konsep Circle STARKs relatif lebih sederhana.

Kesimpulan

Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan STARKs. Memahami Circle FRI dan Circle FFTs dapat menjadi cara untuk memahami FFTs khusus lainnya.

Dengan menggabungkan teknologi seperti Mersenne31, BabyBear, dan Binius, kita mendekati batas efisiensi lapisan dasar STARKs. Arah optimasi STARK di masa depan mungkin termasuk:

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