Binius STARKs Analizi ve Optimizasyonu

1. Giriş

STARK'ların verimsizliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır; ancak Merkle ağacı kanıtlarının güvenliğini sağlamak için, Reed-Solomon kodlaması kullanarak 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 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 bir israf alanı vardır. İkili alan, bitler üzerinde doğrudan işlem yapılmasına izin verir, kodlama sıkı ve verimlidir ve herhangi bir israf alanı yoktur, bu da 4. nesil STARKs olabilir.

Binius, verimliliği çeşitli açılardan artırmak için kule benzeri ikili alan üzerinde aritmetik, geliştirilmiş HyperPlonk çarpım ve yer değiştirme kontrolü, alt alan çok terimli taahhüt gibi teknolojiler kullanmaktadır.

2. İlkelerin Analizi

Binius, beş ana teknolojiden oluşmaktadır:

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

2.1 Kule tipi ikili alan üzerinde aritmetik

Kule tipi ikili alan, verimli aritmetik işlemleri ve basitleştirilmiş aritmetik süreçleri destekler. İkili alan elemanları k bitlik dizelere doğrudan eşlenebilir ve birebir eşleme avantajı sunar.

2.2 Uyarlama HyperPlonk Çarpım ve Değiştirme Kontrolü

Binius, HyperPlonk'un çekirdek kontrol mekanizmasını, GateCheck, PermutationCheck, LookupCheck gibi unsurları örnek alarak geliştirmiştir ve aşağıdaki alanlarda iyileştirmeler yapmıştır:

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

2.3 Yeni Çoklu Kaydırma Tezi

Binius, sanal polinomları oluşturmak ve işlemek için iki ana yöntem olan Packing ve kaydırma operatörlerini tanıttı.

2.4 Uygulama Lasso Arama Kanıtı

Binius, Lasso'yu ikili alan işlemlerine uyarlayarak, Lasso protokolünün çarpan versiyonunu tanıttı.

2.5 Küçük Alan Çok Terimli Taahhüt

Binius, ikili alanlara dayalı iki Brakedown polinom taahhüt planı sunmaktadır; bunlar esasen küçük alan polinom taahhüdü ve genişletilmiş alan değerlendirmesi, küçük alan genel yapıları ve blok düzeyinde kodlama ile Reed-Solomon kodu teknolojisini kullanmaktadır.

3. Optimizasyon Düşüncesi

3.1 GKR tabanlı PIOP

GKR tabanlı ikili alan çarpma işlemi algoritması, "A·B =? C olan iki 32-bit tam sayı A ve B'nin kontrolü" ifadesini, "(gA)B =? gC'nin sağlanıp sağlanmadığını kontrol et" olarak dönüştürerek, GKR protokolü yardımıyla taahhüt masraflarını büyük ölçüde azaltmaktadır.

3.2 ZeroCheck PIOP optimizasyonu

İspat ve doğrulama tarafları 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 noktalarının sayısını azalt
• Cebirsel Enterpolasyon Optimizasyonu

3.3 Sumcheck PIOP optimizasyonu

Ingonyama, küçük alanlara dayalı Sumcheck protokolü için t'nin seçiminde döngü geçişine odaklanan bir iyileştirme önerdi.

3.4 PCS optimizasyonu: FRI-Binius

FRI-Binius, ikili alan FRI katlama mekanizmasını uyguladı ve 4 alanda yenilik getirdi:

• Düzleştirilmiş Çokgen
• Alt alan kaybolma polinomu
• Cebirsel Temel Paketleme
• Çevrim Değişimi SumCheck

4. Özet

Binius, "donanım, yazılım ve FPGA'da hızlandırılmış Sumcheck protokolü" kullanan bir işbirliği tasarım çözümüdür ve çok düşük bir bellek kullanımı ile hızlı bir şekilde kanıt sunabilir. Binius'ta Prover'ın commit taahhüt darboğazı neredeyse tamamen ortadan kaldırılmıştır, yeni darboğaz ise Sumcheck protokolündedir ve bu, özel donanımlar sayesinde verimli bir şekilde çözülebilir.

FRI-Binius çözümü, alan ispat katmanından gömülü maliyetleri ortadan kaldırmadan, FRI varyantı için kullanılabilir ve toplu ispat katmanının maliyet patlamasına neden olmaz. Şu anda, birden fazla ekip, yinelemeli katman, zkVM gibi Binius ile ilgili teknolojiler geliştiriyor.