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

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

◉ Вся структура данных которую мы рассматриваем называется древом.

◉ Каждый элемент в древе называется листком, а несколько элементов - листьями, по аналогии с реальными деревьями.

◉ Путь от верхнего элемента до нужного нам листка называется веткой.

◉ Все Древо Меркла - это 32 байтная строка, называемая рутом.

◉ Меркель пруф - это путь из 32 байтного массива хэшей от рута до проверяемого кошелька (его хэша).

Сами листья не могут являтся числом или массивом. Каждый лист - это хэш, чаще всего keccak256 помещаемых нами данных.

Шифр - это обратимая функция, а хэш - необратимая.

То есть, например, если мы знаем, что строка зашифрована шифром Цезаря под ключом 2 (то есть изменение вперед на 2 буквы) то мы можем ее расшифровать.

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

Это все понятно, но зачем его использовать, если можно все данные хранить в массиве/списке?

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

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

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

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

Второе преимущество - это безопасность.

◉ Во первых, поскольку Древо состоит из хэшей, не получится узнать чужие кошельки в WL (т.к. по хэшу нельзя получить исходную строку).

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

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

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

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

Итак, открываем вашу IDE (если кому интересно, я использую коммерческую версию WebStorm) и устанавливаем две библиотеки, которые нам понадобятся. Первая нужна, чтобы превратить строку в keccak256, а вторая - чтобы создать древо.

$ npm i keccak256 merkletreejs

Бум! Все установилось и теперь начинаем кодить.

Для начала импортируем две библиотеки которые мы установили выше:

const { MerkleTree } = require("merkletreejs");
const keccak256 = require('keccak256');

Теперь создадим массив из кошельков которые у нас в WL:

const addresses = ["0x5B38Da6a701c568545dCfcB03FcB875f56beddC4","0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2"];

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

const buf2hex = x => "0x" + x.toString("hex");

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

const leaves = addresses.map(address => keccak256(address));

Затем наконец-то создаем наше Древо:

const tree = new MerkleTree(leaves, keccak256, { sortPairs: true });

И получаем нужный нам рут хэш, который мы далее сохраним в смарт контракте:

const merkleRootString = buf2hex(tree.getRoot());

Теперь реализуем получение пруфа для кошелька:

const leaf = keccak256("0x5B38Da6a701c568545dCfcB03FcB875f56beddC4");
const proof = tree.getProof(leaf);
const proofString = "[" + proof.map(x => `"${buf2hex(x.data)}"`) + "]"

proofString это есть нужный нам пруф, который мы можем ввести в контракт и все пройдет.

Напишем простую реализацию смарт-контракта на Solidity, проверяющего есть ли кошель в WL.

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

pragma solidity ^0.8.4;
 
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

Создаем сам контракт, изначально задаем меркель рут, и добавляем функцию для проверки, которая вернет true если кошель в WL, и false если нет.

contract SimpleMerkleTree {
  bytes32 merkleRoot = 0xeeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097; 
  function checkIsAddressInWl(bytes32[] memory _merkleProof) public view returns(bool) {
    return MerkleProof.verify(_merkleProof, merkleRoot, keccak256(abi.encodePacked(msg.sender)));
  }  
 }