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ı, 256 bitlik alanlar, yani büyük sayılardaki modülo aritmetiği (örn. 21888...95617) kullanıyordu; bu, bu protokolleri eliptik eğri tabanlı imzalarla uyumlu hale getiriyordu. 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 alanlara taşınmaya 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 uygulanan) 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.

Ö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. Daha sonra A (r) = c'ye doğru geriye doğru çalışın ve Q = \frac {A - c}{X - r}'nin bir polinom olduğunu kanıtlayın.

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 A'nın bu iki noktadan geçen düz bir çizgi olmasını sağlayabilirsiniz.

Bu saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmemiz gerekir (Fiat-Shamir, saldırıları önlemek için belirli parametreleri bazı hash değerlerine ayarlayarak protokol güvenliğini artırmak için kullanılan bir tekniktir. Parametrelerin yeterince büyük bir kaynaktan gelmesi gerekir) Saldırganın bu parametreleri tahmin edememesini veya tahmin edememesini sağlamak için ayarlanır, böylece sistemin güvenliği artar.

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, ancak kararlı bir saldırgan için bu hala tamamen mümkün!

Bu sorunun iki çözümü var:

• Birden fazla rastgele kontrol gerçekleştirin

• HAYIR

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)

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, bu, tur başına 104 bit güvenlik sağlar. 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 alanları gerçekte yalnızca FRI (Fast Reed-Solomon Interactive) protokollerinde ve rastgele doğrusal kombinasyonlar gerektiren diğer senaryolarda kullanılır. Matematiğin çoğu hâlâ temel alanlar üzerinde yapılıyor; bunlar genellikle modulo ppp veya qqq alanlarıdır. 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:

• Diyelim ki bir A polinomunun değerlendirmesine sahipsiniz ve derecesinin 2^{20}'den küçük olduğunu kanıtlamak istiyorsunuz.

• B (x^2) = A (x) + A (-x), C (x^2) = \frac {A (x) - A (-x)}{x} polinomunu düşünün

• D, B ve C'nin rastgele doğrusal birleşimidir, yani D=B+rCD = B + rCD=B+rC olup r, rastgele bir katsayıdır.

Esas olarak, B, A'nın çift katsayılarını ve ? tek katsayıları izole eder. 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 gereksinimleri karşıladığını doğrulamak için D'nin derecesini kullanmanıza olanak tanır.

Birincisi, FRI, d dereceli bir polinomun kanıtlanması sorununu d/2 dereceli bir polinomun kanıtlanması sorununa 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. Bir veri kümesinin çoğu konumda d dereceli bir polinoma eşit olması durumunda 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ıya indiriyoruz ve ayrıca noktalar kümesini (ilgilendiğimiz noktalar kümesi) de yarıya indiriyoruz. İ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 adım adım 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 bir nokta x derece ise bu işlemden sonra 2x derece 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 eşleme işlemini her defasında daire üzerindeki 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ırdan farklı tüm değerleri içerdiği belirli bir modüle sahip bir sistemdir, böylece 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. Daha sonraki işlemler artık yukarıdaki teknikler için uygun değildir, yani BabyBear gibi etkili polinom derecesi indirgeme için FFT'yi kullanmak mümkün değildir.

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 özel CPU talimatları (genellikle yüksek dereceli kaydırma talimatları olarak adlandırılır) kullanılır. 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ıda açıklanan ö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 uygulamalarını daha verimli hale getirecektir.

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 popülasyon 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}

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 karşıt noktanın x koordinatlarını, çarpılan noktanın x koordinatları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 sonuç olarak 7 elde ederiz. 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 bu 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.

Çevre grupları ayrıca FRI'lere benzer şekilde oluşturulan FFT'leri de destekler. Ancak önemli bir fark, Circle FFT'nin (ve Circle FRI'nin) tam olarak polinom olmayan nesnelerle ilgilenmesidir. 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 değerlendirilmiş değerler kümesi olarak saklarsınız. FFT'yi kullanmanız gereken tek yer, düşük dereceli bir genişletme yapmaktır (Riemann-Roch uzaylarına benzer): N değerleri verildiğinde, tümü aynı polinom üzerinde k*N değerleri oluşturun. 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 tek özel FFT türü değildir. Eliptik eğriFFT'ler 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 Circle STARK'ların uygulanmasını normal STARK'lardan farklı kılan daha belirsiz ayrıntılardan bazılarına dalacağız.

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 bunu şu adımları izleyerek yapabilirsiniz:

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

Polinomları kanıtlayın: Q'nun kesir değil bir polinom olduğunu kanıtlayın. Bu şekilde P(x)=y'nin doğru olduğu kanıtlanır.

Ayrıca DEEP-FRI protokolünde değerlendirme noktaları rastgele seçilerek Merkle şubelerinin sayısı azaltılır, böylece FRI protokolünün güvenliği ve verimliliği artar.

Çember grubunun 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 getirip 0'a eşitlemeye 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

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 şöyle görünür:

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

Bu sıralama, FRI değerlendirme sürecinin başlarında birlikte gruplanan değerlerin sıralamada bitişik hale gelmesi gibi temel özelliğe sahiptir. Ö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 ve p ve q'yi 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.

Ters bit sırasına göre 16 boyutunda bir katlama 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.

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 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 de bir kapı olabilir: Binius ve daha önce LibSTARK tarafından kullanılanlar gibi en önemlisi ikili alan FFT'leri ve ayrıca birkaç tane kullanan eliptik eğri FFT'leri gibi daha karmaşık yapılar. to-many haritalaması 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şlevlerinin, imzaların vb. 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çimlerine 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.

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.