Son yıllarda, STARKs protokol tasarımı, daha küçük alanlar kullanmaya doğru bir eğilim göstermektedir. İlk STARKs üretim uygulamaları 256 bit alan kullanıyordu, yani büyük sayılar üzerinde modül işlemleri yapılıyordu. Ancak bu tasarımın verimliliği düşüktü ve büyük sayıları işlemek çok fazla hesap gücü israfına yol açıyordu. Bu sorunu çözmek için, STARKs daha küçük alanlar kullanmaya başladı: önce Goldilocks, ardından Mersenne31 ve BabyBear.
Bu dönüşüm, kanıtlama hızını büyük ölçüde artırdı. Örneğin, Starkware artık bir M3 dizüstü bilgisayarda saniyede 620.000 Poseidon2 hash'ini kanıtlayabiliyor. Bu, Poseidon2'yi bir hash fonksiyonu olarak güvenilir bulduğumuz sürece, verimli ZK-EVM geliştirme sorununu çözebileceğimiz anlamına geliyor. Peki bu teknolojiler nasıl çalışıyor? Küçük alanlardaki kanıtlar nasıl inşa ediliyor? Bu makale bu ayrıntıları inceleyecek ve özellikle Mersenne31 alanıyla uyumlu Circle STARKs çözümüne odaklanacak.
Küçük alanlar kullanırken sık karşılaşılan sorunlar
Hash tabanlı bir kanıt oluştururken, önemli bir teknik, polinom özelliklerini dolaylı olarak doğrulamak için polinomun rastgele noktalar üzerindeki değerlendirmesini kullanmaktır. Bu, kanıt sürecini büyük ölçüde basitleştirebilir.
Örneğin, protokolün A polinomunun bir taahhüdünü oluşturmanızı gerektirdiğini varsayalım, A^3(x) + x - A(ωx) = x^N koşulunu sağlamalıdır. Protokol, rastgele bir r koordinatı seçmenizi ve A(r)^3 + r - A(ωr) = r^N olduğunu kanıtlamanızı isteyebilir. Ardından A(r) = c'yi geriye doğru çıkarırsınız, Q = (A - c)/(X - r)'in bir polinom olduğunu kanıtlayabilirsiniz.
Saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmemiz gerekiyor. Eliptik eğriye dayalı protokollerde bu oldukça basit: r olarak rastgele bir 256 bit sayı seçebiliriz. Ancak küçük alanlı STARK'larda, yalnızca yaklaşık 2 milyar r seçeneği var, saldırganlar bu durumu deneme-yanılma ile aşabilir.
Bu sorunun iki çözümü var:
Birden fazla rastgele kontrol yapmak
Genişletilmiş Alan
Birçok rastgele kontrol basit ve etkilidir, ancak verimlilik sorunları olabilir. Genişletilmiş alanlar karmaşık sayılara benzer, ancak sonlu alanlara dayanır. Yeni bir değer α tanıtıyoruz ve α^2=belirli bir değer olarak beyan ediyoruz. Bu şekilde, sonlu alanlarda daha karmaşık işlemler yapabilen yeni bir matematiksel yapı oluşturulmuştur.
Genişletilmiş alanlar sayesinde, güvenlik ihtiyaçlarını karşılamak için yeterli değere sahibiz. Çoğu matematiksel işlem hala temel alanda gerçekleştirilirken, yalnızca güvenliği artırmak gerektiğinde daha büyük alanlar kullanılır.
Düzenli CUMA
FRI (Hızlı Reed-Solomon Etkileşimli) protokolü, SNARK veya STARK inşa etmenin önemli bir adımıdır. Bu, kanıt polinomunun derecesi d olan bir sorunu, derecesi d/2 olan bir sorunun kanıtı haline getirerek doğrulama sürecini basitleştirir. Bu işlem birkaç kez tekrarlanabilir, her seferinde sorun yarı yarıya basitleştirilir.
FRI'nin çalışma prensibi tekrarlayan basitleştirme sürecidir. Çok değişkenli polinomun derecesinin d olduğunu kanıtlamakla başlayarak, bir dizi adım aracılığıyla nihayet d/2 derecesinin kanıtına ulaşılır. Her basitleştirme sonrasında, üretilen polinomun derecesi kademeli olarak azalır. Eğer belirli bir aşamada çıkan sonuç beklenildiği gibi değilse, o tur kontrolü başarısız olur.
Alanın kademeli olarak azaltılmasını sağlamak için ikiye bir eşleme kullanılmıştır. Bu eşleme, veri kümesinin boyutunu yarıya indirirken aynı özellikleri korumaya olanak tanır. Bu işlem, çember üzerindeki bir segmentin çember boyunca iki tur genişletilmesi süreci olarak hayal edilebilir.
Eşleme teknolojisinin etkili olabilmesi için, orijinal çarpma alt grubunun boyutunun büyük bir 2'nin kuvvetini faktör olarak içermesi gerekir. BabyBear'ın modülü, maksimum çarpma alt grubunun tüm sıfır olmayan değerleri içermesini sağlar, bu teknoloji için oldukça uygundur. Mersenne31'in çarpma alt grubunun boyutu yalnızca bir 2'nin kuvveti faktörüne sahiptir, bu da uygulama alanını kısıtlar.
Mersenne31 alanı, 32 bit CPU/GPU'larda aritmetik işlemler için oldukça uygundur ve BabyBear alanından yaklaşık 1.3 kat daha hızlıdır. Mersenne31 alanında FRI uygulamak, hesaplama verimliliğini önemli ölçüde artıracaktır.
Circle FRI
Circle STARKs'ın inceliği, verilen bir asal p için, benzer ikiye bir özelliklere sahip p büyüklüğünde bir grup bulunabilmesidir. Bu grup, x^2 mod p'nin belirli bir değere eşit olduğu noktalar gibi belirli koşulları karşılayan noktaların kümesinden oluşur.
Bu noktalar toplama kuralını izler: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
Çift biçimi şudur: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI öncelikle tüm noktaları bir doğru üzerinde toplar, ardından rastgele lineer kombinasyon yaparak bir boyutlu çok terimli P(x) elde eder. İkinci turdan itibaren, haritalama şu hale gelir: f0(2x^2-1) = (F(x) + F(-x))/2
Bu haritalama, her seferinde küme boyutunu yarıya indirir ve daire üzerindeki iki karşıt noktanın x koordinatını, çarpan noktası x koordinatına dönüştürür. Bu iki boyutlu alanda gerçekleştirilebilir, ancak bir boyutlu işlem daha etkilidir.
Daire FFT'leri
Circle grubu aynı zamanda FFT'yi destekler, yapısı FRI'ye benzerdir. Circle FFT'nin işlediği nesne Riemann-Roch alanıdır, katı çok terimli değil. Circle FFT'nin çıktısı olan katsayılar Circle FFT'ye özgü bir temeldir.
Geliştirici olarak, bunu neredeyse tamamen göz ardı edebilirsiniz. STARK'lar, çok terimli ifadeleri değerlendirme değeri kümesi olarak saklamak için yalnızca ihtiyaç duyar. FFT'nin gerekli olduğu tek yer, düşük dereceli genişlemedir: N değer verildiğinde, aynı çok terim üzerinde k*N değer üretmektir.
Bölme İşlemi
Circle STARKs'te, tek bir nokta ile doğrusal bir fonksiyon kullanılamadığından, geleneksel çarpma işlemlerinin yerine farklı teknikler kullanmak zorundayız. Sanal bir nokta ekleyerek, iki nokta üzerinde değerlendirme yaparak bunu kanıtlamak zorundayız.
Eğer polinom P, x1'de y1'e, x2'de y2'ye eşitse, bu iki noktada eşit olan L interpolasyon fonksiyonunu seçeriz. Sonra P-L'nin bu iki noktada sıfır olduğunu ispatlayarak, L'yi L'ye bölerek Q'nun bir polinom olduğunu kanıtlarız.
Kaybolan polinomlar
Circle STARKs'te kaybolan polinom şöyledir:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Bu, katlama fonksiyonundan türetilebilir: Circle STARKs'ta x → 2x^2 - 1'i tekrar kullanma. İlk tur özel bir işleme ihtiyaç duyar.
Ters bit sırası
Circle STARKs, son basamak hariç her basamağı ters çevirerek değiştirilmiş bir ters sıralama kullanır ve diğer basamakların ters çevrilip çevrilmeyeceğine son basamak karar verir. Bu, Circle STARKs'a özgü katlama yapısını yansıtır.
Verimlilik
Circle STARKs çok verimlidir. Hesaplamalar genellikle şunları içerir:
Yerel aritmetik: İş mantığı için kullanılır
Yerel aritmetik: Kriptografi için (, Poseidon hash'i ) gibi
Parametreleri Bulma: Çeşitli hesaplamaları gerçekleştirmek için tablo üzerinden değer bulma
Circle STARKs, hesaplama alanını tam olarak kullanarak daha az israf yapar. Binius'a göre biraz daha zayıf, ancak kavram daha basit.
Sonuç
Circle STARKs, geliştiriciler için normal STARKs kadar karmaşık değildir. Circle FRI ve FFT'leri anlamak, diğer özel FFT'leri anlamaya yardımcı olabilir. Şu anda STARKs temel katman verimliliği sınırına yakın, gelecekteki optimizasyon yönleri şunları içerebilir:
Hash fonksiyonunun ve imzanın aritmetik verimliliğini maksimize et
Paralelleşmeyi artırmak için özyinelemeli yapı
Geliştirme deneyimini iyileştirmek için aritmetik sanal makine
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
19 Likes
Reward
19
4
Repost
Share
Comment
0/400
NftBankruptcyClub
· 08-09 22:10
Yazı küçük olunca verimlilik arttı...666
View OriginalReply0
GasWhisperer
· 08-09 22:08
hmm... daha küçük alanlar = daha hızlı kanıtlar, ama poseidon2'ye güvenebilir miyiz? bu verimlilik/güvenlik ikilemi hakkında kararsız hissediyorum açıkçası
View OriginalReply0
alpha_leaker
· 08-09 21:58
Stark biraz korkutucu.
View OriginalReply0
ChainDetective
· 08-09 21:54
Ancak anladım, temelde hacmi küçültmek ve hızlı hesaplamak.
Circle STARKs: Küçük alan yüksek verimli ZK kanıtlarının araştırılması ve突破
Circle STARKs'ı Keşfet
Son yıllarda, STARKs protokol tasarımı, daha küçük alanlar kullanmaya doğru bir eğilim göstermektedir. İlk STARKs üretim uygulamaları 256 bit alan kullanıyordu, yani büyük sayılar üzerinde modül işlemleri yapılıyordu. Ancak bu tasarımın verimliliği düşüktü ve büyük sayıları işlemek çok fazla hesap gücü israfına yol açıyordu. Bu sorunu çözmek için, STARKs daha küçük alanlar kullanmaya başladı: önce Goldilocks, ardından Mersenne31 ve BabyBear.
Bu dönüşüm, kanıtlama hızını büyük ölçüde artırdı. Örneğin, Starkware artık bir M3 dizüstü bilgisayarda saniyede 620.000 Poseidon2 hash'ini kanıtlayabiliyor. Bu, Poseidon2'yi bir hash fonksiyonu olarak güvenilir bulduğumuz sürece, verimli ZK-EVM geliştirme sorununu çözebileceğimiz anlamına geliyor. Peki bu teknolojiler nasıl çalışıyor? Küçük alanlardaki kanıtlar nasıl inşa ediliyor? Bu makale bu ayrıntıları inceleyecek ve özellikle Mersenne31 alanıyla uyumlu Circle STARKs çözümüne odaklanacak.
Küçük alanlar kullanırken sık karşılaşılan sorunlar
Hash tabanlı bir kanıt oluştururken, önemli bir teknik, polinom özelliklerini dolaylı olarak doğrulamak için polinomun rastgele noktalar üzerindeki değerlendirmesini kullanmaktır. Bu, kanıt sürecini büyük ölçüde basitleştirebilir.
Örneğin, protokolün A polinomunun bir taahhüdünü oluşturmanızı gerektirdiğini varsayalım, A^3(x) + x - A(ωx) = x^N koşulunu sağlamalıdır. Protokol, rastgele bir r koordinatı seçmenizi ve A(r)^3 + r - A(ωr) = r^N olduğunu kanıtlamanızı isteyebilir. Ardından A(r) = c'yi geriye doğru çıkarırsınız, Q = (A - c)/(X - r)'in bir polinom olduğunu kanıtlayabilirsiniz.
Saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmemiz gerekiyor. Eliptik eğriye dayalı protokollerde bu oldukça basit: r olarak rastgele bir 256 bit sayı seçebiliriz. Ancak küçük alanlı STARK'larda, yalnızca yaklaşık 2 milyar r seçeneği var, saldırganlar bu durumu deneme-yanılma ile aşabilir.
Bu sorunun iki çözümü var:
Birçok rastgele kontrol basit ve etkilidir, ancak verimlilik sorunları olabilir. Genişletilmiş alanlar karmaşık sayılara benzer, ancak sonlu alanlara dayanır. Yeni bir değer α tanıtıyoruz ve α^2=belirli bir değer olarak beyan ediyoruz. Bu şekilde, sonlu alanlarda daha karmaşık işlemler yapabilen yeni bir matematiksel yapı oluşturulmuştur.
Genişletilmiş alanlar sayesinde, güvenlik ihtiyaçlarını karşılamak için yeterli değere sahibiz. Çoğu matematiksel işlem hala temel alanda gerçekleştirilirken, yalnızca güvenliği artırmak gerektiğinde daha büyük alanlar kullanılır.
Düzenli CUMA
FRI (Hızlı Reed-Solomon Etkileşimli) protokolü, SNARK veya STARK inşa etmenin önemli bir adımıdır. Bu, kanıt polinomunun derecesi d olan bir sorunu, derecesi d/2 olan bir sorunun kanıtı haline getirerek doğrulama sürecini basitleştirir. Bu işlem birkaç kez tekrarlanabilir, her seferinde sorun yarı yarıya basitleştirilir.
FRI'nin çalışma prensibi tekrarlayan basitleştirme sürecidir. Çok değişkenli polinomun derecesinin d olduğunu kanıtlamakla başlayarak, bir dizi adım aracılığıyla nihayet d/2 derecesinin kanıtına ulaşılır. Her basitleştirme sonrasında, üretilen polinomun derecesi kademeli olarak azalır. Eğer belirli bir aşamada çıkan sonuç beklenildiği gibi değilse, o tur kontrolü başarısız olur.
Alanın kademeli olarak azaltılmasını sağlamak için ikiye bir eşleme kullanılmıştır. Bu eşleme, veri kümesinin boyutunu yarıya indirirken aynı özellikleri korumaya olanak tanır. Bu işlem, çember üzerindeki bir segmentin çember boyunca iki tur genişletilmesi süreci olarak hayal edilebilir.
Eşleme teknolojisinin etkili olabilmesi için, orijinal çarpma alt grubunun boyutunun büyük bir 2'nin kuvvetini faktör olarak içermesi gerekir. BabyBear'ın modülü, maksimum çarpma alt grubunun tüm sıfır olmayan değerleri içermesini sağlar, bu teknoloji için oldukça uygundur. Mersenne31'in çarpma alt grubunun boyutu yalnızca bir 2'nin kuvveti faktörüne sahiptir, bu da uygulama alanını kısıtlar.
Mersenne31 alanı, 32 bit CPU/GPU'larda aritmetik işlemler için oldukça uygundur ve BabyBear alanından yaklaşık 1.3 kat daha hızlıdır. Mersenne31 alanında FRI uygulamak, hesaplama verimliliğini önemli ölçüde artıracaktır.
Circle FRI
Circle STARKs'ın inceliği, verilen bir asal p için, benzer ikiye bir özelliklere sahip p büyüklüğünde bir grup bulunabilmesidir. Bu grup, x^2 mod p'nin belirli bir değere eşit olduğu noktalar gibi belirli koşulları karşılayan noktaların kümesinden oluşur.
Bu noktalar toplama kuralını izler: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Çift biçimi şudur: 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI öncelikle tüm noktaları bir doğru üzerinde toplar, ardından rastgele lineer kombinasyon yaparak bir boyutlu çok terimli P(x) elde eder. İkinci turdan itibaren, haritalama şu hale gelir: f0(2x^2-1) = (F(x) + F(-x))/2
Bu haritalama, her seferinde küme boyutunu yarıya indirir ve daire üzerindeki iki karşıt noktanın x koordinatını, çarpan noktası x koordinatına dönüştürür. Bu iki boyutlu alanda gerçekleştirilebilir, ancak bir boyutlu işlem daha etkilidir.
Daire FFT'leri
Circle grubu aynı zamanda FFT'yi destekler, yapısı FRI'ye benzerdir. Circle FFT'nin işlediği nesne Riemann-Roch alanıdır, katı çok terimli değil. Circle FFT'nin çıktısı olan katsayılar Circle FFT'ye özgü bir temeldir.
Geliştirici olarak, bunu neredeyse tamamen göz ardı edebilirsiniz. STARK'lar, çok terimli ifadeleri değerlendirme değeri kümesi olarak saklamak için yalnızca ihtiyaç duyar. FFT'nin gerekli olduğu tek yer, düşük dereceli genişlemedir: N değer verildiğinde, aynı çok terim üzerinde k*N değer üretmektir.
Bölme İşlemi
Circle STARKs'te, tek bir nokta ile doğrusal bir fonksiyon kullanılamadığından, geleneksel çarpma işlemlerinin yerine farklı teknikler kullanmak zorundayız. Sanal bir nokta ekleyerek, iki nokta üzerinde değerlendirme yaparak bunu kanıtlamak zorundayız.
Eğer polinom P, x1'de y1'e, x2'de y2'ye eşitse, bu iki noktada eşit olan L interpolasyon fonksiyonunu seçeriz. Sonra P-L'nin bu iki noktada sıfır olduğunu ispatlayarak, L'yi L'ye bölerek Q'nun bir polinom olduğunu kanıtlarız.
Kaybolan polinomlar
Circle STARKs'te kaybolan polinom şöyledir: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Bu, katlama fonksiyonundan türetilebilir: Circle STARKs'ta x → 2x^2 - 1'i tekrar kullanma. İlk tur özel bir işleme ihtiyaç duyar.
Ters bit sırası
Circle STARKs, son basamak hariç her basamağı ters çevirerek değiştirilmiş bir ters sıralama kullanır ve diğer basamakların ters çevrilip çevrilmeyeceğine son basamak karar verir. Bu, Circle STARKs'a özgü katlama yapısını yansıtır.
Verimlilik
Circle STARKs çok verimlidir. Hesaplamalar genellikle şunları içerir:
Circle STARKs, hesaplama alanını tam olarak kullanarak daha az israf yapar. Binius'a göre biraz daha zayıf, ancak kavram daha basit.
Sonuç
Circle STARKs, geliştiriciler için normal STARKs kadar karmaşık değildir. Circle FRI ve FFT'leri anlamak, diğer özel FFT'leri anlamaya yardımcı olabilir. Şu anda STARKs temel katman verimliliği sınırına yakın, gelecekteki optimizasyon yönleri şunları içerebilir: