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. 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. 2.
    The hash is calculated for each sheet and node.
  3. 3.
    The sheet hash is calculated from the data it contains (by the state of the item).
  4. 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. 1.
    Storing the state of an element for each point in time (history of changes).
  2. 2.
    Minimizing the time of receiving the value of an element by its identifier.
  3. 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):
graph TD
root{ } --- R0
root{ } --- R1
R0{ } --- R00
R0{ } --- R01
R1{ } --- R10
R1{ } --- R11
R00{ } --- R000
R00{ } --- R001
R01{ } --- R010
R01{ } --- R011
R10{ } --- R100
R10{ } --- R101
R11{ } --- R110
R11{ } --- R111
R000{ } --- 0000
R000{ } --- 0001
R001{ } --- 0010
R001{ } --- 0011
R010{ } --- 0100
R010{ } --- 0101
R011{ } --- 0110
R011{ } --- 0111
R100{ } --- 1000
R100{ } --- 1001
R101{ } --- 1010
R101{ } --- 1011
R110{ } --- 1100
R110{ } --- 1101
R111{ } --- 1110
R111{ } --- 1111
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)):
graph TD
subgraph Virtual
App[AppSnapshot] ---|H1| R
R{ } ---|H1| R0
R{ } -.- R1
R0{ } -.- R00
R0{ } ---|H1| R01
R1{ } -.- R10
R1{ } -.- R11
R00{ } -.- R000
R00{ } -.- R001
R01{ } ---|H1| R010
R01{ } -.- R011
R10{ } -.- R100
R10{ } -.- R101
R11{ } -.- R110
R11{ } -.- R111
R000{ } -.- 0000
R000{ } -.- 0001
R001{ } -.- 0010
R001{ } -.- 0011
R010{ } -.- 0100
R010{ } ---|H1| 0101((0101))
R011{ } -.- 0110
R011{ } -.- 0111
R100{ } -.- 1000
R100{ } -.- 1001
R101{ } -.- 1010
R101{ } -.- 1011
R110{ } -.- 1100
R110{ } -.- 1101
R111{ } -.- 1110
R111{ } -.- 1111
end
subgraph Real
AppSnapshot ---|H1| L0101((0101))
end
classDef className stroke-width:3px
class 0101,R010,R01,R0,R className
class L0101,Root className
class App,AppSnapshot className
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):
graph TD
subgraph Virtual
App[AppSnapshot] ---|H12| R
R{ } ---|H1| R0
R{ } ---|H2| R1
R0{ } -.- R00
R0{ } ---|H1| R01
R1{ } -.- R10
R1{ } ---|H2| R11
R00{ } -.- R000
R00{ } -.- R001
R01{ } ---|H1| R010
R01{ } -.- R011
R10{ } -.- R100
R10{ } -.- R101
R11{ } -.- R110
R11{ } ---|H2| R111
R000{ } -.- 0000
R000{ } -.- 0001
R001{ } -.- 0010
R001{ } -.- 0011
R010{ } -.- 0100
R010{ } ---|H1| 0101((0101))
R011{ } -.- 0110
R011{ } -.- 0111
R100{ } -.- 1000
R100{ } -.- 1001
R101{ } -.- 1010
R101{ } -.- 1011
R110{ } -.- 1100
R110{ } -.- 1101
R111{ } -.- 1110
R111{ } ---|H2| 1111((1111))
classDef className stroke-width:3px
class 1111,R111,R11,R1,R className
end
subgraph Real
AppSnapshot ---|H12| Root{ }
Root{ } ---|H1| L0101((0101))
Root{ } ---|H2| L1111((1111))
end
classDef className stroke-width:3px
class 1111,R111,R11,R1,R className
class L1111,H12,Root className
class App,AppSnapshot className
After adding one more element (A-1010) we get:
graph TD
subgraph Virtual
App[AppSnapshot] ---|H142| R
R{ } ---|H1| R0
R{ } ---|H32| R1
R0{ } -.- R00
R0{ } ---|H1| R01
R1{ } ---|H3| R10
R1{ } ---|H2| R11
R00{ } -.- R000
R00{ } -.- R001
R01{ } ---|H1| R010
R01{ } -.- R011
R10{ } -.- R100
R10{ } ---|H3| R101
R11{ } -.- R110
R11{ } ---|H2| R111
R000{ } -.- 0000
R000{ } -.- 0001
R001{ } -.- 0010
R001{ } -.- 0011
R010{ } -.- 0100
R010{ } ---|H1| 0101((0101))
R011{ } -.- 0110
R011{ } -.- 0111
R100{ } -.- 1000
R100{ } -.- 1001
R101{ } ---|H3| 1010((1010))
R101{ } -.- 1011
R110{ } -.- 1100
R110{ } -.- 1101
R111{ } -.- 1110
R111{ } ---|H2| 1111((1111))
end
subgraph Real
AppSnapshot ---|H123| Root{ }
Root{ } ---|H1| L0101((0101))
Root{ } ---|H32| H32{ }
H32{ } ---|H3| L1010((1010))
H32{ } ---|H2| L1111((1111))
end
classDef className stroke-width:3px
class 1010,R101,R10,R1,R className
class L1010,H32,Root className
class App,AppSnapshot className
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):
graph TD
subgraph Virtual
App[AppSnapshot] ---|H142| R
R{ } ---|H1| R0
R{ } ---|H42| R1
R0{ } -.- R00
R0{ } ---|H1| R01
R1{ } ---|H4| R10
R1{ } ---|H2| R11
R00{ } -.- R000
R00{ } -.- R001
R01{ } ---|H1| R010
R01{ } -.- R011
R10{ } -.- R100
R10{ } ---|H4| R101
R11{ } -.- R110
R11{ } ---|H2| R111
R000{ } -.- 0000
R000{ } -.- 0001
R001{ } -.- 0010
R001{ } -.- 0011
R010{ } -.- 0100
R010{ } ---|H1| 0101((0101))
R011{ } -.- 0110
R011{ } -.- 0111
R100{ } -.- 1000
R100{ } -.- 1001
R101{ } ---|H4| 1010((1010))
R101{ } -.- 1011
R110{ } -.- 1100
R110{ } -.- 1101
R111{ } -.- 1110
R111{ } ---|H2| 1111((1111))
end
subgraph Real
AppSnapshot ---|H142| Root{ }
Root{ } ---|H1| L0101((0101))
Root{ } ---|H42| H42{ }
H42{ } ---|H4| L1010((1010))
H42{ } ---|H2| L1111((1111))
end
classDef className stroke-width:3px
class 1010,R101,R10,R1,R className
class L1010,H42,Root className
class App,AppSnapshot className
When adding a new element, there are also changes along the path from the top to that element (added A-1100):
graph TD
subgraph Virtual
App[AppSnapshot] ---|H1452| root
root{ } ---|H1| R0
root{ } ---|H452| R1
R0{ } -.- R00
R0{ } ---|H1| R01
R1{ } ---|H4| R10
R1{ } ---|H52| R11
R00{ } -.- R000
R00{ } -.- R001
R01{ } ---|H1| R010
R01{ } -.- R011
R10{ } -.- R100
R10{ } ---|H4| R101
R11{ } ---|H5| R110
R11{ } ---|H2| R111
R000{ } -.- 0000
R000{ } -.- 0001
R001{ } -.- 0010
R001{ } -.- 0011
R010{ } -.- 0100
R010{ } ---|H1| 0101((0101))
R011{ } -.- 0110
R011{ } -.- 0111
R100{ } -.- 1000
R100{ } -.- 1001
R101{ } ---|H4| 1010((1010))
R101{ } -.- 1011
R110{ } ---|H5| 1100((1100))
R110{ } -.- 1101
R111{ } -.- 1110
R111{ } ---|H2| 1111((1111))
end
subgraph Real
AppSnapshot ---|H1452| Root{ }
Root{ } ---|H1| L0101((0101))
Root{ } ---|H452| H452{ }
H452{ } ---|H4| L1010((1010))
H452{ } ---|H52| H52{ }
H52{ } ---|H5| L1100((1100))
H52{ } ---|H2| L1111((1111))
end
classDef className stroke-width:3px
class 1100,R110,R11,R1,R className
class L1100,H52,H452,Root className
class App,AppSnapshot className
Copy link
On this page
Merkle's Discharged Tree