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

1 Giriş

STARKs'ın verimsizliğinin başlıca nedenlerinden biri: gerçek programlardaki çoğu değer oldukça küçüktür, örneğin, for döngüsündeki indeksler, doğruluk değerleri, sayaçlar vb. Ancak, Merkle ağacı kanıtlarının güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verilerin genişletilmesi sırasında birçok ek fazlalık değeri tüm alanı kaplayacaktır, hatta orijinal değer kendisi çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARKs kodlama genişliği 252bit, 2. nesil STARKs kodlama genişliği 64bit, 3. nesil STARKs kodlama genişliği 32bit, ancak 32bit kodlama genişliği hala büyük bir israf alanı barındırmaktadır. Karşılaştırıldığında, ikili alan doğrudan bitlerle işlem yapmaya izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı olmadan, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara 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 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 dayanmakta olup, tekrarlamalara çok uygun bir hash algoritmasıdır.

Küçük bir alan kullanıldığında, genişletme işlemleri 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 polinomların genişletme alanına girmesine gerek yoktur; yalnızca temel alanda işlem yapmaları yeterlidir ve bu sayede küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hala gerekli güvenliği sağlamak için daha büyük bir genişletme alanına inmek zorundadır.

İkili alan temelinde bir kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs içinde izlerin temsilini hesaplamak için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs içinde Merkle ağacı taahhütleri için Reed-Solomon kodlaması yapılması gerektiğinden, kullanılan alan boyutu, kodlamanın genişletilmiş boyutundan büyük olmalıdır.

Binius, bu iki problemi ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı verileri iki farklı şekilde temsil ederek bunu gerçekleştirdi: İlk olarak, çok değişkenli ( ile tek değişkenli polinom yerine çok lineer ) polinomunu kullanarak, "hiperküpler" ( üzerindeki değerlerini alarak tüm hesaplama izini temsil etti; İkincisi, 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 bir 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ırdı.

2 İlke Analizi

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

• Bilgi Teorisi 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 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 az sayıda polinomun değerlendirme sonuçlarını sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi çeşitli protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme biçiminde farklılık gösterir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Protokolü (Polynomial Commitment Scheme, PCS): Polinom taahhüt protokolü, PIOP tarafından üretilen polinom denkleminin geçerliliğini kanıtlamak için kullanılır. PCS, bir şifreleme aracıdır; bununla, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizleyebilir. Yaygın polinom taahhüt protokolleri 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çebilir ve uygun bir sonlu alan veya eliptik eğri ile birleştirerek farklı özelliklere sahip kanıt sistemleri oluşturabilirsiniz. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın ortadan kaldırılmasına odaklanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS kombinasyonunu kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir yineleme gerçekleştirmek için 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, böylece sistemin doğruluğu, performansı ve güvenliği sağlanır. Bu kombinasyonların seçimi yalnızca SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gerektirmeden şeffaflık sağlaması, yineleme kanıtları veya toplama kanıtları gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknolojiyi içermektedir. İlk olarak, kule benzeri ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturmakta olup, ikili alan içinde basitleştirilmiş işlemleri gerçekleştirir. İkinci olarak, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrollerini uyarlayarak, değişkenler ve bunların permütasyonları arasındaki güvenli ve verimli tutarlılık kontrolünü 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ı getirir. 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, küçük alan 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 alanların kuleleri üzerinde hesaplama

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir öneme sahiptir, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temelde yüksek verimli aritmetik işlemleri destekler ve bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, ikili alan üzerinde gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde ifade edilebileceği basitleştirilmiş bir aritmetik süreci destekler. Bu özellikler, kule yapısını tam olarak kullanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "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 haritalanabilir. 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ına karşılık gelmezken, ikili alan bu birbiriyle eşleşme kolaylığına sahiptir. 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öntemleridir. İ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 rekürsif azaltma (, Tower ) gibi yöntemler vardır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı makale, ikili alanın hem toplama hem de çarpma işlemlerinde taşma gerektirmediğini ve ikili alanın kare alma işleminin son derece verimli olduğunu, çünkü (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralını izlediğini belirtmektedir.

Ş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 eleman olarak düşünülebilir veya iki 64 bitlik kule alan elemanı, dört 32 bitlik kule alan elemanı, on altı 8 bitlik kule alan elemanı veya 128 tane 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 gerçekleştirilir, bu da oldukça ilginç ve kullanışlı bir özelliktir. Aynı zamanda, küçük alan elemanları daha büyük alan elemanlarına ekstra hesaplama maliyeti olmadan 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 benzeri ikili alanda( m bitlik alt alana) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

( 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ık ω ve açık girdi x'in, devre hesaplama ilişkisi C)x,ω###=0'ı karşılayıp karşılamadığını doğrulayarak devrenin doğru çalıştığından emin olun.

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

3. LookupCheck: Verilen arama tablosunda çok terimli değerlendirmenin doğruluğunu doğrulamak, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğunu sağlamak.

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: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun bir beyan edilen değer ∏x∈Hµ f(x) = s ile eşit olup olmadığını kontrol edin, böylece polinom çarpımının doğruluğunu sağlamış olun.

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

7. SumCheck: Çok değişkenli çok terimli bir polinomun toplamının, belirtilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol etme. Çok değişkenli polinomun değerlendirme sorununu, tek değişkenli polinom değerlendirme sorununa dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek, birden fazla toplam kontrol örneğinin işlenmesini sağlamak için lineer kombinasyonlar oluşturmayı da mümkün kılar.

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ırmak üzere.

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ı gerekmektedir; 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şleyemiyor ve U'nun hiper küpte sıfır olmayan problemine dair kesin bir yargıya varılamıyor; Binius bu sorunu doğru bir şekilde ele aldı, hatta paydanın sıfır olduğu durumlarda Binius'un ProductCheck'i işlemeye devam edebiliyor ve her türlü çarpım değerine genişletilmesine izin veriyor.

• 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 sıralama durumlarını işleyebilmesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasının geliştirilmesiyle protokolün esnekliğini ve verimliliğini artırdı, özellikle daha karmaşık çok değişkenli polinom doğrulamalarını işlerken daha güçlü işlevsellik sundu. Bu geliştirmeler yalnızca 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 çoklu kaydırma argümanı------boolean hiper kümesine uygundur

Binius protokolünde, sanal polinomların yapımı ve işlenmesi anahtar teknolojilerden biridir ve girdi kollarından veya diğer sanal polinomlardan türetilen polinomları etkin bir şekilde oluşturup işlemesine olanak tanır. İşte iki anahtar yöntem:

• Ambalaj: Bu yöntem aracılığıyla