Circle STARKs'ı Derinlemesine Keşfet

Son yıllarda, STARKs protokol tasarımında trend daha küçük alanlar kullanmaya yönelmekte. En erken STARKs uygulamaları 256-bit alan kullanıyordu, bu da bu protokollerin eliptik eğri tabanlı imzalarla uyumlu olmasını sağlıyordu. Ancak bu tasarımın verimliliği düşüktü, büyük sayıları işlemek büyük miktarda hesap gücü israfına neden oluyordu. 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ıt hızını önemli ölçüde artırdı. Örneğin, Starkware M3 dizüstü bilgisayarda saniyede 620.000 Poseidon2 hash değeri kanıtlayabiliyor. Bu, Poseidon2'yi hash fonksiyonu olarak güvenilir bulduğunuz takdirde, verimli ZK-EVM sorununu çözebileceğiniz anlamına geliyor. Peki bu teknolojiler nasıl çalışıyor? Küçük alanlarda nasıl kanıt oluşturuluyor? Bu makalede bu ayrıntılar incelenecek ve özellikle Circle STARKs çözümüne odaklanılacaktır.

Küçük alanların kullanımıyla ilgili sıkça sorulan sorular

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

Örneğin, A polinomunun bir taahhüdünün üretilmesi gerektiğini varsayalım, A^3(x) + x - A(ωx) = x^N olacak şekilde. Protokol, rastgele koordinat r seçilmesini ve A(r) + r - A(ωr) = r^N olduğunu kanıtlamasını isteyebilir. Sonra A(r) = c geri çıkarılabilir, Q = (A - c)/(X - r) bir polinom olduğunu kanıtlayabilir.

Saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmek gerekir. Büyük alan protokolünde, r için rastgele 256 bitlik bir sayı seçilebilir. Ancak küçük alan STARK'larda, yaklaşık 2 milyar r değeri seçeneği vardır, bu nedenle saldırgan tüm olasılıkları deneyebilir.

Bu sorunun iki çözümü var:

1. Birkaç rastgele denetim gerçekleştirin
2. Genişletilmiş Alan

Birden fazla rastgele kontrol basit ve etkilidir, ancak verimlilik sorunları vardır. Genişletilmiş alanlar, sınırlı alanlara dayalı olarak çoğul gibidir. α^2= belirli bir değeri sağlayan yeni bir α değeri tanıtılır ve yeni bir matematiksel yapı oluşturulur. Bu, daha fazla değer seçeneğine sahip olmamızı sağlar ve güvenliği artırır.

Düzenli CUMA

FRI protokolünün ilk adımı genellikle aritmetikleştirmedir, hesaplama problemini denkleme dönüştürmek P(X,Y,Z)=0, burada P bir polinomdur, X, Y, Z parametrelerdir. Denklemi çözmek, orijinal problemi çözmekle eşdeğerdir.

Çözümün doğruluğunu kanıtlamak için, önerilen değerin makul bir polinom olduğunu ve en yüksek dereceli olduğunu kanıtlamak gerekir. Rastgele lineer kombinasyon tekniğini kullanarak:

• A polinom A'nın değerlendirme değerinin derecesinin <2^20 olduğunu kanıtlayın.
• B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D, B ve C'nin rastgele lineer kombinasyonudur: D = B + rC

Temelde B, çift katsayıları izole eder; C, tek katsayıları izole eder. B ve C, A'yı geri yükleyebilir. Eğer A'nın derecesi < 2^20 ise, B ve C'nin dereceleri sırasıyla A'nın derecesi ve A'nın derecesi - 1 olmalıdır. D, rastgele bir kombinasyon olarak A'nın derecesi kadar olmalıdır.

FRI bu basitleştirme sürecini tekrarlayarak her seferinde sorunu yarıya indirir. Bu tasarım, gereksinimleri karşılamayan girdileri etkili bir şekilde tespit eder.

Circle FRI

İşte Circle STARKs'ın inceliği. Verilen bir asal p için, p boyutunda, benzer bir ikili özellik taşıyan bir grup bulunabilir. Bu grup, belirli koşulları sağlayan noktalar kümesinden oluşur, örneğin x^2 mod p'nin belirli bir değere eşit olduğu noktalar.

Bu noktalar toplama kuralını takip eder: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Çift form şu şekildedir: 2 * (x,y) = (2x^2 - 1, 2xy)

Daire üzerindeki tek konumlardaki noktalara odaklanıyoruz ve tüm noktaları tek bir doğruya sıkıştırıyoruz: f0(x) = (F(x,y) + F(x,-y))/2

Sonra rastgele lineer kombinasyon yaparak bir boyutlu polinom P(x) elde edilir.

İkinci turdan itibaren, eşleme şöyle değişiyor: f0(2x^2-1) = (F(x) + F(-x))/2

Bu haritalama 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 destekler, yapılandırma yöntemi FRI'ye benzer. Ancak Circle FFT'nin işlediği nesne Riemann-Roch alanıdır, katı çok terimli değil.

Geliştirici olarak, bu noktayı temel olarak göz ardı edebilirsiniz. STARKs, çok terimli ifadeyi yalnızca değerlendirme değerleri kümesi olarak depolamanızı gerektirir. FFT, esasen düşük dereceli genişleme için kullanılır: N değer verildiğinde, aynı çok terimli ifadede k*N değer oluşturur.

Bölme

Circle STARKs'ta, tek nokta doğrusal fonksiyonun olmaması nedeniyle, geleneksel çarpma işlemini değiştirmek için farklı teknikler kullanılmalıdır. İki noktada değerlendirme yaparak, sanal bir nokta ekleyerek kanıt sağlanır.

Eğer polinom P, x1'de y1'e eşit ve x2'de y2'ye eşit ise, bu iki noktada eşit olan interpolasyon fonksiyonu L'yi seçiniz. Sonra P-L'nin iki noktada sıfır olduğunu ispatlayın, L'yi böldüğünüzde elde edilen bölüm Q bir polinomdur.

Kaybolan polinomlar

Circle STARKs'taki kaybolan çok terimli polinom şudur: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Bu, katlama fonksiyonundan türetilebilir: x → 2x^2 - 1 ifadesinin tekrar kullanılması.

Ters bit sırası

Circle STARKs'daki ters sıra ayarlanmalı: son bit hariç her bit tersine çevrilmeli, diğer bitlerin ters çevrilip çevrilmeyeceğine son bit karar vermelidir.

16 boyutunda 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. İş mantığının yerel aritmetiği
2. Kriptolojinin Yerel Aritmetiği
3. Parametreleri Bul

Verimlilik, hesaplama izleme alanının tam olarak kullanılmasına bağlıdır. 31 bitlik alan, israfı azaltır. Binius, farklı boyutlardaki alanları birleştirerek daha yüksek verimlilik sağlar, ancak kavram daha karmaşıktır.

Sonuç

Circle STARKs geliştiriciler için karmaşık değildir. Arkasındaki matematiği anlamak zaman alır, ancak karmaşıklık iyi bir şekilde gizlenmiştir. Bu ayrıca diğer özel FFT'leri anlamanın bir yoludur.

Şu anda STARKs temel katman verimliliği neredeyse sınırda. Gelecek optimizasyon yönleri arasında şunlar olabilir:

• Hash fonksiyonları gibi temel kriptografik yapıların verimliliğini maksimize etmek
• Paralelleşmeyi artırmak için özyinelemeli yapı
• Geliştirme deneyimini iyileştirmek için aritmetik sanal makine