Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri
1 Giriş
STARK'ların düşük verimliliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının küçük olmasıdır, ancak Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlamasıyla verilerin genişletilmesi sırasında birçok ek yedek değer tüm alanı kaplamaktadır. Bu sorunu çözmek için alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.
nesil STARKs kodlama bit genişliği 252 bit, 2. nesil 64 bit, 3. nesil 32 bit'tir, ancak 32 bit kodlama genişliği hala büyük ölçüde israf alanı içermektedir. Buna göre, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama kompakt ve verimlidir ve herhangi bir israf alanı yoktur, yani 4. nesil STARKs.
Küçük bir alan kullanıldığında, genişletme işlemi güvenliğin sağlanması için giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliği ve pratik kullanılabilirliği sağlamak için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadelerin genişletme alanına girmesi gerekmez, sadece temel alanda işlem yaparak küçük alanlarda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmek zorundadır.
Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde temsil ederek bunu başardı: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerlerini kullanarak tüm hesaplama yolunu temsil ediyor; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare olarak düşünülebilir ve bu kare temel alınarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliği sağlarken, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.
2 Prensip Analizi
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius verimliliğini ve güvenliğini sağlamak için beş ana teknoloji içermektedir:
İkili alanların kuleleri (towers of binary fields) üzerine kurulu aritmetik
HyperPlonk çarpım ve yer değiştirme kontrolünü değiştirdi
Yeni Çoklu Kaydırma Teoremi
Geliştirilmiş Lasso bulma kanıtı
Küçük Alan Çok Terimli Taahhüt Planı (Small-Field PCS)
2.1 Sonlu Alanlar: binary alanların kuleleri üzerine temellendirilmiş aritmetik
İkili alanlar, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir öneme sahiptir; bu, esasen iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temel olarak son derece verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş bir aritmetik süreci destekler; yani, ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir.
2.2 PIOP: Uyarlama HyperPlonk Ürünü ve PermutationCheck
Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almıştır ve çok terimlerin ve çok değişkenli kümelerin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:
GateCheck
PermutasyonKontrol
LookupCheck
MultisetCheck
ÜrünKontrol
ZeroCheck
SumCheck
BatchCheck
Binius aşağıdaki 3 alanda iyileştirmeler yaptı:
ProductCheck optimizasyonu
Sıfır bölme sorununun çözümü
Sütunlar Arası Permütasyon Kontrolü
2.3 PIOP: yeni çoklu kaydırma argümanı
Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi temel teknolojilerden biridir. Bu, esasen iki yöntem içerir:
Paketleme
Kaydırma Operatörü
2.4 PIOP: Uyarlama Lasso arama argümanı
Lasso protokolü aşağıdaki üç bileşenden oluşmaktadır:
Büyük tablo için sanal çok terim soyutlaması
Küçük tablo arama
Çoklu küme kontrolü
Binius protokolü, Lasso'yu ikili alan işlemlerine uyarlayarak, Lasso protokolünün çarpan versiyonunu tanıttı.
2.5 PCS:uyarlama Brakedown PCS
BiniusPCS'nin temel düşüncesi packing'tir. Binius polinom taahhüdü esas olarak şunları kullanır:
Küçük alan çoklu taahhüt ve genişletilmiş alan değerlendirmesi
Küçük alan evrensel yapısı
Blok kodlama ve Reed-Solomon kodu
3 Optimize Düşünme
Binius protokolünün performansını daha da artırmak için bu makalede dört ana optimizasyon noktası önerilmektedir:
GKR tabanlı PIOP: İkili alan çarpma işlemleri için
ZeroCheck PIOP optimizasyonu: Prover ile Verifier arasında hesaplama maliyeti dengesi sağlama
Sumcheck PIOP optimizasyonu: Küçük alan Sumcheck için optimizasyon
PCS optimizasyonu: proof boyutunu azaltmak için FRI-Binius ile optimize edildi.
3.1 GKR tabanlı PIOP: GKR tabanlı ikili alan çarpımı
GKR tabanlı tam sayı çarpma işlem algoritması, "iki 32-bit tam sayı A ve B'nin A·B =? C'yi sağlayıp sağlamadığını kontrol et" ifadesini, "kontrol et (gA)B =? gC'nin geçerli olup olmadığını" şeklinde dönüştürerek, GKR protokolünden faydalanarak taahhüt maliyetlerini büyük ölçüde azaltır.
3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama gideri dengesi
Başlıca aşağıdaki birkaç optimizasyon yönünü içerir:
FRI-Binius, ikili alan FRI katlama mekanizmasını gerçekleştirdi ve 4 alanda yenilik getirdi:
Düzleştirilmiş çok terimli
Alt alan kaybolan polinom
Cebirsel Temel Paketleme
Halka Değişimi SumCheck
4 Özet
Binius'un tüm değer önerisi, tanıklar için en az power-of-two alanını kullanabilmesi, bu nedenle yalnızca gerekli olan alan boyutunun seçilmesi gerektiğidir. Binius, "donanım, yazılım ve FPGA'daki hızlandırılmış Sumcheck protokolü ile" iş birliği tasarım çözümüdür ve çok düşük bellek kullanımı ile hızlı bir şekilde kanıt sunabilir.
Binius'ta Prover'ın commit taahhüt darboğazı temelde tamamen ortadan kaldırıldı, yeni darboğaz Sumcheck protokolünde bulunuyor. Sumcheck protokolündeki çok sayıda polinom değerlendirmesi ve alan çarpma gibi sorunlar, özel donanım kullanılarak verimli bir şekilde çözülebilir. FRI-Binius çözümü, FRI varyantıdır ve alan kanıtı katmanından gömülü maliyetleri ortadan kaldırarak, toplu kanıt katmanının maliyetlerinin aşırı artmasına neden olmadan oldukça cazip bir seçenek sunar.
Şu anda, Irreducible ekibi kendi yinelemeli katmanını geliştirmekte ve Binius tabanlı zkVM inşa etmek için Polygon ekibi ile işbirliği yaptığını duyurmuştur; JoltzkVM, yinelemeli performansını geliştirmek için Lasso'dan Binius'a geçmektedir; Ingonyama ekibi Binius'un FPGA versiyonunu gerçekleştirmektedir.
View Original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
12 Likes
Reward
12
6
Share
Comment
0/400
SilentObserver
· 07-16 18:11
Verimlilik bu kadar arttı nasıl?
View OriginalReply0
StakeOrRegret
· 07-16 11:52
Bu, gerçek 4. nesile evrimleşmek için ne kadar kaynak israf edilmeli dediğim şey.
View OriginalReply0
Ser_This_Is_A_Casino
· 07-16 06:56
Burada dördüncü nesile hızlıca geçiyoruz.
View OriginalReply0
AirdropHunterXiao
· 07-15 16:49
Airdrop iç içe geçmiş durumda, gün boyunca bu derin konuyu araştırıyorum.
View OriginalReply0
CodeSmellHunter
· 07-15 16:44
stark şımarık 666
View OriginalReply0
RektRecorder
· 07-15 16:41
Tüy yumağı dışındaki paraları tercih ederim, bu yığın metafiziği değil.
Binius STARKs optimizasyon çözümü: İkili alan aritmetiği ve çok değişkenli çok terimli polinom verimliliğini artırma
Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri
1 Giriş
STARK'ların düşük verimliliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının küçük olmasıdır, ancak Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlamasıyla verilerin genişletilmesi sırasında birçok ek yedek değer tüm alanı kaplamaktadır. Bu sorunu çözmek için alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.
Küçük bir alan kullanıldığında, genişletme işlemi güvenliğin sağlanması için giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliği ve pratik kullanılabilirliği sağlamak için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadelerin genişletme alanına girmesi gerekmez, sadece temel alanda işlem yaparak küçük alanlarda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmek zorundadır.
Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde temsil ederek bunu başardı: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerlerini kullanarak tüm hesaplama yolunu temsil ediyor; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare olarak düşünülebilir ve bu kare temel alınarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliği sağlarken, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.
2 Prensip Analizi
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius verimliliğini ve güvenliğini sağlamak için beş ana teknoloji içermektedir:
2.1 Sonlu Alanlar: binary alanların kuleleri üzerine temellendirilmiş aritmetik
İkili alanlar, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir öneme sahiptir; bu, esasen iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temel olarak son derece verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş bir aritmetik süreci destekler; yani, ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir.
2.2 PIOP: Uyarlama HyperPlonk Ürünü ve PermutationCheck
Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almıştır ve çok terimlerin ve çok değişkenli kümelerin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:
Binius aşağıdaki 3 alanda iyileştirmeler yaptı:
2.3 PIOP: yeni çoklu kaydırma argümanı
Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi temel teknolojilerden biridir. Bu, esasen iki yöntem içerir:
2.4 PIOP: Uyarlama Lasso arama argümanı
Lasso protokolü aşağıdaki üç bileşenden oluşmaktadır:
Binius protokolü, Lasso'yu ikili alan işlemlerine uyarlayarak, Lasso protokolünün çarpan versiyonunu tanıttı.
2.5 PCS:uyarlama Brakedown PCS
BiniusPCS'nin temel düşüncesi packing'tir. Binius polinom taahhüdü esas olarak şunları kullanır:
3 Optimize Düşünme
Binius protokolünün performansını daha da artırmak için bu makalede dört ana optimizasyon noktası önerilmektedir:
3.1 GKR tabanlı PIOP: GKR tabanlı ikili alan çarpımı
GKR tabanlı tam sayı çarpma işlem algoritması, "iki 32-bit tam sayı A ve B'nin A·B =? C'yi sağlayıp sağlamadığını kontrol et" ifadesini, "kontrol et (gA)B =? gC'nin geçerli olup olmadığını" şeklinde dönüştürerek, GKR protokolünden faydalanarak taahhüt maliyetlerini büyük ölçüde azaltır.
3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama gideri dengesi
Başlıca aşağıdaki birkaç optimizasyon yönünü içerir:
3.3 Sumcheck PIOP optimizasyonu: Küçük alanlara dayalı Sumcheck protokolü
Ana optimizasyon noktaları şunlardır:
3.4 PCS Optimizasyon: FRI-Binius Binius kanıt boyutunu azaltır
FRI-Binius, ikili alan FRI katlama mekanizmasını gerçekleştirdi ve 4 alanda yenilik getirdi:
4 Özet
Binius'un tüm değer önerisi, tanıklar için en az power-of-two alanını kullanabilmesi, bu nedenle yalnızca gerekli olan alan boyutunun seçilmesi gerektiğidir. Binius, "donanım, yazılım ve FPGA'daki hızlandırılmış Sumcheck protokolü ile" iş birliği tasarım çözümüdür ve çok düşük bellek kullanımı ile hızlı bir şekilde kanıt sunabilir.
Binius'ta Prover'ın commit taahhüt darboğazı temelde tamamen ortadan kaldırıldı, yeni darboğaz Sumcheck protokolünde bulunuyor. Sumcheck protokolündeki çok sayıda polinom değerlendirmesi ve alan çarpma gibi sorunlar, özel donanım kullanılarak verimli bir şekilde çözülebilir. FRI-Binius çözümü, FRI varyantıdır ve alan kanıtı katmanından gömülü maliyetleri ortadan kaldırarak, toplu kanıt katmanının maliyetlerinin aşırı artmasına neden olmadan oldukça cazip bir seçenek sunar.
Şu anda, Irreducible ekibi kendi yinelemeli katmanını geliştirmekte ve Binius tabanlı zkVM inşa etmek için Polygon ekibi ile işbirliği yaptığını duyurmuştur; JoltzkVM, yinelemeli performansını geliştirmek için Lasso'dan Binius'a geçmektedir; Ingonyama ekibi Binius'un FPGA versiyonunu gerçekleştirmektedir.