Введение

В идеальном децентрализованном приложении мы бы хотели хранить все в блокчейне на смарт-контрактах — в хранилище Ethereum: данные не могут быть изменены несанкционированным способом. Но запись какой-либо информации, размером 32 байта обойдется нам в 20000 газа. На момент написания статьи это примерно $0.26, c одной стороны не много, но что если мы хотим хранить в хранилище какой-то значительный массив информации.

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

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

Теория

Результат формирования дерева Меркла это корневой хэш, находящийся в самом верху пирамиды хэшей. На изображении ниже хэш H(AH) - корневой. Давайте разберемся как он получился.

Например, изначально мы имеем 8 хэшей(A, B, C, D, E, F, G, H) каких-то данных, которые никак не относятся друг к другу. Затем происходит попарное хэширование(H(AB), H(CD), H(EF), H(GH)), а именно: результат конкатенации A и B помещается в хэш-функцию keccak256, таким образом мы получим хэш H(AB):

Подобным образом вычисляются также H(EF) и H(GH), если имеется нечетное количество хэшей, то оставшийся перейдет на следующий уровень попарного хэширования и там найдет себе пару, если и там не будет пары, то он перейдет снова на следующий уровень, и так до тех пор пока не будет найдена пара.

Как вы уже могли догадаться H(AD) будет результатом попарного хэширования H(AB) и H(CD), которое осуществляется по точно такой же формуле:

Таким образом:

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

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

Примечание: здесь и далее для попарного хэширования применятся хэш функция keccak256, вы поймете в дальнейшем почему, но это не есть обязательное к исполнению правило, например, входные аргументы для попарного хэширования могут быть переведены в двоичный код, а результатом попарного хэширования будет строгая дизъюнкция этих данных в двоичном виде или другими словами применение оператора исключающего ИЛИ(XOR) для этих данных.

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

Представим ситуацию, где мы хотим убедиться в том что хэш C(выделен синим) присутствует в дереве. В таком случае доказательством будет следующий массив данных: хэш D, H(AB), H(EH) (выделены зеленым). Благодаря им мы сможем восстановить корневой хэш.

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

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

Ссылка на репозиторий будет дана в конце материала.

const addresses = [
    '0x70997970C51812dc3A010C7d01b50e0d17dc79C8',
    '0x3C44CdDdB6a900fa2b585dd299e03d12FA4293BC',
    '0x90F79bf6EB2c4f870365E785982E1f101E93b906',
    '0x15d34AAf54267DB7D7c367839AAf71A00a2C6A65',
    '0x9965507D1a55bcC2695C58ba16FB37d819B0A4dc',
    '0x976EA74026E726554dB657fA54763abd0C3a0aa9',
    '0x14dC79964da2C08b23698B3D3cc7Ca32193d9955',
    '0x23618e81E3f5cdF7f54C3d65f7FBc0aBf5B21E8f',
    '0xa0Ee7A142d267C1f36714E4a8F75612F20a79720',
    '0xBcd4042DE499D14e55001CcbB24a551F3b954096',
    '0x71bE63f3384f5fb98995898A86B02Fb2426c5788',
    '0xFABB0ac9d68B0B445fB7357272Ff202C5651694a',
    '0x1CBd3b2770909D4e10f157cABC84C7264073C9Ec',
    '0xdF3e18d64BC6A983f673Ab319CCaE4f1a57C7097'
]; // массив с адресами для которых мы вычислим корневой хэш
    
// dataArray - массив с хэшами, то есть корневой хэш будет получен из хэшей адресов
// а не из адресов напрямую
const dataArray = addresses.map(address => ethers.utils.keccak256(address));

// функция для получения хэша от пары двух других хэшей
function getPair(hashOne: string, hashTwo: string): string {
// результирующий хэш зависит от порядка контактенации
// в нашем случае первым аргументом всегда будет идти меньший хэш
    if (BigInt(hashOne) < BigInt(hashTwo)) {
// парное хеширование происходит с помощью вспомогательной библиотеки ethers
        return ethers.utils.solidityKeccak256([ 'bytes32', 'bytes32' ], [ hashOne, hashTwo ]);
    } else {
        return ethers.utils.solidityKeccak256([ 'bytes32', 'bytes32' ], [ hashTwo, hashOne ]);
    }
}

