Merkle ağacı

Kriptografi ve bilgisayar bilimlerinde, Hash ağacı ya da Merkle ağacında her yaprak düğümü veri blokunun özet değerini, her yaprak olmayan düğüm ise kendi alt düğümlerinin kriptografik özet değerlerini içerir. Merkle ağacı büyük veri yapılarının verimli ve güvenli bir şekilde doğrulanmasını sağlar. Merkle ağaçları, özet listeleri ve özet zincirlerinin genelleştirilmiş halidir. Aynı isimdeki Merkle İmza Algoritması, Merkle özet değeri ağacını kullanmaktadır.

Bir yaprak düğümün verilen Merkle ağacının bir parçası olduğunu göstermek için, ağaçtaki yaprak düğümü sayısının logaritması kadar bir takım hesaplama yapılması gerekmektedir;^[1] bu da yaprak düğümü sayısı kadar işlem gerektiren özet listeleriyle çelişir.

Merkle ağacı kavramı adını 1979 yılında Ralph Merkle'in patentiyle almıştır.^[2]^[3]

Kullanım

Merkle ağaçları bilgisayarlar arası transfer edilen ya da bilgisayarlarda saklanan, işlenen her türlü verinin doğrulanmasında kullanılabilir. Kişiden kişiye (P2P) ağlarda alınan veri bloklarının hasarsız, değiştirilmemiş ve hatta sahte olup olmadığını anlamamıza yardımcı olurlar.

Merkle ağaçları kriptografik hash fonksiyonlarında kullanılmaktadır. Merkle ağaçları aynı zamanda IPFS, Btrfs ve ZFS dosya sistemlerinde^[4] (veri bozulmalarını saymak için^[5]), Dat protokolünde, Apache Wave protokolünde,^[6] Git ve Mercurial dağıtık versiyon kontrol sistemlerinde, Tahoe-LAFS yedek sisteminde, Zeronet, Bitcoin ve Ethereum P2P ağlarında,^[7] seritfika şeffaflığı sisteminde ve Apache Cassandra, Riak, Dynamo^[8] gibi birçok NoSql sisteminde kullanılmaktadır.^[9]

Satoshi Nakamoto Bitcoin uygulamaya geçirildiği noktada Merkle ağaçlarını aşırı boyutlu özet fonksiyonlarının Hızlı Merkle ağaçları kullanarak sıkıştırma aşamasında hafifletmiştir.

Genel bakış

Merkle ağaçları bir dosya veya dosya grubu örneğinde olduğu gibi yaprakları veri bloklarının özeti olan bir özet ağacıdır. Ağaçta bulunan düğümler altlarındaki kendi ilgili çocuklarının özet değerleri alınmış halidir. Örneğin, resimde görüldüğü gibi özet değeri 0, altından barındırdığı özet değeri 0-0 ve özet değeri 0-1 birleşiminin özet değerinin hesaplanması sonucudur. Yani, işaretinin birleştirme olduğu özet 0 = özet(özet 0-0 özet 0-1) ifadesi ile anlatımı ifade edebiliriz.

Çoğu Merkle ağacı uygulaması ikilidir (her düğüm altındaki iki alt düğüm); ancak her düğümün altında çok daha fazla alt düğümde kullanılabilir.

Genellikle, özet değeri için SHA-2 gibi bir kriptografik özet fonksiyonu kullanılır. Merkle ağacı 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 özet değeri (veya kök özet değeri veya ana özet değeri) bulunur. Bir p2p ağında bir dosya indirmeden önce, çoğu durumda üst özet değeri indirilecek dosyalara iyi tavsiyelerde bulunduğu bilinen bir arkadaş veya bir İnternet sitesi gibi güvenilir bir kaynaktan edinilmiş olur. Üst özet değeri varsa, Merkle ağacı, p2p ağındaki herhangi bir eş gibi güvenilir olmayan herhangi bir kaynaktan alınabilir. Daha sonra alınan özet değeri ağacı güvenilir üst özet değeri ile karşılaştırılır ve özet değeri ağacı hasar görmüş veya sahte ise, program en iyi özet değeri ile eşleşene kadar başka bir kaynaktan başka bir Merkle ağacı denenecektir.

Özet değeri listesinden temel farkı, aynı anda her ağacın bir dalının indirilebilmesi ve anında kontrol edilebilmesidir. Örneğin, yukarıdaki resimde, veri bloku 2 bütünlüğü, ağaçta özet 0-0 ve özet 1 içeriyorsa veri blokunun özet işlemi yapılarak ve sonucu özet 0-0 ve ardından özet 1 ile tekrarlı birleşimiyle hemen doğrulanabilir. Benzer şekilde, ağaçta özet 1-1 ve özet 0 varsa, veri bloku 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. Özet değeri dosyası çok büyükse, böyle bir özet ağacı veya özet listesi 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 preimage saldırısı

Merkle özet kökü (hash root), bir saldırganın aynı Merkle özet köküne sahip olan orijinal farklı bir belge oluşturduğu ikinci preimage saldırısı sağlayan ağaç derinliğini göstermez. Yukarıdaki örnekte, bir saldırgan, iki veri bloku içeren yeni bir belge oluşturabilir; ilk özet 0-0 özet 0-1 ve ikincisi özet 1-0 özet 1-1 şeklindedir. Sertifika Şeffaflığı Sisteminde basit bir düzeltme tanımlanmıştır: yaprak düğüm özet değerleri hesaplanırken, özet verilere bir 0x00 bayt ön eklenir ve iç düğüm özet değerleri hesaplanırken 0x01 eklenir. Merkle 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 özet ağaç derinlik ön eklerinin özet değerini alır, öncesi kullanarak ağaç derinliğini sınırlar; böylece ayıklanan özet zincir yalnızca ön ek her adımda azalırsa ve yaprağa ulaşıldığında hala pozitif ise geçerli olarak tanımlanır.

Kaplan ağacı özeti

Kaplan ağaç özeti (Tiger Tree Hash) yaygın olarak kullanılan bir özet ağacı şeklidir. Genellikle 1024 bayt veri bloku boyutları ve Kaplan özeti ile ikili özet ağaç (düğümün altında kendine ait iki düğüm) yapısıyla kullanılır.

Kaplan ağaç özetleri, Gnutella, Gnutella2, Direct Connect P2P dosya paylaşım protokollerinde ve Phex, BearShare, LimeWire, Shareaza, DC ve Valknut gibi dosya paylaşım uygulamalarında kullanılmaktadır.

Örnek

Base32: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN: urn:tree:tiger:RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

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

Ayrıca bakınız

İkili ağaç
Blok Zinciri
Dağılmış komut çizelgesi
Komut Çizelgesi
Hash trie
Linked timestamping

Başvurular

^ Becker, Georg (18 Temmuz 2008). "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis" (PDF). Ruhr-Universität Bochum. s. 16. 22 Aralık 2014 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 20 Kasım 2013.
^ Merkle, R. C. (1988). "A Digital Signature Based on a Conventional Encryption Function". Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science. 293. s. 369. doi:10.1007/3-540-48184-2_32. ISBN 978-3-540-18796-7.
^ US patent 4309569, Ralph Merkle, "Method of providing digital signatures", Jan 5, 1982 tarihinde yayımlandı, assigned to The Board Of Trustees Of The Leland Stanford Junior University
^ Bonwick, Jeff. "ZFS End-to-End Data Integrity". Jeff Bonwick's Blog. 6 Mayıs 2017 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018.
^ Likai Liu. "Bitrot Resistance on a Single Drive". likai.org. 8 Nisan 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018.
^ "General Verifiable Federation". Google Wave Protocol. 8 Nisan 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018.
^ Koblitz, Neal; Menezes, Alfred J. (Ocak 2016). "Cryptocash, cryptocurrencies, and cryptocontracts". Designs, Codes and Cryptography. 78 (1). ss. 87-102. doi:10.1007/s10623-015-0148-5.
^ Adam Marcus. "The NoSQL Ecosystem". aosabook.org. 8 Nisan 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018. When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data.
^ Kilian, J. (1995). "Improved efficient arguments (preliminary version)". CRYPTO.

Konuyla ilgili yayınlar

Merkle tree patent 4,309,569
– Hash ağaç yapısına ve tek kullanımlık imzaların bu yapıyla kullanımına dair açıklamalar
Tree Hash EXchange format (THEX) – Tiger ağaçlarının detaylı anlatımı
Efficient Use of Merkle Trees 17 Nisan 2017 tarihinde Wayback Machine sitesinde arşivlendi. – Merkle ağaçlarının asıl amacı olan birden fazla tek kullanımlık Lambort imzasının ele alınmasının RSA Labs tarafından açıklanması

Dış bağlantılar

Dinamik olarak yeniden boyutlandırılmış ikili SHA-256 hash ağacının C dilinde uygulaması (Merkle Ağacı)
J 12 Aralık 2020 tarihinde Wayback Machine sitesinde arşivlendi. ava dilinde Merkle Ağacı uygulaması
Tiger Tree Hash (TTH) C# dilinde kaynak kodu 5 Ağustos 2020 tarihinde Wayback Machine sitesinde arşivlendi., Gil Schmidt
Tiger Tree Hash (TTH) C ve Java 18 Kasım 2019 tarihinde Wayback Machine sitesinde arşivlendi. dilinde uygulamaları
RHash 7 Haziran 2019 tarihinde Wayback Machine sitesinde arşivlendi., TTH ve TTH magnet bağlantı linklerinin hesaplanmasını sağlayan açık kaynak kodlu komut satırı aracı

[1] Becker, Georg (18 Temmuz 2008). "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis" (PDF). Ruhr-Universität Bochum. s. 16. 22 Aralık 2014 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 20 Kasım 2013.

[2] Merkle, R. C. (1988). "A Digital Signature Based on a Conventional Encryption Function". Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science. 293. s. 369. doi:10.1007/3-540-48184-2_32. ISBN 978-3-540-18796-7.

[3] US patent 4309569, Ralph Merkle, "Method of providing digital signatures", Jan 5, 1982 tarihinde yayımlandı, assigned to The Board Of Trustees Of The Leland Stanford Junior University

[4] Bonwick, Jeff. "ZFS End-to-End Data Integrity". Jeff Bonwick's Blog. 6 Mayıs 2017 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018.

[5] Likai Liu. "Bitrot Resistance on a Single Drive". likai.org. 8 Nisan 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018.

[6] "General Verifiable Federation". Google Wave Protocol. 8 Nisan 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018.

[7] Koblitz, Neal; Menezes, Alfred J. (Ocak 2016). "Cryptocash, cryptocurrencies, and cryptocontracts". Designs, Codes and Cryptography. 78 (1). ss. 87-102. doi:10.1007/s10623-015-0148-5.

[8] Adam Marcus. "The NoSQL Ecosystem". aosabook.org. 8 Nisan 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Nisan 2018. When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data.

[9] Kilian, J. (1995). "Improved efficient arguments (preliminary version)". CRYPTO.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]