Menjelajahi Circle STARKs

Dalam beberapa tahun terakhir, tren desain protokol STARKs telah beralih ke penggunaan bidang yang lebih kecil. Implementasi produksi STARKs yang paling awal menggunakan bidang 256-bit, yaitu melakukan operasi modulo pada angka besar, yang membuat protokol ini kompatibel dengan tanda tangan berbasis kurva elips. Namun, efisiensi desain ini cukup rendah, dalam banyak kasus, memproses perhitungan angka besar ini tidak memiliki kegunaan praktis, dan juga akan membuang banyak daya komputasi. Untuk mengatasi masalah ini, STARKs mulai beralih ke penggunaan bidang yang lebih kecil: pertama Goldilocks, kemudian Mersenne31 dan BabyBear.

Transformasi ini meningkatkan kecepatan pembuktian, misalnya Starkware dapat membuktikan 620.000 nilai hash Poseidon2 per detik pada laptop M3. Ini berarti, selama kita bersedia mempercayai Poseidon2 sebagai fungsi hash, maka kita dapat menyelesaikan tantangan dalam mengembangkan ZK-EVM yang efisien. Jadi, bagaimana teknologi ini bekerja? Bagaimana pembuktian ini dibangun di atas bidang yang lebih kecil? Bagaimana protokol ini dibandingkan dengan solusi seperti Binius? Artikel ini akan menjelajahi detail tersebut, dengan fokus khusus pada sebuah solusi yang disebut Circle STARKs, yang memiliki atribut unik yang kompatibel dengan bidang Mersenne31.

Masalah Umum Saat Menggunakan Bidang Matematika yang Lebih Kecil

Saat membuat bukti berbasis hash ( atau jenis bukti lainnya ), teknik yang sangat penting adalah dengan membuktikan hasil evaluasi polinomial pada titik acak, yang dapat secara tidak langsung memverifikasi sifat polinomial tersebut. Metode ini dapat sangat menyederhanakan proses pembuktian, karena evaluasi pada titik acak biasanya jauh lebih mudah dibandingkan dengan menangani seluruh polinomial.

Misalnya, anggaplah sebuah sistem bukti meminta Anda untuk menghasilkan komitmen terhadap polinomial, A, yang harus memenuhi A^3(x) + x - A(ωx) = x^N(, salah satu jenis bukti yang sangat umum dalam protokol ZK-SNARK ). Protokol dapat meminta Anda untuk memilih koordinat acak r dan membuktikan A(r) + r - A(ωr) = r^N. Kemudian, mundur A(r) = c, Anda membuktikan Q = (A - c)/(X - r) adalah sebuah polinomial.

Untuk mencegah serangan, kita perlu memilih r setelah penyerang memberikan A. Parameter yang dipilih harus berasal dari kumpulan yang cukup besar untuk memastikan bahwa penyerang tidak dapat memprediksi atau menebak parameter tersebut, sehingga meningkatkan keamanan sistem.

Dalam protokol berbasis kurva elips dan STARKs dari tahun 2019, masalah ini sangat sederhana: semua operasi matematika kami dilakukan pada angka 256 bit, jadi kami dapat memilih r sebagai angka 256 bit acak, dan itu sudah cukup. Namun, dalam STARKs pada bidang yang lebih kecil, kami menghadapi masalah: hanya ada sekitar 2 miliar kemungkinan nilai r yang dapat dipilih, jadi seorang penyerang yang ingin memalsukan bukti hanya perlu mencoba 2 miliar kali, meskipun bebannya cukup besar, tetapi bagi seorang penyerang yang bertekad, itu masih sepenuhnya mungkin!

Masalah ini memiliki dua solusi:

• Melakukan pemeriksaan acak berkali-kali
• Bidang tambahan

Metode pelaksanaan pemeriksaan acak berkali-kali adalah yang paling sederhana dan efektif: alih-alih memeriksa di satu koordinat, lebih baik memeriksa ulang di empat koordinat acak. Ini secara teoritis dapat dilakukan, tetapi ada masalah efisiensi. Jika Anda menangani polinomial dengan derajat kurang dari nilai tertentu, dan beroperasi di suatu bidang dengan ukuran tertentu, penyerang sebenarnya dapat membangun polinomial jahat yang tampak normal di posisi-posisi ini. Oleh karena itu, apakah mereka dapat berhasil merusak protokol adalah masalah probabilitas, sehingga perlu meningkatkan jumlah putaran pemeriksaan untuk meningkatkan keamanan secara keseluruhan dan memastikan dapat secara efektif mempertahankan serangan dari penyerang.