// функция получения корневого хэша, принимает массив хэшей, возвращает корневой
function getRoot(data: string[]): string {
// сначала смотрим четное ли количество элементов в массиве
    const parity: boolean = !(data.length % 2); 

// затем указываем нужную нам длину для цикла for в зависимости от четности
// если количетво четное, значит возвращаем исходную длину
// иначе длина будет уменьшена на 1, так как в случае нечетности
// последний хэш не найдет себе пары
    let length = parity ? data.length : data.length - 1;
    let result = [];
    for (var i = 0; i < length - 1; i += 2) {
// заполняем массив парными хешами
        result.push(getPair(data[i], data[i + 1]));
    }   
    if (!parity) {
// если количество нечетное, добавляем в конец результирующего массива 
// последний элемент, которому не нашлось пары для парного хеширования
        result.push(data[data.length - 1]);
    }
// если в результирующем массиве один элемент, то возвращаем его, 
// потому что это и есть искомый корневой хэш
// иначе снова вызываем getRoot
// таким образом функция getRoot будет рекурсивной 
    return result.length == 1 ? result[0] : getRoot(result); 
}

const root = getRoot(dataArray);
console.log('root', root);

Запустим скрипт и посмотрим на результат.

npx hardhat run scripts/example-merkle.ts

Результат из логов: ‘0x2e3bc03e1c67b59152c362a773c515a01d9dfdde6aaaa6796ad3bb1ec3b65300’.

Практика

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

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.9;

import "@openzeppelin/contracts/token/ERC20/utils/SafeERC20.sol";
import "@openzeppelin/contracts/token/ERC20/extensions/IERC20Metadata.sol"; 

contract AirdropV1 {
    using SafeERC20 for IERC20Metadata;

    address owner; // только этот адрес имеет доступ к функции addToWhitelist
    address dropToken; // адрес контракта токена стандарта ERC20
    uint256 dropAmount; // фиксированная сумма, которую получит каждый, кто есть в вайтлисте
    mapping(address => bool) public whitelist; // mapping возвращает true если адрес есть в вайтлисте
    
    constructor(address _dropToken, uint256 _dropAmount) {
// при деплое контракта в конструктор передается адрес раздаваемого токена
// и сумма единичного клейма 
        owner = msg.sender;
        dropToken = _dropToken;
        dropAmount = _dropAmount;
    } 


// функция для добавления в вайтлист новых участников аирдропа
// в качестве аргумента она принимает массив с адресами участников
    function addToWhitelist(address[] calldata _users) public {
        require(owner == msg.sender, "Only owner!");
        for(uint i = 0; i < _users.length; i++) {
            whitelist[_users[i]] = true;
        }
    }

// эту функцию вызывает участник, который находится в вайтлисте
// после успешного завершения транзакции на его адресе окажется сумма dropAmount токена dropToken
    function claim() public {
        require(whitelist[msg.sender], "You are not whitelisted.");
        IERC20Metadata(dropToken).safeTransfer(
            msg.sender,
            dropAmount
        );
        whitelist[msg.sender] = false;
    }
}

Напишем для контракта тестирование, в котором будет продемонстрирован полный цикл работы всей функциональности контракта, а также воспользуемся встроенным инструментом hardhat gas-reporter, чтобы выяснить какое количество газа было потрачено на вызов функции “addToWhitelist”.

import { expect } from "chai";
import { ethers } from "hardhat";
import { SignerWithAddress } from "@nomiclabs/hardhat-ethers/signers";
import { BigNumber } from "ethers";
import * as mocha from "mocha-steps";
import { parseEther } from '@ethersproject/units';
import { AirdropV1, Token20 } from '../typechain-types';

