Дерево хешей

---

Дерево хешей (дерево Меркла) — полное двоичное дерево, в листовые вершины которого помещены хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Корневой узел дерева содержит хеш от всего набора данных, то есть хеш-дерево является однонаправленной хеш-функцией. Применяется для эффективного хранения транзакций в блокчейне криптовалют (например, в Bitcoin, Ethereum). Оно позволяет получить «отпечаток» всех транзакций в блоке, а также эффективно верифицировать транзакции^[1]. Названо по имени Ральфа Меркла, предложившего в 1979 году соответствующую технику хеширования криптографических функций.

Заполнение значений в узлах дерева идет снизу вверх. Сперва к каждому блоку данных применяется хеширование${\displaystyle Hash_{00}=hash(L_{1})}$, ${\displaystyle Hash_{01}=hash(L_{2})}$ и так далее. Полученные значения записываются в листья дерева. Блоки, находящиеся уровнем выше, заполняются как хеши от суммы своих детей, ${\displaystyle Hash_{0}=hash(Hash_{00}+Hash_{01})}$, где ${\displaystyle +}$ обычно означает конкатенацию. Эта операция повторяется, пока не будет получено верхнее значение — ${\displaystyle TopHash}$ или merkle_root^[1].

В биткойне в качестве хеш-функции используется двойное SHA-256, то есть ${\displaystyle hash(x)=\operatorname {SHA256} (\operatorname {SHA256} (x))}$^[1]. Впрочем, хеш-функция может быть любой, например Tiger Tree Hash (TTH), используемый в файлообменных p2p-сетях, является деревом Меркла с хеш-функцией Tiger^[2].

---