Rus

Дерево состояний

Дерево состояний выступает хранилищем данных.

Дерево состояний позволяет хранить только наборы данных, которым можно заранее присвоить идентификатор или адрес в виде 8-байтового числа. По этому идентификатору они и адресуются.

Например, каждый аккаунт имеет свой идентификатор, который рассчитывается по публичному ключу. Этот идентификатор и выступает адресом объекта в рамках дерева состояний. Для того, чтобы однозначно определять состояние аккаунта в конкретный момент времени, все состояния аккаунтов объединяются в хеш-дерево состояний. В дальнейшем, вершина дерева состояний используется как идентификатор общего состояния приложения.

Разряженное дерево Меркла

В целом, дерево состояний похоже на дерево Меркла. Классическое дерево Меркла ориентировано на хранение фиксированного списка элементов или на хранение хронологически добавляемых элементов, т.е. идет сплошной поток элементов без разрывов.

В дереве состояний хранится относительно немного элементов, но при этом имеется четкая область значений и конкретный адрес каждого элемента. После чего эти элементы объединяются в дерево Меркла. Мы называем это “разряженным деревом Меркла”.

Дерево состояний представляет из себя бинарное дерево, в котором для каждого состояния элемента есть четко закрепленная позиция (задаваемая по ID элемента).

Дерево строится по следующим принципам:

  1. ID элемента однозначно определяет лист, в котором должно храниться состояние этого элемента. В листе дерева хранится текущее состояние элемента.

  2. Для каждого листа и узла рассчитывается его хеш.

  3. Хеш листа рассчитывается по содержащимся в нем данным (т.е. по состоянию элемента).

  4. Хеш узла рассчитывается по хешам левого и правого поддеревьев. Если левого или правого поддерева у узла нет, то хеш равен хешу того поддерева, которое есть.

Благодаря подобной структуре удалось достичь:

  1. Хранение состояния элемента для каждого момента времени (история изменений).

  2. Минимизация времени получения значения элемента по его идентификатору.

  3. Минимизация изменений в дереве состояний с течением времени (изменения затрагивают только новые или измененные листы и “путь” от них до вершины дерева).

Помимо быстрого доступа к состоянию элемента, дерево состояний обеспечивает дополнительный уровень валидации состояния сети.

Если после обработки блока данных, хеш вершины дерева состояний не совпал с тем, что получилось на удаленном пире, то набор данных не принимается, т.к. он был по-разному обработан на разных пирах.

Пример работы разряженное дерево Меркла

Например, дерево состояний для 16 (2^4) элементов выглядит так (в реальном дереве 9’223’372’036’854’775’808 (2^64) возможных позиций):

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

В нем указаны все возможные элементы.

Следует различать виртуальное состояние дерева и его реальное представление. Например, для дерева из 1 элемента (с ID A-0101) будет фактически храниться только 1 лист (Virtual - виртуальное представление дерева, Real - реальное, которое будет использоваться для поиска данных в снапшоте (текущем срезе)):

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

Если в дерево добавить еще один элемент (A-0111), то получим следующее (для бинарного дерева количество узлов на единицу меньше количества листов):

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

После добавления еще одного элемента (A-1010) получим:

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

Если же происходит изменение состояния существующего элемента, то изменяются только узлы по пути от вершины до этого элемента (например, изменилось состояние A-1010):

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

При добавлении нового элемента также происходят изменения по пути от вершины до этого элемента (добавлен 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
PreviousСтруктура пираNextАрхитектура TestNet

Last updated