Orijinal başlık: " STARK çemberini keşfetmek "

Yazan: Vitalik Buterin, Ethereum'un kurucu ortağı

Derleyen: Chris, Techub Haberleri

Bu makaleyi anlamanın ön koşulu, SNARK'ların ve STARK'ların temel prensiplerini zaten anlamış olmanızdır. Eğer bu konuya aşina değilseniz, temelleri anlamak için bu makalenin ilk birkaç bölümünü okumanızı öneririm.

Son yıllarda STARK'ın protokol tasarımındaki eğilim daha küçük alanların kullanılması yönünde olmuştur. STARK'ların en eski üretim uygulamaları, bu protokolleri eliptik eğri tabanlı imzalarla uyumlu hale getiren 256 bitlik alanlar, çok sayıda modülo aritmetiği (21888...95617 gibi) kullanıyordu. Ancak bu tasarımın verimliliği nispeten düşüktür. Normal koşullar altında bu büyük sayıları işlemenin ve hesaplamanın pratik bir kullanımı yoktur ve X'in (belirli bir sayıyı temsil eden) işlenmesi ve X'in dört katının işlenmesi gibi çok fazla hesaplama gücü israfına neden olur. , işleme Hesaplama süresinin yalnızca dokuzda biri gereklidir. Bu sorunu çözmek için STARK'lar daha küçük alanlar kullanmaya yönelmeye başladı: önce Goldilocks , ardından Mersenne31 ve BabyBear .

Bu değişim, Starkware'in bir M3 dizüstü bilgisayarda saniyede 620.000 Poseidon2 karma değerini kanıtlayabilmesi gibi gelişmiş kanıt hızlarına sahip oldu. Bu, karma işlevi olarak Poseidon2'ye güvenmeye istekli olduğumuz sürece, verimli ZK-EVM geliştirmenin zor sorununu çözebileceğimiz anlamına gelir. Peki bu teknolojiler nasıl çalışıyor? Bu kanıtlar daha küçük alanlara nasıl dayanıyor? Bu protokoller Binius gibi çözümlerle nasıl karşılaştırılır? Bu makale, Mersenne31 alanlarıyla uyumlu olma gibi benzersiz bir özelliğe sahip olan Circle STARK'lar ( Starkware'in stwo'sunda , Polygon'un plonky3'ünde ve Python'daki kendi sürümümde uygulanmıştır) adı verilen bir şemaya odaklanarak bu ayrıntıları inceleyecektir.

Daha küçük matematik alanlarıyla çalışırken sık karşılaşılan sorunlar

Karma tabanlı kanıtlar (veya herhangi bir türde kanıt) oluştururken çok önemli bir püf noktası, polinomu rastgele noktalarda değerlendirerek bir polinomun özelliklerini dolaylı olarak doğrulayabilmektir. Bu yaklaşım ispat sürecini büyük ölçüde basitleştirebilir, çünkü rastgele noktalarda değerlendirme genellikle polinomun tamamıyla uğraşmaktan çok daha kolaydır.

Daha küçük matematik alanlarıyla çalışırken sık karşılaşılan sorunlar

Karma tabanlı kanıtlar (veya herhangi bir türde kanıt) oluştururken çok önemli bir püf noktası, polinomu rastgele noktalarda değerlendirerek bir polinomun özelliklerini dolaylı olarak doğrulayabilmektir. Bu yaklaşım ispat sürecini büyük ölçüde basitleştirebilir, çünkü rastgele noktalarda değerlendirme genellikle polinomun tamamıyla uğraşmaktan çok daha kolaydır.

Örneğin, bir ispat sisteminin, A^3 (x) + x - A (\omega*x) = x^N (ZK'de çok yaygın olan) koşullarını karşılaması gereken bir A polinomuna yönelik bir taahhüt oluşturmanızı gerektirdiğini varsayalım. -SNARK protokolü kanıt türü). Protokol sizden rastgele bir koordinat 𝑟 seçmenizi ve A (r) + r - A (\omega*r) = r^N olduğunu kanıtlamanızı isteyebilir. Sonra A (r) = c'yi ters çevirin ve Q = \frac {A - c}{X - r}'nin bir polinom olduğunu kanıtlarsınız.

Protokollerin ayrıntılarını veya iç kısımlarını önceden biliyorsanız, bunları atlamanın veya hacklemenin yollarını bulabilirsiniz. Bunu başarmak için spesifik eylemler veya yöntemlerden daha sonra bahsedilebilir. Örneğin, A (\omega * r) denklemini sağlamak için A (r)'yi 0'a ayarlayabilir ve ardından A'nın bu iki noktadan geçen düz bir çizgi olmasına izin verebilirsiniz.

Bu saldırıları önlemek için saldırgan A ( Fiat-Shamir) 'i sağladıktan sonra r'yi seçmemiz gerekiyor. Belirli parametreleri bazı hash değerlerine ayarlayarak saldırıları önlemek için protokolün güvenliğini artırmak için kullanılan bir tekniktir. Parametrelerin nereden gelmesi gerektiğini seçin. Saldırganın bu parametreleri tahmin edememesini veya tahmin edememesini sağlayacak kadar geniş bir set, böylece sistemin güvenliğini artırır.

2019 dönemindeki eliptik eğri tabanlı protokollerde ve STARK'larda sorun basittir: tüm matematik işlemlerimiz 256 bitlik sayılar üzerinde gerçekleştirilir, dolayısıyla r'yi rastgele 256 bitlik bir sayı olarak seçebiliriz, böylece . Ancak daha küçük alanlardaki STARK'larda bir sorunla karşılaşıyoruz: r'nin seçilebilecek yalnızca 2 milyar olası değeri var, bu nedenle sahte kanıt oluşturmak isteyen bir saldırganın yalnızca 2 milyar kez denemesi gerekiyor; çok iş var ama kararlı bir saldırgan için bu hala tamamen mümkün!

Bu sorunun iki çözümü var:

Birden fazla rastgele kontrol gerçekleştirmenin en basit ve en etkili yolu şudur: tek bir koordinatta kontrol etmek yerine kontrolü dört rastgele koordinatta tekrarlayın. Bu teorik olarak mümkün ancak verimlilik sorunları var. Derecesi belirli bir değerin altında olan bir polinomla uğraşıyorsanız ve belirli bir boyuttaki bir etki alanı üzerinde çalışıyorsanız, bir saldırgan aslında bu konumlarda normal görünen kötü niyetli bir polinom oluşturabilir. Bu nedenle, protokolü başarılı bir şekilde kırıp kıramayacakları olasılıksal bir sorudur; dolayısıyla genel güvenliği artırmak ve saldırganların saldırılara karşı etkili bir şekilde savunulabilmesini sağlamak için kontrol turlarının sayısının artırılması gerekir.

Bu başka bir çözüme yol açar: Genişletilmiş alanlar karmaşık sayılara benzer ancak sonlu alanlara dayanır. α\alphaα olarak gösterilen yeni bir değer getiriyoruz ve bunun α2=bir değer\alpha^2 = \text {bir değer}α2=bir değer gibi belirli bir ilişkiyi karşıladığını beyan ediyoruz. Bu sayede sonlu alanlar üzerinde daha karmaşık işlemleri gerçekleştirebilen yeni bir matematiksel yapı oluşturuyoruz. Bu genişletilmiş alanda, çarpmanın hesaplanması yeni α\alphaα değerini kullanan bir çarpma haline gelir. Artık sadece tek sayılar değil, genişletilmiş bir alandaki değer çiftleri üzerinde çalışabiliyoruz. Örneğin Mersenne ya da BabyBear gibi bir alanda çalışıyorsak böyle bir uzantı bize daha fazla değer seçeneği sunarak güvenliği artırıyor. Alan boyutunu daha da artırmak için aynı tekniği tekrar tekrar uygulayabiliriz. α\alphaα'yı zaten kullandığımız için, Mersenne31'de α2=bir değer\alpha^2 = \text {bir değer}α2=bir değer olacak şekilde α\alphaα seçilerek temsil edilen yeni bir değer tanımlamamız gerekir.

Kod ( Karatsuba ile geliştirebilirsiniz)

Kod ( Karatsuba ile geliştirebilirsiniz)

Etki alanını genişleterek artık güvenlik ihtiyaçlarımızı karşılayacak yeterli değere sahip oluyoruz. Ddd'den daha düşük dereceli polinomlarla uğraşıyorsanız, her tur 104 bitlik güvenlik sağlayabilir. Bu yeterli güvenliğe sahip olduğumuz anlamına gelir. 128 bit gibi daha yüksek bir güvenlik düzeyi gerekiyorsa, güvenliği artırmak için protokole bazı ek hesaplama çalışmaları ekleyebiliriz.

Genişletilmiş etki alanı aslında yalnızca FRI (Fast Reed-Solomon Interactive) protokolünde ve rastgele doğrusal kombinasyonlar gerektiren diğer senaryolarda kullanılır. Matematiksel işlemlerin çoğu halen modulo ppp veya qqq alanları olan temel alanlar üzerinde gerçekleştirilmektedir. Ayrıca karma oluşturma işlemi uygulanmış verilerin neredeyse tamamı temel alanlarda yapılır, dolayısıyla değer başına yalnızca dört bayt karma oluşturma işlemine tabi tutulur. Bunu yapmak, küçük alanların verimliliğinden yararlanırken, güvenlik iyileştirmelerine ihtiyaç duyulduğunda daha büyük alanların kullanılmasına da olanak tanır.

Normal Cuma

Bir SNARK veya STARK oluştururken ilk adım genellikle aritmetizasyondur. Bu, herhangi bir hesaplama probleminin bazı değişkenlerin ve katsayıların polinom olduğu bir denkleme dönüştürülmesidir. Spesifik olarak, bu denklem tipik olarak P (X,Y,Z)=0P (X,Y,Z) = 0P (X,Y,Z)=0 gibi görünecektir; burada P bir polinomdur ve Z belirli bir parametredir ve çözücünün X ve Y değerlerini sağlaması gerekir. Böyle bir denklem elde ettiğinizde, bu denklemin çözümü, altta yatan hesaplama probleminin çözümüne karşılık gelir.

Bir çözüme sahip olduğunuzu kanıtlamak için, bulduğunuz değerlerin gerçekten meşru polinomlar olduğunu (kesirlerin aksine veya bazı yerlerde tek bir polinom, diğerlerinde farklı bir polinom gibi göründüğünü vb.) göstermeniz gerekir. Ve bu polinomların belli bir maksimum derecesi vardır. Bunu yapmak için adım adım uygulanan stokastik doğrusal kombinasyon tekniğini kullanıyoruz:

Esas itibarıyla olan şey, B'nin A çift katsayılarını izole etmesi ve 𝐶'nin tek katsayıları izole etmesidir. B ve C verildiğinde, orijinal A polinomunu kurtarabilirsiniz: A (x) = B (x^2) + xC (x^2). Eğer A'nın derecesi gerçekten 2^{20}'den küçükse, o zaman B ve C'nin dereceleri sırasıyla A'nın derecesi ve A'nın derecesi eksi 1 olacaktır. Çünkü çift ve tek terimlerin birleşimi dereceyi arttırmaz. D, B ve C'nin rastgele doğrusal birleşimi olduğundan, D'nin derecesi aynı zamanda A'nın derecesi olmalıdır; bu, A'nın derecesinin D derecesi aracılığıyla gereksinimleri karşılayıp karşılamadığını doğrulamanıza olanak tanır.

İlk olarak FRI, polinomun d derecesine sahip olduğunu kanıtlama problemini polinomun d/2 derecesine sahip olduğunu kanıtlama problemine indirgeyerek doğrulama sürecini basitleştirir. Bu işlem birçok kez tekrarlanabilir ve her seferinde sorunu yarı yarıya basitleştirir.

FRI bu basitleştirme sürecini tekrarlayarak çalışır. Örneğin, bir polinomun derecesinin d olduğunu kanıtlayarak başlarsanız, bir dizi adımla sonunda polinomun derecesinin d/2 olduğunu kanıtlayacaksınız. Her basitleştirmeden sonra elde edilen polinomun derecesi giderek azalır. Bir aşamanın çıktısı beklenen polinom derecesinde değilse, bu kontrol turu başarısız olacaktır. Birisi bu teknikle d derecesi olmayan bir polinomu zorlamaya çalışırsa, o zaman çıktının ikinci turunda derecesi belirli bir olasılıkla beklentileri karşılamayacak, üçüncü turda ise tutarsız olma olasılığı daha yüksek olacaktır, ve son olarak Kontrol başarısız olacaktır. Bu tasarım, gereksinimleri karşılamayan girdiyi etkili bir şekilde algılayabilir ve reddedebilir. Veri seti çoğu konumda d dereceli bir polinoma eşitse, veri setinin FRI doğrulamasını geçmesi muhtemeldir. Ancak böyle bir veri seti oluşturmak için saldırganın gerçek polinomları bilmesi gerekir, dolayısıyla biraz kusurlu bir kanıt bile kanıtlayıcının "gerçek" bir kanıt üretebildiğini gösterir.

Burada neler olup bittiğine ve bunların işe yaraması için gereken özelliklere daha yakından bakalım. Her adımda polinomun derecesini yarı yarıya azaltıyoruz ve ayrıca noktalar kümesini (ilgilendiğimiz noktalar kümesi) de yarı yarıya azaltıyoruz. İlki, FRI (Fast Reed-Solomon Interactive) protokolünün düzgün çalışmasını sağlamanın anahtarıdır. İkincisi, algoritmanın son derece hızlı çalışmasını sağlar: her turun boyutu önceki turla karşılaştırıldığında yarı yarıya azaldığından, toplam hesaplama maliyeti O (N*log (N)) yerine O (N) olur.

Alanın kademeli olarak azaltılmasını sağlamak için ikiye bir eşleme kullanılır, yani her nokta iki noktadan birine eşlenir. Bu eşleme, veri kümesinin boyutunu yarı yarıya azaltmamıza olanak tanır. Bu ikiye bir eşlemenin önemli bir avantajı tekrarlanabilir olmasıdır. Yani, bu eşlemeyi uyguladığımızda ortaya çıkan sonuç kümesi hala aynı özellikleri korur. Bir çarpımsal alt grupla başladığımızı varsayalım. Bu alt grup, her x elemanının kümede de 2x katının bulunduğu bir S kümesidir. S kümesinin karesini alırsanız (yani kümedeki her x öğesini x^2 ile eşlerseniz), yeni S^2 kümesi de aynı özellikleri koruyacaktır. Bu işlem, sonunda tek bir değer kalana kadar veri kümesinin boyutunu küçültmeye devam etmemizi sağlar. Teoride veri setini tek bir değere indirgeyebiliyorken pratikte genellikle daha küçük bir sete ulaşmadan duruyoruz.

Bu işlemi, bir doğrunun (örneğin bir doğru parçası veya bir yayın) dairenin çevresi üzerinde iki tur dönecek şekilde gerilmesi işlemi olarak düşünebilirsiniz. Örneğin çevre üzerinde x derecelik bir nokta bulunuyorsa bu işlemden sonra 2x dereceye hareket edecektir. Çember üzerinde 0'dan 179 dereceye kadar her noktanın 180'den 359 dereceye kadar karşılık gelen bir noktası vardır ve bu iki nokta çakışacaktır. Bu, x dereceden 2x dereceye kadar bir noktayı haritaladığınızda, x+180 derecelik bir konumla çakışacağı anlamına gelir. Bu işlem tekrarlanabilir. Yani, bu haritalama işlemini her seferinde çevredeki noktaları yeni konumlarına taşıyarak birden çok kez uygulayabilirsiniz.

Haritalama tekniğinin etkili olabilmesi için, orijinal çarpımsal alt grubun boyutunun faktör olarak 2'nin büyük kuvvetlerine sahip olması gerekir. BabyBear, maksimum çarpımsal alt grubunun sıfır olmayan tüm değerleri içerdiği belirli bir değerin modülüne sahip bir sistemdir, dolayısıyla alt grubun boyutu 2k−1'dir (burada k, modüldeki basamak sayısıdır). Bu büyüklükteki alt gruplar, eşleme işleminin tekrar tekrar uygulanmasıyla polinomun derecesinin etkili bir şekilde azaltılmasına olanak tanıdığı için yukarıdaki tekniğe çok uygundur. BabyBear'da 2^k boyutunda bir alt grup seçebilir (veya yalnızca tüm seti kullanabilirsiniz), ardından polinomun derecesini kademeli olarak 15'e düşürmek için FRI yöntemini uygulayabilir ve sonunda polinomun derecesini kontrol edebilirsiniz. Bu yöntem, modülün özelliklerinden ve çarpımsal alt grubun boyutundan yararlanarak hesaplama sürecini çok verimli hale getirir. Mersenne31, modülü çarpımsal alt grubun boyutu 2^31 - 1 olacak şekilde bir değer olan başka bir sistemdir. Bu durumda, çarpımsal alt grubun boyutu faktör olarak yalnızca 2'nin üssüne sahiptir ve bu da onun yalnızca bir kez 2'ye bölünmesine olanak tanır. Yukarıdaki teknoloji artık sonraki işlemlere uygulanamaz; yani FFT, BabyBear gibi etkili polinom derecesi azaltma için kullanılamaz.

Mersenne31 alanları, mevcut 32 bit CPU/GPU işlemlerindeki aritmetik işlemler için çok uygundur. Modül özellikleri nedeniyle (2^{31} - 1 gibi), birçok işlem verimli bit işlemleri kullanılarak tamamlanabilir: iki sayının eklenmesinin sonucu modülü aşarsa, onu azaltmak için sonuç modül işlemiyle kaydırılabilir. uygun bir aralığa getirin. Yer değiştirme operasyonu oldukça verimli bir operasyondur. Çarpma işlemlerinde, sonucu işlemek için belirli CPU talimatları (genellikle yüksek dereceli kaydırma talimatları olarak adlandırılır) kullanılabilir. Bu talimatlar çarpma işleminin yüksek dereceli kısmını verimli bir şekilde hesaplayabilir, böylece işlemin verimliliğini artırabilir. Mersenne31 alanında yukarıdaki özelliklerden dolayı aritmetik işlemler BabyBear alanına göre yaklaşık 1,3 kat daha hızlıdır. Mersenne31 daha fazla hesaplama verimliliği sağlar. FRI, Mersenne31 alanında uygulanabilirse, bu, hesaplama verimliliğini önemli ölçüde artıracak ve FRI uygulamasını daha verimli hale getirecektir.

FRI'yi daire içine alın

FRI'yi daire içine alın

Circle STARK'ların güzel yanı da budur; p asal sayısı verildiğinde, benzer ikiye bir özelliklere sahip p boyutunda bir grup bulabilirsiniz. Bu popülasyon belirli koşulları karşılayan tüm noktalardan oluşur; örneğin x^2 mod p'nin belirli bir değere eşit olduğu noktalar kümesi.

Bu noktalar, yakın zamanda trigonometri veya karmaşık çarpmayla ilgili herhangi bir şey yaptıysanız size tanıdık gelebilecek bir toplama modelini izler.

(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)

İki katına çıkan form:

2 * (x, y) = (2x^2 - 1, 2xy)

Şimdi bu çember üzerindeki tek sayılı noktalara odaklanalım:

Öncelikle tüm noktaları düz bir çizgide birleştiriyoruz. Normal FRI'da kullandığımız B (x²) ve C (x²) formüllerinin eşdeğer formu:

f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}

Daha sonra, x-doğrularının bir alt kümesi üzerinde tanımlanan tek boyutlu bir P(x) polinomunu elde etmek için rastgele doğrusal kombinasyonlar uygulayabiliriz:

İkinci turdan itibaren haritalama değişir:

f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}

İkinci turdan itibaren haritalama değişir:

f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}

Bu eşleme aslında yukarıdaki kümenin boyutunu her seferinde yarı yarıya azaltır, burada olan şey her x'in bir anlamda iki noktayı temsil etmesidir: (x, y) ve (x, -y). Ve (x → 2x^2 - 1) yukarıdaki nokta ikiye katlama kuralıdır. Bu nedenle çember üzerindeki iki zıt noktanın x koordinatlarını çarpılan noktanın x koordinatına dönüştürüyoruz.

Örneğin çember üzerinde sağdan ikinci değer olan 2'yi alıp 2 → 2 (2^2) - 1 = 7 eşlemesini uygularsak elde ettiğimiz sonuç 7 olur. Orijinal çembere geri dönersek, (2, 11) sağdan üçüncü noktadır, yani ikiye katlayarak sağdan altıncı noktayı, yani (7, 13) elde ederiz.

Bu iki boyutta yapılabilirdi ama tek boyutta çalışmak süreci daha verimli hale getiriyor.

FFT'leri daire içine alın

FRI ile yakından ilişkili bir algoritma, derecesi n'den küçük bir polinomun n değerlendirmesini polinomun n katsayısına dönüştüren FFT'dir . FFT süreci FRI'ye benzer, ancak FFT her adımda f_0 ve f_1 rastgele doğrusal kombinasyonları oluşturmak yerine yinelemeli olarak bunlar üzerinde yarı boyutlu bir FFT gerçekleştirir ve FFT (f_0) çıktısını çift katsayılar olarak alır. FFT'nin (f_1) tek katsayılar olarak.

Circle grubu ayrıca FRI'ye benzer şekilde inşa edilen FFT'yi de destekliyor. Ancak önemli bir fark, Circle FFT (ve Circle FRI) tarafından işlenen nesnelerin tam olarak polinom olmamasıdır. Bunun yerine, bunlar matematiksel olarak Riemann-Roch uzayları olarak adlandırılan uzaylardır: bu durumda polinomlar modulo daireseldir ( x^2 + y^2 - 1 = 0 ). Yani, x^2 + y^2 - 1'in herhangi bir katını sıfır olarak kabul ederiz. Bunu düşünmenin başka bir yolu da şudur: sadece y'nin bir üssü olmasına izin veriyoruz: bir y^2 terimi ortaya çıktığı anda onu 1 - x^2 ile değiştiriyoruz.

Bu aynı zamanda Circle FFT tarafından çıkan katsayıların normal FRI gibi tek terimli olmadığı anlamına gelir (örneğin, normal FRI çıktıları [6, 2, 8, 3] ise, bunun P (x) = 3x^3 + 8x anlamına geldiğini biliyoruz ^2 + 2x + 6). Buna karşılık, Daire FFT'nin katsayıları Daire FFT tabanına özeldir: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

İyi haber şu ki, bir geliştirici olarak bunu neredeyse tamamen görmezden gelebilirsiniz. STARK'lar asla katsayıları bilmenizi gerektirmez. Bunun yerine, polinomu belirli bir etki alanı üzerinde bir dizi değerlendirme değeri olarak saklarsınız. FFT'nin tek kullanımı düşük dereceli bir genişletme yapmaktır (Riemann-Roch uzaylarına benzer): N değerleri verildiğinde, hepsi aynı polinom üzerinde k*N değerleri üretir. Bu durumda, katsayıları oluşturmak için bir FFT kullanabilir, bu katsayılara (k-1) n sıfır ekleyebilir ve ardından daha büyük bir değerlendirilen değerler kümesi elde etmek için ters FFT'yi kullanabilirsiniz.

Circle FFT'ler FFT'nin tek özel türü değildir. Eliptik eğri FFT'leri daha güçlüdür çünkü herhangi bir sonlu alanda (asal alan, ikili alan vb.) çalışabilirler. Ancak ECFFT daha karmaşık ve daha az verimli olduğundan p = 2^{31}-1'de Circle FFT'yi kullanabileceğimiz için onu kullanmayı seçiyoruz.

Buradan itibaren Circle STARK'ların uygulanmasını normal STARK'lardan farklı kılan daha belirsiz ayrıntılardan bazılarına değineceğiz.

Bölümleme

Buradan Circle STARK'ların uygulanmasını normal STARK'lardan farklı kılan daha belirsiz ayrıntılardan bazılarına değineceğiz.

Bölümleme

STARK protokolünde ortak bir işlem belirli noktalarda bölüm işlemlerinin yapılmasıdır. Bu noktalar kasıtlı veya rastgele seçilebilir. Örneğin P(x) = y olduğunu kanıtlamak istiyorsanız aşağıdaki adımları takip edebilirsiniz:

Bölümü hesaplayın: P(x) polinomu ve y sabiti verildiğinde, Q ={P - y}/{X - x} bölümünü hesaplayın; burada X, seçilen noktadır.

Polinomu kanıtlayın: Q'nun kesirli bir değer değil, bir polinom olduğunu kanıtlayın. Bu şekilde P(x)=y'nin kurulduğu kanıtlanır.

Ayrıca DEEP-FRI protokolünde Merkle şubelerinin sayısını azaltmak için değerlendirme noktaları rastgele seçilerek FRI protokolünün güvenliği ve verimliliği artırılır.

Çember gruplarının STARK protokolü ile uğraşırken tek noktadan geçebilecek doğrusal bir fonksiyon olmadığından geleneksel bölüm işlemi yönteminin yerine farklı tekniklerin kullanılması gerekmektedir. Bu genellikle daire gruplarının benzersiz geometrik özelliklerini kullanarak yeni algoritmalar tasarlamayı gerektirir.

Bir daire grubunda, belirli bir noktaya (P_x, P_y) teğet olan bir teğet fonksiyon oluşturabilirsiniz, ancak bu fonksiyon nokta boyunca 2 katına sahip olacaktır, yani bir polinom, olması gereken bir doğrusal fonksiyonun A katı haline gelir. o noktada sıfır olmaktan daha katı koşulları karşılar. Bu nedenle değerlendirme sonuçlarını tek seferde kanıtlayamazsınız. Peki bununla nasıl başa çıkacağız?

Bu zorluğu kabul edip iki noktada değerlendirerek kanıtlamamız, böylece odaklanmamıza gerek olmayan bir kukla noktayı eklememiz gerekiyordu.

Çizgi fonksiyonu: balta + ile + c. Bunu bir denklem haline getirir ve 0'a eşit olmaya zorlarsanız, bunu lise matematiğinde standart form olarak adlandırılan bir çizgi olarak tanıyabilirsiniz.

Eğer x_1'de y_1'e ve x_2'de y_2'ye eşit bir P polinomumuz varsa, x_1'de y_1'e ve x_2'de y_2'ye eşit bir L enterpolasyon fonksiyonu seçebiliriz. Bu basitçe L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1 olarak ifade edilebilir.

