Sıfır Bilgi Kanıtlarının Gücü: zk-SNARK'lara Derinlemesine Bakış

Bu makale, bu teknolojinin şifresini matematik kullanarak çözecek ve herhangi bir bilgiyi açığa vurmadan bilginin doğruluğunu nasıl kanıtlayabileceğini gösterecek.

Derleyen: DODO Araştırma

Yazar: 0xAlpha Kurucu Ortağı @DeriProtocol

Giriş

Zk-SNARK veya sıfır bilgi, kısa ve etkileşimli olmayan bilgi argümanı, doğrulayıcının, bir kanıtlayıcının, bilginin kendisi hakkında herhangi bir bilgiyi açıklamadan belirli ilişkileri karşılayan belirli bilgilere (tanıklar olarak adlandırılır) sahip olduğunu doğrulamasını sağlar.

Belirli bir sorun için zk-SNARK oluşturmak aşağıdaki dört aşamayı içerir:

• Bir problemi (veya fonksiyonu) bir aritmetik devreye dönüştürün.
• Bu devre daha sonra bir matris denklemine dönüştürülür.
• Bu matris denklemi ayrıca belirli bir minimum polinoma bölünmesi gereken bir polinoma dönüştürülür.
• Son olarak bu bölünebilirlik, kanıtın yer aldığı sonlu bir alan üzerindeki eliptik eğri noktalarıyla ifade edilir.

İlk üç adım yalnızca orijinal ifadenin temsilini dönüştürür. Son adım, üçüncü adımdaki ifadeyi homomorfik şifreleme kullanarak şifrelenmiş bir alana yansıtır ve kanıtlayıcının buradaki yansıtılmış ifadeleri doğrulamasına olanak tanır. Bu projeksiyonun asimetrik şifreleme kullandığı göz önüne alındığında, 3. adımdaki ifadeden orijinal ifadeye geri dönüş yapılması mümkün değildir, böylece sıfır bilgi açığa çıkar.

Bu makaleyi okumak için gereken matematiksel altyapı, STEM üniversitesinin birinci sınıf öğrencilerinden beklenen cebir düzeyiyle karşılaştırılabilir. Zorlayıcı olabilecek tek kavram eliptik eğri kriptografisi olabilir. Bilmeyenler için bunu özel tabanlı üstel bir fonksiyon olarak düşünebilirsiniz, tersinin çözümsüz kaldığını unutmayın.

Bu makalede aşağıdaki gösterim kuralları izlenecektir:

Matrisler: Kalın büyük harfler, örneğin A; açık formlarda yazılmış \
Vektörler: Açık biçimlerde yazılmış oklu küçük harf [ ]; tüm vektörler varsayılan olarak sütun vektörleridir \
Skalerler: Normal harflerle temsil edilir

Örnek olarak aşağıdaki soruyu ele alalım:

f(x)=x^3+x^2+5 (1)

Diyelim ki Alice bir gerçeği bildiğini kanıtlamak istiyor. Alice'in kanıtı için bir zk-SNARK oluşturmak için gerçekleştirmesi gereken tüm prosedürü anlatacağız.
Bu soru çok basit görünebilir çünkü kontrol akışını (örneğin, if-then-else) içermemektedir. Ancak kontrollü akışa sahip fonksiyonları aritmetik ifadelere dönüştürmek zor değildir. Örneğin, aşağıdaki sorunu (veya programlama dillerindeki "işlevi") göz önünde bulundurun:

f(x,z):
eğer(z==1):
dönüş xxx+xx+5
başka:
x x+5'i döndür

Bu problemi aşağıdaki aritmetik ifadeye yeniden yazmak (z'nin (0,1)'e ait olduğunu varsayarak) denklem (1)'den daha karmaşık değildir.

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

Bu makalede tartışmamızın temeli olarak denklem (1)'i kullanmaya devam edeceğiz.

Adım 1: Aritmetik Devre

Denklem (1) aşağıdaki temel aritmetik işlemlere ayrılabilir:

Bu, aşağıdaki aritmetik devreye karşılık gelir:

Ayrıca denklem (2)'ye 4 "birincil kısıtlama" kümesi olarak atıfta bulunuyoruz; her kısıtlama devredeki bir aritmetik kapının ilişkisini tanımlıyor. Genel olarak, n adet birincil kısıtlamadan oluşan bir dizi, daha sonra açıklanacak olan ikinci dereceden aritmetik program (QAP) olarak özetlenebilir.

Adım 2: Matris

Öncelikle bir “tanık” vektörünü şu şekilde tanımlayalım:

burada y, s1, s2 ve s3 denklem (2)'deki gibi tanımlanır.
Tipik olarak, m girişi ve n aritmetik kapısı olan bir problem için (ör. n-1 ara adım ve son çıktı), bu tanık vektörü (m+n+1) boyutlu olacaktır. Gerçek hayattaki durumlarda n sayısı son derece büyük olabilir. Örneğin karma işlevler için n genellikle binler cinsindendir.

