Circle STARKs'ı Keşfet

Son yıllarda, STARKs protokol tasarımında eğilim, daha küçük alanların kullanılmasına doğru kaymaktadır. İlk STARKs üretim uygulamaları 256 bit alan kullanıyordu, yani büyük sayılar üzerinde mod işlemleri yapıyordu, bu da bu protokollerin eliptik eğri tabanlı imzalarla uyumlu olmasını sağlıyordu. Ancak bu tasarımın verimliliği oldukça düşüktür, genellikle bu büyük sayıların hesaplanması pratik bir işe yaramamaktadır ve çok fazla hesaplama gücü israfına neden olmaktadır. 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 bir M3 dizüstü bilgisayarda her saniye 620,000 Poseidon2 hash değeri kanıtlayabiliyor. Bu, Poseidon2'yi hash fonksiyonu olarak güvenmeye istekli olduğumuz sürece, verimli bir ZK-EVM geliştirmedeki zorluğu çözebileceğimiz anlamına geliyor. Peki, bu teknolojiler nasıl çalışıyor? Bu kanıtlar daha küçük alanlarda nasıl kuruluyor? Bu protokoller, Binius gibi çözümlerle karşılaştırıldığında nasıl? Bu makale, Mersenne31 alanıyla uyumlu benzersiz özelliklere sahip Circle STARKs adı verilen bir çözümü özellikle inceleyecek.

Küçük matematik alanları kullanırken sık karşılaşılan sorunlar

Hash tabanlı bir kanıt ( veya herhangi bir tür kanıt ) oluştururken, çok önemli bir teknik, polinomun rastgele noktalar üzerindeki değerlendirme sonuçları aracılığıyla kanıtlayarak, polinomun özelliklerini dolaylı olarak doğrulamaktır. Bu yöntem, kanıt sürecini büyük ölçüde basitleştirebilir, çünkü rastgele noktalardaki değerlendirmeler genellikle tüm polinomu işlemekten çok daha kolaydır.

Örneğin, bir kanıt sisteminin, bir polinom için bir taahhüt oluşturmanızı gerektirdiğini varsayalım, A, A^3(x) + x - A(ωx) = x^N(ZK-SNARK protokolünde oldukça yaygın bir kanıt türüdür ). Protokol, sizden rastgele bir koordinat r seçmenizi ve A(r) + r - A(ωr) = r^N olduğunu kanıtlamanızı isteyebilir. Ardından, A(r) = c'yi geriye doğru çıkararak, Q = (A - c)/(X - r) bir polinom olduğunu kanıtlamış olursunuz.

Saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmemiz gerekiyor. Seçilen parametreler, saldırganın bu parametreleri tahmin edememesi veya kestiremeyebilmesi için yeterince büyük bir kümeden gelmelidir, böylece sistemin güvenliğini artırır.

Eliptik eğri tabanlı protokoller ve 2019 dönemine ait STARK'lar söz konusu olduğunda, bu problem oldukça basit: Tüm matematiksel işlemlerimizi 256 bitlik sayılar üzerinde yapıyoruz, bu nedenle r'yi rastgele bir 256 bitlik sayı olarak seçebiliriz, bu kadar basit. Ancak, daha küçük alanlardaki STARK'larda bir sorunla karşılaşıyoruz: Seçilebilecek yalnızca yaklaşık 2 milyar olası r değeri var, bu nedenle bir kanıtı sahtelemek isteyen bir saldırganın yalnızca 2 milyar kez denemesi gerekiyor; bu, büyük bir iş yükü olsa da, kararlı bir saldırgan için tamamen yapılabilir!

Bu sorunun iki çözümü var:

• Birçok rastgele kontrol gerçekleştirin
• Genişletilmiş alan

Rastgele kontrollerin birden fazla kez yapılması en basit ve etkili yöntemdir: Tek bir koordinatta kontrol etmek yerine, dört rastgele koordinatta tekrar kontrol etmeyi tercih edin. Bu teorik olarak mümkündür, ancak verimlilik sorunları vardır. Eğer belirli bir değerin altında bir dereceye sahip bir çokterimle uğraşıyorsanız ve belirli bir boyuttaki bir alanda işlem yapıyorsanız, saldırgan aslında bu pozisyonlarda oldukça normal görünen kötü niyetli çokterimler oluşturabilir. Dolayısıyla, protokolü başarıyla bozup bozamayacakları bir olasılık sorunudur, bu nedenle genel güvenliği artırmak ve saldırganların saldırılarına karşı etkili bir şekilde savunma sağlayabilmek için kontrol sayısını artırmak gerekmektedir.

Bu, başka bir çözümü gündeme getiriyor: genişletilmiş alan, genişletilmiş alanlar, sonlu alanlara dayanan çoklulara benzer. Yeni bir değeri α olarak tanıtıyoruz ve bunun belirli bir ilişkiyi sağladığını bildiriyoruz, örneğin α^2=some value. Bu şekilde, sonlu alanlarda daha karmaşık hesaplamalar yapabilen yeni bir matematiksel yapı oluşturuyoruz. Bu genişletilmiş alanda, çarpma hesaplaması yeni değer olan α'nın çarpımı olarak dönüşüyor. Artık sadece tek bir sayı değil, genişletilmiş alanda değer çiftleri üzerinde işlem yapabiliyoruz. Örneğin, Mersenne veya BabyBear gibi alanlarda çalışıyorsak, bu tür bir genişletme, daha fazla değer seçeneğimiz olmasını sağlayarak güvenliği artırır. Alanın boyutunu daha da artırmak için aynı tekniği tekrar uygulayabiliriz. α'yı kullandığımız için, yeni bir değeri tanımlamamız gerekiyor; bu, Mersenne31'de α'yı α^2=some value olacak şekilde seçmek olarak ortaya çıkıyor.

Uzantı alanı sayesinde, artık güvenlik ihtiyaçlarımızı karşılamak için yeterince değerimiz var. Eğer işlenen polinomun derecesi d'den küçükse, her tur 104 bit güvenlik sağlayabilir. Bu, yeterli güvenlik sağladığımız anlamına geliyor. Eğer 128 bit gibi daha yüksek bir güvenlik seviyesi gerekiyorsa, protokole ek hesaplamalar ekleyerek güvenliği artırabiliriz.

Genişletilmiş alan, yalnızca FRI(Fast Reed-Solomon Interactive) protokolü ve diğer rastgele lineer kombinasyonlar gerektiren senaryolar içinde pratik olarak kullanılmaktadır. Matematiksel işlemlerin çoğu hala temel alanlar üzerinde gerçekleştirilmektedir; bu temel alanlar genellikle mod p veya q alanlarıdır. Aynı zamanda, neredeyse tüm hash verileri de temel alanlar üzerinde gerçekleştirilmektedir, bu nedenle her değer yalnızca dört baytı hash'lemek zorundadır. Bu, küçük alanların verimliliğini kullanırken, güvenlik artırımı gerektiğinde daha büyük alanlar kullanılmasına olanak tanır.

Düzenli FRI

SNARK veya STARK inşa ederken, ilk adım genellikle arithmetization'dır. Bu, her türlü hesaplama sorununu, belirli değişkenlerin ve katsayıların polinomlar olduğu bir denkleme dönüştürmektir. Özellikle, bu denklem genellikle P(X,Y,Z)=0 gibi görünür; burada P bir polinomdur, X, Y ve Z verilen parametrelerdir ve çözücünün X ve Y'nin değerlerini sağlaması gerekir. Böyle bir denkleme sahip olunduğunda, bu denklemin çözümü, temel hesaplama sorununun çözümü ile ilişkilidir.

Bir çözümünüz olduğunu kanıtlamak için, sunduğunuz değerin gerçekten makul bir polinom ( olduğunu ve bir kesir olmadığını, ya da bazı yerlerde bir polinom gibi görünüp diğer yerlerde farklı bir polinom olduğunu kanıtlamanız gerekiyor, vb. ), ve bu polinomların belirli bir maksimum dereceye sahip olması gerekiyor. Bunun için, adım adım uygulanan rastgele lineer kombinasyon tekniğini kullandık:

• Diyelim ki bir A çokpolinomunun değerlendirme değeri var, onun derecesinin 2^20'den küçük olduğunu kanıtlamak istiyorsun.
• Çok terimli B(x^2) = A(x) + A(-x),C(x^2) = (A(x) - A(-x))/x
• D, B ve C'nin rastgele lineer kombinasyonudur, yani D=B+rC, burada r rastgele bir katsayıdır.

Temelde, olan şey B'nin çift katsayıları A'dan ve C'nin tek katsayılarıyla izole edilmesidir. B ve C verildiğinde, orijinal polinom A'yı geri kazanabilirsiniz: A: 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 derecesinden bir eksik olacaktır. Çünkü çift terimler ve tek terimlerin kombinasyonu dereceleri artırmaz. D, B ve C'nin rastgele lineer bir kombinasyonu olduğu için, D'nin derecesi de A'nın derecesi olmalıdır, bu da D'nin derecesi üzerinden A'nın derecesinin gereksinimleri karşılayıp karşılamadığını doğrulamanızı sağlar.

Öncelikle, FRI, d dereceli bir polinomun doğrulanması sorununu d/2 dereceli bir polinomun doğrulanması sorununa indirgererek doğrulama sürecini basitleştirmiştir. Bu süreç, her seferinde sorununu yarıya indirerek birçok kez tekrarlanabilir.

FRI'nin çalışma prensibi bu basitleştirme sürecini tekrarlamaktır. Örneğin, eğer d dereceli bir polinom ispatlamaya başlıyorsanız, bir dizi adım aracılığıyla, sonunda polinomun derecesinin d/2 olduğunu ispatlayacaksınız. Her basitleştirmeden sonra, üretilen polinomun derecesi kademeli olarak azalır. Eğer bir aşamanın çıktısı beklenen polinom derecesi değilse, o tur kontrolü başarısız olacaktır. Eğer biri bu teknikle d dereceli bir polinom olmayan bir şeyi itmeye çalışırsa, ikinci tur çıktısında, o derecenin beklenenle uyumlu olmama olasılığı vardır, üçüncü turda uyumsuzluk olma olasılığı daha yüksektir ve nihai kontrol başarısız olacaktır. Bu tasarım, gereksinimlere uymayan girdileri etkili bir şekilde tespit edip reddetme yeteneğine sahiptir. Eğer veri setinin çoğu yerinde d dereceli bir polinom eşitse, bu veri seti FRI doğrulamasından geçme potansiyeline sahiptir. Ancak, böyle bir veri seti oluşturmak için, saldırganın gerçek polinomu bilmesi gerekmektedir, bu nedenle en küçük bir hata bile, ispatlayıcının "gerçek" bir ispat üretebildiğini göstermektedir.