Daha sonra P'nin x_1'de y_1'e ve x_2'de y_2'ye eşit olduğunu, L'yi çıkararak (P - L'yi her iki noktada da sıfır yaparak) ve L ile (yani x_2 - x_1 arasında doğrusal bir fonksiyon) kanıtlarız. Q bölümünün bir olduğunu kanıtlamak için L'ye bölün. polinom.

Kaybolan polinomlar

Kaybolan polinomlar

STARK'ta kanıtlamaya çalıştığınız polinom denklemi genellikle C (P (x), P ({sonraki}(x))) = Z (x) ⋅ H (x) gibi görünür; burada Z (x) bir A'dır tüm orijinal değerlendirme alanı boyunca polinomun sıfıra eşit olması. Normal STARK'ta bu işlev x^n - 1'dir. Dairesel STARK'ta karşılık gelen fonksiyon şöyledir:

Z_1 (x,y) = y

Z_2 (x,y) = x

Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1

Kaybolan polinomu katlama işlevinden türetebileceğinizi unutmayın: normal STARK'ta x → x^2'yi yeniden kullanırsınız, dairesel STARK'ta ise x → 2x^2 - 1'i yeniden kullanırsınız. Ancak ilk turda bunu farklı şekilde yaparsınız çünkü ilk tur özeldir.

Bit sırasını ters çevir

STARK'larda polinomlar genellikle "doğal" sırayla değil (örn. P (1), P (ω), P (ω2),…, P (ωn−1)) değil, benim ters dediğim şekilde değerlendirilir. ters bit sırası:

P (\omega^{\frac {3n}{8}})

Eğer n=16 ayarlayıp sadece ω'nin hangi kuvvetlerini değerlendirdiğimize odaklanırsak liste şu şekilde görünür:

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Bu sıralamanın önemli bir özelliği, FRI değerlendirme sürecinin başlarında birlikte gruplanan değerlerin sıralamada bitişik hale gelmesidir. Örneğin FRI gruplarının ilk adımı x ve -x. N = 16 durumunda, ω^8 = -1, bu P (ω^i) ) ve ( P (-ω^i) = P (ω^{i+8}) \) anlamına gelir. Gördüğümüz gibi bunlar tam olarak yan yana olan çiftler. FRI gruplarının ikinci adımı P (ω^i) , P (ω^{i+4}) , P (ω^{i+8}) ve P (ω^{i+12}). Bunlar tam olarak dörtlü gruplarda gördüğümüz şeyler vb. Bunu yapmak FRI'yi daha verimli hale getirir, çünkü birlikte katlanan değerler için (veya aynı anda k tur katlarsanız tüm 2^k değerleri için) bir Merkle kanıtı sağlamanıza olanak tanır.

Daire STARK'larda katlama yapısı biraz farklıdır: ilk adımda (x, y)'yi (x, -y) ile eşleştiririz; ikinci adımda x'i -x ile eşleştiririz, p'yi eşleştiririz; q ile p ve q'yu Q^i (p) = -Q^i (q) olacak şekilde seçin; burada Q^i, x → 2x^2-1 i kez tekrarlayan bir eşlemedir. Noktaları daire üzerindeki konumlarına göre düşünürsek, her adımda ilk nokta son noktayla, ikinci nokta ikinciden son noktaya vb. eşleştirilmiş gibi görünür.

Bu katlama yapısını yansıtacak şekilde ters bit sırasını ayarlamak için son bit dışındaki her biti ters çevirmemiz gerekir. Son parçayı saklıyoruz ve onu diğer parçaları çevirip çevirmeyeceğimize karar vermek için kullanıyoruz.

Boyutu 16 olan katlanmış ters bit sırası aşağıdaki gibidir:

{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Önceki bölümdeki daireye bakarsanız 0, 15, 8 ve 7 noktalarının (sağdan saat yönünün tersine) (x, y), (x, -y), (-x, -) olduğunu göreceksiniz. y) ve (-x, y), tam olarak ihtiyacımız olan şey bu.

Önceki bölümdeki daireye bakarsanız 0, 15, 8 ve 7 noktalarının (sağdan saat yönünün tersine) (x, y), (x, -y), (-x, -) olduğunu göreceksiniz. y) ve (-x, y), tam olarak ihtiyacımız olan şey bu.

yeterlik

Circle STARK'larda (ve genel olarak 31 bit prime STARK'larda) bu protokoller çok verimlidir. Circle STARK'ta kanıtlanmış bir hesaplama genellikle birkaç tür hesaplamayı içerir:

1. Yerel aritmetik: Sayma gibi iş mantığı için kullanılır.

2. Yerel aritmetik: Poseidon gibi hash fonksiyonları gibi kriptografide kullanılır.

3. Arama parametreleri : Tablodan değerleri okuyarak çeşitli hesaplamaları uygulayan genel ve etkili bir hesaplama yöntemi.