Daha sonra, denklem (2)'yi aşağıdaki gibi yeniden yazabilmemiz için üç n(m+n+1) A,B,C matrisi oluşturalım:

Denklem (3), denklem (2)'nin sadece başka bir temsilidir: her set (ai, bi, ci) devredeki bir kapıya karşılık gelir. Bunu matris denklemini açıkça genişleterek görebiliriz:

Yani LHS=RHS denklem (2) ile tam olarak aynıdır ve matris denkleminin her satırı bir birincil kısıtlamaya (yani devredeki bir aritmetik kapıya) karşılık gelir.

Aslında nispeten basit olan (A, B, C) oluşturma adımlarını atladık. (A, B, C), yani (ai, bi, ci)'nin her satırının içeriğini belirlemek için bunları yalnızca karşılık gelen birincil kısıtlamalara göre matrise dönüştürmemiz gerekir. İlk satırı örnek alırsak: İlk birincil kısıtı x ile x'in s1'e eşit olması için [0,1,0,0,0], [0, 1,0, ile çarpmamız gerektiğini kolaylıkla görebiliriz. 0,0] ve [0,0,0,1,0,0] s vektörüyle.

Böylece aritmetik devreyi başarıyla bir matris denklemine, yani denklem (3)'e dönüştürdük. Aynı zamanda master olduğu kanıtlanması gereken nesneyi de tanık vektörlerine dönüştürdük.

Adım 3: Polinomlar

Şimdi z'ye ilişkin bir dizi polinomu tanımlayan bir n(n+m+*1) matrisi PA oluşturalım:

Fonksiyonun sağlanması {1, 2, 3, 4} noktasında aşağıdaki değerleri alır ve koşulları sağlar:

O zaman A'yı şu şekilde yeniden yazabiliriz:

Bunlar, geleneksel yöntemler kullanılarak çözülebilen, altı değişkeni içeren dört grup doğrusal denklemdir. Ancak bu durumda PA'yı çözmenin daha etkili bir yolu, problemin özelliklerinden yararlanan Lagrangian enterpolasyonudur. Burada biraz sıkıcı ama basit olan PA çözme sürecini atlıyoruz.

Benzer şekilde, B ve C için PB ve PC'yi ayrı ayrı oluşturuyoruz. Daha sonra matris denklemini yeniden yazabiliriz.aşağıdaki gibi:

Her satıra ayrı ayrı bakıldığında bu dört satırın, dört farklı noktada değerlendirilen aynı ifadeye karşılık geldiği görülmektedir. Bu nedenle yukarıdaki matris denklemi şuna eşdeğerdir:

Adım 3: Eliptik Eğri Noktası

Denklemi (4) şu şekilde yeniden yazın:

burada i(z)=1, denklemleri birleştirmek için kullanılan z'deki önemsiz bir sıfırıncı derece polinomudur - tüm terimler ikinci derecedendir. Bunun gerekliliği kısa sürede ortaya çıkacak. Bu denklemin yalnızca z'deki polinomların toplamasını ve çarpımını içerdiğini unutmayın.

Toplama (+) ve çarpma (X) gibi aritmetik işlemlerin de eliptik eğri noktalarının sonlu alanındaki karşılık gelen işlemlerle eşleştirildiğini lütfen unutmayın. Semboller Ve karışıklığı önlemek ve bunların yeniden tanımlanmış saha operasyonları olduğunu belirtmek için kullanılır.

Daha sonra pratik adımları daha ayrıntılı olarak açıklayacağız.

Eliptik Eğri Kriptografisi

