Circle STARKs'ı Keşfet

Son yıllarda, STARKs protokol tasarımı daha küçük alanlar kullanmaya yöneldi. İlk STARKs uygulamaları 256 bit alan kullanıyordu ve eliptik eğri tabanlı imzalarla uyumluydu. Ancak bu tasarım verimsizdi, büyük sayıları işlerken hesap gücünü boşa harcıyordu. Bu sorunu çözmek için, STARKs daha küçük alanlar kullanmaya yönelmeye başladı: önce Goldilocks, ardından Mersenne31 ve BabyBear.

Bu dönüşüm, kanıtlama hızını artırdı. Örneğin, Starkware, M3 dizüstü bilgisayarında saniyede 620.000 Poseidon2 hash değeri kanıtlayabiliyor. Poseidon2'yi bir hash fonksiyonu olarak güvenilir bulduğumuz sürece, verimli bir ZK-EVM geliştirme sorununu çözebiliriz. Peki bu teknolojiler nasıl çalışıyor? Bu kanıtlar daha küçük alanlarda nasıl kurulur? Bu makale bu ayrıntıları ele alacak, özellikle Circle STARKs çözümlerine odaklanacaktır.

Küçük matematik alanlarını kullanmanın yaygın sorunları

Hash tabanlı bir kanıt oluştururken, önemli bir teknik, polinomun rastgele noktalar üzerindeki değerlendirme sonuçlarını kanıtlayarak, polinomun özelliklerini dolaylı olarak doğrulamaktır. Bu, kanıt sürecini büyük ölçüde basitleştirebilir.

Örneğin, çok terimli A'nın taahhüdünü oluşturması isteniyorsa, A^3(x) + x - A(ωx) = x^N olarak karşılanması gerekir. Protokol, rastgele koordinat r'in seçilmesini ve A(r) + r - A(ωr) = r^N olduğunu kanıtlamasını isteyebilir. Sonra A(r) = c olarak geri çıkarma yapılır ve Q = (A - c)/(X - r)'in bir çok terim olduğunu kanıtlar.

Saldırıları önlemek için, saldırganın A sağlamasından sonra r seçilmelidir. Eliptik eğriye dayalı protokollerde rastgele 256 bitlik bir sayı seçilebilir. Ancak daha küçük alanlardaki STARK'larda yalnızca yaklaşık 2 milyar r değeri seçilebilir; saldırganlar bu değerleri deneme-yanılma yöntemiyle kırabilir.

Çözüm iki tanedir:

1. Birkaç rastgele kontrol yapmak
2. Genişletilmiş Alan

Birçok rastgele kontrol basit ve etkili, ancak verimlilik sorunları var. Genişletilmiş alanlar, sınırlı alanlara dayalı karmaşık sayılar gibidir. Yeni bir değer α tanıtılır, α^2=belirli bir değer olarak ifade edilir. Bu şekilde, sınırlı alan üzerinde daha karmaşık işlemler gerçekleştirilebilir. Genişletilmiş alan yalnızca FRI protokolü gibi senaryolarda kullanılır, çoğu matematiksel işlem hala temel alan üzerinde gerçekleştirilir.

Genel FRI

SNARK veya STARK inşa ederken, ilk adım aritmatikleştirmedir, hesaplama problemini çok terimli denklemlere dönüştürmektir. Çözümün var olduğunu kanıtlamak için, önerilen değerin makul bir çok terimli olduğunu ve en yüksek dereceden olduğunu kanıtlamak gerekir. Bunun için aşamalı olarak uygulanan rastgele lineer kombinasyon tekniği kullanılır:

1. Bir polinom A'nın değerlendirme değerine sahip olduğunu varsayalım, derecesinin 2^20'den küçük olduğunu kanıtlayalım.
2. B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D, B ve C'nin rastgele lineer kombinasyonudur: D = B + rC

Esasen, B ayrılmış çift katsayı, C ayrılmış tek katsayıdır. Verilen B ve C ile A geri kazanılabilir. Eğer A derecesi < 2^20 ise, B ve C dereceleri sırasıyla A derecesi ve A derecesi - 1 olmalıdır. D, rastgele lineer kombinasyon olarak, derece A derecesi olmalıdır.

FRI, d dereceli bir polinomun kanıtını d/2 dereceli bir kanıta indirgeme problemi ile doğrulama sürecini basitleştirir. Bu süreç, her seferinde problemi yarıya indirerek birden çok kez tekrarlanabilir.

Alanı kademeli olarak azaltmak için ikiye bir eşleme kullanın. Bu eşleme, veri kümesinin boyutunu yarıya indirmeyi sağlar ve tekrarlanabilir. Çarpan alt gruptan başlayarak, S kümesine kare alma işlemi uygulanır, yeni S^2 kümesi aynı özellikleri korur. Bu, veri kümesinin boyutunu sürekli olarak azaltmayı sağlar, ta ki sonunda sadece bir değer kalana kadar.

BabyBear modülü, maksimum çarpma alt grubunun tüm sıfır olmayan değerleri içermesini sağlar ve alt grup boyutu 2k-1'dir. 2^k boyutunda bir alt grup seçilebilir ve ardından çok terimliliği 15'e azaltmak için FRI yöntemi uygulanabilir. Mersenne31 modülü, çarpma alt grubunun boyutunu 2^31-1 yapar; yalnızca bir kez 2 ile bölünebilir, sonrasında yukarıdaki teknikler kullanılamaz.

Mersenne31 alanı 32 bit CPU/GPU hesaplamaları için uygundur. Modül özellikleri sayesinde birçok işlem verimli bit işlemleri ile gerçekleştirilebilir. Mersenne31 alanında, aritmetik işlemler BabyBear alanına göre yaklaşık 1.3 kat daha hızlıdır. Eğer Mersenne31 alanında FRI uygulanabilirse, hesaplama verimliliği önemli ölçüde artacaktır.

Circle FRI

Circle STARKs'ın inceliği, verilen bir asal p için, ikiye bir benzeri özellikler taşıyan p büyüklüğünde bir grup bulunabilmesidir. Bu grup, belirli koşulları sağlayan noktaların bir araya gelmesiyle oluşur; örneğin x^2 mod p'nin belirli bir değeri eşit olan noktalar kümesi.

Bu noktalar toplama kuralını izler: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Çift form: 2 * (x,y) = (2x^2 - 1, 2xy)

Daire üzerindeki tek konumlara odaklanıyoruz. Öncelikle tüm noktaları bir doğru üzerinde toplayın: f0(x) = (F(x,y) + F(x,-y))/2

Sonra rastgele lineer kombinasyon yapın, bir boyutlu polinom P(x) elde edin.

İkinci turdan itibaren, haritalama şu hale geliyor: f0(2x^2-1) = (F(x) + F(-x))/2

Bu harita her seferinde küme boyutunu yarıya indirir. Her x, iki noktayı temsil eder: (x,y) ve (x,-y). (x → 2x^2 - 1), nokta çarpan kuralıdır.

Daire FFT'leri

Circle grubu da FFT'yi desteklemektedir, yapısı FRI'ye benzer. Circle FFT'nin işlediği nesne Riemann-Roch uzayıdır: çok terimli modülo daire (x^2 + y^2 - 1 = 0).

Daire FFT çıktısındaki sabitler şunlardır: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Geliştiriciler bu noktayı neredeyse görmezden gelebilir. STARKs, çok terimli ifadeleri değerlendirme değer kümesi olarak saklamak için gereklidir. FFT, düşük dereceli genişleme için kullanılır: N değer verildiğinde, aynı çok terimli ifadede k*N değer oluşturulur.

Ticaret İşlemleri

STARK protokolünde, yaygın bir işlem belirli noktalar üzerinde çarpma işlemi yapmaktır. Örneğin, P(x)=y:

1. İşlem Q = (P - y)/(X - x)
2. Q'nun çok terimli olduğunu ve kesir olmadığını kanıtlayın.

circle grubu STARK'ta, tek bir noktanın lineer fonksiyonu olmadığı için, geleneksel çarpan işlem yöntemlerinin yerine farklı tekniklerin kullanılması gerekmektedir. İki noktada değerlendirme yaparak, dikkate alınması gerekmeyen sanal bir noktanın eklenmesini kanıtlayarak.

Eğer polinom P, x1'de y1'e, x2'de y2'ye eşitse, x1'de y1'e, x2'de y2'ye eşit olan interpolasyon fonksiyonu L'yi seçin: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Sonra P - L'nin bu iki noktada sıfır olduğunu kanıtlayarak, L'yi L'ye bölerek Q'nun bir çok terimli olduğunu kanıtlayın.

Kaybolan Polinom

STARK'ta, çok terimli denklemler genellikle C(P(x), P(next(x))) = Z(x) · H(x), Z(x) tüm değerlendirme alanında sıfırdır.

Dairesel STARK'ta, ilgili fonksiyon şudur: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Kaybolan polinomlar katlama fonksiyonundan türetilebilir: klasik STARK x → x^2 tekrarını kullanırken, dairesel STARK x → 2x^2 - 1 tekrarını kullanır.

Ters Sıralama

STARKs'te, polinom değerlendirmesi genellikle ters bit sırasına göre düzenlenir. Örneğin n=16 olduğunda: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Bu sıralama, FRI değerlendirme sürecindeki erken grupların değerlerinin sıralamada yan yana olmasını sağlar ve alan tasarrufu sağlar.

circle STARKs'te, katlanma yapısı biraz farklıdır. Bu yapıyı yansıtmak için ters sıralamayı ayarlamak gerekir, her bir bitin son bit hariç tersine çevrilmesi ve diğer bitlerin tersine çevrilip çevrilmeyeceğine son bitin karar vermesi gerekir.

Boyutu 16 olan katlanabilir ters sıralama: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Verimlilik

Circle STARKs çok verimlidir. Hesaplamalar genellikle şunları içerir:

1. Yerel aritmetik: İş mantığı için kullanılır
2. Yerel Aritmetik: Kriptografi için kullanılır
3. Parametreleri Bulma: Genel Verimli Hesaplama Yöntemi

Verimlilik, hesaplama izleme alanının tam kullanımı ile anahtardır. Circle STARKs alan boyutu 2^31 olup, daha az alan israfı vardır.

Binius, Circle STARKs'tan daha iyidir, farklı boyutlardaki alanları karıştırmaya izin verir ve daha verimli bit paketleme sağlar. Ancak bunun bedeli daha karmaşık bir kavramdır, Circle STARKs'ın kavramı ise görece daha basittir.

Sonuç

Circle STARKs, geliştiriciler için STARKs'tan daha karmaşık değildir. Circle FRI ve Circle FFT'leri anlamak, diğer özel FFT'leri anlamanın bir yolu olarak kullanılabilir.

Mersenne31, BabyBear ve Binius gibi teknolojileri birleştirerek, STARKs temel katman verimlilik sınırına yaklaşıyoruz. Gelecekte STARK optimizasyon yönleri şunları içerebilir:

1. Hash fonksiyonları ve imza vb. için aritmetik verimliliğini maksimize et
2. Daha fazla paralelleşmeyi etkinleştirmek için özyinelemeli yapı
3. Geliştirici deneyimini geliştirmek için aritmetik sanal makine