Dalam beberapa tahun terakhir, tren desain protokol STARKs telah beralih ke penggunaan bidang yang lebih kecil. Implementasi awal STARKs 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 di laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan tantangan dalam mengembangkan ZK-EVM yang efisien.
Artikel ini akan membahas cara kerja teknologi ini, dengan perhatian khusus pada solusi Circle STARKs yang kompatibel dengan bidang Mersenne31.
Masalah Umum Menggunakan Bidang Kecil
Saat membuat bukti berbasis hash, teknik penting adalah dengan memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial pada titik acak. Ini sangat menyederhanakan proses pembuktian.
Untuk mencegah serangan, kita perlu memilih titik acak setelah penyerang menyediakan polinomial. Dalam bidang besar, kita dapat dengan mudah memilih angka acak 256 bit. Namun, dalam bidang kecil, jumlah nilai yang dapat dipilih terlalu sedikit, sehingga mudah dieksploitasi oleh penyerang.
Ada dua solusi:
Melakukan pemeriksaan acak berkali-kali
Kolom tambahan
Pemeriksaan berulang sederhana dan efektif, tetapi efisiensinya rendah. Bidang yang diperluas mirip dengan plural, memungkinkan operasi yang lebih kompleks dilakukan pada bidang terbatas. Ini meningkatkan keamanan, sambil mempertahankan efisiensi bidang kecil.
Circle FRI
Kecerdikan Circle STARKs terletak pada, dengan diberikan bilangan prima p, dapat ditemukan grup berukuran p yang memiliki sifat dua-ke-satu yang serupa. Grup ini terdiri dari titik-titik yang memenuhi kondisi tertentu, seperti himpunan titik di mana x^2 mod p sama dengan nilai tertentu.
Titik-titik ini mengikuti suatu pola penjumlahan:
(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
Bentuk ganda adalah:
2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI mengonvergensikan semua titik ke satu garis lurus, lalu melakukan kombinasi linier acak, menghasilkan 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 yang berlawanan di lingkaran menjadi koordinat x dari titik yang dikalikan.
FFT Lingkaran
Grup Circle juga mendukung FFT, cara konstruksinya mirip dengan FRI. Satu perbedaan kunci adalah, Circle FFT tidak memproses polinomial dalam arti ketat, melainkan ruang Riemann-Roch.
Sebagai pengembang, hal ini hampir dapat diabaikan. STARKs hanya perlu menyimpan polinomial sebagai kumpulan nilai evaluasi. Satu-satunya tempat yang memerlukan FFT adalah untuk melakukan perpanjangan tingkat rendah.
Operasi Bisnis
Dalam STARK, operasi yang umum dilakukan adalah melakukan perhitungan modulus pada titik tertentu. Dalam grup lingkaran, karena tidak ada fungsi linier pada satu titik, diperlukan teknik yang berbeda.
Kita harus melakukan evaluasi pada dua titik untuk membuktikan, sehingga menambahkan satu titik virtual yang tidak perlu diperhatikan.
Polinomial Hilang
Dalam lingkaran STARK, fungsi polinomial yang menghilang yang sesuai adalah:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Urutan Balik
Circle STARKs perlu mengubah urutan bit terbalik untuk mencerminkan struktur lipatnya. Kita perlu membalik setiap bit kecuali bit terakhir, menggunakan bit terakhir untuk menentukan apakah akan membalik bit lainnya.
Efisiensi
Circle STARKs sangat efisien. Sebuah perhitungan yang telah dibuktikan biasanya melibatkan:
Aritmetika asli untuk logika bisnis
Aritmatika asli untuk enkripsi
Temukan parameter
Kunci efisiensi adalah memanfaatkan ruang dalam pelacakan komputasi dengan baik. Circle STARKs membuang lebih sedikit ruang dalam bidang berukuran 2^31.
Kesimpulan
Circle STARKs tidak lebih rumit bagi pengembang dibandingkan STARKs konvensional. Meskipun matematika di baliknya sangat rumit, kompleksitas ini disembunyikan dengan baik.
Dengan menggabungkan teknologi seperti Mersenne31, BabyBear, dan Binius, kami semakin mendekati batas efisiensi lapisan dasar STARKs. Arah optimasi di masa depan mungkin termasuk:
Memaksimalkan efisiensi fungsi hash dan primitif lainnya
Konstruksi rekursif untuk meningkatkan paralelisme
Mesin Virtual Aritmatik 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.
Circle STARKs: Teknologi terobosan untuk pembuktian efisien dengan bidang kecil
Menjelajahi Circle STARKs
Dalam beberapa tahun terakhir, tren desain protokol STARKs telah beralih ke penggunaan bidang yang lebih kecil. Implementasi awal STARKs 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 di laptop M3. Ini berarti selama kita mempercayai Poseidon2 sebagai fungsi hash, kita dapat menyelesaikan tantangan dalam mengembangkan ZK-EVM yang efisien.
Artikel ini akan membahas cara kerja teknologi ini, dengan perhatian khusus pada solusi Circle STARKs yang kompatibel dengan bidang Mersenne31.
Masalah Umum Menggunakan Bidang Kecil
Saat membuat bukti berbasis hash, teknik penting adalah dengan memverifikasi sifat polinomial secara tidak langsung melalui evaluasi polinomial pada titik acak. Ini sangat menyederhanakan proses pembuktian.
Untuk mencegah serangan, kita perlu memilih titik acak setelah penyerang menyediakan polinomial. Dalam bidang besar, kita dapat dengan mudah memilih angka acak 256 bit. Namun, dalam bidang kecil, jumlah nilai yang dapat dipilih terlalu sedikit, sehingga mudah dieksploitasi oleh penyerang.
Ada dua solusi:
Pemeriksaan berulang sederhana dan efektif, tetapi efisiensinya rendah. Bidang yang diperluas mirip dengan plural, memungkinkan operasi yang lebih kompleks dilakukan pada bidang terbatas. Ini meningkatkan keamanan, sambil mempertahankan efisiensi bidang kecil.
Circle FRI
Kecerdikan Circle STARKs terletak pada, dengan diberikan bilangan prima p, dapat ditemukan grup berukuran p yang memiliki sifat dua-ke-satu yang serupa. Grup ini terdiri dari titik-titik yang memenuhi kondisi tertentu, seperti himpunan titik di mana x^2 mod p sama dengan nilai tertentu.
Titik-titik ini mengikuti suatu pola penjumlahan: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
Bentuk ganda adalah: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI mengonvergensikan semua titik ke satu garis lurus, lalu melakukan kombinasi linier acak, menghasilkan 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 yang berlawanan di lingkaran menjadi koordinat x dari titik yang dikalikan.
FFT Lingkaran
Grup Circle juga mendukung FFT, cara konstruksinya mirip dengan FRI. Satu perbedaan kunci adalah, Circle FFT tidak memproses polinomial dalam arti ketat, melainkan ruang Riemann-Roch.
Sebagai pengembang, hal ini hampir dapat diabaikan. STARKs hanya perlu menyimpan polinomial sebagai kumpulan nilai evaluasi. Satu-satunya tempat yang memerlukan FFT adalah untuk melakukan perpanjangan tingkat rendah.
Operasi Bisnis
Dalam STARK, operasi yang umum dilakukan adalah melakukan perhitungan modulus pada titik tertentu. Dalam grup lingkaran, karena tidak ada fungsi linier pada satu titik, diperlukan teknik yang berbeda.
Kita harus melakukan evaluasi pada dua titik untuk membuktikan, sehingga menambahkan satu titik virtual yang tidak perlu diperhatikan.
Polinomial Hilang
Dalam lingkaran STARK, fungsi polinomial yang menghilang yang sesuai adalah:
Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Urutan Balik
Circle STARKs perlu mengubah urutan bit terbalik untuk mencerminkan struktur lipatnya. Kita perlu membalik setiap bit kecuali bit terakhir, menggunakan bit terakhir untuk menentukan apakah akan membalik bit lainnya.
Efisiensi
Circle STARKs sangat efisien. Sebuah perhitungan yang telah dibuktikan biasanya melibatkan:
Kunci efisiensi adalah memanfaatkan ruang dalam pelacakan komputasi dengan baik. Circle STARKs membuang lebih sedikit ruang dalam bidang berukuran 2^31.
Kesimpulan
Circle STARKs tidak lebih rumit bagi pengembang dibandingkan STARKs konvensional. Meskipun matematika di baliknya sangat rumit, kompleksitas ini disembunyikan dengan baik.
Dengan menggabungkan teknologi seperti Mersenne31, BabyBear, dan Binius, kami semakin mendekati batas efisiensi lapisan dasar STARKs. Arah optimasi di masa depan mungkin termasuk: