Merkle Tree

İkili Ağaç (Binary Tree)

Resim 1. Küçük bir ikili ağaç yapısı.

Ağaç şeklinde açılan ve her bir dalında iki farklı dal bulunan bir veri yapısıdır. Her ağacın bir adet kökü olduğu gibi bizim ağaçlarımızın da her daim tek bir kökü olmalıdır. Dal sayısına kendimiz karar veriyoruz ama kök tek ve her ağaçta olmak zorundadır. İkili ağaç (Binary Tree) dememizin sebebi de bu dal sayısının iki adet olmasıdır. Her dalın ucunda meyve diyebileceğimiz “DÜĞÜM”(Node) yapıları bulunmaktadır. Biz bu düğümlerde saklamak istediğimiz verileri saklıyoruz. İkili ağaçların en temel özellikleri de şunlardır;

■ Bir adet kökü vardır.

■ En alt katmandaki düğümlere “YAPRAK” (Leaf) denir.

■ Her düğümün iki adet çocuğu yani alt düğümü vardır.

■ Yaprakların çocukları diyebileceğimiz dalları yani düğümleri yoktur.

İkili ağaç neden önemli?

Şimdi elimizde 32 tane sayıyı tutan düz bir liste olduğunu varsayalım.

Resim 2. düz bir liste.

Şimdi de biz bu liste içerisinde 32 sayısının olup olmadığını arayalım. Bunun için en baştan başlayıp her sayıya tek tek bakmamız ve 32 sayısına ulaştığımızda bulduğumuzu söylememiz gerekiyor. Bu işlem elbette 32 adet veri için son derece kısa sürecektir. Elimizde 32 değil de milyonlarca veri olduğunu düşünürsek bu süre tahmin edersiniz ki çok uzun sürecektir.

Şimdi de elimizde bir ikili ağaç olsun ve bu ikili ağaçta bir veriyi aramaya çalışalım.

Resim 3. Küçük bir ikili arama ağacı.

Elimizdeki bu ikili ağaçta “14” sayısını arayalım. Elbette elimizde iki farklı yöntem var. Bunlardan ilki yine en baştan başlayarak tek tek bütün verilere bakarak bulabiliriz. Bu yöntem bize ikili ağaçların özelliklerini verimli kullandıran bir yöntem değildir. Bunun yerine daha akıllıca bir yöntemle istediğimiz sayıyı bulabiliriz.

Özel Bir Ağaç Yapısı

Bu ağaçta özel bir şey fark etmemiz gerekiyor. Bu özel şey de her düğümün sağ çocuğu kendisinden büyük ve sol çocuğu kendisinden küçüktür. O halde en mantıklı hamle kök düğümünden (root) başlayıp aramak istediğimiz sayı kökten büyükse sağ dallara, küçükse sol dallara doğru ilerleyerek bakmamız gereken düğüm sayısını her seferinde yarısına indirgeyerek aramak olacaktır. Örneğin 14, kök düğümüne baktığımızda 14'ün 8'den büyük olduğunu biliyoruz. O halde 14 sayısı kök düğümünün sol kısmında yer alamaz. Biz de bunu bildiğimiz için bakmamız gereken düğüm miktarını yarıya indirmiş olduk. Yani en fazla sadece 7 düğüme bakacağız.

Veri Boyutunu Yarıya İndirmek

Şimdi 14'ün sağda olduğunu bildiğimiz için değeri 12 olan düğüme gidiyoruz. 12 yine 14'ten küçük olduğu için yine 12'nin sol kısmına bakmadan direkt sağ tarafına bakacağız. Yani bakmamız gereken düğüm sayısı yine yarıya düştü. Kök düğümüne baktığımızda yarısına düşürmüştük, şimdi bir daha yarısına düşürdük. Toplamda bütün veriyi 4'te birine düşürmüş olduk. 12'nin sağına bakıyoruz ve 14 sayısını buluyoruz. Toplamda 15 adet veri arasından sadece en fazla 3 denemede aradığımız sayıyı bulduk. İkili ağaç yapısı arama işlemlerinde en fazla logaritma 2 tabanında “n” defa da aradığımız veriyi bulmamızı sağlıyor.

Buradaki “n” veri sayımızı belirtiyor.

Bu ikili ağaç veri yapısını kullanarak tasarlamak istediğimiz merkeziyetsiz (decentralized) bir sistem kurmak için en temel adımı atmış oluyoruz.

