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

1 Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri şudur: Gerçek programlardaki çoğu sayısal değer oldukça küçüktür, örneğin for döngüsündeki indeksler, doğru/yanlış değerleri, sayaçlar vb. Ancak, Merkle ağacına dayalı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verilerin genişletilmesi sırasında, birçok ek gereksiz değer tüm alanı kaplar, oysaki orijinal değerler kendileri çok küçük olabilir. 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 bit genişliği hala büyük miktarda israf alanı barındırmaktadır. Karşılaştırıldığında, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı olmadan, 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'li yıllara kadar uzanmaktadır. Günümüzde, ikili alan kriptografide yaygın olarak kullanılmakta olup, tipik örnekler şunlardır:

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

• Galois mesaj kimlik 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 F28 alanına dayanan ve SHA-3 finaline giren Grøstl hash fonksiyonu, 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 terimlinin genişletmeye girmesine gerek yoktur, yalnızca temel alanda işlem yaparak küçük alanda 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 inmeyi gerektirir.

İkili alanlara dayalı bir kanıt sistemi inşa edilirken, iki pratik sorun vardır: STARKs'te trace temsilini hesaplamak için kullanılan alan boyutunun, polinomun derecesinden büyük olması gerekir; STARKs'te Merkle ağacı taahhütleri için Reed-Solomon kodlaması yapılması gerektiğinden, kullanılan alan boyutunun kodlama genişletildikten sonraki boyutundan büyük olması gerekir.

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, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak "hiperküpler" üzerindeki değerlerini kullanarak tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare (square) olarak düşünülebilir ve bu kare temel alınarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliğin sağlanmasının yanı sıra, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.

2 Prensip Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki kısmı içerir:

• Bilgi Teorik Polinom Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin çekirdeği 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 aşamalı olarak polinom göndermesine izin vererek, doğrulayıcının yalnızca birkaç polinom değerlendirme sonucunu 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 şekli açısından farklılık gösterir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Şeması (Polynomial Commitment Scheme, PCS): Polinom taahhüt şeması, PIOP tarafından üretilen polinom eşitliğinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bununla birlikte, kanıtlayıcı belirli bir polinoma taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, polinomun diğer bilgilerini gizler. 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 uygulama senaryolarına sahiptir.

Belirli gereksinimlere göre farklı PIOP ve PCS'ler seçerek ve uygun sonlu alan veya eliptik eğrilerle birleştirerek, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile geliştirilen ve Pasta eğrisi temelinde oluşturulmuştur. Halo2 tasarlanırken, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'yi birleştirerek Goldilocks alanına dayanmaktadır. Plonky2, verimli bir özyinelemeyi gerçekleştirmek için tasarlanmıştır. Bu sistemleri tasarlarken, seçilen PIOP ve PCS'nin kullanılan sonlu alan veya eliptik eğri ile eşleşmesi gerekir, böylece sistemin doğruluğu, performansı ve güvenliği sağlanır. Bu kombinasyonların seçimi sadece SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar olmaksızın şeffaflığı gerçekleştirip gerçekleştiremeyeceği, özyinelemeli kanıtlar veya toplu kanıtlar gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş anahtar teknolojiyi içermektedir. Öncelikle, kule tarzı ikili alanlar (towers of binary fields) üzerine inşa edilen aritmetik, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirilmesini sağlar. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve yer değiştirme kontrollerini 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 alanlarda çoklu doğruları doğrulama 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ğlamak için geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi sağlamak ve genellikle büyük alanlarla ilişkili maliyetleri azaltmak için küçük alan çokpolinom taahhüt planını (Small-Field PCS) kullanmaktadır.

2.1 Sınırlı Alan: binary alanların kuleleri temelinde sayısallaştırma

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bu iki ana nedene dayanmaktadır: etkin hesaplama ve etkin aritmetik. İkili alan, temel olarak yüksek derecede 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 alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde ifade edilebileceği basitleştirilmiş bir aritmetik süreçlerini destekler. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemlerine özel olarak 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 alanlar 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 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 bulunmaktadır. İkili alan F2k'de, yaygın olarak kullanılan azaltma yöntemleri özel azaltmalar (örneğin, AES'de kullanılan), Montgomery azaltması (örneğin, POLYVAL'da kullanılan) ve özyinelemeli azaltma (örneğin, Tower) içerir. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı makaleye göre, ikili alan, toplama ve çarpma işlemlerinde taşıma eklemeyi gerektirmez ve ikili alanın kare alma işlemi oldukça etkilidir, çünkü (X + Y )2 = X2 + Y 2'nin basitleştirilmiş kuralını takip eder.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dizi: Bu dizi, ikili alan bağlamında birçok şekilde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir öğe olarak görü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 çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile sağlanır ve son derece ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan öğeleri, ek bir hesaplama yükü olmadan daha büyük alan öğelerine paketlenebilir. 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 biçimindeki ikili alanda (m bitlik alt alanlara ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığı incelenmiştir.

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 çoklu polinomların 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 giriş x'in C(x,ω)=0 devre hesaplama ilişkisini karşılayıp karşılamadığını doğrulamak için, devrenin doğru çalıştığından emin olun.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Boolean hiperkübünde değerlendirilme sonuçlarının permütasyon ilişkisi olup olmadığını doğrulamak için f(x) = f(π(x)) olduğundan emin olun, böylece polinom değişkenleri arasındaki düzen tutarlılığı sağlanır.

3. LookupCheck: Verilen arama tablosunda çok terimli polinomun değerinin doğrulanması, yani f(Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğunu garanti eder.

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: Boolean hiperküp üzerindeki rasyonel çok terimli polinomun bir beyan edilmiş değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol eder, polinom çarpımının doğruluğunu sağlamak için.

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

7. SumCheck: Çok değişkenli çok terimli polinomların toplamının beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol eder. Çok değişkenli polinomların 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 kullanarak birden fazla toplam kontrol örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturmayı mümkün kılar.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinom 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 yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck, paydanın U'nun hiperküpte her yerde sıfır olmamasını ve çarpımın belirli bir değere eşit olmasını gerektirir; 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 çözümü: HyperPlonk, sıfıra bölme durumlarını yeterince ele alamamış ve U'nun hiper küp üzerindeki sıfır olmayan durumu hakkında kesin bir şey söylenememiştir; Binius bu sorunu doğru bir şekilde ele almış, hatta paydanın sıfır olduğu durumlarda bile, Binius'un ProductCheck işlemi devam edebilmekte ve herhangi bir çarpım değerine genişletilmesine izin vermektedir.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu işlevi desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapılmasını destekler, bu da Binius'un daha karmaşık çok terimli sıralama durumlarını ele almasını 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şlenmesinde 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ı ispat sistemlerinin temellerini attı.

2.3 PIOP: Yeni çok çizgili kaydırma argümanı------boolean hiper küp için uygundur

Binius protokolünde, sanal polinomların inşası ve işlenmesi anahtar teknolojilerden biridir ve giriş kollarından veya diğer sanal polinomlardan türetilen polinomları etkili bir şekilde oluşturup işlemesini sağlar. İşte iki anahtar yöntem:

• Paketleme: