Merkle Patricia Dijital Ağacı

Son düzenleme: @0xselimc(opens in a new tab), 23 Kasım 2023

Merkle Patricia Dijital Ağacı, tüm (key, value) bağlamalarını depolamak için kullanılabilen, kriptografik olarak kimliği doğrulanmış bir veri yapısı sağlar.

Merkle Patricia Dijital Ağacı tamamen belirleyicidir, yani aynı (key, value) bağlamalarına sahip olan dijital ağaçların son bayta kadar tamamen aynı olacağı garanti edilir. Bu, aynı kök karmasına sahip oldukları anlamına gelir ve ekleme, arama ve silme işlemleri için O(log(n)) verimliliğini sağlar. Ayrıca, kırmızı-siyah ağaçlar gibi daha karmaşık karşılaştırma tabanlı alternatiflere göre anlaşılması ve kodlanması daha kolaydır.

Ön koşullar

Bu sayfayı daha iyi anlamak için karmalar(opens in a new tab), Merkle ağaçları(opens in a new tab), tries(opens in a new tab) ve serileştirme(opens in a new tab) hakkında temel düzeyde bilgi sahibi olmak faydalı olabilir.

Temel taban dijital ağaçları

Temel bir taban dijital ağacında her düğüm aşağıdaki şekilde görünür:

1    [i_0, i_1 ... i_n, value]

Burada i_0 ... i_n, alfabenin sembollerini (genellikle ikili veya altılı) temsil eder; value, düğümdeki terminal değerdir ve i_0, i_1 ... i_n yuvalarındaki değerler ya NULL veya diğer düğümlerin (bizim durumumuzda, karmaları) işaretçilerdir. Bu, temel düzeyde bir (key, value) deposunu oluşturur.

Bir dizi anahtar değer çiftinin tabi olduğu sıralamayı sürdürmek için bir taban ağaç veri yapısını kullanmak istediğinizi varsayalım. Örneğin, dijital ağaçta şu anda dog anahtarı ile eşlenen değeri bulmak istiyorsanız, önce dog anahtarını alfabenin harflerine dönüştürün (64 6f 67 değerini vererek) ve ardından değeri bulana kadar bu yolu takip ederek dijital ağaçtan aşağı doğru inin. Diğer bir deyişle, dijital ağacın kök düğümünü bulmak için kök karmasını düz bir anahtar/değer veritabanında arayarak başlayın. Kök düğüm, diğer düğümlere işaret eden bir dizi anahtar olarak gösterilir. Dizin 6'daki değeri bir anahtar olarak kullanın ve düğümü bir seviye aşağı çekmek için düz anahtar/değer veritabanına bakın. Daha sonra bir sonraki değere bakmak için dizin 4'ü seçin, ardından dizin 6'yı seçin ve şu yolu izleyene kadar bu şekilde devam edin: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, düğümün değerine bakın ve sonucu döndürün.

"Dijital ağaçta" bir şeye bakmak ile altta yatan düz anahtar/değer "veritabanı" arasında bir fark vardır. Her ikisi de anahtar/değer düzenlemelerini tanımlasa da temel veritabanı, bir anahtarın geleneksel 1 adımlık aramasını yapabilir. Dijital ağaçtaki bir anahtara bakmak, yukarıda açıklanan son değere ulaşmak için birden çok temel veritabanı araması yapılmasını gerektirir. Belirsizliği ortadan kaldırmak için gelin ikincisine path adını verelim.

Taban dijital ağaçları için güncelleme ve silme işlemleri aşağıdaki gibi tanımlanabilir:

