Vitalik Buterin aracılığıyla Vitalik Buterin'in Blogu
Bu, şu adresteki yazının bir aynasıdır: https://medium.com/@VitalikButerin/zk-snarks-under-the-head-b33151a013f6
Bu, zk-SNARK'ların arkasındaki teknolojinin nasıl çalıştığını açıklayan bir dizi makalenin üçüncü bölümüdür; önceki makaleler ikinci dereceden aritmetik programlar ve eliptik eğri eşleşmeleri okunması zorunludur ve bu makale her iki kavramın da bilindiğini varsayacaktır. zk-SNARK'ların ne olduğu ve ne yaptıklarına ilişkin temel bilgilerin de olduğu varsayılmaktadır. Ayrıca bakınız Christian Reitwiessner'ın makalesi burada başka bir teknik tanıtım için.
Önceki makalelerde, herhangi bir hesaplama problemini, çeşitli matematiksel hile biçimlerine çok daha uygun olan bir polinom denklemiyle temsil etmenin bir yolu olan ikinci dereceden aritmetik programını tanıtmıştık. Ayrıca eşitlik kontrolü yapmanıza olanak tanıyan tek yönlü homomorfik şifrelemenin çok sınırlı bir biçimine izin veren eliptik eğri eşleştirmelerini de tanıttık. Şimdi, kaldığımız yerden başlayacağız ve bir kanıtlayıcının, QAP hakkında başka hiçbir şey açıklamadan, belirli bir QAP için bir çözüm bildiğini kanıtlamasına izin vermek için eliptik eğri eşleştirmelerini birkaç başka matematik hilesiyle birlikte kullanacağız. gerçek çözüm.
Bu makale şunlara odaklanacak: Pinokyo protokolü Parno, Gentry, Howell ve Raykova tarafından 2013'ten itibaren (genellikle PGHR13 olarak anılır); temel mekanizmada birkaç değişiklik vardır; dolayısıyla pratikte uygulanan zk-SNARK şeması biraz farklı çalışabilir ancak temel ilkeler genel olarak aynı kalacaktır.
Başlangıç olarak kullanacağımız mekanizmanın güvenliğinin altında yatan temel kriptografik varsayıma geçelim: *üs bilgisi* varsayım.
Temel olarak, �⋅�=� olmak üzere bir � ve � noktası çifti elde ederseniz ve bir � noktası elde ederseniz, o zaman � bir şekilde �'den "türetilmedikçe" �⋅� elde etmek mümkün değildir bildiğin. Bu sezgisel olarak açık görünebilir, ancak bu varsayım aslında eliptik eğri tabanlı protokollerin güvenliğini kanıtlarken genellikle kullandığımız başka herhangi bir varsayımdan (örneğin, ayrık log sertliği) türetilemez ve bu nedenle zk-SNARK'lar aslında bir miktar varsayıma dayanır. Daha genel anlamda eliptik eğri kriptografisine göre daha sağlam bir temele sahiptir; yine de çoğu kriptografın kabul edeceği kadar sağlamdır.
Şimdi bunun nasıl kullanılabileceğine geçelim. Gökten bir çift noktanın (�,�) düştüğünü varsayalım, burada �⋅�=� ama kimse �'nin değerinin ne olduğunu bilmiyor. Şimdi, �⋅�=� olan bir çift nokta (�,�) bulduğumu varsayalım. O halde, KoE varsayımı, bu nokta çiftini elde edebilmemin tek yolunun � ve � alıp her ikisini de bir r faktörüyle çarpmak olduğunu ima eder. şahsen bildiğim. Ayrıca eliptik eğri eşleştirmelerinin büyüsü sayesinde �=�⋅� ifadesinin kontrol edildiğini de unutmayın. aslında bilmeyi gerektirmiyor – bunun yerine �(�,�)=�(�,�) olup olmadığını kontrol edebilirsiniz.
Daha ilginç bir şey yapalım. Diyelim ki gökten on çift nokta düşüyor: (�1,�1),(�2,�2)…(�10,�10). Her durumda ��⋅�=��. Daha sonra size �⋅�=� olan bir çift nokta (�,�) sunduğumu varsayalım. Şimdi ne biliyorsun? �'nin �1⋅�1+�2⋅�2+…+�10⋅�10 doğrusal kombinasyonu olduğunu biliyorsunuz, burada �1,�2…�10 katsayılarını biliyorum. Yani böyle bir nokta çiftine (�,�) ulaşmanın tek yolu �1,�2…�10’un katlarından bazılarını alıp toplayıp aynı hesaplamayı �1,�2… ile yapmaktır. �10.
Doğrusal kombinasyonları kontrol etmek isteyebileceğiniz herhangi bir belirli �1…�10 nokta kümesi verildiğinde, aslında �’nin ne olduğunu bilmeden ona eşlik eden �1…�10 noktayı yaratamayacağınızı ve eğer biliyorsanız ne olduğunu bildiğinizi unutmayın. � o zaman doğrusal bir kombinasyon oluşturma zahmetine girmeden, istediğiniz � için �⋅�=� olan bir çift (�,�) oluşturabilirsiniz. Dolayısıyla bunun işe yaraması için, bu noktaları oluşturan kişinin güvenilir olması ve on noktayı oluşturduktan sonra gerçekten silmesi kesinlikle zorunludur. “Güvenilir kurulum” kavramı buradan geliyor.
Bir QAP çözümünün, �(�)⋅�(�)−�(�)=�(�)⋅�(�) olacak şekilde bir dizi polinom (�,�,�) olduğunu unutmayın; burada:
- � bir dizi polinomun doğrusal birleşimidir {�1…��}
- �, {�1…��}'nin aynı katsayılara sahip doğrusal birleşimidir
- �, {�1…��}'nin aynı katsayılara sahip doğrusal birleşimidir
{�1…��},{�1…��} ve {�1…��} kümeleri ve � polinomu problem ifadesinin bir parçasıdır.
Ancak gerçek dünyadaki çoğu durumda �,� ve � son derece büyüktür; Karma işlevi gibi binlerce devre kapısına sahip bir şey için polinomlar (ve doğrusal kombinasyonlara ilişkin faktörler) binlerce terime sahip olabilir. Bu nedenle, kanıtlayıcının doğrusal kombinasyonları doğrudan sağlamasını sağlamak yerine, yukarıda tanıttığımız hileyi kullanarak kanıtlayıcının, başka hiçbir şeyi açığa vurmadan, doğrusal bir kombinasyon olan bir şey sağladığını kanıtlamasını sağlayacağız.
Yukarıdaki yöntemin polinomlarda değil eliptik eğri noktalarında işe yaradığını fark etmiş olabilirsiniz. Dolayısıyla gerçekte olan şey, güvenilir kuruluma aşağıdaki değerleri eklememizdir:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
T'yi polinomun değerlendirildiği "gizli nokta" olarak düşünebilirsiniz. � bir “jeneratör”dür (protokolün bir parçası olarak belirtilen bazı rastgele eliptik eğri noktaları) ve �,��,�� ve �� “zehirli atıktır”, ne pahasına olursa olsun kesinlikle silinmesi gereken sayılardır veya aksi takdirde bunlara sahip olan kişi sahte deliller sunabilecektir. Şimdi, eğer biri size �⋅��=� şeklinde bir �, � noktası çifti verirse (hatırlatma: eşleştirme kontrolü yapabileceğimiz için bunu kontrol etmek için �� işaretine ihtiyacımız yok), o zaman onların ne yaptığını bilirsiniz. size � olarak değerlendirilen �� polinomlarının doğrusal bir birleşimini veriyoruz.
Bu nedenle, şu ana kadar kanıtlayıcı şunları vermelidir:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Kanıtlayıcının bu değerleri hesaplamak için aslında �,��,�� veya ��’yi bilmesine gerek olmadığını (ve bilmemesi gerektiğini) unutmayın; bunun yerine kanıtlayıcının bu değerleri yalnızca güvenilir kuruluma eklediğimiz noktalardan hesaplayabilmesi gerekir.
Bir sonraki adım, üç doğrusal kombinasyonun hepsinin aynı katsayılara sahip olduğundan emin olmaktır. Bunu, güvenilir düzene başka bir değer kümesi ekleyerek yapabiliriz: �⋅(��(�)+��(�)+��(�))⋅�, burada �, "zehirli" olarak kabul edilmesi gereken başka bir sayıdır. atık” ve güvenilir kurulum tamamlanır tamamlanmaz atılır. Daha sonra kanıtlayıcının aynı katsayılara sahip bu değerlerle doğrusal bir kombinasyon oluşturmasını sağlayabiliriz ve bu değerin sağlanan "+�+" ile eşleştiğini doğrulamak için yukarıdakiyle aynı eşleştirme numarasını kullanabiliriz.
Son olarak �⋅�−�=�⋅� olduğunu kanıtlamamız gerekiyor. Bunu bir kez daha eşleştirme kontrolüyle yapıyoruz:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Burada �ℎ=�⋅�(�). Bu denklem ile �⋅�−�=�⋅� arasındaki bağlantı size anlamlı gelmiyorsa geri dönüp aşağıdakileri okuyun. eşleştirmelerle ilgili makale.
Yukarıda �,� ve �'yi eliptik eğri noktalarına nasıl dönüştüreceğimizi gördük; � sadece üreteçtir (yani bir numaranın eliptik eğri noktası eşdeğeri). Güvenilir kuruluma �⋅�(�) ekleyebiliriz. daha zordur; � sadece bir polinomdur ve her bir QAP çözümü için katsayılarının ne olacağı konusunda önceden çok az tahminde bulunabiliriz. Bu nedenle güvenilir kuruluma daha fazla veri eklememiz gerekiyor; özellikle sıra:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
Zcash güvenilir kurulumunda buradaki sıralama yaklaşık 2 milyona kadar çıkıyor; bu, en azından onların önemsediği belirli QAP örneği için, her zaman �(�)'yi hesaplayabileceğinizden emin olmak için �'nin kaç kuvvetine ihtiyaç duyduğunuzdur. Ve bununla birlikte, kanıtlayıcı, doğrulayıcının son kontrolü yapması için tüm bilgileri sağlayabilir.
Konuşmamız gereken bir detay daha var. Çoğu zaman belirli bir soruna yönelik bir çözümün var olduğunu soyut olarak kanıtlamak istemiyoruz; bunun yerine, ya belirli bir çözümün doğruluğunu kanıtlamak istiyoruz (örneğin, "inek" kelimesini ve SHA3'ün bunu milyon kez hashlemesini yaparsanız, nihai sonucun 0x73064fe5 ile başladığını kanıtlamak), ya da kısıtlarsanız bir çözümün var olduğunu kanıtlamak istiyoruz. parametrelerden bazıları. Örneğin, işlem tutarlarının ve hesap bakiyelerinin şifrelendiği bir kripto para birimi örneğinde, aşağıdaki gibi bir k şifre çözme anahtarını bildiğinizi kanıtlamak istersiniz:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
şifreli old_balance
, tx_value
ve new_balance
bunlar, o anda doğrulamaya çalıştığımız spesifik değerler olduğundan, kamuya açık olarak belirtilmelidir; yalnızca şifre çözme anahtarı gizlenmelidir. Girişlerdeki belirli kısıtlamalara karşılık gelen bir "özel doğrulama anahtarı" oluşturmak için protokolde bazı küçük değişiklikler yapılması gerekir.
Şimdi biraz geriye gidelim. Her şeyden önce, Ben'in izniyle, doğrulama algoritmasının tamamı burada. Sasson, Tromer, Virza ve Chiesa:
İlk satır parametrelendirmeyle ilgilidir; esasen işlevini "özel doğrulama anahtarı" oluşturmak olarak düşünebilirsiniz sorunun spesifik örneği için bazı argümanların belirtildiği yer. İkinci satır �,� ve � için doğrusal kombinasyon kontrolüdür; üçüncü satır doğrusal kombinasyonların aynı katsayılara sahip olduğunun kontrolü, dördüncü satır ise ⋅�−�=�⋅� çarpım kontrolüdür.
Toplamda, doğrulama süreci birkaç eliptik eğri çarpımından (her "genel" giriş değişkeni için bir tane) ve biri ek bir eşleştirme çarpımı içeren beş eşleştirme kontrolünden oluşur. İspat sekiz eliptik eğri noktası içerir: her biri �(�),�(�) ve �(� için bir çift nokta, �⋅(�(�)+�(�)+�(� için bir �� noktası) )) ve �(�) için bir �ℎ noktası. Bu noktalardan yedisi �� eğrisi üzerindedir (her biri 32 bayt, � koordinatını tek bir bit’e sıkıştırabilirsiniz) ve Zcash uygulamasında bir nokta (��) ��2’deki bükülmüş eğri üzerindedir (64 bayt), dolayısıyla kanıtın toplam boyutu ~288 bayttır.
Bir kanıt oluşturmanın hesaplama açısından en zor iki kısmı şunlardır:
- � elde etmek için (�⋅�−�)/� bölme (algoritmalar Hızlı Fourier dönüşümü bunu ikinci dereceden altı zamanda yapabilir, ancak yine de hesaplama açısından oldukça yoğundur)
- �(�),�(�),�(�) ve �(�) değerlerini ve bunlara karşılık gelen çiftleri oluşturmak için eliptik eğri çarpımlarını ve toplamalarını yapmak
Kanıt oluşturmanın bu kadar zor olmasının temel nedeni, orijinal hesaplamada tek bir ikili mantık kapısının, sıfır bilgi kanıtını yapıyorsak, eliptik eğri işlemleri aracılığıyla kriptografik olarak işlenmesi gereken bir işleme dönüşmesidir. . Bu gerçek, hızlı Fourier dönüşümlerinin süper doğrusallığıyla birlikte, bir Zcash işlemi için kanıt oluşturmanın ~20-40 saniye sürdüğü anlamına gelir.
Bir başka çok önemli soru da şudur: Güvenilir kurulumu biraz daha az güven gerektiren hale getirmeye çalışabilir miyiz? Ne yazık ki bunu tamamen güvenilmez hale getiremiyoruz; KoE varsayımının kendisi, �'nin ne olduğunu bilmeden bağımsız (��,��⋅�) çiftleri oluşturmayı engeller. Bununla birlikte, çok taraflı hesaplamayı kullanarak, yani taraflar arasında güvenilir kurulumu, katılımcılardan en az biri toksik atıklarını sildiği sürece sorun olmayacak şekilde oluşturarak güvenliği büyük ölçüde artırabiliriz. .
Bunu nasıl yapacağınıza dair biraz fikir edinmek için, mevcut bir kümeyi (�,�⋅�,�⋅�2,�⋅�3…) alıp kendi sırrınızı "eklemek" için basit bir algoritmayı burada bulabilirsiniz. böylece hile yapmak için hem sırrınıza hem de önceki sırrınıza (veya önceki sır grubuna) ihtiyacınız vardır.
Çıkış seti basitçe:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Bu seti yalnızca orijinal seti ve s'yi bilerek üretebileceğinizi ve yeni setin, artık � yerine "zehirli atık" olarak �⋅� kullanılması dışında, eski setle aynı şekilde çalıştığını unutmayın. Siz ve önceki seti oluşturan kişi (veya kişiler) zehirli atıklarınızı silmeyi ihmal etmediğiniz ve daha sonra işbirliği yapmadığınız sürece set “güvenlidir”.
Güvenilir kurulumun tamamı için bunu yapmak biraz daha zordur, çünkü birden fazla değer söz konusudur ve algoritmanın taraflar arasında birkaç turda yapılması gerekir. Bu, çok partili hesaplama algoritmasının daha da basitleştirilip daha az tur gerektirecek şekilde yapılıp yapılamayacağını veya daha fazla paralelleştirilebilir hale getirilip getirilemeyeceğini görmek için aktif bir araştırma alanıdır; çünkü bunu ne kadar çok yaparsanız, güvenilir kurulum prosedürüne o kadar çok partiyi dahil etmek mümkün hale gelir. . Birbirini tanıyan ve birlikte çalışan altı katılımcı arasındaki güvenilir bir kurulumun neden bazı insanları rahatsız edebileceğini anlamak mantıklıdır, ancak binlerce katılımcının olduğu güvenilir bir kurulum, hiç güvenmemekten neredeyse ayırt edilemez - ve eğer gerçekten paranoyaksanız , kurulum prosedürüne kendiniz girip katılabilirsiniz ve değerinizi kişisel olarak sildiğinizden emin olabilirsiniz.
Aktif araştırmanın diğer bir alanı da aynı hedefe ulaşmak için eşleştirmeleri ve aynı güvenilir kurulum paradigmasını kullanmayan diğer yaklaşımların kullanılmasıdır; Görmek Eli ben Sasson'un son sunumu bir alternatif için (ama dikkatli olun, matematiksel olarak en az SNARK'lar kadar karmaşıktır!)
İncelemeleri için Ariel Gabizon ve Christian Reitwiessner'a özellikle teşekkür ederiz.
- SEO Destekli İçerik ve Halkla İlişkiler Dağıtımı. Bugün Gücünüzü Artırın.
- PlatoData.Network Dikey Üretken Yapay Zeka. Kendine güç ver. Buradan Erişin.
- PlatoAiStream. Web3 Zekası. Bilgi Genişletildi. Buradan Erişin.
- PlatoESG. karbon, temiz teknoloji, Enerji, Çevre, Güneş, Atık Yönetimi. Buradan Erişin.
- PlatoSağlık. Biyoteknoloji ve Klinik Araştırmalar Zekası. Buradan Erişin.
- Blok Ofsetleri. Çevre Dengeleme Sahipliğini Modernleştirme. Buradan Erişin.
- Kaynak: Plato Veri Zekası.