Dalam beberapa tahun terakhir, tren desain protokol STARKs adalah beralih ke penggunaan bidang yang lebih kecil. Implementasi produksi STARKs yang paling awal menggunakan bidang 256-bit, yaitu melakukan operasi modulo pada angka besar. Namun, desain ini memiliki efisiensi yang rendah, dan memproses angka besar akan membuang banyak daya komputasi. Untuk mengatasi masalah ini, STARKs mulai menggunakan bidang yang lebih kecil: pertama Goldilocks, kemudian Mersenne31 dan BabyBear.
Perubahan ini secara signifikan meningkatkan kecepatan pembuktian. Misalnya, Starkware sekarang dapat membuktikan 620.000 hash Poseidon2 per detik di satu laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan tantangan pengembangan ZK-EVM yang efisien. Lalu, bagaimana teknologi ini bekerja? Bagaimana bukti dibangun di bidang kecil? Artikel ini akan membahas detail tersebut, dengan fokus khusus pada Circle STARKs, solusi yang kompatibel dengan bidang Mersenne31.
Masalah Umum Saat Menggunakan Field Kecil
Saat membuat bukti berbasis hash, teknik penting adalah memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial pada titik acak. Ini dapat sangat menyederhanakan proses pembuktian.
Misalnya, anggaplah protokol mengharuskan Anda untuk menghasilkan suatu commitment dari polinomial A, yang memenuhi A^3(x) + x - A(ωx) = x^N. Protokol dapat mengharuskan Anda untuk memilih koordinat acak r dan membuktikan A(r)^3 + r - A(ωr) = r^N. Kemudian, mundur untuk membuktikan A(r) = c, Anda membuktikan Q = (A - c)/(X - r) adalah suatu polinomial.
Untuk mencegah serangan, kita perlu memilih r setelah penyerang memberikan A. Dalam protokol berbasis kurva elips, ini cukup sederhana: kita dapat memilih angka acak 256-bit sebagai r. Namun, dalam STARKs dengan bidang kecil, hanya ada sekitar 2 miliar pilihan r, dan penyerang mungkin bisa memecahkannya melalui pencarian menyeluruh.
Masalah ini memiliki dua solusi:
Melakukan beberapa pemeriksaan acak
Field Ekstensi
Pemeriksaan acak berkali-kali sederhana dan efektif, tetapi mungkin ada masalah efisiensi. Domain ekstensi mirip dengan bilangan kompleks, tetapi berdasarkan domain terbatas. Kami memperkenalkan nilai baru α, dengan menyatakan α^2 = suatu nilai. Dengan cara ini, sebuah struktur matematika baru dibuat yang dapat melakukan perhitungan yang lebih kompleks di atas domain terbatas.
Dengan memperluas domain, kami memiliki cukup banyak nilai untuk dipilih yang memenuhi kebutuhan keamanan. Sebagian besar operasi matematis masih dilakukan pada bidang dasar, hanya menggunakan bidang yang lebih besar saat diperlukan untuk meningkatkan keamanan.
Regular FRI
FRI (Fast Reed-Solomon Interactive) adalah langkah penting dalam membangun SNARK atau STARK. Ini menyederhanakan proses verifikasi dengan mengubah masalah pembuktian polinomial derajat d menjadi masalah pembuktian derajat d/2. Proses ini dapat diulang beberapa kali, dengan setiap kali menyederhanakan masalah setengah.
Prinsip kerja FRI adalah mengulangi proses penyederhanaan. Dimulai dari membuktikan derajat polinomial adalah d, melalui serangkaian langkah, akhirnya membuktikan derajatnya adalah d/2. Setiap kali disederhanakan, derajat polinomial yang dihasilkan secara bertahap berkurang. Jika output pada suatu tahap tidak sesuai harapan, maka putaran pemeriksaan tersebut akan gagal.
Untuk mencapai pengurangan bertahap dari domain, digunakan pemetaan dua-ke-satu. Pemetaan ini memungkinkan ukuran dataset menjadi setengah, sambil mempertahankan atribut yang sama. Operasi ini dapat dibayangkan sebagai proses merentangkan segmen di keliling menjadi dua putaran di sepanjang keliling.
Agar teknologi pemetaan efektif, ukuran subkelompok perkalian asli perlu memiliki faktor besar dari 2. Modulus BabyBear memungkinkan subkelompok perkalian maksimumnya mencakup semua nilai non-nol, sangat cocok untuk teknologi ini. Ukuran subkelompok perkalian Mersenne31 hanya memiliki satu faktor 2, membatasi jangkauan aplikasinya.
Domain Mersenne31 sangat cocok untuk melakukan operasi aritmatika pada CPU/GPU 32-bit, sekitar 1,3 kali lebih cepat dibandingkan domain BabyBear. Jika FRI dapat diterapkan di domain Mersenne31, akan secara signifikan meningkatkan efisiensi komputasi.
Circle FRI
Keunggulan Circle STARKs terletak pada kemampuannya untuk, dengan diberikan bilangan prima p, menemukan kelompok berukuran p yang memiliki karakteristik dua-ke-satu yang serupa. Kelompok ini terdiri dari kumpulan titik yang memenuhi kondisi tertentu, seperti himpunan titik di mana x^2 mod p sama dengan nilai tertentu.
Poin-poin ini mengikuti aturan penjumlahan:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
Bentuk ganda adalah: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI pertama-tama mengumpulkan semua titik ke dalam satu garis lurus, kemudian melakukan kombinasi linier acak untuk mendapatkan polinomial satu dimensi P(x). Mulai dari putaran kedua, pemetaan berubah menjadi: f0(2x^2-1) = (F(x) + F(-x))/2
Pemetaan ini mengurangi ukuran koleksi setengah setiap kali, mengubah koordinat x dari dua titik berlawanan di lingkaran menjadi koordinat x dari titik yang dikalikan. Ini dapat dilakukan di ruang dua dimensi, tetapi operasi satu dimensi lebih efisien.
FFT Lingkaran
Grup Circle juga mendukung FFT, cara konstruksinya mirip dengan FRI. Objek yang diproses oleh Circle FFT adalah ruang Riemann-Roch, bukan polinomial yang ketat. Koefisien yang dihasilkan oleh Circle FFT adalah dasar yang khusus untuk Circle FFT.
Sebagai pengembang, Anda hampir dapat mengabaikan hal ini sepenuhnya. STARKs hanya perlu menyimpan polinomial sebagai kumpulan nilai evaluasi. Satu-satunya tempat yang membutuhkan FFT adalah untuk melakukan perluasan derajat rendah: diberikan N nilai, menghasilkan k*N nilai pada polinomial yang sama.
Pembagian
Dalam Circle STARKs, karena tidak ada fungsi linier yang dapat diakses melalui titik tunggal, perlu menggunakan teknik yang berbeda untuk menggantikan operasi komutatif tradisional. Kita harus membuktikan dengan mengevaluasi di dua titik dengan menambahkan satu titik virtual.
Jika polinomial P sama dengan y1 di x1, dan sama dengan y2 di x2, kita memilih fungsi interpolasi L, yang sama di kedua titik tersebut. Kemudian buktikan bahwa P-L bernilai nol di kedua titik, dengan membagi L dengan L untuk membuktikan bahwa hasil bagi Q adalah polinomial.
Polinomial yang menghilang
Dalam Circle STARKs, polinomial yang menghilang adalah:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Ini dapat diturunkan dari fungsi lipat: dalam Circle STARKs, gunakan kembali x → 2x^2 - 1. Putaran pertama memerlukan perlakuan khusus.
Pembalikan urutan bit
Circle STARKs menggunakan urutan bit terbalik yang dimodifikasi, membalik setiap bit kecuali bit terakhir, dengan bit terakhir menentukan apakah bit lainnya dibalik. Ini mencerminkan struktur lipatan yang khas dari Circle STARKs.
Efisiensi
Circle STARKs sangat efisien. Perhitungan biasanya melibatkan:
Aritmatika asli: digunakan untuk logika bisnis
Aritmatika Asli: digunakan untuk kriptografi ( seperti hash Poseidon )
Mencari parameter: Melalui tabel untuk mencari nilai untuk melakukan berbagai perhitungan
Circle STARKs memanfaatkan ruang komputasi dengan baik, lebih sedikit membuang. Sedikit lebih rendah dari Binius, tetapi konsepnya lebih sederhana.
Kesimpulan
Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan dengan STARKs konvensional. Memahami Circle FRI dan FFT dapat membantu memahami FFT khusus lainnya. Saat ini, efisiensi lapisan dasar STARKs mendekati batas, arah optimasi di masa depan mungkin termasuk:
Memaksimalkan efisiensi aritmetika dari fungsi hash dan tanda tangan
Konstruksi rekursif untuk meningkatkan paralelisasi
Mesin virtual aritmatika 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.
19 Suka
Hadiah
19
4
Posting ulang
Bagikan
Komentar
0/400
NftBankruptcyClub
· 08-09 22:10
Ukuran huruf lebih kecil malah meningkatkan efisiensi...666
Lihat AsliBalas0
GasWhisperer
· 08-09 22:08
hmm... bidang yang lebih kecil = bukti yang lebih cepat, tetapi bisakah kita mempercayai poseidon2? merasa bingung tentang tradeoff efisiensi/keamanan ini sejujurnya
Lihat AsliBalas0
alpha_leaker
· 08-09 21:58
Stark sedikit menakutkan ya
Lihat AsliBalas0
ChainDetective
· 08-09 21:54
Baru saja mengerti, pada dasarnya itu adalah perhitungan cepat dengan ukuran yang disederhanakan.
Circle STARKs: Eksplorasi dan Terobosan ZK Pembuktian Efisien dengan Bidang Kecil
Menjelajahi Circle STARKs
Dalam beberapa tahun terakhir, tren desain protokol STARKs adalah beralih ke penggunaan bidang yang lebih kecil. Implementasi produksi STARKs yang paling awal menggunakan bidang 256-bit, yaitu melakukan operasi modulo pada angka besar. Namun, desain ini memiliki efisiensi yang rendah, dan memproses angka besar akan membuang banyak daya komputasi. Untuk mengatasi masalah ini, STARKs mulai menggunakan bidang yang lebih kecil: pertama Goldilocks, kemudian Mersenne31 dan BabyBear.
Perubahan ini secara signifikan meningkatkan kecepatan pembuktian. Misalnya, Starkware sekarang dapat membuktikan 620.000 hash Poseidon2 per detik di satu laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan tantangan pengembangan ZK-EVM yang efisien. Lalu, bagaimana teknologi ini bekerja? Bagaimana bukti dibangun di bidang kecil? Artikel ini akan membahas detail tersebut, dengan fokus khusus pada Circle STARKs, solusi yang kompatibel dengan bidang Mersenne31.
Masalah Umum Saat Menggunakan Field Kecil
Saat membuat bukti berbasis hash, teknik penting adalah memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial pada titik acak. Ini dapat sangat menyederhanakan proses pembuktian.
Misalnya, anggaplah protokol mengharuskan Anda untuk menghasilkan suatu commitment dari polinomial A, yang memenuhi A^3(x) + x - A(ωx) = x^N. Protokol dapat mengharuskan Anda untuk memilih koordinat acak r dan membuktikan A(r)^3 + r - A(ωr) = r^N. Kemudian, mundur untuk membuktikan A(r) = c, Anda membuktikan Q = (A - c)/(X - r) adalah suatu polinomial.
Untuk mencegah serangan, kita perlu memilih r setelah penyerang memberikan A. Dalam protokol berbasis kurva elips, ini cukup sederhana: kita dapat memilih angka acak 256-bit sebagai r. Namun, dalam STARKs dengan bidang kecil, hanya ada sekitar 2 miliar pilihan r, dan penyerang mungkin bisa memecahkannya melalui pencarian menyeluruh.
Masalah ini memiliki dua solusi:
Pemeriksaan acak berkali-kali sederhana dan efektif, tetapi mungkin ada masalah efisiensi. Domain ekstensi mirip dengan bilangan kompleks, tetapi berdasarkan domain terbatas. Kami memperkenalkan nilai baru α, dengan menyatakan α^2 = suatu nilai. Dengan cara ini, sebuah struktur matematika baru dibuat yang dapat melakukan perhitungan yang lebih kompleks di atas domain terbatas.
Dengan memperluas domain, kami memiliki cukup banyak nilai untuk dipilih yang memenuhi kebutuhan keamanan. Sebagian besar operasi matematis masih dilakukan pada bidang dasar, hanya menggunakan bidang yang lebih besar saat diperlukan untuk meningkatkan keamanan.
Regular FRI
FRI (Fast Reed-Solomon Interactive) adalah langkah penting dalam membangun SNARK atau STARK. Ini menyederhanakan proses verifikasi dengan mengubah masalah pembuktian polinomial derajat d menjadi masalah pembuktian derajat d/2. Proses ini dapat diulang beberapa kali, dengan setiap kali menyederhanakan masalah setengah.
Prinsip kerja FRI adalah mengulangi proses penyederhanaan. Dimulai dari membuktikan derajat polinomial adalah d, melalui serangkaian langkah, akhirnya membuktikan derajatnya adalah d/2. Setiap kali disederhanakan, derajat polinomial yang dihasilkan secara bertahap berkurang. Jika output pada suatu tahap tidak sesuai harapan, maka putaran pemeriksaan tersebut akan gagal.
Untuk mencapai pengurangan bertahap dari domain, digunakan pemetaan dua-ke-satu. Pemetaan ini memungkinkan ukuran dataset menjadi setengah, sambil mempertahankan atribut yang sama. Operasi ini dapat dibayangkan sebagai proses merentangkan segmen di keliling menjadi dua putaran di sepanjang keliling.
Agar teknologi pemetaan efektif, ukuran subkelompok perkalian asli perlu memiliki faktor besar dari 2. Modulus BabyBear memungkinkan subkelompok perkalian maksimumnya mencakup semua nilai non-nol, sangat cocok untuk teknologi ini. Ukuran subkelompok perkalian Mersenne31 hanya memiliki satu faktor 2, membatasi jangkauan aplikasinya.
Domain Mersenne31 sangat cocok untuk melakukan operasi aritmatika pada CPU/GPU 32-bit, sekitar 1,3 kali lebih cepat dibandingkan domain BabyBear. Jika FRI dapat diterapkan di domain Mersenne31, akan secara signifikan meningkatkan efisiensi komputasi.
Circle FRI
Keunggulan Circle STARKs terletak pada kemampuannya untuk, dengan diberikan bilangan prima p, menemukan kelompok berukuran p yang memiliki karakteristik dua-ke-satu yang serupa. Kelompok ini terdiri dari kumpulan titik yang memenuhi kondisi tertentu, seperti himpunan titik di mana x^2 mod p sama dengan nilai tertentu.
Poin-poin ini mengikuti aturan penjumlahan:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Bentuk ganda adalah: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI pertama-tama mengumpulkan semua titik ke dalam satu garis lurus, kemudian melakukan kombinasi linier acak untuk mendapatkan polinomial satu dimensi P(x). Mulai dari putaran kedua, pemetaan berubah menjadi: f0(2x^2-1) = (F(x) + F(-x))/2
Pemetaan ini mengurangi ukuran koleksi setengah setiap kali, mengubah koordinat x dari dua titik berlawanan di lingkaran menjadi koordinat x dari titik yang dikalikan. Ini dapat dilakukan di ruang dua dimensi, tetapi operasi satu dimensi lebih efisien.
FFT Lingkaran
Grup Circle juga mendukung FFT, cara konstruksinya mirip dengan FRI. Objek yang diproses oleh Circle FFT adalah ruang Riemann-Roch, bukan polinomial yang ketat. Koefisien yang dihasilkan oleh Circle FFT adalah dasar yang khusus untuk Circle FFT.
Sebagai pengembang, Anda hampir dapat mengabaikan hal ini sepenuhnya. STARKs hanya perlu menyimpan polinomial sebagai kumpulan nilai evaluasi. Satu-satunya tempat yang membutuhkan FFT adalah untuk melakukan perluasan derajat rendah: diberikan N nilai, menghasilkan k*N nilai pada polinomial yang sama.
Pembagian
Dalam Circle STARKs, karena tidak ada fungsi linier yang dapat diakses melalui titik tunggal, perlu menggunakan teknik yang berbeda untuk menggantikan operasi komutatif tradisional. Kita harus membuktikan dengan mengevaluasi di dua titik dengan menambahkan satu titik virtual.
Jika polinomial P sama dengan y1 di x1, dan sama dengan y2 di x2, kita memilih fungsi interpolasi L, yang sama di kedua titik tersebut. Kemudian buktikan bahwa P-L bernilai nol di kedua titik, dengan membagi L dengan L untuk membuktikan bahwa hasil bagi Q adalah polinomial.
Polinomial yang menghilang
Dalam Circle STARKs, polinomial yang menghilang adalah: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Ini dapat diturunkan dari fungsi lipat: dalam Circle STARKs, gunakan kembali x → 2x^2 - 1. Putaran pertama memerlukan perlakuan khusus.
Pembalikan urutan bit
Circle STARKs menggunakan urutan bit terbalik yang dimodifikasi, membalik setiap bit kecuali bit terakhir, dengan bit terakhir menentukan apakah bit lainnya dibalik. Ini mencerminkan struktur lipatan yang khas dari Circle STARKs.
Efisiensi
Circle STARKs sangat efisien. Perhitungan biasanya melibatkan:
Circle STARKs memanfaatkan ruang komputasi dengan baik, lebih sedikit membuang. Sedikit lebih rendah dari Binius, tetapi konsepnya lebih sederhana.
Kesimpulan
Circle STARKs tidak lebih kompleks bagi pengembang dibandingkan dengan STARKs konvensional. Memahami Circle FRI dan FFT dapat membantu memahami FFT khusus lainnya. Saat ini, efisiensi lapisan dasar STARKs mendekati batas, arah optimasi di masa depan mungkin termasuk: