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.

  1. 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ı.

Bitlayer Research: Binius STARKs prensibi analizi ve optimizasyon düşünceleri

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:

  1. İkili alanların kuleleri (towers of binary fields) üzerine kurulu aritmetik
  2. HyperPlonk çarpım ve yer değiştirme kontrolünü değiştirdi
  3. Yeni Çoklu Kaydırma Teoremi
  4. Geliştirilmiş Lasso bulma kanıtı
  5. 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.

Bitlayer Research: Binius STARKs ilkesi analizi ve optimizasyon düşünceleri

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:

  1. GateCheck
  2. PermutasyonKontrol
  3. LookupCheck
  4. MultisetCheck
  5. ÜrünKontrol
  6. ZeroCheck
  7. SumCheck
  8. 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

Bitlayer Research: Binius STARKs prensibi analizi ve optimizasyon düşünceleri

3 Optimize Düşünme

Binius protokolünün performansını daha da artırmak için bu makalede dört ana optimizasyon noktası önerilmektedir:

  1. GKR tabanlı PIOP: İkili alan çarpma işlemleri için
  2. ZeroCheck PIOP optimizasyonu: Prover ile Verifier arasında hesaplama maliyeti dengesi sağlama
  3. Sumcheck PIOP optimizasyonu: Küçük alan Sumcheck için optimizasyon
  4. 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.

Bitlayer Research: Binius STARKs prensip analizi ve optimizasyon düşüncesi

3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama gideri dengesi

Başlıca aşağıdaki birkaç optimizasyon yönünü içerir:

  • Kanıtlayıcı tarafın veri iletimini azaltmak
  • Kanıtlayıcı değerlendirme noktalarının sayısını azaltmak
  • Cebirsel İnterpolasyon Optimizasyonu

Bitlayer Research: Binius STARKs prensibi analizi ve optimizasyon düşünceleri

3.3 Sumcheck PIOP optimizasyonu: Küçük alanlara dayalı Sumcheck protokolü

Ana optimizasyon noktaları şunlardır:

  • Dönüşüm döngülerinin etkisi ve iyileştirme faktörü
  • Temel alan boyutunun performansa etkisi
  • Karatsuba algoritmasının optimizasyon getirisi
  • Bellek verimliliğinin artırılması

Bitlayer Research: Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri

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:

  • Düzleştirilmiş çok terimli
  • Alt alan kaybolan polinom
  • Cebirsel Temel Paketleme
  • Halka Değişimi SumCheck

Bitlayer Research: Binius STARKs prensip analizi ve optimizasyon düşünceleri

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.

Bitlayer Research: Binius STARKs ilke analizi ve optimizasyon düşünceleri

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.
  • Reward
  • 6
  • Share
Comment
0/400
SilentObservervip
· 07-16 18:11
Verimlilik bu kadar arttı nasıl?
View OriginalReply0
StakeOrRegretvip
· 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_Casinovip
· 07-16 06:56
Burada dördüncü nesile hızlıca geçiyoruz.
View OriginalReply0
AirdropHunterXiaovip
· 07-15 16:49
Airdrop iç içe geçmiş durumda, gün boyunca bu derin konuyu araştırıyorum.
View OriginalReply0
CodeSmellHuntervip
· 07-15 16:44
stark şımarık 666
View OriginalReply0
RektRecordervip
· 07-15 16:41
Tüy yumağı dışındaki paraları tercih ederim, bu yığın metafiziği değil.
View OriginalReply0
Trade Crypto Anywhere Anytime
qrCode
Scan to download Gate app
Community
  • 简体中文
  • English
  • Tiếng Việt
  • 繁體中文
  • Español
  • Русский
  • Français (Afrique)
  • Português (Portugal)
  • Bahasa Indonesia
  • 日本語
  • بالعربية
  • Українська
  • Português (Brasil)