Ini menimbulkan solusi lain: ekstensi domain, ekstensi domain mirip dengan bilangan kompleks, tetapi itu didasarkan pada domain terbatas. Kami memperkenalkan nilai baru, yang disebut α, dan menyatakan bahwa ia memenuhi hubungan tertentu, seperti α^2=some value. Dengan cara ini, kami menciptakan struktur matematis baru yang mampu melakukan perhitungan yang lebih kompleks di atas domain terbatas. Dalam ekstensi domain ini, perhitungan perkalian menjadi menggunakan nilai baru α. Kami sekarang dapat beroperasi pada pasangan nilai dalam domain yang diperluas, bukan hanya angka tunggal. Misalnya, jika kami bekerja pada bidang seperti Mersenne atau BabyBear, ekstensi semacam ini memungkinkan kami memiliki lebih banyak pilihan nilai, sehingga meningkatkan keamanan. Untuk lebih meningkatkan ukuran bidang, kami dapat menerapkan teknik yang sama berulang kali. Karena kami telah menggunakan α, kami perlu mendefinisikan nilai baru, yang dalam Mersenne31 muncul sebagai pemilihan α sehingga α^2=some value.

Dengan memperluas domain, kami sekarang memiliki cukup banyak nilai untuk dipilih, memenuhi kebutuhan keamanan kami. Jika yang diproses adalah polinomial dengan derajat kurang dari d, setiap putaran dapat memberikan keamanan 104 bit. Ini berarti kami memiliki cukup perlindungan keamanan. Jika perlu mencapai tingkat keamanan yang lebih tinggi, seperti 128 bit, kami dapat menambahkan beberapa pekerjaan komputasi tambahan dalam protokol untuk meningkatkan keamanan.

Domain ekstensi hanya digunakan secara praktis dalam protokol FRI(Fast Reed-Solomon Interactive) dan skenario lain yang memerlukan kombinasi linier acak. Sebagian besar operasi matematika masih dilakukan di atas bidang dasar, yang biasanya merupakan bidang modulo p atau q. Sementara itu, hampir semua data hash dilakukan di atas bidang dasar, sehingga setiap nilai hanya perlu di-hash empat byte. Dengan cara ini, efisiensi bidang kecil dapat dimanfaatkan, sementara ketika perlu meningkatkan keamanan, bidang yang lebih besar dapat digunakan.

FRI Reguler

Dalam membangun SNARK atau STARK, langkah pertama biasanya adalah arithmetization. Ini adalah proses mengubah masalah perhitungan yang arbitrer menjadi sebuah persamaan, di mana beberapa variabel dan koefisien adalah polinomial. Secara khusus, persamaan ini biasanya akan terlihat seperti P(X,Y,Z)=0, di mana P adalah polinomial, X, Y, dan Z adalah parameter yang diberikan, dan solver perlu memberikan nilai untuk X dan Y. Setelah ada persamaan seperti itu, solusi dari persamaan tersebut akan sesuai dengan solusi dari masalah perhitungan yang mendasarinya.

Untuk membuktikan bahwa Anda memiliki solusi, Anda perlu membuktikan bahwa nilai yang Anda ajukan benar-benar merupakan polinomial yang masuk akal ( dan bukan pecahan, atau di beberapa tempat terlihat seperti polinomial, tetapi di tempat lain merupakan polinomial yang berbeda, dan seterusnya ), dan polinomial ini memiliki derajat maksimum tertentu. Untuk itu, kami menggunakan teknik kombinasi linier acak yang diterapkan secara bertahap:

• Misalkan kamu memiliki nilai evaluasi dari polinomial A, kamu ingin membuktikan derajatnya kurang dari 2^20
• Pertimbangkan polinomial B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D adalah kombinasi linear acak dari B dan C, yaitu D=B+rC, di mana r adalah koefisien acak.

Pada dasarnya, yang terjadi adalah B memisahkan koefisien genap A, dan C memisahkan koefisien ganjil. Diberikan B dan C, Anda dapat memulihkan polinomial asli A: A(x) = B(x^2) + xC(x^2). Jika derajat A memang kurang dari 2^20, maka derajat B dan C masing-masing akan menjadi derajat A dan derajat A dikurangi 1. Karena kombinasi suku genap dan suku ganjil tidak akan meningkatkan derajat. Karena D adalah kombinasi linier acak dari B dan C, derajat D juga harus sama dengan derajat A, yang memungkinkan Anda untuk memverifikasi apakah derajat A sesuai dengan persyaratan berdasarkan derajat D.

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

Cara kerja FRI adalah mengulang proses penyederhanaan ini. Misalnya, jika Anda mulai dari polinomial yang derajatnya d, melalui serangkaian langkah, Anda pada akhirnya akan membuktikan bahwa derajat polinomial tersebut adalah d/2. Setiap kali setelah penyederhanaan, derajat polinomial yang dihasilkan secara bertahap berkurang. Jika keluaran pada suatu tahap bukan derajat polinomial yang diharapkan, maka pemeriksaan di putaran ini akan gagal. Jika seseorang mencoba untuk mendorong polinomial yang bukan derajat d menggunakan teknik ini, maka pada keluaran putaran kedua, derajatnya akan memiliki probabilitas tertentu untuk tidak sesuai harapan, di putaran ketiga kemungkinan untuk tidak sesuai akan meningkat, dan pemeriksaan akhir akan gagal. Desain ini dapat secara efektif mendeteksi dan menolak input yang tidak memenuhi syarat. Jika dataset di sebagian besar posisi sama dengan polinomial derajat d, dataset ini memiliki kemungkinan untuk diverifikasi melalui FRI. Namun, untuk membangun dataset semacam itu, penyerang perlu mengetahui polinomial yang sebenarnya, sehingga bahkan dengan bukti yang sedikit cacat pun menunjukkan bahwa pembuktinya mampu menghasilkan bukti yang "nyata".

