Merkle Ağaçları: Ölçekli İşlem Bütünlüğü

Bir Bitcoin bloğu yaklaşık 2000 işlem içerir. Tüm 2000 işlemi indirmeden T işleminin dahil olduğunu kanıtlamak için kompakt bir kanıta ihtiyacımız vardır. Merkle ağaçları bunu çözer: kanıt boyutu, O(n) işlem yerine O(log n) özettir.

Yapraklar: her işlemin SHA256d (çift SHA256) özeti. Üst düğüm: SHA256d(left_child_hash || right_child_hash). Tek bir kök özet kalana kadar tekrarlayın. Düğüm sayısı tekse son düğümü çoğaltın. Kök, blok başlığında saklanan Merkle köküdür (32 bayt).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

T işleminin i konumunda olduğunu kanıtlamak için T'nin yaprağından köke kadar her düzeydeki kardeş özetleri sağlayın (O(log n) özet). Doğrulayıcı, T'den ve kardeş yolundan kökü yeniden hesaplar. Hesaplanan kök, blok başlığındaki Merkle köküyle eşleşirse T'nin dahil olduğu kanıtlanır.

1024 işlem → Merkle kanıtı = 10 özet = 320 bayt. Tam blok = yaklaşık 1 MB. SPV istemcileri, ilgilendikleri her işlem için yalnızca 80 baytlık başlığı + 320 baytlık Merkle kanıtını indirir — tam bloğu indirmeye kıyasla bant genişliğinde %99,97 tasarruf.

Ağaçtaki herhangi bir işlem değişirse yaprak özeti değişir ve bu değişiklik yukarı doğru yayılarak Merkle kökünü değiştirir. Değiştirilmiş kök, artık PoW ile mühürlenmiş blok başlığıyla eşleşmez. İşlemlerden kök hesaplanarak her değişiklik tespit edilebilir.

Ethereum, Merkle ağaçlarını trie'lerle genişletir (Patricia Merkle Trie): her düğümün Merkle özeti alınan, onaltılık önekle kodlanmış bir radix trie. Şunlar için kullanılır: durum trie'si (hesap bakiyeleri), işlem trie'si, makbuz trie'si. Tam düğüm verilerine ihtiyaç duymadan hesap durumunun verimli biçimde kanıtlanmasını sağlar.

Merkle Dağ Dizisi (MMR), günlük benzeri veriler için yalnızca ekleme yapılabilen bir Merkle yapısıdır. Yeni öğeler eklenir; tepeler (2'nin kuvveti büyüklüğündeki alt ağaçların kökleri) korunur. Grin/MimbleWimble ve ZCash'te, yalnızca ekleme yapılan bir günlük üzerinde verimli ve kompakt kanıtlar için kullanılır.

Verkle ağaçları, Ethereum'un yol haritasında Merkle ağaçlarının yerini alır (EIP-6800): özetler yerine vektör taahhütleri (KZG polinom taahhütleri) kullanır. Kanıt boyutu: Merkle için O(log n) yerine O(1). Durum bilgisi olmayan istemcilerin tüm trie'yi saklamadan durumu doğrulamasını sağlar.

Sertifika Şeffaflığı (RFC 6962), yalnızca ekleme yapılabilen bir Merkle günlüğü kullanır: CA tarafından verilen her sertifika bir yapraktır. Dahil etme kanıtları bir sertifikanın günlüğe kaydedildiğini doğrular. Tutarlılık kanıtları, günlüğün yalnızca ekleme yapılabilen yapısını koruduğunu (silme veya ekleme yapılmadığını) doğrular. Tarayıcı üreticileri SCT'leri bu günlük aracılığıyla doğrular.

Git ağaçları (dizin anlık görüntüleri) Merkle ağaçlarıdır: her ağaç düğümü, dosya nesnelerinin ve alt ağaçların özetini alır. Bir işleme ait özet, kod tabanının tüm durumunu benzersiz biçimde tanımlar. Bu nedenle git checkout her zaman tam olarak aynı dosyaları verir.

1024 yapraklı bir ağaca dahil olduğunu kanıtlamak için bir Merkle kanıtı kaç özet gerektirir?

Merkle ağaçları O(log n) boyutunda dahil etme kanıtları sağlar. Bitcoin, Merkle kökünü blok başlıklarında saklar; SPV istemcileri kanıtları kullanır. Ethereum bunu Patricia Merkle Trie'lerine genişletir. Verkle ağaçları O(1) boyutunda kanıtlar için Merkle ağaçlarının yerini alacak. Sırada: İş İspatı madenciliği ve zorluk.