Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri

1 Giriş

STARKs'ın düşük verimliliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır; örneğin döngülerdeki indeksler, doğru-yanlış değerleri, sayaçlar vb. Ancak Merkle ağaçlarına dayalı kanıtların güvenliğini sağlamak için, verileri genişletmek amacıyla Reed-Solomon kodlaması kullanıldığında, 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 geldi.

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. Karşılaştırıldığında, ikili alan doğrudan bitler üzerinde 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 sınırlı alan araştırmalarına kıyasla, ikili alan araştırmaları 1980'lere kadar uzanmaktadır. Şu anda, ikili alan 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 ve rekürsif için oldukça uygun bir hash algoritması olan Grøstl hash fonksiyonu, SHA-3 finaline girmiştir.

Küçük alanlar kullanıldığında, genişletme işlemi güvenliğin sağlanmasında giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliğini ve gerçek 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, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmek zorundadır.

İkili alanlar üzerinde kanıt sistemleri inşa ederken, iki pratik sorun vardır: STARKs'ta izin (trace) temsilini hesaplamak için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüdü sırasında, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutu, 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ı verileri iki farklı şekilde temsil etti: İlk olarak, bir değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak "hiperküpler" üzerindeki değerleri kullanarak tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğu için, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare (square) olarak düşünülebilir ve bu kare üzerinden Reed-Solomon genişletmesi gerçekleştirilebilir. Bu yöntem, güvenliği sağlarken kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırmaktadır.

2 Prensip Analizi

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

• Bilgi Teorisi Çok Terimli Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin merkezi olarak, girişteki hesaplama ilişkisini doğrulanabilir çok terimli eşitliklere dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşimde bulunarak, kanıtlayıcının aşamalı olarak çok terimler göndermesine izin verir; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca az sayıda çok terimin değerlendirme sonuçlarını sorgulayarak doğrulama yapabilir. Mevcut PIOP protokolleri arasında PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmakta olup, bunların her biri çok terim ifadelerinin işlenme biçiminde farklılık gösterir ve bu da tüm SNARK sisteminin performansı ve verimliliğini etkiler.

• Polinom Taahhüt Şeması (Polynomial Commitment Scheme, PCS): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denkleminin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografi aracıdır; bu sayede, kanıtlayıcı bir polinom taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonucunu doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizleyebilir. 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 bir kanıt sistemi oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ile Bulletproofs PCS'nin birleşimi ve Pasta eğrisi temelinde oluşturulmuştur. 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 kombinasyonunu kullanarak Goldilocks alanına dayanmaktadır. Plonky2, verimli bir rekursif 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 boyutu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gerektirmeden şeffaflık sağlaması, rekursif kanıtlar veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliği ve güvenliğini sağlamak için beş ana teknoloji içermektedir. İlk olarak, kulesel ikili alanlar (towers of binary fields) temelinde yapılandırılan aritmetik, hesaplamalarının temelini oluşturarak ikili alan içinde basitleştirilmiş işlemler gerçekleştirmesine olanak tanır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde HyperPlonk çarpım ve permütasyon kontrolünü uyarlayarak, değişkenler ve bunların permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol, küçük alanlar üzerinde çoklu doğrusal ilişkilerin doğrulanma 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ş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirebilmesini sağlamak ve genellikle büyük alanlarla ilgili olan maliyetleri azaltmak için küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

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

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynar ve bu iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetizasyon. İkili alan, temelde yüksek verimli aritmetik işlemleri destekler, bu da onu performans hassasiyeti olan kriptografik uygulamalar için ideal bir seçenek haline getirir. Ayrıca, ikili alan yapısı, ikili alan üzerinde gerçekleştirilen işlemlerin kompakt ve kolayca doğrulanabilir cebirsel biçimlerde temsil edilmesine olanak tanıyan basitleştirilmiş bir aritmetizasyon sürecini destekler. Bu özellikler ve kule yapısı aracılığıyla hiyerarşik özelliklerinden tam olarak yararlanabilme yeteneği, ikili alanı Binius gibi ölçeklenebilir kanıtlama sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alan içinde elemanların 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ıları içinde bu tür standart bir temsil sunamaz. 32 bitlik bir asal alan 32 bitlik bir alanda yer alabilirken, her 32 bitlik dizi benzersiz bir şekilde bir alan elemanına karşılık gelmeyebilir. Oysa ikili alan bu birbiriyle eşleşme kolaylığını sunar. Asal alan Fp'de yaygın olan indirgeme yöntemleri arasında Barrett indirgemesi, Montgomery indirgemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel indirgeme yöntemleri bulunur. İkili alanda F2k için, yaygın indirgeme yöntemleri arasında özel indirgeme (AES'te kullanılan), Montgomery indirgemesi (POLYVAL'da kullanılan) ve özyinelemeli indirgeme (Tower gibi) yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" makalesi, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediğini ve ikili alanın kare alma işleminin oldukça verimli olduğunu, çünkü (X + Y )2 = X2 + Y 2'yi izleyen basitleştirilmiş kurallara tabi olduğunu belirtmektedir.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dizi: Bu dizi, ikili alan bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir unsur olarak düşünülebilir veya iki 64 bitlik kule alan unsuru, dört 32 bitlik kule alan unsuru, on altı 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak yorumlanabilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile sağlanır ve oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama yükü olmadan daha büyük alan unsurlarına 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" makalesi, n bitlik kule biçimli ikili alanda (m bitlik alt alanlara ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

2.2 PIOP: Yeniden düzenlenmiş 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ğrulamak için, devrenin doğru çalıştığından emin olun.

2. PermutationCheck: İki değişkenli çok terimli polinom f ve g'nin Boolean hiperküpteki 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 dizilimin tutarlılığını sağlamak amacıyla.

3. LookupCheck: Verilen bir arama tablosunda çok terimli bir ifadenin değerinin doğruluğunu kontrol eder, yani f(Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olur.

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üpteki rasyonel çok terimli fonksiyonun belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmek, çok terimli çarpımın doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean hiperküpteki herhangi bir noktanın 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 ç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ğerlendirme sorununu tek değişkenli polinom değerlendirmesine 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ği için toplu işleme olanak tanır.

8. BatchCheck: SumCheck'e dayalı olarak, çoklu çok değişkenli polinom değerlerinin 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 geliştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in, hiper küp üzerinde her yerde sıfırdan farklı olan bir U paydası gerektirir ve çarpım belirli bir değere eşit olmalıdır; 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 problemiyle ilgili çözüm: HyperPlonk, sıfıra bölme durumunu yeterince ele alamamıştır, bu da U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirlemeyi imkansız kılmıştır; Binius bu durumu doğru bir şekilde ele almıştır, sıfır olan bir paydada bile Binius'un ProductCheck'i işlemeye devam edebilir ve herhangi bir çarpan değerine genişletilmesine izin verir.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değildir; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapılmasını destekler, bu da Binius'un daha karmaşık çok terimli sıralama durumlarını işlemesine olanak tanır.

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 polinom doğrulamalarını işlerken daha güçlü işlevsel destek 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, giriş tutamağından veya diğer sanal polinomlardan türetilen polinomları etkili bir şekilde oluşturup işlemesini sağlayan anahtar teknolojilerden biridir. İşte iki anahtar yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlarda bulunan daha küçük öğeleri daha büyük öğeler haline paketleyerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan blok işlemlerine yöneliktir ve bunları