Sıfır Bilgi Kanıtları: Sihir Gibi, Ama Açıklayacağım

Diyelim ki Peggy, Victor'a sırrı ifşa etmeden bir sırra sahip olduğunu kanıtlamak zorunda. Bunu, Victor'u sırrı gerçekten bildiğine ikna edecek şekilde yapabilir mi? Kimlik sistemlerinde kullanabileceğimiz en güçlü kriptografik süreçlerden birinin merkezindeki soru budur: sıfır bilgi kanıtları (ZKP'ler) .

Örneğin, Peggy'nin dijital bir sürücü belgesine sahip olduğunu ve barmen Victor'a yalnızca sürücü belgesini vermeden ve hatta ona doğum tarihini göstermeden 21 yaşın üzerinde olduğunu kanıtlamak istediğini varsayalım. ZKP'ler, Peggy'nin, Peggy'nin başka bir şey açıklamasına gerek kalmadan Victor'u ikna edecek şekilde sürücü belgesinde en az 21 yaşında olduğunu kanıtlamasına izin veriyor (yani, sıfır fazla bilgi var).

Bu sorun ilk olarak 1980'lerde MIT araştırmacıları Shafi Goldwasser, Silvio Micali ve Charles Rackoff tarafından bilgi sızıntısıyla mücadele etmenin bir yolu olarak araştırıldı. Amaç, doğrulayıcı Victor'un kanıtlayıcı Peggy hakkında öğrenebileceği ekstra bilgi miktarını azaltmaktır.

ZKP'lerin nasıl çalıştığını anlamanın bir yolu, ilk olarak kriptograflar Quisquater, Guillou ve Berson1 tarafından yayınlanan Alibaba Mağarası'nın hikayesidir. Aşağıdaki şemada bir örnek verilmektedir.

Alibaba Mağarası, girişe bağlanan tek bir geçidi ayıran A ve B etiketli iki geçitten oluşuyor. Peggy, A ve B'yi birbirine bağlayan kapının kilidini açmasına olanak tanıyan gizli bir koda sahiptir. Victor, kodu satın almak ister ancak Peggy'nin bunu bildiğinden emin olana kadar ödeme yapmaz. Peggy, bedelini ödeyene kadar Victor'la paylaşmayacak.

Peggy'nin kodu bildiğini kanıtlama algoritması şu şekilde ilerliyor:

• Peggy içeri girip geçitlerden birini seçerken Victor mağaranın dışında duruyor. Victor'un Peggy'nin hangi yolu izlediğini görmesine izin verilmiyor.
• Victor mağaraya girer ve rastgele "A" veya "B" diye seslenir.
• Peggy doğru geçitten çıkıyor çünkü girerken hangi seçimi yaparsa yapsın kapının kilidini kolayca açabiliyor.
• Elbette Peggy şanslı olabilir ve doğru tahmin edebilirdi, bu yüzden Peggy ve Victor deneyi birçok kez tekrarladılar.

Eğer Peggy, Victor'un seçtiği geçitten her zaman geri dönebiliyorsa, Peggy'nin kodu gerçekten bilme ihtimali giderek artıyor. 20 denemeden sonra Peggy'nin Victor'un hangi harfi arayacağını tahmin etmesi ihtimali milyonda birden az. Bu, Peggy'nin sırrı bildiğine dair olasılıksal bir kanıt teşkil ediyor.

Bu algoritma Peggy'nin Victor'u kodu bildiğine ikna etmesine olanak sağlamakla kalmıyor, aynı zamanda bunu Victor'un Peggy'nin kodu bildiğine kimseyi ikna edememesini sağlayacak şekilde yapıyor. Victor'un tüm işlemi kaydettiğini varsayalım. Bir gözlemcinin gördüğü tek şey Victor'un mektupları seslendirmesi ve Peggy'nin sağ tünelden çıkmasıdır. Gözlemci, Victor ve Peggy'nin, gözlemcileri kandırmak için önceden bir dizi mektup üzerinde anlaşmaya varmadıklarından emin olamaz.

Dolayısıyla Peggy, Victor'un sırrı bildiğini inkar edemezken, diğer üçüncü şahısların sırrı bildiğini inkar edebilir. Bu, Victor'a kanıtladığı her şeyin aralarında kalmasını ve Victor'un bunu en azından Peggy'den geldiğini kanıtlayacak kriptografik bir şekilde sızdırmamasını sağlar. Peggy hem sırrının hem de bunu bildiği gerçeğinin kontrolünü elinde tutuyor.

"Sıfır bilgi" derken ve Victor'un söz konusu önermenin ötesinde hiçbir şey öğrenmediğinden bahsettiğimizde bu tamamen doğru değil. Alibaba'nın mağarasında Peggy, sıfır bilgiyle sırrı bildiğini kanıtlar. Ancak Victor'un Peggy hakkında öğrendiği ve ZKP'lerin hiçbir şey yapamayacağı başka birçok şey var. Örneğin Victor, Peggy'nin kendisini duyabildiğini, onun dilini konuştuğunu, yürüdüğünü ve işbirliği yaptığını biliyor. Ayrıca mağara hakkında, kapının kilidini açmanın yaklaşık ne kadar süreceği gibi şeyler de öğrenebilir. Peggy, Victor hakkında da benzer şeyler öğrenir. Yani gerçek şu ki, kanıt tamamen sıfır bilgi değil, yaklaşık olarak sıfır bilgidir.

ZKP Sistemleri

Alibaba Mağarası örneği , bilginin sıfır bilgi kanıtı olarak adlandırılan ZKP'lerin çok özel bir kullanımıdır. Peggy bildiğini (veya bir şeye sahip olduğunu) kanıtlıyor. Daha genel olarak Peggy, Victor'a pek çok gerçeği kanıtlamak isteyebilir. Bunlar önerme cümlelerini ve hatta değerleri içerebilir. ZKP'ler de bunu yapabilir.

Sıfır bilgiyle önermeleri nasıl kanıtlayabileceğimizi anlamak için, bazen Sosyalist Milyoner Sorunu olarak adlandırılan farklı bir örneği düşünün. Peggy ve Victor'un kendilerine adil bir ücret ödenip ödenmediğini bilmek istediklerini varsayalım. Özellikle, kendilerine aynı miktarda ödeme yapılıp yapılmadığını bilmek istiyorlar ancak belirli saatlik ücretlerini birbirlerine, hatta güvenilir bir üçüncü tarafa açıklamak istemiyorlar. Bu örnekte Peggy bir sır bildiğini kanıtlamıyor, bunun yerine bir eşitlik (veya eşitsizlik) önermesini kanıtlıyor.

Basit olması açısından Peggy ve Victor'a saat başına 10$, 20$, 30$ veya 40$'dan biri ödendiğini varsayalım.

Algoritma şu şekilde çalışır:

• Peggy dört kilit kutusu satın alır ve bunları 10 $, 20 $, 30 $ ve 40 $ olarak etiketler.
• Üzerinde maaşının yazılı olduğu kutu dışındaki her kutunun anahtarını atıyor.
• Peggy, tüm kilitli kutuları Victor'a verir ve Victor, kutunun üst kısmında maaşının yazılı olduğu yuvaya "+" işaretli bir kağıt parçası koyar. Diğer tüm kutulara "-" içeren bir fiş koyuyor.
• Victor kutuları, üzerinde maaşının bulunduğu kutuyu özel olarak açmak için anahtarını kullanan Peggy'ye geri verir.
• Eğer "+" bulursa aynı miktarı kazanırlar. Aksi takdirde farklı bir miktar kazanırlar. Bunu Victor'a gerçeği kanıtlamak için kullanabilir.

Buna habersiz transfer denir ve VictorSalary = PeggySalary önermesinin sıfır bilgiyle (yani başka herhangi bir bilgi vermeden) doğru veya yanlış olduğunu kanıtlar.

Bunun işe yaraması için Peggy ve Victor'un diğerinin yaklaşacağına güvenmeleri ve gerçek maaşlarını belirtmeleri gerekir. Victor'un Peggy'nin diğer üç anahtarı atacağına güvenmesi gerekiyor. Peggy, Victor'un kutulara yalnızca üzerinde "+" bulunan tek bir fiş koyacağına güvenmelidir.

Tıpkı dijital sertifikaların, yalnızca kendi kendine verilen sertifikalarla mümkün olanın ötesinde güven oluşturmak için bir PKI'ya ihtiyaç duyması gibi, ZKP'ler de Peggy ve Victor'un yalnızca onların hakkında söylediklerinden değil, başkalarının kendileri hakkında söylediklerinden de gerçekleri kanıtlamasına olanak tanıyan bir sistemde daha güçlüdür. kendileri. Örneğin, Peggy ve Victor'un maaşlarını kendileri beyan etmeleri yerine, iddialarını yaparken İK departmanından gelen imzalı bir belgeye güvenebileceklerini ve böylece her ikisinin de diğerinin gerçek maaşını belirttiğini bilebileceğini varsayalım. Doğrulanabilir Kimlik Bilgileri, birçok farklı gerçeği tek başına veya birlikte kanıtlamak için ZKP'leri yönteme ve verilere güven verecek şekilde kullanmak için bir sistem sağlar.

Etkileşimli Olmayan ZKP'ler

Önceki örneklerde Peggy, bir dizi etkileşim aracılığıyla Victor'a bazı şeyleri kanıtlayabilmişti. ZKP'lerin pratik olabilmesi için kanıtlayıcı ile doğrulayıcı arasındaki etkileşimlerin minimum düzeyde olması gerekir. Neyse ki SNARK adı verilen bir teknik, etkileşimli olmayan sıfır bilgi kanıtlarına olanak tanıyor.

SNARK'lar aşağıdaki özelliklere sahiptir (adlarını buradan alırlar):

• Kısa ve öz: Mesajların boyutları, gerçek kanıtın uzunluğuna kıyasla küçüktür.
• Etkileşimli değil : bazı kurulumlar dışında, kanıtlayıcı doğrulayıcıya yalnızca bir mesaj gönderir.
• Argümanlar: Bu aslında bir şeyin doğru olduğuna dair bir argümandır, matematiksel olarak anladığımız şekliyle bir kanıt değildir. Spesifik olarak, kanıtlayıcı yeterli hesaplama gücü verildiğinde teorik olarak yanlış ifadeleri kanıtlayabilir. Yani SNARK'lar "mükemmel ses" yerine "hesaplama açısından ses"tir.
• Bilgi: Kanıtlayan kişi söz konusu gerçeği bilir.

Bu süreç sırasında doğrulayıcının kanıtlanan gerçeklerden başka hiçbir şey öğrenmediğini belirtmek için genellikle ön tarafta "zk" (sıfır bilgi için) işaretinin işaretlendiğini göreceksiniz.

zkSNARK'ların altında yatan matematik, yüksek dereceli polinomlar üzerinde homomorfik hesaplamayı içerir. Ancak zkSNARK'ların nasıl çalıştığını, onların sağlam olmasını sağlayan temel matematiği bilmeden de anlayabiliriz. Matematikle ilgili daha fazla ayrıntı istiyorsanız, Christian Reitwiessner'ın "zkSNARKs in a Özet" kitabını öneririm.

Basit bir örnek olarak, Victor'a belirli bir değere sahip bir sha256 hash'inin ( H verildiğini varsayalım. Peggy, Victor'a s açıklamadan sha265(s) == H olacak şekilde bir s bildiğini kanıtlamak istiyor. İlişkiyi yakalayan bir C fonksiyonu tanımlayabiliriz:

 C(x, w) = ( sha256(w) == x )

Yani, C(H, s) == true iken w diğer değerleri false döndürecektir.

Bir zkSNARK'ın hesaplanması üç işlevi gerektirir G , P ve V G , lambda adı verilen gizli bir parametreyi ve C fonksiyonunu alan ve iki genel anahtar, kanıtlama anahtarı pk ve doğrulama anahtarı vk üreten anahtar oluşturucudur. Belirli bir C işlevi için yalnızca bir kez oluşturulmaları gerekir. lambda parametresine bir daha ihtiyaç duyulmaması ve bu parametreye sahip olan herkesin sahte deliller üretebilmesi nedeniyle bu adımdan sonra yok edilmesi gerekmektedir.

Kanıtlama işlevi P , girdi olarak pk kanıtlama anahtarını, genel girdi x ve özel (gizli) tanığı w alır. P(pk,x,w) komutunu çalıştırmanın sonucu, kanıtlayıcının w için C karşılayan bir değer bildiğinin bir kanıtıdır, prf .

Doğrulayıcı işlevi V prf prf doğruysa doğru, aksi takdirde yanlış olan V(vk, x, prf) yi hesaplar.

Peggy ve Victor'a dönersek Victor, Peggy'nin kanıtlamasını istediği şeyi temsil eden bir C fonksiyonunu seçer, rastgele bir lambda sayısı oluşturur ve kanıtlama ve doğrulama anahtarlarını oluşturmak için G çalıştırır:

 (pk, vk) = G(C, lambda)

Peggy lambda değerini öğrenmemeli. Victor, C , pk ve vk Peggy ile paylaşıyor.

Peggy x = H için C sağlayan s değerini bildiğini kanıtlamak istiyor. Bu değerleri girdi olarak kullanarak P kanıtlama fonksiyonunu çalıştırır:

 prf = P(pk, H, s)

Peggy, doğrulama işlevini yürüten Victor'a kanıt prf sunar:

 V(vk, H, prf)

Sonuç doğruysa, Victor Peggy'nin s değerini bildiğinden emin olabilir.

Bu örnekte yaptığımız gibi C fonksiyonunun bir karma ile sınırlı olmasına gerek yoktur. Temel matematiğin sınırları dahilinde, C oldukça karmaşık olabilir ve Victor'un Peggy'nin kanıtlamasını istediği sayıda değeri aynı anda içerebilir.

Bu makale O'Reilly Media tarafından yayınlanan Learning Digital Identity kitabımdan bir alıntıdır.

Notlar

1. Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). Sıfır Bilgi Protokollerini Çocuklarınıza Nasıl Açıklayabilirsiniz (PDF). Kriptolojideki Gelişmeler – CRYPTO '89: Bildiriler. Bilgisayar Bilimleri Ders Notları. 435. s. 628–631. doi:10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.