Merkle Tree Nedir?

Merkle tree ve örnek kullanımları

---

Merkle tree aynı zamanda hash tree olarak da bilinir çünkü temel olarak verilerin hash fonksiyonlarının ard arda alınmasından oluşan bir veri yapısıdır. Merkle tree veri doğrulama ve senkronizasyonu için kullanılmaktadır. Peki nedir bu hash fonksiyonları?

Hash Fonksiyonları

Hash fonksiyonları şifreleme fonksiyonlarıdır. Herhangi boyutta bir veriden 64 karakterden oluşan kısa bir veri haline çevirir. Girdi olarak verdiğimiz veriye özel bir çıktı oluştur. Giren verideki en ufak bir değişiklik bambaşka bir çıktı oluşturur. Böylece her girdinin eşsiz birer çıktısı olur. 

Biraz kafa karıştırıcı olmuş olabilir fakat basit bir örnekle hemen anlayacaksınız. Öncelikle boyutsal olarak inceleyeylim. Yazıyı yazmış olduğum günün 10 Kasım olması dolayısıyla örneğimi Atatürk’ün bizlere seslendiği Gençliğe Hitabeden vereceğim.

Gördüğünüz gibi tüm gençliğe hitabeyi Keccak256 Hash fonksiyonu ile şifrelediğimizde bize 64 karakterden oluşan ufacık bir çıktı verdi. Biz ne zaman bu girdiği verirsek verelim, bize verdiği çıktı alttaki gibi olacaktır. 

Peki hash’i anladık da Keccak256 ne diyecek olursanız, keccak256 bir hash fonksiyon algoritmasıdır. Keccak256 gibi pek çok farklı hash algrotiması vardır ve bunlardan en ünlüsü SHA256 hash algoritmasıdır. Bitcoin SHA256 şifreleme algoritmasını kullanır. Buna da birazdan değineceğiz.

Şimdi girdi ile çıktı arasındaki boyutsal farkı görmek için bir de hitabenin en son paragrafının hash fonksiyonunu alalım isterseniz.

Burada da gördüğünüz gibi, girdi boyutundan bağımsız bir şekilde çıktı her zaman 64 karakterden oluşmaktadır. Dikkat ederseniz çıktı her zaman farklıdır. Hatta bu fark öylesine bir farktır ki, en ufak bir değişiklik bambaşka bir çıktı verir. Boşluklar dahil! Gelin bir de onu da Atatürk’ün güzel bir sözü ile test edelim.

Girdi:

Benden sonra beni benimsemek isteyenler bu temel mihver üzerinde akıl ve ilmin rehberliğini kabul ederlerse, manevi mirasçılarım olurlar.

Çıktı:

dace99ba9f7bc44f158464418ef67f0751af822a8073dbc707059d787e6e1ff8

Girdi:

Benden sonra beni benimsemek isteyenler bu temel mihver üzerinde akıl ve ilmin rehberliğini kabul ederlerse, manevi mirasçılarım olurlar

Çıktı:

2dbc8706551b994a6226fb9b6b77547983f98859f4f78e0639a056b01e23a449

Neredeyse birebir aynı girdi. Fakat ikincisinde sonunda nokta yok! En ufak bir değişiklik tamamen bambaşka bir çıktı veriyor. Bu şifreleme algoritması sayesinde biz çıktıya bakarak girmiş olunan veridinin doğruluğundan emin oluyoruz. 

Merkle tree olmadan sadece tek bir hash fonsiyonunun kullanımına bir örnek verelim isterseniz. Diyelim ki bir akıllı kontrat yazdınız ve bu kontratı etherscan’de onaylayarak blockchain üzerinde hayata geçirdiniz. Bu kontratın yazarı olarak orada adınızın yazmasını istiyorsunuz fakat herkesin adınızı görmesini de istemiyorsunuz diyelim.

