State tree
The state tree acts as a data repository.
The state tree stores only those datasets that can be preassigned an identifier or address as an 8-byte number. They are addressed by this identifier.
For example, each account has its own identifier, which derives from the public key. This identifier acts as the address of the object within the state tree. In order to clearly identify the state of an account at a particular point in time, all the states of the accounts are combined into a hash tree of states. Subsequently, the top of the state tree is used as an identifier of the overall state of the application.

Merkle's Discharged Tree

In general, the state stree is similar to the Merkle tree. Classic Merkle tree is focused on storing a fixed list of elements or chronologically added elements ()continuous flow of elements without gaps).
The state tree stores relatively little amount of elements, but has a clear value area and a specific address for each element. These elements are then combined into a Merkle tree. We call this the "unstacked Merkle tree".
The state tree is a binary tree, in which each state of an item has a fixed position (set by item ID).
The tree is built according to the following principles:
    1.
    The item ID clearly defines the sheet where the state of the item should be stored. The tree sheet stores the current state of the element.
    2.
    The hash is calculated for each sheet and node.
    3.
    The sheet hash is calculated from the data it contains (by the state of the item).
    4.
    The hash of a node is calculated from the hashes of the left and right subtrees. If a node has no left or right subtree, the hash equals to the hash of the subtree it has.
Thanks to this type of structure it was possible to achieve the following:
    1.
    Storing the state of an element for each point in time (history of changes).
    2.
    Minimizing the time of receiving the value of an element by its identifier.
    3.
    Minimizing changes in the state tree over time (changes affect only new or changed sheets and the "path" to the top of the tree.)
In addition to quick access to the state of an item, the state tree provides an additional level of validation of the network state.
If after processing a block of data, the hash at the top of the state tree does not match what was obtained on the remote peer, then the dataset is not accepted, since it was processed differently on different peers.

Merkle's discharged tree work example

