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

1 Giriş

STARKs'ın verimsizliğinin 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ç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ı kaplayacaktır, oysa orijinal değer kendisi çok küçüktür. Bu sorunu çözmek için, alanın boyutunu azaltmak ana strateji haline gelmiştir.

Tablo 1'de gösterildiği gibi, 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ı içermektedir. Buna kıyasla, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı olmaksızın, yani 4. nesil STARKs.

Tablo 1: STARKs Türev Yolu

| Cebir | Genişlik | Alan | |------|------|------| | 1. Nesil | 252bit | Asal Alan | | 2. Nesil | 64bit | Goldilocks | | 3. Nesil | 32bit | Asal Alan | | 4. nesil | 1bit | ikili alan |

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alan araştırmaları 1980'lerin başlarına 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 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 bu, özyinelemeli hash algoritmaları için oldukça uygundur.

Küçük alanlar 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 girmek zorunda değildir; yalnızca temel alanda işlem yaparak küçük alanda 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 inmek zorundadır.

İkili alanlara dayalı bir kanıt sistemi kurarken, iki pratik sorun vardır: STARKs'ta izlerin gösterimi için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüt edilmesi sırasında Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutu, kodlama sonrası genişletilmiş boyuttan büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele almak için yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde temsil ederek bunu gerçekleştirdi: Öncelikle, çok değişkenli (, yani çoklu lineer ) polinomları, tek değişkenli polinomlar yerine kullanılmakta ve "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etmektedir; İ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 bir kare ) olarak düşünülebilir ve bu kare temel alınarak 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ırmaktadır.

2 Prensip Analizi

Mevcut çoğu SNARKs sisteminin yapımı genellikle aşağıdaki iki bölümden oluşur:

• Bilgi Teorisi Polinomlu Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin temelini oluşturmakta olup, girişteki hesaplama ilişkisini doğrulanabilir polinom denklemlerine dönüştürmektedir. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının polinomları adım adım göndermesine izin vererek, doğrulayıcının az sayıda polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulamasını sağlamaktadır. Mevcut PIOP protokolleri arasında PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunlar, polinom ifadelerinin işlenme şekli açısından farklılık göstermekte, bu da tüm SNARK sisteminin performansını ve verimliliğini etkilemektedir.

• Çok Terimli Taahhüt Şeması ( Polynomial Commitment Scheme, PCS ): Çok terimli taahhüt şeması, PIOP tarafından üretilen çok terimli eşitliklerin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli bir çok terime taahhüt edebilir ve daha sonra bu çok terimin değerlendirme sonuçlarını doğrulayabilir, aynı zamanda çok terimin diğer bilgilerini gizli tutabilir. Yaygın çok terimli taahhüt şemaları KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown gibi araçlardır. Farklı PCS'ler, farklı performans, güvenlik ve kullanım senaryolarına sahiptir.

Belirli gereksinimlere göre farklı PIOP ve PCS'ler seçerek, 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'nin birleşimi olup, Pasta eğrisi temel alınmıştır. Halo2 tasarımında ö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şimini kullanarak ve Goldilocks alanına dayanmaktadır. Plonky2, verimli bir rekursiyon gerçekleştirmek amacıyla tasarlanmıştır. Bu sistemlerin tasarımında, seçilen PIOP ve PCS'nin kullanılan sonlu alan veya eliptik eğri ile uyumlu olması gerekmektedir, 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 etkilemenin yanı sıra, sistemin güvenilir bir kurulum gerektirmeden şeffaflık sağlaması, 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 teknoloji içermektedir. İlk olarak, kule biçimindeki ikili alanların (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş hesaplamalar yapabilmektedir. İkinci olarak, Binius etkileşimli Oracle kanıt protokolü (PIOP)'unda, HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlamış, değişkenler ile değişim arasındaki güvenli ve verimli tutarlılık kontrolünü sağlamıştır. Üçüncü olarak, protokol küçük alanlarda çoklu doğrusal ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrusal kaydırma kanıtı getirmiştir. Dördüncü olarak, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan 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 şemasını (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alanlar: İkili Alanların Kuleleri Üzerine Arithmetization

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır, bunun başlıca iki nedeni vardır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli 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ı, ikili alan üzerinde 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, kulenin yapısının katmanlı özelliklerinden tam olarak yararlanabilme 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 elemanların 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 elemanına eşlenebilir. Bu, asal alanlardan farklıdır; asal alan belirli bir bit sayısı içinde bu tür bir standart temsil 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 gelmezken, 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 alanlara yönelik özel azaltma yöntemleri bulunur. İkili alan F2k'de yaygın 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" başlıklı makale, ikili alanların toplama ve çarpma işlemlerinde taşma gerektirmediğini ve ikili alanların kare alma işleminin son derece verimli olduğunu belirtmektedir; çünkü bu, (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralını izler.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: Bu dize, ikili alan bağlamında çeşitli şekillerde yorumlanabilir. 128 bit 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 adet F2 alan öğesi olarak ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizesinin tür dönüşümü (typecast) olan çok ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan öğeleri daha büyük alan öğeleri olarak paketlenebilir, ek hesaplama maliyeti olmadan. Binius protokolü, hesaplama verimliliğini artırmak için bu özellikten yararlanmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" adlı makalede, n bitlik kule ikili alanlarının ( m bitlik alt alanlara ) ayrıştırılması durumunda çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığı ele alınmaktadır.

Şekil 1: Kule İkili Alan

( 2.2 PIOP: Uyarlanmış 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ıklama ω ve açık girdi x'in elektrik devresi işlem ilişkisi C)x, ω(=0'ı sağlamasını doğrulamak için, devrenin düzgün çalıştığından emin olun.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Boolean hiperküplerindeki değerlendirme sonuçlarının yer değiştirme ilişkisi olup olmadığını doğrulamak için f)x### = f(π)x(), polinom değişkenleri arasındaki dizilim tutarlılığını sağlamak amacıyla.

3. LookupCheck: Polinomun değerinin verilen arama tablosunda 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şitliğini kontrol eder, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, birden fazla küme arasındaki tutarlılığı sağlar.

5. ProductCheck: Akıllı çok terimli polinomun boolean hiperkübünde bir beyan edilen değerle ∏x∈Hµ f(x) = s olup olmadığını kontrol eder, böylece polinom çarpımının doğruluğunu garanti eder.

6. ZeroCheck: Bir çok değişkenli çok terimliliğin Boolean hiperküresindeki 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 fonksiyonların toplamının, beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol etme. Çok değişkenli polinomların değerleme sorununu, tek değişkenli polinom değerleme 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ğinin toplu işlenmesini sağlamak için lineer kombinasyonlar inşa etmeyi de mümkün kılar.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli polinom değerlemesinin doğruluğunu doğrulayarak 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ü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ştir ve böylece hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme problemiyle ilgili işlem: HyperPlonk sıfıra bölme durumunu yeterince iyi yönetememekte, bu da U'nun hiper küp üzerindeki sıfırdan farklı olduğu durumunu kesinleştiremiyor; Binius bu problemi doğru bir şekilde ele alıyor, sıfır olan bir payda durumunda 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 ö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ı işlemesini 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 polinom doğrulamalarını 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 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 terimlerin oluşturulması ve işlenmesi anahtar öneme sahiptir.