Merkle Tree

Resim 4. Basit bir merkle tree yapısı.

Merkle Tree Nedir ?

Yukarıda bahsetmiş olduğumuz ikili ağaçların birebir kullanıldığı bir veri yapısıdır Merkle Tree’ler. Merkle Tree’lerde sayı depolamak yerine hash (karıştırma) algoritmaları ile oluşturulmuş “Hash”leri depoluyor.

🚧 HÜ için SHA-256 algoritması ile oluşturulan hash → 38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e15

🚧 CHAIN için SHA-256 algoritması ile oluşturulan hash → 945c72078d9c878587e1d29181b97a50b88187b7969792478a28ba1f512c5ca3

Hash’leri Hash’e Çevirmek

Yukarıda da görüldüğü gibi HÜ ve CHAIN kelimeleri için oluşturulmuş hash kodları mevcut. merkle tree’lerde sadece 2 değil istediğimiz kadar verinin hash kodlarını saklayabiliyoruz. Basit olması açısından burada 2 adet veri ile neler yapılabilir onu anlamaya çalışacağız. Bildiğimiz gibi her bir farklı veri için farklı bir hash kodu elde ediyoruz. İlk etapta her veri için birer hash kodu oluşturuyoruz ve daha sonra oluşan bu hash kodlarını ikişer ikişer birleştirip yeni bir hash kodu elde ediyoruz. Örneğin;

👉 38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e15945c72078d9c878587e1d29181b97a50b88187b7969792478a28ba1f512c5ca3

Yukarıdaki hash kodu HÜ ve CHAIN verilerinin hash kodlarının arka arkaya yazılmış halidir ve aslında bu da bir veridir ve bu veri için de özel bir hash kodu elde edilebilir.

⚠️ 5aec6c7f6a6d055c9c5dd9e0bf3d8f19936075ab335283d52fbac09a9345e87a

Bu şekilde. Bu yeni hash kodlarını da yine ikişer ikişer birleştirip ve onların hash kodlarını alarak bütün verinin boyutunu 1’e düşürmeye çalışıyoruz. Örneğimizde olan en üstteki hash kodu da bu 1 adet veridir. Bu verinin özel bir adı vardır.

| Merkle Kök (Merkle Root)

2 farklı boyuttaki veriyi saklamak yerine 256 bitlik bir kodu saklamak hafıza açısından çok daha verimlidir.

Peki Bu Kod Ne İşe Yarayacak?

Bildiğimiz gibi blockchain merkeziyetsiz (decentralized) bir sistem oluşturmuş ve bunu korumayı amaçlamaktadır. Bunun sağlanabilmesi için tüm verilerin tüm kullanıcılar arasında paylaşılması gerekir. Birkaç yüz veya birkaç bin veriyi belki kolayca paylaşabiliriz ama bugün itibariyle 300 gigabyte’ı geçmiş olan bitcoin blockchain’i için bu pek mümkün değildir. Hem veri büyük hem de bu veri saniyede onlarca defa değişiyor. Bu verinin tamamı bazı node’lar tarafından tutulsa da bazı node’lar verinin sadece merkle tree’sini tutar. Hızlı kontroller yapılırken de bu node’lar bize merkle tree’yi tarayarak yardımcı olabilir.

Merkle Tree Çözüm mü ?

Yukarıda da bahsettiğimiz gibi merkle tree’nin kök düğümü yani root’u sadece 256 bitlik 64 karakterli bir veridir. Bu o kadar küçük bir boyuttur ki tüm blockchain ağında saliseler içerisinde yayılabilir. Bu sayede blockchain’de yapılan değişiklikleri tüm veriyi tüm kullanıcılara aktarmak yerine sadece o değişimin hash kodunu aktarıyoruz. Bu sayede zincirdeki her değişimin bilgisi ve kanıtı her kullanıcıda olduğu için merkeziyetsiz yapı korunmuş oluyor.

