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 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ı tabanlı kanıtların güvenliğini sağlamak için, verilere Reed-Solomon kodlaması ile genişletme yapıldığında, birçok ek yedeklilik değeri tüm alanı kaplar, orijinal değer kendisi çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

Tablo 1'de gösterildiği gibi, 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ği hala büyük ölçüde israf alanı içermektedir. Karşılaştırıldığında, ikili alan bitlere doğrudan işlem yapmaya izin verir, kodlama kompakt ve verimli olup, herhangi bir israf alanı olmadan, yani 4. nesil STARKs.

| Cebir | Kodlama Bit Genişliği | Tipik Uygulama | |------|----------|----------| | 1. Nesil | 252bit | StarkWare | | 2. nesil | 64bit | Plonky2 | | 3. nesil | 32bit | Plonky3 | | 4. Nesil | 1bit | Binius |

Goldilocks, BabyBear ve Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Şu anda, ikili alanlar kriptografide yaygın olarak kullanılmaktadır; tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standardı (AES), F2^8 alanına dayanmaktadır
• Galois Mesaj Doğrulama Kodu ( GMAC ), F2^128 alanına dayanmaktadır.
• QR kodu, F2^8 tabanlı Reed-Solomon kodlaması kullanarak
• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline katılan Grøstl hash fonksiyonu, F2^8 alanına dayanmaktadır ve tekrarlama için çok uygun bir hash algoritmasıdır.

Küçük bir alan 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ği ve pratik kullanılabilirliği sağlamak için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan polinomlar, genişletme alanına girmeden sadece temel alan altında işlem görerek küçük alanlarda 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 inmek zorundadır.

İkili alanlar temelinde bir kanıtlama sistemi oluştururken, iki pratik sorun bulunmaktadır: STARKs'ta izlerin gösterimi için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutu, kodlama genişletildikten sonra elde edilen boyuttan 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 temsil ederek bunu başardı: İlk olarak, çok değişkenli (, özellikle çok lineer ) polinomları, tek değişkenli polinomlar yerine kullanıldı ve bu, "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etmek için gerçekleştirildi; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp bir kare ) olarak düşünülebilir 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ırmıştır.

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 temelini oluşturarak, girilen hesaplama ilişkisini doğrulanabilir polinom eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının adım adım polinomlar 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 bulunmaktadır ve bunlar, polinom ifadelerinin işlenme biçiminde farklılık gösterir, bu da tüm SNARK sisteminin performansı ve verimliliği üzerinde etkili olur.

• Polinom Taahhüt Şeması ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denklemlerinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografi aracıdır; bununla, kanıtlayıcı belirli bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, ayrıca polinomun diğer bilgilerini gizleyebilir. Yaygın polinom taahhüt şemaları arasında KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown bulunmaktadır. Farklı PCS'ler farklı performans, güvenlik ve kullanım senaryolarına sahiptir.

Belirli gereksinimlere göre, farklı PIOP ve PCS'leri seçerek ve uygun sonlu alan veya eliptik eğri ile birleştirerek, farklı özelliklere sahip kanıtlama sistemleri oluşturabilirsiniz. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile oluşturulmuş ve Pasta eğrisi temel alınmıştır. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın ortadan kaldırılmasına odaklanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir yinelemeyi gerçekleştirmek için tasarlanmıştır. Bu sistemleri tasarlarken, seçilen PIOP ve PCS, kullanılan sonlu alan veya eliptik eğri ile eşleşmelidir, böylece sistemin doğruluğu, performansı ve güvenliği sağlanabilir. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar olmaksızın şeffaflık sağlayıp sağlayamayacağını, yinelemeli kanıtları veya toplu kanıtlar gibi genişletilmiş işlevleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Spesifik olarak, Binius, yüksek verimliliği ve güvenliğini sağlamak için beş anahtar teknolojiyi içermektedir. İlk olarak, ( ikili alanların kuleleri) temelinde yapılan aritmetik, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirilmesine olanak tanır. İkincisi, Binius, etkileşimli Oracle kanıtlama protokolü ( PIOP ) içinde, HyperPlonk çarpım ve permütasyon kontrolünü uyarlayarak, değişkenler ve bunların permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlar. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı tanıtmaktadır. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş bir Lasso arama kanıtı kullanmaktadır. Son olarak, protokol, ( Küçük Alan PCS ) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesine ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltmasına olanak tanır.