describe("AirdropV1.sol testing", async () => {
    let airdrop: AirdropV1;
    let dropToken: Token20;
    let admin: SignerWithAddress, user1: SignerWithAddress, user2: SignerWithAddress, user3: SignerWithAddress, user4: SignerWithAddress, 
        user5: SignerWithAddress, user6: SignerWithAddress, user7: SignerWithAddress, user8: SignerWithAddress, user9: SignerWithAddress,
        user10: SignerWithAddress, user11: SignerWithAddress, user12: SignerWithAddress, user13: SignerWithAddress, user14: SignerWithAddress,
        unwhitelisted: SignerWithAddress;
    
    let dropAmount: BigNumber;

    beforeEach(async () => {
        [admin, user1, user2, user3, user4, 
         user5, user6, user7, user8, user9, 
         user10, user11, user12, user13, 
         user14, unwhitelisted] = await ethers.getSigners();
    });

    mocha.step("Деплой токена ERC20, который мы будем раздавать", async function() {
        const dropTokenFactory = await ethers.getContractFactory("Token20");
        dropToken = await dropTokenFactory.connect(admin).deploy(
            'Drop Token',
            'DTN',
            parseEther('100000')
        )
    });

    mocha.step("Деплой контракта аирдропа", async function() {
        const airdropFactory = await ethers.getContractFactory("AirdropV1");
        dropAmount = parseEther('1000');
        airdrop = await airdropFactory.deploy(dropToken.address, dropAmount);
    });

    mocha.step("Трансфер раздаваемого токена на адрес контракта аирдропа", async function() {
        await dropToken.connect(admin).transfer(airdrop.address, parseEther('100000'));
    });

    mocha.step("Добавление пользователей в вайтлист", async function() {
        const whitelist = [
            user1.address, user2.address, user3.address, 
            user4.address, user5.address, user6.address, 
            user7.address, user8.address, user9.address,
            user10.address, user11.address, user12.address,
            user13.address, user14.address,
        ];
        await airdrop.connect(admin).addToWhitelist(whitelist);
    });

    mocha.step("Вызов функции claim, пользователями из вайтлиста", async function() {
        await airdrop.connect(user1).claim();
        await airdrop.connect(user2).claim();
        await airdrop.connect(user3).claim();
// в исходном коде репозитория клейм производится для 14 адресов из вайтлиста
// здесь сокращенно для экономии пространства 
        await airdrop.connect(user14).claim();
    });

    mocha.step("Проверка баланса пользователей после claim", async function() {
        expect(await dropToken.balanceOf(user1.address)).to.be.equal(dropAmount);              
        expect(await dropToken.balanceOf(user2.address)).to.be.equal(dropAmount);              
        expect(await dropToken.balanceOf(user3.address)).to.be.equal(dropAmount);   
// в исходном коде репозитория проверка баланса производится для 14 адресов из вайтлиста
// здесь сокращенно для экономии пространства 
        expect(await dropToken.balanceOf(user14.address)).to.be.equal(dropAmount);           
    });

    mocha.step("Проверка защиты от несанкционированного клейма", async function() {
        await expect(airdrop.connect(unwhitelisted).claim()).to.be.revertedWith('You are not whitelisted.');
    });
});

Зафиксируем количество потраченного газа на вызов функции “addToWhitelist”.

Средняя цена газа на момент тестирования 16 gwei, на вызов “addToWhitelist” было потрачено 348171 газа или 8.83 usd в долларовом эквиваленте. Теперь представьте какое бы здесь было значение, если бы мы устраивали аирдроп для 100, 1000 адресов и т. д.

Теперь напишем новую версию аирдропа, где проверка на наличие в вайтлисте будет происходить с помощью дерева Меркла.

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.9;

import "@openzeppelin/contracts/token/ERC20/utils/SafeERC20.sol";
import "@openzeppelin/contracts/token/ERC20/extensions/IERC20Metadata.sol"; 
// импортируем вспомогательную библиотеку для проверки наличия того или иного адреса в дереве
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

contract AirdropV2 {
    using SafeERC20 for IERC20Metadata;

    address owner; // только этот адрес имеет доступ к функции addToWhitelist
    address dropToken; // адрес контракта токена стандарта ERC20
    uint256 dropAmount; // фиксированная сумма, которую получит каждый, кто есть в вайтлисте
    bytes32 public root; // корневой хэш дерева, по которому будет происходить сверка на наличие адреса в вайтлисте
    mapping(address => bool) public usersClaimed; // в этот мапинг записываются адреса которые уже произвели клейм, чтобы предотвратить повторный клейм
    
    constructor(address _dropToken, uint256 _dropAmount) {
// конструктор такой же как и у контракта AirdropV1
        owner = msg.sender;
        dropToken = _dropToken;
        dropAmount = _dropAmount;
    } 

    function setRoot(bytes32 _root) public {
// благодаря этой функции можно установить корневой хэш
        require(owner == msg.sender, "Only owner!");
        root = _root;
    }

// в отличии от первой версии здесь функция клейм принимает массив с промежуточными хешами дерева,
// которые позволят с помощью библиотеки MerkleProof убедиться в том, что msg.sender присутствует в дереве
    function claim(bytes32[] calldata _proof) public {
// убеждаемся в том, что юзер ещё не склеймил долю на которую он претендует
        require(!usersClaimed[msg.sender], "Already claimed");
// из библиотеки MerkleProof вызываем функцию verify, чтобы проверить есть ли msg.sender в вайтлисте
// подробнее остановимся на аргументах:
// _proof - массив хэшей из которых будет востановлен корневой
// root - корневой хэш, если востановленный из _proof корневой хэш равен root, то функция verify вернет true
// keccak256(abi.encodePacked(msg.sender)) - хэш, наличие которого мы хотим проверить в дереве
// последний аргумент функции verify мы пропускаем через ф-цию keccak256, так как дерево было сформировано на основе хешей а не адресов
        require(MerkleProof.verify(_proof, root, keccak256(abi.encodePacked(msg.sender))), "You are not whitelisted.");
// после прохождения проверки переводим юзеру монеты на которые он претендует
        IERC20Metadata(dropToken).safeTransfer(
            msg.sender,
            dropAmount
        );
// делаем отметку о том, что юзер склеймил монеты, чтобы предотвратить повторный клейм
        usersClaimed[msg.sender] = true;
    }
}

На этом месте считаю нужным остановиться на библиотеки MerkleProof и на функции verify в частности. Полный код библиотеки можно посмотреть на github OpenZeppelin.

Мы же только обратим внимание на функцию verify и другие внутренние функции, к которым обращается verify.

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

Ситуция: мы хотим проверить, зашиврован ли хэш C в корневом корневом хэше H(AH), тогда функция verify будет принмать следующие аргументы:

• proof - массив [ D, H(AB), H(EH) ]

• root - H(AH), то есть сам коревой хэш, в котором мы проверяем наличие хэша C

• leaf - хэш C, наличие которого мы проверяем.

Функция verify внутри себя обращается к processProof, если она вернет хэш, который равен целевому хэшу значит верификция прошла успешно, и хэш leaf действительно захеширован в root.

function verify(
    bytes32[] memory proof,
    bytes32 root,
    bytes32 leaf
) internal pure returns (bool) {
    return processProof(proof, leaf) == root;
}

Внутри функции processProof восcтанавливается root, разберем работу функции итерация за итерацией цикла for:

• 1-я итерация: _hashPair(C, D) -> H(CD);

• 2-я итерация: _hashPair(H(CD), H(AB)) -> H(AD);

• 3-я итерация: _hashPair(H(AD), H(EH)) -> H(AH);

Таким образом воcстанавливается корневой хэш дерева и возвращается в функцию verify для сверки.

function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
    bytes32 computedHash = leaf;
    for (uint256 i = 0; i < proof.length; i++) {
        computedHash = _hashPair(computedHash, proof[i]);
    }
    return computedHash;
}

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

function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
    return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
}

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

function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
    /// @solidity memory-safe-assembly
    assembly {
		// с помощью mstore обращаемся к слотам быстрой памяти(memory)
        mstore(0x00, a) // хэш а заполняет ячейки с 0x00 по 0x19 включительно
        mstore(0x20, b) // хэш b заполняет ячейки с 0x20 по 0x39 включительно
        value := keccak256(0x00, 0x40) // содержимое ячеек с 0x00 по 0x39 включительно
		// передается в функцию keccak256, это и есть контактенация
    }
}

Вернемся к практике и напишем тестирование для контракта нового аирдропа AirdropV2:

import { expect } from "chai";
import { ethers } from "hardhat";
import { SignerWithAddress } from "@nomiclabs/hardhat-ethers/signers";
import { BigNumber } from "ethers";
import * as mocha from "mocha-steps";
import { parseEther } from '@ethersproject/units';
import { AirdropV2, Token20 } from '../typechain-types';
import  keccak256  from "keccak256";
// импортируем библиотеку MerkleTree для формирования дерева
import { MerkleTree } from "merkletreejs"; 