Peki Bu Hash Kodu Nasıl Bir Kanıt Sunar?
Yukarıdaki 2 verilik merkle tree’mizi hatırlarsanız elimizde bir adet merkle kök adını verdiğimiz bir hash kodu var. Bu hash kodu ağdaki tüm kullanıcılarla paylaşıldığı için kaybolması ya da değiştirilmesi imkansızdır. Örneğin ben bu iki veriden “CHAIN” i, “CHAİN” mi yoksa “CHAIN” mi yazdığımı unuttum. Ve benim elimde sadece merkle kök var. Bu kök ile ben verilere ulaşamıyorum. Peki ama ben bu kökü kullanarak nasıl bir doğrulama yapabilirim?

Merkle Proof (Merkle Kanıt)

Resim 5. Merkle proof mekanizması.

Gerekli Olan HASH’ler

Bir verinin merkle tree içerisinde olup olmadığını anlamak için kullanılan yönteme Merkle Proof (Merkle Kanıt) deniyor. Yukarıdaki resimde Hk isimli (yeşil olan) verimizin içinde olup olmadığını araştırdığımız dosyanın hash kodudur. Yavaş yavaş yukarı katmanlara tırmanmak için elimizden tutacak bilgilere ihtiyacımız var. Örneğin Hkl yani Hk ve Hl hash’lerinin birleşmesiyle oluşmuş hash kodunu bulabilmemiz için bize Hl gerekli. Çünkü zaten Hk elimizde Hl’yi de bilirsek Hkl’yi hesaplarız.

Yeni Merkle Kök Ne İfade Ediyor?

Bunu bir örnekle görelim.

Resim 6. Basit Merkle Tree yapısı.

Benim elimde merkle kök adını verdiğim hash kodu var. Benim amacım verilerden birisinin “CHAİN” mi “CHAIN” mi olduğunu anlamaya çalışmak. Bildiğimiz gibi hash kodları geri döndürülemez kodlardır. Yani ben kök hash’i ile geriye giderek verilere ulaşamıyorum. Peki ama o zaman ben, veriyi nasıl doğrulayacağım ?

CHAİN mi CHAIN mi ?

Elimizdeki verileri bir yere not edelim ki neleri kullanabileceğimize bakalım.

Merkle kök :
5aec6c7f6a6d055c9c5dd9e0bf3d8f19936075ab335283d52fbac09a9345e87a


HÜ verisinin hash kodu:
38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e15

Elimizdeki bilgiler bununla sınırlı. Şimdi ben merkle kök’ün nasıl oluştuğunu biliyorum.

Nasıl oluşuyor?

Merkle kök hash’i için HÜ hash’ini ve bilmediğim diğer hash’i kullanıyorum. O halde ben ilk önce doğru olduğunu düşündüğüm “CHAİN” hash’i ile HÜ hash’ini birleştirerek yeni bir hash elde edeyim. Eğer bu elde ettiğim yeni hash merkle kök’le aynı ise o zaman benim verim “CHAİN”miş diyeceğim. Eğer değilse “CHAIN” hash’i ile HÜ hash’ini birleştirerek yeni bir hash oluşturacağım. Ve tekrar merkle kök ile karşılaştıracağım.

“CHAİN”

HÜ verisi için hash:
38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e15

CHAİN verisi için hash:
7720da957e6f83b45d403ee2a8c32711bc4390b3696bd1c1ee3270f799ea4a14

Ve yeni Merkle kök hash:
⚠️ Yani → 38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e157720da957e6f83b45d403ee2a8c32711bc4390b3696bd1c1ee3270f799ea4a14

Verisinin hash’i.
Bu veriyi nasıl elde ettik: HÜ hash’i ile CHAİN hash’ini yan yana yazdık.

Ve yeni Merkle kök hash:
f1c01f8529687ece171ed9528cee08f3a7800d7ac9c1c98a71ce2cee90176a8a

Eski Merkle kök hash:
5aec6c7f6a6d055c9c5dd9e0bf3d8f19936075ab335283d52fbac09a9345e87a

Gördüğümüz gibi iki hash birbirinden tamamen farklı. Bunun anlamı verimizin “CHAİN” olmadığıdır. Peki verimiz “CHAIN” mi?

“CHAIN”

HÜ verisi için hash:
38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e15


CHAIN verisi için hash:
945c72078d9c878587e1d29181b97a50b88187b7969792478a28ba1f512c5ca3

Ve yeni Merkle kök hash:
⚠️ Yani → 38dd53b718c9a20be0800309c7250b477e3bbc41dc52f86ffb94f1193b098e15945c72078d9c878587e1d29181b97a50b88187b7969792478a28ba1f512c5ca3
verisinin hash’i.

Bu veriyi nasıl elde ettik: HÜ hash’i ile CHAIN hash’ini yan yana yazdık.

Ve yeni Merkle kök hash:
5aec6c7f6a6d055c9c5dd9e0bf3d8f19936075ab335283d52fbac09a9345e87a


Eski Merkle kök hash:
5aec6c7f6a6d055c9c5dd9e0bf3d8f19936075ab335283d52fbac09a9345e87a

Burada da gördüğümüz gibi iki hash birbirinin tıpa tıp aynısı. Bu demek oluyor ki verilerden birisi “HÜ” iken diğeri “CHAIN”miş.

Blockchain Merkle Tree’yi Nasıl Kullanıyor?
Bildiğimiz ve adı üzerinde olduğu gibi blockchain bir block’lar zinciridir ve bu zincir yüksek miktarda veri tutar. Hızlı doğrulamalar yapmaya ihtiyaç duyduğumuzda da bu büyük veriyi taramamız zorlaşır. Bu sebeple bazı doğrulamalar için Merkle Tree’ler kullanılır.

Blockchain’de Merkle Proof Nasıl Çalışır?

Yukarıda bahsettiğimiz gibi merkle proof ile bir verinin merkle tree içerisinde olup olmadığını anlayabiliyoruz. Bu tekniği kullanarak blockchain üzerindeki değişiklikleri kontrol edebiliyoruz. Örneğin ben Yasin’e 50 bitcoin gönderdim ve bu merkle tree’ye eklendi. Aradan biraz zaman geçti ve ben bitcoin’in bu kadar değerlendiğini gördüğüm için 50 bitcoin değil de 40 bitcoin gönderdim ama benim cüzdanımdan 50 alınmış diyerek bir dolandırıcılık yapmak istedim.

Bir Değil Milyonlarca Kopya

Bu noktada blockchain üzerinde o tarihe ve zamana ait merkle kök bulunuyor. Yukarıda yaptığımız gibi sanki ben Yasin’e 40 bitcoin göndermişim gibi bir veri oluşturuluyor ve merkle tree’deki diğer ihtiyacımız olan hash’leri de kullanarak yeni bir merkle kök elde ediyoruz. Bakıyoruz ki elde ettiğimiz hash ile eski merkle kök hash’i aynı değil. Buradan da benim Yasin’e 40 bitcoin göndermediğim anlaşılıyor. Kaç bitcoin gönderdiğimizi bulmak için de tahmin ettiğimiz 50 bitcoin değeri için aynı işlemleri yapıyoruz. Sürpriz… Hash’ler aynı. Ve ben bu merkle kök hash’ini silmeye çalıştım ama maalesef bu hash milyonlarca kişide zaten kayıtlı. Benim silmem hiçbir şey ifade etmiyor. Bu yüzden merkeziyetsiz sistemleri kandıramayız.

Simple Peyment Verification (SPV)

Double Spending Nedir?

Diyelim ki benim elimde 50 bitcoin var ve ben bu bitcoinleri hem Yasin’e hem de Murat’a göndererek potansiyel bir dolandırıcılık yapmak istedim. Buna double spending (çift harcama) deniyor ve bu durumdan blockchain ve bitcoin’i kurtaran merkle tree’lerdir.

Nasıl Harcanır?

Bitcoin ya da herhangi bir kripto para alım-satımına bir transaction (işlem) denir. Bu işlemler tıpkı yukarıdaki örneklerdeki gibi birer veridir ve hash’lenerek blockchain’e eklenirler. Bu işlem belli transaction’ların birikmesiyle merkle tree oluşturulur ve blockchain’e yeni bir block eklenir. Bu sırada yani merkle tree oluşumu sırasında ben bir transaction yaptım ve bu işlem merkle tree’ye eklendi. Hemen ardından aynı tutarda bir işlem daha yapıyorum ve bu durumda blockchain benim o işlemi yapmak için yeterli miktarda bitcoin’im var mı yok mu bakması gerekiyor. Peki yüzlerce gigabyte veriye o kadar kısa sürede nasıl bakıp da bana izin verecek?

Light Node Super Node Nedir?

