Blockchain çalışması | Sıfır bilgi kanıtının dört temel teknolojisini ve Ethereum ile nasıl tepki verileceğini ayrıntılı olarak açıklayın
Leifeng.com: Orijinal başlık "kısaca zkSNARKs" ve yazar, Ethereum akıllı sözleşme dili Solidity'nin mucidi Christian Reitwiessner. Çevirmen Yang Wentao, yazar Zhihu köşesinden yeniden basma yetkisi verdi.
Özet:
ZkSNARK'ların (sıfır bilgili, etkileşimli olmayan bilgi argümanları) başarılı bir şekilde uygulanması bizi etkiledi, çünkü bir hesaplamanın sonucunun doğru olup olmadığını, yürütmenin belirli içeriğini yürütmeden veya hatta bilmeden belirleyebilirsin - ve siz Bilinen tek bilgi, doğru bir şekilde tamamlandığıdır. Ne yazık ki, zkSNARK'ların çoğu açıklaması yüzeyseldir ve sadece en zeki insanların nasıl çalıştığını anlayabileceğini ima eder. Aslında, zkSNARK'lar 4 basit teknoloji olarak özetlenebilir ve bu blog bu teknolojileri tek tek açıklayacaktır. RSA şifreleme sisteminin çalışma prensibini anlayan herkes, şu anda kullanılmakta olan zkSNARK'ları daha iyi anlayacak ve anlayacaktır.
Şu anda kullandığımız zkSNARK'lar 4 ana bölümden oluşmaktadır:
A) Bir polinom problemi olarak kodlayın (Polinom problemi)
Doğrulanacak programı ikinci dereceden bir polinom denklemi olarak yazın: t (x) h (x) = w (x) v (x) Bu denklem, ancak ve ancak programın hesaplama sonucu doğruysa geçerlidir. Kanıtlayıcı, doğrulayıcıyı bu denklemin geçerli olduğuna ikna etmelidir.
B) Basit rastgele örnekleme
Doğrulayıcı, polinom çarpma problemini basitleştirmek ve polinom fonksiyonunun basit bir çarpma ve doğrulama denklemine t (s) h (s) = w (s) v (s) eşit olduğunu doğrulamak için özel bir değerlendirme noktası s seçecektir. Bu yalnızca sertifikanın boyutunu küçültmekle kalmaz, aynı zamanda doğrulama için gereken süreyi de büyük ölçüde azaltır.
C) Homomorfik kodlama / şifreleme
Çevirmenin Notu: 1978'de Ron Rivest, Leonard Adleman ve Michael L. Dertouzos, banka ile homomorfik şifreleme kavramını bir uygulama arka planı olarak ortaya koydu. O sırada kullanılan kelime, soyut cebirin homomorfizmi ile aynı olan homomorfizmdi. kelime. Günümüzde genellikle homomorfik şifreleme kullanılmaktadır ve yerel kriptografi çemberi temelde homomorfik şifreleme olarak adlandırılır. Ron Rivest ve Leonard Adleman, ünlü RSA algoritmasında sırasıyla R ve A'dır (diğeri Adi Shamir'dir).
Ek (Öğretmen Bai'den): Homeomorfizm ve homomorfizm matematikte aynı değildir. Homeomorfizm, sürekli deformasyon altındaki değişmezliği ifade eder ve homomorfizm, haritalama altındaki cebirsel ilişkilerin korunmasını ifade eder.
Bazı homomorfik özelliklere sahip bir kodlama / şifreleme işlevi E kullanıyoruz (tamamen homomorfik değil, en azından bazıları gerçek kullanımda homomorfik değil). Bu işlev, atasözünün s bilmeden E (t (s)), E (h (s)), E (w (s)), E (v (s)) hesaplamasını sağlar.Sadece E'yi bilir ( s) ve diğer bazı yararlı şifrelenmiş bilgiler.
D) Sıfır Bilgi
İspatlayıcı, bir sayıyı çarparak E (t (s)), E (h (s)), E (w (s)), E (v (s)) değerini değiştirir, böylece doğrulayıcı Gerçek kod değerini bilerek, doğru yapısını doğrulayın.
Zor problem, rastgele bir gizli sayı için k (k, 0'a eşit değildir), t (s) h (s) = w (s) v (s) 'yi kontrol edin ve t (s) h (s)' yi kontrol edin. k = w (s) v (s) neredeyse tamamen aynıdır, ancak fark şu ki, yalnızca (t (s) h (s) k) ve w (s) v (s) alırsanız T (s) h (s) veya w (s) v (s) 'nin değeri neredeyse imkansızdır.
Tabii ki, okuyucuların zkSNARK'ların doğasını daha iyi anlamalarını sağlamak için bunlar sadece temel parçalar ve sonra bu bilgi noktalarını ayrıntılı olarak açıklamaya başlayacağız.
RSA ve sıfır bilgi kanıtı
Şimdi, önemsiz ayrıntılara bakmaksızın RSA'nın nasıl çalıştığını hızlıca hatırlayalım. Bir düşünün, çoğu tam sayıları değil, bazı sayıları değiştirmek için bir sayı kullanırız. Buradaki denklem "a + b c (mod n)", "(a + b)% n = c% n" ile eşdeğerdir. "(Mod n)" kısmının "c" ye değil "" ye ve aynı denklemin diğer "" kısmına uygulandığına dikkat edin. Bunu okumak çok zor olsa da, onları idareli kullanacağıma söz veriyorum. O zaman RSA'ya dönelim:
Onaylayıcı aşağıdaki rakamları sağlamıştır:
p, q: rastgele iki özel asal sayı
n: = p q
d: 1
e: d e 1 (mod (p-1) (q-1))
Genel anahtar (e, n) ve özel anahtar d. P ve q asal sayıları atılabilir, ancak açığa çıkarılamaz.
Mesaj m aşağıdaki formülle şifrelenir:
c = E (m), aşağıdaki formülle çözülür:
Yüzünden
, Ve m üssü, modulo (p-1) (q-1) sayı grubudur, dolayısıyla
(Çevirmenin Notu: Fermat'ın Küçük Teoreminden ve Çin Kalan Teoreminden türetilebilir). Ve RSA'nın güvenliği, n'nin kolayca ve etkili bir şekilde çarpanlarına ayrılamayacağı ve d'nin e ile hesaplanamayacağı varsayımına dayanır (p ve q'yu bilirsek, istediğimiz değeri kolayca elde edebiliriz).
RSA'nın harika özelliklerinden biri Homomorfik çarpma . Genel olarak, hesaplama sonucunu etkilemeden iki işlemin sırasını değiştirebilirseniz, o zaman iki işlemin homomorfik olduğunu söyleriz. Homomorfik şifrelemede bu, şifrelenmiş veriler üzerinde hesaplamalar yapabileceğiniz bir özelliktir. Tamamen homomorfik şifreleme mevcuttur, ancak henüz pratikte uygulanmamıştır.Kriptolu verilere dayalı herhangi bir program için hesaplamaları tamamlayabilir. RSA için burada sadece grup çarpmasından bahsediyoruz. Daha kesin olmak gerekirse:
Metin açıklaması şudur: iki şifrelenmiş bilginin ürünü, iki bilginin ürününün şifrelenmesine eşittir.
Bu homomorfik özellik, sıfır bilgi çarpımı ile kanıtlanmıştır: kanıtlayıcı, bazı özel sayılar x ve y'yi bilir ve ürünlerini hesaplar, ancak yalnızca şifrelenmiş sürümü doğrulayıcıya gönderir: a = E (x) , b = E (y) ve c = E (xy). Doğrulayıcı, (a b)% n c% n denkleminin doğru olup olmadığını kontrol eder. Şu anda, doğrulayıcı yalnızca şifrelenmiş versiyonun ürününü ve ürünün doğru hesaplanıp hesaplanmadığını bilir, ancak iki çarpanı ve gerçek ürünü bilmez. Çarpma yerine toplama kullanırsanız, ana işlemi denge eklemek olan bir blok zinciri yönüdür.
Etkileşimli doğrulama
Zaten sıfır bilgi kavramına dair belirli bir anlayışa sahibiz, şimdi zkSNARK'ların bir başka önemli özelliğine odaklanalım: özlü. Daha sonra, bu özlülüğün zkSNARK'ların daha güçlü kısmı olduğunu göreceksiniz, çünkü sıfır bilgi kısmının gerçekleştirilmesi bu özel kodlamadan kaynaklanmaktadır ve bu özel kodlama, sınırlı bir homomorfik kodlama biçimidir.
SNARK'lar, özlü, etkileşimli olmayan bilgi argümanlarının kısaltmasıdır. Genel olarak, ortak ayara etkileşimli protokol adı verilir çünkü bir kanıtlayıcı ve bir doğrulayıcı vardır, kanıtlayıcı bilgi alışverişi yaparak doğrulayıcıyı bir ifadeye inanmaya ikna etmek ister (örneğin, f (x) = y). Genel olarak konuşursak, hiçbir kanıtlayıcı, doğrulayıcıyı yanlış bir ifadeye (güvenilirliğe) inanmaya ikna edemez ve kanıtlayanın, doğrulayıcıyı herhangi bir gerçek ifadeye (bütünlük) inanmaya ikna etmesi için kesin bir strateji olmalıdır. SNARK'ların her bir bölümünün anlamı aşağıdaki gibidir:
-
Kısa: Gerçekten hesaplanması gereken uzunlukla karşılaştırıldığında, gönderdiğimiz mesajın boyutu çok küçük.
-
Etkileşimsiz: Etkileşim yok veya çok az. ZkSNARK'lar için, kanıtlayıcı doğrulayıcıya bir mesaj gönderdikten sonraki süreçtir. Ek olarak, SNARK'lar genellikle "genel doğrulayıcı" olarak adlandırılan bir özelliğe sahiptir, bu da herkesin tekrar etkileşime girmeden doğrulayabileceği anlamına gelir, bu da blok zinciri için çok önemlidir.
-
Argümanlar: Doğrulayıcı, yalnızca sınırlı bilgi işlem gücüne sahip kanıtlayıcı için geçerlidir. Yeterli bilgi işlem gücüne sahip bir kanıtlayıcı, yanlış ifadeler hakkında kanıtlar ve parametreler oluşturabilir (yeterli bilgi işlem gücüne sahip oldukları sürece, herhangi bir açık anahtar şifreleme sisteminin kırılabileceğini unutmayın). Bu, "mükemmel güvenilirliğin" aksine "hesaplama güvenilirliği" olarak da adlandırılır.
-
Bilgi: Bir tanık bilmeden kanıtlayıcının bir dizi parametre ve kanıt oluşturması imkansızdır (bir hash fonksiyonunun ön görüntüsü veya Merkle-ağaç düğümlerini belirleme yolu gibi) nın-nin.
Bir sıfır bilgi öneki eklerseniz, etkileşimde bir özelliğe ihtiyacınız vardır, yani doğrulayıcı ifadenin doğruluğundan başka hiçbir şey bilmez. Özellikle doğrulayıcı, tanık dizesini bilemez - bunun ne olduğunu daha sonra ayrıntılı olarak açıklayacağız.
Sıfır bilginin nispeten resmi tanımı (hala bazı detaylardan yoksundur): bazı ayar alanları oluşturabilen, ancak özel tanığı bilmeyen ve ayrıca doğrulayıcı ile etkileşime girebilen bir öykünücü vardır - ancak harici gözlem Bununla birlikte, kişi hangi etkileşimin doğrulayıcı ile hangisinin kanıtlayıcıyla etkileşim olduğunu ayırt edemez.
NP ve basitleştirilmiş karmaşıklık teorisi
ZkSNARK'ların hangi problemler ve hesaplamalar için kullanılabileceğini anlamak için, karmaşık teorilere dayalı bazı ifadeler tanımlamamız gerekir. "Tanıklığın" ne olduğunu bilmiyorsanız, sıfır bilgi ispatını "okuduktan" sonra bile, ne olduğunu bilemezsiniz ve zkSNARK'ların neden yalnızca belirli polinom problemleri için uygun olduğunu anlamazsınız, eğer durum buysa. Sonra bu bölümü atlayabilirsiniz.
P ve NP
İlk olarak, işlevi 0 ve 1 çıktılarıyla sınırlıyoruz ve bu tür işlevlere sorunlar adını veriyoruz. Uzun bir sonucun her bir bitini ayrı ayrı sorgulayabileceğiniz için, bu gerçek bir sınırlama değildir, ancak teoremi biraz daha basit hale getirebilir. Şimdi, belirli bir problemi çözmenin (hesaplama fonksiyonu) ne kadar "zor" olduğunu ölçmek istiyoruz. Bir matematiksel fonksiyon f'nin belirli bir makine uygulaması M için, bir x girdisi verildiğinde, bu f fonksiyonunun gerektirdiği adımların sayısını hesaplayabiliriz - buna, "adım sayısı" nın gerçekte olmadığı M üzerinde x'in yürütme süresi denir. Çok önemli. Programlar genellikle daha büyük girişler için daha fazla adım gerektirdiğinden, yürütme süresi giriş değerinin boyutu veya uzunluğu (bit sayısı) ile ölçülür. Bu örneğin "
Algoritmanın kaynağı "- bu, giriş değeri boyutunun en fazla n olduğu zamandır
Adım sayısının algoritması. Burada "program" ve "algoritma" genel olarak aynıdır.
Yürütme süresi en fazla
Programlar ayrıca "polinom zamanlı programlar" (polinom zamanlı programlar) olarak da adlandırılır.
Karmaşıklık teorisinde iki ana kategori vardır, bunlar P problemleri ve NP problemleridir:
P problemi, polinom zamanı ile ilgili bir tür problemdir
Bazı problemler için k indeksi gerçekten çok büyük olmasına rağmen, aslında insan yapımı olmayan problemler için, 4'ten büyük olmayan k ile P problemi hala bir "çözülebilir" problem olarak kabul edilir. Bir Bitcoin işlemini onaylamak P problemidir, çünkü değerlendirmeden sonra polinom bir süre alır (ve yalnızca 0 ve 1 çıktı verebilir). Basitçe ifade etmek gerekirse, bazı değerleri "arama" yapmadan hesaplarsanız, o zaman bu problem P problemidir. Ancak bir şey aramanız gerekiyorsa, NP problemleri adı verilen başka bir kategori gireceksiniz.
NP sorunu
Neredeyse tüm NP problemleri zkSNARK'lardır.Günümüzde pratikte kullanılan zkSNARK'ların hepsi olağan anlamda NP problemleridir. Henüz bilmediğimiz şey, NP problemi olmayan zkSNARK'ların olup olmadığıdır.
Tüm NP problemleri, NP problemlerinin tanımından gelen belirli bir yapıya sahiptir:
-
NP problemi bir tür L problemidir (polinom zamanlı V programı) Bu program V, polinom ölçekli bir faktör olarak adlandırılan bir tanık verildiğinde bu faktörü doğrulayabilir. Daha resmi olarak: L (x) = 1, ancak ve ancak bazı polinom ölçekli w (tanık olarak adlandırılır) dizisi V (x, w) = 1'i sağlıyorsa doğrudur.
P = NP?
Bir NP problemini 0 uzunluğunda tanık dizeleri olarak tanımlarsanız, bunun bir P problemi olduğunu göreceksiniz. Bu nedenle, her P problemi aslında bir NP problemidir. Karmaşıklık teorisi araştırmasındaki ana görevlerden biri, bu iki problem türü arasındaki farkı keşfetmektir - yani, P.'ye ait olmayan bir NP problemi. Burada apaçık görünüyor ama genel olarak ispatlayabilirseniz 1 milyon dolar kazanabilirsiniz. Ayrıca, P ve NP'nin eşdeğer olduğunu tersine ispatlayabilirseniz, bonusu da alabilirsiniz. Ve dijital para alanının bir gün kanıtlama olasılığı çok yüksek. Bunu söylememin nedeni, bir iş problemi çözümünün kanıtını bulmanın, bir hash fonksiyonunun çarpışmasından veya bir adrese dayalı özel bir anahtar bulmanın açıkça daha kolay olmasıdır. Bunların hepsi NP problemleridir, çünkü P = NP olduğunu henüz kanıtladınız, o zaman bu NP problemleri için bir polinom zaman programı olması gerekir. Ancak çoğu araştırmacı P problemi ile NP probleminin eşdeğer olmadığını düşünse de bu makale onu tartışmayacaktır.
NP tam problem
SAT'a dönelim. Görünüşte basit olan bu problemin ilginç bir özelliği, bunun sadece bir NP problemi değil, aynı zamanda bir NP tam problemi olmasıdır. Buradaki "tamamlandı" sözcüğü, "Turing tamamlandı" ile aynı anlama sahiptir. Bu, NP'deki en zor problem olduğu anlamına gelir, ancak daha da önemlisi, NP tamamen tanımlanmıştır - herhangi bir NP probleminin girdisi aşağıdaki şekilde aynı SAT girişine dönüştürülebilir:
Tüm NP problemleri L, polinom zamanında hesaplanabilen bir "indirgeme işlevi" f'ye sahiptir:
-
L (x) = SAT (f (x))
Böyle bir azaltma işlevi bir derleyici olarak kabul edilemez: Bir derleyici, bazı programlama dillerinde yazılmış kaynak kodunu eşdeğer olarak başka bir programlama diline, yani anlamsal davranışa sahip bir makine diline dönüştürebilen bir makinedir. SAT NP tamamlandığından, bir Bitcoin işleminin yasal olup olmadığını doğrulamak için uygun bir blok karması verilmesi gibi olası herhangi bir NP sorunu için böyle bir azalma vardır. Burada ayrıca bir işlemi Boole işlevinin azaltma işlevine dönüştürebilirsiniz, böylece Boole işlevi ancak ve ancak işlem yasal ise tatmin edicidir.
Örneği geri yükle
Böyle bir indirgeme yöntemini anlamak için önce polinomları değerlendirme sorununu ele alalım. İlk olarak, tamsayı sabitleri, değişkenler, toplama, çıkarma, çarpma ve (doğru şekilde eşleşen) parantezlerden oluşan bir polinom (Boole işlevine benzer) tanımlayalım. Şimdi şu soruları ele alalım:
-
F, değişkenlerinin tümü {0, 1} kümesinden gelen ve sıfır terim içeren bir polinom ise, PolyZero (f): = 1
Şimdi SAT'dan PolyZero'ya bir azaltma yöntemi oluşturabiliriz, bu da PolyZero'nun aynı zamanda NP-tam bir sorun olduğunu da gösterir (NP'ye ait olup olmadığını doğrulamak sizin için küçük bir alıştırma).
Bazı insanlar r ((f g)) 'nin r (f) + r (g) olarak tanımlandığını varsayabilir, ancak bu durumda polinomun sonucu {0, 1} kümesini aşacaktır.
R fonksiyonunu kullanarak, ((x y) ¬x), (1 - (1 - (1 - x)) (1 - (1 - y)) (1 - (1 - x)) biçimine dönüştürülür.
R için, her değiştirme kuralının önceden belirtilen amacı karşıladığını, dolayısıyla r'nin de geri yüklemeyi doğru bir şekilde uyguladığını unutmayın:
-
Yalnızca ve ancak r (f), {0, 1} kümesinde bir 0 içeriyorsa, SAT (f) = PolyZero (r (f)) veya f tatmin edilebilir
Tanık koruma
Bu örnekten, geri yükleme işlevinin yalnızca girdinin nasıl dönüştürüleceğini tanımladığını görebilirsiniz, ancak dikkatlice baktığınızda (veya kullanılabilir bir restorasyon kanıtının nasıl tamamlanacağını okuduktan sonra), kullanılabilir bir tanığı girdiyle birlikte nasıl dönüştüreceğinizi bileceksiniz. . Örneğimizde, sadece fonksiyonun bir polinomiye nasıl dönüştürüleceğini tanımladık, ancak açıkladığımız kanıtı görevi yerine getiren bir tanığa nasıl dönüştüreceğimizi bilmiyoruz. Aynı zamanda tanık dönüşümü işlem için gerekli değildir, ancak genellikle dahil edilir. Ve bu zkSNARKs için çok önemlidir, çünkü kanıtlayıcı için tek görevi doğrulayıcıyı böyle bir tanık olduğuna ikna etmektir ve tanık hakkında herhangi bir bilgi ifşa etmeyecektir.
Karesel Aralık Programları
Önceki bölümde, NP problemlerinin hesaplanmasının birbirleriyle, özellikle NP tam problemleriyle nasıl basitleştirilebileceğini gördük.Bu NP tam problemleri, işlem doğrulama problemleri de dahil olmak üzere, temelde diğer NP problemlerini yeniden oluşturur. O zaman, tüm NP problemlerinde ortak olan bir zkSNARK bulmak bizim için çok kolay hale geliyor: sadece uygun NP tam problemini seçmemiz gerekiyor. Bu nedenle, işlemleri doğrulamak için zkSNARK'ları nasıl kullanacağımızı göstermek istiyorsak, bu belirli NP-tam sorununun nasıl ele alınacağını göstermek etkili bir yöntemdir ve teorik bir açıklamadan daha kabul edilebilir.
Bir sonraki adım, GGPR12 kağıdına dayalı konuşmaktır (buraya bağlanan teknik rapor, orijinal makaleden daha kurudur) Bu makalenin yazarı, tamamen zkSNARK'lar için hazırlanmış, Quadratic Span Programs (QSP) adlı bir problem keşfetti. . Bir Kuadratik Açıklık Programı, bir dizi polinomdan ve belirli bir polinomun katlarını bulmanın doğrusal bir kombinasyon görevinden oluşur. Ek olarak, giriş dizesinin her bir biti, kullanabileceğiniz polinomları sınırlar. Ayrıntılı olarak (genel olarak konuşursak, GSP'ler çok kısıtlayıcı değildir, ancak bu oldukça kısıtlanmış sürüme ihtiyacımız var, çünkü onu daha sonra kullanacağız):
Giriş uzunluğu n olan F alanındaki QSP problemi aşağıdaki bölümlerden oluşur:
Buradaki görev çok kaba, yani polinomları bir faktörle çarpmak ve onları bir araya toplamak ("doğrusal kombinasyon" olarak da adlandırılır), böylece toplamları t'nin katıdır. Her bir ikili girdi dizisi u için, f fonksiyonu kullanılabilen polinomları sınırlar veya daha kesin olarak bunlar doğrusal kombinasyon faktörleri olmalıdır. Resmi ifade şöyledir:
2n, m'den küçük olduğunda, a ve b gruplarını seçmede hala çok fazla özgürlük olduğunu unutmayın. Bu, QSP'nin yalnızca belirli bir girdi boyutu için değerli olduğu anlamına gelir - bu sorun, tek tip olmayan karmaşıklık kullanılarak çözülebilir. Bugün tek tip olmayan karmaşıklık konusuna girmeyeceğiz. Yalnızca girdi değerinin ne zaman olduğunu bilmemiz gerekiyor Kriptografimiz çok gençken iyi çalışıyor.
Burada genel hesaplamaları ve devre problemlerini QSP problemlerine nasıl basitleştireceğimizi tartışmayacağız, çünkü temel kavramları anlamamız bize yardımcı olmuyor.Yalnızca QSP'nin NP-tam olduğunu (veya NP / poli gibi tekdüze dağıtılmamış bazı problemlerden daha iyi) bilmemiz gerekiyor Daha eksiksiz) gayet iyi. Aslında, bu sadeleştirme bir "mühendislik" bölümüdür - QSP problemlerini olabildiğince küçük hale getirmek ve diğer bazı iyi özelliklere sahip olmak için çok akıllı bir yöntem kullanılmalıdır.
zkSNARK detaylı
Şimdi QSP'deki zkSNARK'ı ayrıntılı olarak anlatalım. Kurulum aşamasının başında her bir QSP'yi yürütecektir. ZCash'te, işlem doğrulayıcının satırı sabittir, bu nedenle QSP'nin polinomu da sabitlenir.Bu QSP'nin kurulum aşamasında yalnızca bir kez çalıştırılmasına ve ardından farklı u girişine sahip tüm işlemlerde yeniden kullanılmasına izin verilir. Bu ilk ayar, ortak bir referans dizisi (CRS) oluşturacaktır Doğrulayıcı, rastgele ve özel bir alan öğesi seçer ve bu noktada polinomun değerini şifreler. Doğrulayıcı, bazı özel şifreleme yöntemi E kullanır ve CRS'de
Bir polinomu basitçe tahmin etmek için sıfır bilgi nasıl kullanılır
İlk olarak, basit bir duruma, yani bir polinomun özel bir noktada şifrelenmiş değerlemesine bakalım, QSP probleminin tamamı yerine.
Buradaki örnek bize, doğrulayıcının bunu kanıtlamak için tam bir polinom bulmasına gerek olmadığını, sadece eşleştirme işlevini kullandığını söylüyor. Bir sonraki adım, sıfır bilgi bölümünü eklemektir, böylece doğrulayıcı, E (f (s)) gibi şifrelenmiş bilgiler dahil olmak üzere, f (s) 'nin değeri hakkında herhangi bir bilgi oluşturamaz.
Tamam, artık doğrulayıcı bu değeri bilmediğinde, kanıtlayıcının şifrelenmiş bir özel noktada polinom şifreli değeri nasıl hesapladığını nihayet biraz biliyoruz. Şimdi bunları QSP sorularına uygulayalım.
QSP sorunları için SNARK
Son denklem, doğru polinomun kullanılıp kullanılmadığını kontrol etmek için kullanılır (bu kısım henüz ele alınmamıştır, ancak diğer örnekler onu kapsayacaktır). Unutulmamalıdır ki, tüm şifrelenmiş değerlerimiz, kanıtlayıcı tarafından yalnızca CRS'yi bilerek hesaplanabilir.
Doğrulayıcı artık şunları yapmak zorundadır:
İspatlayanın doğru bir kanıt sağladığını varsayarsak, denklemin karşılanıp karşılanmadığını kontrol edelim. Sol ve sağ kısımlar:
Sıfır bilgi ekleyin
Girdi ve Şahidin boyutu arasında bir uzlaşma sağlayın
Yukarıdaki alt bölümlerde gördüğünüz gibi, ispatımız bir grubun 7 öğesinden (yani eliptik bir eğri) oluşur. Ve doğrulayıcının işi, bazı eşleştirme fonksiyonlarının denklemlerinin tutup tutmadığını kontrol etmektir ve hesaplamaktır.
Girdi boyutunu takip eden böyle doğrusal bir görev. En önemli şey, bu doğrulama sürecinde QSP'yi (SNARK yok) doğrulamak için ne tanık dizisinin boyutunun ne de hesaplama iş yükünün gerekli olmasıdır. Bu, SNARK'ların doğrulanmasının çok karmaşık bir sorun olduğu ve basit sorunların genellikle aynı olduğu anlamına gelir. Bu sonucun temel nedeni, polinomun tutarlılığını tüm noktalarda değil, yalnızca tek bir noktada test etmemizdir. Polinomlar çok çok karmaşık olabilir, ancak bir nokta her zaman bir noktadır. Doğrulama sonucunu etkileyebilecek tek parametre, güvenlik seviyesi (grubun boyutu gibi) ve giriş değerinin maksimum boyutudur.
İkinci parametreyi azaltmak, girdi değerinin bir kısmını tanığa taşımak mümkündür: f (u, w) fonksiyonunu doğrulamıyoruz, u girdi, w tanık, ancak bir hash yapın ve sonra doğrulayın:
Bu, h (u) girişini temsil etmek için bir hash kullanabileceğimiz anlamına gelir (bu onu kısaltacaktır). F (x, w) 'yi doğrulamaya ek olarak, belirli bir x değerinin hash değerinin H (u)' ya eşit olduğunu da doğrulamamız gerekir. ) (Bu durumda, x büyük olasılıkla u'ya eşittir). Bu, orijinal giriş u'yu tanık dizgisine taşır.Bu, tanığın boyutunu artıracak olsa da, giriş değerinin boyutu bir sabite düşürülür.
Bu çok güçlüdür, çünkü herhangi bir karmaşık ifadenin testini sabit zamanda tamamlayabileceğimiz anlamına gelir.
zkSNARK'lar ve Ethereum yakından ilişkilidir
Doğrulama hesaplamaları Ethereum blok zincirinin özü olduğundan, zkSNARK'lar ve Ethereum yakından ilişkilidir. ZkSNARK'larla, yalnızca herkesin doğrulayabileceği özel hesaplamaları değil, aynı zamanda verimli bir şekilde tamamlayabiliyoruz.
Ethereum bir Turing-complete sanal makine kullansa da, şu anda Ethereum'da bir zkSNARK uygulamak imkansız. Kavramsal olarak, doğrulayıcının görevi basit görünüyor, ancak eşleştirme işlevinin hesaplanması gerçekten zor ve tek bir blokta daha fazla gaz tüketiyor. Eliptik eğrilerin çarpımı nispeten karmaşıktır ve eşleştirme işlevi başka bir karmaşıklık düzeyi ekler.
ZCash gibi mevcut zkSNARK sistemleri her görev için aynı problemi, devre hesaplamasını kullanır. ZCash'te işlem doğrulamasıdır. Ethereum'da zkSNARK'lar sadece bir hesaplama problemi yapmakla kalmayacak, aynı zamanda herkesin yeni bir blok zinciri yayınlamadan kendi zkSNARK sistemini kurmasına izin verecek. Ethereum'a eklenen her zkSNARK sistemi, yeni bir CRS oluşturmak gibi yeni, özel ve güvenilir bir hazırlık aşaması gerektirir (bazıları yeniden kullanılabilir, bazıları kullanılamaz). Bir "evrensel sanal makineye" zkSNARK sisteminin eklenmesi gibi mümkün olacaktır. Bu şekilde, yeni bir örnek kullandığınızda onu sıfırlamanıza gerek kalmaz, çünkü Ethereum'da yeni bir akıllı sözleşme için artık yeni bir blok zinciri yayınlamanıza gerek kalmaz.
Ethereum'da zkSNARK'lar nasıl etkinleştirilir
Ethereum'da zkSNARK'ları etkinleştirmenin birçok yolu vardır. Tüm yöntemler, eşleştirme işlevleri ve eliptik eğri işlemleri için gerçek kaybı azaltabilir (diğer gerekli işlemler çok basittir), bu nedenle bu işlemler tarafından tüketilen gazı da azaltmamız gerekir.
-
EVM'nin performansını iyileştirin (temin edin)
-
EVM'nin yalnızca belirlenen eşleştirme işlevi ve eliptik eğri çarpımı üzerindeki performansını iyileştirin
İlk öğe uzun vadede açıkça iyi getiri elde edecek, ancak gerçekleştirilmesi daha zor. Şimdi EVM'ye, tam zamanında derleme için daha iyi destek ve mevcut uygulama altında en az değişiklikle yorumlayıcının uygulanması gibi bazı yeni özellikler ve kısıtlamalar ekliyoruz. Tabii ki, EVM'yi doğrudan eWASM ile değiştirmeyi de göz ardı etmez.
İkinci öğe, tüm Ethereum istemcilerini belirli bir eşleştirme işlevini ve önceden derlenmiş bir sözleşme olarak adlandırılan belirli eliptik eğri çarpımını gerçekleştirmeye zorlayarak uygulanabilir. Bunun avantajı, uygulamanın basit ve hızlı olmasıdır. Dezavantajı, bu şekilde belirli bir eşleştirme işlevine ve belirli bir eliptik eğriye sabitlenmemizdir. Ethereum'daki tüm yeni müşteriler bu önceden derlenmiş sözleşmeyi tekrar uygulamak zorundadır. Dolayısıyla, herhangi bir yeni gelişme varsa veya birisi daha iyi bir zkSNARKs yöntemi, daha iyi bir eşleştirme işlevi, daha iyi eliptik eğri bulabilir veya eliptik eğri, eşleştirme işlevi ve zkSNARK'ın bazı eksikliklerini keşfedebilirse, o zaman biz Yeni önceden derlenmiş sözleşmeye eklenecektir.
