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

1 Giriş

STARKs'ın verimsizliğinin ana nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır. Ancak Merkle ağacı kanıtının güvenliğini sağlamak için Reed-Solomon kodlamasıyla verilerin genişletilmesi sırasında, birçok ek yedek değer tüm alanı kaplar; bu, orijinal değerin kendisi çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu küçültmek ana strateji haline gelmiştir.

1. nesil STARKs kod genişliği 252bit, 2. nesil STARKs kod genişliği 64bit, 3. nesil STARKs kod genişliği 32bit, ancak 32bit kod genişliği hala büyük miktarda israf alanı içermektedir. Karşılaştırıldığında, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimlidir, ayrıca 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ırması 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 dayanıyor;

• Galois mesaj kimlik 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, yinelemeye 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 güvenmek zorundadır. Çoğu Prover hesaplamasında yer alan çok terimlinin genişletmeye girmesi gerekmez, yalnızca temel alanda 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şletmeye derinlemesine inmeyi gerektirir.

İkili alanlara dayalı bir kanıtlama sistemi inşa ederken, iki pratik sorun vardır: STARKs içinde iz temsilini hesaplamak için kullanılan alan büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs içinde Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerekmektedir ve kullanılan alan büyüklüğü, kodlama genişletildikten sonraki 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ı 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ğerleriyle tüm hesaplama yolunu temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküpü kare olarak düşünerek, bu kare temelinde 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 İlkelerin Analizi

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

• Bilgi Teorik Polinomsal Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, bir kanıt sistemi olarak, girişteki hesaplama ilişkisini doğrulanabilir polinom denklemlerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının aşamalı olarak polinom gönderimine 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ı 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 Ş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; bununla birlikte, kanıtlayıcı belirli bir polinoma taahhüt verebilir 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 yapılar bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve kullanım senaryolarına sahiptir.

Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler 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 tasarımında ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'yi bir araya getirir ve Goldilocks alanına dayanır. Plonky2, verimli bir özyineleme sağlamak 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; bu, sistemin doğruluğunu, performansını ve güvenliğini sağlamak için önemlidir. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum olmadan şeffaflık sağlamasını, özyineleme kanıtlarını veya toplu kanıtlar gibi genişletilebilir özellikleri destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius'ın verimliliği ve güvenliği sağlamak için beş anahtar teknoloji içermektedir. Öncelikle, kuleler şeklindeki ikili alanlara (towers of binary fields) dayanan aritmetik, hesaplamanın temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirmektedir. İkincisi, Binius, etkileşimli Oracle kanıtlama protokolünde (PIOP), HyperPlonk çarpımı ve yer değiştirme kontrolünü uyarlayarak, değişkenler ile yer değiştirmeleri arasındaki güvenli ve verimli tutarlılık kontrolünü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu lineer kaydırma kanıtı getirmiştir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sunan geliştirilmiş Lasso arama kanıtını 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 polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

2.1 Sonlu Alanlar: binary alanlarının kuleleri temelinde 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: etkili hesaplama ve etkili aritmatizasyon. İkili alan, özünde yüksek verimli aritmetik işlemleri destekleyerek, performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline gelmektedir. Ayrıca, ikili alan yapısı, sadeleştirilmiş bir aritmatizasyon sürecini destekler; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulaması kolay cebirsel bir formda temsil edilebilir. Bu özellikler, kule yapısını tam olarak kullanabilme yeteneğiyle birlikte, ikili alanı Binius gibi ölçeklenebilir kanıtlama sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alan içindeki bir öğenin benzersiz ve doğrudan gösterim şeklidir. Örneğin, en temel ikili alan olan F2'de, herhangi bir k bitlik dizgi doğrudan k bitlik bir ikili alan öğesine haritalanabilir. Bu, asal alanlardan farklıdır; asal alanlar belirli bir bit sayısı içinde bu tür bir standart gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dizgi benzersiz bir alan öğesine karşılık gelmeyebilir; oysa ikili alan bu birbiriyle eşleştirme kolaylığını sunar. 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'de kullanılan) ve rekürsif azaltma (Tower gibi) yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı makale, ikili alanın toplama ve çarpma işlemlerinde taşma eklemeye ihtiyaç duymadığını belirtmekte ve ikili alanın kare alma işlemlerinin oldukça verimli olduğunu, çünkü (X + Y )2 = X2 + Y2 sadeleştirme kuralına uyduğunu vurgulamaktadır.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: Bu dize, ikili alan bağlamında birçok şekilde yorumlanabilir. 128 bit ikili alanında benzersiz bir öğe olarak görülebilir veya iki 64 bit kule alanı öğesi, dört 32 bit kule alanı öğesi, 16 adet 8 bit kule alanı öğesi veya 128 adet F2 alanı öğesi olarak çözümlenebilir. 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 faydalı bir özelliktir. Aynı zamanda, küçük alan öğeleri, ek bir hesaplama maliyeti olmadan daha büyük alan öğelerine 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" başlıklı makale, n bit kule ikili alanında (m bit alt alanına ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

2.2 PIOP: Uyarlama 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 açık girdi x'in, devre işlem ilişkisi C(x, ω)=0'ı sağlamasını doğrulayarak devrenin düzgün çalıştığını garanti eder.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Boolean hiper küp üzerindeki değer sonuçlarının, çok değişkenli polinomlar arasındaki düzenin tutarlılığını sağlamak için bir yer değiştirme ilişkisi olup olmadığını doğrulamak f(x) = f(π(x)).

3. LookupCheck: Verilen bir arama tablosunda polinomun değerlendirilmesinin doğruluğunu kontrol eder, yani f(Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğunu garantiler.

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: Mantıksal hiper küpte bir rasyonel çok terimli polinomun değerlendirilmesinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s olup olmadığını kontrol eder, böylece çok terimli polinomun çarpımının doğruluğunu sağlar.

6. ZeroCheck: Bir çok değişkenli çok terimli bir polinomun Boolean hiperkübündeki herhangi bir noktanın sıfır olup olmadığını doğrulamak için ∏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ğer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinom 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 doğrulama örneğini topluca işlemek için lineer kombinasyonlar oluşturulmasına da olanak tanır.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli polinomun değerlerinin doğruluğunu doğrulamak için kullanılır ve protokol verimliliğini artırır.

Binius ve HyperPlonk'un protokol tasarımında birçok benzerliği olmasına rağmen, Binius aşağıdaki 3 alanda iyileştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in paydasının 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 bu kontrol sürecini basitleştirmiş ve hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme sorunlarının işlenmesi: HyperPlonk, sıfıra bölme durumunu yeterince işleyemediğinden, U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirleyememektedir; Binius bu sorunu doğru bir şekilde ele almış, paydanın sıfır olması durumunda bile Binius'un ProductCheck'i işlemlere devam edebilmekte ve herhangi bir çarpım değerine yayılmasına izin vermektedir.

• 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 dizilim 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ğrulamaları işlerken daha güçlü işlevsellik sağladı. Bu iyileştirmeler sadece HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıt sistemleri için bir temel oluşturdu.

2.3 PIOP: Yeni çok çizgili kaydırma argümanı ------ Boolean hiper küpe uygundur

Binius protokolünde, sanal polinomların inşası ve işlenmesi önemli tekniklerden biridir ve giriş tutamağından veya diğer sanal polinomlardan türetilen polinomları etkin bir şekilde oluşturup işlemesine olanak tanır. İşte iki ana yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlarda daha küçük öğeleri vurarak