( 2.1 Sonlu Alanlar: binary alanlarının kuleleri temelinde aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynamaktadır, bu da iki ana nedenden kaynaklanmaktadır: verimli hesaplama ve verimli aritmetikleştirme. İkili alan, esasen son derece verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, ikili alan üzerinde gerçekleştirilen işlemlerin kompakt ve kolayca doğrulanabilir cebirsel biçimde ifade edilebileceği basitleştirilmiş aritmetikleştirme süreçlerini destekler. Bu özellikler, kule yapısı aracılığıyla hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alandaki elemanların benzersiz ve doğrudan gösterim biçimini ifade eder. Ö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; asal alan belirli bir bit sayısı içinde bu tür bir standart gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmeyebilir; oysa ikili alan bu birbiriyle eşleşme kolaylığını sunar. Asal alan Fp'de yaygın olarak kullanılan azaltma yöntemleri arasında Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlara yönelik özel azaltma yöntemleri bulunmaktadır. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında AES'de kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower( gibi ) gibi yinelemeli azaltma bulunmaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı çalışmada, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediği, ayrıca ikili alanın kare alma işleminin son derece verimli olduğu belirtilmiştir; çünkü (X + Y )^2 = X^2 + Y^2 simplification kuralını izler.

Ş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 alanında 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ı ya da 128 tane F2 alanı elemanı olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizesinin tür dönüşümü (typecast) ile ilgili olup, oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan elemanları, ek bir hesaplama maliyeti olmaksızın 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 biçimindeki ikili alanda ( m bitlik alt alana ) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

( 2.2 PIOP: HyperPlonk Ürün ve Permutasyon Kontrolü için Uyarlanmış Sürüm------İkili alan için uygundur

Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almış olup, çok terimli 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ıklık ω ve açık girdi x'in, devre işlemi ilişkisi C)x, ω(=0'ı karşılayıp karşılamadığını doğrulamak için devrenin doğru çalıştığını sağlamak.

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

3. LookupCheck: Polinomun değerinin belirli bir arama tablosunda doğrulanması, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olmak.

4. MultisetCheck: İki çok değişkenli kümenin eşit olup olmadığını kontrol eder, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, birden fazla küme arasındaki tutarlılığı garanti eder.

5. ProductCheck: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun belirli bir beyan değeriyle ∏x∈Hµ f(x) = s olup olmadığını kontrol edin, böylece polinom çarpımının doğruluğunu sağlarsınız.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean hiperküpteki 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 polinomların toplam değerinin beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol eder. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirmesine dönüştürerek, doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek, birden fazla toplam doğrulama örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar inşa eder.

8. BatchCheck: SumCheck'e dayanan, birden fazla çok değişkenli çok terimli polinomun değerinin 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 geliştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in paydası U'nun hiperküp üzerinde 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ştirir ve böylece hesaplama karmaşıklığını azaltır.

• Sıfıra bölme probleminin çözümü: HyperPlonk, sıfıra bölme durumlarını yeterince ele alamadı ve bu nedenle U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirlemek mümkün olmadı; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan bir payda durumunda bile Binius'un ProductCheck'i işlemeye devam etmesine izin vererek herhangi bir çarpan değerine genişletilmesine olanak tanıdı.

• Sütunlar arası PermutationCheck: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında PermutationCheck'i destekleyerek, Binius'un daha karmaşık çok terimli sıralama durumlarını ele almasını sağlıyor.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasını geliştirerek protokolün esnekliğini ve verimliliğini artırmıştır; özellikle daha karmaşık çok değişkenli polinom doğrulamalarını işlerken daha güçlü işlevsellik sunmuştur. Bu iyileştirmeler, HyperPlonk'taki sınırlamaları aşmanın yanı sıra, gelecekteki ikili alanlara dayalı kanıt sistemleri için de bir temel oluşturmuştur.

( 2.3 PIOP: yeni çoklu kaydırma argümanı------boolean hiperküp için uygundur

Binius protokolünde, sanal çokgenlerin oluşturulması ve işlenmesi anahtar teknolojilerden biridir ve etkili bir şekilde üretilebilir.