Judul asli: "Menjelajahi lingkaran STARK"
Ditulis oleh: Vitalik Buterin, salah satu pendiri Ethereum
Disusun oleh: Chris, Techub News
Prasyarat untuk memahami artikel ini adalah Anda sudah memahami prinsip dasar SNARK dan STARK. Jika Anda belum mengetahuinya, saya sarankan Anda membaca beberapa bagian pertama artikel ini untuk memahami dasar-dasarnya.
Dalam beberapa tahun terakhir, tren desain protokol STARK mengarah pada penggunaan bidang yang lebih kecil. Implementasi produksi STARK yang paling awal menggunakan bidang 256-bit, yaitu modulo aritmatika pada bilangan besar (seperti 21888...95617), yang membuat protokol ini kompatibel dengan tanda tangan berbasis kurva elips. Namun, efisiensi desain ini relatif rendah. Dalam keadaan normal, pemrosesan dan penghitungan angka-angka besar ini tidak memiliki kegunaan praktis, dan akan membuang banyak daya komputasi, seperti pemrosesan X (mewakili angka tertentu) dan pemrosesan empat kali X. , pemrosesan Hanya diperlukan sepersembilan waktu komputasi. Untuk mengatasi masalah ini, STARK mulai berpindah ke bidang yang lebih kecil: pertama Goldilocks, lalu Mersenne31 dan BabyBear.
Pergeseran ini telah meningkatkan kecepatan pembuktian, seperti Starkware yang mampu membuktikan 620.000 hash Poseidon2 per detik pada laptop M3. Artinya, selama kita mau mempercayai Poseidon2 sebagai fungsi hash, kita dapat memecahkan masalah sulit dalam mengembangkan ZK-EVM yang efisien. Jadi bagaimana cara kerja teknologi ini? Bagaimana bukti-bukti ini dibangun pada bidang yang lebih kecil? Bagaimana protokol ini dibandingkan dengan solusi seperti Binius? Artikel ini akan mengeksplorasi detail ini, dengan fokus khusus pada skema yang disebut Circle STARKs (diimplementasikan di stwo Starkware, plonky3 Polygon, dan versi saya sendiri di Python), yang memiliki properti unik yaitu kompatibel dengan bidang Mersenne31.
Masalah umum saat bekerja dengan bidang matematika yang lebih kecil
Trik yang sangat penting ketika membuat bukti berbasis hash (atau bukti apa pun) adalah dengan dapat memverifikasi sifat-sifat polinomial secara tidak langsung dengan mengevaluasi polinomial tersebut pada titik-titik acak. Pendekatan ini dapat menyederhanakan proses pembuktian, karena evaluasi pada titik acak biasanya jauh lebih mudah daripada menangani seluruh polinomial.
Misalnya, sistem pembuktian mengharuskan Anda membuat komitmen terhadap polinomial, A, yang harus memenuhi A^3 (x) + x - A (\omega*x) = x^N (yang sangat umum di ZK -Jenis bukti protokol SNARK). Protokol dapat meminta Anda untuk memilih koordinat acak ? dan membuktikan bahwa A (r) + r - A (\omega*r) = r^N. Kemudian kerjakan mundur ke A (r) = c, dan Anda membuktikan bahwa Q = \frac {A - c}{X - r} adalah polinomial.
Jika Anda mengetahui detail atau internal protokol sebelumnya, Anda mungkin dapat menemukan cara untuk melewati atau meretasnya. Tindakan atau metode khusus untuk mencapai hal ini dapat disebutkan selanjutnya. Misalnya, untuk memenuhi persamaan A (\omega * r), Anda dapat menyetel A (r) ke 0 dan misalkan A adalah garis lurus yang melalui kedua titik tersebut.
Untuk mencegah serangan ini, kita perlu memilih r setelah penyerang memberikan A (Fiat-Shamir adalah teknik yang digunakan untuk meningkatkan keamanan protokol dengan menetapkan parameter tertentu ke beberapa nilai hash untuk menghindari serangan. Pilih Parameter harus berasal dari nilai yang cukup besar diatur untuk memastikan bahwa penyerang tidak dapat memprediksi atau menebak parameter ini, sehingga meningkatkan keamanan sistem.
Dalam protokol berbasis kurva elips dan STARK pada periode 2019, masalahnya sederhana: semua operasi matematika kita dilakukan pada bilangan 256-bit, sehingga kita dapat memilih r sebagai bilangan acak 256-bit, sehingga . Namun, dalam STARK pada bidang yang lebih kecil, kita mengalami masalah: hanya ada sekitar 2 miliar kemungkinan nilai r yang dapat dipilih, sehingga penyerang yang ingin memalsukan bukti hanya perlu mencoba 2 miliar kali, yaitu a banyak pekerjaan. , tapi untuk penyerang yang gigih, itu masih mungkin!
Ada dua solusi untuk masalah ini:
Lakukan beberapa pemeriksaan acak
TIDAK
Cara paling sederhana dan efisien untuk melakukan beberapa pemeriksaan acak adalah: daripada memeriksa pada satu koordinat, ulangi pemeriksaan pada empat koordinat acak. Secara teoritis hal ini mungkin dilakukan, namun terdapat masalah efisiensi. Jika Anda berurusan dengan polinomial yang derajatnya kurang dari nilai tertentu, dan Anda beroperasi pada domain dengan ukuran tertentu, penyerang sebenarnya dapat membuat polinomial berbahaya yang terlihat normal di lokasi tersebut. Oleh karena itu, apakah mereka berhasil melanggar protokol masih merupakan pertanyaan yang bersifat probabilistik, sehingga jumlah putaran pemeriksaan perlu ditingkatkan untuk meningkatkan keamanan secara keseluruhan dan memastikan bahwa penyerang dapat bertahan secara efektif dari serangan.
Hal ini mengarah pada solusi lain: bidang yang diperluas seperti bilangan kompleks, tetapi didasarkan pada bidang yang terbatas. Kita memperkenalkan nilai baru, dilambangkan dengan α\alphaα, dan mendeklarasikan bahwa nilai tersebut memenuhi hubungan tertentu, seperti α2=some value\alpha^2 = \text {some value}α2=some value. Dengan cara ini, kami menciptakan struktur matematika baru yang mampu melakukan operasi yang lebih kompleks pada bidang berhingga. Dalam domain yang diperluas ini, penghitungan perkalian menjadi perkalian menggunakan nilai baru α\alphaα. Kami sekarang dapat mengoperasikan pasangan nilai dalam domain yang diperluas, bukan hanya angka tunggal. Misalnya, jika kita bekerja di bidang seperti Mersenne atau BabyBear, ekstensi seperti itu memungkinkan kita memiliki lebih banyak pilihan nilai, sehingga meningkatkan keamanan. Untuk lebih meningkatkan ukuran bidang, kita dapat menerapkan teknik yang sama berulang kali. Karena kita sudah menggunakan α\alphaα, kita perlu mendefinisikan nilai baru, yang di Mersenne31 diwakili dengan memilih α\alphaα sehingga α2=some value\alpha^2 = \text {some value}α2=some value.
Kode (Anda dapat memperbaikinya dengan Karatsuba)
Dengan memperluas domain, kami kini memiliki cukup nilai untuk dipilih yang memenuhi kebutuhan keamanan kami. Jika Anda berurusan dengan polinomial dengan derajat kurang dari ddd, ini memberikan keamanan 104 bit per putaran. Ini berarti kami memiliki keamanan yang memadai. Jika tingkat keamanan yang lebih tinggi diperlukan, seperti 128-bit, kita dapat menambahkan beberapa pekerjaan komputasi tambahan ke protokol untuk meningkatkan keamanan.
Domain yang diperluas sebenarnya hanya digunakan dalam protokol FRI (Fast Reed-Solomon Interactive) dan skenario lain yang memerlukan kombinasi linier acak. Sebagian besar perhitungan masih dilakukan pada bidang dasar, yang biasanya berupa bidang modulo ppp atau qqq. Selain itu, hampir semua data yang di-hash dilakukan pada kolom yang mendasarinya, sehingga hanya empat byte per nilai yang di-hash. Hal ini akan memanfaatkan efisiensi field kecil sekaligus memungkinkan penggunaan field yang lebih besar ketika peningkatan keamanan diperlukan.
Jumat Reguler
Saat membuat SNARK atau STARK, langkah pertama biasanya adalah aritmetisasi. Ini adalah konversi masalah komputasi apa pun menjadi persamaan yang beberapa variabel dan koefisiennya berbentuk polinomial. Secara khusus, persamaan ini biasanya akan terlihat seperti P (X,Y,Z)=0P (X,Y,Z) = 0P (X,Y,Z)=0, dengan P adalah polinomial dan Z adalah parameter tertentu, dan pemecah perlu memberikan nilai X dan Y. Setelah Anda memiliki persamaan seperti itu, solusi persamaan tersebut akan sesuai dengan solusi masalah komputasi yang mendasarinya.
Untuk membuktikan bahwa Anda memiliki solusi, Anda perlu menunjukkan bahwa nilai yang Anda peroleh memang merupakan polinomial yang sah (bukan pecahan, atau terlihat seperti satu polinomial di beberapa tempat dan polinomial berbeda di tempat lain, dll.), Dan polinomial ini mempunyai derajat maksimum tertentu. Untuk melakukan ini kami menggunakan teknik kombinasi linier stokastik yang diterapkan secara bertahap:
Misalkan Anda mempunyai evaluasi polinomial A dan Anda ingin membuktikan bahwa derajatnya kurang dari 2^{20}
Perhatikan polinomial B (x^2) = A (x) + A (-x), C (x^2) = \frac {A (x) - A (-x)}{x}
D adalah kombinasi linier acak dari B dan C, yaitu D=B+rCD = B + rCD=B+rC, dengan r adalah koefisien acak.
Pada dasarnya, yang terjadi adalah B mengisolasi koefisien genap dari A, dan ? Mengingat B dan C, Anda dapat memulihkan polinomial asli A: A (x) = B (x^2) + xC (x^2). Jika derajat A memang lebih kecil dari 2^{20}, maka derajat B dan C masing-masing adalah derajat A dan derajat A dikurangi 1. Karena penggabungan suku genap dan ganjil tidak menaikkan derajat. Karena D adalah kombinasi linier acak dari B dan C, maka derajat D juga harus berupa derajat A, sehingga Anda dapat menggunakan derajat D untuk memverifikasi bahwa derajat A memenuhi persyaratan.
Pertama, FRI menyederhanakan proses verifikasi dengan mereduksi permasalahan pembuktian polinomial berderajat d menjadi permasalahan pembuktian polinomial berderajat d/2. Proses ini dapat diulang berkali-kali, sehingga setiap kali menyederhanakan permasalahan menjadi setengahnya.
FRI bekerja dengan mengulangi proses penyederhanaan ini. Misalnya, jika Anda memulai dengan membuktikan bahwa derajat suatu polinomial adalah d, melalui serangkaian langkah pada akhirnya Anda akan membuktikan bahwa derajat polinomial tersebut adalah d/2. Setelah setiap penyederhanaan, derajat polinomial yang dihasilkan secara bertahap menurun. Jika keluaran suatu tahapan tidak sesuai dengan derajat polinomial yang diharapkan, maka putaran pemeriksaan ini akan gagal. Jika seseorang mencoba untuk mendorong polinomial yang tidak berderajat d melalui teknik ini, maka pada keluaran putaran kedua, derajatnya tidak akan memenuhi harapan dengan probabilitas tertentu, dan pada putaran ketiga kemungkinan besar akan tidak konsisten, dan akhirnya Pengecekan akan gagal. Perancangan ini dapat secara efektif mendeteksi dan menolak masukan yang tidak memenuhi persyaratan. Suatu kumpulan data kemungkinan lolos validasi FRI jika sama dengan polinomial derajat d di sebagian besar lokasi. Namun, untuk membangun kumpulan data seperti itu, penyerang perlu mengetahui polinomial sebenarnya, sehingga bahkan bukti yang sedikit cacat pun menunjukkan bahwa pembukti mampu menghasilkan bukti yang "nyata".
Mari kita lihat lebih dekat apa yang terjadi di sini, dan properti yang diperlukan agar semua ini berfungsi. Pada setiap langkah, kita mengurangi derajat polinomial menjadi dua, dan juga mengurangi himpunan titik (kumpulan titik yang kita minati) menjadi dua. Yang pertama adalah kunci agar protokol FRI (Fast Reed-Solomon Interactive) berfungsi dengan baik. Hal terakhir ini membuat algoritme berjalan sangat cepat: karena ukuran setiap putaran dikurangi setengahnya dibandingkan putaran sebelumnya, total biaya komputasi adalah O (N) dan bukan O (N*log (N)).
Untuk mencapai pengurangan domain secara progresif, digunakan pemetaan dua-ke-satu, yaitu setiap titik dipetakan ke salah satu dari dua titik. Pemetaan ini memungkinkan kami mengurangi ukuran kumpulan data hingga setengahnya. Keuntungan penting dari pemetaan dua-ke-satu ini adalah pemetaan ini dapat diulang. Artinya, ketika kita menerapkan pemetaan ini, kumpulan hasil yang dihasilkan masih mempertahankan properti yang sama. Misalkan kita memulai dengan subgrup perkalian. Subgrup ini adalah himpunan S yang setiap elemen x mempunyai kelipatan 2x juga dalam himpunan tersebut. Jika Anda mengkuadratkan himpunan S (yaitu, memetakan setiap elemen x dalam himpunan ke x^2), himpunan baru S^2 juga akan mempertahankan properti yang sama. Operasi ini memungkinkan kami untuk terus mengurangi ukuran kumpulan data hingga akhirnya hanya tersisa satu nilai. Meskipun secara teori kita dapat memperkecil kumpulan data menjadi satu nilai saja, dalam praktiknya kita biasanya berhenti sebelum mencapai kumpulan data yang lebih kecil.
Anda dapat membayangkan operasi ini sebagai proses merentangkan sebuah garis (misalnya ruas garis atau busur) pada keliling lingkaran sehingga membuat dua putaran mengelilingi lingkaran. Misalnya, jika suatu titik berada pada x derajat pada kelilingnya, maka titik tersebut akan berpindah ke 2x derajat setelah operasi ini. Setiap titik pada lingkaran dari 0 hingga 179 derajat memiliki titik yang bersesuaian dari 180 hingga 359 derajat, dan kedua titik ini akan berimpit. Artinya, jika Anda memetakan suatu titik dari x derajat ke 2x derajat, maka titik tersebut akan bertepatan dengan posisinya di x+180 derajat. Proses ini bisa diulang. Artinya, Anda dapat menerapkan operasi pemetaan ini beberapa kali, setiap kali memindahkan titik-titik pada lingkaran ke posisi barunya.
Agar teknik pemetaan menjadi efektif, ukuran subkelompok perkalian asli harus memiliki pangkat 2 yang besar sebagai faktor. BabyBear adalah sistem dengan modulus tertentu sehingga subgrup perkalian maksimalnya memuat semua nilai bukan nol, sehingga ukuran subgrupnya adalah 2k−1 (dimana k adalah banyaknya digit dalam modulus). Subkelompok sebesar ini sangat cocok untuk teknik di atas karena memungkinkan pengurangan derajat polinomial secara efisien dengan penerapan operasi pemetaan berulang kali. Di BabyBear, Anda dapat memilih subgrup berukuran 2^k (atau cukup menggunakan seluruh himpunan), lalu menerapkan metode FRI untuk mengurangi derajat polinomial secara bertahap menjadi 15, dan memeriksa derajat polinomial di akhir. Metode ini memanfaatkan sifat modulus dan ukuran subgrup perkalian sehingga membuat proses perhitungan menjadi sangat efisien. Mersenne31 adalah sistem lain yang modulusnya bernilai sedemikian rupa sehingga ukuran subgrup perkaliannya adalah 2^31 - 1. Dalam hal ini, ukuran subgrup perkalian hanya mempunyai pangkat 2 sebagai faktornya, sehingga subkelompok tersebut dapat dibagi 2 hanya sekali. Pemrosesan selanjutnya tidak lagi sesuai dengan teknik di atas, yaitu tidak mungkin menggunakan FFT untuk pengurangan derajat polinomial yang efisien seperti BabyBear.
Bidang Mersenne31 sangat cocok untuk operasi aritmatika pada operasi CPU/GPU 32-bit yang ada. Karena sifat modulusnya (seperti 2^{31} - 1), banyak operasi yang dapat diselesaikan menggunakan operasi bit yang efisien: jika hasil penjumlahan dua bilangan melebihi modulus, hasilnya dapat digeser dengan operasi modulus untuk menguranginya ke kisaran yang sesuai. Operasi perpindahan adalah operasi yang sangat efisien. Dalam operasi perkalian, instruksi CPU khusus (sering disebut instruksi shift tingkat tinggi) digunakan untuk memproses hasilnya. Instruksi ini dapat secara efisien menghitung bagian perkalian tingkat tinggi, sehingga meningkatkan efisiensi operasi. Di domain Mersenne31, operasi aritmatika kira-kira 1,3 kali lebih cepat dibandingkan di domain BabyBear karena properti yang dijelaskan di atas. Mersenne31 memberikan efisiensi komputasi yang lebih besar. Jika FRI dapat diimplementasikan di domain Mersenne31, hal ini akan meningkatkan efisiensi komputasi secara signifikan dan membuat aplikasi FRI lebih efisien.
Lingkari JUM
Ini adalah hal yang menarik tentang Circle STARK, dengan bilangan prima p, Anda dapat menemukan populasi berukuran p yang memiliki sifat dua banding satu yang serupa. Populasi ini terdiri dari semua titik yang memenuhi kondisi tertentu, misalnya himpunan titik di mana x^2 mod p sama dengan nilai tertentu.
Poin-poin ini mengikuti pola penjumlahan, yang mungkin tampak familier bagi Anda jika Anda baru saja melakukan sesuatu yang berhubungan dengan trigonometri atau perkalian kompleks.
(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)
Bentuk gandanya adalah:
2 * (x, y) = (2x^2 - 1, 2xy)
Sekarang, mari kita fokus pada titik-titik ganjil pada lingkaran ini:
Pertama, kita konvergenkan semua titik menjadi satu garis lurus. Bentuk persamaan dari rumus B (x²) dan C (x²) yang kita gunakan pada FRI biasa adalah:
f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}
Kita kemudian dapat melakukan kombinasi linier acak untuk mendapatkan polinomial satu dimensi P(x) yang didefinisikan pada subset garis x:
Mulai putaran kedua, pemetaannya berubah:
f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}
Pemetaan ini sebenarnya mengurangi ukuran himpunan di atas hingga setengahnya setiap kali, yang terjadi di sini adalah setiap x mewakili dua titik: (x, y) dan (x, -y). Dan (x → 2x^2 - 1) adalah aturan penggandaan poin di atas. Oleh karena itu, kita ubah koordinat x dari dua titik yang berlawanan pada lingkaran menjadi koordinat x dari titik yang dikalikan.
Misalnya, jika kita mengambil nilai kedua pada lingkaran dari kanan, 2, dan menerapkan pemetaan 2 → 2 (2^2) - 1 = 7, kita mendapatkan hasilnya 7. Jika kita kembali ke lingkaran semula, (2, 11) adalah titik ketiga dari kanan, maka gandakan sehingga kita mendapatkan titik keenam dari kanan, yaitu (7, 13).
Hal ini dapat dilakukan dalam dua dimensi, namun pengoperasian dalam satu dimensi membuat prosesnya lebih efisien.
Lingkari FFT
Algoritme yang terkait erat dengan FRI adalah FFT, yang mengubah n evaluasi polinomial yang derajatnya kurang dari n menjadi n koefisien polinomial tersebut. Proses FFT mirip dengan FRI, hanya saja alih-alih menghasilkan kombinasi linier acak f_0 dan f_1 pada setiap langkah, FFT secara rekursif melakukan FFT setengah ukuran dan mengambil keluaran FFT (f_0) sebagai koefisien genap. Perlakukan keluarannya dari FFT (f_1) sebagai koefisien ganjil.
Kelompok lingkaran juga mendukung FFT, yang dibangun dengan cara yang mirip dengan FRI. Namun, perbedaan utamanya adalah Lingkaran FFT (dan Lingkaran FRI) berhubungan dengan objek yang tidak sepenuhnya polinomial. Sebaliknya, secara matematis disebut ruang Riemann-Roch: dalam hal ini, polinomialnya berbentuk modulo lingkaran ( x^2 + y^2 - 1 = 0 ). Artinya, kelipatan x^2 + y^2 - 1 dianggap nol. Cara lain untuk memikirkannya adalah: kita hanya mengizinkan y dipangkatkan: segera setelah suku y^2 muncul, kita menggantinya dengan 1 - x^2 .
Artinya juga koefisien-koefisien yang dihasilkan oleh FFT Lingkaran bukanlah monomial seperti FRI biasa (misalnya jika keluaran FRI biasa adalah [6, 2, 8, 3], maka kita mengetahui bahwa ini berarti P (x) = 3x^3 + 8x ^2 + 2x + 6). Sebaliknya, koefisien FFT Lingkaran khusus untuk basis FFT Lingkaran: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}
Kabar baiknya adalah sebagai pengembang Anda hampir dapat mengabaikan hal ini sepenuhnya. STARK tidak pernah mengharuskan Anda mengetahui koefisiennya. Sebagai gantinya, Anda cukup menyimpan polinomial sebagai kumpulan nilai evaluasi pada domain tertentu. Satu-satunya tempat di mana Anda perlu menggunakan FFT adalah dengan melakukan ekstensi derajat rendah (mirip dengan ruang Riemann-Roch): jika diberi nilai N, hasilkan nilai k*N, semuanya pada polinomial yang sama. Dalam hal ini, Anda dapat menggunakan FFT untuk menghasilkan koefisien, menambahkan (k-1) n angka nol ke koefisien ini, dan kemudian menggunakan FFT invers untuk mendapatkan kumpulan nilai evaluasi yang lebih besar.
FFT Lingkaran bukan satu-satunya tipe FFT khusus. FFT kurva elips lebih kuat karena dapat bekerja pada bidang berhingga apa pun (bidang prima, bidang biner, dll.). Namun, ECFFT lebih kompleks dan kurang efisien, jadi karena kita dapat menggunakan FFT Lingkaran pada p = 2^{31}-1, kita memilih untuk menggunakannya.
Dari sini kita akan menyelami beberapa detail yang tidak jelas yang membuat implementasi Circle STARK berbeda dari STARK biasa.
hasil bagi
Dalam protokol STARK, operasi umum adalah melakukan operasi hasil bagi pada titik-titik tertentu. Titik-titik ini dapat dipilih secara sengaja atau acak. Misalnya, jika Anda ingin membuktikan P(x) = y, Anda dapat melakukannya dengan mengikuti langkah-langkah berikut:
Menghitung hasil bagi: Diketahui polinomial P (x) dan konstanta y, hitung hasil bagi Q ={P - y}/{X - x}, dengan X adalah titik yang dipilih.
Buktikan polinomial: Buktikan bahwa Q adalah polinomial, bukan pecahan. Dengan cara ini terbukti bahwa P (x)=y benar.
Selain itu, dalam protokol DEEP-FRI, titik evaluasi dipilih secara acak untuk mengurangi jumlah cabang Merkle, sehingga meningkatkan keamanan dan efisiensi protokol FRI.
Saat menangani protokol STARK grup lingkaran, karena tidak ada fungsi linier yang dapat melewati satu titik, teknik berbeda perlu digunakan untuk menggantikan metode operasi hasil bagi tradisional. Hal ini sering kali memerlukan perancangan algoritma baru menggunakan sifat geometris unik dari kelompok lingkaran.
Dalam grup lingkaran, Anda dapat membuat fungsi tangen yang bersinggungan dengan suatu titik tertentu (P_x, P_y), tetapi fungsi ini akan memiliki multiplisitas 2 melalui titik tersebut, yaitu polinomial menjadi kelipatan A dari fungsi linier yang harus memenuhi kondisi yang lebih ketat daripada hanya menjadi nol pada saat itu. Oleh karena itu, Anda tidak bisa hanya membuktikan hasil evaluasi pada satu titik saja. Jadi bagaimana kita menghadapinya?
Kami harus menerima tantangan ini dan membuktikannya dengan mengevaluasi pada dua titik, sehingga menambah titik tiruan yang tidak perlu kami fokuskan.
Fungsi garis: ax + by + c. Jika Anda mengubahnya menjadi persamaan, memaksanya menjadi 0, maka Anda mungkin mengenalinya sebagai garis yang disebut bentuk standar dalam matematika sekolah menengah.
Jika kita mempunyai polinomial P yang sama dengan y_1 di x_1 dan y_2 di x_2, kita dapat memilih fungsi interpolasi L yang sama dengan y_1 di x_1 dan y_2 di x_2. Hal ini dapat dinyatakan secara sederhana sebagai L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1.
Lalu kita buktikan bahwa P sama dengan y_1 di x_1 dan y_2 di x_2 dengan mengurangkan L (membuat P - L nol di kedua titik) dan dengan L (yaitu fungsi linier antara x_2 - x_1) Bagi dengan L untuk membuktikan bahwa hasil bagi Q adalah a polinomial.
Polinomial yang hilang
Dalam STARK, persamaan polinomial yang ingin Anda buktikan biasanya terlihat seperti C (P (x), P ({next}(x))) = Z (x) ⋅ H (x) , dengan Z (x) adalah A polinomial sama dengan nol di seluruh domain evaluasi asli. Dalam STARK biasa, fungsi ini adalah x^n - 1. Dalam STARK melingkar, fungsi yang sesuai adalah:
Z_1 (x,y) = kamu
Z_2 (x,y) = x
Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1
Perhatikan bahwa Anda dapat memperoleh polinomial hilang dari fungsi lipat: dalam STARK biasa Anda menggunakan kembali x → x^2 , sedangkan dalam STARK melingkar Anda menggunakan kembali x → 2x^2 - 1 . Namun untuk ronde pertama, Anda melakukannya secara berbeda karena ronde pertama spesial.
Urutan bit terbalik
Dalam STARK, polinomial biasanya dievaluasi bukan dalam urutan "alami" (misalnya P (1), P (ω), P (ω2),…, P (ωn−1)), tetapi dalam apa yang saya sebut kebalikannya. urutan bit terbalik:
P (\omega^{\frac {3n}{8}})
Jika kita menetapkan n=16 dan hanya fokus pada pangkat ω mana yang kita evaluasi, daftarnya akan terlihat seperti ini:
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Penyortiran ini memiliki properti kunci yaitu nilai-nilai yang dikelompokkan bersama di awal proses evaluasi FRI menjadi berdekatan dalam penyortiran. Misalnya langkah pertama grup FRI x dan -x. Dalam kasus n = 16, ω^8 = -1, yang berarti P (ω^i) ) dan ( P (-ω^i) = P (ω^{i+8}) \). Seperti yang bisa kita lihat, ini adalah pasangan yang bersebelahan. Langkah kedua grup FRI P (ω^i) , P (ω^{i+4}) , P (ω^{i+8}) dan P (ω^{i+12}). Inilah yang kita lihat dalam kelompok beranggotakan empat orang, dan seterusnya. Melakukan hal ini membuat FRI lebih hemat ruang, karena memungkinkan Anda memberikan bukti Merkle untuk nilai yang dijumlahkan (atau, jika Anda melipat k putaran sekaligus, semua nilai 2^k).
Pada STARK lingkaran, struktur lipatannya sedikit berbeda: pada langkah pertama, kita pasangkan (x, y) dengan (x, -y); pada langkah kedua, kita pasangkan x dengan -x; dengan q, dan pilih p dan q sehingga Q^i (p) = -Q^i (q), di mana Q^i adalah pemetaan yang mengulangi x → 2x^2-1 i kali. Jika kita memikirkan titik-titik berdasarkan posisinya pada lingkaran, maka pada setiap langkahnya terlihat seperti titik pertama berpasangan dengan titik terakhir, titik kedua dengan titik kedua hingga terakhir, dan seterusnya.
Untuk menyesuaikan urutan bit terbalik agar mencerminkan struktur pelipatan ini, kita perlu membalik setiap bit kecuali bit terakhir. Kami menyimpan bagian terakhir dan menggunakannya untuk memutuskan apakah akan membalik bagian lainnya.
Lipatan ukuran 16 dalam urutan bit terbalik adalah sebagai berikut:
{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
Jika diperhatikan lingkaran pada bagian sebelumnya, terlihat bahwa titik 0, 15, 8, dan 7 (berlawanan arah jarum jam dari kanan) adalah (x, y), (x, -y), (-x, - y) dan (-x, y), itulah yang kita butuhkan.
efisiensi
Dalam Circle STARK (dan STARK prime 31-bit secara umum), protokol ini sangat efisien. Perhitungan yang dibuktikan dalam Circle STARK biasanya melibatkan beberapa jenis perhitungan:
1. Aritmatika asli: digunakan untuk logika bisnis, seperti berhitung.
2. Aritmatika asli: digunakan dalam kriptografi, seperti fungsi hash seperti Poseidon.
3. Parameter pencarian: Metode penghitungan umum dan efisien yang mengimplementasikan berbagai penghitungan dengan membaca nilai dari tabel.
Ukuran utama efisiensi adalah apakah Anda memanfaatkan sepenuhnya seluruh ruang untuk melakukan pekerjaan berguna dalam jejak komputasi, atau apakah Anda menyisakan banyak ruang kosong. Dalam SNARK untuk bidang yang besar, seringkali terdapat banyak ruang kosong: logika bisnis dan tabel pencarian sering kali melibatkan perhitungan pada angka-angka kecil (angka-angka ini cenderung kurang dari N, dimana N adalah jumlah total langkah dalam perhitungan, jadi dalam berlatih kurang dari 2^{25 }), namun Anda tetap harus membayar biaya penggunaan bidang berukuran 2^{256} bit. Di sini, ukuran bidangnya adalah 2^{31}, sehingga ruang yang terbuang tidak terlalu besar. Hash dengan kompleksitas aritmatika rendah yang dirancang untuk SNARK (seperti Poseidon) memanfaatkan sepenuhnya setiap bit dari setiap angka dalam jejak di bidang apa pun.
Binius adalah solusi yang lebih baik daripada Circle STARK karena memungkinkan Anda mencampur bidang dengan ukuran berbeda, sehingga menghasilkan pengepakan bit yang lebih efisien. Binius juga menyediakan opsi untuk melakukan penambahan 32-bit tanpa biaya tambahan tabel pencarian. Namun, keuntungan ini (menurut saya) harus mengorbankan konsep yang lebih kompleks, sedangkan Circle STARK (dan STARK berbasis BabyBear biasa) secara konseptual jauh lebih sederhana.
Kesimpulan: Pendapat Saya tentang Circle STARKs
Circle STARK bagi pengembang tidak lebih rumit daripada STARK. Dalam proses implementasinya, ketiga hal tersebut di atas pada dasarnya merupakan perbedaan dengan FRI konvensional. Meskipun matematika di balik polinomial yang dijalankan Circle FRI sangat kompleks, dan memerlukan waktu untuk memahami dan mengapresiasi matematika tersebut, kompleksitas ini sebenarnya sangat tersembunyi sehingga tidak dirasakan langsung oleh pengembang.
Memahami Circle FRI dan Circle FFT juga dapat menjadi pintu gerbang untuk memahami FFT khusus lainnya: terutama FFT domain biner, seperti yang digunakan oleh Binius dan sebelumnya LibSTARK, tetapi juga beberapa konstruksi yang lebih kompleks, seperti FFT kurva elips, FFT ini Menggunakan sedikit Pemetaan -ke-banyak dapat dikombinasikan dengan baik dengan operasi titik kurva elips.
Dikombinasikan dengan Mersenne31, BabyBear, dan teknologi domain biner seperti Binius, kami merasa seperti mendekati batas efisiensi lapisan dasar STARK. Pada titik ini, saya memperkirakan arah optimasi STARK akan fokus pada poin-poin berikut:
Aritmetisasi fungsi hash, tanda tangan, dll. untuk memaksimalkan efisiensi: Optimalkan primitif kriptografi dasar seperti fungsi hash dan tanda tangan digital ke dalam bentuk yang paling efisien sehingga dapat mencapai kinerja optimal saat digunakan dalam bukti STARK. Ini berarti optimasi khusus untuk primitif ini guna mengurangi upaya komputasi dan meningkatkan efisiensi.
Konstruksi rekursif untuk memungkinkan lebih banyak paralelisasi: Konstruksi rekursif mengacu pada penerapan proses bukti STARK secara rekursif ke tingkat yang berbeda, sehingga meningkatkan kemampuan pemrosesan paralel. Dengan cara ini, sumber daya komputasi dapat digunakan lebih efisien dan proses pembuktian dapat dipercepat.
Aritmetisasi mesin virtual untuk meningkatkan pengalaman pengembang: Aritmetisasi mesin virtual memungkinkan pengembang membuat dan menjalankan tugas komputasi dengan lebih efisien dan sederhana. Hal ini termasuk mengoptimalkan mesin virtual untuk digunakan dalam bukti STARK dan meningkatkan pengalaman pengembang saat membuat dan menguji kontrak pintar atau tugas komputasi lainnya.