Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi
1 Pendahuluan
Salah satu alasan utama ketidak efisienan STARKs adalah sebagian besar nilai dalam program nyata cukup kecil, tetapi untuk memastikan keamanan bukti berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama dari STARKs memiliki lebar kode 252bit, generasi kedua 64bit, dan generasi ketiga 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.
Ketika menggunakan bidang yang lebih kecil, operasi perluasan bidang menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius harus sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan bidang, dan hanya perlu beroperasi dalam bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu menyelami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.
Binius mengusulkan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilainya pada "hyper-cube" (hypercubes) untuk mewakili seluruh jejak perhitungan; kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hyper-cube dapat dipandang sebagai persegi (square), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini meningkatkan efisiensi pengkodean dan kinerja komputasi secara signifikan sambil memastikan keamanan.
2 Analisis Prinsip
Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya:
Aritmatika berbasis menara bidang biner (towers of binary fields)
Mengadaptasi pemeriksaan produk dan permutasi HyperPlonk
Pembuktian pergeseran multilinier yang baru
Versi yang ditingkatkan dari argumen pencarian Lasso
Skema Komitmen Polinomial Lapangan Kecil (Small-Field PCS)
2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields
Bidang biner berbentuk menara adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi yang efisien dan aritmetika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di bidang biner dapat dinyatakan dalam bentuk aljabar yang padat dan mudah diverifikasi.
2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan multivariabel. Pemeriksaan inti ini meliputi:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius melakukan perbaikan di 3 bidang berikut:
Optimasi ProductCheck
Penanganan masalah pembagian dengan nol
Pemeriksaan Permutasi Lintas Kolom
2.3 PIOP: argumen pergeseran multilinear baru
Dalam protokol Binius, konstruksi dan pengolahan polinomial virtual adalah salah satu teknologi kunci, yang terutama mencakup dua metode:
Pengemasan
Operator pergeseran
2.4 PIOP: versi adaptasi argumen pencarian Lasso
Protokol Lasso terdiri dari tiga komponen berikut:
Abstraksi polinomial virtual dari tabel besar
Pencarian tabel kecil
Pemeriksaan multi-kumpulan
Protokol Binius mengadaptasi Lasso untuk operasi di domain biner, memperkenalkan versi perkalian dari protokol Lasso.
2.5 PCS：Versi Adaptasi Brakedown PCS
Gagasan inti dari membangun BiniusPCS adalah packing. Janji polinomial Binius terutama menggunakan:
Komitmen Polin Kecil dan Evaluasi Domain Perluasan
Struktur Umum Kecil
Kode blok dan kode Reed-Solomon
3 Pemikiran yang Dioptimalkan
Untuk lebih meningkatkan kinerja protokol Binius, artikel ini mengusulkan empat poin optimasi kunci:
PIOP berbasis GKR: untuk operasi perkalian domain biner
Optimasi ZeroCheck PIOP: Menimbang pengeluaran komputasi antara Prover dan Verifier
Optimasi PIOP Sumcheck: optimasi untuk Sumcheck pada domain kecil
Optimasi PCS: Mengurangi ukuran proof melalui optimasi FRI-Binius
3.1 PIOP berbasis GKR: Perkalian bidang biner berbasis GKR
Algoritma perkalian integer berbasis GKR, dengan mengubah "memeriksa apakah 2 integer 32-bit A dan B memenuhi A·B =? C" menjadi "memeriksa apakah (gA)B =? gC terpenuhi", secara signifikan mengurangi biaya komitmen dengan bantuan protokol GKR.
3.2 ZeroCheck PIOP optimasi: Perimbangan biaya perhitungan Prover dan Verifier
Utamanya mencakup beberapa arah optimasi berikut:
Mengurangi transfer data pihak yang membuktikan
Mengurangi jumlah titik evaluasi pihak yang membuktikan
Optimasi Interpolasi Aljabar
3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil
Poin utama yang dioptimalkan meliputi:
Pengaruh dan faktor perbaikan dari pergantian putaran
Pengaruh ukuran domain terhadap kinerja
Manfaat optimasi algoritma Karatsuba
Peningkatan efisiensi memori
3.4 PCS Optimasi: FRI-Binius mengurangi ukuran bukti Binius
FRI-Binius telah mengimplementasikan mekanisme lipatan FRI dalam domain biner, membawa 4 inovasi:
Polinomial Datar
Polinomial menghilang subruang
Paket Basis Aljabar
Pertukaran Lingkaran SumCheck
4 Kesimpulan
Seluruh proposisi nilai Binius adalah dapat menggunakan domain power-of-two terkecil untuk saksi, sehingga hanya perlu memilih ukuran domain sesuai kebutuhan. Binius adalah solusi desain kolaboratif "menggunakan perangkat keras, perangkat lunak, dan protokol Sumcheck yang dipercepat dengan FPGA" yang dapat membuktikan dengan cepat dengan penggunaan memori yang sangat rendah.
Binius telah secara dasar menghilangkan hambatan komitmen Prover, hambatan baru terletak pada protokol Sumcheck, di mana banyak evaluasi polinomial dan masalah perkalian domain dapat diselesaikan dengan efisien menggunakan perangkat keras khusus. Skema FRI-Binius adalah varian FRI yang menawarkan pilihan yang sangat menarik—menghilangkan biaya penyisipan dari lapisan bukti domain tanpa menyebabkan lonjakan biaya pada lapisan bukti agregat.
Saat ini, tim Irreducible sedang mengembangkan lapisan rekursifnya dan mengumumkan kerja sama dengan tim Polygon untuk membangun zkVM berbasis Binius; JoltzkVM sedang beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursifnya; tim Ingonyama sedang mewujudkan versi FPGA dari Binius.
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.
12 Suka
Hadiah
12
6
Bagikan
Komentar
0/400
SilentObserver
· 07-16 18:11
Mengapa efisiensi meningkat begitu banyak
Lihat AsliBalas0
StakeOrRegret
· 07-16 11:52
Inilah yang selalu saya katakan, berapa banyak sumber daya yang harus dibuang untuk berevolusi menjadi generasi ke-4 yang sebenarnya.
Lihat AsliBalas0
Ser_This_Is_A_Casino
· 07-16 06:56
Sudah hampir memasuki generasi keempat di sini
Lihat AsliBalas0
AirdropHunterXiao
· 07-15 16:49
Airdrop sudah sangat kompetitif, sepanjang hari mempelajari hal yang mendalam ini.
Lihat AsliBalas0
CodeSmellHunter
· 07-15 16:44
stark manja 666
Lihat AsliBalas0
RektRecorder
· 07-15 16:41
Lebih baik melihat koin di luar arena daripada melihat tumpukan mistik ini.
Rencana optimasi Binius STARKs: Aritmatika bidang biner dan polinomial multilinier meningkatkan efisiensi
Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi
1 Pendahuluan
Salah satu alasan utama ketidak efisienan STARKs adalah sebagian besar nilai dalam program nyata cukup kecil, tetapi untuk memastikan keamanan bukti berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama dari STARKs memiliki lebar kode 252bit, generasi kedua 64bit, dan generasi ketiga 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.
Ketika menggunakan bidang yang lebih kecil, operasi perluasan bidang menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius harus sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan bidang, dan hanya perlu beroperasi dalam bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu menyelami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.
Binius mengusulkan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilainya pada "hyper-cube" (hypercubes) untuk mewakili seluruh jejak perhitungan; kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hyper-cube dapat dipandang sebagai persegi (square), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini meningkatkan efisiensi pengkodean dan kinerja komputasi secara signifikan sambil memastikan keamanan.
2 Analisis Prinsip
Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya:
2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields
Bidang biner berbentuk menara adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi yang efisien dan aritmetika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di bidang biner dapat dinyatakan dalam bentuk aljabar yang padat dan mudah diverifikasi.
2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan multivariabel. Pemeriksaan inti ini meliputi:
Binius melakukan perbaikan di 3 bidang berikut:
2.3 PIOP: argumen pergeseran multilinear baru
Dalam protokol Binius, konstruksi dan pengolahan polinomial virtual adalah salah satu teknologi kunci, yang terutama mencakup dua metode:
2.4 PIOP: versi adaptasi argumen pencarian Lasso
Protokol Lasso terdiri dari tiga komponen berikut:
Protokol Binius mengadaptasi Lasso untuk operasi di domain biner, memperkenalkan versi perkalian dari protokol Lasso.
2.5 PCS：Versi Adaptasi Brakedown PCS
Gagasan inti dari membangun BiniusPCS adalah packing. Janji polinomial Binius terutama menggunakan:
3 Pemikiran yang Dioptimalkan
Untuk lebih meningkatkan kinerja protokol Binius, artikel ini mengusulkan empat poin optimasi kunci:
3.1 PIOP berbasis GKR: Perkalian bidang biner berbasis GKR
Algoritma perkalian integer berbasis GKR, dengan mengubah "memeriksa apakah 2 integer 32-bit A dan B memenuhi A·B =? C" menjadi "memeriksa apakah (gA)B =? gC terpenuhi", secara signifikan mengurangi biaya komitmen dengan bantuan protokol GKR.
3.2 ZeroCheck PIOP optimasi: Perimbangan biaya perhitungan Prover dan Verifier
Utamanya mencakup beberapa arah optimasi berikut:
3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil
Poin utama yang dioptimalkan meliputi:
3.4 PCS Optimasi: FRI-Binius mengurangi ukuran bukti Binius
FRI-Binius telah mengimplementasikan mekanisme lipatan FRI dalam domain biner, membawa 4 inovasi:
4 Kesimpulan
Seluruh proposisi nilai Binius adalah dapat menggunakan domain power-of-two terkecil untuk saksi, sehingga hanya perlu memilih ukuran domain sesuai kebutuhan. Binius adalah solusi desain kolaboratif "menggunakan perangkat keras, perangkat lunak, dan protokol Sumcheck yang dipercepat dengan FPGA" yang dapat membuktikan dengan cepat dengan penggunaan memori yang sangat rendah.
Binius telah secara dasar menghilangkan hambatan komitmen Prover, hambatan baru terletak pada protokol Sumcheck, di mana banyak evaluasi polinomial dan masalah perkalian domain dapat diselesaikan dengan efisien menggunakan perangkat keras khusus. Skema FRI-Binius adalah varian FRI yang menawarkan pilihan yang sangat menarik—menghilangkan biaya penyisipan dari lapisan bukti domain tanpa menyebabkan lonjakan biaya pada lapisan bukti agregat.
Saat ini, tim Irreducible sedang mengembangkan lapisan rekursifnya dan mengumumkan kerja sama dengan tim Polygon untuk membangun zkVM berbasis Binius; JoltzkVM sedang beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursifnya; tim Ingonyama sedang mewujudkan versi FPGA dari Binius.