İçeriğe atla

Merkle ağacı

İkili hash ağacı örneği. 0-0 ve 0-1 hash değerleri sırasıyla L1 ve L2 veri bloklarının hashleridir. Hash 0 ise 0-0 ve 0-1 hashlerinin birleşiminin hashi alınmasıyla oluşmuştur.

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

  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. 

Konuyla ilgili yayınlar

Dış bağlantılar

İlgili Araştırma Makaleleri

MD5, yaygın olarak kullanılan bir kriptografik özet fonksiyonudur. Girilen verinin boyutundan bağımsız olarak, 128-bit özet değeri üretir. MD5 ilk olarak kriptografik özet fonksiyonu olarak tasarlanmış olmasına rağmen geniş çaplı güvenlik açıkları tespit edilmiştir. Veri bütünlüğünün sağlandığını kontrol etmek için sağlama değeri üretmek amacıyla kullanılır. Ancak sadece kasıtsız yapılan değişiklere karşı kullanışlıdır.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit kendini-dengeleyen ikili arama ağacı veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili B-ağaçları" olarak adlandıran Rudolf Bayer tarafından bulunmuştur. Bugünkü ismini 1978 yılında Leo J. Guibas ve Robert Sedgewick tarafından yayımlanan bir makaleyle almıştır. Karmaşık ancak çalışma süresi en kötü durumda bile iyi ve pratikte verimlidir: O(log n) (n ağaçtaki eleman sayısını gösterir) zamanda arama, ekleme ve çıkarma işlemleri yapabilir.

<span class="mw-page-title-main">Filogenetik ağacı</span> evrimsel ilişkileri gösteren bir grafik ağacı

Bir filogenetik ağaç veya evrim ağacı farklı biyolojik türler veya ortak bir atası olan diğer varlıkların arasındaki evrimsel ilişkileri gösteren bir grafik ağaçtır. Bir filogenetik ağaçta, iki dalın ayrıldığı her bir düğüm noktası altsoyların ortak atasını temsil etmektedir. Bazı ağaçların dal uzunlukları alt türlerin birbirinden evrimsel olarak ayrışma zamanı ile ilişkilidir. Her düğüm bir takson, yani bir taksonomi birimidir. İç düğümler geçmişte var olmuş taksonlara ait olup doğrudan gözlemlenemeyeceği için hipotetik taksonlar olarak adlandırılır.

Döngüsel artıklık denetimi, çoğunlukla sayısal şebekelerde ve depolama cihazlarında kullanılan ve ham veride yapılan hatalı değişimleri algılayan, uygulaması kolay ve güvenliği güçlü bir hata bulma yöntemidir.

<span class="mw-page-title-main">Dal-yaprak grafikleri</span>

Dal-yaprak grafikleri, betimsel istatistik ve "istatistiksel grafik" konusu olup sayısal olarak elde edilen verilerin grafik olarak görsel şekilde özetlemek amacıyla çizilir. Bu çizimi tek değişkenli verileri incelerken kullanılır. Bu gösterim şekli veri setinin yapısını, örüntüsünü veya genel eğilimini gösterir.

Kriptografide, SHA-1 NSA tarafından dizayn edilmiş ve NIST tarafından yayınlanmış bir Amerika Birleşik Devletleri Federal Bilgi İşleme Standartı 'nda bir kriptografik özet fonksiyonudur. SHA-1, mesaj özeti olarak da bilinen 160-bit özet değeri üretir. Bir SHA-1 özet değeri genellikle 40 basamaklı bir onaltılık sayı olarak üretilir.

<span class="mw-page-title-main">Kriptografik özet fonksiyonu</span>

Kriptografik özet fonksiyonu çeşitli güvenlik özelliklerini sağlayan bir özet fonksiyonudur. Veriyi belirli uzunlukta bir bit dizisine, (kriptografik) özet değerine, dönüştürür. Bu dönüşüm öyle olmalıdır ki verideki herhangi bir değişiklik özet değerini değiştirmelidir. Özetlenecek veri mesaj, özet değeri ise mesaj özeti veya kısaca özet olarak da adlandırılır.

Mesaj doğrulama kodu kriptografi biliminde bir mesajın doğruluğunu kanıtlamak için kullanılan küçük boyutlu bilgilerdir.

Treap ya da tree heap, arama, ekleme, silme gibi temel işlemler için log(n) zamanı garanti eden dinamik bir ikili arama ağacıdır. İkili arama ağacına sıralı şekilde ekleme yapılırsa binary arama ağacı bağlantılı listeye dönüşür ve arama ancak O(n) zamanda yapılabilir. Bu durumu ortadan kaldırmak için treap her düğümde binary arama ağacında kullanılan asıl değere ek olarak bir de rastgele olusturulmus bir anahtar tutar. Treap veri yapısı hem asıl değere göre veri ağacının kurallarına uyularak hem de rastgele anahtar ata düğümden küçük olacak şekilde kurulur.

SHA-2, ABD Ulusal Güvenlik Ajansı (NSA) tarafından tasarlanmış kriptografik özet (hash) fonksiyonları kümesidir. Kriptografik özet fonksiyonları, hesaplanmış “özet” ile bilinen ve beklenen özet değerinin karşılaştırılmasıyla, dijital veri üzerinde yürüyen matematiksel operasyonlardır. Özet fonksiyonları ile bir kişi verinin bütünlüğüne karar verebilir. Örneğin, yüklenmiş bir dosyanın özet değerini hesaplamak ve sonucu önceden açıklanmış özet sonucu ile karşılaştırmak, yüklemenin değiştirilip değiştirilmediğini veya üzerinde oynama yapılıp yapılmadığını gösterebilir. Kriptografik Hash fonksiyonlarının kilit noktası çakışma dirençleridir: hiç kimse aynı özet çıktısı veren iki farklı girdi bulamamalıdır.

