Просмотр кода страницы Дерево хешей

[[Файл:Hash Tree.svg|thumb|300px|right|Двоичное хеш-дерево]]
'''Дерево хешей''' (''дерево Меркла'') — полное [[двоичное дерево]], в листовые вершины которого помещены [[Хеширование|хеши]] от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Корневой узел дерева содержит хеш от всего набора данных, то есть хеш-дерево является однонаправленной хеш-функцией. Применяется для эффективного хранения транзакций в [[блокчейн]]е [[Криптовалюта|криптовалют]] (например, в [[Bitcoin]], [[Ethereum]]). Оно позволяет получить «отпечаток» всех транзакций в блоке, а также эффективно верифицировать транзакции<ref name=":4">{{Книга |автор=Antonopoulos, Andreas M. |заглавие=Mastering bitcoin: unlocking digital cryptocurrencies |язык=en |ссылка=https://www.worldcat.org/oclc/876351095 |издание=1st ed |место=Sebastopol, CA |страниц=xxi, 272 |isbn=9781449374044 |archivedate=2018-01-19 |archiveurl=https://web.archive.org/web/20180119175504/https://www.worldcat.org/oclc/876351095}}</ref>. Названо по имени [[Меркл, Ральф|Ральфа Меркла]], предложившего в 1979 году соответствующую технику хеширования криптографических функций.

== Построение ==
[[Файл:Hash Tree bitcoin.svg|мини|300x300px|Пример хеш-дерева в биткойн-блоке]]
Заполнение значений в узлах дерева идёт снизу вверх. Сперва к каждому блоку данных применяется хеширование <math>\mathrm{Hash}_{00} = \operatorname{hash}(L_1)</math>, <math>\mathrm{Hash}_{01} = \operatorname{hash}(L_2)</math> и так далее. Полученные значения записываются в листья дерева. Блоки, находящиеся уровнем выше, заполняются как хеши от суммы своих детей, <math>\mathrm{Hash}_0 = \operatorname{hash}(\mathrm{Hash}_{00} + \mathrm{Hash}_{01})</math>, где <math>+</math> обычно означает [[Конкатенация|конкатенацию]]. Эта операция повторяется, пока не будет получено верхнее значение — <math>\mathrm{TopHash}</math> или <code>merkle_root</code><ref name=":4" />.

В биткойне в качестве хеш-функции используется двойное [[SHA-2|SHA-256]], то есть <math>\operatorname{hash}(x) = \operatorname{SHA256}(\operatorname{SHA256}(x))</math><ref name=":4" />. Впрочем, хеш-функция может быть любой, например Tiger Tree Hash (TTH), используемый в файлообменных [[P2P]]-сетях, является деревом Меркла с хеш-функцией [[Tiger (хеш-функция)|Tiger]]<ref name=":2">{{Cite web |url=http://adc.sourceforge.net/draft-jchapweske-thex-02.html#anchor2 |title=Tree Hash EXchange format (THEX) |lang=en |author={{nobr|J. Chapweske}}, {{nobr| G. Mohr}} |website= |description=Стандарт обмена хеш-деревьями над файлами |date=2003-03-04 |publisher=Onion Networks, Inc. |lang=en |accessdate=2017-12-08 |archive-date=2018-03-04 |archive-url=https://web.archive.org/web/20180304055310/http://adc.sourceforge.net/draft-jchapweske-thex-02.html#anchor2 |deadlink=no}}</ref>.

Если количество блоков на каком-то уровне дерева оказывается нечётным, то один блок дублируется<ref name=":4" /> или переносится без изменений на следующий уровень, как это происходит при вычислении Tiger Tree Hash<ref name=":2" />.

== Эффективность ==
[[Файл:Hash Tree proof.svg|мини|300x300px|Доказательство существования в хеш-дереве]]
Хеш-деревья имеют преимущество перед хеш-цепочками или хеш-функциями. При использовании хеш-деревьев гораздо менее затратным является доказательство принадлежности определённого блока данных к множеству. Поскольку различными блоками часто являются независимые данные, такие как транзакции или части файлов, то нас интересует возможность проверить только один блок, не пересчитывая хеши для остальных узлов дерева. Пусть интересующий нас блок — это <math>L_3</math> (см. рис.). Тогда доказательством его существования и валидности будут корневой хеш, а также верхние хеши других веток (<math>\mathrm{auth}_{L_4} = \mathrm{Hash}_{11}</math> и <math>\mathrm{auth}_{L_2} = \mathrm{Hash}_0</math>)<ref name=":4" /><ref name=":1">{{Статья |автор={{nobr|Einar Mykletun}}, {{nobr|Maithili Narasimha}}, {{nobr|Gene Tsudik}} |заглавие=Providing Authentication and Integrity in Outsourced Databases using Merkle Hash Tree’s |ссылка=https://people.eecs.berkeley.edu/~raluca/cs261-f15/readings/merkleodb.pdf |язык=en |издание=ACM Transactions on Storage |тип=Журнал |год=2006 |месяц=май |том=2 |номер=2 |страницы=107—138 |issn= |archivedate=2020-02-19 |archiveurl=https://web.archive.org/web/20200219062943/https://people.eecs.berkeley.edu/~raluca/cs261-f15/readings/merkleodb.pdf}}</ref>. В данном случае проверка не пройдена, если <math>\mathrm{TopHash} \neq \operatorname{hash}\big(\mathrm{Hash}_0 + \operatorname{hash}(\operatorname{hash}(L_3) + \mathrm{Hash}_{11})\big)</math>.

В общем случае можно записать
: <math>\operatorname{signature}(L) = (L \mid \mathrm{auth}_{L_1}, \dots, \mathrm{auth}_{L_{K-1}}),</math>
а проверку осуществить как <math>\mathrm{TopHash} = \mathrm{Hash}_K</math>, где
: <math>\mathrm{Hash}_k = \begin{cases}
  \operatorname{hash}(L),  & \text{если } k = 1, \\
  \operatorname{hash}(\mathrm{Hash}_{k-1} + \mathrm{auth}_{L_{k-1}}), & \text{если } 2 \leqslant k \leqslant K.
\end{cases}</math>

Набор блоков <math>\{\mathrm{auth}_{L_1}, \dots, \mathrm{auth}_{L_{K-1}}\} </math> называется ''аутентификационный путь'' или ''путь Меркла''<ref name=":4" />.

Видно, что проверку выше можно выполнить за <math>O(K) = O(\log_2 N)</math> действий, где <math>K</math> — это высота дерева или длина аутентификационного пути, а <math>N</math> — это количество блоков данных. Такая же проверка в случае хеш-цепочки имела бы сложность <math>O(N)</math><ref name=":4" /><ref name=":5">{{Книга |автор=Georg Becker |заглавие=Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis |язык=en |ссылка=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.392.7879 |archivedate=2017-12-14 |archiveurl=https://web.archive.org/web/20171214125700/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.392.7879}}</ref>.

Таблица ниже демонстрирует, что даже при значительном количестве транзакций в блоке о сложности вычислений можно не беспокоиться<ref name=":4" />.
{| class="wikitable" style="text-align:right"
! Количество<br/> транзакций
! Приблизительный<br/> размер блока
! Размер пути<br/> (в хешах)
! Размер пути<br/> (в байтах)
|-
| 16
| 4 килобайта
| 4
| 128
|-
| 512
| 128 килобайт
| 9
| 288
|-
| 2048
| 512 килобайт
| 11
| 352
|-
| 65535
| 16 мегабайт
| 16
| 512
|}

== Упрощенная проверка оплаты ==
Заголовок блока Биткойна хранит значение <code>merkle_root</code> - то есть хеш всех транзакций в блоке. Это создает определённые преимущества и позволяет снизить общую нагрузку на сеть.

После накопления достаточного числа блоков появляется возможность удалять старые транзакции для экономии места. При этом заголовок блока остаётся неизменным, так как в нём хранится только <code>merkle_root</code>. Блок без транзакций занимает 80 Б, или 4,2 МБ в год (при генерации блока каждые 10 минут)<ref name=":0">{{Статья |автор=Сатоси Накамото |заглавие=Биткойн: система цифровой пиринговой наличности |ссылка=https://bitcoin.org/files/bitcoin-paper/bitcoin_ru.pdf |язык=ru |издание=bitcoin.org |archivedate=2018-04-05 |archiveurl=https://web.archive.org/web/20180405212930/https://bitcoin.org/files/bitcoin-paper/bitcoin_ru.pdf}}</ref>.

Становится возможной упрощённая проверка оплаты ({{lang-en|simplified payment verification}}). SPV-узел загружает не весь блок, а только его заголовок. Для интересующей его транзакции он запрашивает также её аутентификационный путь. Таким образом он загружает всего несколько килобайт, тогда как полный размер блока может быть больше 10 мегабайт (см. таблицу)<ref name=":4" />. Использование этого метода, однако, требует, чтобы пользователь доверял узлу сети, у которого будет запрашивать заголовки блоков. Один из способов избежать атаки, то есть подмены узла недобросовестной стороной, — рассылать оповещения по всей сети при обнаружении ошибки в блоке, вынуждая пользователя загружать блок целиком<ref name=":0" />.

На упрощённой проверке оплаты основана работа так называемых «тонких» биткойн-клиентов<ref name=":7">{{Статья |автор=Israa Alqassem, Davor Svetinovic |заглавие=Towards Reference Architecture for Cryptocurrencies: Bitcoin Architectural Analysis |ссылка=http://ieeexplore.ieee.org/abstract/document/7059703/authors |язык=en |издание=IEEE International Conference on Internet of Things (iThings), and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) |тип=журнал |год=2014 |месяц=09  |страницы= |isbn=978-1-4799-5967-9 |doi=10.1109/iThings.2014.78 |archivedate=2018-04-02 |archiveurl=https://web.archive.org/web/20180402123651/http://ieeexplore.ieee.org/abstract/document/7059703/authors}}</ref><ref>{{Cite web |url=https://bitcoin.org/en/glossary/simplified-payment-verification |title=Simplified Payment Verification |website=Глоссарий Bitcoin |lang=en |accessdate=2017-12-07 |archive-date=2017-12-07 |archive-url=https://web.archive.org/web/20171207191927/https://bitcoin.org/en/glossary/simplified-payment-verification |deadlink=no}}</ref>.

== Дополнительно ==

=== Проблема обхода дерева Меркла ===
Дерево Меркла имеет также и недостатки, проявляющиеся при растущем количестве листьев. Как было показано ранее, для вычисления подписи произвольного блока <math>L</math> нужно знать все значения из множества <math>\{\mathrm{auth}_{L_i}\}</math>. Это не вызывает проблем, если есть возможность хранить все внутренние вершины дерева в памяти, однако для больших деревьев (количество листьев может увеличиваться до <math>2^{40}</math>) это не подходит. Можно также каждый раз вычислять внутренние блоки заново, но это значительно понизит производительность такой системы. Поэтому возникает проблема эффективного обхода дерева и генерации подписей ({{Lang-en|Merkle tree traversal problem}})<ref name=":5" />. На сегодняшний день существуют решения, использующие <math>2\log_2(N)</math> времени и <math>3\log_2(N)</math> памяти, где <math>N</math> — это количество листьев. Было также доказано, что не существует алгоритма обхода, который бы был одновременно лучше, чем <math>O(\log_2(N))</math> и по времени, и по памяти<ref name=":3">{{Статья |автор=Michael Szydlo |заглавие=Merkle Tree Traversal in Log Space and Time |ссылка=https://link.springer.com/chapter/10.1007/978-3-540-24676-3_32 |язык=en |издание=Advances in Cryptology — EUROCRYPT 2004 |издательство=Springer |место=Berlin, Heidelberg |год=2004-05-02 |страницы=541—554 |isbn=9783540219354, 9783540246763 |doi=10.1007/978-3-540-24676-3_32 |archivedate=2017-12-15 |archiveurl=https://web.archive.org/web/20171215111340/https://link.springer.com/chapter/10.1007/978-3-540-24676-3_32}}</ref>.

== Примечания ==
{{примечания}}

== См. также ==
* [[Подпись Меркла]]
* [[Двоичное дерево]]
* [[Tiger (хеш-функция)]]
* [[Magnet-ссылка]]
* [[URN]]

== Ссылки ==
* [https://eth.wiki/en/fundamentals/patricia-tree Merkle Patricia Tree] — улучшенная реализация дерева Меркла, использующаяся в Ethereum.
* [https://web.archive.org/web/20130401041139/http://forum.bittorrent.org/viewtopic.php?id=360  Tiger Tree Torrent] — предложение по замене [[SHA-1]] на [[Tiger Tree Hash]] в [[.torrent]]-файлах.

{{Хеш-алгоритмы}}
{{Деревья (структуры данных)}}

[[Категория:Хеш-функции]]
[[Категория:Деревья (структуры данных)]]