describe("AirdropV2.sol testing", async () => {
    let airdrop: AirdropV2;
    let dropToken: Token20;
    let admin: SignerWithAddress, user1: SignerWithAddress, user2: SignerWithAddress, user3: SignerWithAddress, user4: SignerWithAddress, 
        user5: SignerWithAddress, user6: SignerWithAddress, user7: SignerWithAddress, user8: SignerWithAddress, user9: SignerWithAddress,
        user10: SignerWithAddress, user11: SignerWithAddress, user12: SignerWithAddress, user13: SignerWithAddress, user14: SignerWithAddress,
        unwhitelisted: SignerWithAddress;
    
    let dropAmount: BigNumber;
    let Tree: MerkleTree;
    let RootTree: string;

    beforeEach(async () => {
        [admin, user1, user2, user3, user4, 
         user5, user6, user7, user8, user9, 
         user10, user11, user12, user13, 
         user14, unwhitelisted] = await ethers.getSigners();
    });

    mocha.step("Деплой токена ERC20, который мы будем раздавать", async function() {
        const dropTokenFactory = await ethers.getContractFactory("Token20");
        dropToken = await dropTokenFactory.connect(admin).deploy(
            'Drop Token',
            'DTN',
            parseEther('100000')
        )
    });

    mocha.step("Деплой контракта аирдропа", async function() {
        const airdropFactory = await ethers.getContractFactory("AirdropV2");
        dropAmount = parseEther('1000');
        airdrop = await airdropFactory.deploy(dropToken.address, dropAmount);
    });

    mocha.step("Трансфер раздаваемого токена на адрес контракта аирдропа", async function() {
        await dropToken.connect(admin).transfer(airdrop.address, parseEther('100000'));
    });

    mocha.step("Формирование дерева меркла и получение корневого хэша", async function () {
        const whitelist = [
            user1.address, user2.address, 
            user3.address, user4.address, 
            user5.address, user6.address, 
            user7.address, user8.address,
            user9.address, user10.address,
            user11.address, user12.address,
            user13.address, user14.address,
        ];        
        const leafs = whitelist.map(address => keccak256(address)); 
  // sortPairs: true - говорит о том, что меньший хэш будет идти первым
  // при парном хэшировании (смотреть функцию getPair в js-полифилие)
        Tree = new MerkleTree(leafs, keccak256, {sortPairs: true});
        RootTree = Tree.getHexRoot();
    });

    mocha.step("Установка корневого хэша в контракт аирдропа", async function () {      
        console.log('RootTree', RootTree);
        await airdrop.connect(admin).setRoot(RootTree);  
    });

    mocha.step("Вызов функции claim, пользователями из вайтлиста", async function() {
        await airdrop.connect(user1).claim(Tree.getHexProof(keccak256(user1.address)));
        await airdrop.connect(user2).claim(Tree.getHexProof(keccak256(user2.address)));
// в исходном коде репозитория клейм производится для 14 адресов из вайтлиста
// здесь сокращенно для экономии пространства 
        await airdrop.connect(user14).claim(Tree.getHexProof(keccak256(user14.address)));
    });

    mocha.step("Проверка баланса пользователей после claim", async function() {
        expect(await dropToken.balanceOf(user1.address)).to.be.equal(dropAmount);              
        expect(await dropToken.balanceOf(user2.address)).to.be.equal(dropAmount);              
// в исходном коде репозитория проверка баланса производится для 14 адресов из вайтлиста
// здесь сокращенно для экономии пространства 
        expect(await dropToken.balanceOf(user14.address)).to.be.equal(dropAmount);
    });

    mocha.step("Проверка на повторный клейм", async function() {
        await expect(airdrop.connect(user1).claim(Tree.getHexProof(keccak256(user1.address)))).to.be.revertedWith('Already claimed');
    });

    mocha.step("Проверка защиты от несанкционированного клейма", async function() {
        await expect(airdrop.connect(unwhitelisted).claim(Tree.getHexProof(keccak256(unwhitelisted.address)))).to.be.revertedWith('You are not whitelisted.');
    });
});

Зафиксируем количество потраченного газа на вызов функции “setRoot”.

Вызов функции “setRoot” обошолся в 46273 газа, по сравнению с вызовом “addToWhitelist”, мы сэкономили примерно в 7.5, при этом, если бы в тестировании AirdropV1 мы бы добавляли больше адhесов в вайтлист, то и экономия вышла бы больше, то есть чем больше информации нам нужно сохранить, тем рентабельнее использовать деревья Меркла в ваших умных контрактах.

Послесловие

Репозиторий демо-проекта

Остались вопросы? С чем-то не согласны? Пишите комментарии

Поддержать автора криптовалютой: 0x021Db128ceab47C66419990ad95b3b180dF3f91F