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

1. Giriş

STARKs'ın verimsizliğinin başlıca nedenlerinden biri, gerçek uygulamalardaki çoğu sayının oldukça küçük olmasıdır, ancak Merkle ağacı temelli kanıtları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 küçültmek kritik bir strateji haline gelmiştir.

1. nesil STARKs kodlama bit genişliği 252bit, 2. nesil 64bit, 3. nesil 32bit, ancak 32bit kodlama genişliğinde hala büyük miktarda israf alanı bulunmaktadır. Buna göre, ikili alan doğrudan bit işlemlerine izin verir, kodlama sıkı ve verimli olup herhangi bir israf yapmadan, yani 4. nesil STARKs.

Son yıllarda araştırılan Goldilocks, BabyBear, Mersenne31 gibi sonlu alanlarla karşılaştırıldığında, ikili alan araştırmaları 1980'li yıllara kadar uzanmakta olup, AES(F28 alanı), GMAC(F2128 alanı), QR kodu(F28 alanı Reed-Solomon kodlaması) gibi kriptografide yaygın bir şekilde uygulanmaktadır.

Binius, ikili alan kullanır ve güvenlik ve kullanılabilirliği sağlamak için geniş alanlara tamamen bağımlıdır. Çoğu Prover hesaplaması, temel alanda verimli bir şekilde çalışır, rastgele nokta kontrolü ve FRI hesaplamaları güvenliği sağlamak için derinlemesine geniş alana ihtiyaç duyar.

Binius, "hiperküp" üzerinde çok değişkenli çok terimli polinomlar kullanarak hesaplama yollarını temsil eder, hiperküpü kare olarak ele alarak Reed-Solomon genişlemesi yapar ve güvenliği sağlarken kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırır.

2. İlkelerin Analizi

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan.

Beş anahtar teknolojiyi içerir:

1. Kule tipi ikili alanına dayalı aritmetik yapı hesaplama temeli

2. HyperPlonk çarpım ve yer değiştirme kontrolünü yeniden düzenleyin, değişkenlerin ve yer değiştirmelerin tutarlılık kontrolünü sağlayın.

3. Yeni çok çizgili kaydırma kanıtı, küçük alanlarda çok çizgili ilişki doğrulama verimliliğini optimize eder

4. Geliştirilmiş Lasso bulma kanıtı, bulma mekanizmasına esneklik ve güvenlik sağlar.

5. Küçük alan çok terimli taahhüt planı, ikili alanda etkili bir kanıt sistemi gerçekleştirir.

2.1 Sınırlı Alan: binary alanların kuleleri temelinde aritmetik

Kule biçimindeki ikili alan, özellikle Binius gibi ölçeklenebilir kanıt sistemleri için verimli aritmetik işlemler ve basitleştirilmiş aritmetik süreçleri destekler.

128 bitlik bir dize, 128 bitlik ikili alan içindeki benzersiz bir öğe olarak veya iki 64 bitlik dairesel alan öğesi, dört 32 bitlik dairesel alan öğesi, 16 sekiz bitlik dairesel alan öğesi veya 128 adet F2 alan öğesi olarak yorumlanabilir. Bu esneklik, hesaplama maliyeti olmadan, yalnızca bit dizisinin tür dönüşümüdür.

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

Binius PIOP, HyperPlonk'tan esinlenerek, çok terimli ve çok değişkenli küme doğruluğunu doğrulamak için temel kontrol mekanizmalarını kullanır; bunlar arasında GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck ve BatchCheck bulunmaktadır.

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

• ProductCheck optimizasyonu: Değeri 1 olarak özelleştirerek kontrol sürecini basitleştirir ve hesaplama karmaşıklığını azaltır.

• Sıfıra bölme problemi çözümü: Payda sıfır olduğunda durumu doğru bir şekilde ele almak, herhangi bir çarpım değerine yayılmasına izin vermek

• Sütunlar Arası Permutasyon Kontrolü: Daha karmaşık çok terimli sıralama durumlarını işlemek için birden fazla sütun arasında Permutasyon Kontrolü desteği.

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

Binius'ta sanal polinomların yapımı ve işlenmesi anahtar teknolojidir:

• Paketleme: Sözlük sırası komşu pozisyonlardaki daha küçük elemanları daha büyük elemanlar halinde paketleme optimizasyonu.

