What is the shared nibble of this extension node?

Question

I have an extension node here:

Key:

000b17906abb9f83c5e190bc3d0bed212e66bf44d99997c53c2071e1413194b6

Value:

[

3866a6d45a815576000da23c1a017179233e9d6437806aef7c2264588739d0,

f84d80890159f20bed00f00000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470,

]

This extension nodes second value can be decoded using RLP into this

Value:

[

"",

0159f20bed00f00000,

56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421,

c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470,

]

What is the shared nibble of this extension node? Where is the prefix? This is all discussed in the yellow paper and I was hoping to have some clarification on where to find these values when actually decoding the byte[].

Answer 1

First of all this is note extension node - this is leaf. You can use state._get_node_type() function in Python to understand that.

If this node is really extension it must look like:

extension_node:[key,value]

, or because value in extension nodes = hash of next node (usually next node type is branch_node, but it may be leaf_node if it size more that don't remember how many bits) this node looks like:

extension_node:[key,hash_of_branch_node]
// or
extension_node:[key,hash_of_leaf_node]

So by that your representation not good at all - looks like you into a muddle, because you has:

some_node:[key,data]
// or
leaf_node:[key,data]

In your example you just see node in database where key is hash in DB, value - node saved behind that key.

Key   = hash in LevelDB =
      = 000b17906abb9f83c5e190bc3d0bed212e66bf44d99997c53c2071e1413194b6
Value = node of merkle tree =
      = [
            3866a6d45a815576000da23c1a017179233e9d6437806aef7c2264588739d0,
            f84d80890159f20bed00f00000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
        ]

So, lets look at node:

node k = merkle tree node key =
       = 3866a6d45a815576000da23c1a017179233e9d6437806aef7c2264588739d0
node v = merkle tree node value =
       = data = info about wallet which encoded in node k
       = f84d80890159f20bed00f00000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470

It will be interesting for you, lets look at my own blockhain at leaf node stored in DB by hash

f44517e043e683d6c64eb208107b67db33051664f3350f1107f674365402d4b2

leaf node (hash in DB) : f44517e043e683d6c64eb208107b67db33051664f3350f1107f674365402d4b2
leaf node (value in DB): [
                            '4{\xaerrz\x9e\x8b~\x9f\xc8\xc2.i\x03E\x17\x93g\x91_}lW\xc4>L\x86:\xe4\x8b' ,
                            "\xf8^\x80\x9a\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\
                             x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xa0V\xe8\x1f\x17\x1b\xccU\xa6\xff\
                             x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!\xa0\xc5\xd2F\
                             x01\x86\xf7#<\x92~}\xb2\xdc\xc7\x03\xc0\xe5\x00\xb6S\xca\x82';{\xfa\xd8\x04]\x85\xa4p"
                         ]
leaf node k: '4{\xaerrz\x9e\x8b~\x9f\xc8\xc2.i\x03E\x17\x93g\x91_}lW\xc4>L\x86:\xe4\x8b'
leaf node v: "\xf8^\x80\x9a\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\
              x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xa0V\xe8\x1f\x17\x1b\xccU\xa6\xff\
              x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!\xa0\xc5\xd2F\
              x01\x86\xf7#<\x92~}\xb2\xdc\xc7\x03\xc0\xe5\x00\xb6S\xca\x82';{\xfa\xd8\x04]\x85\xa4p"

So, this is leaf node. To understand what is it we must know that if we look at

1. StateRoot: key of node will be wallet, value of node will be data about that wallet
2. TransactionRoot: key will be big-endian integers representing the transaction count in the current block

So decode from RLP leaf value:

[   '',
    '\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00',
    'V\xe8\x1f\x17\x1b\xccU\xa6\xff\x83E\xe6\x92\xc0\xf8n[H\xe0\x1b\x99l\xad\xc0\x01b/\xb5\xe3c\xb4!',
    "\xc5\xd2F\x01\x86\xf7#<\x92~}\xb2\xdc\xc7\x03\xc0\xe5\x00\xb6S\xca\x82';{\xfa\xd8\x04]\x85\xa4p"
]

We got info about wallet:

[   '',
    '0100000000000000000000000000000000000000000000000000',
    '56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421',
    'c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470'
]

So, where is nibbles? Nibbles are used in keys, e.g. leaf node k and extension node k, let's look at it:

extension node key: [ '\x1b' ]
leaf node key     : [ '4{\xaerrz\x9e\x8b~\x9f\xc8\xc2.i\x03E\x17\x93g\x91_}lW\xc4>L\x86:\xe4\x8b' ]

Each key packed by RLP with nibbles (terminator and odd flags). But if we has extension node linked to leaf sheared key saved in extension node. Otherwise when we have both keys are only one nibble longer, like '0001' and '0005', than the key for the branch node itself, the final nibble is encoded implicitly by the position (positions 1 (000_1) and 5 (000_5)) of the nodes in the branch node. So, in that case shared key is [ '\x1b' ] = [ '1b' ] = '11011' for our leaf.

Our shared key we can decode to hex and see by that:

extension node key: [ '1b' ]

After that we can see our nibbles, for that we must use 2 functions from trie.py (pyethereum/ethereum):

without_terminator(nibbles)
unpack_to_nibbles(bindata)

Like that:

without_terminator(unpack_to_nibbles('1b')) = 11 = our key without nibbles (HexPrefix)

Also you must know, that nibbles is just half of byte (xxxxbbbb), to see that you need get byte and look for it after decoded to bits. Lets do that. We have '1b', decode it to bits: '0001 1011', after remove HexPrefix we obtain '1011' - this is or shared key.

In your case shared key not stored anywhere here, but because 3866a6d45a815576000da23c1a017179233e9d6437806aef7c2264588739d0 - leaf of branch, it consist of parts and stored in key value of that leaf and branch node position which look at that leaf.

How we obtain nibbles you can see in trie.py in:

pack_nibbles(nibbles)
without_terminator(nibbles)
unpack_to_nibbles(bindata)

Also lets look at real extension node. In this case we got extension_node which point to leaf_node. So representation must be looks like (example from my own blockchain):

extension node (hash in DB) : [ 'bac02ec3c4fa5a468f711a626a42a23b32031fb9bc9255ed27a428dabee61544']
extension node (value in DB): [ '\x1b', ''e\x96K\x85n\xf0k[\xe4\x19\x9bI\xf2\xc1\x06E\x82E\x80Y\x8b6\x90\xf8\x13\x8d\xdc@S?\x12F'']
    extension node k (value in DB): [ '\x1b' ] <<-key packed by RLP with nibbles (terminator and odd flags)
    extension node v (value in DB): [ '65964b856ef06b5be4199b49f2c10645824580598b3690f8138ddc40533f1246' ] <<-encoded ranch node to hex

By geting branch

state._decode_to_node(extension_node_v)

we obtain merkle branch node value:

[
    '',
    '\xf4E\x17\xe0C\xe6\x83\xd6\xc6N\xb2\x08\x10{g\xdb3\x05\x16d\xf35\x0f\x11\x07\xf6t6T\x02\xd4\xb2',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '',
    '\x00\xa4\xe2/Dk-!\x05\x19H\xa6\x04\xd4\xc0\xf1&<\xb5&m\xc4f\xdd\xb7\xa6\xd6\x8c\xe1U<\x18',
    ''
]

Node saved by hash

'\xf4E\x17\xe0C\xe6\x83\xd6\xc6N\xb2\x08\x10{g\xdb3\x05\x16d\xf35\x0f\x11\x07\xf6t6T\x02\xd4\xb2'

is our leaf with wallet seen before.