1    def update(node,path,value):
2        if path == '':
3            curnode = db.get(node) if node else [ NULL ] * 17
4            newnode = curnode.copy()
5            newnode[-1] = value
6        else:
7            curnode = db.get(node) if node else [ NULL ] * 17
8            newnode = curnode.copy()
9            newindex = update(curnode[path[0]],path[1:],value)
10            newnode[path[0]] = newindex
11        db.put(hash(newnode),newnode)
12        return hash(newnode)
13
14    def delete(node,path):
15        if node is NULL:
16            return NULL
17        else:
18            curnode = db.get(node)
19            newnode = curnode.copy()
20            if path == '':
21                newnode[-1] = NULL
22            else:
23                newindex = delete(curnode[path[0]],path[1:])
24                newnode[path[0]] = newindex
25
26            if all(x is NULL for x in newnode):
27                return NULL
28            else:
29                db.put(hash(newnode),newnode)
30                return hash(newnode)
Tümünü göster

Bir "Merkle" Taban ağacı, düğümleri birbirine bağlayıp deterministik olarak oluşturulmuş kriptografik karma özetlerini kullanarak oluşturulur. Bu içerik adresleme (anahtar/değer veritabanında key == keccak256(rlp(value))), depolanan veri için kriptografik bütünlük garantisi sağlar. Belli bir dijital ağacın kök karmasının herkesçe bilinmesi durumunda, alttaki yaprak verilere erişimi olan herkes, belirli bir değeri ağaç köküne ekleyen her düğümün karmasını sağlayarak dijital ağacın belirli bir yol üzerinde bir değeri içerdiğine dair kanıt oluşturabilir.

Bir saldırganın var olmayan bir (path, value) çiftinin kanıtını sunması imkansızdır, çünkü kök karması nihayetinde onun altındaki tüm karmalara dayanmaktadır. Temelde yapılacak herhangi bir değişiklik kök karmasını değiştirecektir. Karmayı, veri hakkındaki yapısal bilgilerin, karma işlevinin ön görüntü koruması ile güvence altına alınan sıkıştırılmış bir gösterimi olarak düşünebilirsiniz.

Bir taban ağacının atomik birimini (örneğin tek bir onaltılık karakter veya 4 bitlik bir ikili sayı) "nibble" olarak adlandıracağız. Yukarıda açıklandığı gibi, bir seferde bir nibble boyunca bir yol üzerinde gezinirken düğümler maksimum olarak 16 alt öğeye atıfta bulunabilirken ancak bir value öğesi içerebilir. Bu nedenle onları, uzunluğu 17 olan bir dizi olarak gösteririz. 17 öğeli bu dizileri "dal düğümleri" olarak adlandırıyoruz.

Merkle Patricia Önek Ağacı

Taban dijital ağaçları, büyük bir kısıtlamaya tabidir: bu ağaçlar verimsizdir. Ethereum'daki olduğu gibi, yolun 64 karakter uzunluğunda (bytes32 içindeki nibble sayısı) olduğu durumda bir (path, value) bağlaması depolamak istiyorsanız, her karakter için bir seviye depolamak için bir kilobayttan fazla ekstra alan gerekecektir ve her arama veya silme işlemi, 64 adımın tamamından geçecektir. Aşağıda açıklanan Patricia dijital ağacı bu sorunu çözer.

Optimizasyon

Merkle Patricia dijital ağacındaki bir düğüm aşağıdaki şekillerden biri gibi gözükür:

NULL (boş dize olarak gösterilir)
branch 17 öğeli bir düğüm [ v0 ... v15, vt ]
leaf 2-öğeli bir düğüm [ encodedPath, value ]
extension 2 öğeli bir düğüm [ encodedPath, key ]

64 karakterlik yollar sayesinde dijital ağacın ilk birkaç katmanını geçtikten sonra, aşağı inerken yolun en azından bir kısmında ayrılan yolun bulunmadığı bir düğüme ulaşmanız kaçınılmazdır. Yol boyunca en fazla 15 seyrek NULL düğüm oluşturmak zorunda kalmaktan kaçınmak için [ encodedPath, key ] biçiminde bir extension düğümü kurarak inişi kısaltıyoruz. Burada encodedPath, ileri atlamayı sağlayan "kısmi yolu" içerir (aşağıda açıklanan sıkıştırılmış bir kodlama kullanılarak) ve key, bir sonraki veritabanı araması içindir.

