Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri

1 Giriş

Elli eğri tabanlı SNARK'lardan farklı olarak, STARK'lar hash tabanlı SNARK'lar olarak görülebilir. Mevcut STARK'ların verimsiz olmasının 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ğaç tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında, birçok ek fazlalık değeri tüm alanı kaplar; bu, orijinal değer ç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ği hala büyük ölçüde israf alanı içermektedir. Karşılaştırıldığında, ikili alan doğrudan bitler üzerinde işlem yapmaya olanak tanır, kodlama sıkı ve verimli olup herhangi bir israf alanı içermez, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alan araştırmaları 1980'lere 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 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 birlikte, F28 alanına dayanan ve özyinelemeye oldukça uygun bir hash algoritması olan Grøstl hash fonksiyonu, SHA-3 finaline girmiştir.

Küçük alanlar kullanıldığında, genişletme işlemi güvenliğin sağlanmasında giderek daha önemli hale gelmektedir. Binius'un kullandığı ikili alan, güvenliğini ve gerçek kullanılabilirliğini sağlamak için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadelerin genişletmeye girmesine gerek yoktur, yalnızca temel alan altında işlem yaparak 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 derinlemesine inmeyi gerektirir.

İkili alanlar üzerinde bir kanıtlama sistemi inşa ederken, iki pratik sorun vardır: STARKs'da izlerin temsilini hesaplarken, kullanılan alan boyutu polinomun derecesinden büyük olmalıdır; STARKs'da Merkle ağacı taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alan boyutu kodlama genişletme 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 temsil etti: İlk olarak, çok değişkenli (, tam olarak çoklu lineer ) çok terimli yerine tek değişkenli çok terimli kullanarak, "hiperküp" ( üzerindeki değerlerini alarak tüm hesaplama yolunu temsil eder; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğu için STARK'lar gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp bir kare ) olarak görülebilir ve bu kareye dayalı olarak Reed-Solomon genişlemesi yapılabilir. Bu yöntem, güvenliği sağlarken kodlama verimliliği ve hesaplama performansını büyük ölçüde artırmaktadı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 temel unsuru olarak, giriş 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 polinomu aşamalı olarak 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ı sorgulayarak doğrulama yapabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme şekli bakımından farklılık gösterir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Projesi ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt projesi, PIOP tarafından üretilen polinom eşitliğinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli bir polinoma taahhütte bulunabilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizleyebilir. Yaygın polinom taahhüt projeleri arasında KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown gibi projeler bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama senaryolarına sahiptir.

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

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleştirilmesiyle oluşturulmuş ve Pasta eğrisi temel alınarak geliştirilmiştir. Halo2, ölçeklenebilirliğe odaklanarak ZCash protokolündeki trusted setup'ı kaldırmayı amaçlamaktadır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanır. Plonky2, yüksek verimli bir özyinelemeyi 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, bu da sistemin doğruluğunu, performansını ve güvenliğini sağlamak için gereklidir. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemenin yanı sıra, sistemin güvenilir bir ayar gerektirmeden şeffaflık sağlayıp sağlayamayacağını, özyinelemeli kanıtları veya toplama kanıtları gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliği ve güvenliğini sağlamak için beş temel teknolojiyi içerir. İlk olarak, kule biçimindeki ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş işlemlerin gerçekleştirilmesine olanak tanır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpan ve yer değiştirme kontrolünü uyarlayarak, değişkenler ve bunların yer değiştirmeleri arasında güvenli ve verimli bir tutarlılık kontrolü sağlar. Üçüncüsü, protokol, küçük alanlar üzerinde çoklu doğrusal ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrusal 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, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesini sağlamak ve genellikle büyük alanlarla ilişkilendirilen yükleri azaltmak için (Small-Field PCS) küçük alan polinom taahhüt şemasını kullanmaktadır.

( 2.1 Sonlu Alan: binary fields'in kulelerine dayanan aritmetik

Kule tipi ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bu, iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimlilikte aritmetik işlemleri destekler, bu da onu performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş aritmetik süreçleri destekler; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulaması kolay cebirsel bir biçimde temsil edilebilir. Bu özellikler, kule yapısını kullanarak 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 alan içindeki bir öğenin benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k bitlik dize doğrudan k bitlik bir ikili alan öğesine haritalanabilir. Bu, asal alanlardan farklıdır; asal alan belirli bir bit sayısında bu tür bir standart temsil sağlayamaz. 32 bitlik asal alan 32 bit içinde yer alabilirken, her 32 bitlik dize benzersiz bir alan öğesine karşılık gelmeyebilir; oysa ikili alan bu birine bir eşleme kolaylığını sağlar. Asal alan Fp'de yaygın azaltma yöntemleri arasında Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel azaltma yöntemleri bulunur. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında AES'te kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower ( gibi özyinelemeli azaltma ) yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı çalışmada, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediği ve ikili alanın kare alma işleminin oldukça verimli olduğu belirtilmektedir, çünkü bu işlem (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralına tabidir.

Ş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 düşünülebilir veya iki 64 bitlik kule alan öğesi, dört 32 bitlik kule alan öğesi, on altı 8 bitlik kule alan öğesi veya 128 F2 alan öğesi olarak ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden yalnızca bit dizisinin tür dönüşümünü (typecast) gerektirir ve bu çok ilginç ve kullanışlı bir özelliktir. Ayrıca, küçük alan öğeleri, ek hesaplama maliyeti olmadan daha büyük alan öğeleri haline getirilebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özelliği kullanır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" adlı makalede, n bitlik kule ikili alanının ( m bitlik alt alana ) ayrıştırılarak çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığı incelenmiştir.

( 2.2 PIOP: Uyarlama HyperPlonk Ürünü ve Permütasyon Kontrolü------ İ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ık ω ve açık girdi x'in, devre işletim ilişkisi C)x,ω(=0'ı karşılayıp karşı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 Boolean hiperküpündeki değerlerinin, çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak için, bir permütasyon ilişkisi olan f)x### = f(π)x() olup olmadığını doğrulayın.

3. LookupCheck: Verilen arama tablosunda çok terimli polinomun değerinin 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ında tutarlılığı sağlar.

5. ProductCheck: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun belirli bir beyan edilen değere ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etme, polinom çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli 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 noktası dağılımını sağlamak için.

7. SumCheck: Çok değişkenli çok terimli polinomun toplamının belirtilen değerle eşit olup olmadığını kontrol etme ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirme sorununa dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck toplu işleme de izin verir; rastgele sayılar kullanarak, birden fazla toplam doğrulama örneği için lineer kombinasyon oluşturarak toplu işlem gerçekleştirir.

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

Binius ve HyperPlonk protokol tasarımında birçok benzerliğe sahip olmasına rağmen, Binius 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ştirmiş ve hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme sorununun işlenmesi: HyperPlonk, sıfıra bölme durumunu yeterince işleyemediği için U'nun hiper küp üzerindeki sıfırdan farklı olduğunu kesin olarak söylemek mümkün değildir; Binius bu durumu doğru bir şekilde ele almıştır, sıfır olan bir payda durumunda bile Binius'un ProductCheck'i işlemeye devam edebilir ve herhangi bir çarpan değerine genişletilmesine izin verir.

• 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ı işleyebilmesini 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ı işlerken daha güçlü işlevsel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıt sistemleri için bir temel oluşturdu.

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

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi anahtar teknolojilerden biridir ve giriş işleyicilerinden veya diğer sanal çok terimlerden türetilen çok terimleri etkin bir şekilde oluşturup işlemeyi sağlar. İşte iki anahtar yöntem:

• Paketleme: Bu yöntem, sözlük sırası içinde komşu konumların daha küçük olanını kullanarak