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

1. Giriş

STARKs'ın düşük verimliliğinin ana nedenlerinden biri şudur: Gerçek programlarda çoğu değer küçüktür, ancak Merkle ağacına dayalı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verilerin genişletilmesi sırasında birçok ek yedeklilik değeri tüm alanı kaplar, bu nedenle orijinal değerler çok küçük olsa bile. Alanın boyutunu azaltmak kritik bir strateji haline gelir.

1. nesil STARKs kodlama bit genişliği 252bit, 2. nesil 64bit, 3. nesil 32bit, ancak 32bit hala çok fazla israf alanı bulunmaktadır. İkili alan, doğrudan bit işlemlerine izin verir, kodlama kompakt, verimli ve israf olmadan, 4. nesil STARKs olabilir.

İkili alan, AES(F28), GMAC(F2128), QR kodu(F28) gibi kriptografide yaygın olarak kullanılmaktadır. Daha küçük alanlar kullanıldığında, genişletme işlemi güvenliği sağlamak için giderek daha önemli hale gelir. Binius tarafından kullanılan ikili alan, güvenlik ve kullanılabilirliği sağlamak için tamamen genişletmeye dayanır. Çoğu Prover hesaplaması temel alanda çalışır, etkilidir; rastgele nokta kontrolü ve FRI hesaplamaları daha büyük bir genişletmeye derinlemesine inerek güvenliği sağlamalıdır.

Binius yenilikçi çözümleri:

1. Çok değişkenli ( çoklu lineer ) çok terimli polinomun yerine tek değişkenli polinom, "hiperküp" değer alarak hesaplama izini temsil eder.
2. hiper küpü kare olarak görmek, kareye dayalı Reed-Solomon genişlemesi yapmak

2. İlkelerin Analizi

Binius = HyperPlonk PIOP + Brakedown PCS + ikili alan

Beş anahtar teknoloji:

1. Tabanlı ikili alan üzerinde aritmetik
2. HyperPlonk'un çarpım ve permütasyon kontrolü ile uyarlanması
3. Yeni Çoklu Kaydırma Teoremi
4. Geliştirilmiş Lasso Arama Tezi
5. Küçük Alan Çok Terimli Taahhüt Planı

2.1 Sonlu Alan: binary alanların kuleleri üzerine kurulu aritmetik

Kule İkili Alan Avantajları:

• Verimli Hesaplama: İkili alan verimli aritmetik işlemleri destekler
• Verimli Arithmetik: İkili alan yapısı, aritmetik süreci basitleştirmeyi destekler.
• Katmanlı özelliklerden tam olarak yararlanmak için kule yapısı aracılığıyla

128 bitlik dize esnek bir şekilde yorumlanabilir:

• 128 bitlik ikili alanda benzersiz bir eleman
• İki 64 bitlik kule alanı elemanı
• Dört 32 bit kule alanı elementi
• 16 adet 8 bitlik Tower Domain elemanı
• 128 adet F2 alan elemanı

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

Binius çekirdek kontrol mekanizması:

1. GateCheck
2. PermutasyonKontrolü
3. LookupCheck
4. MultisetCheck
5. ÜrünKontrol
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius'un HyperPlonk İyileştirmesi:

• ProductCheck optimizasyonu
• Sıfıra bölme sorununu doğru bir şekilde ele alma
• Sütunlar arası Permutasyon Kontrolünü destekler

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

Anahtar yöntem:

• Paketleme: Komşu daha küçük elemanları daha büyük elemanlar haline getirin
• Kaydırma operatörü: blok içindeki elemanları yeniden sıralama

2.4 PIOP: Uyarlama Lasso arama argümanı

Lasso protokolünün avantajları:

• Kanıt verimliliği yüksek: m+n alan elemanı taahhüt
• Büyük tablolar için taahhüt gerektirmez: çok büyük tabloları işleyebilir.

Binius, çarpan versiyon Lasso protokolünü tanıttı:

• İkili alan çarpımı ile oluşturulan "bellek sayacı" artışı
• Kanıtlayıcı taraf, güvenliği sağlamak için sıfır olmayan okuma sayısı vektörünü taahhüt eder.

2.5 PCS: uyarlama versiyonu Brakedown PCS

Ana fikir: packing

İki seçenek:

1. concatenated code kullanılarak örnekleme
2. Block düzeyi kodlama kullanarak, Reed-Solomon kodlarının ayrı bir şekilde kullanılmasını destekler.

Küçük alan çoktanımlı taahhütleri ve genişletilmiş alan değerlendirmesi:

• Küçük alan K'da taahhüt etmek
• Daha büyük genişletme alanı L/K içinde değerlendirme

Blok kodlama ve Reed-Solomon kodu:

• Küçük alan ( gibi F2) çok terimli büyük alfabe ( gibi F216) Reed-Solomon kodu ile verimli taahhüt eder.

3. Optimizasyon Düşüncesi

Dört ana optimizasyon noktası:

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

"kontrol et A·B =? C" ifadesini "kontrol et (gA)B =? gC" ifadesine dönüştür

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

3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi

Optimizasyon Yöntemi:

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

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

Geliştirme odak noktası:

• Döngü t seçimi
• Temel alan boyutu etkisi
• Karatsuba algoritması optimizasyonu
• Bellek verimliliği artışı

3.4 PCS optimizasyonu: FRI-Binius proof boyutunu düşürüyor

Dört yenilik:

1. Düzleştirilmiş Çok Terimli
2. Alt alan kaybolma polinomları
3. Cebirsel Temel Paketleme
4. Çevrim Değişimi SumCheck

FRI-Binius, Binius kanıtının boyutunu bir büyüklük azaltabilir.

4. Özet

Binius avantajları:

• witnesses için en az power-of-two alanı kullanılabilir
• Düşük bellek kullanımı ile hızlı kanıt
• Temel olarak Prover commit taahhüt darboğazını ortadan kaldırma

Yeni Engel: Sumcheck Protokolü

• Özel donanım kullanarak verimli bir şekilde çözüm sağlanabilir.

FRI-Binius:

• Alan kanıtı katmanının gömme maliyetlerini ortadan kaldırma
• Toplama kanıtı katmanının maliyetinin artmasına neden olmaz

Güncel Gelişme:

• Irreducible ekibi, Binius tabanlı zkVM oluşturmak için Polygon ile iş birliği yaparak geri döngü katmanı geliştiriyor.
• JoltzkVM, Lasso'dan Binius'a geçiyor
• Ingonyama, FPGA sürümü Binius'u gerçekleştirir.