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

1 Giriş

STARKs'ın verimsizliğinin ana nedenlerinden biri, gerçek programlardaki çoğu sayının küçük olmasıdır; ancak Merkle ağacı kanıtlarının güvenliğini sağlamak için Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında birçok ek yedek değer tüm alanı kaplar. Alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARKs kodlama bit genişliği 252 bit, 2. nesil 64 bit, 3. nesil ise 32 bit'tir, ancak 32 bit kodlama bit genişliği hala büyük miktarda israf alanı içermektedir. İkili alan, bitler üzerinde doğrudan işlem yapılmasına izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı olmadan gerçekleştirilebilir, 4. nesil STARKs haline gelebilir.

İkili alan, AES, GMAC, QR kodu, orijinal FRI ve zk-STARK protokolleri gibi kriptografi alanında yaygın olarak kullanılmaktadır.

Binius, ikili alan kullanırken, güvenliği ve gerçek kullanılabilirliği sağlamak için tamamen geniş alanlara bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadelerin geniş alana girmesine gerek yoktur, sadece temel alanda işlem yapmaları yeterlidir, böylece küçük alanda yüksek verimlilik sağlanır.

Binius yenilikçi çözümler sundu:

1. Çok değişkenli çok terimli ifadeleri, tek değişkenli çok terimli ifadelerin yerine kullanarak, "hiperküp" üzerindeki değerleriyle tüm hesaplama izini temsil eder.
2. hiper küpü kare olarak Reed-Solomon genişletmesi olarak değerlendirin

2 Prensip Analizi

Binius = HyperPlonk PIOP + Brakedown PCS + ikili alan

Beş anahtar teknolojiyi içerir:

1. Tabanlı ikili alan üzerinde aritmatikleştirme
2. HyperPlonk çarpım ve permütasyon kontrolü uyarlaması
3. Yeni Çoklu Kaydırma Teoremi
4. Geliştirilmiş Lasso Arama Kanıtı
5. Küçük Alan Çoklu Terim Taahhüt Planı

2.1 Sınırlı Alan: binary alanların kuleleri üzerine yapılan aritmetik

Kule tipi ikili alan, yüksek verimli aritmetik işlemleri ve basitleştirilmiş aritmetik süreçleri destekler.

128 bitlik bir dize, 128 bitlik ikili alanın bir öğesi olarak değerlendirilebilir veya iki adet 64 bitlik alan öğesi, dört adet 32 bitlik alan öğesi, on altı adet 8 bitlik alan öğesi veya 128 adet F2 alan öğesi olarak çözümlenebilir. Bu temsil esnekliği ek hesaplama maliyeti gerektirmez.

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

Binius protokolündeki PIOP tasarımı HyperPlonk'tan esinlenmiştir ve bir dizi temel kontrol mekanizması kullanmaktadır:

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

Binius aşağıdaki 3 alanda iyileştirmeler yaptı:

• ProductCheck optimizasyonu
• Sıfır bölme sorunlarının çözümü
• Sütunlar Arası Permutasyon Kontrolü

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

Binius protokolünde sanal çok terimli yapı ve işleme için anahtar yöntemler:

• Paketleme
• Kaydırma operatö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 protokolü, Lasso'yu ikili alan işlemlerine uyarlamış ve Lasso protokolünün çarpma versiyonunu tanıtmıştır.

2.5 PCS：uyarlama versiyonu Brakedown PCS

Binius makalesi, ikili alanlara dayalı 2 adet Brakedown çoktanımlı taahhüt şeması sunmaktadır:

1. concatenated code kullanarak örneklendiriliyor
2. block-level encoding teknolojisini kullanır, Reed-Solomon kodlarını ayrı olarak destekler.

Küçük alan çok terimli taahhüt ve genişletilmiş alan değerlendirmesi, küçük alan genel yapılar ve blok düzeyinde kodlama ile Reed-Solomon kodları gibi teknikler, Binius çok terimli taahhüdünü oluşturmak için kullanılmıştır.

3 Optimizasyon Düşüncesi

Dört ana optimizasyon noktası:

1. GKR tabanlı PIOP: İkili alan çarpma işlemleri için GKR protokolünü kullanarak Lasso Lookup algoritmasını değiştirme.

2. ZeroCheck PIOP optimizasyonu: Prover ile Verifier arasında hesaplama yükü dengesi sağlama

3. Sumcheck PIOP optimizasyonu: Küçük alan Sumcheck için optimizasyon

4. PCS optimizasyonu: FRI-Binius optimizasyonu ile kanıt boyutunu azaltma.

3.1 GKR tabanlı PIOP: GKR'ye dayalı ikili alan çarpımı

GKR tabanlı tam sayı çarpma işlemi algoritması, "A·B =? C olup olmadığını kontrol et" ifadesini, "(gA)B =? gC'nin geçerli olup olmadığını kontrol et" ifadesine dönüştürerek, GKR protokolü sayesinde taahhüt maliyetlerini önemli ölçüde azaltır.

3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama yükü dengesi

Ana optimizasyon yönü:

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

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

Ana iyileştirme noktaları:

• Dönem değişiminin etkisi ve iyileştirme faktörü
• Temel alan boyutunun performansa etkisi
• Karatsuba algoritmasının optimizasyon getirisi
• Bellek verimliliğinin artırılması

3.4 PCS optimizasyonu: FRI-Binius Binius kanıt boyutunu azaltır

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

• Düzleştirilmiş Çok Terimli
• Alt alan kaybolma polinomu
• Cebirsel temel paketleme
• Çevrim Değişim SumCheck

4 Özet

Binius'un değer önerisi, witness'lerin en az power-of-two alanını kullanabilmesidir. Binius'ta Prover'ın commit taahhüt darboğazı temelde tamamen ortadan kaldırılmıştır, yeni darboğaz ise Sumcheck protokolündedir.

FRI-Binius çözümü, alan kanıtı katmanından gömülü maliyetleri ortadan kaldırarak, birleşik kanıt katmanının maliyetinin aşırı artmasına neden olmadan FRI varyantıdır.

Şu anda, Irreducible ekibi kendi yinelemeli katmanını geliştiriyor ve Polygon ekibi ile birlikte Binius tabanlı zkVM inşa ediyor; JoltzkVM Lasso'dan Binius'a geçiyor; Ingonyama ekibi Binius'un FPGA versiyonunu gerçekleştiriyor.