Bunun için adınızın bir hash fonksiyonunu alırsınız, ve kontrata bunu aşağıdaki gibi yerleştirirsiniz. Herkese açık bu kontratta yazar olarak şifreli bir şekilde adım yazıyor. Benim yazdığımı bilmesini istediğim kişilere Keccak256 algoritmasıyla “Bora Özenbirkan” hash’ini alırsanız, kontratta yazan çıktıyı alacaksınız derim. Bu da benim bu kontratı yazan kişi olduğumu kanıtlar. Adınızı değil de herhangi bir mesaj da yazabilirsiniz. Sonuçta bu çıktığı üreten girdiği biliyorsanız, bunu siz yazmışsınızdır.

/// @author ad1f03c31b91e619dd07983453dfd95587addd52ab31e32d2909817c3ba1beeb

Tüm bu gösterdiğim örnekleri kendiniz denemek için online bir araç olarak bu linkteki adresi kullanabilirsiniz. Farklı hash algoritmalarını ve girdilerde değişiklikler yaparak çıktının nasıl değiştiğini kendiniz deneyimleyerek konsepti daha iyi kavrayabilirsiniz.

Merkle Tree

Hash fonksyionlarının nasıl işlediğini anladığımıza göre merkle tree’ye geri dönebiliriz. Merkle tree yada diğer adıyla hash tree de birden fazla verinin tek bir hash fonksiyonu olana kadar ikili hash fonksiyonlarının alınmasıyla oryaya çıkar. 

Aşağıdaki görselde L1, L2, L3 ve L4 olarak gördüğünüz veriler bizim ana verilerimiz. Biz bu verilerin tamamının tek satırlık bir çıktıya dönüşmesini istiyoruz.

Merkle tree algoritması ilk olarak bu verilerin (L1, L2…) hash fonksiyonlarını alarak 64 karakterlik bir çıktı elde ediyor. Bu ilk elde edilen hash çıktılarına leaf yani yaprak deniliyor. Bunlar ağacımızın en uç verileri. Daha sonra bu hash çıktıları birleştirerip, bu birleşimin de hash fonksyionunu alarak 2 adet hash çıktıdan 1 adet hash çıktı elde ediyoruz. Bunu en son elimizde bir adet çıktı kalana kadar tekrarlıyoruz. Son olarak elde ettiğimiz çıktıya ise Root yani kök deniliyor. Leaf ve root haricinde bir de Merkle Proof dediğimiz bir veri daha var, bunu da en sonda bahsediyor olacağım.

Merkle ağacımızın yapraklarını oluşturan girdi verilerinden herhangi birinde en ufak bir değişiklik olursa Merkle root yani ağacımızın kökü tamamen bambaşka bir çıktı haline geliyor. Gelin basit bir örnekle bunu test edelim.

Diyelim ki herkesin ne kadar bitcoin’i olduğunu sakladığım bir veri setim var. Ben bu veri setini merkle tree ile tek bir köke çevirdiğimde yukarıda gördüğünüz gibi bir kök (root) ortaya çıkıyor. İlk başta verilerimin hashlerini alıp yapraklarımı(hash) oluşturuyorum. Daha sonra bu yaprakları birleştirip tekrar hash’ini alarak yeni bir hash çıktısı alıyorum. Bu işlemi tekrarladığımda son bir hash ortaya çıkıyor. Bu da benim merkle ağacımın kökü oluyor. Aradaki hash çıktılarını uzun oluyor diye kısalttım fakat kontrol ederseniz gerçek hash çıktıları. (keccak256 ile)

Diyelim ki ben bir düzenbazlık yaptım ve Ahmet’in 5 bitcoin’i varken onu 4 olarak değiştirdim. Böyle bir durumda Ahmet için aldığım yaprak (hash) bambaşka bir hash olacak. Dolayısıyla onu birleştirdiğim bir sonraki hash ve en sonunda ortaya çıkan kök de bambaşka bir çıktı olacak. Böylece herkes benim bir düzenbazlık yaptığımı anlayabilecek. Çünkü onlara gösterdiğim veri ile asıl verinin merkle kökü farklı! 

