ZKP Sezgisi: Ali Baba Mağarası

Sıfır Bilgi İspatı (ZKP), ispatlayan tarafın bir sırrı bildiğine (veya bir ifadenin doğru olduğuna), sırrın kendisini açıklamadan doğrulayan tarafı ikna etmesini sağlar. Üç özelliği vardır: Tamlık, Sağlamlık ve Sıfır Bilgi.

İspatlayan taraf sırrı biliyorsa doğrulayan tarafı her zaman ikna edebilir. Protokolü izleyen dürüst bir ispatlayan taraf, 1 olasılıkla (veya ezici bir olasılıkla) başarılı olur. Doğrulayan taraf geçerli bir ispatı reddetmez.

Hile yapan bir ispatlayan taraf (sırrı bilmeyen biri), yalnızca ihmal edilebilir bir olasılıkla doğrulayan tarafı ikna edebilir. Her etkileşim turu hile yapma olasılığını azaltır — k turdan sonra hile yapan tarafın başarı olasılığı en fazla 2^{-k} olur.

Doğrulayan taraf, ifadenin doğru olduğu gerçeğinin ötesinde hiçbir şey öğrenmez. Biçimsel olarak: sırrı bilmeden, gerçek bir ispatlayan-doğrulayan etkileşiminden ayırt edilemeyen bir iletişim kaydı üreten bir simülatör vardır. Doğrulayan taraf hiçbir ek bilgi edinmez.

Bir mağarada, ortasında sihirli bir kapı bulunan halka biçimli bir geçit vardır. İspatlayan taraf (Alice), parolayı bildiğini iddia eder. Doğrulayan taraf (Bob) dışarıda bekler. Alice içeri girip sola veya sağa gider. Bob, hangi taraftan çıkması gerektiğini seslenerek söyler. Alice parolayı biliyorsa her zaman doğru taraftan çıkar. Tur başına hile yapma olasılığı: 1/2.

20 turdan sonra hile yapan tarafın başarı olasılığı 2^{-20} ≈ milyonda 1 olur. Parolayı bilen Alice her seferinde başarılı olur. Bob parolayı hiçbir zaman öğrenmez — yalnızca Alice'in istenen taraftan çıktığını görür. Bu, sıfır bilgidir.

Etkileşimli ZKP'ler, ispatlayan taraf ile doğrulayan taraf arasında karşılıklı iletişim gerektirir. Etkileşimsiz ZKP'ler (NIZK'ler), Fiat-Shamir dönüşümünü kullanır: doğrulayan tarafın rastgele meydan okuması, taahhüdün özet değeriyle değiştirilir (özet = rastgele kâhin). Herkesin doğrulayabileceği tek bir ispat dizesi üretilir.

Bir ZKP, ispatlayan tarafın stratejisi sırrı çıkarabileceğini ima ediyorsa Bilgi İspatıdır (PoK). Bu, yalnızca bir ifadenin doğru olduğunu ispatlamaktan daha güçlüdür. ECDSA ve Schnorr imzaları, özel anahtarı bildiğine dair etkileşimsiz bilgi ispatlarıdır.

Parolayı göndermeden parola doğrulama. Doğum tarihini açıklamadan yaş doğrulama. Maaşı açıklamadan maaşınızın belirli bir aralıkta olduğunu kanıtlayan aralık ispatları. Blok zinciri: işlemi açığa çıkarmadan geçerli bir işlemi bildiğinizi kanıtlama.

Kusursuz sıfır bilgi: simülatörün çıktısı gerçek etkileşim kaydıyla aynıdır. İstatistiksel ZK: yalnızca ihmal edilebilir bir olasılıkla ayırt edilemez. Hesaplamalı ZK: polinom zamanda çalışan doğrulayıcılar için ayırt edilemez. Daha zayıf güvenceler = daha verimli kanıtlar.

Mağara, 3 hamleli bir protokoldür: taahhüt → meydan okuma → yanıt. Resmî olarak Sigma protokolü adı verilir. Uygulamadaki ZKP'lerin çoğu (Schnorr, Pedersen, Fiat-Shamir) Sigma protokolleridir veya bunların bileşimlerinden oluşur. Adı, ileti akışı şemasının Σ biçiminden gelir.

ZKP'ler, bir sırrı açığa çıkarmadan o sırrın bilindiğini kanıtlar. Üç özellik: tamlık, sağlamlık, sıfır bilgi. Ali Baba mağarası, etkileşimli ZKP'yi gösterir. Sıradaki konu: Sigma protokolleri ve Schnorr kimlik kanıtlama.