Дерево хешей

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

Построение править

Пример хеш-дерева в биткойн-блоке

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

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

Если количество блоков на каком-то уровне дерева оказывается нечетным, то один блок дублируется^[1] или переносится без изменений на следующий уровень, как это происходит при вычислении Tiger Tree Hash^[2].

Эффективность править

Доказательство существования в хеш-дереве

Хеш-деревья имеют преимущество перед хеш-цепочками или хеш-функциями. При использовании хеш-деревьев гораздо менее затратным является доказательство принадлежности определённого блока данных к множеству. Поскольку различными блоками часто являются независимые данные, такие как транзакции или части файлов, то нас интересует возможность проверить только один блок, не пересчитывая хеши для остальных узлов дерева. Пусть интересующий нас блок — это $L_{3}$ (см. рис.). Тогда доказательством его существования и валидности будут корневой хеш, а также верхние хеши других веток ( ${auth_{L}}_{4}=Hash_{11}$ и ${auth_{L}}_{2}=Hash_{0}$ )^[1]^[3]. В данном случае проверка не пройдена, если $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$ .

В общем случае можно записать

$signature(L)=(L\ |\ {auth_{L}}_{1},\dots ,{auth_{L}}_{K-1})$ ,

а проверку осуществить как $TopHash==Hash_{K}$ , где

$Hash_{k}={\begin{cases}hash(L),&{\mbox{if }}k=1,\\hash(Hash_{k-1}+{auth_{L}}_{k-1}),&{\mbox{if }}2\leq k\leq K\end{cases}}$ .

Набор блоков $\{{auth_{L}}_{1},\dots ,{auth_{L}}_{K-1}\}$ называется аутентификационный путь или путь Меркла^[1].

Видно, что проверку выше можно выполнить за $O(K)=O(\log _{2}N)$ действий, где $K$ — это высота дерева или длина аутентификационного пути, а $N$ — это количество блоков данных. Такая же проверка в случае хеш-цепочки имела бы сложность $O(N)$ ^[1]^[4].

Таблица ниже демонстрирует, что даже при значительном количестве транзакций в блоке о сложности вычислений можно не беспокоиться^[1].

Количество транзакций	Приблизительный размер блока	Размер пути (в хешах)	Размер пути (в байтах)
16 транзакций	4 килобайта	4 хеша	128 байт
512 транзакций	128 килобайт	9 хэшей	288 байт
2048 транзакций	512 килобайт	11 хэшей	352 байт
65535 транзакций	16 мегабайт	16 хэшей	512 байт

Упрощенная проверка оплаты править

Блок биткойна хранит только значение merkle_root своих транзакций. Это позволяет получить определённые преимущества и снизить нагрузку на сеть.

После накопления достаточного числа блоков можно удалять старые транзакции для экономии места. При этом сам блок остается неизменным, так как в нём хранится только merkle_root. Блок без транзакций занимает 80 Б, или 4,2 МБ в год (при генерации блока каждые 10 минут)^[5].

Становится возможной упрощенная проверка оплаты (англ. Simplified payment verification). SPV-узел загружает не весь блок, а только заголовок блока. Для интересующей его транзакции он запрашивает также её аутентификационный путь. Таким образом он загружает всего несколько килобайт, тогда как полный размер блока может быть больше 10 мегабайт (см. таблицу)^[1]. Использование этого метода, однако, требует, чтобы пользователь доверял узлу сети, у которого будет запрашивать заголовки блоков. Один из способов избежать атаки, то есть подмены узла недобросовестной стороной, — рассылать оповещения по всей сети при обнаружении ошибки в блоке, вынуждая пользователя загружать блок целиком^[5].

На упрощенной проверке оплаты основана работа так называемых «тонких» биткойн-клиентов^[6]^[7].

Дополнительно править

Проблема обхода дерева Меркла править

Дерево Меркла имеет также и недостатки, проявляющиеся при растущем количестве листьев. Как было показано ранее, для вычисления подписи произвольного блока $L$ нужно знать все значения из множества $\{{auth_{L}}_{i}\}$ . Это не вызывает проблем, если есть возможность хранить все внутренние вершины дерева в памяти, однако для больших деревьев (количество листьев может увеличиваться до $2^{40}$ ) это не подходит. Можно также каждый раз вычислять внутренние блоки заново, но это значительно понизит производительность такой системы. Поэтому возникает проблема эффективного обхода дерева и генерации подписей (англ. Merkle tree traversal problem)^[4]. На сегодняшний день существуют решения, использующие $2\log _{2}(N)$ времени и $3\log _{2}(N)$ памяти, где $N$ — это количество листьев. Было также доказано, что не существует алгоритма обхода, который бы был одновременно лучше, чем $O(\log _{2}(N))$ и по времени, и по памяти^[8].

Примечания править

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ Antonopoulos, Andreas M.,. Mastering bitcoin : unlocking digital cryptocurrencies. — First edition. — Sebastopol, CA. — xxi, 272 pages с. — ISBN 9781449374044. Архивировано 19 января 2018 года.
↑ ¹ ² J. Chapweske, G. Mohr. Tree Hash EXchange format (THEX) (англ.). Onion Networks, Inc. (4 марта 2003). — Стандарт обмена хеш-деревьями над файлами. Дата обращения: 8 декабря 2017. Архивировано 4 марта 2018 года.
↑ Einar Mykletun, Maithili Narasimha, Gene Tsudik. Providing Authentication and Integrity in Outsourced Databases using Merkle Hash Tree’s (англ.) // ACM Transactions on Storage : Журнал. — 2006. — Май (vol. 2, no. 2). — P. 107—138. Архивировано 19 февраля 2020 года.
↑ ¹ ² Georg Becker, Ruhr-universität Bochum. Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis. Архивировано 14 декабря 2017 года.
↑ ¹ ² Сатоси Накамото. Биткойн: система цифровой пиринговой наличности (рус.) // bitcoin.org. Архивировано 5 апреля 2018 года.
↑ Israa Alqassem, Davor Svetinovic. Towards Reference Architecture for Cryptocurrencies: Bitcoin Architectural Analysis (англ.) // IEEE International Conference on Internet of Things (iThings), and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) : журнал. — 2014. — Сентябрь. — ISBN 978-1-4799-5967-9. — doi:10.1109/iThings.2014.78. Архивировано 2 апреля 2018 года.
↑ Simplified Payment Verification (англ.). Глоссарий Bitcoin. Дата обращения: 7 декабря 2017. Архивировано 7 декабря 2017 года.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (англ.) // Advances in Cryptology - EUROCRYPT 2004. — Springer, Berlin, Heidelberg, 2004-05-02. — P. 541–554. — ISBN 9783540219354, 9783540246763. — doi:10.1007/978-3-540-24676-3_32. Архивировано 15 декабря 2017 года.

См. также править

Ссылки править

Merkle Patricia Tree — улучшенная реализация дерева Меркла, использующаяся в Ethereum.
Tiger Tree Torrent — предложение по замене SHA-1 на Tiger Tree Hash в .torrent файлах.

[:4-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ Antonopoulos, Andreas M.,. Mastering bitcoin : unlocking digital cryptocurrencies. — First edition. — Sebastopol, CA. — xxi, 272 pages с. — ISBN 9781449374044. Архивировано 19 января 2018 года.

[:2-2] ¹ ² J. Chapweske, G. Mohr. Tree Hash EXchange format (THEX) (англ.). Onion Networks, Inc. (4 марта 2003). — Стандарт обмена хеш-деревьями над файлами. Дата обращения: 8 декабря 2017. Архивировано 4 марта 2018 года.

[:1-3] Einar Mykletun, Maithili Narasimha, Gene Tsudik. Providing Authentication and Integrity in Outsourced Databases using Merkle Hash Tree’s (англ.) // ACM Transactions on Storage : Журнал. — 2006. — Май (vol. 2, no. 2). — P. 107—138. Архивировано 19 февраля 2020 года.

[:5-4] ¹ ² Georg Becker, Ruhr-universität Bochum. Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis. Архивировано 14 декабря 2017 года.

[:0-5] ¹ ² Сатоси Накамото. Биткойн: система цифровой пиринговой наличности (рус.) // bitcoin.org. Архивировано 5 апреля 2018 года.

[:7-6] Israa Alqassem, Davor Svetinovic. Towards Reference Architecture for Cryptocurrencies: Bitcoin Architectural Analysis (англ.) // IEEE International Conference on Internet of Things (iThings), and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) : журнал. — 2014. — Сентябрь. — ISBN 978-1-4799-5967-9. — doi:10.1109/iThings.2014.78. Архивировано 2 апреля 2018 года.

[7] Simplified Payment Verification (англ.). Глоссарий Bitcoin. Дата обращения: 7 декабря 2017. Архивировано 7 декабря 2017 года.

[:3-8] Michael Szydlo. Merkle Tree Traversal in Log Space and Time (англ.) // Advances in Cryptology - EUROCRYPT 2004. — Springer, Berlin, Heidelberg, 2004-05-02. — P. 541–554. — ISBN 9783540219354, 9783540246763. — doi:10.1007/978-3-540-24676-3_32. Архивировано 15 декабря 2017 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]