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

1 Giriş

STARK'ların verimsizliğinin başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu sayısal değer küçük olup, örneğin for döngüsündeki indeksler, doğru/yanlış değerleri, sayaçlar vb. Ancak, Merkle ağaçları tabanlı 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ı kaplar; orijinal değerler kendileri çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu küçültmek 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ği hala büyük miktarda israf alanı barındırıyor. Buna karşın, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı içermez, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan sınırlı alan araştırmalarına kıyasla, ikili alan araştırmaları 1980'lere kadar uzanmaktadır. Günümüzde, ikili alan kriptoloji 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 ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve özyinelemeli hash algoritmaları için son derece uygun bir yöntemdir.

Küçük bir alan 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şletmeye ihtiyaç duymadan yalnızca temel alan altında işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolleri ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmeyi gerektirir.

İkili alan üzerine kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izin temsilinin hesaplanmasında kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağaç taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alanın 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 ) çok terimli polinomları tek değişkenli polinomların yerine kullanarak, "hiperküpler" ( üzerindeki değerleri ile tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARK'lar 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 Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin temel unsuru olarak, 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 polinomları aşamalı olarak göndermesine izin vererek, doğrulayıcının yalnızca birkaç polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulamasını sağlar. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme biçiminde farklılık göstererek, tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Protokolü (Polynomial Commitment Scheme, PCS): Polinom taahhüt protokolü, PIOP tarafından üretilen polinom denklemlerinin geçerliliğini kanıtlamak için kullanılır. PCS, bir şifreleme aracıdır; bu sayede, kanıtlayıcı bir polinoma 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 protokolleri arasında KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) ve Brakedown bulunmaktadır. Farklı PCS'ler farklı performans, güvenlik ve uygulanabilirlik senaryolarına sahiptir.

Belirli gereksinimlere göre, farklı PIOP ve PCS'leri seçip 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'in birleşimi ve Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarlanırken ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleştirilmesi ile 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 uyumlu olmalıdır, 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 gerektirmeden şeffaflık sağlayıp sağlayamayacağını ve rekursif kanıtlar veya toplu kanıtlar gibi genişletme özelliklerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknoloji içermektedir. İlk olarak, kule şeklindeki ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemlerin gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpan ve permütasyon kontrollerini uyarlayarak, değişkenler ve bunların permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol yeni bir çoklu-lineer kaydırma kanıtı getirmiştir, bu da küçük alanlarda çoklu-lineer ilişkilerin doğrulama verimliliğini optimize etmektedir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını benimsemiştir. Son olarak, protokol, ikili alanda verimli bir kanıt sistemi gerçekleştirebilmesi ve genellikle büyük alanlarla ilişkili olan yükleri azaltabilmesi için küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alan: towers of binary fields üzerindeki aritmetik

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir öneme sahiptir ve bu, iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemlerini destekler, bu da onu performansa 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çimlerde ifade edilebileceği basitleştirilmiş bir aritmetik süreci 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.

Burada "canonical" terimi, ikili alan içindeki elemanların benzersiz ve doğrudan gösterim biçimini ifade etmektedir. Örneğin, en temel ikili alan F2'de, herhangi bir k-bit dizesi doğrudan k-bit ikili alan elemanına haritalanabilir. Bu, asal alanlardan farklıdır; asal alan belirli bir bit sayısı içinde bu tür standart bir gösterim sunamaz. 32-bit asal alan 32-bit içinde yer alabilir, ancak her 32-bit dizesi benzersiz bir alan elemanına karşılık gelmezken, ikili alan bu birbiriyle eşleşme kolaylığına sahiptir. Asal alan Fp'de yaygın olarak kullanılan azaltma yöntemleri Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel azaltma yöntemleridir. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma ) AES'te kullanılan ###, Montgomery azaltması ( POLYVAL'da kullanılan ) ve tekrarlı azaltma ( Tower) bulunmaktadır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetmek" başlıklı makalede, ikili alanların toplama ve çarpma işlemlerinde taşma gerektirmediği ve ikili alanın kare alma işleminin son derece verimli olduğu vurgulanmaktadır; çü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 unsur olarak görülebilir veya iki 64 bitlik kule alan unsuru, dört 32 bitlik kule alan unsuru, on altı 8 bitlik kule alan unsuru veya 128 tane F2 alan unsuru olarak ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümünü gerektirir (typecast), oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama maliyeti olmadan daha büyük alan unsurları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" başlıklı makale, n bitlik kule şeklindeki ikili alanda ( m bitlik alt alan )'ye ayrıştırılarak çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

( 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 açık girdi x'in C)x,ω###=0 devre hesaplama ilişkisini karşılayıp karşılamadığını doğrulayarak devrenin doğru çalıştığını sağlamaktadır.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boole hiperküpündeki değerlendirme sonuçlarının, çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak için bir permütasyon ilişkisi olup olmadığını kontrol eder: f(x) = f(π)x((.

3. LookupCheck: Polinomun değerlendirmesinin verilen bir arama tablosunda olup olmadığını doğrulamak, 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şitliğini kontrol etmek, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, birden fazla küme arasındaki tutarlılığı sağlamak.

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

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole 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 polinomun toplamının 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ğerlendirme sorununa 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 kontrol örneğini yönlendirmek için lineer kombinasyonlar oluşturarak toplu işleme de olanak tanır.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli 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 iyileştirmeler yapmaktadı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ı gerekir; 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 sorunlarının çözümü: HyperPlonk, sıfıra bölme durumlarını yeterince ele alamadı, bu da U'nun hiperküpte sıfırdan farklı olup olmadığını kesinleştiremiyor; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan bir paydada bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genişletilmesine izin veriyor.

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

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şlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıtlama sistemleri için bir temel oluşturdu.

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

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi anahtar teknolojilerden biridir ve giriş kollarından veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturup işlemesini sağlar. Aşağıda iki anahtar yöntem bulunmaktadır:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu pozisyonlardaki daha küçük öğeleri daha büyük öğeler halinde paketleyerek işlemleri optimize eder. Pack operatörü 2κ boyutundaki blok işlemleri için tasarlanmıştır ve bunları yüksek boyutlu alanlarda birleştirir.