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ı üzerine kurulu kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması ile verileri genişletirken, birçok ek yedek değer tüm alanı kaplayacaktır, oysa orijinal değer kendisi çok küçük olabilir. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARKs kod genişliği 252 bit, 2. nesil STARKs kod genişliği 64 bit, 3. nesil STARKs kod genişliği 32 bit, ancak 32 bit kod genişliği hâlâ büyük miktarda israf alanı içermektedir. Buna karşılık, ikili alan doğrudan bitler üzerinde işlem yapılmasına izin verir, kodlama sıkı ve verimlidir ve hiçbir israf alanı yoktur, yani 4. nesil STARKs.

Goldilocks, BabyBear ve Mersenne31 gibi son yıllarda yapılan yeni araştırmalarla karşılaştırıldığında, ikili alanların araştırması 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alanlar kriptografide yaygın olarak kullanılmaktadır, tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standardı (AES), F28 alanına dayanmaktadır;

• Galois Mesaj Kimlik Kodu ( GMAC ), F2128 alanına dayanmaktadır;

• QR kodu, F28 tabanlı Reed-Solomon kodlaması kullanır;

• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve yinelemeli hash algoritmaları için oldukça uygundur.

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ğ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 girmeden, yalnızca temel alan altında işlem yaparak küçük alanlarda yüksek verimlilik sağlamaktadır. 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 inmelidir.

İkili alan üzerine kanıt sistemleri inşa ederken, iki pratik sorun vardır: STARKs içinde izin temsilini hesaplamak için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs içinde Merkle ağacı taahhüdü sırasında, Reed-Solomon kodlaması yapılması gerektiğinden, kullanılan alan boyutu kodlama genişletildikten sonra 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 gerçekleştirdi: İlk olarak, çok değişkenli (, özellikle çok lineer ) çok terimli polinomları, "hiperküp" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etmek için tek değişkenli polinomların yerine kullanılmaktadır; İkincisi, hiperküpün her boyutunun uzunluğu 2 olduğu için, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp 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ırmaktadır.

2 Prensip Analizi

Günümüzde ç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, girilen hesaplama ilişkilerini 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 polinom göndermesine olanak tanır, 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; bunlar, polinom ifadelerinin işlenme biçiminde farklılık gösterir, bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Planı ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt planı, PIOP tarafından üretilen polinom eşitliğinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır, bu sayede 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 planları 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 bir sonlu alan veya eliptik eğri ile birleştirerek, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi olup, Pasta eğrisi üzerine kuruludur. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanmaktadır.

• Plonky2: PLONK PIOP ve FRI PCS'yi birleştirerek ve Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir rekursif yapı sağlamak amacıyla 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ğlanır. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gerektirmeden şeffaflığı sağlayıp sağlayamayacağını, rekursif 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, in its interactive Oracle proof protocol (PIOP), Binius adapts the HyperPlonk product and permutation checks to ensure secure and efficient consistency checks between variables and their permutations. Third, the protocol introduces a new multilinear shift proof, optimizing the efficiency of verifying multilinear relationships over small fields. Fourth, Binius employs an improved Lasso search proof, providing flexibility and strong security for the search mechanism. Finally, the protocol utilizes a small field polynomial commitment scheme (Small-Field PCS), enabling it to implement an efficient proof system over binary fields and reducing the overhead typically associated with large fields.

( 2.1 Sonlu Alanlar: binary alanların kulelerine dayanan aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaları gerçekleştirmenin anahtarıdır ve bu, iki ana nedenden kaynaklanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekleyerek, performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimde temsil edilmesini sağlayan basitleştirilmiş bir aritmetik süreç destekler. Bu özellikler, kule yapısını tam olarak kullanabilme yeteneği ile birleştirildiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical" terimi, ikili alan içindeki öğelerin benzersiz ve doğrudan temsil şekline atıfta bulunmaktadır. Örneğin, en temel ikili alan F2'de, herhangi bir k-bit dizesi doğrudan k-bit'lik bir ikili alan öğesine haritalanabilir. Bu, asal alanlardan farklıdır; asal alanlar, belirli bir bit sayısı içinde bu tür standart bir temsil sunamaz. 32-bit'lik bir asal alan 32-bit içinde yer alabilir, ancak her 32-bit dizesi benzersiz bir alan öğesine karşılık gelmezken, ikili alan bu bir-bir eşleme kolaylığını sunar. Asal alan Fp'de, yaygın olan 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 olarak kullanılan indirgeme yöntemleri arasında özel indirgeme ) gibi AES'te kullanılan ###, Montgomery indirgemesi ( gibi POLYVAL'de kullanılan ) ve yeniden girişim indirgemesi ( gibi Tower ) bulunmaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı ç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 belirtmektedir, çünkü (X + Y )2 = X2 + Y 2'nin sadeleştirilmiş kuralını izlemektedir.

Ş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 ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizesinin tür dönüşümüdür (typecast), oldukça ilginç ve kullanışlı bir özelliktir. Aynı zamanda, küçük alan elemanları, ek bir hesaplama yükü olmaksızın daha büyük alan elemanları olarak paketlenebilir. Binius protokolü, bu özelliği kullanarak hesaplama verimliliğini artırır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" başlıklı makale, n bitlik kule ikili alanında ( m bitlik alt alan ) için çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

( 2.2 PIOP: Uyarlama HyperPlonk Ürünü ve Permutasyon Kontrolü------ İkili alan için uygundur

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

1. GateCheck: Gizli tanık ω ve açık giriş x'in, devre hesaplama ilişkesi C)x, ω###=0'ı karşılayıp karşılamadığını doğrulayarak devrenin doğru çalıştığından emin olun.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Boolean hiperküpündeki değerlerinin bir permutasyon ilişkisi olup olmadığını doğrulamak için f(x) = f(π)x((, polinom değişkenleri arasındaki düzenliliği sağlamak amacıyla.

3. LookupCheck: Çok terimli polinomun değerinin verilen arama tablosunda olup olmadığını doğrulamak, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğunu sağlamak.

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üpte rasyonel çok terimli bir polinomun değerinin belirli bir beyan edilen değere ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmek, polinom çarpımının doğruluğunu sağlamak için.

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

7. SumCheck: Çok değişkenli çok terimli polinomun toplamının belirtilen 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ğerlendirmesine dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek, birden fazla toplam doğrulama örneğinin işlenmesi için lineer kombinasyon yapmayı sağlar.

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

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

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

• Sıfıra bölme sorunlarının işlenmesi: HyperPlonk, sıfıra bölme durumlarını yeterince ele alamadı ve U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirleyemedi; Binius bu sorunu doğru bir şekilde ele aldı, hatta payda sıfır olduğunda bile Binius'ün ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine yayılmasına izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu işlevi desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli düzenlemeleri işlemesini 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 çok terimli doğrulamalarını işlerken daha güçlü işlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alanlara dayalı kanıt sistemleri için bir temel oluşturdu.

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

Binius protokolünde, sanal çok terimlerin yapımı ve işlenmesi anahtar teknolojilerden biridir ve giriş kollarından veya diğer sanal çok terimlerden türetilen çok terimleri etkin bir şekilde oluşturma ve işleme yeteneğine sahiptir. İşte iki anahtar yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlarda bulunan daha küçük elemanları daha büyük elemanlar haline getirerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan bloklara yönelik çalışır ve bunları yüksek boyutlu hale getirir.