← Timeline
Avatar
Chelovekopodobny Robot
(updated )
Merkle Tree

Хочу рассказать об одной структуре данных, которая одновременно (1) красивая, (2) полезная, (3) на мой взгляд, недостаточно популярная (т.е. я буквально несколько раз в год попадаю в ситуацию, когда человек, от которого я жду, что у него это будет от зубов отскакивать, понятия об этом не имеет). И даже вот Shmuel Leib Melamud, рассказывая про bitcoin, ухитрился обойти её молчанием: рассказ построен так, что эта техническая деталь, может быть, и вправду в нём лишняя, но ведь кросивое же!

Итак, речь пойдёт о Merkle Tree, но перед этим освежим понятие криптографической хэш-функции. Начать можно опять же с заметки @lamed, я не надеюсь рассказать лучше, но хотелось бы добавить формализма.

В криптографических рассуждениях используются две модели, описывающие криптографическую хэш-функцию. Одна из них (модель случайного оракула) фактически пересказана по ссылке выше: она состоит в том, что некий "оракул" (или "паспортный стол") по предъявлении какого-то числа (или набора байтов) вспоминает, видел ли он точно такие же данные раньше. Если не видел, он выдаёт в ответ "паспорт числа": случайное целое число из интервала [0..2^512-1], выбранное так, что все возможные "паспорта" равновероятны. Если же оракул уже видел такие данные, он выдаёт точно такой же "паспорт", который выдал для этих данных в прошлый раз.

Модель случайного оракула -- недостижимый идеал, которому стремятся подражать настоящие криптографические хэш-функции (просто взять и реализовать этот идеал они не могут -- у них нет внутреннего состояния, они не "помнят" и не "знают", для каких данных их вызывали раньше). Самые важные критерии подражания дают нам вторую модель: три критерия, делающие хэш-функцию "криптографически удовлетворительной". Критерии:

  1. Для заданного "паспорта" нельзя вычислить исходные данные сильно быстрее, чем перебором вариантов исходных данных (невозможность preimage attack)
  2. Для заданной пары исходных данных и "паспорта" нельзя подобрать второй набор исходных данных, который имеет совпадающий паспорт (невозможность second preimage attack)
  3. Никто не может за разумное время предъявить два разных набора исходных данных с одинаковым "паспортом" (трудность поиска коллизий).

Очевидно, что случайный оракул подходит под три критерия, т.е. это более "сильная" конструкция (бывает так, что какое-то свойство протокола, использующего хэш-функцию, доказано в модели случайного оракула, но не доказано при более слабых требованиях "трех свойств").

Итак, вернёмся к нашим деревьям (названным по имени изобретателя, Ralph Merkle, и он не Merkel, хотя его так регулярно обзывают):

Предположим, у нас есть 100500 упорядоченных однородных объектов (дисковых блоков, записей в бухгалтерской книге, картинок с котиками...). Применим к каждому из них криптографическую хэш-функцию, получив 100500 значений хэша. Затем разобъём список значений на пары, получив 50250 пар, и для каждой пары вычислим криптографическую хэш-функцию от "склеенных вместе" значений этой пары. Полученные 50250 хэшев разобъём на 25125 пар, повторим процедуру (обнаружив на каком-то уровне нечётное количество хэшей, мы "добиваем" его до чётного, обычно это делается дублированием последнего элемента в списке). В конце концов мы получаем "слой" из всего двух значений хэша, который на следующем шаге превращается в одно значениe. Это последнее значение называется "Merkle root" -- корнем нашего дерева. Из корня растут две "веточки", из каждой из них в свою очередь растут ещё две веточки, и так далее, пока мы не придём к "листьям", каждый из которых содержит хэш-функцию от элемента нашего первоначального набора из 100500 объектов.

Итак, мы старались, вычисляли примерно 201000 хэш-функций, и что это нам даёт? А даёт нам это очень интересную штуку: если известен Merkle root какого-то набора объектов, мы можем предъявить объект, соответствующий "листику" в нашем дереве, и предъявить несколько значений хэш-функции (для парного к нему "листика", затем, поднявшись на уровень выше, для парной "веточки", и так далее, пока не дойдём до merkle root -- для 100500 объектов таких значений будет 17 штук), и доказать за пределами разумных сомнений, что этот объект находится в исходном наборе, причём на определённой позиции (иногда это важно, иногда не очень; в любом случае, при предъявлении парного листика или веточки надо указывать, с какой стороны от нашего листика или нашей веточки он находится -- слева или справа; именно эти указания однозначно определяют номер объекта в нашем упорядоченном наборе, и даже если номер неважен -- они необходимы, чтобы проверять доказательство, правильно "склеивая" хэши каждого уровня).

