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

1 Giriş

STARKs'in verimsizliğinin başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu sayısal değer oldukça küçüktür, ancak Merkle ağacı kanıtlarının güvenliğini sağlamak için Reed-Solomon kodlamasıyla verilerin genişletilmesi sırasında, birçok ek gereksiz değer tüm alanı kaplar, hatta orijinal değer kendisi çok küçük olsa bile. 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ğinde hala büyük ölçüde israf alanı mevcuttur. Buna karşılık, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup hiçbir israf alanı yoktur, 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 alanlar kriptografide 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 yeniden uygulama için çok uygun bir hash algoritmasıdır.

Küçük bir alan kullanıldığında, genişletme işlemi güvenliğin sağlanması 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 dayanmak zorundadır. Çoğu Prover hesaplamasında yer alan polinomlar genişletme alanına girmek zorunda değildir ve 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 inmek zorundadır.

İkili alanlar üzerinde bir kanıt sistemi oluştururken 2 pratik sorun vardır: STARKs'ta iz gösterimini hesaplamak için kullanılan alanın büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüdü için Reed-Solomon kodlaması yapılması gerektiğinde, kullanılan alanın büyüklüğü kodlama genişletildikten sonra olan 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: Öncelikle, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküp" (hypercubes) üzerindeki değerleri ile tüm hesaplama yolunu temsil etti; ikinci olarak, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare (square) olarak değerlendirilebilir 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ırmıştır.

2 Prensip Analizi

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

• Bilgi Teorik Polinom Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin temelini oluşturarak, 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 adım adım polinom göndermesine izin verir; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca az sayıda polinomun değerlendirme sonuçlarını sorgulayarak kontrol edebilir. Mevcut PIOP protokolleri arasında PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi farklılıklar vardır; bunlar polinom ifadelerinin işlenme şekline bağlı olarak, 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 şifreleme aracıdır; bu araç sayesinde, kanıtlayıcı bir polinoma taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, polinomun diğer bilgilerini gizli tutar. Yaygın polinom taahhüt şemaları 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 senaryolarına sahiptir.

Belirli ihtiyaçlara göre, farklı PIOP ve PCS'leri seçerek ve 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 üzerine inşa edilmiştir. Halo2 tasarlanırken, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın ortadan kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleştirilmesiyle ve Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir geri dönüşüm sağlamak amacıyla tasarlanmıştır. Bu sistemlerin tasarımında 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, SNARK'ın kanıt boyutu ve doğrulama verimliliğini sadece etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gerektirmeden şeffaflık sağlayıp sağlayamayacağını, geri dönüşüm kanıtları veya toplama kanıtları gibi genişletilmiş işlevleri destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliği ve güvenliği sağlamak için beş ana teknoloji içermektedir. İlk olarak, kule benzeri ikili alanlar (towers of binary fields) temelinde aritmetiklemesi, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirmektedir. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpan ve yer değiştirme kontrolünü uyarlayarak değişkenler ve bunların yer değiştirmeleri arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkileri doğrulama verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı tanıtmaktadır. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını benimsemektedir. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesini sağlayan ve genellikle büyük alanlarla ilişkili olan yükleri azaltan küçük alan çoklu polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

2.1 Sonlu Alan: binary alanların kuleleri üzerine kurulu aritmetik

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bunun başlıca iki nedeni vardır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekleyerek performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline gelmektedir. Ayrıca, ikili alan yapısı, basitleştirilmiş bir aritmetik süreç desteklemektedir; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir. Bu özellikler, kule yapısı aracılığıyla hiyerarşik özelliklerini tam olarak kullanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirmektedir.

Burada "canonical", ikili alan içinde bir elemanın benzersiz ve doğrudan gösterim biçimini ifade eder. Örneğin, en temel ikili alan F2 içinde, herhangi bir k-bit dizesi doğrudan k-bit ikili alan elemanına eşlenebilir. Bu, asal alanlardan farklıdır; asal alanlar belirli bir bit sayısında bu tür bir standart gösterim sunamaz. 32-bit asal alan 32-bit içinde yer alabilir, ancak her 32-bit dizesinin benzersiz bir alan elemanına karşılık gelmesi mümkün değildir, oysa ikili alan bu bir-bir eşleme kolaylığını sağlar. Asal alan Fp'de yaygın 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 bulunur. İkili alan F2k'de yaygın indirgeme yöntemleri arasında özel indirgemeler (AES'de kullanılan), Montgomery indirgemesi (POLYVAL'de kullanılan) ve özyinelemeli indirgeme (Tower gibi) yer alır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetme" 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ını izler.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: Bu dize, ikili alan bağlamında birden fazla şekilde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir eleman olarak görülebilir 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 ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü olmaksızın sadece bit dizesinin tür dönüşümü (typecast) ile mümkündür ve oldukça ilginç ve yararlı bir özelliktir. Ayrıca, küçük alan elemanları, ek bir hesaplama yükü 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" makalesi, n bitlik kule yapıdaki ikili alanda (m bitlik alt alanlara ayrılabilen) ç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 ilham almış olup, çok terimli ve çok değişkenli küme 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 işlemi ilişkisi C(x,ω)=0'ı karşılayıp karşılamadığını doğrulayarak devrenin düzgün çalışmasını sağlamak.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boole hiperküresinde 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ı doğrulamak için f(x) = f(π(x)).

3. LookupCheck: Verilen arama tablosunda çok terimli ifadelerin değerlendirilip değerlendirilmediğini doğrulamak, yani f(Bµ) ⊆ T(Bµ), belirli değerlerin belirlenen aralıkta olduğundan emin olmak.

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 hiper küp üzerindeki akılcı çok terimli polinomun değerlendirilmesinin belirli bir bildirilmiş değere eşit olup olmadığını kontrol etme ∏x∈Hµ f(x) = s, polinomun çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli polinomun Boolean hiperküpü üzerindeki 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ı güvence altına almak için.

7. SumCheck: Çok değişkenli polinomların toplamının belirtilen değer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme problemini tek değişkenli polinom değerlendirmesine 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 doğrulama örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturmayı da mümkün kılar.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli çok terimli polinomun değerlendirilmesinin doğruluğunu doğrular ve 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'in paydası U'nun hiper küp üzerinde her yerde sıfırdan farklı olması 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ş ve hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme problemiyle ilgili işlem: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı ve U'nun hiperküpte sıfırdan farklı olup olmadığına dair kesin bir ifade vermek mümkün olmadı; Binius bu problemi doğru bir şekilde ele aldı ve Binius'un ProductCheck'i, paydanın sıfır olduğu durumlarda bile devam edebilir, herhangi bir çarpan değerine genişletilmesine izin verir.

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

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ğrulaması yaparken daha güçlü işlevsellik desteği sağladı. Bu iyileştirmeler, HyperPlonk'taki sınırlamaların üstesinden gelmekle kalmayıp, aynı zamanda gelecekte ikili alanlara dayalı kanıt sistemleri için bir temel oluşturdu.

2.3 PIOP: Yeni çoklu 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 anahtar teknolojilerden biridir ve giriş tutamağından veya diğer sanal çok terimlerden türetilen çok terimlerin etkili bir şekilde üretilmesini ve işlenmesini sağlar. Aşağıda iki anahtar yöntem bulunmaktadır:

• Paketleme: Bu yöntem, sözlük sırasındaki bitişik konumlardaki daha küçük elemanları kullanarak