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

1 Giriş

STARKs'in verimsiz olmasının başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu değer oldukça küçüktür, örneğin for döngüsündeki indeksler, doğru/yanlış değerleri, sayıcılar vb. Ancak, Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanarak verileri genişlettiğimizde, birçok ek fazla değer tüm alanı kaplar, oysa orijinal değer kendisi oldukça küçüktür. Bu sorunu çözmek için, alanın boyutunu azaltmak ana 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. Buna göre, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı yoktur, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Günümüzde ikili alan, kriptografi 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 yinelemeli hash algoritmaları için oldukça uygundur.

Küçük bir alan kullanıldığında, genişletme işlemleri güvenliğin sağlanmasında 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 polinomlar genişletmeye girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlamaktadır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hala gereken güvenliği sağlamak için daha büyük bir genişletme alanına inmek zorundadır.

İkili alanlara dayanan bir kanıt sistemi oluştururken, iki pratik sorun vardır: STARKs'ta izlerin temsilini hesaplarken, kullanılan alanın boyutunun polinomun derecesinden büyük olması gerekir; STARKs'ta Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerekmektedir ve kullanılan alanın 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 ifade ederek bunu başardı: İlk olarak, tek değişkenli polinom yerine çok değişkenli ( özellikle çok lineer ) polinom kullanarak, bu polinomun "hiperküpler" ( üzerindeki değerlerini bütün hesaplama izini göstermek için kullandı; İkincisi, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamamaktadır, 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 İlkelerin Analizi

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

• Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin merkezi 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 polinomu aşamalı olarak göndermesine olanak tanır, böylece doğrulayıcı az sayıda polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğruluğunu doğrulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller yer alır ve bunlar polinom ifadelerinin işlenme yöntemleri bakımından farklılık göstererek, 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 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 şemaları arasında KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve kullanım senaryolarına sahiptir.

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

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleştirilmesi ile oluşturulmuş ve Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanmaktadır.

• Plonky2: PLONK PIOP ve FRI PCS'nin bir araya getirilmesi ile 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 kurulum gerektirmeden şeffaflık sağlama kapasitesini ve rekürsif kanıtlar veya toplu kanıtlar gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + binary fields. Spesifik olarak, Binius, yüksek verimliliği ve güvenliğini 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şturarak ikili alan içinde basitleştirilmiş işlemler gerçekleştirme yeteneği sağlamaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde HyperPlonk çarpımı ve yer değiştirme kontrolünü uyarlayarak, değişkenler ile yer değiştirmeleri arasındaki güvenli ve verimli tutarlılık kontrolünü sağlamaktadır. Üçüncü olarak, protokol, küçük alanlarda çok değişkenli ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı getirmektedir. 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, küçük alan çokgen taahhüt şemasını (Small-Field PCS) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmekte ve genellikle büyük alanlarla ilişkili olan masrafları azaltmaktadır.

( 2.1 Sonlu Alan: binary fields üzerindeki towers'a dayalı aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynamaktadır, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekler ve 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 temsil edilebileceği basitleştirilmiş bir aritmetik süreç destekler. Bu özellikler, kule yapısı aracılığıyla 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 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 alan belirli bir bit sayısı içerisinde bu tür bir standart gösterimi sağlayamaz. 32 bitlik bir asal alan 32 bitlik bir alanda yer alabilir, ancak her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmeyebilir; oysa ikili alan bu bir-bir eşleşme kolaylığını sunar. Asal alan Fp'de, yaygın olarak kullanılan indirgeme yöntemleri arasında Barrett indirgemesi, Montgomery indirgemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel indirgeme yöntemleri bulunmaktadır. İkili alan F2k'de, yaygın olarak kullanılan indirgeme yöntemleri arasında AES'te kullanılan özel indirgeme ), POLYVAL'de kullanılan Montgomery indirgemesi ### ve Tower( gibi özyinelemeli indirgeme ) bulunmaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı makale, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediğini ve ikili alanın kare alma işleminin çok verimli olduğunu belirtmektedir; çünkü bu (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralına uyar.

Ş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 eleman olarak veya iki 64 bitlik kule alan elemanı, dört 32 bitlik kule alan elemanı, 16 adet 8 bitlik kule alan elemanı veya 128 adet F2 alan elemanı olarak yorumlanabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümünü (typecast) gerektirir, bu da oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan elemanları, ek bir hesaplama maliyeti olmaksızın daha büyük alan elemanlarına 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ı makale, n bitlik kule benzeri ikili alanda ('in m bitlik alt alana ) ayrıştırılmasıyla çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

( 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 şunlardır:

1. GateCheck: gizli tanık ω ve açık girdi x'in, devre hesaplama ilişkisi C)x,ω(=0'ı karşılayıp karşılamadığını doğrular, böylece devrenin doğru çalıştığından emin olur.

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

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 olunması.

4. MultisetCheck: İki çok değişkenli kümenin eşit olup olmadığını kontrol edin, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, birden fazla küme arasındaki tutarlılığı garanti etmek.

5. ProductCheck: Boolean hiperküp üzerindeki akıllı çok terimli polinomun değerinin belirli bir bildirilen değerle ∏x∈Hµ f(x) = s ile eşit olup olmadığını kontrol etmek, polinom çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean hiperküpteki herhangi bir noktanın sıfır olup olmadığını doğrulamak için ∏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 bir polinomun toplamının beyan edilen değerle eşit olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirmesi haline dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek, birden fazla toplam doğrulama örneği için toplu işlem gerçekleştirmek üzere lineer kombinasyonlar oluşturulmasına izin verir.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli çok terimli polinom değerlemesinin doğruluğunu doğrulamak için, protokol verimliliğini artırır.

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

• Sıfıra bölme problemi ile ilgili çözüm: HyperPlonk sıfıra bölme durumunu yeterince ele alamadı ve U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını belirleyemedi; Binius bu durumu doğru bir şekilde ele aldı, sıfır olan bir paydada bile Binius'un ProductCheck'i işlemeye devam edebiliyor, 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 dizilimleri işlemeye olanak tanıyor.

Binius, mevcut PIOPSumCheck mekanizmasının geliştirilmesi sayesinde protokolün esnekliğini ve verimliliğini artırdı. Özellikle daha karmaşık çok değişkenli polinom doğrulamalarıyla başa çıkarken daha güçlü işlevsel destek sağladı. Bu iyileştirmeler sadece HyperPlonk'taki sınırlamaları çözmekle kalmıyor, aynı zamanda gelecekteki ikili alanlara dayalı kanıt sistemleri için bir temel oluşturuyor.

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

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi önemli tekniklerden biridir ve giriş tutamağı veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturup işlemesine olanak tanır. İşte iki ana yöntem:

• Ambalaj:Bu yöntem aracılığıyla