Ralph C. Merkle — криптограф, чьи работы помогли заложить основы современной криптографии. Загадки Меркла решают задачу согласования общего секрета через прослушиваемый канал; Merkle Tree позволяет подтвердить принадлежность элемента определённому списку, не загружая список целиком. Это разные задачи, и ни одна сама по себе не определяет действительность транзакций Bitcoin.
Вы хотите отправить зашифрованное сообщение. Получателю нужен секретный ключ, чтобы его прочитать. Но как передать ключ, если кто-то наблюдает за всем обменом? В статье 1978 года Ralph Merkle описал неожиданный способ: отправитель готовит множество зашифрованных загадок; получатель случайно выбирает и решает одну, затем открыто возвращает спрятанный внутри идентификатор. Теперь оба знают общий ключ. Подслушивающий тоже видит идентификатор, но не знает, в какой загадке тот находился. В описанной модели его затраты растут квадратично с размером задачи, а работа участников — линейно. Разрыв квадратичный, не экспоненциальный. Исторический прорыв не является сегодняшней рекомендацией по шифрованию сообщений. [1]
В статье 1978 года важно, что разрешено противнику. Он может слушать, но изменения и подделки по-прежнему предполагаются обнаружимыми. Представьте человека, который читает письма, и человека, который ещё и переписывает их, подписывая вашим именем. Второй случай требует дополнительной защиты: проверки, с кем вы действительно общаетесь. Разница в вычислительной работе этого вопроса не решает. Поэтому загадки не делают безопасным произвольный обмен через активного посредника. Их вклад — показать возможность договориться без заранее общего секретного ключа при указанных предпосылках. [1]
Merkle Tree решает другую задачу. Такое дерево аутентификации описано в диссертации Меркла 1979 года. Представьте архив договоров: вы хотите проверить конкретный договор, не загружая весь архив. Для каждого элемента вычисляется хеш — короткий цифровой отпечаток. Отпечатки объединяются попарно и снова хешируются, пока не останется общий корень. Хеширование не шифрует содержимое, а позволяет проверять соответствие. Для осмысленной проверки нужен заранее аутентифицированный корень — подтверждённый отпечаток нужного архива. Если мошенник может предоставить и свой документ, и произвольный корень, их совпадение ничего не доказывает об исходном архиве. [2]
Возьмём сбалансированное бинарное дерево с 8 элементами. Чтобы проверить выбранный лист, нужны 3 соседних хеша: на каждом уровне отпечаток соседней ветви. Из своего листа и этих отпечатков вы вычисляете корень и сравниваете его с аутентифицированным корнем. Сам лист и корень не входят в число вспомогательных хешей. Нужно также знать структуру дерева и порядок объединения: сосед располагается слева или справа? Экономия не основана на фокусе со скрытыми данными. Удалённые части архива представлены отпечатками, поэтому полные документы для этой конкретной проверки не нужны. [2]
Merkle Tree подтверждает связь между элементом и определённым набором данных. Ошибочное утверждение от этого не становится истинным. В нашем архиве может быть договор с неверным именем; доказательство правильно подтвердит его присутствие, не обнаружив ошибки в имени. Отпечаток также не подтверждает полномочий автора документа. Полезно разделять вопросы: соответствует ли элемент этому корню, откуда известен корень и по каким правилам принимается содержимое? Это различие помогает понять возможности той же техники в Bitcoin и задачи, которые должны решать другие части системы. [2]
Bitcoin использует Merkle Tree для связи транзакций с заголовком блока — его компактной записью. Корень входит в заголовок; изменение включённых транзакций влияет на общий отпечаток. Satoshi Nakamoto описывает эту конструкцию в разделе 7 whitepaper и ссылается на работу Меркла. Это свидетельствует о техническом влиянии, а не об авторстве Bitcoin. Дерево не выбирает действительную историю и не проверяет подписи транзакций вместо узлов. Bitcoin сочетает его с другими правилами, включая проверку транзакций и Proof of Work — доказательство вычислительной работы. Понять отдельный компонент полезнее, чем приписывать ему возможности всей системы. [3]
Раздел 8 whitepaper описывает SPV — упрощённую проверку платежей. Лёгкий клиент использует заголовки блоков и ветвь дерева, связывающую транзакцию с выбранным блоком. Это экономит данные, но опирается на предположения о цепочке с наибольшей накопленной работой и поведении майнеров. Само доказательство включения не проверяет все правила транзакций так, как Full Node — полностью проверяющий узел. Оно также не показывает, был ли выход потрачен позднее: для этого нужно знать последующие события. Новичку важно не путать фразу «этот платёж находится в этом блоке» с полной проверкой денег, доступных сейчас. [3]
В диссертации 1979 года дерево аутентификации используется также для конечного набора одноразовых цифровых подписей. Цифровая подпись позволяет проверить, что владелец определённого секретного ключа одобрил сообщение; это не картинка подписи на бумаге. Дерево может связать множество проверочных значений с одним известным корнем. Однако в этой конструкции запас подписей конечен и корень со временем приходится обновлять. Это не разрешает бесконечно использовать один и тот же одноразовый ключ. Более сложная часть работы Меркла показывает общую идею: проверять нужную часть небольшим доказательством, точно понимая предпосылки такой проверки. [2]
Для полной картины прочитайте эту статью вместе с David Chaum, Timothy May, Merkle Tree, Block Header. На эту статью также ссылаются David Chaum, Timothy May.