# 基数树

 [0, i1 ... in , 值]


 def update(node,path,value):

if path == '':

curnode = db.get(node) if node else [ NULL ] * 17

newnode = curnode.copy()

newnode[-1] = value

else:

curnode = db.get(node) if node else [ NULL ] * 17

newnode = curnode.copy()

newindex = update(curnode[path[0]],path[1:],value)

newnode[path[0]] = newindex

db.put(hash(newnode),newnode)

return hash(newnode)

def delete(node,path):

if node is NULL:

return NULL

else:

curnode = db.get(node)

newnode = curnode.copy()

if path == '':

newnode[-1] = NULL

else:

newindex = delete(curnode[path[0]],path[1:])

newnode[path[0]] = newindex

if len(filter(x -> x is not NULL, newnode)) == 0:

return NULL

else:

db.put(hash(newnode),newnode)

return hash(newnode)


# 默克尔帕特里夏树

## 优化

• NULL（表示为空字符串）

• branch，一个 17 元素节点 [ v0 … v15, vt ]

• leaf，一个双元素节点 [ encodedPath, value ]

• extension，一个双元素节点 [ encodedPath, key ]

leaf 节点可以通过 encodedPath 的第一个半字节中的标志位确定。

## 规范：带有可选终止符的十六进制序列的压缩编码

hex char    bits    |    node type partial     path length

----------------------------------------------------------

0        0000    |       extension              even

1        0001    |       extension              odd

2        0010    |   terminating (leaf)         even

3        0011    |   terminating (leaf)         odd


def compact_encode(hexarray):

term = 1 if hexarray[-1] == 16 else 0

if term: hexarray = hexarray[:-1]

oddlen = len(hexarray) % 2

flags = 2 * term + oddlen

if oddlen:

hexarray = [flags] + hexarray

else:

hexarray = [flags] + [0] + hexarray

// hexarray now has an even length whose first nibble is the flags.

o = ''

for i in range(0,len(hexarray),2):

o += chr(16 * hexarray[i] + hexarray[i+1])

return o


> [ 1, 2, 3, 4, 5, ...]

'11 23 45'

> [ 0, 1, 2, 3, 4, 5, ...]

'00 01 23 45'

> [ 0, f, 1, c, b, 8, 10]

'20 0f 1c b8'

> [ f, 1, c, b, 8, 10]

'3f 1c b8'


def get_helper(node,path):

if path == []: return node

if node = '': return ''

curnode = rlp.decode(node if len(node) < 32 else db.get(node))

if len(curnode) == 2:

(k2, v2) = curnode

k2 = compact_decode(k2)

if k2 == path[:len(k2)]:

return get(v2, path[len(k2):])

else:

return ''

elif len(curnode) == 17:

return get_helper(curnode[path[0]],path[1:])

def get(node,path):

path2 = []

for i in range(len(path)):

path2.push(int(ord(path[i]) / 16))

path2.push(ord(path[i]) % 16)

path2.push(16)

return get_helper(node,path2)


## 前缀树示例

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


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


# 以太坊中的前缀树

• stateRoot

• transactionsRoot

• receiptsRoot

## 存储树

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"}


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


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"}


## 交易树

if legacyTx:
value = rlp(tx)
else:
value = TxType | encode(tx)


## 收据树

transactionIndex 是它在挖矿区块中的索引。

# 参考资料

https://ethereum.org/zh/developers/docs/data-structures-and-encoding/patricia-merkle-trie/