<span class="mw-page-title-main">HMAC</span>

Kriptografide, HMAC, kriptografik özet fonksiyonu ve gizli bir kriptografik anahtar içeren bir mesaj doğrulama kodu türüdür. Diğer MAC türleri gibi, HMAC de hem veri bütünlüğünü kontrol etmek hem de mesaj içeriğini onaylamakta kullanılabilir. HMAC in hesaplanmasında herhangi bir kriptografik özet fonksiyonu kullanılabilir. Örneğin, HMAC in hesaplanmasında MD5 veya SHA-1 özet fonksiyonu kullanılması durumunda, ilgili MAC algoritması da buna uygun olarak HMAC-MD5 veya HMAC-SHA1 olarak isimlendirilebilir. HMAC'in kriptografik saldırılara karşı dayanıklılığı, kullanılan özet fonksiyonunun dayanıklılığına, elde edilen özetin boyutuna, kullanılan kriptografik anahtarın boyutuna ve kalitesine bağlıdır.

Kriptografi 'de bir 'Lamport imzası' veya 'Lamport bir defalık imza şeması' dijital imza oluşturmak için kullanılan bir yöntemdir. Lamport imzaları, kriptografik olarak güvenli herhangi bir tek yönlü fonksiyon ile oluşturulabilir; genellikle bir Kriptografik özet fonksiyonu kullanılır.

Emek ispatı , denial-of-service saldırıları ve bir ağ üzerinde bulunan spam mesajlar ile servislerin kötüye kullanımını, istemciden bir miktar iş yapmasını isteyerek önleme amaçlı ekonomik bir ölçüdür. Bu kavram, Cynthia Dwork ve Moni Naor tarafından 1993 tarihli bir dergi makalesiyle ilk kez ortaya konmuştur. "Emek İspatı" terimi ya da POW ilk kez Markus Jakobsson ve Ari Juels tarafından 1999 tarihli bir yayında literatüre kazandırılarak resmîleştirilmiştir. Emek ispatı sisteminin bir para birimine değer kazandırmak amacıyla kullanıldığı ilk örneklerden biri Solomon Adalarında kullanılan shell moneydir.

Merkle imzası, anahtarlama ağaçları ve sayısal imza şemalarını birleştiren bir veri doğrulama yapısıdır. Özet değeri tabanlı kriptografidir ve Merkle ağacı da denen özet değeri ağacını kullanmaktadır. Verileri Lampart imza algoritması gibi tek kullanımlık şekilde imzalar. Ralph Merkle tarafından 1970 sonu itibarıyla geliştirilmiştir ve RSA, Dijital İmza Algoritması gibi geleneksel dijital imzalara alternatif olmuştur.

Kriptografide, doldurma birçok farklı uygulamaya işaret eder.

<span class="mw-page-title-main">AVL ağacı</span>

Bilgisayar bilimlerinde bir AVL ağacı kendi kendini dengeleyen bir İkili arama ağacıdır. Bu tip Veri yapılarının icat edilmiş ilk örneğidir. Bir AVL ağacında, iki çocuk alt ağacın uzunluk farklı en fazla bir olabilir; Eğer herhangi bir anda fark birden fazlaysa, dengeleme yapılarak bu özellik korunur. Arama, ekleme ve silme işlemlerinin hepsi hem ortalama hem de en kötü durumlarda O(log n) zaman sürer, burada harfi operasyon öncesindeki düğüm(node) adetidir. Ekleme ve çıkarma işlemleri ağacın bir veya daha fazla ağaç rotasyonları ile dengelenmesini gerektirebilir.

Karar ağacı, bir kurum veya kuruluş tarafından tercihlerin, risklerin, kazançların ve hedeflerin anlaşılmasına yardımcı olan bir teknik türüdür. Aynı zamanda birçok önemli yatırım sahalarında uygulanabilen, birbiriyle bağlantılı şans olaylarıyla ilgili olarak çıkan çeşitli karar noktalarını incelemek için kullanılan bir karar destek aracıdır. Yalnızca koşullu kontrol ifadeleri içeren bir algoritmayı görüntülemenin bir yoludur.

<span class="mw-page-title-main">Dağıtılmış defter teknolojisi</span>

Dağıtılmış defter teknolojisi, ekonomi, toplum ve endüstride organizasyon ve işbirliğini değiştirme potansiyeline sahip bilgi teknolojileri alanında en umut verici yeniliklerden biridir. Dağıtılmış defter teknolojileri, değer yaratma ve yakalama için yeni imkanlar yaratarak, klasik hale gelen ticari işlem kavramlarını yeniden oluşturmaktadır. DLT; verilerin, bir ağ üzerinde bulunan birden fazla alanda erişilebilir, güncellenebilir, doğrulanabilir olmasına imkan sağlayan, merkeziyetsiz, teknolojik altyapıdır. Bir tür konsensüs mekanizması olarak tanımlanır. Merkeziyetsiz yapılarda herhangi bir otorite söz konusu olmadığı için verilerin fikir birliği içerisinde saklanması, erişilmesi, güncellenmesi ve doğrulanması gerekir.

Kriptografide, bir kriptografik hash üzerindeki bir çarpışma saldırısı, aynı hash değerini üreten iki girdi bulmaya çalışır, yani bir hash çarpışması. Bu, belirli bir hedef karma değerinin belirtildiği bir ön görüntü saldırısı nın aksine bir saldırıdır. Kabaca iki tür çarpışma saldırısı vardır:


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.