Circle STARKs'i Keşfet

Son yıllarda, STARKs protokol tasarımı daha küçük alanlar kullanmaya yöneldi. İlk STARKs uygulamaları 256 bit alan kullanarak büyük sayılar üzerinde mod hesaplaması yapıyordu ve bu, eliptik eğri tabanlı imzalarla uyumlu hale getiriliyordu. Ancak bu tasarımın verimliliği düşüktü ve büyük sayıları işlemek hesaplama gücünün israfına neden oluyordu. Bu sorunu çözmek için, STARKs daha küçük alanlar kullanmaya başladı: Goldilocks, Mersenne31 ve BabyBear.

Bu dönüşüm, kanıt 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 kabul ettiğinizde, verimli ZK-EVM geliştirme sorununu çözebilirsiniz. Peki bu teknolojiler nasıl çalışıyor? Küçük alanlarda nasıl kanıt oluşturuluyor? Bu makale, bu ayrıntıları inceleyecek ve özellikle Circle STARKs çözümüne odaklanacaktır.

Küçük Alanların Kullanımına Dair Sıkça Sorulan Sorular

Hash tabanlı bir kanıt oluştururken, önemli bir teknik, polinom özelliklerini dolaylı olarak doğrulamak için rastgele noktalardaki polinomun değerlendirilmesidir. Bu, kanıt sürecini büyük ölçüde basitleştirir.

Örneğin, A polinomunun A^3(x) + x - A(ωx) = x^N koşulunu sağladığını kanıtlamak istiyorsak, protokol rastgele bir r koordinatı seçmeyi ve A(r) + r - A(ωr) = r^N olduğunu kanıtlamayı gerektirebilir. Sonra A(r) = c'yi geri çıkararak, Q = (A - c)/(X - r) polinom olduğunu kanıtlarız.

Saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmek gerekir. 256 bitlik bir alanda bu oldukça basit: rastgele 256 bitlik bir sayı seçmek yeterlidir. Ancak küçük alanlarda, seçilebilecek r değerleri yalnızca yaklaşık 2 milyar türdür; saldırganın çabası büyük olsa da, yine de tüm olasılıkları denemeyi deneyebilir.

İki çözüm var:

1. Birçok rastgele kontrol gerçekleştirin
2. Genişletilmiş Alan

Birden fazla kontrol basit ve etkili, ancak verimlilik sorunu var. Genişletilmiş alanlar, sınırlı alanlara dayalı olarak çokluktan benzer. Belirli bir ilişkiyi karşılayan yeni bir değer α tanıtılır, örneğin α^2 = belirli bir değer. Bu, sınırlı alan üzerinde daha karmaşık hesaplamalar yapılabilen yeni bir matematiksel yapı oluşturur. Genişletilmiş alan yalnızca rastgele lineer kombinasyonlar gerektiğinde kullanılır, çoğu işlem hala temel alanda gerçekleştirilir.

Genel FRI

SNARK veya STARK inşa etmenin ilk adımı, hesaplama problemini P(X,Y,Z)=0 çok polinom denklemi şeklinde dönüştürmektir. Çözüm, sunulan değerlerin makul çok terimli olduğunu ve derecenin sınırlı olduğunu kanıtlamalıdır. Bu, rastgele lineer kombinasyonların adım adım uygulanmasıyla gerçekleştirilir:

1. Bir polinom A'nın değerlendirme değerine sahip olduğunu varsayalım, derecesinin <2^20 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

B, A'nın çift katsayılarını; C ise tek katsayılarını izole eder. B ve C verildiğinde A geri kazanılabilir: A(x) = B(x^2) + xC(x^2). 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, derecesi A'nın derecesi olmalıdır.

FRI, d dereceli polinomun derecesini d/2 olan bir polinomu kanıtlayarak doğrulamayı basitleştirir. Bu süreç, her seferinde sorunu yarıya indirerek birden fazla kez tekrarlanabilir. Eğer bir aşamada çıkan sonuç beklenen dereceye uymazsa, o turdaki kontrol başarısız olacaktır.

FRI, her adımda polinom derecesini ve nokta kümesi büyüklüğünü yarıya indirir. İlki, FRI'nin çalışması için anahtardır, ikincisi algoritmanın çok hızlı çalışmasını sağlar: toplam hesaplama maliyeti O(N) değil, O(N*log(N)).

Alanı kademeli olarak azaltmak için, ikiye bir eşleme kullanılır. Bu eşleme, veri kümesinin boyutunu yarıya indirmeye izin verir ve tekrarlanabilir. Çarpan alt grubundan başlayarak, her x elemanının çarpanı 2x de kümede bulunur. Küme S'nin karesi alındığında, yeni küme S^2 aynı özelliği korur. Bu, veri kümesinin boyutunun sadece bir değere kalana kadar sürekli olarak azaltılmasına izin verir.

BabyBear'ın modülü, maksimum çarpan alt grubunun tüm sıfır olmayan değerleri içermesini sağlar, boyutu 2^k-1'dir. Bu, yukarıda belirtilen teknik için çok uygundur ve tekrarlanan haritalama ile polinom derecesini etkili bir şekilde azaltabilir. Mersenne31'in çarpan alt grubu boyutu 2^31-1'dir, yalnızca bir kez 2 ile bölünebilir, sonrasında bu teknik kullanılamaz.

Mersenne31 alanı 32 bit CPU/GPU hesaplamaları için son derece uygundur. Modül özelliği (, 2^31-1) gibi birçok işlemin verimli bit işlemleri ile yapılmasını sağlar: modülden büyük sonuçlar kaydırma ile azaltılabilir. Çarpma belirli CPU talimatları ile verimli bir şekilde işlenebilir. Mersenne31'in aritmetik işlemleri BabyBear'den yaklaşık 1.3 kat daha hızlıdır. Mersenne31'de FRI uygulanabilirse, verimlilik önemli ölçüde artacaktır.

Circle FRI

Circle STARKs'ın cleverliği, verili bir asal p ile p büyüklüğünde bir grup bulunabilmesidir; bu grup ikiye bir benzeri bir özellik taşır. Bu grup, belirli koşulları sağlayan noktaları içerir, örneğin x^2 mod p'nin belirli bir değere eşit olduğu noktalar seti.

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 konumların noktalarına odaklanıyoruz. Öncelikle tüm noktaları tek bir doğruya toplayın: f0(x) = (F(x,y) + F(x,-y))/2

Ardından rastgele lineer kombinasyon yaparak 1 boyutlu polinom P(x) elde edilir.

İkinci turdan itibaren, haritalama şu şekilde değişir: f0(2x^2-1) = (F(x) + F(-x))/2

Bu eşleme 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 üzerindeki iki karşıt noktanın x koordinatlarını, çarpan sonrası noktaların x koordinatlarına dönüştürüyoruz.

Daire FFT'leri

Circle grubu da FFT'yi desteklemektedir, yapılandırma yöntemi FRI'ye benzerdir. Ana fark, Circle FFT'nin katı bir çokpolinom değil, Riemann-Roch uzayını işlemesidir: çokpolinom mod daire (x^2 + y^2 - 1 = 0).

Daire FFT çıkış katsayıları belirli bir temeldir: {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öz ardı edebilir. STARKs, polinomları değerlendirme değerleri kümesi olarak saklar. FFT, yalnızca düşük dereceli genişletme için kullanılır: N değer verildiğinde, aynı polinom üzerindeki k*N değerini üretir.

Ticaret İşlemleri

STARK'ın yaygın işlemleri belirli noktalar üzerinde bölme işlemi yapmaktır. Örneğin, P(x)=y'yi kanıtlamak aşağıdaki adımlarla yapılabilir:

1. Hesaplanan oran: Q = (P - y)/(X - x)
2. Q'nun bir polinom olduğunu ve bir kesir olmadığını kanıtlayın.

circle group STARK'ta, tek bir noktanın lineer fonksiyonu ile geçmediği için farklı beceriler gereklidir. Tanjant fonksiyonu oluşturulabilir, ancak bu noktalarda kat sayısı 2'dir. Bu nedenle, kanıtlamak için iki noktada değerlendirmek gerekmektedir.

Eğer P, x1'de y1'e ve x2'de y2'ye eşitse, bu iki noktada eşit olan interpolasyon fonksiyonu L'yi seçeriz. Sonra P-L'nin bu iki noktada sıfır olduğunu kanıtlayarak, L'yi L'ye bölerek Q'nun bir polinom olduğunu kanıtlarız.

Kaybolan Polinom

STARK'ta ispat etmeye çalışılan polinom denklemleri genellikle şu şekilde olur: C(P(x), P(next(x))) = Z(x) · H(x), Z(x) orijinal değerlendirme alanında her zaman sıfıra eşittir.

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

Ters Sıra

STARK'larda çok değişkenli polinom değerlendirmeleri genellikle ters bit sırasına göre düzenlenir. Circle STARK'larda, katlama yapısı biraz farklıdır:

• İlk adım: (x,y) ile (x,-y) eşleştirin
• İkinci adım: x ile -x eşleştir
• Sonraki adımlar: p ve q eşleştirilecek, böylece Q^i(p) = -Q^i(q)

Ters sıralamayı ayarlamak için, son basamak hariç her bir basamağı ters çevirmek gerekir ve diğer basamakların ters çevrilip çevrilmeyeceğine son basamak karar verir.

Verimlilik

Circle STARKs çok etkili. Hesaplama genellikle şunları içerir:

1. Yerel aritmetik: İş mantığı için kullanılır
2. Yerel Aritmetik: Kriptografi için (, Poseidon Hash'ı )
3. Parametre Bulma: Genel Verimli Hesaplama Yöntemi

Verimliliğin anahtarı, hesaplama izleme alanını tam olarak kullanmaktır. Burada alan boyutu 2^31, böylece boşa giden alan çok azdır. Poseidon gibi hash fonksiyonları, herhangi bir alanda her bir sayının her bir bitini tam olarak kullanır.

Binius, farklı boyutlardaki alanları karıştırarak daha verimli bir bit paketleme sağlar, ancak bunun bedeli daha karmaşık bir kavramdır. Circle STARK'lar kavramsal olarak nispeten basittir.

Sonuç

Circle STARKs, geliştiriciler için STARKs'tan daha karmaşık değildir. Uygulamadaki ana fark, yukarıda belirtilen üç sorudadır. Arka plandaki matematik karmaşık olmasına rağmen, bu karmaşıklık iyi bir şekilde gizlenmiştir.

Circle FRI ve FFT'leri anlamak, ikili alan FFT'leri ve eliptik eğri FFT'leri gibi diğer özel FFT'leri anlamanın bir yolu olabilir.

Mersenne31, BabyBear ve Binius gibi teknolojileri birleştirerek, STARKs temel katman verimliliği sınırına yaklaşıyoruz. Gelecekteki optimizasyonlar muhtemelen şunlara odaklanabilir:

1. Hash fonksiyonu ve imza gibi aritmetik verimliliği maksimize etme
2. Daha fazla paralelleşmeyi etkinleştirmek için özyinelemeli yapı
3. Geliştirici deneyimini iyileştirmek için aritmetik sanal makine