Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri

1. Giriş

STARK'ların verimsizliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının küçük olmasıdır; ancak Merkle ağaçları üzerine 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. Bu sorunu çözmek için alanın boyutunu azaltmak anahtar 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 genişliğinde hâlâ büyük miktarda israf alanı bulunmaktadır. Karşılaştırıldığında, ikili alan doğrudan bitlere işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı bulunmamaktadır, yani 4. nesil STARKs.

Binius'un kullandığı ikili alan, güvenliğini ve pratik uygulanabilirliğini sağlamak için tamamen genişletilmiş alana bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimlilerin genişletilmiş alana girmesi gerekmez, sadece temel alanda işlem 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 bir genişletilmiş alana derinlemesine inmelidir.

Binius'un yenilikçi bir çözüm önerisi var: Öncelikle, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak "hiperküpler" üzerindeki değerleri alarak tüm hesaplama izini temsil etmek; ikincisi, hiperküpün her boyutunun uzunluğunun 2 olması sebebiyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare olarak düşünülebilir ve bu kareye dayanarak Reed-Solomon genişletmesi gerçekleştirilebilir.

2. Prensip Analizi

Binius beş ana teknolojiyi içerir:

1. Kule tipi ikili alan üzerine dayalı aritmetik
2. Düzenlenmiş HyperPlonk çarpımı ve yer değiştirme kontrolü
3. Yeni Çoklu Kaydırma Tezi
4. Geliştirilmiş Lasso bulma kanıtı
5. Küçük Alan Çok Terimli Taahhüt Planı

2.1 Sonlu Alan: binary alanların kuleleri üzerine inşa edilmiş aritmetik

Kule tipi ikili alanın avantajları:

• Yüksek verimli hesaplama: İkili alan esasen yüksek verimli aritmetik işlemleri destekler.
• Verimli Arithmatik: İkili alan yapısı basitleştirilmiş aritmetik işlemleri destekler
• Standart gösterim: İkili alandaki elemanların benzersiz ve doğrudan bir gösterim şekli vardır.

İkili alan avantajları:

• Toplama ve çarpma işlemlerinin taşıma gerektirmeden yapılabilir.
• Kare hesaplama çok verimlidir, (X + Y)^2 = X^2 + Y^2 sadeleştirme kuralına uyar.
• Esneklik gösterir: 128 bitlik bir dize, 128 bitlik ikili alandaki benzersiz bir eleman olarak görülebilir veya çeşitli kule alanı elemanlarının kombinasyonu olarak analiz edilebilir.

2.2 PIOP: Uyarlama HyperPlonk Ürünü ve Permutasyon Kontrolü

Binius PIOP çekirdek kontrol mekanizması:

• GateCheck
• PermutasyonKontrol
• LookupCheck
• MultisetCheck
• ÜrünKontrol
• ZeroCheck
• SumCheck
• BatchCheck

Binius'un HyperPlonk üzerindeki iyileştirmesi:

• ProductCheck optimizasyonu
• Sıfıra bölme sorunlarının yönetimi
• Sütunlar arası Permutasyon Kontrolü desteği

2.3 PIOP: yeni çoklu kaydırma argümanı

Anahtar Yöntemler:

• Ambalaj: Komşu öğeleri birleştirerek işlemi optimize etme
• Kaydırma operatörü: blok içindeki öğeleri yeniden düzenleme

2.4 PIOP: uyarlama Lasso arama argümanı

Lasso protokolü bileşenleri:

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

Binius'un Lasso'ya uyarlaması:

• Lasso protokolünün çarpan versiyonunu tanıtma
• Kanıtlayıcıdan her yerde sıfır olmayan bir okuma sayımı vektörüne taahhüt etmesi istenir.

2.5 PCS: uyarlama Brakedown PCS

Temel düşünce: packing

İki adet ikili alan tabanlı Brakedown polinom taahhüt şeması:

1. concatenated code kullanarak örnek oluşturma
2. block-level encoding teknolojisi kullanarak, Reed-Solomon kodlarını ayrı kullanmayı destekler.

Ana Teknoloji:

• 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

3. Optimizasyon Düşüncesi

Dört ana optimizasyon noktası:

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

Binius lookup çözümüne göre avantajları:

• Sadece bir yardımcı taahhüt yeter
• Sumchecks maliyetini azalt

3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi

Optimize yöntemleri:

• Kanıtlayan tarafın veri iletimini azaltmak
• İspat tarafının değerlendirme noktası sayısını azaltmak
• Cebirsel İnterpolasyon Optimizasyonu

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

Anahtar Nokta:

• Dönüşüm sırasının etkisi ve iyileştirme faktörü
• Temel alan boyutunun performansa etkisi
• Karatsuba algoritmasının optimizasyon kazancı
• Bellek verimliliğinin artırılması

3.4 PCS optimizasyonu: FRI-Binius Binius kanıt boyutunu düşürüyor

FRI-Binius dört yenilik:

• Düzleştirilmiş Çokgen
• Alt alan kaybolma polinomları
• Cebirsel Temel Paketleme
• Çember Değişimi SumCheck

FRI-Binius PCS süreci:

• Taahhüt Aşaması
• Değerlendirme Aşaması

4. Kısa Özet

Binius'un değer önerisi:

• Tanıklar için en az power-of-two alanı kullanılabilir
• İşbirliği tasarım planı, düşük bellek kullanımıyla hızlı kanıt
• Prover'ın commit taahhüt darboğazını temel olarak kaldırın
• Yeni darboğaz Sumcheck protokolünde, özel donanım kullanarak verimli bir şekilde çözülebilir.

FRI-Binius planı:

• Alan kanıtı katmanından gömülü maliyeti kaldırmak
• Toplama kanıtı katmanının maliyetlerini artırmaz

Güncel ilerleme:

• Irreducible ekibi, Polygon ile işbirliği yaparak Binius tabanlı zkVM'yi geliştiren bir rekürsif katman inşa etti.
• JoltzkVM, Lasso'dan Binius'a geçiş yaptı.
• Ingonyama ekibi FPGA versiyonu Binius'u gerçekleştirdi