Thread by @OrientusPrime

0)Konumuz %100 ve %99.9999... olasılık arasındaki devasa fark.

1)Bir sistemde %100 kesinlik sağlayan bir garanti yerine %99.9999... garantiyi hedeflemek yazılan algoritmada verimlilik anlamında devasa farklara sebep olabilir. Bu probabilistic garantilerin gücünden kaynaklanır.

2)Bu farkı cryptoda kullanan 2 güzel örnek

A)Avalanche Consensus
B)Zero Knowledge'lar

Peki bu aradaki ufacık fark pratikte neden devasa ölçek farkı oluşturuyor?

3)Probabilistic Proof'larda Sample alma kavramı vardır. Örneğin saymanız gereken 10 milyon oy ve belirlemeniz gereken bir kazanan var. 100 000 oyu rastgele seçtiniz ve saydınız. Kazananı belirlemek için diğer oyları da saymak size ne kadar yüzde kesinlik kazandıracak?

4)Tek bir Sample'da dahi ciddi miktarda fikriniz oluştu. Bu Sample'ları ise defalarca almaya devam ettiğinizde hata olasılığınız Exponential şekilde azalacaktır.

Hata ihtimalini 1/2^n gibi düşünebilirsiniz.

5)Avalanche Consensus'unu düşünelim. Her Node rastgele görüşünü almak istediği Node'ları belirliyor ve görüş istiyor. Bu işlemi her tekrarladığında eminlik seviyesi ciddi oranda artıyor.

6)Buna ek olarak Node'ların aldıkları Sample'ların diğer Node'ların eminliğine de katkıda bulunması Kar topu etkisi oluşturuyor, ismi de burdan geliyor. Kar topu büyüyüp Avalanche'a dönüşüyor.

Bu Probabilistic yapı ise Algoritma'nın ölçeklenmesine devasa katkıda bulunuyor.

7)Burda İnteraktif bir yapı da var aslında. Node'lar Random şekilde fikir isteyecekleri Node'ları seçiyor. Seçtikleri Node'lar da bu taleplere yanıt veriyor. Rastgele yanıt iste - yanıt al interaksiyonlarının farklı şekilleri de var. Bunlardan biri de bilgi ispatları.

8)Ben 10 000 kişilik bir okuldaki herkesin ismini bildiğimi iddia ediyorum. Bunu doğrulamak isteyen kişi bana rastgele kişilerin isimlerini soruyor ben de isimlerini bilerek bilgimi kanıtlıyorum. Kaç kişi de ikna olur ve bu neden 10 000 değil :)

9)Bu tarz ispatlara Interactive Proof denir. Bu Interactive Proof'larda kanıtlayan tarafın iddia ettiği şeyin doğruluğunu ispatlarken başka hiçbir bilgi açığa çıkarmamasına da Zero Knowledge deniyor, ardına henüz SNARK eklemedim ama dikkat ederseniz.

10)Bu tarz bir Proof yapısında karşıya bilgi sızdırmadan ispat yapabilmek için yapının bir Computational Complexity'ye dayanması gerekir. Mevcut bilgisayar mimarilerinin yetenekleri baz alınarak oluşturulan modellere Standard Model denir.

11)Bu modelde Kriptografide işimize yarayan bazı sınırlamalar bulunur. Discrete logarithm, factorization veya Eliptic Curve hesaplamaları gibi. Quantum Computing Standard Model'e uymadığı için bu varsayımlardan bazılarını bozuyor fakat hepsini değil.

12)ZK Interactive Proof sistemleri 80'lerde ortaya çıkmıştı. Bunların sıkıntısı ise ispat sırasında ortak bir randomlukta karar kılınamadığı için ispatlamak istediğin kişiyle etkileşime geçmen gerekiyor. Bir şeyi büyük bir topluluğa ispatlamak da imkansız hale geliyor.

13)Bu sebeple doğrulanabilir, manipüle edilemeyen ve herkesin güvenebileceği bir Random Oracle eklenebilirse bu Interactive olma durumundan kurtulunabilir. Zero Knowledge Interactive Proof'ların 3 yazarından olan Silvio Micali'nin bu alana ilgisi de bundan.

14)Silvio Micali sonrasında Algo"rand" deki Random'luğun da temelini oluşturacak doğrulanabilir Random'luk yapıları üzerinde çalıştı. VRF'nin de mucidi bu sebeple. Silvio bu Random'luğa sahip olduğumuz taktirde günümüzün NonInteractive yapılarına ulaşabileceğimizi 90'larda yazdı.

15)Bunun doğru şekilde nasıl yapılabileceği ise 2010'lu yıllara kadar gösterilemedi. Sonrasında farklı şekillerde de çözüldü ama yeterince detaya girdim bence.

16)Toparlarsak ZK-Snark'ların 3 temel yapısı bulunuyor
A)Yapısının küçük olmasını sağlayan Random Sampling yapısı
B)Güvenilir Randomluk
C)ZK olmak için dayandığı bir Computational Complexity

17)Non-Interactive'den kasıt da Sampling'deki ilişkinin tamamen ortadan kalkması demek değildir. Bu Sampling gerçekleşirken doğrulamayı yapanı dışardan aktif olarak yönlendirmemizin artık gerekmediğini anlatır. Sistem onu zaten doğru şekilde yönlendiriyor demektir.

18)Bu olayın nasıl uç noktalara vardığını farklı Zero Knowledge sistemleri anlatırken konuşuyoruz da burda dikkat çekmek istediğim taraf daha çok başladığı nokta.

19)Her şey 1:1 algoritmic karmaşıklığa sahip algoritmalara yol açan %100 kesinlikteki doğrulamalardan rastgele örnek toplayan ihtimale dayalı doğrulamaya geçmekle başladı.

20)Mesele 0.99:1 olduğu andan itibaren ise bir şeyi doğrulamak için oluşturduğun kanıt doğruladığın şeyden küçük hale gelmiş oldu. Bu neden bu kadar ölümcül bir fark oluşturuyor?

21)Çünkü oluşturduğun kanıtları da kendilerinden küçük başka bir kanıt ile doğrulayabiliyorsun. Yine benzer bir kar topu efekti oluştu.

1^n yapısında n ne olursa olsun sonuç 1'dir. Peki 0.9999^n yapısında n büyüdükçe sonuç ne olur?

22)
1 ve 0
Olmak ya da Olmamak
İşte %100 ile %99.99... arasındaki fark bu kadar büyüktür.