Если вы читаете по-русски, наверное, вам доводилось скачивать торренты. Задумывались ли вы о том, как какой-то случайный хрен из интернета кидает вам по сети кусочек музыкального альбома, и ваша торрентокачалка кладёт кусочек на правильное место в файле, нисколько не сомневаясь, что кусочек правильный и место тоже правильное?
Зная про криптографические хэши, мы, конечно, могли бы проверить альбом целиком, когда он скачается (а потом, если окажется, что какой-то из наших анонимных сетевых друзей подменил кусок, перекачать альбом заново...). Мы можем также просто нарезать альбом на блоки и начинать закачку тогда, когда у нас есть хэш каждого блока.

С появлением и распространением merkle hash tree torrents клиенту достаточно знать merkle root; каждый, кто отправляет ему блок данных, предъявляет заодно и доказательство, что блок "подходит" на своё место в нужном файле, что его не подменили и не переместили.

Подсистема dm-verity в Linux позволяет создавать дисковые устройства, где каждый читаемый блок проверяется на отсутсвие искажений и подмен. При этом значения хэшей со всех уровней дерева тоже лежат на диске и тоже могут быть подвержены злонамеренному искажению и ошибкам, но и эти искажения будут неизбежно обнаружены, если dm-verity сообщили _правильное значение merkle root _. То есть для того чтобы гарантировать аутентичность каждого читаемого блока, нам достаточно надёжно сохранить 256 (ну ладно, пусть 512) жалких бит и убедиться, что именно они переданы модулю dm-verity.

И наконец, в заголовке блока bitcoin тоже хранится merkle root содержащихся в блоке "бухгалтерских записей". Это позволяет работать легковесным bitcoin-кошелькам, которые не скачивают блоки целиком, а получают от дружественных серверов затрагивающие их транзакции (с доказательством, что транзакции на самом деле совершены и попали в блок). Конечно, модель безопасности SPV-кошельков существенно слабее "настоящих": во-первых, хотя proof of work в виде "красивого хэша с нулями" говорит за себя, это ещё не 100% доказательство, что блок реально соответствует правилам сети, а лишь доказательство, что некий мощный везучий майнер считает его таковым. Во-вторых, хотя дружественный сервер не может высосать из пальца транзакцию (с доказательством её наличия в блоке), но скрыть транзакцию ему никто не мешает (спасает то, что годных серверов обычно много, кошелёк может опросить несколько).

Сервера opentimestamps, которые помогают доказать существование документа на определённую дату (причём публиковать документ для этого не обязательно) пользуются этим свойством bitcoin-блоков, чтобы "пристегнуть" специальную bitcoin-транзакцию, которую они периодически создают, к пользовательским данным (также используется слегка модифицированный вариант merkle tree, чтобы соединить данные всех клиентов, ожидающих "аттестации", так чтобы на всех хватило одной транзакции). Наличие ots-файла на сайте с подписанным софтом, подтверждающего "возраст" подписи, в свою очередь, довольно сильно затрудняет атаки вида "сломали сайт, подменили софт и подменили подпись" (если вы вчера дописали фальшивую софтину, то подменённая подпись обязательно будет свежей; выкладывание ots вместе с подписью пока не очень популярно, но постепенно идёт в массы).

Фактически, знаменитое теперь понятие blockchain означает эдакое скособоченное merkle tree, к которому регулярно пристраивается новый корень (так что старое дерево становится левой веточкой, а некий новый блок -- правой). В современных модных молодёжных текстах о том, как блокчейн изменит нашу жизнь, я люблю мысленно заменить его на merkle tree, иногда даже получается что-то осмысленное, но забавно становится всегда и тошнит меньше (в задачах "защиты от подмен" часто бывает так, что реально-то людям нужен как раз merkle tree, а не blockchain -- впрочем, беднягам нужно же и инвестиций добыть, так что см. тж. рассказ Аверченко "Неизлечимые").

👍💯🔥5
To react or comment  View in Web Client
Comments (2)
Avatar

Сразу не понял, но сейчас дошло. Например, если у нас есть листики
A B C D E F G H
склеиваем и хэшируем попарно:
[AB] [CD] [EF] [GH]
[[AB][CD]] [[EF][GH]]
[[[AB][CD]][[EF][GH]]]

Чтобы доказать E, достаточно предъявить F [GH] [[AB][CD]] и корень

👍2
Avatar

Очень круто расписал, спасибо, интересно

To react or comment  View in Web Client