Binius STARKs İlkeleri Analizi ve Optimize Edilmesi Üzerine Düşünceler

1. Giriş

STARK'ların verimsiz olmasının 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, sayıcılar vb. Ancak, Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması ile verileri genişletirken, birçok ek gereksiz değer tüm alanı kaplayacaktır, bu nedenle 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ı bulunmaktadır. Buna karşılık, 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 keşfedilen sonlu alanlarla kıyaslandığında, ikili alan araştırması 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alan kriptolojide 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 birlikte, F28 alanına dayanan ve özyinelemeye çok uygun olan Grøstl hash fonksiyonu, SHA-3 finaline girmiştir.

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 dayanmak zorundadır. Çoğu Prover hesaplamasında yer alan çok terimli ifadeler genişletme alanına girmeden, yalnızca temel alan altında çalışarak 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şletme alanına derinlemesine inmeyi gerektirir.

İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun bulunmaktadır: STARKs'ta iz göstergesinin hesaplandığı alan büyüklüğü, çokpolinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerekmekte olup, kullanılan alan büyüklüğü kodlama genişletildikten sonra büyüklüğünden büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı verileri iki farklı şekilde temsil ederek bunu gerçekleştirdi: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, tüm hesaplama izini temsil etmek için "hiperküpler" (hypercubes) üzerindeki değerlerini kullandı; İkincisi, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp bir kare (square) olarak düşünülebilir 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ırdı.

2. İlkelerin 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 sistemi olarak, 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 aşamalı olarak polinomlar 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ı sorgulayarak kontrol edebilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi farklılık gösteren polinom ifadelerinin işlenme yöntemleri bulunmaktadır, bu da tüm SNARK sisteminin performansını ve verimliliğini etkilemektedir.

• Polinom Taahhüt Şeması (Polynomial Commitment Scheme, PCS): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denkleminin geçerliliğini kanıtlamak için kullanılır. PCS, bir şifreleme aracıdır; bu aracılığıyla, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonucunu doğrulayabilirken, polinomun diğer bilgilerini gizler. 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 gereksinimlere bağlı olarak, 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şimi olup, Pasta eğrisi temel alınmıştır. Halo2 tasarımında, ölçeklenebilirliğe odaklanılmış ve ZCash protokolündeki trusted setup kaldırılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleştirilmesiyle ve Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir rekürsiyon sağlamak için 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ğlanabilir. 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 gerektirmeden şeffaflık sağlamasına, rekürsif kanıtlar veya toplu kanıtlar gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknoloji içerir. Öncelikle, kule biçimindeki ikili alanlara (towers of binary fields) dayalı aritmetik, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirmeyi mümkün kılar. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrollerini uyarlamıştır, bu da değişkenler ile bunların permütasyonları arasındaki güvenli ve verimli tutarlılık kontrolünü sağlar. Üçüncüsü, protokol, küçük alanlar üzerinde çoklu doğrusal ilişkilerin doğrulama verimliliğini optimize eden yeni bir çoklu doğrusal 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ş bir Lasso arama kanıtı kullanmaktadır. 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 masrafları azaltan küçük alan çoklu terim taahhüt planını (Small-Field PCS) kullanmaktadır.

2.1 Sonlu Alan: binary alanların kuleleri üzerine inşa edilen aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bu, iki ana nedenden kaynaklanmaktadır: verimli hesaplama ve verimli aritmetikleştirme. İkili alan, esasen yüksek 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ş aritmetikleştirme süreçlerini destekler; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve kolay doğrulanabilir cebirsel biçimde ifade edilebilir. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanma 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çinde bir öğenin benzersiz ve doğrudan gösterim biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k-bit dizesi doğrudan k-bit ikili alan öğesine eşlenebilir. Bu, asal alanlardan farklıdır; asal alan belirli bir bit sayısı içinde bu tür bir standart gösterim sunamaz. 32 bit asal alan, 32 bit içinde yer alsa da, her 32 bit dizesinin benzersiz bir alan öğesine karşılık gelmesi mümkün değildir; oysa ikili alan bu birer birer eşleme kolaylığını sunar. Asal alan Fp'de, yaygın 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 bulunur. İkili alan F2k'de, yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltmalar (AES'te kullanılanlar), Montgomery azaltmaları (POLYVAL'de kullanılanlar) ve özyinelemeli azaltmalar (Tower gibi) bulunmaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı makalede, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediği ve ikili alanın kare alma işleminin çok verimli olduğu, (X + Y )2 = X2 + Y2 basitleştirilmiş kuralını izlediği belirtilmektedir.

Ş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 düşünü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 ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizesinin tür dönüşümü (typecast) ile sağlanır ve bu, oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan öğeleri, ek bir hesaplama yükü olmaksızın daha büyük alan öğeleri haline 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 biçimindeki ikili alanda (m bit alt alanına ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını tartışmaktadı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ü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ıklama ω ve açık girdi x'in, devre hesaplama ilişkisi C(x,ω)=0'ı sağladığını doğrulamak için kullanılmaktadır. Bu, devrenin doğru çalıştığını garanti eder.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiperküp üzerindeki değerlendirme sonuçlarının bir permütasyon ilişkisi olup olmadığını kontrol eder f(x) = f(π(x)), böylece çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak için.

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şitliğini 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: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun değerlendirilmesinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol ederek, polinom çarpımının doğruluğunu sağlamak.

6. ZeroCheck: Bir çok değişkenli çok terimli ifadenin boolean hiperküp üzerindeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, çok terimli ifadenin sıfır noktalarının dağılımını sağlamak için.

7. SumCheck: Çok değişkenli çok terimli polinomların toplamının belirtilen değer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerleme sorununu tek değişkenli polinom değerleme sorununa dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek çoklu toplam doğrulama örneklerinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturarak toplu işleme de izin verir.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli çok terimli 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 noktada geliş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ı gerekmektedir; Binius, bu değeri 1 olarak özelleştirerek kontrol sürecini basitleştirir ve böylece hesaplama karmaşıklığını azaltır.

• Sıfıra bölme sorunlarının çözümü: HyperPlonk, sıfıra bölme durumlarını yeterince ele alamadı ve U'nun hiper küp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirleyemedi; Binius bu durumu doğru bir şekilde ele aldı, hatta paydanın sıfır olduğu durumlarda bile Binius'un ProductCheck'i işlemeye devam edebilir ve herhangi bir çarpan değerine genelleştirilmesine izin verir.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değildir; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli permütasyon 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şlemleriyle ilgili olarak daha güçlü işlevsel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlılıkları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıt sistemleri için bir temel oluşturdu.

2.3 PIOP: Yeni çoklu kaydırma argümanı------boolean hiperküp için uygundur

Binius protokolünde, sanal polinomların yapılandırılması ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamağından veya diğer sanal polinomlardan türetilen polinomları etkili bir şekilde oluşturup yönetebilme yeteneği sağlar. İşte iki anahtar yöntem:

• Paketleme: