Доказательство Меркла

Что такое доказательство Меркла?

Доказательство Меркла — это криптографическое доказательство, которое подтверждает, что определенный фрагмент данных входит в более крупный набор данных, не раскрывая и не загружая весь набор.

В криптовалютах доказательство Меркла часто используют, чтобы подтвердить, что транзакция, аккаунт, баланс, значение хранилища, право на NFT, адрес кошелька или другой элемент включен в проверенный набор данных.

Для этого используются хеши дерева Меркла, также называемого хеш-деревом.

Дерево Меркла принимает множество фрагментов данных, хеширует их и помещает в листья, затем попарно объединяет хеши и продолжает хеширование вверх по дереву, пока не останется один итоговый хеш.

Этот итоговый хеш называется корнем Меркла.

Если корень Меркла заслуживает доверия, пользователь может проверить отдельный элемент с помощью небольшого доказательства, не проверяя весь набор данных.

В руководстве для разработчиков Bitcoin объясняется, что деревья Меркла позволяют клиентам проверить включение транзакции в блок, используя корень Меркла из заголовка блока и промежуточные хеши, полученные от другого узла.

Поэтому доказательства Меркла важны для эффективности блокчейна, легких клиентов, раздач токенов, белых списков NFT, мостов, доказательств состояния и проверки данных.

Как работает дерево Меркла

Дерево Меркла начинается с отдельных элементов данных в нижней части дерева.

Эти нижние элементы называются листьями.

В блокчейне каждый лист может представлять хеш транзакции, запись аккаунта, значение хранилища, адрес кошелька или запись о праве на получение актива.

Каждый лист хешируется с помощью криптографической хеш-функции.

Затем хеши объединяются в пары и хешируются повторно.

Процесс продолжается уровень за уровнем, пока дерево не сформирует один верхний хеш.

Этот верхний хеш — корень Меркла.

Если любой лист изменится, изменится и его хеш.

Это изменение передается вверх по дереву и меняет корень Меркла.

Поэтому корень Меркла может служить компактным цифровым отпечатком большого набора данных.

Как работает доказательство Меркла

Доказательство Меркла подтверждает, что конкретный лист входит в дерево Меркла с известным корнем.

Обычно доказательство содержит хеши соседних листьев, необходимые для восстановления пути от проверяемого листа до корня.

Проверяющая сторона начинает с хеша листа.

Затем она объединяет его с первым хешем соседнего элемента и хеширует пару.

Полученный результат объединяется со следующим соседним хешем и хешируется повторно.

Процесс продолжается, пока проверяющая сторона не вычислит итоговый корень.

Если вычисленный корень совпадает с доверенным корнем Меркла, доказательство действительно.

Если корни не совпадают, доказательство недействительно.

Так можно проверить принадлежность элемента, не раскрывая все листья дерева.

Простой пример доказательства Меркла

Представим белый список NFT с четырьмя адресами кошельков.

Каждый адрес хешируется и становится листом.

Лист A и лист B хешируются вместе, образуя родительский хеш.

Лист C и лист D хешируются вместе, образуя другой родительский хеш.

Затем два родительских хеша хешируются вместе, образуя корень Меркла.

Если кошелек A хочет подтвердить, что он входит в белый список, ему не нужно раскрывать весь список.

Ему нужны только собственный лист и соседние хеши, необходимые для восстановления корня Меркла.

Смарт-контракт может проверить доказательство и разрешить кошельку получить актив или выпустить NFT, если доказательство соответствует сохраненному корню.

Зачем нужны доказательства Меркла в криптовалютах

Доказательства Меркла важны, поскольку блокчейнам нужны эффективные способы проверки больших объемов данных.

Без доказательств Меркла пользователям и приложениям, возможно, пришлось бы загружать или принимать на веру значительно больше информации.

Доказательство Меркла делает проверку компактнее, быстрее и практичнее.

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

Легкие кошельки могут использовать доказательства для проверки данных без запуска полной ноды.

Смарт-контракты могут проверять адреса в белых списках с помощью доказательств, не храня в блокчейне тысячи адресов.

Мосты и кроссчейн-системы могут использовать доказательства для проверки событий или состояния другой сети.

Системы доступности данных и роллапы также могут использовать обязательства на основе деревьев Меркла, чтобы помогать подтверждать принадлежность данных более крупной структуре, зафиксированной таким обязательством.

Доказательства Меркла в Bitcoin

Bitcoin использует деревья Меркла для обобщения транзакций в блоке.

Корень Меркла включается в заголовок блока.

Легкий клиент может проверить включение транзакции в блок, сопоставив доказательство Меркла с корнем Меркла этого блока.

Это обеспечивает упрощенную проверку платежей, которую часто называют SPV.

SPV позволяет кошельку или клиенту проверить включение транзакции, не загружая каждый полный блок.

Это не означает, что клиент проверяет все то же, что и полная нода.

Клиент может эффективнее проверять включение транзакции, опираясь на заголовки блоков и данные доказательства.

Доказательства Меркла в Ethereum

Ethereum использует аутентифицированные структуры данных на основе деревьев Меркла для проверки аккаунтов и хранилища.

В документации Ethereum о деревьях Меркла — Патриции объясняется, что Ethereum использует связанные криптографическими хешами структуры деревьев, обеспечивающие целостность хранимых данных.

Доказательства Ethereum могут показать, что аккаунт или значение хранилища входит в конкретный корень состояния.

Стандарт EIP-1186 eth_getProof описывает RPC-метод создания доказательств Меркла для аккаунтов и значений хранилища Ethereum.

Такое доказательство полезно, если приложению нужно проверить состояние аккаунта, не полагаясь безоговорочно на поставщика данных.

Системы доказательств Ethereum сложнее простого бинарного дерева Меркла, поскольку состояние Ethereum хранится в структурах на основе trie.

Однако основной принцип тот же: небольшое доказательство позволяет проверить отдельный фрагмент данных относительно доверенного корня.

Доказательства Меркла в белых списках NFT

NFT-проекты часто используют доказательства Меркла для белых списков и предварительных продаж.

Вместо того чтобы хранить в смарт-контракте адрес каждого одобренного кошелька, проект сохраняет один корень Меркла.

Каждый одобренный пользователь получает доказательство того, что его адрес входит в дерево белого списка.

Когда пользователь получает NFT или выпускает его, смарт-контракт проверяет доказательство относительно сохраненного корня.

Это позволяет сократить расходы на хранение данных в блокчейне: сохранить один корень гораздо дешевле, чем тысячи адресов.

Это также может повысить конфиденциальность, поскольку весь белый список не нужно размещать непосредственно в контракте.

Тем не менее пользователям следует убедиться, что корень создан официальным проектом, а страница получения NFT не является фишинговой.

Доказательства Меркла в раздачах токенов

В раздачах токенов часто используют доказательства Меркла, чтобы проверять, кто может получить токены.

Проект создает набор данных с подходящими адресами кошельков и суммами для получения.

Каждая запись о получении становится листом дерева Меркла.

Смарт-контракт хранит корень Меркла.

Чтобы получить токены, пользователь отправляет свой адрес, сумму и доказательство.

Контракт проверяет, соответствует ли доказательство сохраненному корню.

Если доказательство действительно, а кошелек еще не получал токены, контракт может перечислить их.

Такая схема позволяет проводить крупные раздачи, не храня каждую запись о получении непосредственно в блокчейне.

Доказательства Меркла в легких клиентах

Легкий клиент — это кошелек или нода, которая проверяет данные блокчейна, не загружая и не обрабатывая все данные полной цепочки.

Доказательства Меркла помогают легким клиентам проверять отдельные данные относительно доверенных заголовков блоков или корней состояния.

В документации Ethereum о легких клиентах объясняется, что они позволяют пользователям проверять входящие данные, используя лишь малую долю ресурсов, необходимых полным нодам.

Это важно для мобильных устройств, браузеров, встроенных систем и пользователей с ограниченной пропускной способностью.

Легкие клиенты — не то же самое, что полные ноды.

Они проверяют меньше данных, но могут повысить уровень доверия по сравнению с полной зависимостью от централизованного поставщика данных.

Доказательства Меркла в смарт-контрактах

Смарт-контракты могут проверять доказательства Меркла непосредственно в блокчейне.

Это полезно, когда контракту нужно проверить принадлежность элемента большому набору данных.

В документации OpenZeppelin MerkleProof представлены инструменты для проверки доказательств Меркла в смарт-контрактах.

Распространенный шаблон контракта предусматривает хранение корня Меркла и проверку отправленных пользователями доказательств при получении токенов, выпуске NFT, начислении вознаграждений или проверке доступа.

Так отпадает необходимость хранить в контракте адрес или запись каждого подходящего пользователя.

Основной компромисс заключается в том, что доказательство необходимо правильно сформировать вне блокчейна.

Если дерево построено неверно, выбран неправильный метод хеширования, правило сортировки или формат листа, действительные пользователи могут не пройти проверку, а недействительные — пройти ее в плохо спроектированных системах.

Доказательство Меркла и корень Меркла

Корень Меркла — это итоговый хеш, представляющий все дерево.

Доказательство Меркла — это набор хешей и связанных данных, используемых, чтобы подтвердить принадлежность одного листа дереву.

Корень — своего рода цифровой отпечаток всего набора данных.

Доказательство — подтверждение связи отдельного элемента с этим отпечатком.

Сам по себе корень не раскрывает все данные дерева.

Само по себе доказательство бесполезно, если проверяющая сторона не располагает доверенным корнем для сравнения.

Для проверки нужны обе составляющие.

Доказательство Меркла и доказательство с нулевым разглашением

Доказательство Меркла и доказательство с нулевым разглашением — разные криптографические инструменты.

Доказательство Меркла подтверждает, что конкретный элемент входит в зафиксированный набор данных.

Доказательство с нулевым разглашением позволяет подтвердить истинность утверждения, не раскрывая лежащую в его основе конфиденциальную информацию.

Доказательства Меркла обычно проще, дешевле и легче проверяются, чем многие доказательства с нулевым разглашением.

Доказательства с нулевым разглашением могут применяться в более сложных сценариях, связанных с конфиденциальностью и вычислениями.

В некоторых системах доказательства Меркла и доказательства с нулевым разглашением используют вместе.

Например, схема с нулевым разглашением может скрытно проверить доказательство включения в дерево Меркла.

Доказательство Меркла и доказательство хранения

Доказательство хранения часто представляет собой доказательство на основе дерева Меркла, которое подтверждает значение, сохраненное в состоянии блокчейна.

Например, доказательство хранения Ethereum может показать, что слот хранилища смарт-контракта имел определенное значение в состоянии с конкретным корнем на определенном блоке.

Доказательство Меркла — более широкое понятие.

Доказательство хранения — частный случай подтверждения данных состояния или хранилища.

Это различие важно, поскольку в разных сетях используются разные структуры данных, форматы доказательств и правила хеширования.

Не следует считать, что доказательство одной блокчейн-сети работает так же, как доказательство другой.

Преимущества доказательств Меркла

Первое преимущество — эффективность.

Доказательство позволяет проверить один элемент без загрузки всего набора данных.

Второе преимущество — снижение расходов на хранение данных в блокчейне.

Вместо тысяч или миллионов записей смарт-контракты могут хранить один корень.

Третье преимущество — лучшая масштабируемость.

Большие наборы данных можно зафиксировать с помощью небольшого корня, а затем проверять компактными доказательствами.

Четвертое преимущество — целостность данных.

Если изменить лист или хеш доказательства, вычисленный корень не совпадет с исходным.

Пятое преимущество — частичная конфиденциальность.

Пользователи могут подтвердить включение элемента, не раскрывая остальные элементы набора данных.

Риски и ограничения

Первый риск — неправильное построение дерева.

Если проект построит дерево неверно, доказательства могут не пройти проверку или привести к неожиданным результатам.

Второй риск — некорректное кодирование листьев.

Если данные листьев закодированы недостаточно тщательно, разные входные значения могут привести к неоднозначной или небезопасной работе системы доказательств.

Третий риск — ошибочные предположения о сортировке.

В одних системах доказательств Меркла пары нужно сортировать, в других важен порядок слева направо.

Четвертый риск — недоверенные корни.

Действительное доказательство подтверждает только включение элемента в набор данных, представленный этим корнем. Поэтому источник корня должен быть доверенным или проверенным.

Пятый риск — повторное использование доказательства или повторное получение токенов.

Если получить токены можно только один раз, контракты раздач и получения должны отслеживать, использовалось ли доказательство ранее.

Шестой риск — фишинг.

Мошенники могут создавать поддельные страницы получения токенов, предлагающие отправить доказательства или подписать опасные транзакции.

Как проверить доказательство Меркла

Начните с листа, который нужно проверить.

Хешируйте лист тем же методом, который использовался при построении исходного дерева.

Объедините хеш листа с первым соседним хешем из доказательства.

Хешируйте полученное значение.

Повторите процесс с каждым оставшимся соседним хешем.

Сравните вычисленный итоговый хеш с доверенным корнем Меркла.

Если корни совпадают, доказательство действительно.

Если они не совпадают, доказательство недействительно.

В смарт-контрактах этот процесс обычно выполняет код проверки.

Пользователю особенно важно удостовериться, что корень, контракт, страница получения токенов и источник являются официальными.

Распространенные заблуждения о доказательствах Меркла

Одно из распространенных заблуждений состоит в том, что доказательство Меркла подтверждает истинность данных во всех возможных смыслах.

Оно подтверждает только то, что данные включены в набор, представленный конкретным корнем.

Другое заблуждение — будто доказательство Меркла раскрывает весь набор данных.

Обычно оно раскрывает только проверяемый лист и соседние хеши, необходимые для проверки.

Третье заблуждение — будто все доказательства Меркла имеют одинаковый формат.

В разных системах могут использоваться разные хеш-функции, правила сортировки, формы деревьев и форматы доказательств.

Четвертое заблуждение — будто доказательства Меркла полностью устраняют необходимость доверия.

Они снижают необходимость доверять доставке данных, однако пользователю по-прежнему нужны доверенный корень и корректные правила проверки.

Пятое заблуждение — будто доказательства Меркла используют только для транзакций.

С их помощью также проверяют белые списки, раздачи токенов, состояние аккаунтов, значения хранилища, данные роллапов, кроссчейн-сообщения и цифровые идентификационные данные.

FAQ

Что такое доказательство Меркла?

Доказательство Меркла — это криптографическое доказательство, показывающее, что отдельный фрагмент данных входит в более крупный набор, представленный корнем Меркла.

Что такое корень Меркла?

Корень Меркла — это итоговый хеш в верхней части дерева Меркла, который служит компактным цифровым отпечатком всего набора данных.

Как доказательство Меркла проверяет данные?

Проверяющая сторона хеширует проверяемый лист с соседними хешами из доказательства и проверяет, совпадает ли итоговый результат с доверенным корнем Меркла.

Зачем блокчейны используют доказательства Меркла?

Блокчейны используют доказательства Меркла для эффективной проверки данных без необходимости загружать весь набор каждому пользователю или приложению.

Как доказательства Меркла используют в раздачах токенов?

Контракт раздачи может хранить один корень Меркла, а пользователи — отправлять доказательства того, что их кошелек и сумма для получения включены в список подходящих участников.

Как доказательства Меркла используют в белых списках NFT?

NFT-проекты могут с помощью доказательств Меркла проверить, что адрес кошелька входит в белый список, не храня каждый разрешенный адрес непосредственно в блокчейне.

Обеспечивают ли доказательства Меркла конфиденциальность?

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

Являются ли доказательства Меркла доказательствами с нулевым разглашением?

Нет. Доказательства Меркла подтверждают включение элемента в набор данных, а доказательства с нулевым разглашением могут подтверждать более общие утверждения без раскрытия конфиденциальных входных данных.

Может ли доказательство Меркла быть поддельным?

Поддельное доказательство не пройдет проверку, если проверяющая сторона использует правильные правила хеширования и сверяет его с верным доверенным корнем.

Что проверить перед использованием страницы получения токенов с доказательством Меркла?

Пользователям следует проверить официальный контракт, официальный сайт, доверенный корень Меркла, запрос кошелька, правила получения токенов и безопасность страницы.

Заключение

Доказательство Меркла — один из важнейших инструментов проверки в криптовалютах.

Оно позволяет пользователям, кошелькам, смарт-контрактам и приложениям доказать, что отдельный элемент входит в более крупный набор данных, не загружая и не сохраняя весь набор.

Это делает блокчейн-системы эффективнее, масштабируемее и практичнее.

Доказательства Меркла используют для проверки включения транзакций, работы легких клиентов, раздач токенов, белых списков NFT, проверки состояния аккаунтов, доказательств хранения, мостов и систем роллапов.

Основной принцип прост: доверенный корень Меркла представляет набор данных, а доказательство восстанавливает путь от одного листа к этому корню.

Если вычисленный корень совпадает, данные включены в набор.

Если корни не совпадают, проверка доказательства не проходит.

Доказательства Меркла уменьшают необходимость доверять поставщикам данных, но не устраняют все риски.

Пользователям и разработчикам по-прежнему нужны корректные правила хеширования, безопасные смарт-контракты, доверенные корни, правильное формирование доказательств и защита от фишинга.

При грамотной реализации доказательства Меркла делают криптовалютные системы легче, дешевле и удобнее для проверки.