Burada olanları daha ayrıntılı olarak anlamamıza ve her şeyin düzgün çalışması için gereken özelliklere bakalım. Her adımda, çokpolinomun derecesini yarıya indiriyoruz ve aynı zamanda ilgilendiğimiz nokta kümesi ('yi de yarıya indiriyoruz. İlki, FRI) Hızlı Reed-Solomon Etkileşimli( protokolünün düzgün çalışabilmesi için kritik öneme sahip. İkincisi ise algoritmanın çalışma hızını inanılmaz derecede artırıyor: Her turun ölçeği bir önceki turdan yarıya düştüğü için, toplam hesaplama maliyeti O)N( olur, O)N*log(N() yerine.

Alanların kademeli olarak azaltılmasını sağlamak için, her noktanın iki noktadan birine eşlendiği bir ikiye bir eşleme kullanılmıştır. Bu eşleme, veri setinin boyutunu yarıya indirmemize olanak tanır. Bu ikiye bir eşlemenin önemli bir avantajı, tekrarlanabilir olmasıdır. Yani, bu eşlemeyi uyguladığımızda elde edilen sonuç seti hala aynı özellikleri korur. Farz edelim ki, bir çarpan alt grubu ) multiplicative subgroup ( ile başlıyoruz. Bu alt grup, her x elemanının 2x çarpanının da kümede bulunduğu bir S kümesidir. Eğer S kümesine kare alma işlemi uygularsak ), yani kümedeki her x elemanını x^2('e eşlersek, yeni S^2 kümesi de aynı özellikleri korur. Bu işlem, veri setinin boyutunu azaltmaya devam etmemizi sağlar, ta ki sonunda yalnızca bir değer kalana kadar. Teorik olarak veri setini sadece bir değere indirmek mümkün olsa da, pratikte genellikle daha küçük bir kümeye ulaşmadan önce durulur.

Bu işlemi, bir dairenin çevresindeki bir çizgiyi ), örneğin bir doğru parçası veya yay ( boyunca dairenin çevresinde döndürme süreci olarak düşünebilirsiniz. Örneğin, bir nokta dairenin çevresinde x derecelik bir konumda ise, bu işlemden sonra 2x derecelik bir konuma hareket eder. Dairenin çevresindeki her nokta 0 ile 179 derece arasında bir konuma sahiptir ve 180 ile 359 derece arasında ona karşılık gelen bir nokta vardır; bu iki nokta örtüşecektir. Bu, bir noktayı x dereceden 2x derecesine haritalandırdığınızda, bunun x+180 derecede bulunan bir nokta ile örtüşeceği anlamına gelir. Bu süreç tekrarlanabilir. Yani, bu haritalama işlemini birden fazla kez uygulayabilir, her seferinde dairenin çevresindeki noktaları yeni konumlarına taşıyabilirsiniz.

![Vitalik'in Yeni Eseri: Circle STARKs'i Keşfet])https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp(

Eşleme teknolojisinin etkili olabilmesi için, orijinal çarpan alt grubunun boyutunun büyük bir 2'nin kuvveti olarak faktör içermesi gerekir. BabyBear, belirli bir modül ile çalışan bir sistemdir; modülü, maksimum çarpan alt grubunun tüm sıfır olmayan değerleri içermesini sağlayacak bir değerdir. Bu nedenle alt grubun boyutu 2k−1)'dir; burada k, modülün bit sayısıdır (. Bu boyuttaki alt grup, yukarıda belirtilen teknoloji için oldukça uygundur çünkü tekrarlayan eşleme işlemlerinin uygulanmasıyla polinomun derecesini etkili bir şekilde azaltmaya olanak tanır. BabyBear'da, 2^k boyutunda bir alt grubu ) seçebilir veya doğrudan tüm küme ( kullanarak, ardından FRI yöntemini uygulayarak polinomun derecesini kademeli olarak 15'e indirgeyebilir ve sonunda polinomun derecesini kontrol edebilirsiniz. Bu yöntem, modülün özellikleri ve çarpan alt grubunun boyutunu kullanarak hesaplama sürecini oldukça verimli hale getirir. Mersenne31, çarpan alt grubunun boyutunun 2^31 - 1 olduğu başka bir sistemdir. Bu durumda, çarpan alt grubunun boyutu yalnızca bir 2'nin kuvveti olarak faktör içerir; bu da onun sadece bir kez 2'ye bölünebileceği anlamına gelir. Sonrasındaki işleme yukarıda belirtilen teknoloji uygulanamaz; yani, BabyBear'da olduğu gibi FFT kullanarak etkili bir polinom derecesi azaltma işlemi yapılamaz.

Mersenne31 alanı mevcut 32 bit CPU/GPU işlemlerinde aritmetik işlemler yapmak için oldukça uygundur. Çünkü modülün özelliği ) gibi 2^31 - 1( birçok işlemin verimli bit işlemleri kullanılarak tamamlanmasını sağlar: Eğer iki sayının toplamı modülü aşarsa, sonuç modül ile bitwise işlemi yapılarak