İşte bugün yaşanan bir borsanın kullanıcılarının paralarını farklı şekillerde kullanması, dışarı aktarması gibi durumlar Merkle tree ile fark edilebilecek duruma gelecek. Kripto piyasasında bir felakete yol açan bu olay borsaların rezervlerinin kanıtını merkle tree ile kullanıcılara göstererek, fonların ellerinde olduğunu, bir yerlerde kullanmadıklarını kanıtlamış olacaklar. Merkle ağacının pek çok alanda pek çok farklı kullanım şekli vardır. Blockchain ile ilgili olanlardan bazılarına göz atalım.

Bitcoin

Tıpkı yukarıdaki örneklerde gördüğünüz gibi Bitcoin de hemen hemen aynı sistemi kullanarak tüm transferlerin merkle ağacığını oluşturarak bu ağacın kökünü kaydeder. Mevcut root ile birlikte bir önceki bloğun hash çıktısı da yeni bloğa eklenir ve yeni bloğun da bir hash çıktısı alınır. Bu şekilde her blok bir önceki bloğun hash çıktısını içinde barındırır.

Eğer herhangi bir bloğun, herhangi bir transferinde bir değişilik yaşanırsa, takip eden tüm hash çıktıları da yukarıda gördüğümüz örnekteki gibi değişeceği için yepyeni bir blokzincir oluşturur. Dolayısıyla geçersiz bir zincir yaratmış olursunuz. Bitcoin’in ve blokzincirin nasıl çalıştığı ayrıntılı ve uzun bir konu fakat merkle tree Bitcoin’in temelinde oturan bir yapıdır.

Whitelist

NFT dünyasında fırsatları kovalayan herkes mutlaka Whitelist veya bir diğer adıyla Allowlist kavramı ile karşı karşıya gelmiştir. Whitelist dediğimiz şey, adreslerin içinde bulunduğu bir merkle ağacıdır. 

Blockchainde veri depolamak inanılaz derecede maliyetli bir iş olduğu için çok sayıda adresin bir işlem için akıllı kontratta depolanması yapılmaz. Onun yerine bu adresler bir merkle ağacına dönüştürülür ve bu ağacın kökü (merkle root) akıllı kontrata kaydedilir. Böylece 10,000 yada 100,000,000 adresi 64 karakterden oluşan kısa bir veriye çevirirz.

Peki siz ağacın kökünü kontrata yüklediniz ve bir adres geldi, kontrattan NFT mintlemek istedi. Kontrat sadece köke ve gelen adrese bakarak bu adresin listede olup olmadığını bilemez. Sonuçta kök dediğimiz şey 64 karakterden oluşan küçük bir veri. Peki o zaman bir verinin bize verilen kökün içinde olup olmadığını bütün merkle ağacını depolamadan nasıl bilebiliriz?

İşte burada devreye merkle proof dediğimiz kanıtlar gidiyor. Şifreleme algoritmasına biz merkle ağacının kökünü, kanıtımızı ve kontrolünü yapmak istediğimiz adresin hash’ini vererek bu adresin verdiğimiz kökün içerisinde olup olmadığını kontrol edebiliyoruz. Merkle ağacı ile whitelist oluşturma hakkındaki yazdığımızda linkini buraya ekleyeceğim ve bunu nasıl akıllı kontrata kodlayacağımızı oradan öğrenebileceksiniz. Peki nasıl çalışır bu merkle proof?

Merkle Proof

Merkle proof yani merkle kanıtı, merkle ağacındaki her veri için ayrı üretilir. Yani Whitelist örneğimizden yola çıkacak olursak A adresinin kanıtı ile B, C, D adreslerinin kanıtı birbirinden farklı olur. Merkle kanıtı, ağacın tamamı olmadan, sadece ihtiyacımız olan ara hash’leri barındıran bir hash dizisidir. Hemen bir örnekle gösterelim.

Yukarıdaki ağacımızın içinde bu sefer kimin kaç Bitcoin’e sahip olduğu değil de adresler yazsın. Yeşil olan kutudaki adres geldi bize dedi ki, ben Whitelist’teyim, bana NFT’mi ver. Biz kontrata sadece en tepedeki kökü yüklemiştik. O zaman biz, mavi kutudaki hashlere sahip olursak, mavi-çizgili hashleri oluşturabiliriz. Yani kökü oluşturabiliriz. Oluşturduğumuz kök ile kontrata yüklediğimiz kök aynı ise bize gelen adres Whitelist’tedir, NFT’sini veririz. 

