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

1 Giriş

STARK'ların verimsizliğinin 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, sayacılar vb. Ancak Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında, birçok ek fazlalık değeri tüm alanı kaplar, orijinal değer çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu küçültmek 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 hâlâ büyük miktarda israf alanı bulundurmaktadır. Bununla karşılaştırıldığında, ikili alan doğrudan bitlerle işlem yapmaya olanak tanır, kodlama kompakt ve verimlidir ve herhangi 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 kriptolojide yaygın olarak kullanılmaktadır; tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standartı (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 ve SHA-3 finaline katılan Grøstl hash fonksiyonu, özyinelemeye çok 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 ifadelerin genişletmeye girmesine gerek yoktur, sadece temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hâlâ gerekli güvenliği sağlamak için daha büyük bir genişletilmiş alana derinlemesine inmelidir.

İkili alanlara dayalı kanıt sistemleri inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin hesaplanmasında kullanılan alan büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alan büyüklüğü, kodlama genişletildikten sonraki 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: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak "hiperküpler" üzerindeki değerleri ile tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare olarak değerlendirilerek bu kare üzerinden Reed-Solomon genişlemesi yapılabilir. Bu yöntem, güvenliğin sağlanmasının yanı sıra, kodlama verimliliği 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 bileşeni içerir:

• Bilgi Teorik Polinom Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin merkezinde yer alarak, girişteki 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 birkaç polinomun değerlendirme sonuçlarını sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunlar, polinom ifadelerinin işlenme şekline göre farklılık gösterir, bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Sistemi (Polynomial Commitment Scheme, PCS): Polinom taahhüt sistemi, 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ç sayesinde, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, polinomun diğer bilgilerini gizli tutabilir. Yaygın polinom taahhüt sistemleri arasında KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) ve Brakedown bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulanabilirlik alanlarına sahiptir.

Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler seçilerek uygun 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 olup, Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarlanırken, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ı kaldırmaya odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS kombinasyonunu kullanarak Goldilocks alanına dayanıyor. 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ık 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, etkinliği ve güvenliğini sağlamak için beş ana teknoloji içermektedir. Öncelikle, kuleler halinde ikili alanlar (towers of binary fields) temelinde yapılan aritmetik, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirmektedir. İkinci olarak, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve yer değişim kontrolünü adapte ederek, değişkenler ve bunların yer değişimleri arasındaki güvenli ve etkin tutarlılık kontrolünü sağlamaktadı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ı 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, ikili alan üzerinde etkin bir kanıt sistemi gerçekleştirmesini ve genellikle büyük alanlarla ilişkilendirilen maliyetleri azaltmasını sağlayan küçük alan çoklu terim taahhüt şemasını (Small-Field PCS) kullanmaktadır.

2.1 Sonlu Alanlar: binary alanların kulelerine dayanan aritmetik

Kule tipi 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 aritmetikleştirme. İkili alan, esasen yüksek verimlilikte aritmetik işlemleri destekleyerek, performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline gelir. Ayrıca, ikili alan yapısı, basitleştirilmiş aritmetikleştirme sürecini destekler; yani ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde ifade edilebilir. Bu özellikler, kule yapısını tam olarak kullanarak hiyerarşik özelliklerinden yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical", ikili alan içerisindeki elemanların benzersiz ve doğrudan gösterim 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 karşılık gelebilir. Bu, asal alanlardan farklıdır; asal alanlar belirli bir bit sayısı içinde bu tür bir standart gösterim sunamaz. 32 bitlik bir asal alan 32 bit içinde bulunabilirken, her 32 bitlik dizi benzersiz bir şekilde bir alan elemanına karşılık gelmeyebilir, oysa ikili alan bu birbiriyle eşleşme kolaylığına sahiptir. Asal alan Fp'de, yaygın yeniden düzenleme yöntemleri arasında Barrett yeniden düzenlemesi, Montgomery yeniden düzenlemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel yeniden düzenleme yöntemleri bulunmaktadır. İkili alan F2k'de ise, yaygın yeniden düzenleme yöntemleri arasında özel yeniden düzenleme (AES'te kullanılan), Montgomery yeniden düzenlemesi (POLYVAL'de kullanılan) ve özyinelemeli yeniden düzenleme (Tower) bulunmaktadır. "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 alandaki kare alma işleminin oldukça verimli olduğunu belirtmektedir, çünkü bu işlem (X + Y )2 = X2 + Y2 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 bitlik ikili alandaki benzersiz bir öğe olarak görülebilir veya iki 64 bitlik kule alan öğesi, dört 32 bitlik kule alan öğesi, 16 adet 8 bitlik kule alan öğesi veya 128 adet F2 alan öğesi olarak yorumlanabilir. Bu gösterimin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile mümkündür ve çok ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan öğeleri daha büyük alan öğeleri olarak paketlenebilir ve ek hesaplama maliyeti gerektirmez. 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" makalesi, n bitlik kule benzeri ikili alanda (m bitlik alt alanlara ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

2.2 PIOP: Yenilikçi 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ü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ıklık ω ve kamu girişi x'in, devre hesaplama ilişkisi C(x,ω)=0'ı sağlamasını doğrulamak için, devrenin doğru çalıştığından emin olun.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiper küpü üzerindeki değerlendirme sonuçlarının, çok terimli değişkenler arasındaki sıralama tutarlılığını sağlamak için f(x) = f(π(x)) permütasyon ilişkisi olup olmadığını doğrulamak.

3. LookupCheck: Verilen bir arama tablosunda polinomun değerlendirmesinin 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ığı garanti eder.

5. ProductCheck: Belirli bir ifade değerine ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmek için Boole hiper küpü üzerindeki rasyonel çok terimli polinomun değerlendirilmesini sağlar. Bu, polinom çarpımının doğruluğunu sağlamak içindir.

6. ZeroCheck: Bir çok değişkenli çok terimli ifadenin Boolean hiper küpündeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏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 polinomların toplamının belirtilen değerle eşit olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme problemini tek değişkenli polinom değerlendirme problemine 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 oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, 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üpte her yerde sıfır olmaması ve çarpımın belirli bir değere eşit olması gerekir; Binius, bu değeri 1 olarak özelleştirerek bu kontrol sürecini basitleştirir ve 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 ve U'nun hiper küp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirleyemedi; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan paydalarla bile Binius'un ProductCheck'i devam edebiliyor ve herhangi bir çarpan değerine genişletilmesine izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü gerçekleştirmeyi destekler, bu da Binius'un daha karmaşık çok terimli düzenlemeleri 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 geliştirmeler sadece HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayalı kanıt sistemleri için bir temel oluşturdu.

2.3 PIOP: Yeni çok çizgili kaydırma argümanı------boolean hiper küpüne uygundur

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamacından veya diğer sanal çok terimlerden türetilen çok terimleri etkin bir şekilde oluşturup işlemeye olanak tanır. İşte iki anahtar yöntem:

• Paketleme：