encodedPath'in ilk nibble'ında bir bayrakla işaretlenebilecek bir leaf düğümü söz konusu olduğunda yol, önceki düğümlerin tüm yol parçalarını kodlar ve value'yu doğrudan arayabiliriz.

Bununla birlikte, yukarıdaki optimizasyondan iki anlam çıkıyor.

Nibble'larda yolların üzerinden geçerken geçmemiz gereken nibble sayısının tek olduğu durumlar olabilir ancak bunun nedeni, tüm verilerin bytes biçiminde depolanmasıdır. Örneğin, nibble 1 ile nibble 01 (her ikisi de <01> olarak depolanmalıdır) arasında ayrım yapmak mümkün değildir. Tek sayıda uzunluğu belirtmek için kısmi yola önek olarak bir bayrak verilir.

Özellik: İsteğe bağlı sonlandırıcılı onaltılık dizinin sıkıştırılmış kodlaması

Yukarıda açıklandığı gibi, hem tek ve çift kalan kısmi yol uzunluğu hem de yaprak ve uzantı düğümü işaretlemesi, herhangi bir 2 öğeli düğümün kısmi yolunun ilk nibble'ında bulunur. Bu, aşağıdaki sonuçları verir:

1hex char    bits    |    node type partial     path length
2----------------------------------------------------------
3   0        0000    |       extension              even
4   1        0001    |       extension              odd
5   2        0010    |   terminating (leaf)         even
6   3        0011    |   terminating (leaf)         odd

Çift kalan yol uzunluğu (0 veya 2) için ardından her zaman başka bir 0 "dolgu" nibble'ı gelecektir.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray now has an even length whose first nibble is the flags.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        return o
Tümünü göster

Örnekler:

1    > [ 1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [ 0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [ 0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [ f, 1, c, b, 8, 10]
8    '3f 1c b8'

Merkle Patricia dijital ağacında bir düğüm almak için genişletilmiş kod:

1    def get_helper(node,path):
2        if path == []: return node
3        if node = '': return ''
4        curnode = rlp.decode(node if len(node) < 32 else db.get(node))
5        if len(curnode) == 2:
6            (k2, v2) = curnode
7            k2 = compact_decode(k2)
8            if k2 == path[:len(k2)]:
9                return get(v2, path[len(k2):])
10            else:
11                return ''
12        elif len(curnode) == 17:
13            return get_helper(curnode[path[0]],path[1:])
14
15    def get(node,path):
16        path2 = []
17        for i in range(len(path)):
18            path2.push(int(ord(path[i]) / 16))
19            path2.push(ord(path[i]) % 16)
20        path2.push(16)
21        return get_helper(node,path2)
Tümünü göster

Örnek Dijital Ağaç

Dört yol/değer çifti içeren bir dijital ağaç istediğimizi varsayalım: ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion').

İlk olarak, hem yolları hem de değerleri bytes' dönüştürürüz. Aşağıda, daha kolay anlaşılması için yollar için gerçek bayt gösterimleri <> ile gösterilirken değerler hala '' dizeler olarak gösterilir(bunlar da aslında byte olacaktır):

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coin'
4    <68 6f 72 73 65> : 'stallion'

Şimdi, temel veritabanında aşağıdaki anahtar/değer çiftleriyle böyle bir dijital ağaç oluşturuyoruz:

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashD ]
4    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Bir düğüme başka bir düğüm içinde başvurulduğunda, dahil edilenler H(rlp.encode(x)) olur, burada H(x) = keccak256(x) if len(x) > = 32 else x ve rlp.encode, RLP kodlama işlevidir.

Bir dijital ağacı güncellerken eğer yeni oluşturulan düğümün uzunluğu >= 32 ise, (keccak 256 (x), x) anahtar/değer çiftini kalıcı bir arama tablosunda saklamanız gerektiğini unutmayın. Bununla birlikte düğüm bundan daha kısaysa, f (x) = x işlevi tersine çevrilebilir olduğundan hiçbir şeyin depolanmasına gerek yoktur.

Ethereum'da Dijital Ağaçlar

Ethereum'ün yürütüm katmanındaki tüm merkle ağaçları, Merkle Patricia Dijital Ağacını kullanır.

Bir blok başlığında bu dijital ağaçların 3'ünden 3 kök vardır.

durumKökü (stateRoot)
işlemKökü (transactionsRoot)
makbuzKökü (receiptsRoot)

Durum Dijital Ağacı

Bir adet genel durum dijital ağacı vardır ve bu, bir istemci bir bloğu her işlediğinde güncellenir. İçindeki path her zaman şudur: keccak 256 (ethereumAddress) ve value her zaman şudur: rlp(ethereumAccount). Bir Ethereum account'u 4 öğeli bir [nonce,balance,storageRoot,codeHash] dizisidir. Bu noktada, bu storageRoot öğesinin başka bir patricia dijital ağacının kökü olduğunu belirtmekte fayda vardır:

Depolama Dijital Ağacı

Depolama dijital ağacı, tüm sözleşme verilerinin bulunduğu yerdir. Her bir hesap için ayrı bir depolama dijital ağacı vardır. Verilen bir adresteki belirli depolama konumlarındaki değerleri alabilmek için depolama adresi, depoda depolanan verilerin tam sayı konumu ve blok kimliği gereklidir. Bunlar daha sonra JSON-RPC API'sinde tanımlanan eth_getStorageAt öğesine bağımsız değişkenler olarak yapıştırılabilir, ör. 0x295a70b2de5e3953354a6a8344e616ed314d7251 adresi için depolama yuvası 0'daki verileri almak amacıyla:

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}
4

Depolama alanındaki diğer öğelerin alınması biraz daha karmaşıktır çünkü ilk önce depolama alanındaki konumun hesaplanması gerekir. Konum, adresin keccak 256 karması ve depolama konumu alınarak hesaplanır, her ikisi de 32 bayt uzunluğa kadar sıfırlarla doldurulmuştur. Örneğin, 0x391694e7e0b0cce554cb130d723a9d27458f9298 adresi için depolama yuvası 1'deki verilerin konumu:

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

Geth konsolunda bu aşağıdaki şekilde hesaplanabilir:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

Buradaki path bu nedenle keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>)'dır. Bu, artık daha önce olduğu gibi verileri depolama ağacından almak için kullanılabilir:

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Not: Bir Ethereum hesabının storageRoot'u, eğer bir sözleşme hesabı değilse varsayılan olarak boştur.

İşlem Dijital Ağacı

Her blok için ayrı bir işlem dijital ağacı vardır ve aynı şekilde (key, value) çiftlerini saklar. Buradaki yol: aşağıdakiler tarafından belirlenen bir değere karşılık gelen anahtarı temsil eden rlp(transactionIndex)'dir:

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

Bununla ilgili daha fazla bilgiyi EIP 2718(opens in a new tab) belgelerinde bulabilirsiniz.

Makbuz Dijital Ağaçları

Her bloğun kendi makbuz dijital ağacı vardır. Burada path: rlp(transactionIndex)'dir. transactionIndex, çıkarıldığı blok içerisindeki indeksidir. Makbuz dijital ağacı hiçbir zaman güncellenmez. İşlemler dijital ağacına benzer şekilde güncel ve eski makbuzlar mevcuttur. Makbuzlar dijital ağacı içerisinde belirli bir makbuzu sorgulamak için bloktaki işlemin indeksi, makbuz yükü ve işlem türü gereklidir. Döndürülen makbuz, TransactionType ve ReceiptPayload'un birleşimi olarak tanımlanan Receipt türünde ya da rlp([status, cumulativeGasUsed, logsBloom, logs]) olarak tanımlanan LegacyReceipt türünde olabilir.