• Kaydırma operatörü: Verilen kaydırma miktarına göre blok içindeki elemanları yeniden düzenler.

2.4 PIOP: Uygulama Lasso arama argümanı

Lasso protokolü, ispatlayıcının a vektörünü Fm'ye taahhüt etmesine ve tüm öğelerin önceden belirlenmiş t tablosunda Fn içinde bulunduğunu kanıtlamasına olanak tanır.

Binius, Lasso'yu ikili alan işlemlerine uyarlayarak, kanıtlayıcı ve doğrulayıcı tarafların ortak olarak artırdığı "hafıza sayımı" operasyonunu gerektiren çarpım versiyonu Lasso protokolünü tanıttı ve ikili alan çarpımı ile üreteç artırma sağladı.

2.5 PCS: uyarlama Brakedown PCS

BiniusPCS'nin temel düşüncesi packing'tir. İki tür ikili alan tabanlı Brakedown çokgen taahhüt şeması sağlar:

1. concatenated code kullanarak örnekleme

2. block-level encoding teknolojisini kullanarak, Reed-Solomon kodlarını ayrı olarak destekler.

İkinci çözüm, kanıt ve doğrulama sürecini basitleştiriyor, kanıt boyutu biraz daha büyük ama basitleştirme ve uygulama avantajları buna değer.

3. Optimizasyon Düşüncesi

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

"A·B =? C" ifadesini "(gA)B =? gC" ifadesine dönüştürün, GKR protokolü ile taahhüt maliyetlerini büyük ölçüde azaltın.

GKR tabanlı çarpma işlemi sadece bir yardımcı taahhüt gerektirir, bu da algoritmayı daha verimli hale getirerek Sumchecks masraflarını azaltır, özellikle Sumchecks işlemlerinin taahhüt oluşturma işlemlerinden daha ucuz olduğu durumlarda.

3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi

Kanıtlayıcıdan veri aktarımını azaltma: İşlerin bir kısmını doğrulayıcıya devrederek, kanıtlayıcının gönderdiği veri miktarını azaltma.

Kanıtlayıcı değerlendirme noktasının sayısını azaltma: Polinom gönderim yöntemini değiştirerek değerlendirme noktalarının sayısını azaltma.

Cebirsel içsel optimizasyon: Polinom uzun bölme ile sıralı ayrıştırma oluşturulması, içsel optimizasyonun gerçekleştirilmesi.

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

Dönüşüm turlarının etkisi ve iyileştirme faktörü: Dönüşüm turlarının t seçimi performansı etkiler, en iyi dönüşüm noktası iyileştirme faktörü maksimum değere ulaşır.

Temel alan boyutunun performansa etkisi: Daha küçük temel alan (, GF[2]) optimizasyon algoritmasının avantajlarını daha belirgin hale getirir.

Karatsuba algoritması optimizasyon getirisi: Küçük alan Sumcheck performansını önemli ölçüde artırır, algoritma 4, algoritma 3'ten beş kat daha etkilidir.

Bellek verimliliğinde artış: algoritma 4 bellek gereksinimi O(d·t), algoritma 3 için O(2d·t), sınırlı kaynak ortamlarında uygulanabilir.

3.4 PCS Optimize: FRI-Binius Binius proof boyutunu azaltır

FRI-Binius, ikili alan FRI çökme mekanizmasını gerçekleştirerek 4 alanda yenilik getiriyor:

• Düzleştirilmiş Polinom
• Alt alan kaybolma polinomları
• Cebirsel Temel Paketleme
• Çevrim Değişim SumCheck

FRI-Binius sayesinde, Binius'un kanıt boyutunu bir ölçü azaltabilir ve en ileri sistemlere yakın hale getirebilir.

4. Kısa Özet

Binius, Prover commit taahhüt darboğazını temel olarak kaldırdı, yeni darboğaz Sumcheck protokolüdür. FRI-Binius çözümü, alan kanıtı katmanından gömülü maliyetleri ortadan kaldırabilen FRI varyantıdır.

Irreducible ekibi, Polygon ile iş birliği yaparak Binius tabanlı zkVM inşa eden bir geri çağırma katmanı geliştiriyor. JoltzkVM, geri çağırma performansını geliştirmek için Lasso'dan Binius'a geçiş yapıyor. Ingonyama, Binius'un FPGA versiyonunu gerçekleştiriyor.