Sıfır Bilgi Kanıtları
Sıfır bilgi kanıtı, bir kanıtlayıcının, bir doğrulayıcıyı bir ifadenin doğru olduğuna, doğruluğu gerçeğinden başka hiçbir şeyi açığa çıkarmadan ikna etmesini sağlayan, geniş kriptografik kullanımlara sahip, sezgisel olmayan bir yetenektir.
Tanım
Sıfır bilgi kanıtı, bir kanıtlayıcının bir doğrulayıcıyı bir ifadenin doğru olduğuna, doğrulayıcının ifadenin geçerliliğinden başka hiçbir şey öğrenmediği şekilde ikna ettiği, tanık (witness) olmaksızın doğrulayıcının görünümünü yeniden üreten bir simülatör tarafından resmileştirilen etkileşimli (veya etkileşimli olmayan) bir protokoldür.
Kapsam
Bu kapsam, etkileşimli kanıt sistemlerini ve bunların sıfır bilgi varyantlarını ele almaktadır: tamlık, geçerlilik (soundness) ve sıfır bilginin tanımlayıcı özellikleri; simülasyon paradigması; bilgi kanıtları; Fiat-Shamir dönüşümünün etkileşimli olmayan kanıtlara uygulanması; ve modern özlü sistemler (zk-SNARK'lar ve zk-STARK'lar). Kimlik doğrulama ve gizliliği koruyan doğrulama uygulamalarına değinilmektedir. Etkileşimli kanıtların daha geniş karmaşıklık teorisi ve sıfır bilgiyi bir alt bileşen olarak kullanan protokoller (MPC) bu kapsamın dışındadır.
Temel sorular
- Bir kanıt, başka hiçbir bilgi sızdırmadan gerçeğin kesinliğini nasıl iletebilir?
- Tamlık, geçerlilik (soundness) ve sıfır bilgi özelliği her biri neyi garanti eder?
- Bir simülatörün varlığı, 'hiçbir şey öğrenmeme' durumunu nasıl yakalar?
- Etkileşimli kanıtlar, Fiat-Shamir dönüşümü aracılığıyla nasıl etkileşimli olmayan hale getirilir?
- Özlü kanıtlar (SNARK'lar, STARK'lar) sıfır bilgiyi büyük ölçekte nasıl pratik hale getirir?
Anahtar kavramlar
- etkileşimli kanıt sistemi
- tamlık ve geçerlilik (soundness)
- sıfır bilgi özelliği
- simülatör
- bilgi kanıtı
- Fiat-Shamir dönüşümü
- etkileşimli olmayan sıfır bilgi (NIZK)
- zk-SNARK'lar ve zk-STARK'lar
- taahhüt şemaları (commitment schemes)
Temel kuramlar
- Simülasyon paradigması
- Bir protokol, her doğrulayıcı için, gizli tanığa (secret witness) erişim olmaksızın, gerçek bir etkileşimden ayırt edilemez bir transkript üreten verimli bir simülatör varsa sıfır bilgidir — bu, doğrulayıcının hiçbir şey öğrenmediği fikrini resmileştirmektedir.
- Tamlık, geçerlilik (soundness) ve bilgi kanıtları
- Etkileşimli bir kanıt, dürüst kanıtlayıcılar dürüst doğrulayıcıları ikna ederse tamdır ve yanlış ifadeler yüksek olasılıkla reddedilirse geçerlidir (sound); bir bilgi kanıtı ise ek olarak, bir bilgi çıkarıcı (knowledge extractor) aracılığıyla, kanıtlayıcının tanığı (witness) gerçekten elinde bulundurduğunu garanti etmektedir.
Mekanizmalar
Kanonik üç-hamleli (sigma) bir protokolde, kanıtlayıcı bir taahhüt (commitment) gönderir, doğrulayıcı rastgele bir meydan okuma (challenge) gönderir ve kanıtlayıcı yanıt verir; geçerlilik (soundness), kanıtlayıcının tanık (witness) olmaksızın tüm meydan okumalara yanıt verememesinden kaynaklanmakta, sıfır bilgi ise simülatörün, meydan okumayı (challenge) önce seçerek transkriptleri taklit etme yeteneğinden gelmektedir. Fiat-Shamir dönüşümü, doğrulayıcının meydan okumasını taahhüdün (commitment) bir hash'i ile değiştirerek etkileşimli olmayan bir kanıt sağlamaktadır. Özlü sistemler, kısa ve hızlı doğrulanabilir kanıtlar üretmek için polinom taahhütleri (polynomial commitments) ve aritmetik devreler kullanmaktadır.
Klinik önem
Sıfır bilgi kanıtları, dağıtılmış sistemlerde gizliliği ve ölçeklenebilirliği sağlamaktadır: gizliliği koruyan kripto paralar (Zcash), geçerliliği kanıtlarken işlem detaylarını gizlemekte, blok zinciri rollup'ları, hesaplamayı sıkıştırmak için özlü kanıtlar kullanmakta, anonim kimlik bilgileri ve dijital kimlik sistemleri, nitelikleri (yaş, vatandaşlık) ifşa etmeden kanıtlamakta ve kimlik doğrulama şemaları, bir sırrın sahipliğini ifşa etmeden kanıtlamaktadır.
Kanıt ve kılavuzlar
Sıfır bilgi yapıları, aktif bir standardizasyon alanıdır (ZKProof topluluk standartları çalışması). Üretim sistemleri, iyi incelenmiş SNARK ve STARK kütüphanelerine dayanmaktadır; ancak güvenilir bir kurulum gerektiren SNARK'lar dikkatli tören tasarımı gerektirmekte, STARK'lar ise daha büyük kanıtlar pahasına güvenilir kurulumdan kaçınmaktadır. Geçerlilik (soundness), kriptografik varsayımlara ve Fiat-Shamir için rastgele-oracle modeline bağlıdır.
Tarihçe
Goldwasser, Micali ve Rackoff, etkileşimli kanıtları ve sıfır bilgiyi 1985 yılında tanıttı, dergi versiyonu ise 1989'da yayımlandı. Goldreich, Micali ve Wigderson, her NP ifadesinin bir sıfır bilgi kanıtına sahip olduğunu gösterdi (1987). Fiat-Shamir dönüşümü (1986), kanıtları etkileşimli olmayan hale getirdi. 2010'lar, özlü etkileşimli olmayan argümanları (zk-SNARK'lar) ve şeffaf STARK'ları getirerek, sıfır bilgiyi teoriden blok zinciri ve gizlilik ürünlerine taşıdı.
Öne çıkan isimler
- Shafi Goldwasser
- Silvio Micali
- Charles Rackoff
- Oded Goldreich
- Amos Fiat
- Adi Shamir
İlgili konular
Temel eserler
- goldwasser1989
- katz2020
- goldreich2001
Sıkça sorulan sorular
- Sıfır bilgi için basit bir sezgi nedir?
- Görsel olarak birbirine benzeyen iki nesneyi, gizli bir tarafın hangisini değiştirdiğini tekrar tekrar belirleyerek ayırt edebildiğinizi kanıtladığınızı hayal edin: her doğru yanıt, onları ayırt edebileceğinize dair güveni artırır, ancak doğrulayıcı asla nasıl olduğunu öğrenmez. Bir meydan okuma-yanıtı birçok kez tekrarlamak, hiçbir sırrı açığa çıkarmadan hile yapmayı astronomik olarak imkansız hale getirir.
- Sıfır bilgi kanıtları etkileşim gerektirir mi?
- Orijinal tanım etkileşimlidir, ancak Fiat-Shamir dönüşümü ve özel etkileşimli olmayan yapılar (NIZK'ler, SNARK'lar, STARK'lar), herkesin etkileşimde bulunmadan doğrulayabileceği tek bir kanıt dizisi üretir; bu da onları blok zincirlerinde kullanılabilir kılmaktadır.