Eng

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):

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
PreviousNode structureNextTestNet architecture

Last updated