Merke Ağaçları ve Merkle Kökleri
Ana sayfaMakaleler

Merke Ağaçları ve Merkle Kökleri

İleri Seviye
1mo ago
7m

Merkle ağacı nedir?

Merkle ağacı kavramı, açık anahtar kriptografisi üzerine çalışmalarıyla tanınan bilgisayar mühendisi Ralph Merkle tarafından 80'lerin başında ortaya atılmıştır.

Merkle ağacı yapısı, bir set içindeki verinin bütünlüğünü doğrulamak için kullanılır. Merkle ağaçları özellikle, katılımcıların bilgileri paylaşmasını ve bağımsız olarak doğrulamasını gerektiren eşler arası ağlar bağlamında oldukça ilgi çekici bir kullanıma alanına sahiptir.

Hash fonksiyonları, Merkle ağacı yapılarının merkezinde yer alır. Bu nedenle devam etmeden önce Hashing Nedir? makalemizi okumanızı öneririz.


Merkle ağaçları nasıl çalışır?

Büyük bir dosya indirmek istediğinizi düşünün. Genellikle bir açık kaynak yazılımda, indirdiğiniz dosyanın hash'inin geliştiricilerin herkese açık paylaştığı hash'le örtüşüp örtüşmediğini kontrol etmeniz gerekir. Eğer örtüşüyorsa bilgisayarınızdaki dosyanın geliştiricilerin dosyasıyla birebir aynı olduğunu bilebilirsiniz.

Hash'ler örtüşmüyorsa ortada bir sorun vardır. Ya yazılım altında gizlenen zararlı bir dosya indirmişsinizdir ya da dosya doğru şekilde inmemiştir ve çalışmayacaktır. Eğer ikinci durum söz konusuysa dosyayı indirmek için harcanan zaman boşa gideceğinden keyfiniz kaçabilir. Şimdi sürece baştan başlamanız ve bu sefer dosyada bir bozulma meydana gelmeyeceğini ummanız gerekir.

Aklınızdan keşke bunu yapmanın daha kolay bir yolu olsaydı diye geçebilir. İşte bu noktada Merkle ağaçları devreye girer. Bunlardan biriyle dosyanızı parçalara ayırabilirsiniz. Eğer dosya 50GB ise, bunu her biri 0,5GB olacak şekilde yüz parçaya bölebilir ve daha sonra dosyayı parça parça indirebilirsiniz. Torrent dosyaları ile yaptığınız da tam olarak budur. 

Bu durumda kaynak size Merkle kökü olarak bilinen bir hash sunar. Bu tek hash, dosyanızı oluşturan tüm parçaların bir temsilidir. Fakat Merkle kökü veriyi doğrulamayı çok daha kolay hale getirir. 

Basitçe açıklamak için sekiz parçaya bölünmüş 8GB'lık bir dosya örneğini ele alalım. Parçalara A'dan H'ye kadar isim verelim. Daha sonra her parçayı bir hash fonksiyonundan geçirelim ve sekiz farklı hash elde edelim.


Sekiz parçanın her birini bir hash fonksiyonundan geçirerek hash'lerini alıyoruz.


Artık elimizde biraz daha anlamlı bir veri var. Tüm parçaların hash'leri elimizde, yani bunlardan biri hatalıysa bunu kaynakla karşılaştırarak anlayabiliriz değil mi? Muhtemelen evet, ama bu aynı zamanda son derece verimsiz olur. Eğer dosyanız binlerce parçadan oluşuyorsa, bunların her birini hash etmeniz ve sonuçları teker teker kontrol etmeniz oldukça zor olacaktır.

Bunun yerine hash'leri ikili olarak alır ve bu ikilileri birlikte hash ederiz. Yani hA + hB, hC + hD, hE + hF ve hG + hH'yi hash ederiz. Elimize dört hash geçer. Daha sonra bunları bir tur daha hash ederek iki hash elde ederiz. En nihayetinde, son ikisini de hash ederek ana hash'imiz olan Merkle köküne (ya da kök hash'e) ulaşırız.


Yapı, ters bir ağaca benziyor. En alt sırada yapraklar bulunuyor, bunlar birleşerek düğümleri ve son olarak da kökü oluşturuyor.


Artık elimizde, indirdiğimiz dosyayı temsil eden Merkle kökü var. Bu kök hash'i kaynak tarafından sunulan hash ile karşılaştırabiliriz. Eğer eşleşirlerse harika olur. Ama hash'ler farklıysa verinin üzerinde değişiklik yapıldığından emin olabiliriz. Diğer bir deyişle, parçalardan bir ya da birkaçı farklı bir hash yaratmıştır. Veride yapılacak en küçük bir değişiklik bile tamamen farklı bir Merkle kökünün yaratılmasına neden olur. 

Neyse ki, kolay bir yoldan hangi parçanın hatalı olduğunu kontrol edebiliriz. Bizim örneğimizde, hatalı parçanın hE olduğunu varsayalım. İlk olarak ağdaki bir eşten Merkle kökünü oluşturan iki hash'i (hABCD ve hEFGH) istemeniz gerekir. Sizin hABCD değerinizle eşten gelen değerin örtüşmesi gerekir çünkü bu alt ağaçta hata yoktur. Fakat hEFGH örtüşmeyecektir, dolayısıyla bu alt grubu kontrol etmeniz gerektiğini anlarsınız. Daha sonra kendinizinkiyle kıyaslamak için hEF ve hGH hash'lerini istersiniz. hGH aynı olacaktır, böylece hatalı parçanın hEF olduğu çıkarımını yapabilirsiniz. Son olarak hE ve hF hash'lerini karşılaştırırsınız. Böylece hE'nin hatalı olduğunu belirleyebilir ve bu parçayı tekrar indirebilirsiniz.

Özetle, bir Merkle ağacı verinin birçok parçaya bölünmesi ve daha sonra bir Merkle kökü oluşturmak için bu parçaların tekrar tekrar hash edilmesiyle yaratılır. Böylece veri parçalarında bir hata olup olmadığı kontrol edilebilir. Bir sonraki bölümde inceleyeceğimiz gibi Merkle ağaçlarının ilginç başka uygulamaları da vardır.



Kripto para dünyasına girmek mi istiyorsunuz? Binance üzerinden Bitcoin alabilirsiniz!



Merkle kökleri neden Bitcoin'de kullanılır?

Merkle ağaçları için farklı kullanım alanları bulunur ama biz burada blockchainlere yönelik önemlerine odaklanacağız. Merkle ağaçları Bitcoin ve diğer birçok kripto para için hayati öneme sahiptir. Tüm blokların ayrılmaz parçalarıdır ve blok başlığında yer alırlar. Ağacımızın yapraklarını elde etmek için bloğa eklenen her işlemin işlem hash'ini (TXID) kullanırız. 

Merkle kökü birden fazla amaca hizmet eder. Burada kripto para madenciliğine ve işlem doğrulamaya yönelik uygulamalarından bahsedeceğiz.


Madencilik

Bir Bitcoin bloğu iki parçadan oluşur. İlki blok başlığıdır ve bloğun meta verisini içeren sabit büyüklükte bir parçadır. İkincisi ise büyüklüğü değişebilen ama genellikle başlıktan çok daha büyük olan işlemler listesidir.

Madencilerin geçerli bir blok oluşturabilmek için belirli koşulları karşılayan bir çıktı yaratmak amacıyla veriyi tekrar tekrar hash etmesi gerekir. Her girişimde, farklı bir çıktı yaratabilmek için blok başlığında yer alan rastgele bir sayı (nonce) değiştirilir. Fakat bloğun büyük kısmı aynı kalır. Binlerce işlem olabilir ama yine de her sefer bunları hash etmeniz gerekir.

Bir Merkle kökü, süreci büyük ölçüde kolaylaştırır. Madenciliğe başladığınızda, dahil etmek istediğiniz tüm işlemleri sıralar ve bir Merkle ağacı oluşturursunuz. Ortaya çıkan kök hash'i (32 bit) blok başlığına koyarsınız. Daha sonra madencilik yaparken, tüm blok yerine yalnızca blok başlığını hash etmeniz yeterli olur.

Bu yöntem işe yarar çünkü üzerinde değişiklik yapılmasına dirençlidir. Bloğun tüm işlemlerini kompakt bir formatta özetlemiş olursunuz. Geçerli bir blok başlığı bulup daha sonra işlem listesini değiştiremezsiniz çünkü bu Merkle kökünü de değiştirecektir. Blok diğer node'lara gönderildiğinde, onlar da işlem listesinden kökü hesaplar. Eğer elde ettikleri değer başlıkla aynı değilse blok reddedilir.


Doğrulama

Merkle köklerinin faydalı bir diğer ilginç özelliği daha vardır. Bu özellik hafif node'ları (blockchainin tam bir kopyasını tutmayan node'lar) ilgilendirir. Eğer sınırlı kaynağa sahip bir cihaz üzerinde node çalıştırıyorsanız, bir bloğun tüm işlemlerini indirmeyi ve hash etmeyi istemezsiniz. Bunun yerine bir Merkle ispatı (bir full node tarafından gönderilen ve işleminizin belirli bir blokta bulunduğunu ispat eden kanıt) istemeniz yeterli olur. Buna genellikle Basitleştirilmiş Ödeme Doğrulaması (SPV) adı verilir ve kavram Satoshi Nakamoto tarafından Bitcoin whitepaper'ında açıklanmıştır.


hD'yi kontrol etmek için yalnızca kırmızı hash'lere ihtiyaç duyarız.


TXID'si hD olan bir işlem hakkında bilgi sahibi olmak istediğimiz bir senaryoyu düşünelim. Eğer hC bizimle paylaşılırsa, hCD'yi bulabiliriz. Daha sonra, hABCD'yi hesaplamak için hAB'ye ihtiyacımız olur. Son olarak hEFGH ile, ortaya çıkan Merkle kökünün blok başlığıyla eşleşip eşleşmediğini kontrol edebiliriz. Eşleşiyorsa, işlemin bloğa dahil edildiği kanıtlanmış olur – farklı verilerle aynı hash'i yaratmak neredeyse imkansızdır.

Yukarıdaki örnekte, yalnızca üç kere hash almamız gerekir. Oysa Merkle ispatı olmasa, bunu yedi kere yapmamız gerekirdi. Günümüzde bloklar binlerce işlem içerdiği için, Merkle ispatlarını kullanmak zamandan ve hesaplama gücünden önemli ölçüde tasarruf sağlar.


Son düşünceler

Merkle ağaçlarının farklı birçok bilgisayar bilimi uygulaması için büyük fayda sağladığı bilinmektedir. Yukarıda bahsettiğimiz gibi blockchainler için son derece önemlidirler. Merkle ağaçları sayesinde, dağıtılmış sistemlerde ağ gereksiz verilerle doldurulmadan bilgiler kolayca doğrulanabilir.

Merkle ağaçları (ve Merkle kökleri) olmadan Bitcoin'in ve diğer kripto paraların blokları günümüzdeki kadar kompakt olamazdı. Ve hafif node'lar gizlilik ve güvenlik bakımından daha zayıf olsa da, Merkle ispatları sayesinde kullanıcılar işlemlerinin bir bloğa dahil edilip edilmediğini minimum destekle kontrol edebilir.