Eliptik eğrilerin genel teorisi bu makalenin kapsamının çok ötesine geçer. Buradaki amaçlar doğrultusunda, eliptik bir eğri, bir Fp asal alanından E fonksiyonuna eşlemeler olarak tanımlanır; burada E, y^2=x^3+ax+b (eliptik eğri noktaları veya kısaca ECP'ler olarak adlandırılır) gibi noktaları içerir. .

Şu ana kadar normal aritmetiği tartışırken, asal alana geçiş sırasında sayılar üzerinde aritmetik işlemlerin modüler aritmetik kullanılarak gerçekleştirildiğini lütfen unutmayın. Örneğin, a+b=a+b(mod p), burada p, Fp'nin sırasıdır.

Öte yandan iki eliptik eğri noktasının toplamı aşağıda gösterildiği gibi tanımlanır:

Spesifik olarak, iki ECP'nin P ve Q'sunun eklenmesi:

PQ çizgisi ile R eğrisinin kesişimini bulun ve bunu -(P+Q) olarak tanımlayın.
Eğri üzerindeki R'nin "ayna" noktası R'ye çevirin.
Bu nedenle P+Q=R' eliptik eğri noktalarının toplamını tanımlarız:

Bu kuralın aynı zamanda bir ECP'nin eklenmesinin kullanıldığı özel durum için de geçerli olduğunu unutmayın; bu durumda o noktaya teğet kullanılacaktır.

Şimdi rastgele bir G noktası seçtiğimizi ve 1 sayısını ona eşlediğimizi varsayalım. (Bu “ilk haritalama” kulağa biraz keyfi geliyor. Bunu daha sonra tartışacağız). Ve Fp'ye ait herhangi bir n için şunu tanımlarız:

E(N)=G+G+G+…..+G=G çarpı n

Bir işlem ifadesi var. +G işlemini g ile gösterilen “jeneratör” olarak tanımlayın. O halde yukarıdaki tanım şuna eşdeğerdir:

Toplama tanımlandıktan sonra aşağıdaki doğrusal ilişki ortaya çıkar:

Bu nedenle, Fp'deki herhangi bir doğrusal ilişki (veya kısıtlama), bu eşleme yoluyla şifrelenmiş alan B'de korunacaktır. Örneğin, Fp'deki l + m = n denklemi şuna yol açacaktır:

Ancak Alice'in kanıtlamak istediği denklem (5) ikinci dereceden formda olduğundan yeterince doğrusal değildir. İkinci dereceden terimleri ele almak için şifreli alanda çarpma işlemini tanımlamamız gerekir. Buna eşleştirme veya çift doğrusal harita denir ve bunu aşağıdaki bölümde açıklayacağım.

Çift Doğrusal Harita

G1, G2 ve GT'nin asal mertebeden g grupları olduğunu varsayalım. Bir eşleştirme fonksiyonu veya çift doğrusal harita şu şekilde tanımlanır:

Ortak Referans Dizesi

Bu bütüne “kanıtlama anahtarı” (PK) adı verilir. E() içindeki vektörlerin temsilinin, her noktanın karşılık gelen vektör öğesinden eşlendiği eliptik eğri noktalarının vektörleri olarak anlaşılması gerektiğine dikkat edin. Böylece bu 11 vektör aslında 62 (=42+63+63+63) eliptik eğri noktasından oluşur. Bu 62 ECP, kanıtlayıcı Alice'e sağlanacaktır. Genel bir senaryoda, m girdili ve n birincil kısıtlı bir problem için, PK 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP içerecektir.

Eş zamanlı olarak aşağıdaki hesaplamalar yapılacaktır:

Sürecin tamamına “doğrulama anahtarı” (VK) denir. Burada doğrulayıcıya sağlanması gereken yalnızca 7 eliptik eğri noktası (ECP) yer almaktadır. Sorunda ne kadar çok girdi ve birincil kısıtlama yer alırsa alsın, VK'nın her zaman 7 ECP'den oluştuğu unutulmamalıdır.

Ayrıca, "güvenilir kurulum" ve PK ve VK oluşturma sürecinin belirli bir sorun için yalnızca bir kez yapılması gerektiğini belirtmekte fayda var.

Kanıtlama ve Doğrulama

Artık ortak anahtara (PK) sahip olan Alice, aşağıdaki eliptik eğri noktalarını (ECP'ler) hesaplayacaktır:

Bu 9 eliptik eğri noktası, sıfır bilgili, kısa ve etkileşimli olmayan bir bilgi argümanı (zk-SNARK) için çok önemlidir!

Alice'in aslında sadece genel anahtardaki eliptik eğri noktaları üzerinde doğrusal kombinasyonlar gerçekleştirdiğini unutmayın. Bu özellikle kritiktir ve doğrulama sırasında titizlikle kontrol edilecektir.

Şimdi Alice zk-SNARK kanıtını sunuyor ve sonunda bizi üç adımda gerçekleşen doğrulama sürecine yönlendiriyor.

İlk olarak, ilk 8 eliptik eğri noktasının gerçekten de ortak referans dizisindeki bu noktaların doğrusal kombinasyonları olduğunun doğrulanması gerekir.

Yasal Uyarı:

1. Bu makale[chaincatcher] sitesinden yeniden basılmıştır. Tüm telif hakları orijinal yazara aittir [0xAlpha Kurucu Ortağı @ DeriProtocol]. Bu yeniden basıma itirazlarınız varsa lütfen Gate Learn ekibiyle iletişime geçin; onlar konuyu hemen halledeceklerdir.
2. Sorumluluk Reddi: Bu makalede ifade edilen görüş ve görüşler yalnızca yazara aittir ve herhangi bir yatırım tavsiyesi teşkil etmez.
3. Makalenin diğer dillere çevirileri Gate Learn ekibi tarafından yapılır. Aksi belirtilmedikçe tercüme edilen makalelerin kopyalanması, dağıtılması veya intihal edilmesi yasaktır.