Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri

1 Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri şudur: Gerçek programlardaki çoğu sayı küçüktür, ancak Merkle ağacına dayalı kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması kullanıldığında, verileri genişletirken birçok ek yedek değer tüm alanı kaplar; oysa orijinal değerler kendileri son derece küçüktür. Bu sorunu çözmek için, alanın boyutunu küçültmek ana strateji haline gelmiştir.

1. nesil STARKs kodlama genişliği 252 bit, 2. nesil STARKs kodlama genişliği 64 bit, 3. nesil STARKs kodlama genişliği 32 bit, ancak 32 bit kodlama genişliğinde hala büyük miktarda israf alanı bulunmaktadı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 ve Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alanlar kriptolojide yaygın olarak kullanılmaktadır; tipik örnekler arasında:

• 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 algoritması için son derece 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 terimlilikler genişletmeye girmeden, temel alan altında çalışarak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları yine de gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmelidir.

İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin temsilini hesaplamak için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekmekte olup, kullanılan alanın boyutu kodlama genişletmesinden 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 etti: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerleri ile tüm hesaplama izini temsil etmek; İ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 olarak düşünülebilir ve bu kare üzerinden Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliğin sağlanmasını sağlarken, 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 iki bölüm 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 denklemlerine 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 izin verir, böylece doğrulayıcı az sayıda polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerini işleme biçimi açısından farklılık gösterir ve bu da genel 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 denkleminin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizleyebilir. Yaygın polinom taahhüt planları arasında KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) ve Brakedown gibi seçenekler bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama alanlarına sahiptir.

Belirli ihtiyaçlara göre, farklı PIOP ve PCS'ler seçilerek uygun bir sonlu alan veya eliptik eğri ile birleştirildiğinde, 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 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'nin birleştirilmesiyle ve Goldilocks alanına dayanmaktadır. Plonky2, verimli bir rekürsiyon 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 yalnızca SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir ayar olmadan şeffaflık sağlayıp sağlayamayacağını, rekürsif kanıtlar veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, yüksek verimliliği ve güvenliği sağlamak için beş ana teknolojiyi içermektedir. İlk olarak, kule şekilli ikili alanlar (towers of binary fields) üzerine kurulu aritmetik, hesaplamalarının temelini oluşturarak ikili alan içinde basitleştirilmiş hesaplamalar gerçekleştirmektedir. İkincisi, Binius, etkileşimli Oracle kanıt protokolünde (PIOP), HyperPlonk çarpım ve permütasyon kontrollerini uyarlamıştır, bu da 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, küçük alanlarda çoklu doğrusal ilişkilerin doğrulama verimliliğini optimize eden yeni bir çoklu doğrusal yer değiştirme kanıtı sunmaktadır. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirebilmekte ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltmaktadır.

2.1 Sonlu Alan: Binary Alanların Kuleleri üzerine aritmetik

Kule tipi ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır; bu, iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetizasyon. İkili alan, esasen yüksek verimli aritmetik işlemleri destekler ve bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı basitleştirilmiş bir aritmetizasyon sürecini destekler; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde ifade edilebilir. 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.

"canonical" terimi, ikili alandaki elemanların benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan olan F2'de, herhangi bir k bitlik dize doğrudan k bitlik bir ikili alan elemanına haritalanabilir. Bu, asal alanlardan farklıdır; asal alan belirli bir bit sayısı içinde bu tür bir standart temsili sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilirken, her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmeyebilir; oysa ikili alan bu bir-bir eşleme kolaylığını sunar. Asal alan Fp'de, yaygın olan 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 alanda F2k, yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma (AES'te kullanılan), Montgomery azaltması (POLYVAL'da kullanılan) ve özyinelemeli azaltmalar (Tower gibi) yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" makalesi, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediğini ve ikili alanın kare alma işleminin oldukça verimli olduğunu belirtmektedir; çünkü bu işlem (X + Y )2 = X2 + Y 2 'nin basitleştirilmiş kuralını takip etmektedir.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dizi: Bu dizi, ikilik alanı bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikilik alanında benzersiz bir öğe olarak ele alınabilir veya iki 64 bitlik kule alanı öğesi, dört 32 bitlik kule alanı öğesi, on altı 8 bitlik kule alanı öğesi veya 128 adet F2 alanı öğesi olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile sağlanır; bu, oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan öğeleri, ek hesaplama maliyeti olmaksızın daha büyük alan öğelerine 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" makalesi, n bitlik kule benzeri ikilik alanında (m bitlik alt alanlara ayrılabilir) ç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ü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 hesaplama ilişkisi C(x,ω)=0'ı sağladığını doğrulayarak devrenin doğru çalıştığından emin olun.

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

3. LookupCheck: Verilen bir arama tablosunda çok terimli bir polinomun değerlendirmesinin doğruluğunu kontrol eder, 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: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun bir beyan edilen değer ile eşit olup olmadığını kontrol etme ∏x∈Hµ f(x) = s, polinom çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli çok terimli fonksiyonun Boolean hiperkübesindeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, çok terimli fonksiyonun 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ğere eşit olup olmadığını kontrol etme ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerleme problemini tek değişkenli polinom değerleme problemine dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek çoklu toplam doğrulama örneklerinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturulmasına izin verir.

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

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'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'e ö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 işleyemedi ve U'nun hiperküpte sıfırdan farklı olup olmadığını belirleyemedi; Binius bu sorunu doğru bir şekilde ele aldı, hatta payda sıfır olduğunda bile Binius'in ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genişletmeye 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 dizilim durumlarını ele almasını sağlı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 ç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 sistemlerinin temelini attı.

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

Binius protokolünde, sanal çok terimlerin oluşturulması ve işlenmesi, giriş tutamacından veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturup işleyebilme yeteneği ile temel tekniklerden biridir. İşte iki ana yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlarda daha küçük öğeleri alarak