Binius STARKs Prensiplerinin Analizi ve Optimizasyon Düşünceleri

1 Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri şudur: Gerçek programlardaki çoğu sayı oldukça küçüktür, ancak Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için veri genişletilirken Reed-Solomon kodlaması kullanıldığı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'tir, ancak 32 bit kodlama genişliğinde hala büyük ölçüde israf alanı bulunmaktadır. Buna karşılık, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı bulunmamaktadır, yani 4. nesil STARKs.

İkili alan, kriptografi alanında yaygın olarak kullanılmaktadır, tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standardı ( AES ), F28 alanına dayanmaktadır.
• Galois Mesaj Doğrulama Kodu ( GMAC ), F2128 alanına dayanmaktadır.
• QR kodu, F28 tabanlı Reed-Solomon kodlaması kullanıyor
• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu

Küçük alanlar kullanıldığında, genişletme işlemi güvenliği sağlamak için giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliğini ve pratik kullanılabilirliğini sağlamak için tamamen genişletmeye bağımlıdır.

Binius, yenilikçi bir çözüm önerdi:

• Tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküp" üzerindeki değerleriyle tüm hesaplama izini temsil etmek.
• Hiperkübün bir kare olarak görülmesi ve bu kareye dayanarak Reed-Solomon genişletmesi yapılması

2 Prensip Analizi

Binius = HyperPlonk PIOP + Brakedown PCS + 二进制域

Binius beş ana teknolojiyi içerir:

1. Kule tipi ikili alanlara dayalı aritmetik
2. Uyarlanmış HyperPlonk çarpımı ve yer değiştirme kontrolü
3. Yeni Çoklu Kaydırma Tezleri
4. Geliştirilmiş Lasso Bulma Tezi
5. Küçük Alan Çoklu Polinom Taahhüt Projesi

2.1 Sonlu Alan: binary fields üzerine kurulu towers of binary fields aritmatiği

Kule tipi ikili alanın avantajları:

• Verimli Hesaplama: İkili alan esasen yüksek verimli aritmetik işlemleri destekler
• Verimli Arithmetizasyon: İkili alan yapısı basitleştirilmiş arithmetizasyon sürecini destekler
• Esnek Temsili: Aynı dize, ikili alan bağlamında çeşitli şekillerde yorumlanabilir.
• Taşımaya gerek yok: İkili alanda toplama ve çarpma işlemlerinde taşımaya ihtiyaç yoktur.
• Verimli kare işlemi:(X + Y)2 = X2 + Y2

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

Kilit kontrol mekanizması:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. Ürün Kontrolü
6. ZeroCheck
7. SumCheck
8. BatchCheck

HyperPlonk'a göre iyileştirmeler:

• ProductCheck optimizasyonu
• Sıfır bölme problemi ile başa çıkma
• Sütunlar Arası Permutasyon Kontrolü

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

Anahtar Yöntem:

• Paketleme: Sözlük sırasındaki komşu pozisyonlardaki daha küçük öğeleri daha büyük öğeler haline getirerek işlemi optimize etme.
• Kaydırma operatörü: Verilen kaydırma miktarına dayalı olarak blok içindeki öğeleri yeniden düzenlemek için döngüsel kaydırma.

2.4 PIOP: Uygulama Lasso arama argümanı

Lasso protokolünün avantajları:

• Verimli kanıt: Boyutu n olan bir tabloda m arama için yalnızca m+n alan öğesi taahhüt edilmesi gerekir.
• Büyük tabloya taahhüt yok: Eğer tablo t yapılandırılmışsa, ona taahhüt vermeye gerek yoktur, aşırı büyük tablolar işlenebilir.

Lasso protokolünün bileşenleri:

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

Binius'un Lasso'ya uyarlaması:

• Lasso protokolünün çarpan versiyonunu tanıtmak
• Talep edilen kanıtlayıcı, her yerde sıfır olmayan bir okuma sayısı vektörüne taahhütte bulunmalıdır.

2.5 PCS: Uyarlama Brakedown PCS

Temel düşünce: packing

İki seçenek:

1. concatenated kodu kullanarak
2. Block-level encoding teknolojisi kullanarak, Reed-Solomon kodlarının ayrı olarak kullanılmasını destekler.

Ana teknolojiler:

• 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ı:

1. GKR tabanlı PIOP: İkili alan çarpma işlemi için
2. ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi
3. Sumcheck PIOP optimizasyonu: Küçük alanlara dayalı Sumcheck protokolü
4. PCS Optimizasyonu: FRI-Binius Binius kanıt boyutunu düşürüyor

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

Temel düşünce:

"A ve B'nin A·B =? C eşitliğini sağlayıp sağlamadığını kontrol et" Dönüştürmek için "Kontrol ediliyor (gA)B =? gC geçerli mi"

Avantajlar:

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

3.2 ZeroCheck PIOP optimizasyonu

Optimizasyon Yönü:

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

3.3 Sumcheck PIOP optimizasyonu

Geliştirme Ana Noktası:

• Dönem değişikliği seçimi
• Temel alan boyutunun performansa etkisi
• Karatsuba algoritmasının optimizasyon getirisi
• Bellek verimliliğinin artırılması

Somut sonuçlar:

• GF[2] temel alanında, algoritma 4'ün performansı basit algoritmadan yaklaşık 30 kat daha yüksektir.
• Algoritma 4 sadece 0.26MB bellek gerektirirken, algoritma 3 ise 67MB gerektiriyor.

3.4 PCS optimize: FRI-Binius

Dört yenilikçi nokta:

1. Düzleştirilmiş çok terimli
2. Alt alan kaybolma polinomları
3. Cebirsel Temel Paketleme
4. Dönüşüm SumCheck

Etkisi: Binius'un kanıt boyutunu bir basamak azaltın

4 Özet

Binius'un avantajları:

• Tanıklar için en az power-of-two alanı kullanılabilir.
• Düşük bellek kullanımı, hızlı kanıtlama
• Prover'ın commit taahhüt darboğazı neredeyse tamamen ortadan kaldırıldı.

FRI-Binius Planı: Alan kanıtlama katmanındaki gömülü maliyetleri kaldırmak, toplu kanıt katmanının maliyetinin artmasına neden olmadan.

Son gelişmeler:

• Irreducible ekibi, kendi yinelemeli katmanını geliştiriyor ve Polygon ekibi ile birlikte Binius tabanlı zkVM inşa ediyor.
• JoltzkVM, geri dönüş performansını geliştirmek için Lasso'dan Binius'a geçiyor.
• Ingonyama ekibi Binius'un FPGA versiyonunu gerçekleştiriyor.