Merkle proof’u kullanarak doğrulama yapan fonksiyonun işlem sıralaması şu şekildedir

1. Gelen adresten (yeşil kutu) o adresin yaprağını (1 numara) oluştururum.

2. Bu hash ile eşleyen soldaki mavi hash (2 numara) ile üstteki hashi (3 numara) oluştururum.

3. Yine bunun da sağındaki mavi hash  (4 numara) ile üstteki hashi (5 numara, kök) oluştururum.

Son oluşturduğum hash gördüğünüz gibi kök. Eğer kontrata yüklediğim kök ile bu adres ve bu adresin bana verdiği proof ile oluşturduğum kök aynı ise, demek ki bu adres bu ağacın içerisinde var.

Burada fark etmeniz gereken nokta şu: Kontrata sadece kökü yüklüyoruz. Blockchain üzerinde sadece 64 karakterlik bir kökü depoluyoruz. Geriye kalan adres ve bu adresle bize verilen kanıt, blockchain üzerinde depolanmıyor. Kontrat bu veriyi alıyor, işlemini yapıyor ve sonra veriyi atıyor. Dolayısıyla sadece 64 karakter ile sınırsız uzunlukta bir adres listesini kontratta depolayabiliyoruz. Fakat liste ne kadar uzun olursa yukarıda yaptığım işlemler o kadar uzayacak ve her bir işlem blockchainde GAS dediğimiz bir işlem maliyeti olduğu için, transfer ücretleri artacaktır. Bu nedenle 10 bin adreslik bir liste ile 100 milyon adreslik bir listenin zincir üzerinde depolama maliyeti aynı olsa da, işlem maliyeti çok fark edecektir.

4 tane adresin olduğu bir ağaçta 2 tane (mavi) hash’i bana verirseniz kökü oluşturabilirim. Peki ya daha fazla adrese sahip olduğumuz listelerde kanıtımız ve işlem uzunluğumuz ne kadar fark edecektir?

Gördüğünüz 16 adreslik bir ağaçta, siz 4 adet hash ile herhangi bir adres için ağacı tamamlayıp, doğrulayabiliyorsunuz. Diyelim ki 10 bin adresten oluştan bir whitelist’iniz var. Her adres için oluşturulan proof 14 adet hash içerecek. Proof’un kaç adet olacağını hesabını log₂(x) ile yapabilirsiniz. X adres/veri sayısı.

100,000 adet adresin kayıt olduğu bir ağacı ise sadece 17 adet hash ile doğrulayabileceksiniz. Gördüğünüz gibi şifreleme algoritmaları sayesinde onbinlerce veriden oluşan büyük bir veri ağacını çok küçük bir veri grubu ile doğruyalabiliyoruz ve blockchain üzerindeki masrafımız ve yükümüz minimum seviyeye iniyor. 

Akıllı kontratlar üzerinde Whitelist oluşturarak NFT koleksiyonumuzda belirliediğimiz adreslere ayrıcalıklar tanımanın kodlarla birlikte bir örneğini de bir başka yazımızda paylaşacağız. Zaman içerisinde SCDEVSTR Lab olarak kütüphanemizi zenginleştirip, Türk geliştiricilerin tüm ihtiyaçlarını bulabileceği bir yer haline getireceğiz.

Umarım anlaşılır bir dil kullanabilmişimdir. Hem Türkçe hem İngilizce terimleri karışık kullandım ki, İngilizcesine yabancılık çekmeden Türkçemizi de koruyabilelim.

Yazı ile ilgili geri dönüşlerinizi veya herhangi bir konu ilgili isteklerinizi yorumlardan bizleree iletebilirsiniz. Faydalı olması dileğiyle, bizi takip etmeyi unutmayın, hoşça kalın.

~ Bora