Circle STARKs'i Keşfet

Son yıllarda, STARKs protokol tasarımında eğilim daha küçük alanların kullanılmasına doğru yönelmiştir. İ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 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 kullanım sağlamaz ve birçok işlem gücünün israfına yol açar. 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ı artırdı; örneğin Starkware, bir M3 dizüstü bilgisayarında saniyede 620.000 Poseidon2 hash değeri kanıtlayabiliyor. Bu, Poseidon2'yi hash fonksiyonu olarak güvenmeyi göze aldığımız sürece, verimli bir ZK-EVM geliştirme sorununun çözülebileceği anlamına geliyor. Peki bu teknolojiler nasıl çalışıyor? Bu kanıtlar daha küçük alanlarda nasıl oluşturuluyor? 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 adlı bir çözümü özel olarak vurgulayarak bu detayları inceleyecektir.

Daha Küçük Matematik Alanları Kullanırken Sık Görülen Sorunlar

Hash tabanlı kanıt oluştururken, çok önemli bir teknik, polinomun rastgele noktalar üzerindeki değerlendirme sonuçlarını 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 noktalar üzerindeki değerlendirme, genellikle tüm polinomla uğraşmaktan çok daha kolaydır.

Saldırıları önlemek için, saldırgan A'yı sağladıktan sonra r'yi seçmemiz gerekiyor. Fiat-Shamir, belirli parametreleri belirli bir hash değeri olarak ayarlayarak saldırıları önlemek için kullanılan bir tekniktir. Seçilen parametrelerin yeterince büyük bir kümeden gelmesi gerekir, böylece saldırgan bu parametreleri tahmin edemez veya kestiremez ve böylece sistemin güvenliğini artırır.

Eliptik eğri tabanlı protokoller ve 2019 dönemine ait STARK'larda, bu sorun oldukça basit: Tüm matematiksel işlemlerimizi 256 bitlik sayılar üzerinde gerçekleştiriyoruz, bu yüzden r'yi rastgele bir 256 bit sayısı olarak seçebiliriz, bu kadar yeterli. Ancak daha küçük alanlardaki STARK'larda bir sorunla karşılaşıyoruz: Seçilebilecek yalnızca yaklaşık 2 milyar farklı r değeri var, bu nedenle sahte bir kanıt oluşturmak isteyen bir saldırganın yalnızca 2 milyar kez denemesi gerekiyor; bu oldukça büyük bir iş yükü olsa da, kararlı bir saldırgan için tamamen mümkün!

Bu sorunun iki çözümü var:

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

Rastgele denetimlerin birden çok kez gerçekleştirilmesi en basit ve etkili yöntemdir: tek bir koordinatta denetim yapmak yerine, dört rastgele koordinatta tekrar denetim yapmak daha iyidir. Bu teorik olarak mümkündür, ancak verimlilik sorunları vardır. Eğer bir polinom ile belirli bir değerden küçük bir derece ile ilgileniyorsanız ve belirli bir büyüklükte bir alanda işlem yapıyorsanız, saldırgan aslında bu konumlarda normal görünen kötü niyetli polinomlar oluşturabilir. Dolayısıyla, protokolü başarılı bir şekilde bozup bozamayacakları bir olasılık meselesidir ve bu nedenle genel güvenliği artırmak için denetim turlarının sayısını artırmak gereklidir, böylece saldırganların saldırılarına etkili bir şekilde savunma sağlanabilir.

Bu, başka bir çözümü gündeme getiriyor: genişletilmiş alan, genişletilmiş alan çokluluğa benzer, ancak sınırlı alanlara dayanmaktadır. Yeni bir değeri, α olarak adlandırıyoruz ve onun belirli bir ilişkiyi sağladığını beyan ediyoruz, örneğin α2= belirli bir değer. Bu şekilde, sınırlı alanlarda daha karmaşık hesaplamalar yapabilen yeni bir matematiksel yapı oluşturuyoruz. Bu genişletilmiş alanda, çarpma hesaplaması yeni değer α'nın çarpımı olarak dönüşüyor. Artık genişletilmiş alanda değer çiftleri ile işlem yapabiliriz, sadece tek bir sayı ile değil. Örneğin, Mersenne veya BabyBear gibi alanlarda çalışıyorsak, bu tür bir genişletme daha fazla değer seçeneği sunarak güvenliği artırmamıza olanak tanır. Alanın boyutunu daha da artırmak için aynı tekniği tekrar uygulayabiliriz. α'yı kullandığımız için, yeni bir değer tanımlamamız gerekiyor, bu Mersenne31'de α'nın α2= belirli bir değeri sağlamak üzere seçilmesi şeklinde ortaya çıkıyor.

