Sıfır bilgi kanıtı iyi kardeş, STARKs kodu nasıl uygulanır?
Bu makalenin temel amacı, STARK algoritmasını dağıtmak için python dilini nasıl kullanacağınızı göstermektir.
STARKs (Ölçeklenebilir Şeffaf Bilgi Argümanı) bir ispat oluşturma tekniğidir.Bu ispatta, f (x) = y, burada f'nin hesaplanması uzun zaman alabilir, ancak bu ispat hızlıca doğrulanabilir. STARK "çift genişletmedir": t adım gerektiren bir hesaplama için, ispatın tamamlanması yaklaşık O (t * log (t)) adımı alacaktır. Bu en uygun durum olabilir ve ~ O (log2 (t)) Yalnızca adımlar doğrulanabilir Orta büyüklükteki T değerleri için, orijinal hesaplamadan çok daha hızlıdır. STARK'lar ayrıca gizlilik koruması için "sıfır bilgi kanıtı" özelliğine sahiptir. Doğrulanabilir gecikme işlevini tamamlamak için bu tür bir kullanım senaryosu uygulamamıza rağmen, bu tür bir doğa gerekli değildir, bu nedenle endişelenmemize gerek yoktur.
Öncelikle size birkaç açıklama vereyim:
Bu kod tam olarak incelenmemiştir; gerçek kullanım durumlarında hiçbir garanti yoktur
Kodun bu bölümü henüz ideal duruma ulaşmadı (Python dilinde yazılmıştır)
STARK'ların "gerçek durumu", belirli uygulama verimliliği nedenleriyle birincil alanlar yerine ikili alanlar kullanma eğilimindedir, ancak burada yazılan kodun yasal ve kullanılabilir olduğunu gösterirler.
STARK'ı kullanmanın gerçek bir yolu yoktur. Kullanılabilirliği artırırken kanıtlayanın ve doğrulayıcının karmaşıklığını azaltmak için farklı uygulamalar için farklı ayarlara ve sürekli araştırmaya sahip çok geniş bir şifreleme ve matematiksel mimaridir.
Bu makale, modulo işleminin ve asal sayı alanının nasıl çalıştığını herkesin bildiğini ummaktadır,
Ve polinom kavramları, enterpolasyon ve tahmin ile birleştirildi.
Şimdi birlikte anlayalım!
MIMC
STARK'ın işlev ekranı aşağıdadır:
def mimc (inp, adımlar, round_constants): başlangıç_süresi = aralıktaki i için zaman.zaman (adımlar-1): inp = (inp ** 3 + round_constants )% modül baskısı ("% .4f sn olarak hesaplanan MIMC"% (time.time-start_time)) dönüş girişiDurum olarak MIMC'yi seçtik çünkü (i) anlaşılması kolay ve (ii) gerçek dünyada çokça kullanılıyor. İşlev işlevi aşağıdaki şekilde gösterilmektedir:
Not: MIMC ile ilgili birçok tartışmada, tipik olarak XOR'un + yerine kullanıldığını görebilirsiniz; bunun nedeni, MIMC'nin toplamanın XOR olduğu ikili durumlarda kullanılabilmesidir; burada bunu asal sayılar alanında yapacağız.
Bizim durumumuzda, sabit nispeten küçük bir liste olacaktır (örneğin 64 bit) ve sürekli döngü yapmaya devam edecek (yani k'den sonra). MIMC'nin kendisi bu özelliği alabilir, çünkü MIMC geriye dönük hesaplamalar yapabilir (karşılık gelen çıktıdan girdi alabilir), ancak geriye dönük hesaplamalar ileriye dönük hesaplamalardan 100 kat daha uzun sürer (ve aynı anda ilerlemek için bir yön yoktur). Dolayısıyla geriye doğru hesaplama işlevini, senkronize edilemeyen bir işin kanıtı olarak düşünebilirsiniz ve ileriye doğru hesaplama işlevi bir doğrulama işlemi olarak kullanılabilir.
x- > x (2p-1) / 3, x- > X3'ün ters fonksiyonu; Fermat'ın küçük teoremine göre bu doğrudur, bu teorem Fermat'ın son teoremi kadar iyi bilinmese de matematiğe hala çok şey katmaktadır.
Doğrulayıcının MIMC'yi ileri yönde çalıştırmasını istemek yerine, daha etkili doğrulama için STARK kullanmaya çalışıyoruz. Geriye dönük hesaplamayı tamamladıktan sonra, kanıtlayıcı STARK hesaplamasını ileri yönde gerçekleştirebilir ve doğrulayıcı kolayca doğrulayabilir STARK. STARK hesaplamasının MIMC ileri ve geri arasındaki hız farkından daha küçük olabileceğini umuyoruz, bu nedenle kanıtlayıcının zamanına hala ilk geriye dönük hesaplama hakimdir. Bu bir STARK hesaplaması değildir. STARK sertifikasyonu, ilk hesaplama süresi ne kadar uzun olursa olsun, nispeten hızlı olacaktır (python dili algoritmasında, 0,05-0,3 saniye olabilir). Tüm hesaplamalar 2256 - 351 * 232 + 1 modülünde tamamlanacak; 2256'dan küçük en büyük asal sayı olduğu için asal modülü kullanıyoruz ve çarpan grup 232 alt küme içeriyor (yani, böyle bir g sayısı var, Dolayısıyla, 232 döngüden sonra, G asal sayı döngüsünün sürekli güç modu 1) 'e geri döner ve 6k + 5 şeklindedir. İlk özellik, FFT ve FRI algoritmalarının etkili sürümünü sağlamak, ikincisi ise MIMC'nin gerçekte geriye doğru hesaplanabilmesini sağlamaktır (bkz. Yukarıda x) > x (2p-1) / 3 Nasıl kullanılır).
Prime domain işlemleri
Polinom operasyonların yanı sıra uygun seviyeler oluşturarak ana alanlarda faaliyet gösteriyoruz. Kod aşağıdaki gibidir, ilki ondalık basamakların sayısıdır:
sınıf PrimeField: def __init __ (öz, modül): # Hızlı asallık testi assert pow (2, modül, modül) == 2 self.modulus = modül def add (self, x, y): return (x + y)% self .modulus def sub (self, x, y): return (xy)% self.modulus def mul (self, x, y): return (x * y)% self.modulusVe modülün tersine çevrilmesini hesaplamak için genişletilmiş Öklid algoritmasını kullanın (bu, ana alanda 1 / x'i hesaplamakla aynıdır):
# Genişletilmiş Öklid algoritmasını kullanarak modüler tersi def inv (öz, a): a == 0 ise: 0 lm döndür, hm = 1, 0 düşük, yüksek = a% self.modulus, self.modulus > 1: r = yüksek // düşük nm, yeni = hm-lm * r, yüksek-düşük * r lm, düşük, hm, yüksek = nm, yeni, lm, düşük getiri lm% self.modulusYukarıdaki algoritma nispeten pahalıdır; neyse ki, bazı durumlarda, birçok modüler ters hesaplama yapmamız gerekiyor.Montact toplu ters çevirme adı verilen birçok ters işlemi hesaplamamıza izin veren matematiksel bir yöntem var:
Modüler tersi hesaplamak için Montgomery toplu ters çevirme kullanın, giriş mor, çıktı yeşil, çarpım geçidi siyah ve kırmızı kare tek modüler tersi.
Aşağıdaki kod, bazı özel mantıkları içeren algoritmanın bir tezahürüdür. Tersine çevirdiğimiz set sıfırlar içeriyorsa, bu sıfırların tersini 0 olarak ayarlayacak ve devam edecektir.
def multi_inv (self, değerler): parsiyels = aralıktaki i için (uzunluk (değerler)): parsiyels.append (self.mul (parsiyeller, değerler veya 1)) inv = self.inv (bölümler) çıktıları = * aralıktaki i için uzunluk (değerler) (uzunluk (değerler), 0, -1): çıkışlar = self.mul (kısmi değerler, inv) değerler değilse 0 inv = self.mul (inv, değerler veya 1) dönüş çıktılarıAlgoritmanın bu bölümü, özellikle farklı derecelerin polinomları ile hesaplamaya başladığımızda, çok önemli olarak adlandırılan şeyi doğrulayacaktır. Şimdi bazı polinom hesaplamalara bakalım. Polinomu, i'nin i'inci sıra olduğu bir veri kümesi olarak ele alırız (örneğin, x3 + 2x + 1 olur). Bir polinomun bir noktada nasıl tahmin edileceği aşağıda açıklanmıştır:
# Bir noktadaki bir polinomu değerlendirin eval_poly_at (self, p, x): y = 0 power_of_x = 1 for i, p_coeff in enumerate (p): y + = power_of_x * p_coeff power_of_x = (power_of_x * x)% self.modulus return y% self.modulusZorluklar ve zorluklar
F.eval_poly_at (, 2) çıktısı nedir? Modül 31 mi?
Aşağıdaki açıklama cevaptır
Aslında, polinom toplama, çıkarma, çarpma ve bölme için kodlar da vardır; bu çok uzun bir toplama, çıkarma, çarpma ve bölme işlemidir. Çok önemli bir içerik, girdi olarak bir dizi x ve y koordinatlarını alan ve tüm bu noktalardan geçen en küçük polinomu döndüren Lagrangian interpolasyonudur (bunu polinom değerlendirmesinin tersi olarak düşünebilirsiniz):
# Belirtilen tüm xsdef zpoly'de (self, xs) 0 döndüren bir polinom oluşturun: xs cinsinden x için kök = aralıktaki j için kök.insert (0, 0) (len (kök) -1): kök - = kök * x dönüş def lagrange_interp (öz, xs, ys): # Ana pay polinomu oluşturun, ör. (x-x1) * (x-x2) * ... * (x-xn) kök = self.zpoly (xs) # Değer başına pay polinomları oluşturun, ör. X = x2, # (x-x1) * (x-x3) * ... * (x-xn) için ana polinomu her x koordinat numarasına bölerek = # Her bir x değerde pay poliçelerini değerlendirerek paydalar oluşturun = invdenoms = self.multi_inv (paylar) # Değer başına pay toplamının toplamı olan çıktı polinomu oluşturun # polinomlar, doğru y değerlerine sahip olacak şekilde yeniden ölçeklendirildi b = i için aralık (len (xs)): yslice = self.mul (ys , invdenoms ) aralıktaki j için (len (ys)): eğer nums ve ys : b + = nums * yslice dönüşüİlgili matematik bilgisi için lütfen bu makalenin M-N bölümüne bakın. Ayrıca Lagrange enterpolasyonunu 2'den düşük derece ve 4'ten küçük dereceli polinom operasyonlarını hızlandırmak için özel lagrange_interp_4 ve lagrange_interp_2 yöntemlerine sahip olacağımız unutulmamalıdır.
Hızlı Fourier dönüşümü
Yukarıdaki algoritmayı dikkatlice okursanız, Lagrangian interpolasyonunun ve çok noktalı değerlendirmenin (yani, derecesi N noktasında N'den küçük olan bir polinomun değerini bulmanın) örneğin 1000 nokta için iki kez sürdüğünü görebilirsiniz. Lagrange enterpolasyonunu bulmak birkaç milyon adım alır ve bir milyon nokta Lagrange enterpolasyonu trilyonlarca adım gerektirir. Bu kabul edilemez derecede düşük verimlilik, bu yüzden daha etkili bir algoritma, hızlı Fourier dönüşümü kullanmamız gerekiyor.
FFT yalnızca O (n * log (n)) süre alır (yani, 1000 noktanın hesaplanması 10.000 adım gerektirir ve 1 milyon noktanın hesaplanması 2000 adım gerektirir), ancak aralığı daha sınırlıdır; x koordinatı Tam bir birim kök kümesi olmalı ve N = 2k sırasını karşılamalıdır. Başka bir deyişle, N nokta varsa, o zaman x koordinatı, pN = 1 olduğunda, belirli bir P değerinin sürekli bir gücü olan 1, p, p2, p3 ... olmalıdır. Bu algoritma, çok noktalı hesaplama ve enterpolasyon hesaplaması için kullanılabilir ve yalnızca küçük bir parametrenin ayarlanması gerekir.
Aşağıda, algoritma ayrıntıları verilmiştir (bu basit bir ifade biçimidir; daha fazla ayrıntı için lütfen buradaki koda bakın)
def fft (vals, modül, root_of_unity): eğer len (vals) == 1: return vals L = fft (vals, modül, pow (root_of_unity, 2, modül)) R = fft (vals, modül, pow (root_of_unity, 2, modül)) o = i, (x, y) için numaralandırmada (zip (L, R)): y_times_root = y * pow (root_of_unity, i, modül) o = (x + y_times_root)% modül o = (x-y_times_root)% modül dönüşü odef inv_fft (vals, modül, root_of_unity): f = PrimeField (modül) # Ters FFT invlen = f.inv (uzunluk (vals)) dönüşKodu bir miktar girdi ile kendiniz çalıştırabilir ve istediğiniz sonuçları alıp alamayacağınıza bakabilirsiniz. Eval_poly_at kullandığınızda, beklediğiniz cevabı verin. Örneğin:
> > > fft.fft (, 337, 85, inv = Doğru) > > > f = poly_utils.PrimeField (337) > > >Fourier dönüşümü girdi olarak alacaktır ve amacı ilk öğe olarak x + x + + x ve ikinci öğe olarak x + x * 2 + + x * w ** (n-1) çıktısını almaktır. , Vb .; Hızlı Fourier Dönüşümü, verileri ikiye bölerek, her iki tarafta FFT gerçekleştirerek ve ardından sonuçları birleştirerek bunu başarabilir.
Yukarıdaki şekil, bilgilerin FFT işlemlerini nasıl gerçekleştirdiğinin bir açıklamasıdır. Lütfen FFT'nin verileri iki kez nasıl kopyaladığını ve bir öğe elde edene kadar yapıştırdığını unutmayın.
Şimdi, tüm parçaları bir araya getiriyoruz ve her şeyin nasıl olduğunu görüyoruz: def mk_mimc_proof (inp, adımlar, round_constants), bu, verilen girdinin adım sayısı olduğu MIMC işlevini çalıştırmanın yürütme sonucunun bir kanıtını oluşturur. İlk olarak, bazı assert fonksiyonları vardır:
# X koordinatları kümesini hesaplayın xs = get_power_cycle (root_of_unity, modül) sütun = aralıktaki i için (len (xs) // 4): x_poly = f.lagrange_interp_4 (,,) column.append (f.eval_poly_at (x_poly, special_x) ))Genişletme faktörü, genişleteceğimiz hesaplama yörüngesidir (MIMC işlevini yürüten "ara değerler" kümesi).
m2 = merkelize (sütun) # Örnekleme için sözde rastgele y endeksleri seçin # (m2, sütunun Merkle köküdür) ys = get_pseudorandom_indices (m2, len (sütun), 40) # Polinomdaki değerler için Merkle dallarını hesaplayın ve sütun dalları = ys'deki y için: branch.append (+)Adım sayısını 2 ^ 32'ye kadar genişletme faktörüyle çarpmamız gerekiyor, çünkü k > 32 yaşında, 2 ^ k kere birim kökümüz yok.
computational_trace_polynomial = inv_fft (computational_trace, modül, subroot) p_evaluation = fft (computational_trace_polynomial, modül, root_of_unity)İlk hesaplamamız hesaplanan yörüngeyi, yani hesaplanan tüm ara değerleri, girdiden çıktıya kadar elde etmek olacaktır.
adımları ileri sürmek < = 2 ** 32 // extension_factorassert is_a_power_of_2 (adımlar) ve is_a_power_of_2 (len (round_constants)) assert len (round_constants) < adımlarArdından, hesaplanan yörüngeyi bir polinomiye çevireceğiz ve sürekli değerleri birim kök g'nin sürekli gücünün yörüngesine "bırakacağız" (burada g ^ adımlar = 1) ve sonra daha büyük küme - birim kökü g2 hesaplayacağız. G2 ^ adımlarının sürekli gücü * 8 = 1 (g2 ^ 8 = g olduğuna dikkat edin) bir polinom olarak değerlendirilir.
# Aralıktaki i için hesaplamalı tracecomputational_trace = oluşturun (adımlar-1): computational_trace.append ((computational_trace ** 3 + round_constants )% modül) çıktı = computational_trace
Siyah: g1'in gücü. Mor: g2'nin gücü. Turuncu: 1. Sürekli birim kökünü bu şekilde düzenlenmiş bir daire olarak düşünebilirsiniz. Hesaplama yörüngesini g1'in kuvveti boyunca "yerleştiriyoruz" ve sonra aynı polinomun ara değerdeki değerini (yani g2'nin gücü) hesaplamak için genişletiyoruz.
MIMC'nin döngü sabitini bir polinoma dönüştürebiliriz. Bu döngüsel sabit zincirler çok yaygın olduğu için (bizim testimizde her 64 adım gerçekleştirilecek), sonunda 64. dereceden bir polinom oluşturdukları kanıtlanmıştır ve ekspresyonu ve genişlemesi dışarıda kolayca hesaplanabilir. :
skips2 = adımlar // len (round_constants) sabitler_mini_polynomial = fft (round_constants, modül, f.exp (subroot, skips2), inv = True) constants_polynomial = constants_mini_extension = fft (constants_mini_polynomial, modül, f.exp (root_of_unity)8192 adım ve 64 döngü sabiti olduğunu varsayalım. Yapmak istediğimiz şey bu: döngü sabitini g1128'in bir fonksiyonu olarak hesaplamak için bir FFT yapıyoruz. Daha sonra g1'in işlevini tamamlamak için arasına çok sayıda sıfır ekliyoruz. G1128 yaklaşık olarak her 64 adımda bir döngü oluşturduğundan, g1'in aynı işleve sahip olacağını biliyoruz. Bu uzantıda yalnızca 512 adım sayıyoruz çünkü bu uzantının her 512 adımdan sonra tekrar edeceğini biliyoruz. Şimdi, C (P (x)) 'i Fibonacci durumunda olduğu gibi hesaplıyoruz, ancak bu sefer bu bir hesaplama. Polinomları katsayılar şeklinde değil, daha yüksek dereceden birim kökün sürekli gücüne göre hesapladığımıza dikkat edilmelidir. Polinomu değerlendirin.
c_of_p'nin Q (x) = C (P (x), P (g1 * x), K (x)) = P (g1 * x) - P (x) ** 3 - K (x) 'i karşılaması gerekir; amaç Hesaplama yoluna koyduğumuz herhangi bir x için (son adım hariç, çünkü son adımdan sonra adım yoktur), hesaplama yolundaki bir sonraki değer önceki değer artı döngü sabitine eşittir. Bölüm 1'deki Fibonacci örneğinden farklı olarak, burada belirli bir hesaplama adımı k vektöründe ise, sonraki adım k + 1 vektörü olacaktır.Yörüngeyi hesaplamak için düşük dereceli birim kökün (g1) sürekli gücünü indirdik, Dolayısıyla, belirli bir hesaplama adımı x = g1i'de ise, sonraki adım g1i + 1 = g1i * g1 = x * g1'de olacaktır. Bu nedenle, düşük dereceli birim kökün (g1) her bir gücü için, P (x * g1) = P (x) ** 3 + K (x) veya P (x * g1) - P ( x) ** 3 - K (x) = Q (x) = 0. Bu nedenle, düşük mertebeden birim kökün g (sonuncusu hariç) ardışık tüm güçlerinde Q (x) sıfıra eşit olacaktır.
# Oluşan polinomu # C (P (x), P (g1 * x), K (x)) = P (g1 * x) -P (x) ** 3-K (x) c_of_p_evaluation = print olacak şekilde oluşturun ('Hesaplanmış C (P, K) polinomu')Tüm bu x koordinatlarında Q (x) sıfıra eşitse, en küçük polinomun ürününün tüm bu x koordinatlarında sıfıra eşit olacağına dair cebirsel bir kanıt vardır: Z (x) = (x - x_1) * (x - x_2) * * (X - x_n). Herhangi bir tek koordinatta, Q (x) 'in sıfıra eşit olduğunu kanıtlayarak, bunun zor olduğunu kanıtlamak istiyoruz, çünkü böyle bir ispatın doğrulanması, orijinal hesaplamayı yürütmekten daha uzun sürer. Q kanıtlamak için dolaylı bir yol kullanacağız ( x), Z (x) 'in çarpımıdır. Ve ne yapacağız? D (x) = Q (x) / Z (x) olduğunu kanıtlayarak ve FRI'yi kullanarak bunun bir kesir değil, aslında bir polinom olduğunu kanıtlayarak.
Düşük sıralı birim kökler ve yüksek sıralı birim köklerden oluşan özel bir düzenleme seçiyoruz çünkü Z (x) 'i hesaplamanın ve Z (x) ile bölmenin de çok basit olduğu ortaya çıkıyor: Z ifadesi iki terimin parçasıdır.
Z'nin payının ve paydasının doğrudan hesaplandığı ve daha sonra Z'ye bölmenin, toplu modüler ters yöntem kullanılarak çarpmaya dönüştürüldüğü ve ardından Q (x) değerinin, Z (X) 'in tersiyle nokta nokta çarpıldığı unutulmamalıdır. Sonuncusu hariç, düşük mertebeden birim kökün gücü için Z (x) = 0 elde edilebileceği için ters hesaplamayı içeren bu hesaplama kesintiye uğrayacaktır. Bu çok talihsiz bir durum, ancak bu boşluğu sadece rastgele kontrol ve FRI algoritmasını değiştirerek kapatacağız, bu yüzden bir hata yapsak bile önemli değil.
Z (x) kısa ve öz bir şekilde ifade edilebildiğinden, başka bir fayda da elde edebiliriz: doğrulayıcı, herhangi bir belirli x için Z (x) 'i hızlı bir şekilde hesaplayabilir ve herhangi bir ileri hesaplamaya gerek yoktur. Kanıtlayıcı için, kanıtlayanın büyüklüğü adım sayısına eşit olan bir polinomla ilgilenmesi gerektiğini kabul edebiliriz, ancak doğrulayıcının aynı şeyi yapmasını istemiyoruz çünkü doğrulama sürecinin yeterince basit olmasını istiyoruz.
# Hesaplama D (x) = Q (x) / Z (x) # Z (x) = (x ^ adımlar-1) / (x-x_atlast_step) z_num_evaluation = z_num_inv = f.multi_inv (z_num_evaluation) z_den_evaluation = d_evaluation = print ('Hesaplanmış D polinomu')Birkaç rastgele noktada, transfer kısıtlamalarını doğrulamak için D (x) * Z (x) = Q (x) kavram tespiti gerçekleştirilebilir Her hesaplama adımı, önceki adımın geçerli bir sonucudur. Ancak aynı zamanda, hesaplamanın girdisi ve çıktısının kanıtlayanın söylediği gibi olduğu sınır kısıtlamalarını da doğrulamak istiyoruz. İspatlayanın yalnızca hepsi çok kırılgan olan P (1), D (1), P (son_adım) ve D (son_adım) değerlerini sağlaması gerekir; bu değerlerin hepsinin aynı polinomda olduğuna dair hiçbir kanıt yoktur. Bu nedenle, benzer bir polinom bölme tekniği kullanıyoruz:
# ((1, input), (x_atlast_step, output)) enterpolantını hesaplayın interpolant = f.lagrange_interp_2 (,) i_evaluation = zeropoly2 = f.mul_polys (,) inv_z2_evaluation = f.multi_inv () # B = (P-I) / Z2b_evaluation = print ('Hesaplanmış B polinomu')O halde argümanımız aşağıdaki gibidir. İspatlayıcı, P (1) == girdi ve P (son_adım) == çıktı olduğunu kanıtlamak ister. Enterpolasyon olarak I (x) kullanırsak, o zaman (1, giriş) ve (son_adım, çıktı) 'nın parlak noktalarından geçen çizgidir, dolayısıyla P (x) - I (x) bu parlak noktada sıfıra eşit olacaktır. Bu nedenle, P (x) - I (x) 'in P (x) - I (x)' in ürünü olduğunu kanıtlayacak ve bunu bölümü yükselterek ispatlayabiliriz.
Mor: Yörünge polinomunu (P) hesaplayın. Yeşil: Enterpolasyon (I) (enterpolasyonun nasıl oluşturulduğuna dikkat edin, x = 1'deki girişe eşittir (yörüngeyi hesaplamak için ilk adım olmalıdır) ve x = g ^ (adımlar-1) konumundaki çıktıya eşittir (hesaplama olmalıdır Yörüngenin son adımı) Kırmızı: PI. Sarı: x = 1 ve x = g ^ (adım-1) (yani Z2) için 0'a eşit en küçük polinom. Pembe: (P - I) / Z2.
Şimdi P, D ve B'nin Merkel köklerini bir araya getirmeye bir göz atalım.
Şimdi, P, D ve B'nin aslında polinomlar olduğunu ve en büyük doğru sıralama olduğunu kanıtlamamız gerekiyor. Ancak FRI kanıtı çok büyük ve pahalıdır ve üç FRI ispatına sahip olmak istemiyoruz, bu nedenle P, D ve B'nin sözde rasgele doğrusal kombinasyonunu hesaplıyor ve buna göre FRI kanıtı gerçekleştiriyoruz:
# Merkle köklerini hesapla = merkelize () print ('Hesaplanmış karma kökü')Üç polinomun tümü doğru düşük sıraya sahip olmadıkça, rastgele seçilen bir doğrusal kombinasyona sahip olmak neredeyse imkansızdır, bu nedenle bu yeterlidir.
D'nin sırasının 2 * adımdan az olduğunu ve P ve B sayılarının adımlardan daha az olduğunu kanıtlamak istiyoruz, bu nedenle aslında P, P * xsteps, B, Bsteps ve D'nin rastgele bir kombinasyonunu kullanıyoruz ve bu kısmı görebiliriz Kombinasyon 2 * adımdan azdır.
Şimdi tüm polinom kombinasyonlarını kontrol edelim. Önce birçok rastgele dizin elde ederiz ve ardından bu dizinlerde Merkel dalları için bir polinom sağlarız:
k1 = int.from_bytes (blake (mtree + b '\ x01'), 'büyük') k2 = int.from_bytes (blake (mtree + b '\ x02'), 'büyük') k3 = int.from_bytes ( blake (mtree + b '\ x03'), 'büyük') k4 = int.from_bytes (blake (mtree + b '\ x04'), 'büyük') # Doğrusal kombinasyonu hesaplayın. hesaplama # katsayı biçiminde; sadece root_of_unity_to_the_steps = f.exp (root_of_unity, steps) güçler = aralıktaki i için (1, duyarlılık) değerlendirmelerini hesaplıyoruz: powers.append (powers * root_of_unity_to_the_steps% modülü) l_evaluation =Get_pseudorandom_indices işlevi, aralıktaki rastgele dizine yanıt verir ve exclude_multiples_of parametresi, belirli bir parametrenin katlarının değerini vermez. Bu, orijinal hesaplama yörüngesi boyunca örneklemememizi sağlar, aksi takdirde yanlış cevabı alırız.
İspat, bir dizi Merkel kökü, rastgele kontrol edilen dallar ve rastgele doğrusal kombinasyonların düşük seviyeli kanıtlarından oluşur:
# Merkle ağacının bazı noktasal kontrollerini sözde rastgele koordinatlarda yapın, pendos: dallar: dallar için "extension_factor" dallarının # katları = spot_check_security_factorpositions = get_pseudorandom_indices (l_mtree, duyarlılık, örnekler, exclude_multiples_of = extension_factor) hariçtir. (mtree, pos)) branch.append (mk_branch (mtree, (pos + atlama)% hassasiyet)) branch.append (mk_branch (l_mtree, pos)) print ('Hesaplanan% d nokta kontrolleri'% örnek)Tüm kanıtın en uzun kısmı Merkel ağaç dalı ve FRI kanıtı daha fazla daldan oluşuyor. Bu, doğrulayıcının gerçek sonucudur:
o =Doğrulayıcının Merkel kanıtını kontrol edebilmesi ve C (P (x), P (g1 * x), K (x)) = Z'yi kontrol edebilmesi için her pozisyonda, kanıtlayıcının bir Merkel kanıtı sağlaması gerekir. (x) * D (x) ve B (x) * Z2 (x) + I (x) = P (x) (Hatırlatma: İlk hesaplama yörüngesinde olmayan x için, Z (x) sıfır olmayacaktır, bu nedenle C (P (x), P (g1 * x), K (x) sıfır olmayacaktır) Doğrulayıcı ayrıca doğrusal kombinasyonun doğru olup olmadığını kontrol edecek ve onu arayacaktır.
i, numaralandırmada konum (konumlar): x = f.exp (G2, konum) x_to_the_steps = f.exp (x, adımlar) mbranch1 = doğrulama_branch (m_root, pos, dallar) mbranch2 = doğrulama_branch (m_root, (pos + atlama) )% duyarlık, dallar) l_of_x = doğrulama_branch (l_root, konum, dallar, output_as_int = True) p_of_x = int.from_bytes (mbranch1, 'büyük') p_of_g1x = int.from_bytes (mbranch2, 'büyük') d_of_x = int.frombytes ( mbranch1, 'büyük') b_of_x = int.from_bytes (mbranch1, 'büyük') zvalue = f.div (f.exp (x, adımlar) -1, x-last_step_position) k_of_x = f.eval_poly_at (sabitler_mini_polynomial, f.exp (x, atlama2)) # Geçiş kısıtlamalarını kontrol edin Q (x) = Z (x) * D (x) assert (p_of_g1x-p_of_x ** 3-k_of_x-zvalue * d_of_x)% modül == 0 # Sınır kısıtlamalarını kontrol edin B ( x) * Z2 (x) + I (x) = P (x) interpolant = f.lagrange_interp_2 (,) zeropoly2 = f.mul_polys (,) assert (p_of_x-b_of_x * f.eval_poly_at (zeropoly2, x) -f. eval_poly_at (interpolant, x))% modül == 0 # Doğrusal kombinasyon iddiasının doğruluğunu kontrol edin (l_of_x-d_of_x-k1 * p_of_x-k 2 * p_of_x * x_to_the_steps-k3 * b_of_x-k4 * b_of_x * x_to_the_steps)% modül == 0Aslında, başarılı bir şekilde tamamlanmamıştır; çapraz polinom kontroller ve FRI için gerekli olan rastgele kontrol sayısının güvenilirlik analizinin çok zor olduğunu kanıtlamaktadır. Ancak bunların hepsi kod, en azından çılgın optimizasyonlar konusunda endişelenmenize gerek yok. Yukarıdaki kodu çalıştırdığımda, sertifika maliyetinin 300-400 katına mal olacak bir STARK sertifikası alacağız. Örneğin, 0,2 saniye süren bir MIMC hesaplamasının kanıtlanması 60 saniye sürer). Bu, 4 çekirdekli bir makinenin aslında MIMC'den geriye doğru daha hızlı olabilen MIMC'de STARK'ı hesaplamasına olanak tanır. Yani python dilinde bu nispeten verimsiz olacak ve aynı zamanda çalışma süresi oranının farklı olacağını da kanıtlayacaktır. Aynı zamanda, MIMC'nin STARK'ının maliyetin çok düşük olduğunu kanıtladığını da belirtmekte fayda var, çünkü MIMC neredeyse mükemmel bir şekilde hesaplanabilir ve matematiksel formu çok basit. Ortalama hesaplama için, daha az net hesaplama olacaktır (örneğin, bir sayının diğerinden daha büyük veya daha küçük olup olmadığını kontrol etmek için) ve hesaplama maliyeti, yaklaşık 10.000-50000 kat daha yüksek olabilir.
Gönderildiği andaki Bitcoin fiyatı 43573.06
Orijinal: https://vitalik.ca/general/2018/07/21/starks_part_3.html
Yazar: Vitalik Buterin
Derleme: nuszjj
Makale kaynağı (çeviri): Babbitt Information ( Telif Hakkı Beyanı:
Yazar hakkını saklı tutar. Makale, yazarın bağımsız bakış açısıdır ve Babbitt'in görüşünü temsil etmez.
