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

1 Giriş

STARK'ların düşük verimliliğ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ğerler, sayıcılar vb. Ancak, Merkle ağaçları tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verilerin genişletilmesi sırasında, birçok ek fazlalık değeri tüm alanı kaplar, orijinal değerlerin kendisi ç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 genişliğinde hala büyük ölçüde israf alanı vardır. Buna karşılık, ikili alan doğrudan bitler üzerinde işlem yapılmasına izin verir, kodlama sıkı ve etkili olup herhangi bir israf alanı bulunmamaktadır, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alanların araştırması 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alanlar kriptolojide 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 ile SHA-3 finaline katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve rekürsif işlemler için oldukça 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ğ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 denklemler genişletmeye girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolleri ve FRI hesaplamaları gereken güvenliği sağlamak için daha büyük bir genişletmeye derinlemesine inmeye ihtiyaç duyar.

İkili alanlara dayalı bir kanıt sistemi inşa ederken iki gerçek sorun vardır: STARKs içinde izin temsilini hesaplamak için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs içinde Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alanın boyutu kodlama genişletmesinden sonra büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm sundu ve aynı veriyi iki farklı şekilde temsil ederek bunu gerçekleştirdi: Öncelikle, çok değişkenli (, özellikle çoklu lineer ) çok terimli polinomları tek değişkenli polinomlar yerine kullanarak, "hiperküp" ( üzerindeki değerleriyle tüm hesaplama izini temsil etmektedir; İkincisi, hiperküpün her boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare ) olarak düşünülebilir ve bu kareye dayanarak 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 sistemi genellikle aşağıdaki iki bölümden oluşur:

• Bilgi Teorisi Çok Terimli Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin temelini oluşturarak, girdi hesaplama ilişkisini doğrulanabilir çok terimli eşitliklere dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının adım adım çok terimleri göndermesine izin verir, böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için az sayıda çok terimin değerlendirme sonuçlarını sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve her biri çok terimli ifadeleri işleme biçiminde farklılık gösterir; bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Çok Terimli Taahhüt Protokolü ( Polynomial Commitment Scheme, PCS ): Çok terimli taahhüt protokolü, PIOP tarafından üretilen çok terimli denklemin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır, bununla birlikte, kanıtlayıcı bir polinom taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizler. Yaygın çok terimli taahhüt protokolleri KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown gibi protokollerdir. Farklı PCS'ler farklı performans, güvenlik ve kullanım senaryolarına sahiptir.

Belirli gereksinimlere göre farklı PIOP ve PCS'ler seçerek ve uygun bir sonlu alan veya eliptik eğri ile birleştirerek, farklı özelliklere sahip kanıt sistemleri oluşturmak mümkündür. Örneğin:

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

• Plonky2: PLONK PIOP ve FRI PCS'nin birleştirilmesi ve Goldilocks alanına dayanmaktadır. Plonky2, verimli bir rekursiyon 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ğ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 olmadan şeffaflık sağlamasını, rekursif kanıtlar veya toplama kanıtları gibi genişletilebilir işlevleri destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + binary fields. Specifically, Binius includes five key technologies to achieve its efficiency and security. First, its arithmetic based on tower binary fields (towers of binary fields) forms the basis of its computations, enabling simplified operations within the binary field. Second, Binius adapts HyperPlonk product and permutation checks in its interactive Oracle proof protocol (PIOP), ensuring 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 lookup proof, providing flexibility and strong security for the lookup mechanism. Finally, the protocol uses a small field polynomial commitment scheme (Small-Field PCS), allowing 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 kuleleri üzerine kurulu aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplama gerçekleştirmenin anahtarıdır ve bu iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, özünde yüksek derecede verimli aritmetik işlemleri destekler ve bu nedenle performansa duyarlı kriptografik uygulamalar için ideal bir seçimdir. Ayrıca, ikili alan yapısı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebileceği basitleştirilmiş aritmetik süreçleri destekler. Bu özellikler ile birlikte, kule yapısı sayesinde hiyerarşik özelliklerinden tam olarak faydalanabilme yeteneği, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

burada "kanonik", ikili etki alanındaki bir öğenin benzersiz ve doğrudan bir temsilini ifade eder. Örneğin, en temel ikili etki alanı F2'de, herhangi bir k-bit dizesi doğrudan bir k-bit ikili etki alanı öğesine eşlenebilir. Bu, verilen konum içinde böyle bir kanonik temsil sağlayamayan asal sayı alanının tersidir. 32 bitlik bir asal sayı alanı 32 bitlik bir sistemde bulunabilse de, her 32 bitlik dize benzersiz bir şekilde bir etki alanı öğesine karşılık gelmez ve ikili alanlar bu bire bir eşlemenin rahatlığına sahiptir. 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 bulunur. İkili etki alanı F2k'de, yaygın olarak kullanılan indirgeme yöntemleri, AES'de ) kullanımı gibi özel indirgeme ### içerir. POLYVAL gibi Montgomery indirgeme (, Tower) gibi ( ve özyinelemeli indirgeme ) kullanır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" (Asal Alan ve İkili Alan ECC-Donanım Uygulamalarının Tasarım Uzayını Keşfetmek) başlıklı makale, ikili alanın hem toplama hem de çarpmada taşımayı tanıtmasına gerek olmadığını ve ikili alanın kare işleminin çok verimli olduğunu çünkü (X + Y'yi takip ettiğini belirtiyor )2 = X2 + Y 2 olur.

Ş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 öğe olarak görülebilir veya iki 64 bitlik kule alan öğesine, dört 32 bitlik kule alan öğesine, on altı 8 bitlik kule alan öğesine veya 128 adet F2 alan öğesine ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizesinin tür dönüşümünü gerektirir (typecast), oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan öğeleri ek hesaplama yükü olmaksızın daha büyük alan öğeleriyle paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özellikten yararlanmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" başlıklı makalede, n bitlik kule ikili alanında ('in m bitlik alt alan )'a çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığı incelenmektedir.

( 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ü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ık ω ve kamu girişi x'in C)x,ω###=0 devre hesaplama ilişkisini sağlayıp sağlamadığını doğrulamak için devrenin doğru çalışmasını sağlamak.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Bool 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: Verilen bir arama tablosunda çok terimli polinomun değerlendirilmesinin doğrulanması, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olmasını 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üp üzerindeki rasyonel çok terimli polinomun değerlendirilmesinin belirli bir ifade edilen değerle ∏x∈Hµ f(x) = s, çok terimli çarpımın doğruluğunu sağlamak için eşit olup olmadığını kontrol etme.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole hiper küpündeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏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 polinomların toplamının beyan edilen değerle eşit olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomların değerlendirme sorununu tek değişkenli polinom değerlendirme sorununa dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar kullanarak birden fazla toplam doğrulama örneği için toplu işleme olanak tanır ve doğrulama işlemi için doğrusal kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, çoklu çok değişkenli polinom değerlerinin 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 problemiyle ilgili işleme: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı ve U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığı konusunda kesin bir yargıya varılamadı; Binius bu durumu doğru bir şekilde ele aldı, hatta payda sıfır olduğunda bile Binius'un 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 sıralama durumlarını işlemesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasına yaptığı iyileştirmelerle, protokolün esnekliğini ve verimliliğini artırdı. Özellikle daha karmaşık çok değişkenli çok terimli doğrulamayı işlerken daha güçlü işlevsellik desteği 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 hiper kümesine uygundur

Binius protokolünde, sanal polinomların yapılandırılması ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamağından veya diğer sanal polinomlardan türetilen polinomları etkin bir şekilde oluşturup işleyebilir. İşte iki anahtar yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki bitişik konumlardaki daha küçük öğeleri daha büyük öğeler halinde paketleyerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan blok işlemleri hedef alır ve bunları yüksek boyutlu alanlarda birleştirir.