Merkle Patricia Dijital Ağacı

Ethereum'un durumu (tüm hesapların, bakiyelerin ve akıllı sözleşmelerin toplamı), bilgisayar biliminde genel olarak Merkle Ağacı olarak bilinen veri yapısının özel bir versiyonuna kodlanır. Bu yapı, kriptografideki birçok uygulama için kullanışlıdır çünkü ağaca dolanmış tüm bireysel veri parçaları arasında doğrulanabilir bir ilişki oluşturur ve bu da veriler hakkında bir şeyler kanıtlamak için kullanılabilecek tek bir kök değeriyle sonuçlanır.

Ethereum'un veri yapısı, PATRICIA'nın (Practical Algorithm To Retrieve Information Coded in Alphanumeric - Alfasayısal Kodlanmış Bilgileri Almak için Pratik Algoritma) bazı özelliklerini ödünç aldığı ve Ethereum durumunu oluşturan öğelerin verimli şekilde veri geri alımı (retrieval) için tasarlandığından 'değiştirilmiş Merkle-Patricia Trie'dir.

Bir Merkle-Patricia trie deterministik ve kriptografik olarak doğrulanabilirdir: Bir durum kökü oluşturmanın tek yolu, onu durumun her bir parçasından hesaplamaktır ve aynı olan iki durum, kök karması ve ona yol açan karmalar karşılaştırılarak kolayca kanıtlanabilir (bir Merkle kanıtı). Tam tersinden bakacak olursak, aynı kök karmasına sahip iki farklı durum oluşturmak mümkün değildir ve farklı değerlere sahip durumları değiştirme girişimi farklı bir durum kök karmasına yol açar. Teorik olarak, bu yapı eklemeler, aramalar ve silmeler için O(log(n)) verimliliğinin 'kutsal kasesini' sağlar.

Yakın gelecekte Ethereum, gelecekteki protokol iyileştirmeleri için birçok yeni olasılığın önünü açacak olan bir Verkle Ağacı yapısına geçmeyi planlıyor.

Ö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), trie'lar (opens in a new tab) ve serileştirme (opens in a new tab) hakkında temel bilgilere sahip olmak faydalı olacaktır. Bu makale, temel bir radix ağacının (opens in a new tab) tanımıyla başlıyor, ardından Ethereum'un daha optimize edilmiş veri yapısı için gerekli değişiklikleri kademeli olarak tanıtıyor.

Temel radix trie'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 onaltılık) temsil eder, value düğümdeki terminal değerdir ve i_0, i_1 ... içindeki değerler i_n yuvaları ya NULL ya da diğer düğümlere yönelik işaretçilerdir (bizim durumumuzda, karmalarıdır). Bu, temel bir (anahtar, değer) deposu 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. Trie'da dog anahtarıyla eşleştirilmiş geçerli değeri bulmak için, önce dog kelimesini alfabe harflerine dönüştürür (64 6f 67 vererek) ve ardından değeri bulana kadar bu yolu izleyerek trie'dan aşağı inersiniz. 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. 6 dizinindeki değeri bir anahtar olarak kullanır ve düğümü bir seviye aşağı indirmek için düz anahtar/değer veritabanında aratırsınız. Ardından bir sonraki değere bakmak için 4 dizinini, sonra 6 dizinini seçersiniz ve bu böyle devam eder, ta ki şu yolu izleyene kadar: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, düğümün değerine bakar ve sonucu döndürürsünüz.

"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 ikincisine yol diyelim.

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

1    def update(node_hash, path, value):
2        curnode = db.get(node_hash) if node_hash else [NULL] * 17
3        newnode = curnode.copy()
4        if path == "":
5            newnode[-1] = value
6        else:
7            newindex = update(curnode[path[0]], path[1:], value)
8            newnode[path[0]] = newindex
9        db.put(hash(newnode), newnode)
10        return hash(newnode)
11
12    def delete(node_hash, path):
13        if node_hash is NULL:
14            return NULL
15        else:
16            curnode = db.get(node_hash)
17            newnode = curnode.copy()
18            if path == "":
19                newnode[-1] = NULL
20            else:
21                newindex = delete(curnode[path[0]], path[1:])
22                newnode[path[0]] = newindex
23
24            if all(x is NULL for x in newnode):
25                return NULL
26            else:
27                db.put(hash(newnode), newnode)
28                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 veriler için kriptografik bir 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.

Kök karması nihayetinde altındaki tüm karmalara dayandığından, bir saldırganın var olmayan bir (yol, değer) çiftinin kanıtını sunması imkansızdı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 radix ağacının atomik bir birimine (örneğin, tek bir onaltılık karakter veya 4 bitlik ikili sayı) "nibble" diyeceğiz. Yukarıda açıklandığı gibi, bir yolu her seferinde bir nibble ilerleyerek geçerken, düğümler en fazla 16 alt öğeye başvurabilir ancak bir değer öğesi de 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 Trie

Taban dijital ağaçları, büyük bir kısıtlamaya tabidir: bu ağaçlar verimsizdir. Ethereum'da olduğu gibi, yolun 64 karakter uzunluğunda olduğu (bytes32 içindeki nibble sayısı) bir (yol, değer) bağlamasını saklamak isterseniz, karakter başına bir seviye depolamak için bir kilobayttan fazla ekstra alana ihtiyacınız olacaktır ve her arama veya silme işlemi tam 64 adım sürecektir. 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 temsil edilir)
dal 17 öğeli bir düğüm [ v0 ... v15, vt ]
yaprak 2 öğeli bir düğüm [ encodedPath, value ]
uzantı 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 15'e kadar seyrek NULL düğüm oluşturmaktan kaçınmak için, [ encodedPath, key ] biçiminde bir uzantı düğümü kurarak inişi kısaltırız; burada encodedPath ileri atlamak için "kısmi yolu" içerir (aşağıda açıklanan sıkıştırılmış bir kodlama kullanılarak) ve anahtar sonraki veritabanı araması içindir.

encodedPath'in ilk nibble'ındaki bir bayrakla işaretlenebilen bir yaprak düğüm için, yol önceki tüm düğümün yol parçalarını kodlar ve değeri doğrudan arayabiliriz.

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

Yolları nibble'lar halinde geçerken, geçilecek tek sayıda nibble ile karşılaşabiliriz, ancak tüm veriler bayt formatında saklandığı için. Örneğin, 1 nibble'ı ile 01 nibble'larını (her ikisi de <01> olarak saklanmalıdır) ayırt etmek mümkün değildir. Tek sayıda uzunluğu belirtmek için kısmi yola önek olarak bir bayrak verilir.

Belirtim: İ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:

onaltılık karakter	bitler	düğüm türü	yol uzunluğu
0	0000	uzantı	çift
1	0001	uzantı	tek
2	0010	sonlandırıcı (yaprak)	çift
3	0011	sonlandırıcı (yaprak)	tek

Kalan yol uzunluğu çift olduğunda (0 veya 2), bunu her zaman başka bir 0 "dolgu" nibble'ı takip edecektir.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # hexarray now has an even length whose first nibble is the flags.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        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_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
Tümünü göster

Trie Örneği

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

İlk olarak hem yolları hem de değerleri bayt'a dönüştürürüz. Aşağıda, yollar için gerçek bayt gösterimleri <> ile belirtilirken, değerler daha kolay anlaşılması için hâlâ '' ile belirtilen dizeler olarak gösterilmektedir (onlar da aslında bayt olacaktır):

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coins'
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>, hashC ]
4    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Bir düğüme başka bir düğüm içinde referans verildiğinde, dahil edilen şey, eğer len(rlp.encode(node)) >= 32 ise keccak256(rlp.encode(node)), değilse node'dur; burada rlp.encode RLP kodlama işlevidir.

Bir trie'ı güncellerken, yeni oluşturulan düğümün uzunluğu >= 32 ise, (keccak256(x), x) anahtar/değer çiftini kalıcı bir arama tablosunda saklamak 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'daki Trie'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 Trie'ı

Bir adet genel durum dijital ağacı vardır ve bu, bir istemci bir bloğu her işlediğinde güncellenir. İçinde bir yol her zaman keccak256(ethereumAddress) ve bir değer her zaman rlp(ethereumAccount)'dır. Daha spesifik olarak bir Ethereum hesabı, 4 öğeli bir [nonce,balance,storageRoot,codeHash] dizisidir. Bu noktada, bu storageRoot'un başka bir patricia trie'ının kökü olduğunu belirtmekte fayda var:

Depolama Trie'ı

Depolama trie'ı 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'e argüman olarak aktarılabilir, ör. 0x295a70b2de5e3953354a6a8344e616ed314d7251 adresi için depolama yuvası 0'daki verileri almak için:

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

Depolama alanındaki diğer öğelerin alınması biraz daha karmaşıktır çünkü ilk önce depolama alanındaki konumun hesaplanması gerekir. Konum, adresin ve depolama konumunun keccak256 karması olarak hesaplanır, her ikisi de 32 bayt uzunluğa ulaşacak şekilde başlarına sıfır eklenir. Örneğin, 0x391694e7e0b0cce554cb130d723a9d27458f9298 adresi için depolama yuvası 1'deki verilerin konumu şöyledir:

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"

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

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

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

İşlemler Trie'ı

Her blok için ayrı bir işlemler trie'ı bulunur ve bu da yine (anahtar, değer) çiftlerini saklar. Buradaki bir yol, rlp(transactionIndex)'tir ve bu, şu şekilde belirlenen bir değere karşılık gelen anahtarı temsil eder:

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

Bununla ilgili daha fazla bilgi EIP 2718 (opens in a new tab) belgelerinde bulunabilir.

Makbuzlar Trie'ı

Her bloğun kendi makbuz dijital ağacı vardır. Buradaki bir yol: rlp(transactionIndex)'dir. transactionIndex, dahil edildiği blok içindeki dizinidir. 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 veya rlp([status, cumulativeGasUsed, logsBloom, logs]) olarak tanımlanan LegacyReceipt türünde olabilir.