Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri

1. Giriş

STARKs'ın verimsizliğinin başlıca nedenlerinden biri, gerçek programlarda çoğu sayının küçük olmasıdır. Ancak Merkle ağacına dayalı kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında birçok ek fazlalık değeri tüm alanı kaplar. Alanın boyutunu azaltmak kritik bir strateji haline geldi.

1. nesil STARKs kodlama bit genişliği 252 bit, 2. nesil 64 bit, 3. nesil 32 bit, ancak 32 bit kodlama bit genişliğinde hala büyük miktarda boş alan bulunmaktadır. Buna karşılık, ikili alan doğrudan bit işlemlerine izin verir, kodlama kompakt ve verimlidir ve hiçbir rastgele boş alan içermez, yani 4. nesil STARKs.

Binius, ikili alan kullanır ve güvenliğini ve gerçek kullanılabilirliğini sağlamak için tamamen geniş alanlara güvenmek zorundadır. Çoğu Prover hesaplamasında yer alan çok terimli polinomların geniş alanlara girmesine gerek yoktur, sadece temel alanda işlemler yaparak küçük alanda 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 geniş alanlara derinlemesine inmek zorundadır.

Binius, yenilikçi bir çözüm önerdi: Öncelikle, çok değişkenli (özellikle çok lineer) çok terimli ifadeleri tek değişkenli çok terimli ifadeler yerine kullanarak, "hiperküp" üzerindeki değerleri kullanarak tüm hesaplama izini temsil etti; ikincisi, hiperküpü kare olarak ele alarak, bu kare üzerinde Reed-Solomon genişlemesi yaptı. 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, beş temel teknolojiyi içermektedir:

1. Kule tipi ikili alanına dayalı aritmatizasyon
2. Yeniden düzenlenmiş HyperPlonk çarpımı ve permütasyon kontrolü
3. Yeni Çoklu Kaydırma Teoremi
4. Geliştirilmiş Lasso Bulma Tezi
5. Küçük Alan Çoklu Polinom Taahhüt Projesi

2.1 Sonlu Alan: binary alanlar üzerindeki kulelere dayalı aritmetik

Kule tipi ikili alan, yüksek verimli aritmetik işlemleri destekler ve basitleştirilmiş aritmetik süreçleri destekler. İkili alanın elemanları benzersiz ve doğrudan bir temsil biçimine sahiptir ve farklı boyutlardaki alanlar arasında esnek bir şekilde dönüştürülebilir ve paketlenebilir.

2.2 PIOP: Uyarlanmış HyperPlonk Ürünü ve Permutasyon Kontrolü

Binius, GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck ve BatchCheck dahil olmak üzere bir dizi temel kontrol mekanizması kullanmaktadır.

HyperPlonk'a kıyasla, Binius aşağıdaki alanlarda geliştirmeler yaptı:

• ProductCheck optimizasyonu
• Sıfır bölme sorununun işlenmesi
• Çapraz Sıra Permutasyon Kontrolü

2.3 PIOP: yeni çok satırlı kaydırma argümanı

Binius, sanal çok terimli işlemleri işlemek için Packing ve kaydırma operatörleri olmak üzere iki ana yöntemi kullanır.

2.4 PIOP: uyarlama Lasso arama argümanı

Lasso protokolü üç bileşenden oluşmaktadır:

• Büyük tablonun sanal çoklu polinom soyutlaması
• Küçük tablo arama
• Çoklu küme kontrolü

Binius, ispatçı ve doğrulayıcının ortak olarak artırdığı protokolün "bellek sayımı" işlemini basit bir şekilde 1 artırmak yerine, ikili alandaki çarpan üreteci ile artırarak çarpan versiyonu olan Lasso protokolünü tanıttı.

2.5 PCS: uyarlama versiyonu Brakedown PCS

Binius çoklu taahhüt esas olarak şunları kullanır:

• Küçük alan çok terimli taahhüt ve genişletilmiş alan değerlendirmesi
• Küçük alan genel yapısı
• Blok kodlama ve Reed-Solomon kodu teknolojisi

3. Optimizasyon Düşüncesi

3.1 GKR tabanlı PIOP: GKR tabanlı ikili alan çarpımı

GKR tabanlı tam sayı çarpma işlemi algoritması, "iki 32-bit tam sayısı A ve B'nin A·B =? C eşitliğini sağlayıp sağlamadığını kontrol et" ifadesini, "(gA)B =? gC'nin geçerliliğini kontrol et" şeklinde dönüştürerek GKR protokolü ile taahhüt maliyetlerini önemli ölçüde azaltır.

3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi

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

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

• Değiştirme turlarının etkisi ve iyileştirme faktörleri
• Temel alan boyutunun performansa etkisi
• Karatsuba algoritmasının optimizasyon getirisi
• Bellek verimliliğinin artırılması

3.4 PCS optimize: FRI-Binius Binius proof boyutunu azaltır

FRI-Binius, ikili alan FRI katlama mekanizmasını gerçekleştirdi ve 4 alanda yenilik sundu:

• Düzleştirilmiş çok terimli
• Alt alan kaybolma polinomu
• Cebirsel Temel Paketleme
• Halka Değişim SumCheck

4. Özet

Binius, Prover'ın commit taahhüt dar boğazını temel olarak tamamen ortadan kaldırdı, yeni dar boğaz Sumcheck protokolünde bulunuyor. FRI-Binius çözümü, alan kanıtlama katmanındaki gömülü maliyetleri ortadan kaldıran FRI varyantıdır. Şu anda, Irreducible ekibi, kendi tekrarlamalı katmanını geliştiriyor ve Polygon ekibi ile birlikte Binius tabanlı zkVM inşa ediyor; JoltzkVM Lasso'dan Binius'a geçiş yapıyor; Ingonyama ekibi Binius'un FPGA versiyonunu uyguluyor.