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

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; örneğin, for döngüsündeki indeksler, doğru/yanlış değerleri, sayaçlar vb. Ancak, Merkle ağacı kanıtlarının güvenliğini sağlamak için, verileri genişletmek amacıyla Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değeri tüm alanı kaplar, hatta orijinal değerler çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARKs kodlama bit genişliği 252 bit, 2. nesil STARKs kodlama bit genişliği 64 bit, 3. nesil STARKs kodlama bit genişliği 32 bit, ancak 32 bit kodlama bit genişliğinde hala büyük miktarda israf alanı bulunmaktadır. Karşılaştırıldığında, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı olmaksızın, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanıyor. Günümüzde, ikili 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ır;

• Orijinal FRI ve zk-STARK protokolleri, ayrıca SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve rekürsif için oldukça uygun bir hash algoritmasıdır.

Küçük alanlar kullanıldığında, genişletme işlemleri 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. Çoğu Prover hesaplamasında yer alan çok terimli ifadeler genişletme alanına girmek zorunda kalmadan, sadece temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine girmeyi gerektirir.

İkili alanlara dayalı bir kanıt sistemi kurarken, iki pratik sorun vardır: STARKs'ta izin (trace) temsilini hesaplamak için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüt edilmesi sırasında Reed-Solomon kodlaması yapılması gerekir, kullanılan alanın boyutu kodlama genişletme sonrası boyutundan büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde ifade ederek bunu başardı: İlk olarak, çok değişkenli (, spesifik olarak çoklineer ) çok terimli fonksiyonu tek değişkenli çok terimli fonksiyon yerine kullanarak, "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etti; İkinci olarak, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp bir kare ) olarak ele alınabilir ve bu kare temel alınarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliği sağlarken, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.

2 Prensip Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki bölümden oluşur:

• Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin çekirdeği olarak, girişteki hesaplama ilişkisini doğrulanabilir polinom eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim aracılığıyla, kanıtlayıcının polinomları adım adım göndermesine izin verir; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca birkaç polinomun değerlendirme sonuçlarını sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi farklı polinom ifadelerini işleme yöntemleri vardır ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Şeması ( Polinom Taahhüt Şeması, PCS ): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denklemlerinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bununla, kanıtlayıcı belirli bir polinoma taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, polinomun diğer bilgilerini gizli tutar. Yaygın polinom taahhüt şemaları arasında KZG, Bulletproofs, FRI ( Hızlı Reed-Solomon IOPP ) ve Brakedown bulunmaktadır. Farklı PCS'lerin farklı performansları, güvenlikleri ve kullanım senaryoları vardır.

Belirli gereksinimlere göre, farklı PIOP ve PCS'ler seçilir ve uygun bir sonlu alan veya eliptik eğri ile birleştirilerek, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile ve Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarımında, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'yi birleştirerek Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir özyineleme sağlamak amacıyla tasarlanmıştır. Bu sistemleri tasarlarken, seçilen PIOP ve PCS'nin kullanılan sonlu alan veya eliptik eğri ile uyumlu olması gerekir, böylece sistemin doğruluğu, performansı ve güvenliği sağlanır. Bu kombinasyonların seçimi, yalnızca SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar olmadan şeffaflık sağlaması, özyinelemeli kanıtları veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + binary fields. Specifically, Binius includes five key technologies to achieve its efficiency and security. First, the arithmetic based on tower binary fields (towers of binary fields) forms the foundation of its computation, enabling simplified operations within the binary fields. Second, Binius adapts HyperPlonk's product and permutation checks in its interactive Oracle proof protocol (PIOP) to ensure secure and efficient consistency checks between variables and their permutations. Third, the protocol introduces a new multilinear shift proof that optimizes the efficiency of verifying multilinear relationships over small fields. Fourth, Binius employs an improved version of the Lasso lookup proof, providing flexibility and strong security for the lookup mechanism. Finally, the protocol uses a small field polynomial commitment scheme (Small-Field PCS), enabling the realization of an efficient proof system over binary fields and reducing the overhead typically associated with large fields.

