Dalam beberapa tahun terakhir, tren desain protokol STARKs beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs yang paling awal menggunakan bidang 256-bit, tetapi desain ini kurang efisien. Untuk mengatasi masalah ini, STARKs mulai menggunakan bidang yang lebih kecil, seperti Goldilocks, Mersenne31, dan BabyBear.
Perubahan ini 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 mengatasi tantangan ZK-EVM yang efisien.
Artikel ini akan membahas cara kerja teknologi ini, dengan fokus khusus pada solusi Circle STARKs. Circle STARKs memiliki sifat unik yang kompatibel dengan bidang Mersenne31.
Pertanyaan Umum tentang Penggunaan Bidang Kecil
Saat membuat bukti berbasis hash, sebuah teknik penting adalah dengan memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial di titik acak. Ini sangat menyederhanakan proses pembuktian.
Untuk mencegah serangan, kita perlu memilih titik acak setelah penyerang memberikan polinomial. Dalam STARKs dengan bidang yang lebih kecil, titik acak yang tersedia hanya sekitar 2 miliar, yang tidak aman bagi penyerang yang bertekad.
Ada dua solusi:
Melakukan pemeriksaan acak beberapa kali
Field tambahan
Pemeriksaan berulang kali sederhana dan efektif, tetapi ada masalah efisiensi. Bidang ekstensi mirip dengan bilangan kompleks, tetapi berdasarkan bidang terbatas. Ini memungkinkan kita untuk beroperasi di bidang yang lebih besar, meningkatkan keamanan.
FRI Reguler
Protokol FRI memverifikasi dengan menyederhanakan masalah untuk membuktikan derajat polinomial menjadi d menjadi masalah untuk membuktikan derajat d/2. Proses ini dapat diulang beberapa kali, setiap kali menyederhanakan masalah setengah.
FRI menggunakan pemetaan dua-ke-satu untuk mengurangi ukuran kumpulan data setengah. Pemetaan ini dapat diulang, memungkinkan kita untuk terus mengurangi ukuran kumpulan data.
Circle FRI
Keunggulan Circle STARKs terletak pada fakta bahwa, dengan diberikan bilangan prima p, kita dapat menemukan grup berukuran p yang memiliki sifat dua-ke-satu yang serupa. Grup ini terdiri dari titik-titik yang memenuhi kondisi tertentu.
Mulai dari putaran kedua, pemetaan berubah:
f_0(2x^2-1) = (F(x) + F(-x))/2
Pemetaan ini mengurangi ukuran kumpulan setiap kali menjadi setengah. 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. Namun, objek yang diproses oleh Circle FFT bukanlah polinomial yang ketat, melainkan ruang Riemann-Roch.
Sebagai pengembang, hampir bisa diabaikan. STARKs hanya meminta untuk menyimpan polinomial sebagai nilai evaluasi. Satu-satunya tempat yang memerlukan FFT adalah untuk melakukan perluasan derajat rendah.
Quotienting
Dalam STARK grup circle, karena tidak ada fungsi linier yang dapat dievaluasi melalui titik tunggal, diperlukan teknik berbeda untuk menggantikan operasi komersial tradisional. Biasanya perlu dievaluasi di dua titik untuk membuktikan.
Polinomial yang menghilang
Dalam STARK berbentuk lingkaran, polinomial yang menghilang adalah:
Z_1(x,y) = y
Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1
Membalik urutan bit
Circle STARKs perlu menyesuaikan urutan bit terbalik untuk mencerminkan struktur lipatan khususnya. Setiap bit kecuali bit terakhir harus dibalik, bit terakhir digunakan untuk menentukan apakah bit lainnya dibalik.
Efisiensi
Circle STARKs sangat efisien. Perhitungan biasanya melibatkan:
Aritmatika asli untuk logika bisnis
Aritmatika asli untuk enkripsi
Mencari parameter
Kuncinya adalah memanfaatkan ruang dalam pelacakan komputasi secara maksimal. Bidang berukuran 2^31 mengurangi ruang yang terbuang.
Kesimpulan
Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan dengan STARKs biasa. Meskipun matematika di baliknya rumit, namun bagi pengembang pada dasarnya tersembunyi.
Memahami Circle FRI dan FFT dapat menjadi cara untuk memahami FFT khusus lainnya.
Dengan menggabungkan teknologi Mersenne31, BabyBear, dan domain biner, kami semakin mendekati batas efisiensi lapisan dasar STARKs. Arah optimasi di masa depan mungkin termasuk:
Melakukan aritmetisasi untuk memaksimalkan efisiensi fungsi hash dan lainnya
Melakukan konstruksi rekursif untuk mengaktifkan lebih banyak paralelisasi
Mesin virtual aritmetika untuk meningkatkan pengalaman pengembang
Lihat Asli
Halaman ini mungkin berisi konten pihak ketiga, yang disediakan untuk tujuan informasi saja (bukan pernyataan/jaminan) dan tidak boleh dianggap sebagai dukungan terhadap pandangannya oleh Gate, atau sebagai nasihat keuangan atau profesional. Lihat Penafian untuk detailnya.
20 Suka
Hadiah
20
6
Bagikan
Komentar
0/400
MeltdownSurvivalist
· 07-20 16:08
Teknologi geek sedang membuat sesuatu yang baru lagi.
Lihat AsliBalas0
ApeWithNoChain
· 07-20 13:55
Kamu benar, tepuk tangan dengan keras
Lihat AsliBalas0
NFTArchaeologis
· 07-18 11:38
Keindahan tekstur digital dari zk-SNARKs
Lihat AsliBalas0
PriceOracleFairy
· 07-17 21:48
akhirnya ada alpha nyata tentang teknologi zk
Lihat AsliBalas0
CryptoAdventurer
· 07-17 21:40
Sekali lagi belajar sesuatu yang baru, tetapi pada akhirnya suckers tetap suckers.
Circle STARKs: Solusi baru efisien untuk zk-SNARKs dengan bidang kecil
Menjelajahi Circle STARKs
Dalam beberapa tahun terakhir, tren desain protokol STARKs beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs yang paling awal menggunakan bidang 256-bit, tetapi desain ini kurang efisien. Untuk mengatasi masalah ini, STARKs mulai menggunakan bidang yang lebih kecil, seperti Goldilocks, Mersenne31, dan BabyBear.
Perubahan ini 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 mengatasi tantangan ZK-EVM yang efisien.
Artikel ini akan membahas cara kerja teknologi ini, dengan fokus khusus pada solusi Circle STARKs. Circle STARKs memiliki sifat unik yang kompatibel dengan bidang Mersenne31.
Pertanyaan Umum tentang Penggunaan Bidang Kecil
Saat membuat bukti berbasis hash, sebuah teknik penting adalah dengan memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial di titik acak. Ini sangat menyederhanakan proses pembuktian.
Untuk mencegah serangan, kita perlu memilih titik acak setelah penyerang memberikan polinomial. Dalam STARKs dengan bidang yang lebih kecil, titik acak yang tersedia hanya sekitar 2 miliar, yang tidak aman bagi penyerang yang bertekad.
Ada dua solusi:
Pemeriksaan berulang kali sederhana dan efektif, tetapi ada masalah efisiensi. Bidang ekstensi mirip dengan bilangan kompleks, tetapi berdasarkan bidang terbatas. Ini memungkinkan kita untuk beroperasi di bidang yang lebih besar, meningkatkan keamanan.
FRI Reguler
Protokol FRI memverifikasi dengan menyederhanakan masalah untuk membuktikan derajat polinomial menjadi d menjadi masalah untuk membuktikan derajat d/2. Proses ini dapat diulang beberapa kali, setiap kali menyederhanakan masalah setengah.
FRI menggunakan pemetaan dua-ke-satu untuk mengurangi ukuran kumpulan data setengah. Pemetaan ini dapat diulang, memungkinkan kita untuk terus mengurangi ukuran kumpulan data.
Circle FRI
Keunggulan Circle STARKs terletak pada fakta bahwa, dengan diberikan bilangan prima p, kita dapat menemukan grup berukuran p yang memiliki sifat dua-ke-satu yang serupa. Grup ini terdiri dari titik-titik yang memenuhi kondisi tertentu.
Mulai dari putaran kedua, pemetaan berubah:
f_0(2x^2-1) = (F(x) + F(-x))/2
Pemetaan ini mengurangi ukuran kumpulan setiap kali menjadi setengah. 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. Namun, objek yang diproses oleh Circle FFT bukanlah polinomial yang ketat, melainkan ruang Riemann-Roch.
Sebagai pengembang, hampir bisa diabaikan. STARKs hanya meminta untuk menyimpan polinomial sebagai nilai evaluasi. Satu-satunya tempat yang memerlukan FFT adalah untuk melakukan perluasan derajat rendah.
Quotienting
Dalam STARK grup circle, karena tidak ada fungsi linier yang dapat dievaluasi melalui titik tunggal, diperlukan teknik berbeda untuk menggantikan operasi komersial tradisional. Biasanya perlu dievaluasi di dua titik untuk membuktikan.
Polinomial yang menghilang
Dalam STARK berbentuk lingkaran, polinomial yang menghilang adalah:
Z_1(x,y) = y Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1
Membalik urutan bit
Circle STARKs perlu menyesuaikan urutan bit terbalik untuk mencerminkan struktur lipatan khususnya. Setiap bit kecuali bit terakhir harus dibalik, bit terakhir digunakan untuk menentukan apakah bit lainnya dibalik.
Efisiensi
Circle STARKs sangat efisien. Perhitungan biasanya melibatkan:
Kuncinya adalah memanfaatkan ruang dalam pelacakan komputasi secara maksimal. Bidang berukuran 2^31 mengurangi ruang yang terbuang.
Kesimpulan
Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan dengan STARKs biasa. Meskipun matematika di baliknya rumit, namun bagi pengembang pada dasarnya tersembunyi.
Memahami Circle FRI dan FFT dapat menjadi cara untuk memahami FFT khusus lainnya.
Dengan menggabungkan teknologi Mersenne31, BabyBear, dan domain biner, kami semakin mendekati batas efisiensi lapisan dasar STARKs. Arah optimasi di masa depan mungkin termasuk: