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

1. Giriş

Eliptik eğri tabanlı SNARK'ların aksine, STARK'lar hash tabanlı SNARK'lar olarak düşünülebilir. Şu anda STARK'ların düşük verimliliğ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ğacı tabanlı kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması kullanıldığında, verilerin genişletilmesi sırasında birçok ek gereksiz değer tüm alanı kaplar, hatta orijinal değerler çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir 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şılık, ikili alan bitlere doğrudan 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 alanlara 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 F28 alanına dayanan Grøstl hash fonksiyonu, SHA-3 finaline giren, yineleme için oldukça uygun bir hash algoritmasıdır.

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 terimli ifadeler genişletmeye girmek zorunda değildir ve yalnızca temel alanda işlem yaparak 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şletmeye derinlemesine girmelidir.

İkili alanlara dayalı bir kanıtlama sistemi inşa ederken, iki pratik sorun vardır: STARKs'te izlerin temsilini hesaplarken, kullanılan alanın boyutu polinomun derecesinden büyük olmalıdır; STARKs'te Merkle ağacı taahhütlerinde, Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alanın boyutu kodlama genişletildikten sonra 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 ederek bunu başardı: Öncelikle, tek değişkenli polinomlar yerine çok değişkenli (özellikle çok lineer) polinomlar kullanarak, "hiperküpler" üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etti; ikincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğu için STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp 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ı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 kademeli olarak polinom göndermesine izin vererek, doğrulayıcının yalnızca birkaç polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulamasını sağlar. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunlar, polinom ifadelerinin işlenme ş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 denklemlerinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli bir polinom üzerinde taahhütte bulunabilir 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 bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama senaryolarına sahiptir.

Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler seçilerek, uygun bir sonlu alan veya eliptik eğri ile bir araya getirilerek, 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 güvenilir kurulumun kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'yi birleştirerek Goldilocks alanına dayanmaktadır. Plonky2, verimli bir özyineleme 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, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar olmadan şeffaflığı sağlaması, özyinelemeli kanıtları veya toplu kanıtlar gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliği ve güvenliği sağlamak için beş ana teknolojiyi içermektedir. Öncelikle, kule biçimindeki ikili alanlar (towers of binary fields) üzerine inşa edilmiş aritmetik, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirmektedir. İkincisi, Binius, etkileşimli Oracle kanıtlama protokolü (PIOP) içinde HyperPlonk çarpan ve yer değiştirme kontrollerini uyarlayarak, değişkenler ile 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 doğrusal ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrusal kaydırma kanıtı getirmektedir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlamak için geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, küçük alan çoklu polinom 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 yükleri azaltmaktadır.

2.1 Sonlu Alanlar: binary fields üzerine kurulu towers of binary fields'in aritmetiği

Kule tipi ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir rol oynamaktadır; bu, iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temel olarak yüksek verimli aritmetik işlemleri desteklediğinden, performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçimdir. Ayrıca, ikili alan yapısı, aritmetik süreçleri basitleştirmeyi destekler; yani, ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde ifade edilebilir. Bu özellikler ve kule yapısı aracılığıyla hiyerarşik özelliklerinden tam olarak yararlanabilme yeteneği, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical" terimi, ikili alandaki elementlerin benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k bitlik dizi doğrudan k bitlik bir ikili alan elemanına eşlenebilir. Bu, asal alandan farklıdır; asal alan belirli bit sayısı içinde bu tür bir standart temsil sağlayamaz. 32 bitlik asal alan 32 bit içinde yer alabilirken, her 32 bitlik dizi benzersiz bir alan elemanına karşılık gelmeyebilir, oysa ikili alan bu birer birer eşleme kolaylığını sunar. Asal alan Fp'de yaygın olan azaltma yöntemleri, Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel azaltma yöntemlerini içerir. İkili alan F2k'de ise yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma (AES'de kullanılan), Montgomery azaltması (POLYVAL'da kullanılan) ve özyinelemeli azaltma (Tower gibi) bulunmaktadır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetmek" başlıklı makalede, ikili alanın toplama ve çarpma işlemlerinde taşıma gerektirmediği ve ikili alanın kare alma işleminin oldukça verimli olduğu belirtilmektedir, çünkü bu (X + Y )2 = X2 + Y 2'nin sadeleştirilmiş kuralını takip eder.

Ş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 alanında 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 tane F2 alanı öğesi olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizesinin tür dönüşümüdür (typecast) ve oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan öğeleri, ek bir hesaplama yükü olmadan daha büyük alan öğeleri olarak 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" adlı makale, n bitlik kule biçimindeki ikili alanlarda (m bitlik alt alanlara ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını tartışmaktadır.

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ıklık ω ve açık giriş x'in, devre hesaplama ilişkisi C(x,ω)=0'ı sağlayıp sağlamadığını doğrulamak için devrenin doğru çalıştığını garanti eder.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Bool hiper küpü üzerindeki değerlendirme sonuçlarının bir permutasyon ilişkisi olup olmadığını doğrular f(x) = f(π(x)), böylece çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlar.

3. LookupCheck: Polinomun değerinin verilen arama tablosunda olup olmadığını 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 hiperküp üzerinde rasyonel çok terimli bir polinomun değerinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol eder, polinom çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli polinomun Boolean hiperküpesindeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏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 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ğerlendirmesine dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck birden fazla toplam kontrol örneğini işlemek için rastgele sayılar getirerek lineer kombinasyon oluşturarak toplu işlem yapılmasına olanak tanır.

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

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ı gerekmektedir; Binius, bu değeri 1 olarak özelleştirerek bu kontrol sürecini basitleştirir ve böylece 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, bu da U'nun hiper küp üzerindeki sıfırdan farklı olma sorununu kesin olarak belirlemeyi mümkün kılmadı; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan payda durumunda bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genişletilmesine izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu işlevi desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli sıralama durumlarını işleyebilmesini sağlar.

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ğrulama işlemlerinde daha güçlü işlevsel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayalı kanıtlama sistemleri için bir temel oluşturdu.

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

Binius protokolünde, sanal polinomların inşası ve işlenmesi anahtar teknolojilerden biridir ve giriş kollarından veya diğer sanal polinomlardan türetilen polinomları etkili bir şekilde oluşturma ve işlemede yetenek sağlar. İşte iki temel yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumların daha küçük olanını kullanarak