Jelajahi Circle STARKs

Dalam beberapa tahun terakhir, tren desain protokol STARKs 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 relatif rendah, dalam banyak kasus, pemrosesan perhitungan angka besar ini tidak memiliki kegunaan praktis, dan juga 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 sebuah laptop M3. Ini berarti, selama kita mau 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? Bagaimana protokol ini dibandingkan dengan solusi seperti Binius? Artikel ini akan membahas rincian tersebut, dengan fokus khusus pada solusi yang disebut Circle STARKs, yang memiliki sifat unik yang kompatibel dengan bidang Mersenne31.

Masalah Umum Saat Menggunakan Bidang Matematika yang Lebih Kecil

Saat membuat bukti berbasis hash, salah satu teknik yang sangat penting adalah membuktikan hasil evaluasi polinomial di titik acak, yang dapat secara tidak langsung memverifikasi sifat-sifat polinomial. Metode ini dapat sangat menyederhanakan proses pembuktian, karena evaluasi di titik acak biasanya jauh lebih mudah daripada menangani seluruh polinomial.

Untuk mencegah serangan, kita perlu memilih r setelah penyerang memberikan A. Fiat-Shamir adalah teknik untuk meningkatkan keamanan protokol dengan mengatur beberapa parameter sebagai nilai hash tertentu untuk menghindari serangan. Parameter yang dipilih perlu berasal dari himpunan yang cukup besar untuk memastikan penyerang tidak dapat memprediksi atau menebak parameter ini, 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, sehingga kami dapat memilih r sebagai angka 256-bit acak, dan itu saja. Namun, dalam STARKs pada bidang yang lebih kecil, kami menghadapi masalah: hanya ada sekitar 2 miliar kemungkinan nilai r yang dapat dipilih, sehingga seorang penyerang yang ingin memalsukan bukti hanya perlu mencoba 2 miliar kali. Meskipun beban kerjanya besar, ini masih sepenuhnya mungkin dilakukan oleh penyerang yang bertekad!

Ada dua solusi untuk masalah ini:

• Melakukan pemeriksaan acak berkali-kali
• Bidang Ekstensi

Metode untuk melakukan beberapa pemeriksaan acak adalah yang paling sederhana dan efektif: alih-alih memeriksa pada satu koordinat, lebih baik melakukan pemeriksaan ulang di empat koordinat acak. Ini secara teoritis mungkin, tetapi ada masalah efisiensi. Jika Anda menangani polinomial dengan derajat kurang dari nilai tertentu dan beroperasi pada suatu domain ukuran tertentu, penyerang sebenarnya dapat membangun polinomial jahat yang terlihat normal di lokasi-lokasi 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 bahwa dapat secara efektif mempertahankan serangan dari penyerang.

Ini membawa kita pada solusi lain: bidang perluasan, bidang perluasan mirip dengan bilangan kompleks, tetapi didasarkan pada bidang hingga. Kita memperkenalkan nilai baru, yang kita sebut α, dan menyatakan bahwa ia memenuhi hubungan tertentu, misalnya α2=nilai tertentu. Dengan cara ini, kita menciptakan struktur matematika baru yang mampu melakukan operasi yang lebih kompleks di atas bidang hingga. Dalam bidang perluasan ini, perhitungan perkalian menjadi perkalian menggunakan nilai baru α. Sekarang kita dapat mengoperasikan pasangan nilai dalam bidang perluasan, bukan hanya angka tunggal. Misalnya, jika kita bekerja di atas bidang seperti Mersenne atau BabyBear, perluasan semacam itu memungkinkan kita memiliki lebih banyak pilihan nilai, sehingga meningkatkan keamanan. Untuk lebih meningkatkan ukuran bidang, kita dapat menerapkan teknik yang sama secara berulang. Karena kita telah menggunakan α, kita perlu mendefinisikan nilai baru, yang dalam Mersenne31 muncul sebagai memilih α sehingga α2=nilai tertentu.

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 jaminan keamanan yang cukup. 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 dalam protokol FRI dan skenario lain yang memerlukan kombinasi linear acak. Sebagian besar operasi matematika masih dilakukan di atas bidang dasar, yang biasanya merupakan bidang mod p atau q. Pada saat yang sama, hampir semua data hash dilakukan di atas bidang dasar, sehingga setiap nilai hanya perlu di-hash empat byte. Melakukan ini dapat memanfaatkan efisiensi bidang kecil, sementara saat diperlukan peningkatan keamanan, bidang yang lebih besar dapat digunakan.

FRI Reguler

Dalam membangun SNARK atau STARK, langkah pertama biasanya adalah arithmetization. Ini adalah proses mengubah masalah komputasi 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 sebuah polinomial, X, Y, dan Z adalah parameter yang diberikan, dan pemecah perlu menyediakan nilai untuk X dan Y. Setelah ada persamaan seperti itu, solusi dari persamaan tersebut akan sesuai dengan solusi dari masalah komputasi yang mendasarinya.

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

• Misalkan Anda memiliki nilai evaluasi dari polinomial A, Anda ingin membuktikan bahwa 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 linier acak dari B dan C, yaitu D=B+rC, di mana r adalah koefisien acak.

Pada dasarnya, yang terjadi adalah B mengisolasi koefisien genap A, dan C mengisolasi 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 akan masing-masing menjadi derajat A dan derajat A dikurangi 1. Karena kombinasi suku genap dan 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 memenuhi persyaratan melalui 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.