( 2.1 Sınırlı Alan: binary alanların kuleleri üzerine kurulu aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir rol oynamaktadır, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetikleştirme. İkili alan, esasen yüksek verimli aritmetik işlemleri destekler ve bu da onu performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim yapar. Ayrıca, ikili alan yapısı, aritmetikleştirme sürecinin basitleştirilmesini destekler; yani, ikili alanda gerçekleştirilen işlemler, sıkı ve doğrulanması kolay cebirsel biçimlerde ifade edilebilir. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alan içinde elemanların benzersiz ve doğrudan temsil şekli olarak tanımlanır. Örneğin, en temel ikili alan F2’de, herhangi bir k bitlik dize doğrudan k bitlik bir ikili alan elemanına eşlenebilir. Bu, asal alanlardan farklıdır çünkü asal alanlar belirli bir bit sayısı içinde bu tür standart bir temsili sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilse de, her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmeyebilir; ikili alan ise bu birbiriyle eşleşme kolaylığını sunar. Asal alan Fp’de yaygın indirgeme yöntemleri arasında Barrett indirgemesi, Montgomery indirgemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel indirgeme yöntemleri bulunmaktadır. İkili alan F2k’de yaygın indirgeme yöntemleri arasında özel indirgeme ) (AES’de kullanılan) ###, Montgomery indirgemesi (POLYVAL’de kullanılan) ( ve yinelemeli indirgeme ) (Tower () yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı çalışma, ikili alanın toplama ve çarpma işlemlerinde taşıma gerektirmediğini ve ikili alanın kare alma işleminin son derece verimli olduğunu belirtir çünkü bu işlem )X + Y (2 = X2 + Y 2'nin sadeleştirilmiş kuralını takip eder.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: Bu dize, ikili alan bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir eleman olarak görülebilir veya iki 64 bitlik kule alan elemanı, dört 32 bitlik kule alan elemanı, on altı 8 bitlik kule alan elemanı veya 128 adet F2 alan elemanı olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, sadece bit dizisinin tür dönüşümünü gerektirir )typecast(, oldukça ilginç ve kullanışlı bir özelliktir. Ayrıca, küçük alan elemanları, ek hesaplama yükü olmadan daha büyük alan elemanlarına paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özelliği kullanmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" adlı makale, n bitlik kule yapısındaki ikili alanın ) m bitlik alt alan ( ile çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

![Bitlayer Research: Binius STARKs prensip analizi ve optimizasyon düşünceleri])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 2.2 PIOP: Uyarlanmış HyperPlonk Ürünü ve Permutasyon Kontrolü------İkili alan için uygun

Binius protokolündeki PIOP tasarımı HyperPlonk'tan esinlenmiştir ve çok terimlerin ve çok değişkenli kümelerin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:

1. GateCheck: Gizli tanıklama ω ve kamuya açık girdi x'in, devre hesaplama ilişkisi C(x, ω)=0'ı karşılayıp karşılamadığını doğrulayarak devrenin doğru çalışmasını sağlamaktadır.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Boolean hiperküpteki değerlendirme sonuçlarının bir permütasyon ilişkisi olup olmadığını doğrulamak için f###x( = f)π(x)(, polinom değişkenleri arasındaki sıralamanın tutarlılığını sağlamak amacıyla.

3. LookupCheck: Verilen arama tablosunda çok terimli bir polinomun değerinin doğrulanması, yani f(Bµ) ⊆ T)Bµ(, belirli değerlerin belirtilen aralıkta olduğunu garanti eder.

4. MultisetCheck: İki çok değişkenli kümenin eşitliğini kontrol etme, yani {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, birden fazla küme arasındaki tutarlılığı sağlama.

5. ProductCheck: Mantıksal hiper küpte bir rasyonel çok terimli ifadenin değerlendirmesinin belirli bir bildirilen değerle ∏x∈Hµ f)x( = s ile eşit olup olmadığını kontrol etmek, çok terimli çarpımın doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean hiperküpündeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, polinomun sıfır noktalarının dağılımını sağlamak için.

7. SumCheck: Çok değişkenli çok terimli polinomların toplam değerinin beyan edilen değer olup olmadığını kontrol eder ∑x∈Hµ f)x( = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirmesi olarak dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck toplu işlemlere de izin verir; rastgele sayılar tanıtarak, birden fazla toplam kontrol örneği için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinom değerlemesinin doğruluğunu doğrulamak için, protokol verimliliğini artırır.

Binius, HyperPlonk ile protokol tasarımında birçok benzerliğe sahip olmasına rağmen, aşağıdaki 3 alanda iyileştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in paydası U'nun hiperküpte her yerde sıfır olmaması ve çarpımın belirli bir değere eşit olması gerekmektedir; Binius, bu değeri 1 olarak özelleştirerek bu kontrol sürecini basitleştiriyor ve hesaplama karmaşıklığını azaltıyor.

• Sıfır bölme sorununun çözümü: HyperPlonk, sıfır bölme durumlarını yeterince iyi işlemiyor, bu da U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını belirlemeyi imkansız kılıyor; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan bir payda durumunda bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve her türlü çarpan değerine yayılmasına izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli sıralama durumlarını ele almasını sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasını geliştirerek protokolün esnekliğini ve verimliliğini artırdı; özellikle daha karmaşık çok değişkenli polinom doğrulamalarını işlerken daha güçlü işlevsel destek sağladı. Bu iyileştirmeler, HyperPlonk'taki sınırlamaların yanı sıra, gelecekte ikili alanlara dayalı kanıt sistemleri için de bir temel oluşturdu.

![Bitlayer Research: Binius STARKs prensip analizi ve optimizasyon düşünceleri])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(

) 2.3 PIOP: yeni çoklu kaydırma argümanı------boolean hiper küp için uygundur

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamaklarından veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturup işlemeye olanak tanır. İşte iki anahtar yöntem:

• Ambalaj: Bu yöntem aracılığıyla