Verimliliğin temel ölçüsü, bir hesaplama izinde yararlı işler yapmak için tüm alanı tamamen kullanıp kullanmadığınız veya çok fazla boş alan bırakıp bırakmadığınızdır. Büyük alanlara yönelik SNARK'larda genellikle çok fazla boş alan bulunur: iş mantığı ve arama tabloları genellikle küçük sayılara ilişkin hesaplamalar içerir (bu sayılar N'den daha az olma eğilimindedir; burada N, bir hesaplamadaki toplam adım sayısıdır; 2^{25}'den daha az pratik yapın), ancak yine de 2^{256} bit boyutunda bir alan kullanmanın maliyetini ödemeniz gerekir. Burada alanın boyutu 2^{31} olduğundan boşa harcanan alan çok büyük değildir. SNARK'lar (Poseidon gibi) için tasarlanan düşük aritmetik karmaşıklık karmaları, herhangi bir alandaki izdeki her sayının her bitinden tam olarak yararlanır.

Binius, Circle STARK'lardan daha iyi bir çözümdür çünkü farklı boyutlardaki alanları karıştırmanıza izin vererek daha verimli uç paketleme sağlar. Binius ayrıca arama tablolarının ek yükü olmadan 32 bitlik eklemeler yapma seçeneğini de sunar. Bununla birlikte, bu avantajlar (bana göre) konsepti daha karmaşık hale getirme pahasına geliyor; oysa Circle STARK'lar (ve normal BabyBear tabanlı STARK'lar) kavramsal olarak çok daha basit.

Sonuç: Circle STARK'lar Hakkında Düşüncelerim

Circle STARK'lar geliştiriciler için STARK'lardan daha karmaşık değildir. Uygulama sürecinde yukarıda belirtilen üç husus temel olarak geleneksel FRI'dan farklılıklardır. Circle FRI'ın üzerinde çalıştığı polinomların arkasındaki matematik çok karmaşık olmasına ve matematiğin anlaşılması ve takdir edilmesi biraz zaman almasına rağmen, bu karmaşıklık aslında o kadar gizlidir ki geliştiriciler tarafından doğrudan hissedilmez.

Circle FRI ve Circle FFT'leri anlamak aynı zamanda diğer özel FFT'leri anlamak için bir geçit olabilir: Binius ve daha önce LibSTARK tarafından kullanılanlar gibi en önemlisi ikili alan FFT'leri ve ayrıca eliptik eğri FFT'leri kullanma gibi daha karmaşık yapılar. -Birçok haritalama eliptik eğri noktası işlemleriyle iyi bir şekilde birleştirilebilir.

Mersenne31, BabyBear ve Binius gibi ikili alan teknolojileriyle birleştiğinde, gerçekten STARK'ın temel katmanının verimlilik sınırlarına yaklaştığımızı hissediyoruz. Bu noktada STARK’ın optimizasyon yönünün şu noktalara odaklanacağını tahmin ediyorum:

Verimliliği en üst düzeye çıkarmak için karma işlevleri ve imzaların aritmetizasyonu: STARK kanıtlarında kullanıldığında en iyi performansı elde edebilmeleri için karma işlevleri ve dijital imzalar gibi temel kriptografik temelleri en verimli biçime optimize edin. Bu, hesaplama çabasını azaltmak ve verimliliği artırmak için bu temel öğeler için özel optimizasyonlar anlamına gelir.

Daha fazla paralelleştirme sağlamak için özyinelemeli yapı: Özyinelemeli yapı, STARK kanıt sürecinin yinelemeli olarak farklı düzeylere uygulanması ve böylece paralel işleme yeteneklerinin arttırılması anlamına gelir. Bu sayede bilgi işlem kaynakları daha verimli kullanılabilir ve ispat süreci hızlandırılabilir.

Daha fazla paralelleştirme sağlamak için özyinelemeli yapı: Özyinelemeli yapı, STARK kanıt sürecinin yinelemeli olarak farklı düzeylere uygulanması ve böylece paralel işleme yeteneklerinin arttırılması anlamına gelir. Bu sayede bilgi işlem kaynakları daha verimli kullanılabilir ve ispat süreci hızlandırılabilir.

Geliştirici deneyimini geliştirmek için sanal makineleri aritmetize edin: Sanal makinelerin aritmetize edilmesi, geliştiricilerin bilgi işlem görevlerini daha verimli ve basit bir şekilde oluşturmasına ve çalıştırmasına olanak tanır. Bu, sanal makinenin STARK kanıtlarında kullanılmak üzere optimize edilmesini ve akıllı sözleşmeler veya diğer bilgi işlem görevlerini oluştururken ve test ederken geliştirici deneyimini geliştirmeyi içerir.