Merkle ağacı, büyük veri yapılarının içeriğini verimli ve güvenli bir şekilde doğrulamayı mümkün kılan ikili bir ağaçtır. Bu ağacın konsepti 1982 yılında Amerikalı kriptograf Ralph Merkle tarafından önerildi ve patenti alındı.
Karma uzunluğu herhangi bir miktardaki giriş verisi için aynı kalır. Yaprak köşeleri veri bloklarından elde edilen karmaları içerirken, iç köşeler iki alt köşedeki değerlerin toplamından elde edilen karmaları içerir. Buna karşılık, kök tepe noktası tüm veri setinin karma değerini içerir.
Teori
Başlangıçta birbiriyle hiçbir şekilde ilişkisi olmayan bir veri kümesi vardır. Her veri bloğu için (bir işlem blok zinciri bağlamında), bloğun bir karma değerini hesaplamamız gerekir. Veri bloklarının sayısı 2^N olmalıdır, çünkü ağaç oluşturuldukça önceki bloklar her yinelemede çiftler halinde karma hale getirilir. Daha sonra bir çift karma birlikte gruplandırılır ve bunlara dayalı olarak yeni bir karma oluşturulur. Hashing, her düzeyde gruplanacak bir şey olduğu sürece devam edecek ve kök hash'in (Merkle kökü) elde edildiği yalnızca bir çift kaldığında duracaktır.
H(1-2) = keccak256(H(1) + H(2))
H(3-4) = keccak256(H(3) + H(4))
H(5-6) = keccak256(H(5) + H(6))
H(7-8) = keccak256(H(7) + H(8))
H(1-2-3-4) = keccak256(H(1-2) + H(3-4))
H(5-6-7-8) = keccak256(H(5-6) + H(7-8))
H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))
Kökü aldıktan sonra verileri doğrulayabiliriz. Kök karması orijinal karmayla eşleşiyorsa her şey yolunda demektir, veriler geçerlidir. Ağaç yapısında belirli verilerin bulunup bulunmadığını da verimli bir şekilde kontrol etmek mümkündür.
Diyelim ki ağaçta H2 karmasının mevcut olup olmadığını kontrol etmek istiyoruz. Kanıt bir veri dizisi olacaktır: H1 , H3-4 , H5-6-7-8 . Bu karmalar sayesinde kök karma değerini yeniden oluşturabiliriz:
H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))
Daha sonra ortaya çıkan hash'i orijinal olanla karşılaştırırız. Eşleşirlerse bu, ağaçta H2 karma değerinin mevcut olduğu anlamına gelir.
Pratik
Şimdi Solidity'de Merkle ağacının ve veri doğrulamanın nasıl uygulanacağını görelim.
Basit olması açısından, işlem dizisini ve hash dizisini doğrudan blok zincirine yazacağız. 32 baytlık bir karma değeri döndüren yerleşik keccak256 işlevini kullanacağımız için, karma dizisinin veri türü bytes32 olacaktır. Dizinin ayrıca dinamik bir uzunluğu olacaktır. Genel olarak karma dizisinin uzunluğu, üretilen karmaları tutacağından işlemler dizisinin uzunluğuyla aynı olmayacaktır. Uzunluğu önceden hesaplayabiliriz, ancak kodu basitleştirmek adına bunu yapmayacağız. İsterseniz bu dizilerin her birini public getirebilir ve işlemlerin karmalarını okuyabilirsiniz.
Yapıcıda hashes üreteceğiz. İlk adım, döngüdeki transactions sahip blokların karmalarını saymaktır. Daha sonra ağacın her seviyesinde hash sayısı 2 kat azaltılır. Hash'leri hash dizisinde saklayacağımız için indeks ofsetlerinin ayrı ayrı saklanması gerekir. İç döngüdeki yineleyici 2 artırılır çünkü karmaları hesaplarken ve eklerken birkaç öğe alacağız. abi.encodePacked bu sefer her birine indeksleri doğru şekilde ayarlayacağımız 2 hash ekleyeceğiz: sol eleman için – mevcut kaydırma ofsetinin değeri + mevcut ağaç seviyesindeki indeks ve sağ eleman için – aynı + 1.
Böylece ağacı oluşturduk ancak asıl ilgi alanımız veriyi doğrulamak. Bunu yapmak için bir işlemi ve onun indeksini alan validateTransaction fonksiyonunu yazalım. Ne yazık ki, Solidity'nin diziler için bir find yöntemi yoktur, dolayısıyla işlem dizinini iletmek daha kolaydır.
Öncelikle işlemin hash değerini hesaplayalım ve bir dizi kanıt oluşturalım. İşlem dizisinin uzunluğuna bağlı olarak kanıt sayısını buluyoruz ve proofsIndexes uzunluğunu ayarlıyoruz. Bundan sonra, ağacın her seviyesinde, indekse bağlı olarak, sağ veya sol elemanı alarak, hashes sapmaları göz önünde bulundurarak gerekli elemanı buluruz. Daha sonra kanıt indeksleri dizisini inceliyoruz, indeksin paritesini kontrol ediyoruz ve elemanın çiftte solda mı yoksa sağda mı olduğuna bağlı olarak hash'i hesaplıyoruz. Son olarak, ortaya çıkan hash'i kök hash ile karşılaştırır ve sonucu döndürürüz.
Başvuru
Blockchain'de Merkle ağacının çeşitli uygulamaları vardır.
- İşlem depolama : Örneğin Bitcoin'de bir işlem bloğu, işlemlerinin yalnızca merkle_root'unu saklar. Bu, bloğun boyutunu ve ağdaki yükü azaltır. Belirli sayıda işlem biriktirildikten sonra, yerden tasarruf etmek için eski işlemleri silmek mümkündür, ancak blokların kendileri değişmeden kalır çünkü yalnızca ağacın kökünü depolarlar.
- Madencilik : Bir bitcoin bloğu iki bölümden oluşur: blok başlığı ve işlem listesi. İşlem hash'lerini her seferinde yeniden hesaplamak zorunda kalmamak için bunlar bir Merkle ağacında sıralanır, ardından tüm blok yerine blok başlığına hash uygulanır ve rastgele bir nonce numarası alınır. Blok diğer düğümlere gönderildiğinde işlem listesinin kökü hesaplanır ve başlıktaki kökle eşleşmiyorsa blok reddedilir.
- Doğrulama : Doğrulamanın özü, tüm blok zincirini indirmeye gerek kalmadan denetim yapmaktır. Süreç büyük ölçüde basitleştirilmiştir ve ayrıca verilerle ilgili bilgiler açıklanmadan verilerin varlığının doğrulanmasına olanak tanır; bu, hassas bilgilerin doğrulanması için yararlı olabilir.
Özet
Merkle ağaçları olmasaydı, blok zincirleri çok hantal olurdu ve Merkle kanıtları, veri doğruluğunun uygun maliyetli bir şekilde doğrulanmasına olanak tanır.
Merkle ağaçları, işlemleri verimli bir şekilde depolamak için blok zincirlerde (örn. Bitcoin, Ethereum) aktif olarak kullanılır, ancak tek uygulama bu değildir. Örneğin FTX borsasının çöküşünden sonra birçok borsa Merkle ağacını kullanan Rezerv Kanıtı mekanizmasını uygulamaya koydu.
