Merkle Ağacı Nedir

Merkle Ağacı Nedir

Son güncelleme: Eylül 3, 2017

Merkle ağacı (Merkle Tree) ya da hash ağacı ya da Merkle kökü, kriptografi ve bilgisayar bilimlerinde, her yaprak node’un bir veri bloğu ile etiketlendiği ve her yaprak-olmayan node’un, alt node’larının kriptografik hash ile etiketlendiği bir ağaçtır. Hash ağaçları, büyük veri yapılarının içeriğinin verimli ve güvenli bir şekilde doğrulamasına izin verir. Hash ağaçları, hash listelerin ve hash zincirlerin genelleştirilmesidir.

Bir yaprak node’un belirli bir ikili hash ağacının bir parçası olduğunun gösterilmesi, ağacın yaprak node’larının sayısının logaritması ile orantılı olarak bir dizi hash hesaplamayı gerektirir; bu rakam, yaprak node’ların sayısıyla orantılı olan hash listelerle çelişir.

Merkle ağacı konseoti ismini 1979’da patentini alan Ralph Merkle‘den almıştır.

Merkle Ağacı Kullanımı

Merkle ağaçları, bilgisayarlar arasında saklanan ve taşınan her türlü veriyi doğrulamak için kullanılabilir. Şu anda hash ağaçlarının ana kullanımı, eşler arası bir ağdaki diğer eşlerden alınan veri bloklarının hasarsız ve değiştirilmemiş olarak alınmasını ve hatta diğer eşlerin yalan söylemediğini ve sahte bloklar göndermediğini kontrol etmektir. Hash ağaçlarını güvenilir bilgi işlem sistemlerinde kullanmak için öneriler de yapıldı. Hash ağaçlar ayrıca hash tabanlı şifrelemede kullanılır.

Merkle ağacı, IPFS, Btrfs ve ZFS dosya sistemlerinde (veri bozulmalarını karşılamak için), BitTorrent protokolü, Dat protokolü, Apache Wave protokolü, Git dağıtımlı revizyon kontrol sistemi, Tahoe-LAFS yedekleme sistemi, Bitcoin ve Ethereum peer-to Peer ağları, Sertifika Şeffaflığı framework’ü ve Apache Cassandra, Riak ve Dinamo gibi bir dizi NoSQL sisteminde kullanılmaktadır.

Genel Bakış

Merkle ağacı, yaprakların veri bloklarının hashlerinin olduğu bir hash ağacıdır, örneğin bir dosya veya dosya grubudur. Ağacın ilerisinde yer alan node’lar, ilgili çocuklarının kareleri olur. Örneğin, aşağıdaki görüntüde hash 0, hash 0-0 ve hash 0-1’in birleşimini hash sonucudur. Yani hash 0 = hash (hash 0-0 + hash 0-1) burada + bir birleştirme anlamına gelir.

Merkle Ağacı

Çoğu Merkle ağacı uygulaması ikilidir (her node altındaki iki alt node); ancak her node’un altında çok daha fazla alt node da kullanılabilir.

Genellikle, hash için SHA-2 gibi bir kriptografik hash işlevi kullanılır. Merkle ağacın yalnızca istem dışı hasarlara karşı korunması gerekiyorsa, CRC’ler gibi daha az güvenli checksumlar kullanılabilir.

Bir Merkle ağacın tepesinde bir üst hash (veya kök hash veya ana hash) bulunur. Bir p2p ağında bir dosya indirmeden önce, çoğu durumda en iyi hash, güvenilir bir kaynaktan, örneğin indirilecek dosyalara iyi tavsiyelerde bulunduğu bilinen bir arkadaş veya bir web sitesinden edinilir. Üst hash varsa, Merkle ağacı, p2p ağındaki herhangi bir eş gibi güvenilir olmayan herhangi bir kaynaktan alınabilir. Daha sonra alınan hash ağacı güvenilir üst karma ile karşılaştırılır ve hash ağacı hasar görmüş veya sahte ise, program en iyi hash ile eşleşene kadar başka bir kaynaktan başka bir Merkle ağacı denenecektir.

Hash listesinden temel farkı, aynı anda her ağacın bir şubesinin indirilebilmesi ve derhal kontrol edilebilmesidir. Örneğin, yukarıdaki resimde, veri bloğunun bütünlüğü, ağaçta hash 0-0 ve hash 1 içeriyorsa veri bloğunun hash işlemi yapılarak ve sonucu hash 0-0 ve ardından hash 1 ile yineleyerek birleştirerek hemen doğrulanabilir. Benzer şekilde, ağaçta hash 1-1 ve hash 0 varsa, veri bloğu 3’ün bütünlüğü doğrulanabilir. Bu, çok küçük veri bloklarında dosyaları ayıracak kadar verimli olduğu için bir avantaj olabilir. Böylece yalnızca küçük bloklar olması gerekir ve zarar görürlerse yeniden indirilirler. Hash dosyası çok büyükse, böyle bir hash ağaç veya hash liste oldukça büyük olur. Ancak bu bir ağaçsa, küçük bir dal hızlı bir şekilde indirilebilir, dalın bütünlüğü kontrol edilebilir ve daha sonra veri bloklarının indirilmesi başlatılabilir.

İkinci ters görüntü saldırısı

Merkle hash kökü, bir saldırganın aynı Merkle hash köküne sahip olan orijinalden farklı bir belge oluşturduğu ikinci preimage (ters görüntü) saldırısı sağlayan ağaç derinliğini göstermez. Yukarıdaki örnekte, bir saldırgan, iki veri bloğu içeren yeni bir belge oluşturabilir; ilk hash 0-0 + hash 0-1 ve ikincisi hash 1-0 + hash 1-1 şeklindedir.

Sertifika Şeffaflığı framework’ünde basit bir düzeltme tanımlanmıştır: yaprak node hash’leri hesaplanırken, hash verilere bir 0x00 bayt ön eklenir ve iç node hashleri hesaplanırken 0x01 eklenir. Hash ağacının boyutunu kısıtlamak bazı resmi güvenlik belgelerinin bir ön şartıdır ve bazı kanıtları sıkılaştırmaya yardımcı olur. Bazı uygulamalar hash ağaç derinlik öneklerini hashler öncesi kullanarak ağaç derinliğini sınırlar; böylece ayıklanan hash zincir yalnızca önek her adımda azalırsa ve yaprağa ulaşıldığında hala pozitif olarak tanımlanır.

Kaplan ağacı hash’i

Kaplan ağaç hash’i (Tiger Tree Hash) yaygın olarak kullanılan bir hash ağacı şeklidir. Bir ikili hash ağaç (her node’un altındaki iki alt node) kullanır, genellikle 1024 baytlık bir veri bloğu boyutuna sahiptir ve kaplan hash’ini kullanır.

Kaplan ağaç hash’leri, Gnutella, Gnutella2 ve Direct Connect P2P dosya paylaşım protokollerinde ve Phex, BearShare, LimeWire, Shareaza, DC ++ ve Valknut gibi dosya paylaşım uygulamalarında kullanılır.

Örnek:

Base32: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN: urn:tree:tiger:RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

magnet: magnet:?xt=urn:tree:tiger:RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Bir Cevap Yazın