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

1. Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri, gerçek programlardaki çoğu değerin küçük olmasıdır, ancak Merkle ağacı kanıtının güvenliğini sağlamak için Reed-Solomon kodlaması kullanarak verileri genişletirken, birçok ek yedek değer tüm alanı kaplayacaktır. Alanın boyutunu küçültmek, ana strateji haline gelmiştir.

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 israf alanı bulunmaktadır. İkili alan doğrudan bitlerle işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı içermez, yani 4. nesil STARKs.

Binius aşağıdaki temel teknolojileri kullanmaktadır:

• Kule biçimindeki ikili alanlara dayanan aritmetik.
• Geliştirilmiş HyperPlonk çarpım ve yer değiştirme kontrolü
• Yeni Çoklu Kaydırma Teorisi
• Geliştirilmiş Lasso bulma kanıtı
• Küçük Alan Çoklu Taahhüt Planı

2. İlkelerin Analizi

2.1 Binary alanlarının kuleleri üzerine yapılan aritmetik

Kule tipi ikili alan, yüksek verimli aritmetik işlemleri destekler ve hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynar. Avantajları arasında şunlar bulunmaktadır:

• Verimli hesaplama
• Verimli Sayısallaştırma
• Basitleştirilmiş aritmetik işlemleri destekler
• Katmanlı özelliklerinden tam olarak yararlanmak için kule yapısı kullanılabilir.

2.2 Uygulama HyperPlonk Ürünü ve Permutasyon Kontrolü

Binius, HyperPlonk üzerinde aşağıdaki alanlarda iyileştirmeler yaptı:

• ProductCheck optimizasyonu: Değeri 1 olarak özelleştirin, kontrol sürecini basitleştirin
• Sıfıra bölme sorununun işlenmesi: Payda sıfır olsa bile işleme devam edilebilir.
• Sütunlar Arası Permütasyon Kontrolü: Çoklu sütunlar arası Permütasyon Kontrolünü destekler

2.3 yeni çoklu kaydırma argümanı

Binius, iki ana yöntem tanıttı:

• Paketleme: Komşu öğeleri birleştirerek işlemi optimize etme
• Kaydırma operatörü: Verilen kaydırma miktarına göre blok içindeki öğeleri yeniden düzenler.

2.4 uyarlama Lasso arama argümanı

Binius, Lasso'yu ikili alan işlemlerine uyarlayarak, Lasso protokolünün çarpım versiyonunu tanıttı. İspat tarafı, protokolün güvenliğini sağlamak için her yerde sıfır olmayan bir okuma sayısı vektörüne taahhüt etmek zorundadır.

2.5 uyarlama Brakedown PCS

Binius, ikili alanlara dayalı iki Brakedown çoklu taahhüt çözümü sunmaktadır:

• concatenated code kullanarak örnekleme
• block-level encoding teknolojisi kullanılarak, Reed-Solomon kodlarının ayrı olarak kullanılmasını destekler

3. Optimizasyon Düşüncesi

3.1 GKR tabanlı PIOP

GKR tabanlı ikili alan çarpım işlemi sadece bir yardımcı taahhüt gerektirir, Sumchecks'in maliyetini azaltarak verimliliği artırır.

3.2 ZeroCheck PIOP optimizasyonu

Kanıtlayıcı ve doğrulayıcı arasında iş yükü dağılımını ayarlayarak çeşitli optimizasyon çözümleri önerilmiştir:

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

3.3 Sumcheck PIOP optimizasyonu

Ingonyama, küçük alanlara dayalı Sumcheck protokolü için bir iyileştirme önerdi:

• Dönem seçimlerinin performansı etkiler
• Daha küçük temel alanlar daha belirgin avantajlar gösterir.
• Karatsuba algoritması performansı artırdı
• Bellek verimliliği artırıldı

3.4 PCS optimizasyonu: FRI-Binius

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

• Düzleştirilmiş çok terimli
• Alt alan kaybolma polinomu
• Cebir Temeli Paketleme
• Halka Değişimi SumCheck

4. Kısa Özet

Binius, Prover'ın commit taahhüt darboğazını kaldırdı, yeni darboğaz Sumcheck protokolünde. FRI-Binius çözümü, alan kanıtı katmanının gömülü maliyetlerini ortadan kaldırabilen FRI varyantıdır. Şu anda birçok ekip Binius ile ilgili uygulamalar geliştirmektedir.