Merhaba. Eğer kıvırabilirsek bu bir yazı dizisi olacak. PLONK adı verilen Snark şeması üzerinden şöyle bir geçeceğiz ve illüstrasyonlar ve minik program scriptlerini işin içine sokarak sezgisel olarak konuları kavramaya çalışacağız.
Çerçeveyi her ne kadar PLONK şeklinde çizdiysek de değineceğimiz konu seti biraz geniş. Bu macerada kah elliptic curve kriptografi, imza şemaları, gruplar, polinomlar gibi matematiksel objeleri anlamaya ve kullanmaya çalışacağız, kah rollup’lar semafor’ler maci’ler tornado cash’ler gibi Snark teknikleri sayesinde gerçekleştirilen uygulamaları değerlendireceğiz idrak etmeye çalışacağız, kah dedikodu yapıp onu bunu kendi aklımız sıra çekiştireceğiz.
Bir disclaimer yapayım ben matematikçi değilim. Bu teknolojilerle uğraşan bir bilgisayar mühendisiyim. Matematik üreticisi değil program üreticisiyim. Haliyle bu dizide ki çoğu konuyu bir matematikçi olarak değil de matematiksel araç gereçleri az çok kavramış bir şekilde kullanabilen birisinin gözünden ele alınacak. Hatta belli ki anlatmaya çalışırken ben de bir şekilde bir şeyleri daha iyi kavrayacağım unuttuğum şeyleri hatırlayacağım bir şeyleri tam anlamadığımı göreceğim. Hem sana hem bana gibi.
Okuyucunun planladığımız bu dizide çok fazla matematik veya kodlama bilmesine de gerek yok diye düşünüyorum. Bununla birlikte hiç matematikle hiç kodlamayla bu iş yürümez arkadaşlar elimizi taşın altına koyacağız. Yine de matematikse burda en fazla toplama çarpma yapacağız kodlama ise burda en fazla python script run edeceğiz. Bu kadar.
Öncelikle biraz dedikodu yapalım sonrada doğrulanabilirlik kavramı neye benzer biraz illüstre etmeye çalışalım. Snark konusunu etraflıca kavramaya kalkarsanız denildiği gibi işin moon math olduğu doğru. Bizim bu dizideki hedefimiz bu tekniğin bileşenlerini tanımak ve nasıl kullanıldıklarını kavramak olacak. Biraz derinleşeceğiz fakat kuyunun dibine yolculuk yapmayacağız. Diyelim ki siz bir bilgisayar programcısısınız cpu’nun compiler’ın tam olarak nasıl çalıştığını eğer doğrudan o alanda iş üretemiyorsanız çok bilmenize gerek kalmaz ve çoğu zaman ne işe yaradıklarını bilmeniz yeterli olur ve o yeterlilikle bir çok hayal kurabilirsiniz. Burada da benzer. Bu dizide tanıyacağımız komponentleri hissetmeye çalışacağız aynı zamanda anlaşılır olmak kaydıyla becerebildiğim kadar da derinleşmeye çalışacağım. Ancak önemli olan komponentleri kutular olarak görüp ne işe yaradıklarını anlamak ve kutuları cebe atmak. Genç bir snark geliştiricisine yol açmaya çalışacağız kriptografi diyince erinen arkadaşları engaje etmeye çalışacağız. Amacımız bu domende iş yapmak isteyen arkadaşlara bir miktar konfor, bir miktar ekosistem bilgisi sağlamaktır.
Bir yandan matematiksel konseptleri öğrenirken basit python scriptleri ile bu öğrendiğimiz şeyleri deneysel olarak pekiştirelim diyorum. Mesela 1 2 ay sonra circom ile halo2 ile cairo ile belki devre tasarlamaya cesaret eden okuyucular çıksın ortaya diyorum. Daha ileri gidip ha yeni bi hash function çıkmış dur şunu bir implement edelim diyecek cesur okuyucular çıksın ortaya diyorum. Ya bu meseleyi ben kavradım ben bu oyuncaklarla falanca derde derman buldum galiba diyen girişimciler çıksın diliyorum.
Şimdi bir tur zk ekosisteminde ne tür karakterler var acaba diye minik bir göz atalım ki çevresel olarak da bir nebze bu ekosisteme aşinalık edinelim. Biraz dedikodu gibi biraz ısınma gibi. Burda bi kaç karakterden bahsetmek mümkün ancak bu kimseyi çerçevelemek anlamına gelmesin gayet güzel bir şekilde herhangi bir kimse aynı anda bu karakterlerin hepsine birden bile sahip olabiliyor.
🧑🎓 Akademisyenler. Genellikle matematikçiler özel olarak bilgisayar bilimcileri. Cryptography alanında kimse kafasına göre ya aklıma söyle bişey geldi güzel görünüyor sanki bu çalışır bir deneyelim bakalım şeklinde bir ürün veya bir araç ortaya koyamaz. Yapılan her işin temelleri akademik makaleler içindeki kanıtlarla desteklenmelidir. Aksi takdirde arkadaşlar açık konuşalım, güm, patlatırlar. Her zaman ve her zaman ve tekrar söylüyorum her zaman evil oyundadır ve çok güçlüdür. Cryptography ahlaksızlığa karşı eli çabuklara karşı verilen matematiksel alanda geçen bir savaş gibidir. Hatta evil veya düşman diyin bu karakterin akademide bir tanımı bile vardır: Adversary.
Yeni yayınlanan akademik bir araştırma ne kadar heyecan verici olursa olsun bu taze bir fikir henüz formal ya da informal kritiklerden olur almamışsa kimse gidip bu heyecan verici matematiksel düşünceleri riskli bir alanda kullanmak istemez. Örneğin her ne kadar Zcash ekibi yıldızlar kadrosu olsa da zcash’in ilk versiyonlarında referans aldıkları makalede yer alan bir hata double spendinge imkan sağlıyordu ve sonra bunu kahır bela düzelttiler. Biraz ilginç bir hikaye.
Akademisyenler gerek external teşviklerle gerek kendi inisiyatifleri ile sektördeki (bizim dizimizde genellikle bu sektör blockchain ile ilgili şeyler olacak) problemler üzerine çalışmaya koyulurlar. Feasible ve efficient bir demet çözümler keşfetmeye çalışırlar. Yine ilk private coin olan Zcash’den üzerinden gidelim. Ya bu bitcoin iyi güzel ama buradaki her transaction public kimin ne aldığı ne sattığı belli bu ilişkileri nasıl hususi kılabiliriz sorusu zamanında akademik bir problemdi. Ve akademi zcash teknolojisini mümkün kılacak bir sonuç üretti. Tromer’den dinleyelim.
Elbette akademi yalnızca Zcash örneğindeki gibi high level application sorunları ile uğraşmıyor modüler aritmetik içindeki bir sayının en hızlı şekilde nasil tersi bulunur gibi bir çok uygulamanın istifade edebileceği konuları da inceliyor çözüm buluyor. Pairing denilen anlaması üretmesinden daha zor olan bir konsepti keşfedip BLS Signature, Verkle Tree gibi bir çok uygulamanın/kutunun önünü açıyor. Örneğin BLS Signature denilen teknik olmasaydı Eth2 denilen şey hayal edilebilir miydi?
🤔 Kurcalayanlar. Olay akademiye kadar yürümeden sektörün sorunlarına hızlı bir şekilde var olan matematiksel araçları evirerek çevirerek çözüm bulan veya öneren arkadaşlar. Bir blockchain protokolü veya uygulaması takımında researcher diye birini görüyorsanız o arkadaş büyük ihtimalle bu işi yapmaktadır. Örneğin bu dizide ele acağımız PLONK şeması Aztec ekibinden Zac ve o vakitlerde Filecoin ve Zcash takımlarında yer alan Ariel tarafından geliştirildi. Bu iki arkadaş Kate polynomial commitment protokolünü aldı, permutation argument protokolünü aldı, Sonic paperını onlarca defa okudu ve bir keşifte bulundu. Hakeza şuanda da dank-sharding, data availibility problemleri ile de bu banttaki insanlar uğraşmakta. Kimisinin sadece lise mezunu olduğunu bilmekle beraber bu arkadaşlar bir şekilde edindikleri akademik kültür ve donanımları ile önerdikleri çözümleri hızlı bir şekilde kritik ekosistemine ulaştırırlar ve çeşitli olumlu olumsuz yanıtlar alarak fikirlerini itere ederler. Kimi zaman yosun gelir kimi zaman altın gelir.
🐲 Şamanlar. Kriptography matematikçilerin üretip sağlam olduklarına insanları ikna ettikleri kutulardan oluşur. Kutulardan ev yaparsınız, araba yaparsınız, teleskop yaparsınız. Kutular da zaten bunların yapılabilmesi için icat edilir, keşfedilir. Bu kutular bizim bağlamımızda neler olabilir bizim bağlamımızda: Hash fonksiyonları, imzalama algoritmaları vs. Derin bir matematiksel arka planı olmayıp kutuları genel olarak iyi tanıyan ve bu kutular ile gerçek dünya problemlerini çözmeye uğraşan bir karakter mevcuttur.
Bu arkadaşlar şurada şu kutular var burda bu kutular var ben bunları alsam yan yana koysam üst üste koysam bir şeyler olabilir sanki diye düşünür. Tanıdığım biri vardı onda da filan kutular vardı o oda onları getirse şeklinde juggling yapıp çözüm inşa etme arayışında olan progresif arkadaşlar. Eğer ellerinde eksik kutu varsa böyle bir kutu lazım şeklinde frontierlere haber veren arkadaşlar. Bu sıralar ethereum’u veya benzerlerini scale etmek istiyoruz değil mi böyle bir problem var? Rolluplar bu sınıftan bir davranışın eseridir. Snarklar ile Rollup geliştirme fikri 4 senedir var. Bu tekniğin optimistic teknik ile geliştirilmesi fikri 3 senedir var. A hatta baksana bitcoin de bu sınıftan fırlamış diyebilir miyiz? Proof of work var hazır. ECDSA var hazır. Merkle tree o da hazır. E değil mi o zaman ne duruyorsun :D Bazen bu sınıf akademi neyin üzerine gitmeli zeki insanlar neyi çözmeli bunları tanımlayan kişiler olabiliyor.
👷 Mühendisler. Akademik makaleleri, matematiksel kutularla meydana gelmiş düşünceleri etraflıca anlayıp bununları çeşitli araçlar ile bilgisayar aletine mümkünse en optimum şekilde anlatabilen kimseler yani mühendisler.
Buraya kadar kutu rotator karakterlerden bahsettik bi de çeşit çeşit laf cambazları olmalı bu işin içinde. Mesela şimdi ben gibi veya beni host eden arkadaşımız gibi :D Çok da laf cambazlarının üzerinde durmaya lüzum yok orta vadede progresif ve sazı eline almış bir teknik domende zaten varlıkları neglible olur. Bu kadar dedikodu da bugün yeter. Girişelim.
Bir bilgisayar programının aşağı yukarı neye benzediğini anlatmazsak bir çok arkadaşımızı kaybedebiliriz ve bir çok temelleri yanlış atabiliriz, bir çok temeli yanlış attığımızın farkına varmayabiliriz. Aşağıdaki basit örnekler ile bilgisayar programının aşağı yukarı neye benzediğini tanımlamaya canlandırmaya çalışalım. Bir program bir takım girdiler alır bu girdileri programlanan algoritmalar ile işler ve bir takım sonuçlar verir/döner/ortaya çıkartır/return eder. Kutu gibi düşünelim:
Genel anlamda
Topmala işlemi:
En büyüğünü bul işlemi:
Biraz daha karmaşık bir algoritmanın yürüdüğü örnekler verelim:
Bir programın görevi verilen [1, 7, 4, 1000, 2, 4, 100] sayılarını küçükten büyüğe sıralamak olsun almamız gereken sonuç [1, 2, 4, 4, 7, 100, 1000] olmalıdır.
Aynı girdilerle başka bir örnek program. Bu sefer tek bir sonucumuz olsun program bize bu sayıları toplasın. O zaman sonuç: 1118 olmalıdır.
Şimdi hayatımız boyunca bizi yalnız bırakmayacak kimi zaman biri kimi zaman diğeri olacağımız iki karakter: Prover ve Verifier.
Prover, yani kanıtlayıcı. Bu programı bu girdileri vererek çalıştırdım sonuç olarak bu çıktıları aldım ve işte bu da kanıtı buyur kardeşim lütfen bunları doğrula diyen parti.
Verifier, doğrulayıcı. Ver bakalım şu girdileri çıktıları ve kanıtı. Sen bu programı düzgün çalıştırmış mısın bir kontrol edelim diyen parti. İddia edilen girdi ve çıktıları doğrulayıcı programa (verifier program) girdi olarak verip Prover arkadaşın bu işi doğru yapıp yapmadığını kontrol eden partidir.
Bu minvalde aşağıdaki sürece bir göz atalım:
Güzel. Bu grafiğe geri dönmeyi unutmayalım. Snark’ları ne için kullanabiliriz biraz daha somutlaştıralım.
Snark’lar ne işe yararlar #1: Zero Knowledge
Programı çalıştıran arkadaşın, Prover’ın, bir takım girdileri doğrulayacak arkadaştan Verifier saklayabilmesini veya gizli tutabilmesini sağlar. Prover yukarıdaki toplama probleminde eğer benim elimde öyle altı tane sayı var ki ikisi bende gizli kalsın dört tanesini açık olsun bunların toplamı 1118 eder’i kanıtlamak istiyorsa biz Snark kullanırız. Eğer öyle ki Snark bu amacı kapsıyorsa işimizin adı artık ZK-Snark olabilir yani zero-knowledge eki geldi. Bu özellik cryptography’de programların kanıtlanabilir nesneler haline gelmesinden önce de aslında çok yaygın bir şekilde kullandığımız bir teknik. İmzalama tekniği üzerinden bir case study gelsin öyleyse.
Çok sıkıştırılmış bir şekilde bir bitcoin transferi için gereken matematiksel kutulara bakalım. Bülent Ayşe’ye 1 bitcoin göndermek istiyor. Ancak Ayşe’nin bir hesabı yok! Ayşe’nin bir hesap oluşturması lazım hemen appstoredan kendisine bir bitcoin wallet indiriyor ve indikten sonra hesap oluştur tuşuna basıyor. Bitcoin wallet goes mrrr:
Ayşe’ye özel private key diyeceğimiz bir anahtar üretiyor key_ayse olarak ifade edelim. Bu anahtar arkadaşlar bir sayıdır. 3 gibi 7 gibi bir sayıdır.
Bu key_ayse private key’ine karşılık gelen public key’i hesaplıyor. Hesaplıyor dedik çünkü her sayıya denk gelen yalnızca bir public key vardır. * Bu public key artık Ayşenin bitcoin adresidir diyebiliriz. Tıpkı IBAN numarası gibi. Bu adresi AYSE olarak denote edelim. * Benim IBAN numaramı bilen kredi kartımın şifresini bilemez denkleminde olduğu gibi herhangi bir bitcoin adresinden de private key hesaplanamaz. Yani fonksiyon(priv_ayse) = AYSE şeklinde bir fonksiyon varken fonksiyon(AYSE) = priv_ayse şeklinde bir fonksiyon yoktur.
Bu adımın sonucu olarak Ayşenin indirdiği uygulamada artık priv_ayse ve AYSE olarak iki tane anahtar mevcuttur.
Daha sonra Ayşe bitcoin adresini yani AYSE’yi kopyalayıp SMS ile Bülente gönderiyor. Bülent’in zaten bir bitcoin wallet’ı var telefonunda. Yani Bülent’in de private, public key çifti hazır. Yani priv_bül ve BULENT . Hatta BULENT hesabının harcayabileceği >1 bitcoin bile var şeklinde düşünelim. Bülent tıpkı havale yapacakmış gibi Ayşe’nin bitcoin adresini ve göndermek istediği miktarı UI’dan giriyor ve sonra wallet goes grrr:
Wallet yazılımı bu işlemi bitcoin standartlarında encode eder. Diyelim ki M = {AYSE,1BTC} şeklinde
Private key priv_bül ile bu M metni çarpar ve Bülentin bu niyetini matematiksel olarak ifade eden kanıtı elde eder. KANIT = M * priv_bül şeklinde. (Buradaki çarpma ifadesi 3*5 = 15 deki çarpma gibi bir işlemi değil biraz daha özel bir işlemi tanımlamaktadır)
Bu istek metni {BULENT,KANIT,{AYSE,1BTC}} şeklinde düzenlenir ve yayınlanır. Bu bir transaction!
Yayınlanması demek bu işlemi artık Verifier kanada gönderdik demektir. Geldik bu isteğin doğrulanması işine. Doğrulama bitcoin node’ları tarafından yapılır; aşina olmayanlar için bu doğrulama Ayşe ve Bülent’in dışında bir üçüncü parti tarafından gerçekleştirilir diyebiliriz. Doğrulama işlemi şu anlamı taşır:
Bu isteği yapan parti gerçekten BULENT public key’e isabet eden private key priv_büle sahip mi?
BULENT’i oluşturan private key priv_büle sahip olan kişi gerçekten {AYSE,1BTC} metnini bu private key ile çarpmış mı?
En kolay yöntem tabii ki Bülent’in kanıt yani M * priv_bül yerine direk priv_bül sayısını gönderip bak abi ben bu transaction olsun istiyorum gerçekten demesi olurdu. Ancak Bülent’in bakiyesi henüz bitmedi 50BTC daha var. Yani priv_bül sayısının açık edilmesi Bülent’e çok pahalıya patlayabilir hatta kaçmaz kesin patlar. Buhar olur 50BTC.
Verifier BULENT,KANIT ve M = {AYSE,1BTC} sayıları ile gerçekten Bülent’in priv_bül sayısına sahip olup olmadığını priv_bül sayısını bilmeden/görmeden hesaplayabiliyorsa bir bu özelliğe zero knowledge özelliği diyoruz. Yani Bülent priv_bül sayısını açık etmeden, yayınlamadan BULENT, KANIT, M = {AYSE,1BTC} sayıları o sayıyı bildiğini/gördüğünü ispatlayabilir. Ve niyetini ortaya koyabilir!
İmzalama işi farkedileceği gibi özel amaçlı bir süreçtir. Ben Prover adım BULENT bunu M niyet ediyorum bu da KANIT iseterimki bunlar Verifier’ı ede! şeklinde.
Peki ya BULENT ben 1000 kişilik X grubun bir üyesiyim ancak kim olduğumu belli etmek istemiyorum bunun yanında bu 1000 kişinin içinden 5 kişi benim hesap defterlerimi geçen ay audit etti ve olumlu yanıt döndüler bunun yanında bu 1000 kişiden 8’inin bana falanca miktar üzerinde borcu bulunuyor ayrıca bu 1000 kişi içinden CUNEYT kullanıcısı hakkında bir takım ifşalarda bulunmak istiyorum gibi komplex bir problemi kanıtlamak isterse? E cevap kolay bu problemi bir Snark devresi hali ne getirip Bülentin bir KANIT sunmasını isteyeceğiz. Eğer BULENT bildiği bir takım doğru söylemlerin ispatını kendi kimliğini ya da açığa sunmak istediği ve elinde olan bir takım veriler ile yapabiliyorsa bu sistem zero knowledge bir sistemdir.
Snark’lar ne işe yararlar #2: Computational Integrity
Snarklar yukarıda zaten biraz hissettirdiğimiz gibi bir programın verilen girdiler ve alınan çıktılar ile gerçekten düzgün bir şekilde çalıştığını doğrulayabilme yeteneğini sağlar. Yine yukarıda zk çerçevesinde değindiğimiz soruya gelelim. Bizim bu Verifier arkadaş madem öyle gerçekten bunun doğru çalışıp çalışmadığını kontrol etmek istiyor neden güzelce inputları bahsi geçen programa sokup verip çıktıları kontrol etmiyor? İsabetli ama biraz da saçma bir soru. Saçma diyebiliriz o zaman madem öyle olacaktı hiç outputları Verifier’a vermeye luzum yoktu kendisini bildiği gibi hesaplasındı? Isabetli diyebiliriz bunun başka bir yöntemi mi var? Evet var Snark’lar Verifier’in az iş yaparak çok iş yapan Prover’ın yaptığı işi gerçekten doğru bir şekilde yaptığını doğrulamasını sağlar.
Küçükten büyüğe bir dizi sayıyı sıralama işini her ne kadar modern bir bilgisayar sanki anında yapıyormuş gibi hissedilse de bu işlemin gerçekleşmesi için gerçekten bir zamana ihtiyaç vardır. Girdiyi verdik hop hop anında görüntü şeklinde değil de; verdiğimiz girdilere karşılık program derki lütfen bi t zaman bekler misin hesaplıyorum … hesapladım al buyur şeklindedir. Zaman harcanır.
Eğer yukarıda çizdiğimiz verifier program asıl programdan daha hızlı veya daha az kaynak tüketerek çalışıyorsa mesela idealde 100lerce kat daha hızlı diyelim bu teknik artık Verifier açısından daha manalı hala gelir. Hatta bakın eğer Verifier’ın harcaması gereken zaman doğrulanacak programın uzunluğu ne olursa olsun aynı kalabiliyorsa mesela bu baldır. Yani sen 10 sene çalıştırdın ben 1 saniyede doğruladım evet bu baldır.
Çok doğru bir örnek olmasa da hissetme yollarımız için sorting örneğine bir göz atalım: [1,2,4,4,7,100,1000] cevabını doğrulamak için Verifier ın yapması gereken iki şey var bir önceki eleman diğer elemandan küçük mü veya eşit mi bunu kontrol etmesi yeterli gibi görünüyor. Yani 4 ≤ 7 devam 7 ≤ 100 devam … tamam bu program doğru çalıştırılmıştır gibi. Ancak bu spesifik örnekte Verifier arkadaşımızın yapması gereken bir ciddi iş daha var o da çıktıda yer alan sayıların gerçekten girdide unique olarak yer alıp almadığını kontrol etmesi. Değil mi cevap olarak [1, 2 ,3 ,4, 5 ..] gelse yine büyük küçük eşitliği pass ederiz ancak bu sefer Prover bizi bir şekilde aldatmış olur. Minik bir denklemle ifade etmek gerekirse n eleman sayısı olmak üzere:
Şeklindeyse verifier program maliyet bağlamında anlamlıdır.
Şimdi daha isabetli bir örnek vermeye çalışalım aynı zamanda ilerleyen haftalarda değineceğimiz modüler aritmetiğe ısınma yapalım. Arkadaşlar bir a sayısının tersi 1/a şeklinde ifade edilir. Bir sayıyı tersiyle çarparsak sonuç 1 olur. a * 1/a = 1 gibi.
a * b = 1 ise b = 1 / a olmalıdır ve b = 1 / a olmalıdır.
Ancak ne yazık ki bizim konumuzda çeyrek yani 1/4 = 0.25 gibi kesirli sayılara erişimimiz olmayacak ve sürekli pozitif tam sayılar işlemler yapacağız. Bu bir yana çalıştığımız pozitif tam sayılar kümesi ardışık ancak sonsuza gitmeyen saat gibi tur atan bir yapıda olacak. Saatler değil mi dünyanın dönüşüne senkron olmaya çalışan sürekli tur atan sayılar gibi. [0, 1, 2, 3, ... 24) gibi.
Küçük bir interlude ile % yani modülüs işlemini örnekler ile tanıyalım:
Yukarıda da hissedileceği gibi modülüs işlemi sarma işlemidir; İpi çembere doladım nereye denk geldi işidir. 49 saat geçti en son saate baktığımda 12 buçuktu demek ki şimdi öğleden sonra 1 buçuk olduğunu hesaplama işidir. 14’ü 5’e böldüm kalan 4’dür işidir.
Neden öyle yaptığımızı şimdiden belirtmeden saatlerin 24 tane değilde 101 tane olduğunu düşünelim. Yani 0 dan 100 e kadar elimizde 101 tane saat yani sayı bulunsun. Probleme geldik. Problemimiz bir sayının modüler tersini bulmak. Düzgün bir şekilde ifade edelim:
a * b = 1 % p
Örneğin programımızın 7 * x = 1 % 101 problemini çözmesini x değerini bulmasını yani 7 nin tersini bulmasını istiyoruz. Lütfen x sayısını bulmayı deneyin çok zor değil. İyi derecede ufak sayılarda aritmetik pratiğiniz yoksa bir takım deneme yanılmalar yapmanız gerekecek. 3 verdim hmm 10 hmm sanki şimdi bir de şu deneyelim hmm gibi. Yani “arama problemi”. Deneyecek 100 tane sayı var.
Daha kolay bir yöntem gösterelim Fermat teoremi. Eğer modulus asal ise bizim durumumuzda 101 sayısı asaldır. Teorem:
(a ^ modulus) % modulus = a
şeklindedir. Bir sayıyı modulus sayısı kadar kendi ile çarparsam kendisine ulaşırım. Küçük sayılarda deneyin modulus 5 olsun ve girdi 4 olsun. 4*4*4*4*4 = 1024 ve 1024 % 5 = 4 gibi.
(a^101) % 101 = a
öyleyse,
a = (a * (a^100)) % 101
a = (a * 1) % 101
olmalı. Dahası:
a = (a * (a^100)) % 101
a = (a * a * (a^99)) % 101
# wtf
1/a = a^99
olmalı.
Yani arama probleminden bu işi üs alma exponent alma işine indirgemiş oluyoruz. a sayısını 99 kere kendisi ile çarpmamız lazım a nın modüler tersini bulabilmek için. 99 adet çarpma işlemi maliyeti artı bir en son modulus alma maliyeti. Bu maliyeti aklımızda tutuyoruz.
Peki peki peki Prover arkadaş size 7’nin tersi 29’dir diye sunsa, siz Verifier’lar doğrulama işlemini exponent alma işine göre ne kadar az sürede yapardınız? Epey epey daha kısa olurdu değil mi? Aslında problemi Verifier için ‘7 sayısını 29 ile çarptım sonra 101 e böldüm kalan 1 bir midir?’ sorusuna indirgeyebiliriz. O zaman açık bir maliyet denklemine yazalım:
Öteki türlü Verifier verilen 7 sayısını 100 kere kendisi ile çarpacaktı. Maliyeti sanırım 100x kıstık gibi duruyor.
Bu konunun blockchain kapsamında önemi nedir?
Merkle Tree, arkadaşlar buraya kadar gelindiyse ve daha önce çok incelemediyseniz hemen wikipediadan youtubedan açıp incelemenizi tavsiye ederim yarım saatinizi alır. Üstüne örneğin hash konusunda ve membership kanıtları konusunda gelecek haftalar için bize kolaylık sağlar. Merkle Tree kabaca kocaman bir veri setini minicik bir sayı ile temsil edebilmemizi sağlayan bir araçtır.
Blockchain bağlamında düşünelim. State dediğimiz şey bir blockchainde yer alan ne kadar hesap varsa onların balance’ını tutan smart kontractların kodlarını tutan smart kontratlarda yer alan verilerin tutan devasa bir verisetidir. State aynı zamanda bir Merkle Tree ya da benzeri bir veri yapısıdır. Yani bu kocaman veriseti minicik 32 bytelık unique bir değerle temsil edilebilir. Bugünlük bu değere suret diyelim ve suret şeklinde denote edelim. Ancak literatürde merkle root veya top hash olarak geçer. Somut olarak bu değer yine bir sayıdır aşağıdaki gibi.
Her transaction o blockchain’in State’inde bir takım verileri değiştirir. Bir transaction örneğin ETH transfer eder efendim veya smart contact ile gerçekleşen bir stable coin transfer eder. Çok çeşitli transactionlar olabilir. Dolayısı ile o minicik Merkle Tree suretinin değeri her transactionda toplu olarak her blockda değişecektir.
Elimde bir suret_n var bir verisetini temsil eden Blocklar yepyeni bir transaction listesi Transactionlara bakarım güzel imzalar atılmış mı diye Öyleyse her transaction bana ne söylemişse onu yerine getiririm Öyle ya onlar da da bizim verisetini manipule ederler Bu işin sonunda da Bizim yepyeni bir suret_(n+1) değerimiz oluşacaktır.
Şeklinde bir şiir miner tarafından yazılabilir. Yani denklem miner açısından basitçe şu. eski_suret ile yeni gelen transactionları işledim ve yeni bir yeni_suret değeri buldum! Biraz formülize edelim:
Sonra miner arkadaş yeni_transaction_listesi ve aday_yeni_suret’i bakın bu bir blocktur diye yayınlar. Miner olmayıp o bloğu kabul etmeye karar verecekler taraflar için ise denklem şu olmalı. Ben yani Verifier der ki Prover ile aynı işi bir yapayım bakalım bu yeni_transaction_list’i işleyince bu minerin söylediği yere aday_yeni_suret’e mi geliyoruz?
Farkedileceği gibi block işleme işinde Verifier kanadı, doğrulama işi için Prover yani miner kanadı ile işlemleri aşağı yukarı yapmak zorunda.
Rolluplar Veirifer kanadın yükünü minimize etmeyi amaçlar. Prover der ki: Al kardeş böyle böyle transactionlar var ben bu doğrulama yani yeni_suret bulma işini güzel bir şekilde icra ettim işte bu da KANIT hiç bu işi tekrar yapmaya girişme KANIT seni ikna etsin:
Eğer arkadaşlar bir transaction listesinin güzelce işlendiğini Snark ile doğrulama işlemi yani verify_block işlemi o blockun process_block ile tekrar işleyip önerilen sonuçla mukayese işleminden daha az kaynak tüketiyorsa genel olarak bu işe rollup diyebiliriz.
Burada noktalıyoruz. Yorulduk tekrar gözden geçirince çok da hafif olmadığını farkediyorum. Bu benim hayatımda yazdığım ilk blog yazısı oldu, teşekkür ederim okuduğunuz için. Gelecek dizide Schnorr signature uygulaması üzerinden elliptic curve, sigma protocol ve basit zk ispatlara göz atmayı planlıyorum.
Okuyucularımızla bir takım challengelar üzerinden etkileşime geçmek niyetindeyiz. Bülteni yöneten arkadaşım cevap yollayanlara swag gönderecek. Anahtarlık çakı falan. Hayır NFT isteriz! Hayır arkadaşlar bi sn. Hayır NFT! Tamam dedi arkadaşımız sonra bişeyler ayarlarız gibi şeyler söyledi. Cevapların altında eth adresi de paslansın ne olur ne olmaz. Esasında enteraksiyon da ölçmek niyetindeyiz like gibi ama çift taraflı.
Kolay: Bitcoin wallet konusuna geri dönersek madem her private key için bir public key var ben bütün olası private keyleri deneyip var olan public keylerle mukayese ederek bir başkasının idealde de satoshinin bitcoinini neden çalamam?
Orta: pythonda basit merkele tree implementasyonu (sha256, blake2 hash func farketmez) derinlik 4 olsun. leaf update edebilelim. membership proof yapabilelim.
Orta modulusu saat gibi 24 aldığımız zaman neden tüm asal sayılar birbirinin tersi iken mesela 7 *7 % 24 = 1 neden bu 3 için geçerli değildir 3 * 3 % 24 != 1 ?
Advanced Önden yürümek isteyenlere: python ile schnorr signature implementastonu (hint: use py_ecc)
Elinize sağlık tekrardan :) Hiç yazılım bilgim yok ama meraklıyım bu işlere, kolaydan da bir mantık yürütmek istedim. Sanki buradaki kritik söylem 'bütün var olan private keyler' kısmı çünkü bunun için BIP-39 temelinde 2,048 kelime var. Basit bir combination calculator ile bu sayının okuyamacağım düzeyde büyük olduğunu görüyorum.Bu büyük uzay kümesi içerisinde denk gelme ihtimalinin 'evren büyüklüğü/karıncanın arter yarıçapı' ilişkisine benzemesinden ötürü mü böyle acaba?
cok begendım kafamdakı bazı sorulara cevap buldum elınıze saglık
Elinize sağlık tekrardan :) Hiç yazılım bilgim yok ama meraklıyım bu işlere, kolaydan da bir mantık yürütmek istedim. Sanki buradaki kritik söylem 'bütün var olan private keyler' kısmı çünkü bunun için BIP-39 temelinde 2,048 kelime var. Basit bir combination calculator ile bu sayının okuyamacağım düzeyde büyük olduğunu görüyorum.Bu büyük uzay kümesi içerisinde denk gelme ihtimalinin 'evren büyüklüğü/karıncanın arter yarıçapı' ilişkisine benzemesinden ötürü mü böyle acaba?