Polinomların özelliklerinden dolayı doğrulama süresi etkili bir şekilde kısalır ve basitlik sağlanır.
**Sıfır bilgiye nasıl ulaşılır? **
Basitçe ifade etmek gerekirse, polinomu türetme sürecinde, iki rastgele sayı daha seçilir, böylece türetilmiş polinom, doğrulayıcının orijinal polinomun katsayılarını, yani kanıtlayıcının gizli girdisini elde etmesini engelleyebilir. ZK'yı gerçekleştirmek için.
**Etkileşimsizlik nasıl sağlanır? **
Kanıtlama başlamadan önce, üçüncü bir taraf, yani orijinal doğrulayıcıya güvenilir ayara rasgele sayılar seçme görevini atayan ve böylece doğrulayıcı ile kanıtlayıcı arasındaki etkileşimsizliği gerçekleştiren güvenilir bir ayar sunulur.
ZK teknolojisi, son iki yılda Web3 alanında büyük ilgi gördü. Rollup'tan başlayarak, farklı yollarda giderek daha fazla proje ZK teknolojisini kullanmaya çalışıyor. Bunlar arasında SNARK ve STARK en çok duyulan iki terimdir.ZK teknolojisinin sonraki aşamalarda uygulanmasını daha iyi anlamak için **bu makale SNARK'ın ispat mantığını teknik olmayan bir bakış açısıyla basitleştirecek ve ardından kullanacaktır. * * Scroll's zk Rollup **, zk ispat sisteminin işleyişini göstermek için örnek olarak kullanılmıştır. **
Makalenin amacı, okunması kolay olan temel mantığı açıklamaktır.Terminoloji kullanımından kaçınılmaya çalışılacaktır ve matematiksel dönüşümler gibi ayrıntılara girilmeyecektir.Eksikler için lütfen kusuruma bakmayın.
Ocak 2012'de, Berkeley'deki California Üniversitesi'nde profesör olan Alessandro Chiesa, SNARK hakkında bir makale yazdı ve zk-SNARK terimini önerdi.
zk-SNARK, tam adı Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, ZK teknolojisini kullanan bir ispat sistemidir. **SNARK'ın bir şema sınıfının adı olduğu ve SNARK'ı uygulayabilen birçok farklı kombinasyon yöntemi olduğu unutulmamalıdır. **
Zero-Knowledge (Zero-Knowledge): Sadece ispatlayanın bildiği içerik gizlenir ve ispatlayan dışında kimse göremez.
Kısa (Özlü): Oluşturulan kanıt küçüktür ve doğrulama süresi hızlıdır.
Etkileşimsiz (Etkileşimsiz): Kanıtlayıcı ile doğrulayıcı arasında çok az etkileşim vardır veya hiç etkileşim yoktur.
Argüman: Doğrulayıcının doğrulaması yalnızca sınırlı bilgi işlem gücüne sahip ispatlayıcı için geçerlidir, çünkü süper hesaplama gücüne sahip ispatlayıcı ispatı taklit edebilir, yani sistem hesaplama güvenilirliğine sahiptir.
Bilgi: Kanıtlayıcı ancak doğrulayıcının bilmediği bazı bilgileri biliyorsa ispatı hesaplayabilir.
zk-SNARK'ın çözmesi gereken "hesap doğrulama sorunu", yani doğrulayıcının, kanıtlayıcının gizliliğini bilmeden hesaplama sonuçlarını verimli bir şekilde doğrulayıp doğrulayamayacağıdır.
Aşağıda, sistemin verimli doğrulama elde etmek için sıfır bilgiyi nasıl birleştirdiğini göstermek için zk-SNARK'ın basitleştirilmiş oluşturma süreci kullanılacaktır. **
Zk-SNARK İnşaat
Kanıtlanacak problemi bir polinom haline getirin
Basitçe ifade etmek gerekirse, SNARK fikri, ifadenin doğru olup olmadığının kanıtını polinom eşitliğinin doğru olup olmadığının kanıtına dönüştürmektir.
Tüm dönüştürme süreci: doğrulanması gereken problemler ➡ aritmetik devre ➡ R1CS ➡ polinom ➡ polinomlar arasında dönüştürme
Doğrulanacak soru➡Aritmetik devre
Bir sorunun doğru olup olmadığını hesaplama yoluyla kanıtlamak için, kanıtlanacak sorunun önce bir hesaplama problemine dönüştürülmesi gerekir ve herhangi bir hesaplama bir aritmetik devre olarak tanımlanabilir.
Aritmetik devreler genellikle sabitlerden, "toplama kapıları" ve "çarpma kapılarından" oluşur Kapıların üst üste binmesi yoluyla karmaşık polinomlar oluşturabiliriz.
Yukarıdaki şekilde aritmetik devre tarafından oluşturulan polinom şu şekildedir: (Inp1+Inp2)*(-1) = Çıkış
Gerçekte problem aritmetik bir devreye dönüştürmek için son derece karmaşıktır.Bunu basitçe şu şekilde anlayabiliriz: bir miktar içerik girin, içerik devre tarafından dönüştürülür ve sonunda bir sonuç çıkarır. Şu anda:
Aritmetik devreler kavramına dayanarak, ispatlar üretmek için bir aritmetik devre kuruyoruz, yani:
Devre iki giriş seti içerir, genel giriş x ve gizli giriş w. Genel girdi x, içeriğin, hem doğrulayıcı hem de kanıtlayıcı tarafından bilinen, kanıtlanacak sorunun sabit bir değeri olduğu anlamına gelir ve gizli girdi w, içeriğin yalnızca kanıtlayıcı tarafından bilindiği anlamına gelir.
Kurduğumuz aritmetik devre C( x, w ) = 0, yani devre üzerinden x ve w girişi ve nihai çıkış sonucu 0'dır. Kanıtlayıcı ve doğrulayıcı, devrenin çıkışının 0 ve genel girişin x olduğunu bildiğinde, kanıtlayıcının w gizli girişini bildiğini kanıtlaması gerekir.
Aritmetik devre ➡R1CS
Sonunda bir polinoma ihtiyacımız var, ancak aritmetik devre doğrudan bir polinom'a dönüştürülemez ve ikisi arasında bir aracı olarak R1CS'ye ihtiyaç duyulur, bu nedenle aritmetik devre önce R1CS'ye dönüştürülür.
R1CS, tam adı Rank-1 Constraints (birinci dereceden kısıtlama sistemi), esasen bir matris-vektör denklemi olan devreleri açıklamak için kullanılan bir dildir. Spesifik olarak, R1CS, üç vektörün (a,b,c) bir dizisidir ve R1CS'nin çözümü, s'nin denklemi sağlaması gereken bir s vektörüdür:
Bunlar arasında iç çarpım işlemini temsil eder.
Buradaki belirli matematiksel dönüşüm Vatalik: Quadratic Aritmetic Programs: From Zero to Hero'da bulunabilir
Bilmemiz gereken tek şey, **R1CS'nin rolünün, aritmetik devredeki her geçidin tanımını sınırlamak olduğunu, böylece her kapı arasındaki vektörlerin yukarıdaki ilişkiyi karşılamasını sağlamaktır. **
R1CS➡Polinom
R1CS'nin ortamını elde ettikten sonra, onu bir polinom eşdeğerine dönüştürebiliriz.
Matrisler ve polinomlar arasındaki eşdeğer dönüşümler aşağıdaki şekilde gösterildiği gibi gerçekleştirilebilir:
polinom
matrise dönüştür
Yukarıdaki eşdeğer dönüşümün doğasına göre, R1CS'yi karşılayan bir matris için, polinomun her bir katsayısını eski haline getirmek için Lagrange interpolasyon yöntemini kullanabiliriz.Bu ilişkiye dayanarak, R1CS matrisini bir polinom ilişkisi olarak türetebiliriz, yani:
Not: A, B, C sırasıyla bir polinomu temsil eder
Bir polinom, kanıtlamak istediğimiz probleme karşılık gelen bir R1CS matris kısıtlamasına karşılık gelir.Yukarıdaki dönüşüm sayesinde, polinomların yukarıdaki ilişkiyi sağlaması durumunda, R1CS matrisimizin doğru olduğu anlamına geldiğini bilebiliriz, bu nedenle ispatlayıcının olduğunu gösterir. aritmetik devrededir.için gizli girişi de doğrudur.
Bu noktaya kadar problemimiz şu şekilde basitleştirilmiştir: doğrulayıcı rastgele bir x sayısı seçer ve onaylayıcıdan A(x) * B(x)=C(x)'in doğru olduğunu kanıtlamasını ister. onaylayıcının gizli girişinin doğru olduğu anlamına gelir.
Polinomlar arasında dönüştürme
Karmaşık aritmetik devrelerde on binlerce kapı vardır ve her kapının R1CS kısıtlamasını karşılayıp karşılamadığını doğrulamamız gerekir. Başka bir deyişle, A(x) * B(x)=C(x) eşitliğini birkaç kez doğrulamamız gerekiyor, ancak ayrı ayrı doğrulamanın etkinliği çok düşük. tek seferde kapı kısıtlamaları seks?
Anlama kolaylığı için, bir P(x) tanıtıyoruz, P(x) = A(x) * B(x) – C(x) olsun
Herhangi bir polinomun bir çözümü olduğu sürece lineer polinomlara ayrıştırılabileceğini biliyoruz. Böylece P(x)'i F(x) ve H(x)'e böleriz, yani:
O zaman F(x) herkese açıktır, yani bir H(x) = P(x)/F(x) vardır, dolayısıyla doğrulamak istediğimiz polinom sonunda şuna dönüşür:
A(x) * B(x) – C(x): Polinomun sadece ispatlayıcı yani gizli girdi tarafından bilinen katsayılarını içerir.
F(x) : Hem doğrulayıcı hem de kanıtlayıcı tarafından bilinen genel bir polinom, yani genel girdi.
H(x): Kanıtlayan bunu hesaplama yoluyla bilir, ancak doğrulayıcı bilinemez.
**Kanıtlanacak son problem şudur: A(x) * B(x) – C(x) = F(x) * H(x) polinom denklemi tüm x'ler için geçerlidir. **
Şimdi, tüm kısıtlamaların matris ilişkilerini karşıladığını doğrulamak için polinomu bir kez doğrulamak yeterlidir.
**Burada sistemin basitliğini fark ederek ispatlanacak problemin sadece bir kez doğrulanması gereken bir polinom haline dönüşümünü tamamlamış olduk. **
Ancak bu uygulamanın basitliği, doğrulayıcının doğrulama süresini kısaltmasıdır, peki ya ispat boyutu?
**Basitçe söylemek gerekirse, ispat protokolünde, ispatın boyutunu etkili bir şekilde azaltan Merkle ağaç yapısı kullanılır. **
Tüm dönüştürme işlemi tamamlandıktan sonra doğal olarak iki sorun ortaya çıkacaktır:
Neden polinom dönüştürmek?
Çünkü polinomlar ispatın basitliğini sağlar. Sıfır bilgi ispatının sorunu, hesaplamaların çoklu kısıtlamaları karşıladığını doğrulamaktır ve polinomlar bir noktada çoklu kısıtlamaları doğrulayabilir. Başka bir deyişle, doğrulayıcının sorunu doğrulamak için n kez doğrulaması gerekir, ancak şimdi ispatın doğruluğunu yüksek bir olasılıkla doğrulamak için yalnızca bir kez doğrulaması gerekir.
Neden iki polinom A(x) * B(x) – C(x )= F(x) * H(x) polinom üzerindeki bir noktayı doğrulayarak kurulabilir?
Bu, polinomların özellikleri tarafından belirlenir, yani bir polinomun herhangi bir noktadaki hesaplama sonucu, onun benzersiz kimliğinin temsili olarak kabul edilebilir. İki polinom için, yalnızca sonlu sayıda noktada kesişeceklerdir.
Yukarıdaki d dereceli iki polinom için: A(x) * B(x) – C(x) ve F(x) * H(x), eğer eşit değillerse, sadece en fazla d noktada olacaklardır. Kesişim, yani d noktalarındaki çözümler aynıdır.
Polinom dönüşümünü tamamladıktan sonra polinom ispat aşamasına geçeceğiz.
Şimdi, kanıtlayıcının kanıtlamak istediği problem şudur: tüm x'lerde, P(x) = F(x) * H(x).
Yukarıdaki polinomun kanıtlayıcı ve doğrulayıcı tarafından doğrulanma süreci şu şekildedir:
Doğrulayıcı, x = s varsayarak rastgele bir x sorgulama noktası seçer;
Kanıtlayıcı s'yi aldıktan sonra, P(s) ve H(s)'yi hesaplayın ve bu iki değeri doğrulayıcıya verin;
Doğrulayıcı önce F(s)'yi hesaplar, sonra F(s) * H(s)'yi hesaplar ve F(s) * H(s) = P(s)'nin doğru olup olmadığına karar verir ve doğruysa, doğrulama geçildi.
Ancak dikkatlice düşünürsek, yukarıdaki süreçte bazı problemler olduğunu görürüz:
Kanıtlayıcı tüm denklemin bilgisini bilebilir. Rastgele bir s noktası alırsa, F(s)'yi hesaplayabilir ve sonra bir çift sahte P(x) ve H(x) oluşturabilir, böylece P(s) ) = F(s) * H(s) doğrulayıcıyı kandırmak için.
Kanıtlayıcı, doğrulayıcı tarafından verilen s'leri F(s) ve H(s)'yi hesaplamak için kullanmaz, doğrulayıcıyı aldatmak için başka değerlerle hesaplar.
Doğrulayıcı tarafından alınan değer, kanıtlayıcının genel girdisi ve özel girdisi tarafından hesaplanır. Doğrulayıcının büyük bir hesaplama gücü varsa, kanıtlayıcının özel girdisini kırabilir.
Yukarıdaki sorunları çözmek için aşağıdaki optimizasyonları yapıyoruz:
Doğrulayıcı rastgele bir s noktası seçtikten sonra, s üzerinde homomorfik şifreleme gerçekleştirir. Homomorfik şifreleme, şifrelemeden sonra hesaplanan çözüm = hesaplamadan sonra şifrelenmiş çözüm anlamına gelir; bu şifreleme biçiminde, kanıtlayıcı çözümü hesaplayabilir ancak oluşturamaz yanlış P(x) ve H(x).
Doğrulayıcı, s meydan okuma noktasını seçtiğinde, s ve λ arasında ek bir doğrusal ilişki oluşturmak için başka bir rasgele parametre λ seçilir. Doğrulayıcı, kanıtlayıcıya homomorfik şifrelemeden sonra hem s hem de λ gönderir. Kanıtlayıcı, kanıtı geri gönderir ve doğrulayıcının, kanıtın doğru olup olmadığını doğrulamaya ek olarak rasgele parametre λ ve s arasındaki ilişkiyi doğrulaması gerekir.
**Doğrulayıcının gizli girişi kırabilmesi problemini hedefleyerek ZK'yı tanıtabiliriz. ** İspatın tamamına baktığımızda, doğrulama işlemi sırasında ispatlayıcının sadece hesaplanan polinom değerini doğrulayıcıya gönderdiğini ve doğrulayıcının polinomun katsayısını, polinomun gizli girişi olan değer üzerinden çıkarabildiğini görebiliriz. kanıtlayıcı Doğrulayıcının geri itmesini önlemek için, iki rasgele sayı daha seçebilir ve R1CS'den A, B ve C polinomlarını türetirken bir dizi değer ekleyebiliriz, böylece geri yüklenen polinom orijinal polinomdan bir sıra daha fazladır. , böylece doğrulama Okuyucu, ZK'yi gerçekleştirmek için şifrelenmiş polinomdan orijinal polinomun bilgisini elde edemez.
Optimizasyondan sonra ispat sisteminin hala doğrulayıcı ile ispatlayıcı arasında etkileşim gerektirdiğini gördük Etkileşimsizliğe nasıl ulaşabiliriz?
Etkileşimsiz uygulama
**Etkileşimsizliğe ulaşmak için SNARK, güvenilir ayarlar sunar (Kurulum). **
Başka bir deyişle, ispat başlamadan önce, doğrulayıcının rasgele meydan okuma noktalarını seçme hakkı güvenilir bir üçüncü tarafa teslim edilir.Üçüncü taraf rasgele parametre λ'yı seçtikten sonra, şifreli λ'yı R1CS devresine koyar. şekilde, CRS (Common Reference String, public reference string) oluşturulur. Doğrulayıcı kendi Sv'sini CRS'den alabilir ve kanıtlayıcı kendi Sp'sini CRS'den alabilir.
Sv ve Sp oluşturulduktan sonra λ'nın yok edilmesi gerektiğine dikkat edilmelidir. λ sızdırılırsa, yanlış doğrulama yoluyla sahte işlemler yapmak için kullanılabilir.
zk-SNARK İş Akışı
SNARK'ın yapım sürecini anladıktan sonra, ispat üretebilen kurduğumuz aritmetik devreden yola çıkarak, zk-SNARK'ın ispat süreci şu şekildedir:
Kurulum:(C devresi, λ)= (Sv, Sp)
C devresi ve rasgele parametre λ aracılığıyla, sonraki kanıtlayıcı ve doğrulayıcı tarafından kullanılan rasgele parametreler Sv ve Sp üretilir.
İspat(Sp,x,w) = Π
Prover, rasgele Sp parametresi, genel x girişi ve w gizli girişi aracılığıyla ispatı Π hesaplar.
Doğrula(Sv,x,Π) == (∃ w st C(x,w))
Doğrulayıcı, C(x,w)=0'ın var olup olmadığını rastgele parametre Sv, genel giriş x ve kanıt Π aracılığıyla doğrular. Aynı zamanda ispatın C devresi tarafından hesaplanıp hesaplanmadığını doğrulayın.
Bu noktada zk-SNARK'ın tamamının açıklamasını tamamlamış olduk, asıl uygulama örneğine bir göz atalım.
Vaka: Scroll'un zk Toplamasını örnek olarak alalım
İspat sisteminin rolü, ispatlayanın doğrulayıcıyı bir şeye inanmaya ikna etmesine izin vermektir;
zk ispat sistemi için doğrulayıcıyı, zk algoritması tarafından hesaplanan Sıfır Bilgi İspatının (sıfır bilgi ispatı) doğru olduğuna inandırmaktır.
Zk ispat sisteminin işleyişini göstermek için Scroll'un zk Toplamasını örnek olarak alıyoruz.
Toplama, zincir dışı hesaplama ve zincir içi doğrulama anlamına gelir. zk Toplama için, işlem zincir dışında yürütüldükten sonra kanıtlayıcının, işlem yürütüldükten sonra oluşturulan yeni durum kökü için bir zk sertifikası oluşturması ve ardından zincir üzerinde doğrulama için sertifikayı L1 Toplama sözleşmesine iletmesi gerekir.
zk Toplamasında iki tür blok bulunduğuna dikkat edilmelidir:
L1 Toplama bloğu: Ethereum'a gönderilen blok
L2 bloğu: L2'de kullanıcılar tarafından gönderilen işlemlerden oluşan bir blok
Aşağıda, Scroll'un zk Toplamasının iş akışı yer almaktadır:
Kullanıcı L2'de bir işlem başlatır, Sıralayıcı işlemi alır, işlemi zincir dışı yürütür ve bir L2 bloğu ve yeni bir durum kökü oluşturur; aynı zamanda işlem verilerini ve yeni durum kökünü Toplama sözleşmesine gönderir Ethereum'da (işlem verilerinin gönderilmesi veri kullanılabilirliği içindir);
L2 bloğu oluşturulduğunda, Koordinatör bloğun yürütme izini Sequencer'dan alacak ve ardından izi rastgele herhangi bir Silindire atayacaktır;
Roller, alınan yürütme izini devrelere dönüştürür ve her devre için bir geçerlilik sertifikası oluşturur ve ardından sertifikayı Koordinatöre geri gönderir;
Her k L2 bloğu oluşturulduğunda, Koordinatör, k bloğun kanıtlarını tek bir toplu kanıtta birleştirmek için başka bir Silindire bir toplama görevi gönderecektir;
Koordinatör, Toplama sözleşmesine tek bir toplama kanıtı gönderir ve Toplama sözleşmesi, toplama kanıtını daha önce gönderilen durum kökü ve işlem verileriyle birlikte doğrular. Doğrulama başarılı olursa, ilgili bloğun Scroll üzerinde sonlandırıldığı kabul edilir.
Yukarıdaki süreçten de görülebileceği gibi Roller sistemdeki ispatlayıcı, Rollup sözleşmesi ise doğrulayıcıdır. Roller, zincir dışında gerçekleştirilen işlemler için bir zk kanıtı oluşturur; Toplama sözleşmesi kanıtı doğrular ve doğrulama geçerse, Toplama sözleşmesi, sunulan durum kökünü yeni durum kökü olarak doğrudan kabul eder.
View Original
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.
zk-SNARK'ın yapısı ve durumu
TL;DR
Kanıtlanacak Problemler-Aritmetik Devreler-R1CS-Polinomlar
Polinomların özelliklerinden dolayı doğrulama süresi etkili bir şekilde kısalır ve basitlik sağlanır.
Basitçe ifade etmek gerekirse, polinomu türetme sürecinde, iki rastgele sayı daha seçilir, böylece türetilmiş polinom, doğrulayıcının orijinal polinomun katsayılarını, yani kanıtlayıcının gizli girdisini elde etmesini engelleyebilir. ZK'yı gerçekleştirmek için.
Kanıtlama başlamadan önce, üçüncü bir taraf, yani orijinal doğrulayıcıya güvenilir ayara rasgele sayılar seçme görevini atayan ve böylece doğrulayıcı ile kanıtlayıcı arasındaki etkileşimsizliği gerçekleştiren güvenilir bir ayar sunulur.
ZK teknolojisi, son iki yılda Web3 alanında büyük ilgi gördü. Rollup'tan başlayarak, farklı yollarda giderek daha fazla proje ZK teknolojisini kullanmaya çalışıyor. Bunlar arasında SNARK ve STARK en çok duyulan iki terimdir.ZK teknolojisinin sonraki aşamalarda uygulanmasını daha iyi anlamak için **bu makale SNARK'ın ispat mantığını teknik olmayan bir bakış açısıyla basitleştirecek ve ardından kullanacaktır. * * Scroll's zk Rollup **, zk ispat sisteminin işleyişini göstermek için örnek olarak kullanılmıştır. **
Makalenin amacı, okunması kolay olan temel mantığı açıklamaktır.Terminoloji kullanımından kaçınılmaya çalışılacaktır ve matematiksel dönüşümler gibi ayrıntılara girilmeyecektir.Eksikler için lütfen kusuruma bakmayın.
Ocak 2012'de, Berkeley'deki California Üniversitesi'nde profesör olan Alessandro Chiesa, SNARK hakkında bir makale yazdı ve zk-SNARK terimini önerdi.
zk-SNARK, tam adı Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, ZK teknolojisini kullanan bir ispat sistemidir. **SNARK'ın bir şema sınıfının adı olduğu ve SNARK'ı uygulayabilen birçok farklı kombinasyon yöntemi olduğu unutulmamalıdır. **
zk-SNARK'ın çözmesi gereken "hesap doğrulama sorunu", yani doğrulayıcının, kanıtlayıcının gizliliğini bilmeden hesaplama sonuçlarını verimli bir şekilde doğrulayıp doğrulayamayacağıdır.
Aşağıda, sistemin verimli doğrulama elde etmek için sıfır bilgiyi nasıl birleştirdiğini göstermek için zk-SNARK'ın basitleştirilmiş oluşturma süreci kullanılacaktır. **
Zk-SNARK İnşaat
Kanıtlanacak problemi bir polinom haline getirin
Basitçe ifade etmek gerekirse, SNARK fikri, ifadenin doğru olup olmadığının kanıtını polinom eşitliğinin doğru olup olmadığının kanıtına dönüştürmektir.
Tüm dönüştürme süreci: doğrulanması gereken problemler ➡ aritmetik devre ➡ R1CS ➡ polinom ➡ polinomlar arasında dönüştürme
Doğrulanacak soru➡Aritmetik devre
Bir sorunun doğru olup olmadığını hesaplama yoluyla kanıtlamak için, kanıtlanacak sorunun önce bir hesaplama problemine dönüştürülmesi gerekir ve herhangi bir hesaplama bir aritmetik devre olarak tanımlanabilir.
Aritmetik devreler genellikle sabitlerden, "toplama kapıları" ve "çarpma kapılarından" oluşur Kapıların üst üste binmesi yoluyla karmaşık polinomlar oluşturabiliriz.
Yukarıdaki şekilde aritmetik devre tarafından oluşturulan polinom şu şekildedir: (Inp1+Inp2)*(-1) = Çıkış
Gerçekte problem aritmetik bir devreye dönüştürmek için son derece karmaşıktır.Bunu basitçe şu şekilde anlayabiliriz: bir miktar içerik girin, içerik devre tarafından dönüştürülür ve sonunda bir sonuç çıkarır. Şu anda:
Aritmetik devreler kavramına dayanarak, ispatlar üretmek için bir aritmetik devre kuruyoruz, yani:
Devre iki giriş seti içerir, genel giriş x ve gizli giriş w. Genel girdi x, içeriğin, hem doğrulayıcı hem de kanıtlayıcı tarafından bilinen, kanıtlanacak sorunun sabit bir değeri olduğu anlamına gelir ve gizli girdi w, içeriğin yalnızca kanıtlayıcı tarafından bilindiği anlamına gelir.
Kurduğumuz aritmetik devre C( x, w ) = 0, yani devre üzerinden x ve w girişi ve nihai çıkış sonucu 0'dır. Kanıtlayıcı ve doğrulayıcı, devrenin çıkışının 0 ve genel girişin x olduğunu bildiğinde, kanıtlayıcının w gizli girişini bildiğini kanıtlaması gerekir.
Aritmetik devre ➡R1CS
Sonunda bir polinoma ihtiyacımız var, ancak aritmetik devre doğrudan bir polinom'a dönüştürülemez ve ikisi arasında bir aracı olarak R1CS'ye ihtiyaç duyulur, bu nedenle aritmetik devre önce R1CS'ye dönüştürülür.
R1CS, tam adı Rank-1 Constraints (birinci dereceden kısıtlama sistemi), esasen bir matris-vektör denklemi olan devreleri açıklamak için kullanılan bir dildir. Spesifik olarak, R1CS, üç vektörün (a,b,c) bir dizisidir ve R1CS'nin çözümü, s'nin denklemi sağlaması gereken bir s vektörüdür:
Bunlar arasında iç çarpım işlemini temsil eder.
Buradaki belirli matematiksel dönüşüm Vatalik: Quadratic Aritmetic Programs: From Zero to Hero'da bulunabilir
Bilmemiz gereken tek şey, **R1CS'nin rolünün, aritmetik devredeki her geçidin tanımını sınırlamak olduğunu, böylece her kapı arasındaki vektörlerin yukarıdaki ilişkiyi karşılamasını sağlamaktır. **
R1CS➡Polinom
R1CS'nin ortamını elde ettikten sonra, onu bir polinom eşdeğerine dönüştürebiliriz.
Matrisler ve polinomlar arasındaki eşdeğer dönüşümler aşağıdaki şekilde gösterildiği gibi gerçekleştirilebilir:
polinom
matrise dönüştür
Yukarıdaki eşdeğer dönüşümün doğasına göre, R1CS'yi karşılayan bir matris için, polinomun her bir katsayısını eski haline getirmek için Lagrange interpolasyon yöntemini kullanabiliriz.Bu ilişkiye dayanarak, R1CS matrisini bir polinom ilişkisi olarak türetebiliriz, yani:
Not: A, B, C sırasıyla bir polinomu temsil eder
Bir polinom, kanıtlamak istediğimiz probleme karşılık gelen bir R1CS matris kısıtlamasına karşılık gelir.Yukarıdaki dönüşüm sayesinde, polinomların yukarıdaki ilişkiyi sağlaması durumunda, R1CS matrisimizin doğru olduğu anlamına geldiğini bilebiliriz, bu nedenle ispatlayıcının olduğunu gösterir. aritmetik devrededir.için gizli girişi de doğrudur.
Bu noktaya kadar problemimiz şu şekilde basitleştirilmiştir: doğrulayıcı rastgele bir x sayısı seçer ve onaylayıcıdan A(x) * B(x)=C(x)'in doğru olduğunu kanıtlamasını ister. onaylayıcının gizli girişinin doğru olduğu anlamına gelir.
Polinomlar arasında dönüştürme
Karmaşık aritmetik devrelerde on binlerce kapı vardır ve her kapının R1CS kısıtlamasını karşılayıp karşılamadığını doğrulamamız gerekir. Başka bir deyişle, A(x) * B(x)=C(x) eşitliğini birkaç kez doğrulamamız gerekiyor, ancak ayrı ayrı doğrulamanın etkinliği çok düşük. tek seferde kapı kısıtlamaları seks?
Anlama kolaylığı için, bir P(x) tanıtıyoruz, P(x) = A(x) * B(x) – C(x) olsun
Herhangi bir polinomun bir çözümü olduğu sürece lineer polinomlara ayrıştırılabileceğini biliyoruz. Böylece P(x)'i F(x) ve H(x)'e böleriz, yani:
O zaman F(x) herkese açıktır, yani bir H(x) = P(x)/F(x) vardır, dolayısıyla doğrulamak istediğimiz polinom sonunda şuna dönüşür:
A(x) * B(x) – C(x): Polinomun sadece ispatlayıcı yani gizli girdi tarafından bilinen katsayılarını içerir.
F(x) : Hem doğrulayıcı hem de kanıtlayıcı tarafından bilinen genel bir polinom, yani genel girdi.
H(x): Kanıtlayan bunu hesaplama yoluyla bilir, ancak doğrulayıcı bilinemez.
**Kanıtlanacak son problem şudur: A(x) * B(x) – C(x) = F(x) * H(x) polinom denklemi tüm x'ler için geçerlidir. **
Şimdi, tüm kısıtlamaların matris ilişkilerini karşıladığını doğrulamak için polinomu bir kez doğrulamak yeterlidir.
**Burada sistemin basitliğini fark ederek ispatlanacak problemin sadece bir kez doğrulanması gereken bir polinom haline dönüşümünü tamamlamış olduk. **
Ancak bu uygulamanın basitliği, doğrulayıcının doğrulama süresini kısaltmasıdır, peki ya ispat boyutu?
**Basitçe söylemek gerekirse, ispat protokolünde, ispatın boyutunu etkili bir şekilde azaltan Merkle ağaç yapısı kullanılır. **
Tüm dönüştürme işlemi tamamlandıktan sonra doğal olarak iki sorun ortaya çıkacaktır:
Çünkü polinomlar ispatın basitliğini sağlar. Sıfır bilgi ispatının sorunu, hesaplamaların çoklu kısıtlamaları karşıladığını doğrulamaktır ve polinomlar bir noktada çoklu kısıtlamaları doğrulayabilir. Başka bir deyişle, doğrulayıcının sorunu doğrulamak için n kez doğrulaması gerekir, ancak şimdi ispatın doğruluğunu yüksek bir olasılıkla doğrulamak için yalnızca bir kez doğrulaması gerekir.
Bu, polinomların özellikleri tarafından belirlenir, yani bir polinomun herhangi bir noktadaki hesaplama sonucu, onun benzersiz kimliğinin temsili olarak kabul edilebilir. İki polinom için, yalnızca sonlu sayıda noktada kesişeceklerdir.
Yukarıdaki d dereceli iki polinom için: A(x) * B(x) – C(x) ve F(x) * H(x), eğer eşit değillerse, sadece en fazla d noktada olacaklardır. Kesişim, yani d noktalarındaki çözümler aynıdır.
Polinom dönüşümünü tamamladıktan sonra polinom ispat aşamasına geçeceğiz.
Polinomun geçerli olduğunu kanıtlayın
Açıklama amacıyla, P(x) = F(x) * H(x) polinomunu kullanıyoruz.
Şimdi, kanıtlayıcının kanıtlamak istediği problem şudur: tüm x'lerde, P(x) = F(x) * H(x).
Yukarıdaki polinomun kanıtlayıcı ve doğrulayıcı tarafından doğrulanma süreci şu şekildedir:
Ancak dikkatlice düşünürsek, yukarıdaki süreçte bazı problemler olduğunu görürüz:
Yukarıdaki sorunları çözmek için aşağıdaki optimizasyonları yapıyoruz:
Optimizasyondan sonra ispat sisteminin hala doğrulayıcı ile ispatlayıcı arasında etkileşim gerektirdiğini gördük Etkileşimsizliğe nasıl ulaşabiliriz?
Etkileşimsiz uygulama
**Etkileşimsizliğe ulaşmak için SNARK, güvenilir ayarlar sunar (Kurulum). **
Başka bir deyişle, ispat başlamadan önce, doğrulayıcının rasgele meydan okuma noktalarını seçme hakkı güvenilir bir üçüncü tarafa teslim edilir.Üçüncü taraf rasgele parametre λ'yı seçtikten sonra, şifreli λ'yı R1CS devresine koyar. şekilde, CRS (Common Reference String, public reference string) oluşturulur. Doğrulayıcı kendi Sv'sini CRS'den alabilir ve kanıtlayıcı kendi Sp'sini CRS'den alabilir.
Sv ve Sp oluşturulduktan sonra λ'nın yok edilmesi gerektiğine dikkat edilmelidir. λ sızdırılırsa, yanlış doğrulama yoluyla sahte işlemler yapmak için kullanılabilir.
zk-SNARK İş Akışı
SNARK'ın yapım sürecini anladıktan sonra, ispat üretebilen kurduğumuz aritmetik devreden yola çıkarak, zk-SNARK'ın ispat süreci şu şekildedir:
C devresi ve rasgele parametre λ aracılığıyla, sonraki kanıtlayıcı ve doğrulayıcı tarafından kullanılan rasgele parametreler Sv ve Sp üretilir.
Prover, rasgele Sp parametresi, genel x girişi ve w gizli girişi aracılığıyla ispatı Π hesaplar.
Doğrulayıcı, C(x,w)=0'ın var olup olmadığını rastgele parametre Sv, genel giriş x ve kanıt Π aracılığıyla doğrular. Aynı zamanda ispatın C devresi tarafından hesaplanıp hesaplanmadığını doğrulayın.
Bu noktada zk-SNARK'ın tamamının açıklamasını tamamlamış olduk, asıl uygulama örneğine bir göz atalım.
Vaka: Scroll'un zk Toplamasını örnek olarak alalım
İspat sisteminin rolü, ispatlayanın doğrulayıcıyı bir şeye inanmaya ikna etmesine izin vermektir;
zk ispat sistemi için doğrulayıcıyı, zk algoritması tarafından hesaplanan Sıfır Bilgi İspatının (sıfır bilgi ispatı) doğru olduğuna inandırmaktır.
Zk ispat sisteminin işleyişini göstermek için Scroll'un zk Toplamasını örnek olarak alıyoruz.
Toplama, zincir dışı hesaplama ve zincir içi doğrulama anlamına gelir. zk Toplama için, işlem zincir dışında yürütüldükten sonra kanıtlayıcının, işlem yürütüldükten sonra oluşturulan yeni durum kökü için bir zk sertifikası oluşturması ve ardından zincir üzerinde doğrulama için sertifikayı L1 Toplama sözleşmesine iletmesi gerekir.
zk Toplamasında iki tür blok bulunduğuna dikkat edilmelidir:
Aşağıda, Scroll'un zk Toplamasının iş akışı yer almaktadır:
Yukarıdaki süreçten de görülebileceği gibi Roller sistemdeki ispatlayıcı, Rollup sözleşmesi ise doğrulayıcıdır. Roller, zincir dışında gerçekleştirilen işlemler için bir zk kanıtı oluşturur; Toplama sözleşmesi kanıtı doğrular ve doğrulama geçerse, Toplama sözleşmesi, sunulan durum kökünü yeni durum kökü olarak doğrudan kabul eder.