Alan genişletmesi sayesinde, artık güvenlik ihtiyaçlarımızı karşılamak için yeterli değere sahibiz. Eğer d'den küçük dereceli bir polinom işleniyorsa, her tur 104 bit güvenlik sağlayabilir. Bu, yeterli güvenlik garanti ettiğimiz anlamına gelir. Eğer 128 bit gibi daha yüksek bir güvenlik seviyesine ulaşmamız gerekiyorsa, protokole güvenliği artırmak için bazı ek hesaplama işlemleri ekleyebiliriz.

Genişletilmiş alan yalnızca FRI protokolünde ve diğer rastgele lineer kombinasyonlar gerektiren senaryolarda gerçekten kullanılır. Çoğu matematiksel işlem hala temel alanlarda gerçekleştirilir, bu temel alanlar genellikle p veya q modülü alanlarıdır. Aynı zamanda, neredeyse tüm hash verileri temel alanlarda gerçekleştirilir, bu nedenle her değer sadece dört bayt hash'lenmelidir. Bu, küçük alanların verimliliğinden yararlanırken, güvenlik artırımı gerektiğinde daha büyük alanlar kullanılabilir.

Normal FRI

SNARK veya STARK inşa ederken, genellikle ilk adım arithmetization'dır. Bu, herhangi bir hesaplama problemini, bazı değişkenler ve katsayıların polinom olduğu bir denkleme dönüştürmektir. Özellikle, bu denklem genellikle P(X,Y,Z)=0 şeklinde 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 probleminin çözümüyle ilişkilidir.

Bir çözümünüz olduğunu kanıtlamak için, önerdiğiniz değerin gerçekten makul bir polinom olduğunu (kesir değil, ya da bazı yerlerde bir polinom gibi görünüp diğer yerlerde farklı bir polinom olan bir şey değil, vb.) ve bu polinomların belirli bir maksimum dereceye sahip olduğunu kanıtlamanız gerekir. Bunun için, adım adım uygulanan rastgele doğrusal kombinasyon tekniğini kullandık:

• Diyelim ki bir polinom A'nın 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.

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

Öncelikle, FRI, d dereceli çok terimli bir polinomun doğrulanması sorununu d/2 dereceli çok terimli bir polinomun doğrulanması sorununa indirgemek suretiyle doğrulama sürecini basitleştirmiştir. Bu süreç, her seferinde sorunu yarıya indirerek tekrar edilebilir.

FRI'nin çalışma prensibi, bu basitleştirme sürecini tekrarlamaktır. Örneğin, eğer d dereceli bir çok terimden oluşan polinomdan başlıyorsanız, bir dizi adımda, sonunda çok terimli polinomun derecesinin d/2 olduğunu kanıtlayacaksınız. Her basitleştirmeden sonra, üretilen polinomun derecesi aşamalı olarak azalır. Eğer bir aşamadaki çıktı beklenen polinom derecesi değilse, o turdaki kontrol başarısız olur. Eğer birisi bu teknikle d dereceli olmayan bir polinomu itmeye çalışırsa, ikinci tur çıktısında, derecesinin beklenenden farklı olma olasılığı vardır, üçüncü turda bu durumun beklenenden farklı olma olasılığı daha da artar ve nihai kontrol başarısız olacaktır. Bu tasarım, gereksinimlere uymayan girişleri etkili bir şekilde tespit edip reddetmek için kullanılabilir. Eğer veri kümesi çoğu yerde d dereceli bir polinom ile eşitse, bu veri kümesinin FRI doğrulamasını geçme olasılığı vardır. Ancak, böyle bir veri kümesini oluşturmak için, saldırganın gerçek polinomu bilmesi gerekmektedir; bu nedenle, en ufak bir kanıt hatası bile, kanıtlayıcının "gerçek" bir kanıt üretebildiğini göstermektedir.

Burada olup bitenleri daha ayrıntılı bir şekilde anlamamıza ve her şeyin düzgün çalışması için gereken özelliklere bakalım. Her adımda, polinomun derecesini yarıya indiriyoruz ve aynı zamanda nokta kümesini (üzerinde yoğunlaştığımız noktaların kümesi) yarıya indiriyoruz. İlki, FRI protokolünün düzgün çalışabilmesi için anahtardır. İkincisi, algoritmanın çalışma hızını son derece artırır: her turdaki boyut bir önceki turdan yarıya düştüğünden, toplam hesaplama maliyeti O(N) olur, O(N*log(N)) yerine.

Bir alanı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 kümesinin 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ç kümesi aynı özellikleri korur. Diyelim ki bir çarpan alt grubundan başlıyoruz. Bu alt grup, her x elemanının 2x çarpanının da kümede bulunduğu bir S kümesidir. S kümesi üzerinde kare alma işlemi (yani kümedeki her x elemanını x^2'ye eşleme) yapıldığında, yeni S^2 kümesi de aynı özellikleri korur. Bu işlem, veri kümesinin boyutunu azaltmaya devam etmemize olanak tanır, nihayetinde yalnızca bir değer kalana kadar. Teorik olarak, veri kümesini sadece bir değere indirgememiz 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 kavis) dairenin çevresinde uzatarak iki tur döndürme süreci olarak düşünebilirsiniz. Örneğin, bir nokta dairenin çevresinde x derecesinde bir konumda bulunuyorsa, bu işlemden sonra 2x derecesine hareket eder. Dairenin çevresindeki her nokta 0 ile 179 derece arasında, 180 ile 359 derece arasında karşılık gelen bir noktaya sahiptir ve bu iki nokta örtüşecektir. Bu, x derecesinde bir noktayı 2x derecesine eşleştirdiğinizde, x+180 derecesindeki bir noktayla örtüşeceği anlamına gelir. Bu süreç tekrarlanabilir. Yani, bu eşleştirme işlemini birden fazla kez uygulayabilir ve her seferinde dairenin çevresindeki noktaları yeni konumlarına hareket ettirebilirsiniz.

Eşleme tekniğinin etkili olabilmesi için, orijinal çarpan alt grubunun boyutunun büyük bir 2'nin kuvveti olarak faktörü olması gerekir. BabyBear, belirli bir modüle sahip bir sistemdir ve modülü, maksimum çarpan alt grubunun tüm sıfır olmayan değerleri içerdiği bir değerdir, bu nedenle alt grubun boyutu 2k−1'dir (burada k, modülün bit sayısıdır). Bu boyuttaki alt gruplar, tekrarlı eşleme işlemleri uygulayarak polinomun derecesini etkili bir şekilde azaltmayı sağladığı için yukarıda belirtilen teknik için çok uygundur. BabyBear'da, 2^k boyutunda bir alt grup seçebilir (veya doğrudan tüm küme ile çalışabilirsiniz) ve ardından FRI yöntemini uygulayarak polinomun derecesini adım adım 15'e düşürebilir ve sonunda polinomun derecesini kontrol edebilirsiniz. Bu yöntem, modülün özelliklerini 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 sadece bir 2'nin kuvveti olarak faktörü vardır, bu da yalnızca 2'ye bir kez bölünebilmesi anlamına gelir. Sonraki işlemler yukarıda belirtilen tekniğe uygulanamaz, yani BabyBear'da olduğu gibi FFT kullanılarak etkili polinom derecesi azaltımı gerçekleştirilemez.

Mersenne31 alanı, mevcut 32 bit CPU/GPU işlemlerinde aritmetik işlemler yapmak için oldukça uygundur. Modülünün özellikleri (örneğin 2^31 - 1) sayesinde birçok işlem, verimli bit işlemleri kullanılarak gerçekleştirilebilir: Eğer iki sayının toplamı modülden büyükse, sonucu uygun bir aralığa indirmek için modül ile bit kaydırma işlemi yapılabilir. Bit kaydırma işlemi, son derece verimli bir işlemdir. Çarpma işlemlerinde, sonucu işlemek için özel CPU talimatları (genellikle yüksek bit kaydırma talimatları olarak adlandırılır) kullanılabilir. Bu talimatlar, çarpmanın yüksek bit kısmını verimli bir şekilde hesaplayabilir, böylece işlemlerin verimliliği artar. Mersenne31 alanında, yukarıda belirtilen özellikler nedeniyle, aritmetik işlemler BabyBear alanına göre yaklaşık 1.3 kat daha hızlıdır. Mersenne31, daha yüksek hesaplama verimliliği sunar. Eğer Mersenne31 alanında FRI gerçekleştirilebilirse, bu hesaplama verimliliğini önemli ölçüde artıracak ve FRI'nin uygulanmasını kolaylaştıracaktır.