Binius STARKs İlkeleri 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 küçük olmasıdır; örneğin, for döngüsündeki indeksler, doğru/yanlış değerleri, sayaçlar vb. Ancak, Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması kullanıldığında, verilerin genişletilmesi sırasında birçok ek fazlalık değeri tüm alanı kaplayacaktır, bu da orijinal değerin kendisi çok küçük olsa bile. Bu sorunu çözmek için alanın boyutunu azaltmak anahtar 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 genişliği hala büyük miktarda israf alanı içermektedir. Buna karşılık, ikili alan bitlere doğrudan işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı içermez, 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 geniş bir şekilde kullanılmaktadır, tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standardı (AES), F28 alanına dayanı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 giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve özyinelemeli hash algoritması için oldukça uygundur.

Küçük bir alan kullanıldığında, genişletme işleminin güvenliğin sağlanmasında giderek daha önemli hale geldiği görülmektedir. 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 polinomlar genişletmeye girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlamaktadı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 girmeyi gerektirmektedir.

İkili alan üzerine kanıt sistemleri inşa ederken iki gerçek sorun vardır: STARKs'ta trace temsilini hesaplamak için kullanılan alanın, polinomun derecesinden büyük olması gerekir; STARKs'ta Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alanın, kodlama genişletildikten sonra büyüklüğünden büyük olması gerekir.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde temsil ederek bunu başardı: Öncelikle, çok değişkenli (, özellikle çoklineer ) polinomunu tek değişkenli polinom yerine kullanarak, "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil ediyor; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp 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ırmaktadır.

2. İlke Analizi

Mevcut ç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şturur ve girdi 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 olanak tanır, 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 bulunmaktadır ve bunların her biri polinom ifadelerini işleme şekli bakımından farklılık gösterir, bu da genel SNARK sisteminin performansı 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, 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 gizli tutabilir. 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 birleştirilerek, farklı özelliklere sahip bir kanıt sistemi oluşturulabilir. Örneğin:

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

• Plonky2: PLONK PIOP ve FRI PCS kombinasyonu ile Goldilocks alanına dayanmaktadır. Plonky2, yüksek verimli yinelemeyi 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 kurulum olmaksızın şeffaflık sağlayıp sağlayamayacağını ve yineleme kanıtları veya toplu kanıtlar gibi genişletilmiş işlevleri destekleyip destekleyemeyeceğ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, kule biçimindeki ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemleri gerçekleştirmektedir. İkinci olarak, Binius'un etkileşimli Oracle kanıtlama protokolü (PIOP), HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlayarak, değişkenler ve bunların yer değiştirmeleri arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncü olarak, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu lineer kaydırma kanıtı sunmaktadır. 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 verimli bir kanıt sistemi sağlamak için küçük alan çoklu polinom taahhüt şemasını (Small-Field PCS) kullanmakta ve genellikle büyük alanlarla ilişkili olan masrafları azaltmaktadır.

( 2.1 Sınırlı Alan: binary alanların kuleleri temelinde aritmatizasyon

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynamaktadır ve bu, iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, yüksek verimli aritmetik işlemleri desteklemesi nedeniyle, performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçimdir. Ayrıca, ikili alan yapısı, basitleştirilmiş bir aritmetik süreç destekler; yani, ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel formlarda temsil edilebilir. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanma kabiliyeti ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Buradaki "canonical", ikili alan içerisindeki unsurları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 unsuruna eşlenebilir. Bu, asal alanlardan farklıdır; asal alan, belirli bir bit sayısı içinde bu tür bir standart gösterimi sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilse de, her 32 bitlik dize benzersiz bir alan unsuruna karşılık gelmezken, ikili alan bu birbiriyle eşleşme 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 azaltma ), AES'de kullanılan ###, Montgomery azaltması (, POLYVAL'de kullanılan ) ve tekrarlayan azaltma (, Tower) gibi yöntemler yer alır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetme" başlıklı makale, ikili alanın toplama ve ç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 öğe olarak değerlendirilebilir veya iki 64 bitlik kule alan öğesi, dört 32 bitlik kule alan öğesi, on altı 8 bitlik kule alan öğesi veya 128 tane F2 alan öğesi olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizesinin tür dönüşümünü (typecast) gerektirir, bu da oldukça ilginç ve kullanışlı bir özellik. Aynı zamanda, küçük alan öğeleri, ek 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 bitlik kule biçimindeki ikili alanda ( m bitlik alt alana ) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

( 2.2 PIOP: Uyarlanmış HyperPlonk Ürünü ve Permutasyon Kontrolü------ İkili alan için uygundur

Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almış ve çoklu polinomların 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 hesaplama ilişkisi C)x,ω###=0'ı sağladığını doğrulamak için devrenin doğru çalıştığını temin etmek.

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

3. LookupCheck: Verilen arama tablosunda polinomun değerlendirmesinin doğrulanması, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olmak.

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

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 noktalarının dağılımını sağlamak için.

7. SumCheck: Çok değişkenli çok terimli polinomların toplam değerinin beyan edilen değer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomların 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ğini işleme almayı sağlayan lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinomun 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 paydası U'nun hiperküp üzerinde 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 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ı olma durumunu belirleyemedi; Binius bu sorunu doğru bir şekilde ele aldı, sıfır paydasında bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genelleme yapmaya 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ı ele almasını 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 polinom doğrulamalarını işlerken daha güçlü işlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayanan kanıt sistemleri için bir temel oluşturdu.

( 2.3 PIOP: yeni çok çizgili kaydırma argümanı------boolean hypercube için uygun

Binius protokolünde, sanal çok terimli ifadelerin oluşturulması ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamağından veya diğer sanal çok terimli ifadelerden türetilen çok terimlileri etkili bir şekilde oluşturup işlemesine olanak tanır. İşte iki anahtar yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu pozisyonlardaki daha küçük öğeleri daha büyük öğeler halinde paketleyerek işlemleri optimize eder. Pack operatörü 2κ boyutundaki blok işlemleri hedef alır ve bunları birleştirir.