Dalam beberapa tahun terakhir, tren desain protokol STARKs adalah beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs 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 nilai hash Poseidon2 per detik pada laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, masalah ZK-EVM yang efisien dapat diselesaikan.
Artikel ini akan membahas cara kerja teknologi ini, dengan fokus khusus pada solusi Circle STARKs yang kompatibel dengan bidang Mersenne31.
Pertanyaan Umum tentang Penggunaan Field Kecil
Saat membuat bukti berbasis hash, sebuah teknik penting adalah memvalidasi 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. Ini sangat sederhana dalam bidang 256-bit, tetapi di bidang kecil, nilai acak yang dapat dipilih terlalu sedikit, sehingga mudah untuk dipecahkan oleh penyerang melalui brute force.
Ada dua solusi:
Lakukan beberapa pemeriksaan acak
Field Ekstensi
Pemeriksaan acak berkali-kali sederhana dan efektif, tetapi efisiensinya rendah. Bidang yang diperluas mirip dengan jamak, dapat melakukan perhitungan yang lebih kompleks dalam domain terbatas.
FRI Reguler
Langkah pertama dari protokol FRI adalah mengubah masalah komputasi menjadi persamaan polinomial. Kemudian membuktikan bahwa solusi polinomial yang diajukan benar-benar memenuhi persamaan dan derajatnya tidak melebihi yang diminta.
FRI memverifikasi dengan menyederhanakan masalah membuktikan derajat polinomial menjadi d menjadi masalah membuktikan derajat d/2. Proses ini dapat diulang beberapa kali, setiap kali menyederhanakan masalah setengah.
Kunci dari FRI adalah menggunakan pemetaan satu-ke-dua untuk mengurangi ukuran dataset menjadi setengah. Pemetaan ini perlu dapat diterapkan berulang kali, hingga akhirnya hanya tersisa satu nilai.
Circle FRI
Keunggulan Circle STARKs terletak pada fakta bahwa, untuk bilangan prima p, dapat ditemukan grup berukuran p yang memiliki sifat satu-ke-dua yang serupa. Grup ini terdiri dari titik-titik yang memenuhi kondisi tertentu.
Poin-poin ini mengikuti suatu pola penjumlahan, mirip dengan fungsi trigonometri atau perkalian bilangan kompleks.
Setelah putaran kedua, pemetaan berubah. Setiap x mewakili dua titik: (x,y) dan (x,-y). (x → 2x^2 - 1) adalah hukum penggandaan titik.
FFT Lingkaran
Circle group juga mendukung FFT, cara konstruksinya mirip dengan FRI. Namun objek yang diproses oleh Circle FFT bukanlah polinomial dalam arti ketat, melainkan ruang Riemann-Roch.
Sebagai pengembang, Anda hampir dapat mengabaikan detail ini. Cukup simpan polinomial sebagai nilai evaluasi, dan gunakan FFT ketika perlu melakukan skala rendah.
Pembagian
Dalam STARK di grup circle, karena tidak ada fungsi linier titik tunggal, perlu menggunakan teknik berbeda untuk menggantikan operasi komersial tradisional.
Kami membuktikan dengan mengevaluasi di dua titik untuk menambahkan satu titik virtual.
Polinomial yang menghilang
Dalam STARK bulat, 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
Urut ulang bit
Dalam STARKs, evaluasi polinomial biasanya diurutkan dalam urutan terbalik. Dalam Circle STARKs, perlu mengubah urutan ini untuk mencerminkan struktur lipatan khususnya.
Efisiensi
Circle STARKs sangat efisien. Kuncinya adalah memanfaatkan ruang dalam pelacakan komputasi untuk melakukan pekerjaan yang berguna, tanpa menyisakan banyak ruang kosong.
Dibandingkan dengan Binius, Circle STARKs secara konsep lebih sederhana, tetapi efisiensinya sedikit lebih rendah.
Kesimpulan
Circle STARKs tidak lebih rumit bagi pengembang dibandingkan dengan STARKs biasa. Memahami Circle FRI dan FFTs membantu dalam memahami FFTs khusus lainnya.
Masa depan optimasi STARK mungkin akan terfokus pada:
Memaksimalkan efisiensi fungsi hash dan dasar-dasar kriptografi lainnya
Konstruksi rekursif untuk meningkatkan paralelisasi
Mesin virtual aritmetika untuk meningkatkan pengalaman pengembangan
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.
11 Suka
Hadiah
11
6
Posting ulang
Bagikan
Komentar
0/400
HalfPositionRunner
· 08-10 22:19
620k per detik bull
Lihat AsliBalas0
CountdownToBroke
· 08-10 22:19
Kecepatan ini bull banget pump penuh
Lihat AsliBalas0
LiquidityWitch
· 08-10 22:17
Hah, memang tidak salah lagi Stark yang tua, memang begitu hebat.
Lihat AsliBalas0
NotAFinancialAdvice
· 08-10 22:16
Sama sekali tidak mengerti, hanya mengerti yang dikatakan di belakang dengan cepat.
Lihat AsliBalas0
HashBrownies
· 08-10 22:15
Kecil berarti cepat, seluruh lingkaran enkripsi harus mempercepat.
Lihat AsliBalas0
BoredWatcher
· 08-10 22:00
Setelah bermain dengan L2 selama beberapa tahun, saya masih belum mengerti teknologi ini.
Circle STARKs: Skema baru untuk meningkatkan efisiensi ZK proof dengan field kecil
Eksplorasi Circle STARKs
Dalam beberapa tahun terakhir, tren desain protokol STARKs adalah beralih ke penggunaan bidang yang lebih kecil. Implementasi STARKs 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 nilai hash Poseidon2 per detik pada laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, masalah ZK-EVM yang efisien dapat diselesaikan.
Artikel ini akan membahas cara kerja teknologi ini, dengan fokus khusus pada solusi Circle STARKs yang kompatibel dengan bidang Mersenne31.
Pertanyaan Umum tentang Penggunaan Field Kecil
Saat membuat bukti berbasis hash, sebuah teknik penting adalah memvalidasi 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. Ini sangat sederhana dalam bidang 256-bit, tetapi di bidang kecil, nilai acak yang dapat dipilih terlalu sedikit, sehingga mudah untuk dipecahkan oleh penyerang melalui brute force.
Ada dua solusi:
Pemeriksaan acak berkali-kali sederhana dan efektif, tetapi efisiensinya rendah. Bidang yang diperluas mirip dengan jamak, dapat melakukan perhitungan yang lebih kompleks dalam domain terbatas.
FRI Reguler
Langkah pertama dari protokol FRI adalah mengubah masalah komputasi menjadi persamaan polinomial. Kemudian membuktikan bahwa solusi polinomial yang diajukan benar-benar memenuhi persamaan dan derajatnya tidak melebihi yang diminta.
FRI memverifikasi dengan menyederhanakan masalah membuktikan derajat polinomial menjadi d menjadi masalah membuktikan derajat d/2. Proses ini dapat diulang beberapa kali, setiap kali menyederhanakan masalah setengah.
Kunci dari FRI adalah menggunakan pemetaan satu-ke-dua untuk mengurangi ukuran dataset menjadi setengah. Pemetaan ini perlu dapat diterapkan berulang kali, hingga akhirnya hanya tersisa satu nilai.
Circle FRI
Keunggulan Circle STARKs terletak pada fakta bahwa, untuk bilangan prima p, dapat ditemukan grup berukuran p yang memiliki sifat satu-ke-dua yang serupa. Grup ini terdiri dari titik-titik yang memenuhi kondisi tertentu.
Poin-poin ini mengikuti suatu pola penjumlahan, mirip dengan fungsi trigonometri atau perkalian bilangan kompleks.
Setelah putaran kedua, pemetaan berubah. Setiap x mewakili dua titik: (x,y) dan (x,-y). (x → 2x^2 - 1) adalah hukum penggandaan titik.
FFT Lingkaran
Circle group juga mendukung FFT, cara konstruksinya mirip dengan FRI. Namun objek yang diproses oleh Circle FFT bukanlah polinomial dalam arti ketat, melainkan ruang Riemann-Roch.
Sebagai pengembang, Anda hampir dapat mengabaikan detail ini. Cukup simpan polinomial sebagai nilai evaluasi, dan gunakan FFT ketika perlu melakukan skala rendah.
Pembagian
Dalam STARK di grup circle, karena tidak ada fungsi linier titik tunggal, perlu menggunakan teknik berbeda untuk menggantikan operasi komersial tradisional.
Kami membuktikan dengan mengevaluasi di dua titik untuk menambahkan satu titik virtual.
Polinomial yang menghilang
Dalam STARK bulat, 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
Urut ulang bit
Dalam STARKs, evaluasi polinomial biasanya diurutkan dalam urutan terbalik. Dalam Circle STARKs, perlu mengubah urutan ini untuk mencerminkan struktur lipatan khususnya.
Efisiensi
Circle STARKs sangat efisien. Kuncinya adalah memanfaatkan ruang dalam pelacakan komputasi untuk melakukan pekerjaan yang berguna, tanpa menyisakan banyak ruang kosong.
Dibandingkan dengan Binius, Circle STARKs secara konsep lebih sederhana, tetapi efisiensinya sedikit lebih rendah.
Kesimpulan
Circle STARKs tidak lebih rumit bagi pengembang dibandingkan dengan STARKs biasa. Memahami Circle FRI dan FFTs membantu dalam memahami FFTs khusus lainnya.
Masa depan optimasi STARK mungkin akan terfokus pada: