Menyelami Circle STARKs

Dalam beberapa tahun terakhir, tren desain protokol STARKs telah beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs yang paling awal menggunakan bidang 256-bit, tetapi desain ini kurang efisien. Untuk meningkatkan efisiensi, STARKs mulai menggunakan bidang yang lebih kecil, seperti Goldilocks, Mersenne31, dan BabyBear.

Menggunakan bidang kecil dapat 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 tantangan ZK-EVM yang efisien.

Namun, penggunaan bidang kecil juga membawa beberapa tantangan, yaitu bagaimana menjamin keamanan dengan ukuran bidang yang terbatas. Solusi Circle STARKs menawarkan solusi inovatif yang memanfaatkan sifat khusus dari kelompok lingkaran untuk membangun sistem pembuktian yang efisien dan aman.

Artikel ini akan membahas secara mendalam prinsip dan rincian implementasi Circle STARKs, termasuk:

• Tantangan utama yang dihadapi oleh STARKs kecil
• Prinsip dasar Circle FRI
• Implementasi FFT Lingkaran
• Operasi bisnis dan polinomial yang menghilang dalam STARKs Lingkaran
• Penyesuaian urutan terbalik
• Analisis efisiensi STARKs

Melalui diskusi tentang rincian teknis ini, kita dapat lebih memahami inovasi Circle STARKs, serta kontribusinya yang penting dalam meningkatkan efisiensi STARKs.

Tantangan Menggunakan Bidang Kecil

Dalam protokol berbasis kurva elips, kita dapat memilih angka acak 256-bit sebagai parameter verifikasi. Namun, dalam STARKs dengan field kecil, rentang parameter yang dapat dipilih sangat terbatas, sehingga mudah untuk dieksploitasi oleh penyerang.

Ada dua solusi:

1. Lakukan pemeriksaan acak beberapa kali: Verifikasi ulang di beberapa koordinat acak. Metode ini sederhana dan efektif, tetapi akan mengurangi efisiensi.

2. Kolom Ekstensi: Memperkenalkan struktur matematika baru untuk memperluas rentang nilai yang dapat dipilih. Misalnya, pada bidang Mersenne31, kita dapat mendefinisikan α sehingga α^2 = nilai tertentu, sehingga membangun bidang yang lebih besar.

Bidang ekstensi terutama digunakan dalam skenario seperti protokol FRI yang memerlukan kombinasi linier acak. Sebagian besar perhitungan masih dilakukan pada bidang dasar, mempertahankan efisiensi bidang kecil.

Prinsip Circle FRI

Inovasi inti dari Circle STARKs terletak pada Circle FRI. Diberikan sebuah bilangan prima p, kita dapat membangun sebuah grup berukuran p, grup ini memiliki sifat yang mirip dengan pemetaan dua-ke-satu.

Grup ini terdiri dari sekumpulan titik yang memenuhi x^2 mod p sama dengan suatu nilai tertentu. Titik-titik ini mengikuti aturan penjumlahan khusus:

(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Formula poin ganda adalah:

2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI pertama-tama mengkonsolidasikan semua titik ke dalam satu garis lurus:

f0(x) = (F(x,y) + F(x,-y))/2

Kemudian lakukan kombinasi linear 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 akan mengurangi ukuran himpunan titik setengah setiap kali, mencapai efek yang mirip dengan FRI biasa.

FFT Lingkaran

Lingkaran grup juga mendukung operasi FFT, cara konstruksinya mirip dengan Circle FRI. Perbedaan kunci adalah bahwa Circle FFT tidak memproses polinomial dalam arti ketat, tetapi ruang Riemann-Roch yang disebut.

Ini berarti bahwa koefisien output Circle FFT tidak seperti FFT biasa yang merupakan monomial, melainkan fungsi dasar yang spesifik untuk Circle FFT.

Sebagai pengembang, kita dapat mengabaikan rincian matematika ini. Cukup simpan polinomial sebagai sekumpulan nilai evaluasi, gunakan FFT untuk perluasan derajat rendah.

Perhitungan Bisnis dan Polinomial Hilang

Dalam Circle STARKs, karena tidak ada fungsi linier titik tunggal, diperlukan teknik operasi pembagian yang berbeda. Kami membuktikan dengan melakukan evaluasi pada dua titik untuk menambahkan satu titik virtual.

Polin hilang juga perlu disesuaikan. Dalam Circle STARKs, bentuk polin hilang adalah:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Penyesuaian Urutan Terbalik

Untuk menyesuaikan dengan struktur lipatan Circle FRI, perlu menyesuaikan urutan terbalik. Pemikiran dasar adalah membalik setiap digit kecuali digit terakhir, menggunakan digit terakhir untuk menentukan apakah digit lainnya dibalik.

Analisis Efisiensi

Circle STARKs sangat efisien pada bidang bilangan prima 31. Ini memanfaatkan ruang bidang secara optimal, mengurangi pemborosan. Dibandingkan dengan SNARKs bidang besar, Circle STARKs memiliki keunggulan dalam logika bisnis dan tabel pencarian.

Rencana seperti Binius mencapai efisiensi yang lebih tinggi dengan menggabungkan bidang berukuran berbeda, tetapi meningkatkan kompleksitas. Circle STARKs secara konsep lebih sederhana.

Kesimpulan

Circle STARKs menyediakan solusi implementasi STARKs yang efisien dan relatif sederhana bagi para pengembang. Ini secara cerdik memanfaatkan karakteristik grup lingkaran, sambil mempertahankan keamanan dan secara signifikan meningkatkan efisiensi.

Arah optimasi STARKs di masa depan mungkin termasuk:

• Memaksimalkan efisiensi fungsi hash dan primitive kriptografi dasar lainnya
• Mewujudkan lebih banyak paralelisasi melalui konstruksi rekursif
• Meningkatkan aritmetika mesin virtual untuk meningkatkan pengalaman pengembangan

Secara keseluruhan, Circle STARKs adalah tonggak penting dalam perkembangan teknologi STARKs, memberikan ide baru untuk membangun sistem bukti nol yang lebih efisien.