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

1 Giriş

STARK'ların verimsizliğinin başlıca sebeplerinden biri, gerçek programlardaki çoğu sayının küçük olmasıdır; ancak Merkle ağaçlarıyla kanıtlamanın güvenliğini sağlamak için Reed-Solomon kodlamasıyla verilerin genişletilmesi sırasında, birçok ek fazlalık değeri tüm alanı kaplar, bu da orijinal değerin kendisi çok küçük olsa bile. Bu sorunu çözmek için alanın boyutunu azaltmak temel 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ı içermektedir. Buna karşın, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup hiçbir israf alanı içermez, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlarla karşılaştırıldığında, 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 katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve döngüsel hash algoritmaları için oldukça uygundur.

Daha küçük bir alan kullanıldığında, genişletme işlemi 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ın genişletmeye girmesine gerek yoktur, yalnızca temel alan altında işlem yaparak küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gereken güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmeyi gerektirir.

İkili alanlar üzerinde bir kanıt sistemi inşa ederken iki pratik sorun vardır: STARKs içinde izlerin temsilini hesaplamak için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs içinde Merkle ağacı taahhüdü yapılırken, Reed-Solomon kodlaması yapılmalı ve kullanılan alanın boyutu, kodlama genişletildikten sonra boyutundan büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alarak 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" (hypercubes) üzerindeki değerleri ile tüm hesaplama izini temsil etti; ikinci olarak, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARK'lar gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare (square) olarak düşünülebilir ve bu kare üzerinden Reed-Solomon genişlemesi gerçekleştirilebilir. 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 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şkilerini 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 olanak tanır; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca birkaç polinomun değerlendirme sonuçlarını sorgulayarak kontrol yapabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunların her biri polinom ifadelerini işleme şekli bakımından farklılık gösterir, 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çerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araçla, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, 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 uygun kullanım alanlarına sahiptir.

Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler seçilerek 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şimi ile oluşturulmuştur ve Pasta eğrisi üzerine inşa edilmiştir. 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 kullanarak Goldilocks alanına dayanmaktadır. Plonky2, verimli bir rekursif gerçekleştirmek amacıyla 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, bu da sistemin doğruluğunu, performansını ve güvenliğini sağlamaktadı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 kurulum olmadan şeffaflık sağlayıp sağlayamayacağını, rekursif kanıt veya toplama kanıtı gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliği ve güvenliği sağlamak için beş anahtar teknolojiyi içermektedir. İlk olarak, kule biçimindeki ikili alanlar (towers of binary fields) üzerine kurulu aritmetik, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş hesaplamalar gerçekleştirmektedir. İkincisi, Binius, etkileşimli Oracle kanıt protokolünde (PIOP), HyperPlonk çarpan ve değiştirme kontrollerini uyarlamış, değişkenler ile bunların permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlamıştır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma 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 alanda verimli bir kanıt sistemi uygulamasını sağlar ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltır.

2.1 Sonlu Alanlar: binary alanlarının kuleleri üzerine yapılan aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır, bu da iki ana sebebe dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temel olarak son derece 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ı, basitleştirilmiş aritmetik süreçleri destekler; yani, ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde temsil edilebilir. Bu özellikler ayrıca, 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 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çinde bu tür standart bir gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize benzersiz bir alan elemanıyla eşlenemez, oysa ikili alan bu birbiriyle eşleşme kolaylığına sahiptir. Asal alan Fp'de yaygın olarak kullanılan 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 arasında özel azaltma (AES'te kullanılan), Montgomery azaltması (POLYVAL'da kullanılan) ve özyinelemeli azaltma (Tower gibi) yer almaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı makale, ikili alanın toplama ve çarpma işlemlerinde taşma gerektiğini belirtmeden çalıştığını ve ikili alanın kare alma işleminin çok verimli olduğunu, çünkü (X + Y )2 = X2 + Y 2 basitleştirilmiş kurallarını izlediğini ifade etmektedir.

Ş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 eşsiz bir eleman olarak düşünü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 maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile sağlanır ve bu oldukça ilginç ve yararlı bir özellik olarak öne çıkar. Aynı zamanda, küçük alan elemanları daha büyük alan elemanları içinde ek bir hesaplama maliyeti olmadan paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özellikten yararlanmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" başlıklı makale, n bitlik kule biçimindeki ikili alanda (m bitlik alt alanlara ayrılabilen) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

2.2 PIOP: HyperPlonk Ürününün ve PermutationCheck'in Uyarlanmış Versiyonu ------ İkili Alan için uygundur

Binius protokolündeki PIOP tasarımı HyperPlonk'tan yararlanarak, polinomların ve çok değişkenli kümelerin doğruluğunu doğrulamak için bir dizi çekirdek kontrol mekanizması kullanmaktadır. Bu çekirdek kontroller şunları içerir:

1. GateCheck: Gizli tanık ω ve açık girdi x'in C(x,ω)=0 devre hesaplama ilişkisini karşılayıp karşılamadığını doğrulamak, devrenin doğru çalıştığından emin olmak için.

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

3. LookupCheck: Verilen bir arama tablosunda polinomun değerinin 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ığı sağlar.

5. ProductCheck: Boolean hiperküp üzerindeki rasyonel çokgenlerin değerinin belirli bir beyan edilen değere ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmek, çokgen çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Boolean hiper küp üzerindeki herhangi bir noktada çok değişkenli bir polinomun sıfır olup olmadığını doğrulamak için ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, polinomun 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ğer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirilmesi sorununu tek değişkenli polinom değerlendirilmesi sorununa dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar tanıtarak birden fazla toplam doğrulama örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli polinomun değerlendirilmesinin 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'in paydası U'nun hiperkü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 problemi ile ilgili işlem: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı ve U'nun hiperküpte sıfırdan farklı olduğu konusunda herhangi bir kesinlik sağlayamadı; Binius bu problemi doğru bir şekilde ele aldı, hatta payda sıfır olduğunda Binius'un ProductCheck'i işlemeye devam edebilir, herhangi bir çarpan değerine genişletmeye izin verir.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değil; 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 çok terimli doğrulamalarını işlerken daha güçlü işlevsellik sağladı. Bu iyileştirmeler sadece HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alanlara dayalı kanıt sistemlerinin temellerini attı.

2.3 PIOP: Yeni çok satırlı 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 kritik teknolojilerden biridir ve giriş kollarından veya diğer sanal çok terimlerden türetilen çok terimlerin etkili bir şekilde üretilmesini ve işlenmesini sağlar. İşte iki ana yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlardaki daha küçük öğeleri daha büyük öğeler halinde paketleyerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan blok işlemleri için tasarlanmıştır ve bunları yüksek boyutlu alanlarda tek bir öğe haline getirir. Çok lineer genişleme ile.