Bildiğimiz gibi super node’larda tüm blockchain verisi tutulur (Bu sıralarda 324 GB. Light Nodelar ise yukarıda bahsettiğimiz merkle kök’leri saklarlar. Bu köklerin boyutu çok küçüktür ve örneklendirdiğimiz gibi hızlı doğrulamalar için biçilmiş kaftandır. Light Node’lar genellikle full Node’lara bağlıdır ve ağın uç kısımlarında bulunurlar. Genellikle cüzdanlarla ilişkilidirler. Örneğin siz bir işlem yapmak istediğinizde yukarıda bahsettiğimiz gibi light node’lar tuttukları merkle tree’leri kullanarak hızlıca işleminize izin verip vermemek üzerinde karar verirler. İzin verirlerse işleminiz asıl doğrulama için bellek havuzuna alır ve bir miner’ın kendisini bir bloğa kaydedip zincire eklemesini bekler.

Light Node Ne Yapar?

Benim sanal cüzdanımda nasıl bitcoin olabilir? Benim bir şekilde bir yerlerden bitcoin alıp satmış olmam gerekiyor ki olabilsin. Ben bu işlemleri yaptığımda bunlar merkle tree’lere ve block’lara eklendi. Ve şimdi benim cüzdanımda 40 bitcoin var ve ben Yasin’e 50 bitcoin göndermek için bir işlem başlattım. Ne olacak?

Başarılı mı Başarısız mı?

İşte burada light nodelar ve SPV kavramı işin içine giriyor. Light Nodelar merkle köklere sahip oldukları için herhangi bir işlemin yapılıp yapılmadığını çok kısa bir sürede bulabiliyorlar. Çünkü merkle kökler hem güvenilir hem de çok küçük boyutları var. Bu yüzden light nodelar benim geçmiş tüm işlemlerimi arayıp benim toplamda ne kadar bakiyem olduğunu buluyor ve bakiyem yeterse izin veriyor yetmezse bu işlemi iptal ediyor ve ne merkle tree’ye ekliyor ne de block’a.

Simple Payment Verification (SPV)?

Bu teknik ile bir kişinin bir işlemi yapıp yapamayacağına karar veren lighth nodeler, tüm veriyi indirmek yerine sadece merkle kökleriyle verinin orada olup olmadığını kontrol ediyor. Bu sayede bir işlemin yapılabilir ya da yapılamaz olduğuna karar verme süresi çok büyük oranda kısalıyor.

Fakat SPV tam güvenlik sunmaz. Bu doğrulama bir tüccarın ödeme olarak çek vermesine benzetilebilir. Tam doğrulama için çeki alan kişinin bankaya gidip çekin geçerliliğini kontrol ettirmesi gerekir. (İşlemin bir miner tarafından doğrulanıp ağa duyurularak blok zincire eklenmesi) Örneğin bir kahve almak istediğinizde SPV çok hızlı bir şekilde ödeme yapma imkânı sağladığı için güvenilir olarak kabul edilebilir. Fakat ödemesi yapılan şey bir araba ya da bir ev gibi yüksek maliyetli bir ürün/hizmetse tam doğrulama beklenmelidir.

SPV’yi belli bir oranda güvenlik sağlayan ilk kontrol gibi düşünebiliriz.

Neden Tam Güvenlik Sağlamaz?

Bir işlem ağa yazılmadığı sürece gerçekleşmiş sayılmaz. Örneğin Bitcoin için bir işlemin ağa yazılma süresini 10 dakika alalım. Cüzdanınızda 50 Bitcoin var ve önce Murat’a sonra Yasin’e 50 Bitcoin yolladınız. SPV iki işleme de izin verir çünkü Murat’a yolladığınız 50 BTC henüz blok zincire kaydedilmemiştir ve onu harcadığınıza dair bir işaret yoktur. Ancak ilk işleminiz bir miner tarafından doğrulanıp zincire kaydedildikten sonra Yasin’e gönderdiğiniz 50 BTC’lik harcama iptal edilir. Fakat gördüğünüz gibi ilk işlem doğrulana kadar ikinci işlem SPV’ye takılmaz.

Ama sizin zaten 50 BTC’niz olmasaydı SPV iki işlemi yapmanızı da doğrudan engelleyecek ve hem bellek havuzunu meşgul etmeyecek hem de hızlı bir şekilde dolandırıcıları tespit edecektir.

Blockchain ve kriptografi ile ilgili diğer yazılarımızda görüşmek üzere…