Mari kita lebih memahami apa yang terjadi di sini, serta atribut yang diperlukan agar semuanya berfungsi dengan baik. Di setiap langkah, kita mengurangi derajat polinomial setengah, sambil juga mengurangi himpunan titik ( yang menjadi perhatian kita setengah. Yang pertama adalah kunci agar protokol FRI)Fast Reed-Solomon Interactive( dapat berfungsi dengan baik. Yang terakhir memungkinkan algoritma berjalan sangat cepat: karena ukuran setiap putaran berkurang setengah dari putaran sebelumnya, total biaya komputasi adalah O)N(, bukan O)N*log(N().

Untuk mencapai pengurangan bertahap dari domain, digunakan pemetaan dua-ke-satu, yaitu setiap titik dipetakan ke salah satu dari dua titik. Pemetaan ini memungkinkan kita untuk mengurangi ukuran dataset menjadi setengah. Salah satu keuntungan penting dari pemetaan dua-ke-satu ini adalah bahwa ia dapat diulang. Dengan kata lain, ketika kita menerapkan pemetaan ini, hasil yang diperoleh tetap mempertahankan atribut yang sama. Misalkan kita mulai dari subkelompok perkalian ). Subkelompok ini adalah kumpulan S, di mana setiap elemen x memiliki kelipatannya 2x juga ada dalam kumpulan tersebut. Jika kita melakukan operasi kuadrat pada kumpulan S ( yaitu memetakan setiap elemen x dalam kumpulan ke x^2), kumpulan baru S^2 juga akan mempertahankan atribut yang sama. Operasi ini memungkinkan kita untuk terus mengurangi ukuran dataset, hingga akhirnya hanya tersisa satu nilai. Meskipun secara teori kita dapat memperkecil dataset hingga hanya tersisa satu nilai, dalam praktiknya, kita biasanya berhenti sebelum mencapai kumpulan yang lebih kecil.

Anda dapat membayangkan operasi ini sebagai proses di mana sebuah garis pada keliling, misalnya, segmen atau busur (, membentang di sepanjang keliling, membuatnya berputar dua kali di sekitar keliling. Misalnya, jika suatu titik berada di posisi x derajat pada keliling, maka setelah operasi ini, ia akan bergerak ke posisi 2x derajat. Setiap titik pada keliling dari posisi 0 hingga 179 derajat memiliki titik yang sesuai di posisi 180 hingga 359 derajat, dan kedua titik ini akan重合. Ini berarti bahwa ketika Anda memetakan suatu titik dari x derajat ke 2x derajat, ia akan重合 dengan titik yang berada di posisi x+180 derajat. Proses ini dapat diulang. Dengan kata lain, Anda dapat menerapkan operasi pemetaan ini beberapa kali, setiap kali memindahkan titik pada keliling ke posisi baru mereka.

![Vitalik Karya Baru: Menjelajahi Circle STARKs])https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp(

Untuk membuat teknik pemetaan efektif, ukuran subkelompok perkalian asli perlu memiliki pangkat 2 yang besar sebagai faktor. BabyBear adalah sistem dengan modulus tertentu, di mana modulusnya adalah suatu nilai, sehingga subkelompok perkalian maksimumnya mencakup semua nilai non-nol, sehingga ukuran subkelompoknya adalah 2k−1) di mana k adalah jumlah bit dari modulus (. Ukuran subkelompok seperti ini sangat cocok untuk teknik di atas, karena memungkinkan pengurangan derajat polinomial secara efektif dengan menerapkan operasi pemetaan berulang kali. Di BabyBear, Anda dapat memilih subkelompok berukuran 2^k ) atau langsung menggunakan seluruh himpunan (, kemudian menerapkan metode FRI untuk secara bertahap mengurangi derajat polinomial hingga 15, dan pada akhirnya memeriksa derajat polinomial. Metode ini memanfaatkan sifat modulus dan ukuran subkelompok perkalian, sehingga proses perhitungan menjadi sangat efisien. Mersenne31 adalah sistem lain, di mana modulusnya adalah suatu nilai, sehingga ukuran subkelompok perkalian adalah 2^31 - 1. Dalam hal ini, ukuran subkelompok perkalian hanya memiliki satu pangkat 2 sebagai faktor, yang membuatnya hanya dapat dibagi 2 sekali. Proses selanjutnya tidak lagi cocok dengan teknik di atas, yang berarti tidak dapat menggunakan FFT seperti di BabyBear untuk mengurangi derajat polinomial secara efektif.

Domain Mersenne31 sangat cocok untuk melakukan operasi aritmatika pada CPU/GPU 32-bit yang ada. Karena sifat modulusnya ) misalnya 2^31 - 1( memungkinkan banyak operasi dapat dilakukan dengan menggunakan operasi bit yang efisien: jika hasil penjumlahan dua angka melebihi modulus, dapat dilakukan dengan mengoperasikan hasil tersebut dengan modulus menggunakan bit.