Prinsip kerja FRI adalah mengulangi proses penyederhanaan ini. Misalnya, jika Anda mulai dari membuktikan derajat polinomial adalah d, melalui serangkaian langkah, Anda pada akhirnya akan membuktikan derajat polinomial adalah d/2. Setiap kali setelah penyederhanaan, derajat polinomial yang dihasilkan secara bertahap berkurang. Jika output pada suatu tahap bukan derajat polinomial yang diharapkan, maka pemeriksaan pada putaran tersebut akan gagal. Jika seseorang mencoba untuk mendorong polinomial yang bukan derajat d melalui teknik ini, maka pada output putaran kedua, derajatnya akan memiliki probabilitas tertentu untuk tidak sesuai dengan yang diharapkan, dan pada putaran ketiga kemungkinan besar akan ada ketidakcocokan, sehingga pemeriksaan akhir akan gagal. Desain ini dapat secara efektif mendeteksi dan menolak input yang tidak memenuhi syarat. Jika dataset pada sebagian besar posisi sama dengan polinomial derajat d, dataset ini mungkin dapat divalidasi melalui FRI. Namun, untuk membangun dataset seperti itu, penyerang perlu mengetahui polinomial yang sebenarnya, jadi bahkan jika terdapat bukti dengan cacat kecil, itu menunjukkan bahwa pembuktian mampu menghasilkan bukti "nyata".

Mari kita lebih memahami secara rinci apa yang terjadi di sini, serta atribut yang diperlukan untuk membuat semuanya berfungsi dengan baik. Di setiap langkah, kita mengurangi derajat polinomial setengah, dan juga mengurangi set titik (kumpulan titik yang kita perhatikan) setengah. Yang pertama adalah kunci agar protokol FRI dapat berfungsi dengan baik. Yang kedua membuat algoritma berjalan sangat cepat: karena ukuran setiap putaran berkurang setengah dibandingkan 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 setengah. Salah satu keuntungan penting dari pemetaan dua-ke-satu ini adalah bahwa ia dapat diulang. Artinya, 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. 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, sampai akhirnya hanya tersisa satu nilai. Meskipun secara teori kita dapat mengecilkan dataset hingga menyisakan satu nilai, dalam praktiknya, biasanya kita akan berhenti sebelum mencapai kumpulan yang lebih kecil.

Anda dapat membayangkan proses ini sebagai suatu operasi di mana sebuah garis (misalnya, segmen atau busur) yang berada di tepi lingkaran diperpanjang di sepanjang lingkaran, sehingga berputar dua kali mengelilingi lingkaran. Misalnya, jika sebuah titik berada pada posisi x derajat di tepi lingkaran, maka setelah operasi ini, titik tersebut akan bergerak ke posisi 2x derajat. Setiap titik di tepi lingkaran dari posisi 0 hingga 179 derajat memiliki titik yang sesuai di posisi 180 hingga 359 derajat, dan kedua titik ini akan重合. Ini berarti, ketika Anda memetakan sebuah titik dari x derajat ke 2x derajat, titik tersebut akan重合 dengan sebuah titik yang berada di posisi x+180 derajat. Proses ini dapat diulang. Artinya, Anda dapat menerapkan operasi pemetaan ini beberapa kali, setiap kali memindahkan titik-titik di tepi lingkaran ke posisi baru mereka.

Untuk membuat teknik pemetaan efektif, ukuran subgrup perkalian asli perlu memiliki faktor besar dari 2 yang merupakan pangkat. BabyBear adalah sistem dengan modulus tertentu, di mana modulusnya adalah nilai tertentu yang membuat subgrup perkalian maksimumnya mencakup semua nilai non-nol, sehingga ukuran subgrupnya adalah 2k−1 (di mana k adalah jumlah bit dari modulus). Ukuran subgrup seperti ini sangat cocok untuk teknik di atas, karena memungkinkan pengurangan derajat polinomial secara efisien melalui penerapan operasi pemetaan berulang. Di BabyBear, Anda dapat memilih subgrup 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 tersebut. Metode ini memanfaatkan sifat modulus dan ukuran subgrup perkalian, sehingga proses perhitungan sangat efisien. Mersenne31 adalah sistem lain, di mana modulusnya adalah nilai tertentu yang membuat ukuran subgrup perkalian menjadi 2^31 - 1. Dalam kasus ini, ukuran subgrup perkalian hanya memiliki satu faktor 2 yang merupakan pangkat, yang membuatnya hanya dapat dibagi oleh 2 sekali. Proses selanjutnya tidak lagi berlaku untuk teknik di atas, artinya tidak memungkinkan untuk menggunakan FFT seperti di BabyBear untuk pengurangan derajat polinomial secara efektif.

Domain Mersenne31 sangat ideal untuk operasi aritmatika dalam operasi CPU/GPU 32-bit yang ada. Karena sifat modulusnya (misalnya 2^31 - 1), banyak operasi dapat dilakukan dengan menggunakan manipulasi bit yang efisien: jika jumlah dua angka melebihi modulus, itu dapat dikurangi ke kisaran yang sesuai dengan mengganti hasil dari modulus. Operasi perpindahan adalah operasi yang sangat efisien. Dalam perkalian, hasilnya dapat diproses menggunakan instruksi CPU tertentu (sering disebut sebagai instruksi perpindahan tinggi). Instruksi ini dapat secara efisien menghitung bagian tingkat tinggi dari perkalian, yang meningkatkan efisiensi operasi. Dalam domain Mersenne31, operasi aritmatika sekitar 1,3 kali lebih cepat daripada di domain BabyBear karena karakteristik di atas. Mersenne31 menawarkan efisiensi komputasi yang lebih besar. Jika FRI dapat diimplementasikan di domain Mersenne31, ini akan secara signifikan meningkatkan efisiensi komputasi dan membuat penerapan FRI