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

1 Giriş

Eliptik eğriye dayalı SNARK'lardan farklı olarak, STARK'lar hash tabanlı SNARK'lar olarak düşünülebilir. Mevcut STARK'ları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, boolean değerler, sayaçlar vb. Ancak, Merkle ağacı tabanlı kanıtları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ğer tüm alana yayılır; bu, orijinal değerler çok küçük olsa bile geçerlidir. Bu sorunu çözmek için, alanın boyutunu küçültmek ana strateji haline gelmiştir.

Tablo 1'de gösterildiği gibi, 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ı barındırmaktadır. Buna karşılık, ikili alan doğrudan bitlerle işlem yapılmasına izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı içermez; yani 4. nesil STARKs.

Tablo 1: STARKs Türetilmiş Yolu

| Nesil | Kodlama Genişliği | Temsilci Sistem | |------|----------|----------| | 1. nesil | 252bit | STARK | | 2. Nesil | 64bit | Plonky2 | | 3. nesil | 32bit | Mina | | 4. nesil | 1bit | Binius |

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan sınırlı alan araştırmalarıyla karşılaştırıldığında, ikili alan araştırması 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ı kullanarak
• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve rekürsif hash algoritması için son derece uygundur.

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 bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadeler genişletmeye girmeden, yalnızca temel alanda işlem yapılarak, küçük alanda yüksek verimlilikle gerçekleştirilir. 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 gerektirir.

İkili alanlara dayalı bir kanıtlama sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta iz gösterimini hesaplamak için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüt edilirken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutu, kodlama genişletildikten sonra elde edilen boyuttan 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 ifade ederek bunu gerçekleştirdi: İlk olarak, tek değişkenli polinom yerine çok değişkenli (, özellikle çok lineer ) polinomunu kullanarak, "hiperküpler" ( üzerindeki değerlerini kullanarak tüm hesaplama izini temsil etti; İ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 üzerinde 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 Prensip Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki kısmı içerir:

• Bilgi Teorik Polinom 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 polinom eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının polinomları aşamalı olarak 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 bulunmaktadır; bunlar, polinom ifadelerini işleme yöntemleri bakımından farklılık gösterir ve 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 denkleminin 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 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 şemaları arasında KZG, Bulletproofs, FRI ( Hızlı 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 sonlu alan veya elips eğrisi 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ınarak geliştirilmiştir. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir 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; bu, sistemin doğruluğunu, performansını ve güvenliğini sağlamak için gereklidir. Bu kombinasyonların seçimi, 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 toplu kanıtlar gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliği ve güvenliği sağlamak için beş ana teknolojiyi içermektedir. İlk olarak, kule şeklindeki ikili alanların (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturarak ikili alan içinde basitleştirilmiş işlemlerin gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpan ve permütasyon kontrolünü uyarlayarak, değişkenler ve bunların permütasyonları arasındaki 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ştirmesine olanak tanıyan ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltan küçük alan çoklu polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alan: binary alanların kuleleri temelinde aritmetik

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kilit bir rol oynamaktadır ve bu, iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temel olarak yüksek verimli aritmetik işlemleri destekler ve bu da onu performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, aritmetik işlemlerin ikili alanda gerçekleştirildiği ve kompakt ve doğrulanabilir cebirsel biçimde ifade edilebileceği basitleştirilmiş bir aritmetik süreci destekler. Bu özellikler, kule yapısı aracılığıyla hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile bir araya geldiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical" terimi, ikili alan içindeki bir elemanı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 bir standart 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 gelmeyebilir; oysa ikili alan bu birine bir eşleme kolaylığını sunar. Asal alan Fp'de yaygın yeniden azaltma yöntemleri Barrett yeniden azaltması, Montgomery yeniden azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlara yönelik özel yeniden azaltma yöntemleridir. İkili alan F2k'de yaygın yeniden azaltma yöntemleri arasında AES'de kullanılan özel yeniden azaltma ), POLYVAL'da kullanılan Montgomery yeniden azaltması ### ve Tower ( gibi özyinelemeli yeniden azaltma ) yer almaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı makale, 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 belirtmektedir; çünkü bu işlem (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralını izler.

Ş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 görülebilir veya iki 64 bitlik kule alanı elemanına, dört 32 bitlik kule alanı elemanına, on altı 8 bitlik kule alanı elemanına veya 128 F2 alanı elemanına ayrıştırılabilir. Bu tür bir temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümünü (typecast) gerektirir ve oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan elemanları, ek hesaplama maliyeti olmadan daha büyük alan elemanları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 ikili alanında ('in m bitlik alt alana ) ayrıştırılarak ç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ümenin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:

1. GateCheck: Gizli kanıt ω ve açık girdi x'in C)x, ω(=0 elektrik devresi hesaplama ilişkisini karşılayıp karşılamadığını doğrulayarak devrenin doğru çalışmasını sağlamak.

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

3. LookupCheck: Verilen bir arama tablosunda çok terimli polinomun değerlendirilip değerlendirilmediğini doğrulamak, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirli bir aralıkta olduğunu garanti etmek.

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: Rasyonel çok terimli polinomun Boole hiper küpündeki değerinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol eder, böylece polinom çarpımının doğruluğunu sağlar.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean hiper küpündeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏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 beyan edilen değerle eşit olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinom değerlendirmenin tek değişkenli polinom değerlendirmesine dönüştürülmesiyle doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar kullanarak, birden fazla toplam doğrulama örneğinin grup halinde işlenmesini sağlayan lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinomun değerinin doğruluğunu doğrulamak için 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 U paydasının hiperküpte her yerde sıfır olmaması ve çarpımın belirli bir değere eşit olması gerekir; 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 probleminin çözümü: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı ve U'nun hiperküp üzerindeki sıfır olmayan durumu hakkında kesin bir yargıya varılamadı; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan bir payda durumunda bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genelleme yapılmasına 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 düzenlemeleri 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 çok terimli doğrulamalarda daha güçlü işlevsellik sunmaktadır. Bu geliştirmeler yalnızca HyperPlonk’taki kısıtlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan temelli kanıt sistemleri için bir temel oluşturdu.