For example, the state tree for 16 (2^4) elements looks like the following (the real tree has 9'223'372'036'854'775'808 (2^64) possible positions):
1
graph TD
2
3
root{ } --- R0
4
root{ } --- R1
5
6
R0{ } --- R00
7
R0{ } --- R01
8
R1{ } --- R10
9
R1{ } --- R11
10
11
R00{ } --- R000
12
R00{ } --- R001
13
R01{ } --- R010
14
R01{ } --- R011
15
R10{ } --- R100
16
R10{ } --- R101
17
R11{ } --- R110
18
R11{ } --- R111
19
20
R000{ } --- 0000
21
R000{ } --- 0001
22
R001{ } --- 0010
23
R001{ } --- 0011
24
R010{ } --- 0100
25
R010{ } --- 0101
26
R011{ } --- 0110
27
R011{ } --- 0111
28
29
R100{ } --- 1000
30
R100{ } --- 1001
31
R101{ } --- 1010
32
R101{ } --- 1011
33
R110{ } --- 1100
34
R110{ } --- 1101
35
R111{ } --- 1110
36
R111{ } --- 1111
Copied!
All possible elements are listed.
There is a distinction between the virtual tree state and its real representation. For example, for a tree of 1 element (with ID A-0101) only 1 sheet will actually be stored (Virtual - virtual tree representation, Real - real representation, which will be used to search data in the snapshot (the current version)):
1
graph TD
2
subgraph Virtual
3
4
App[AppSnapshot] ---|H1| R
5
6
R{ } ---|H1| R0
7
R{ } -.- R1
8
9
R0{ } -.- R00
10
R0{ } ---|H1| R01
11
R1{ } -.- R10
12
R1{ } -.- R11
13
14
R00{ } -.- R000
15
R00{ } -.- R001
16
R01{ } ---|H1| R010
17
R01{ } -.- R011
18
R10{ } -.- R100
19
R10{ } -.- R101
20
R11{ } -.- R110
21
R11{ } -.- R111
22
23
R000{ } -.- 0000
24
R000{ } -.- 0001
25
R001{ } -.- 0010
26
R001{ } -.- 0011
27
R010{ } -.- 0100
28
R010{ } ---|H1| 0101((0101))
29
R011{ } -.- 0110
30
R011{ } -.- 0111
31
32
R100{ } -.- 1000
33
R100{ } -.- 1001
34
R101{ } -.- 1010
35
R101{ } -.- 1011
36
R110{ } -.- 1100
37
R110{ } -.- 1101
38
R111{ } -.- 1110
39
R111{ } -.- 1111
40
end
41
42
subgraph Real
43
AppSnapshot ---|H1| L0101((0101))
44
end
45
46
classDef className stroke-width:3px
47
class 0101,R010,R01,R0,R className
48
class L0101,Root className
49
class App,AppSnapshot className
Copied!
If one more element is added to the tree (A-0111), we will get the following (for a binary tree the number of nodes is one less than the number of sheets):
1
graph TD
2
subgraph Virtual
3
4
App[AppSnapshot] ---|H12| R
5
6
R{ } ---|H1| R0
7
R{ } ---|H2| R1
8
9
R0{ } -.- R00
10
R0{ } ---|H1| R01
11
R1{ } -.- R10
12
R1{ } ---|H2| R11
13
14
R00{ } -.- R000
15
R00{ } -.- R001
16
R01{ } ---|H1| R010
17
R01{ } -.- R011
18
R10{ } -.- R100
19
R10{ } -.- R101
20
R11{ } -.- R110
21
R11{ } ---|H2| R111
22
23
R000{ } -.- 0000
24
R000{ } -.- 0001
25
R001{ } -.- 0010
26
R001{ } -.- 0011
27
R010{ } -.- 0100
28
R010{ } ---|H1| 0101((0101))
29
R011{ } -.- 0110
30
R011{ } -.- 0111
31
32
R100{ } -.- 1000
33
R100{ } -.- 1001
34
R101{ } -.- 1010
35
R101{ } -.- 1011
36
R110{ } -.- 1100
37
R110{ } -.- 1101
38
R111{ } -.- 1110
39
R111{ } ---|H2| 1111((1111))
40
41
classDef className stroke-width:3px
42
class 1111,R111,R11,R1,R className
43
end
44
45
subgraph Real
46
AppSnapshot ---|H12| Root{ }
47
Root{ } ---|H1| L0101((0101))
48
Root{ } ---|H2| L1111((1111))
49
end
50
51
classDef className stroke-width:3px
52
class 1111,R111,R11,R1,R className
53
class L1111,H12,Root className
54
class App,AppSnapshot className
Copied!
After adding one more element (A-1010) we get:
1
graph TD
2
subgraph Virtual
3
4
App[AppSnapshot] ---|H142| R
5
6
R{ } ---|H1| R0
7
R{ } ---|H32| R1
8
9
R0{ } -.- R00
10
R0{ } ---|H1| R01
11
R1{ } ---|H3| R10
12
R1{ } ---|H2| R11
13
14
R00{ } -.- R000
15
R00{ } -.- R001
16
R01{ } ---|H1| R010
17
R01{ } -.- R011
18
R10{ } -.- R100
19
R10{ } ---|H3| R101
20
R11{ } -.- R110
21
R11{ } ---|H2| R111
22
23
R000{ } -.- 0000
24
R000{ } -.- 0001
25
R001{ } -.- 0010
26
R001{ } -.- 0011
27
R010{ } -.- 0100
28
R010{ } ---|H1| 0101((0101))
29
R011{ } -.- 0110
30
R011{ } -.- 0111
31
32
R100{ } -.- 1000
33
R100{ } -.- 1001
34
R101{ } ---|H3| 1010((1010))
35
R101{ } -.- 1011
36
R110{ } -.- 1100
37
R110{ } -.- 1101
38
R111{ } -.- 1110
39
R111{ } ---|H2| 1111((1111))
40
end
41
42
subgraph Real
43
AppSnapshot ---|H123| Root{ }
44
Root{ } ---|H1| L0101((0101))
45
Root{ } ---|H32| H32{ }
46
H32{ } ---|H3| L1010((1010))
47
H32{ } ---|H2| L1111((1111))
48
end
49
50
classDef className stroke-width:3px
51
class 1010,R101,R10,R1,R className
52
class L1010,H32,Root className
53
class App,AppSnapshot className
54
Copied!
If the state of an existing element is changed, then the change occurs only in the nodes on the path from the node to the element (for example, the state of A-1010 has changed):
1
graph TD
2
subgraph Virtual
3
4
App[AppSnapshot] ---|H142| R
5
6
R{ } ---|H1| R0
7
R{ } ---|H42| R1
8
9
R0{ } -.- R00
10
R0{ } ---|H1| R01
11
R1{ } ---|H4| R10
12
R1{ } ---|H2| R11
13
14
R00{ } -.- R000
15
R00{ } -.- R001
16
R01{ } ---|H1| R010
17
R01{ } -.- R011
18
R10{ } -.- R100
19
R10{ } ---|H4| R101
20
R11{ } -.- R110
21
R11{ } ---|H2| R111
22
23
R000{ } -.- 0000
24
R000{ } -.- 0001
25
R001{ } -.- 0010
26
R001{ } -.- 0011
27
R010{ } -.- 0100
28
R010{ } ---|H1| 0101((0101))
29
R011{ } -.- 0110
30
R011{ } -.- 0111
31
32
R100{ } -.- 1000
33
R100{ } -.- 1001
34
R101{ } ---|H4| 1010((1010))
35
R101{ } -.- 1011
36
R110{ } -.- 1100
37
R110{ } -.- 1101
38
R111{ } -.- 1110
39
R111{ } ---|H2| 1111((1111))
40
end
41
42
subgraph Real
43
AppSnapshot ---|H142| Root{ }
44
Root{ } ---|H1| L0101((0101))
45
Root{ } ---|H42| H42{ }
46
H42{ } ---|H4| L1010((1010))
47
H42{ } ---|H2| L1111((1111))
48
end
49
50
classDef className stroke-width:3px
51
class 1010,R101,R10,R1,R className
52
class L1010,H42,Root className
53
class App,AppSnapshot className
Copied!
When adding a new element, there are also changes along the path from the top to that element (added A-1100):
1
graph TD
2
subgraph Virtual
3
4
App[AppSnapshot] ---|H1452| root
5
6
root{ } ---|H1| R0
7
root{ } ---|H452| R1
8
9
R0{ } -.- R00
10
R0{ } ---|H1| R01
11
R1{ } ---|H4| R10
12
R1{ } ---|H52| R11
13
14
R00{ } -.- R000
15
R00{ } -.- R001
16
R01{ } ---|H1| R010
17
R01{ } -.- R011
18
R10{ } -.- R100
19
R10{ } ---|H4| R101
20
R11{ } ---|H5| R110
21
R11{ } ---|H2| R111
22
23
R000{ } -.- 0000
24
R000{ } -.- 0001
25
R001{ } -.- 0010
26
R001{ } -.- 0011
27
R010{ } -.- 0100
28
R010{ } ---|H1| 0101((0101))
29
R011{ } -.- 0110
30
R011{ } -.- 0111
31
32
R100{ } -.- 1000
33
R100{ } -.- 1001
34
R101{ } ---|H4| 1010((1010))
35
R101{ } -.- 1011
36
R110{ } ---|H5| 1100((1100))
37
R110{ } -.- 1101
38
R111{ } -.- 1110
39
R111{ } ---|H2| 1111((1111))
40
end
41
42
subgraph Real
43
AppSnapshot ---|H1452| Root{ }
44
Root{ } ---|H1| L0101((0101))
45
Root{ } ---|H452| H452{ }
46
H452{ } ---|H4| L1010((1010))
47
H452{ } ---|H52| H52{ }
48
H52{ } ---|H5| L1100((1100))
49
H52{ } ---|H2| L1111((1111))
50
end
51
52
classDef className stroke-width:3px
53
class 1100,R110,R11,R1,R className
54
class L1100,H52,H452,Root className
55
class App,AppSnapshot className
Copied!
Last modified 6mo ago
Copy link