Главная » Ответы

Понять дерево Меркла, составив белый список майнинга NFT

На чтение 9 мин. Просмотров 80 Опубликовано

TL;DR
Если вы знакомы с деревом Меркла и хотите перейти к коду. То вам сюда:

  • Упрощенные коды, которые я использую в этой статье: Github
  • Более DRY версия, которую вы можете повторно использовать в своем проекте: Github
Содержание
  1. Оглавление
  2. Введение
  3. Что такое дерево Меркла
  4. Проверка данных с помощью дерева Меркла
  5. Создание белого списка с помощью дерева Меркла
  6. Настройка
  7. Смарт-контракт
  8. Создание белого списка
  9. Шаг 1: Создание дерева Меркла
  10. Шаг 2: Получение доказательств Меркла
  11. Шаг 3: Получить корень Меркла
  12. Шаг 4: Верификация адреса и количества пользователей 
  13. Заключение

Оглавление

  • Введение
  • Что такое дерево Меркла
  • Проверка данных с помощью дерева Меркла
  • Создание белого списка с помощью дерева Меркла
    • Настройка
    • Умный контракт
    • Создание белого списка
    • Шаг 1: Создайте дерево Меркла
    • Шаг 2: Получить доказательства Меркеля
    • Шаг 3: Получить корень Меркла
    • Шаг 4: Проверить адрес и количество пользователей
  • Заключение

Введение

Белые списки NFT — это способ поощрения активных пользователей вашего сообщества и эффективный инструмент для предотвращения мошенничества. Вместо того чтобы хранить данные всех пользователей на цепочке (что дорого), мы можем сгенерировать дерево Меркла из данных пользователей. Из дерева мы извлекаем и храним на цепочке только корень дерева (байт32). Это сэкономит тонну платы за газ!
В этой статье я объясню, как работает дерево Меркла на примере создания белого списка майнинга для моего выдуманного проекта NFT, Excited Apes Yacht Club (EAYC).
 

Что такое дерево Меркла

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

В приведенном выше примере дерева есть четыре блока данных. В результате хэширования каждого из них получаются четыре листовых узла A-0, A-1, B-0 и B-1. Каждая последовательная пара листовых узлов (A-0, A-1), (B-0, B-1) многократно хэшируется для создания нелистовых узлов A и B. Наконец, хэши двух нелистовых узлов (A и B) снова хэшируются для создания корневого хэша (корня Меркла).

Проверка данных с помощью дерева Меркла

Чтобы проверить, существует ли хэш A-0 (целевой хэш) в дереве Меркла, нам нужно перестроить дерево. Для этого нам нужны только хэши A-1 и B. Если мы сможем воссоздать корневой хэш, то хэш A-0 будет действительным. В этом и заключается красота дерева Меркла! Нам не нужно знать все его хэши, чтобы проверить целевой хэш.

Создание белого списка с помощью дерева Меркла

Настройка

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

Смарт-контракт

Мы будем использовать ERC721 для нашего проекта NFT.

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

import '@openzeppelin/contracts/token/ERC721/ERC721.sol';
import '@openzeppelin/contracts/utils/Counters.sol';
import {MerkleProof} from '@openzeppelin/contracts/utils/cryptography/MerkleProof.sol';

contract ExcitedApeYachtClub is ERC721 {
    using Counters for Counters.Counter;
    Counters.Counter private _tokenIds;

    bytes32 public merkleRoot;

    constructor(bytes32 merkleRoot_) ERC721('Excited Ape Yacht Club', 'EAYC') {
        merkleRoot = merkleRoot_;
    }

    function mint(uint256 quantity, bytes32[] calldata merkleProof) public {
        bytes32 node = keccak256(abi.encodePacked(msg.sender, quantity));
        require(MerkleProof.verify(merkleProof, merkleRoot, node), 'invalid proof');

        for (uint256 i = 0; i < quantity; i++) {
            uint256 tokenId = _tokenIds.current();
            _mint(msg.sender, tokenId);

            _tokenIds.increment();
        }
    }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Обратите внимание, что мы объявляем bytes32 public merkleRoot; для хранения корня дерева Меркла, и используем его для проверки на merkleProof и node внутри функции mint.

Создание белого списка

Допустим, в нашем сообществе есть 3 активных пользователя: Алиса, Боб и Кэрол. В зависимости от их вклада, мы разрешаем каждому пользователю майнить разное количество.
Мы можем разбить эту процедуру на 4 шага:

  1. Создать дерево Меркла из адресов пользователей и их количества.
  2. Получить доказательство каждого листового узла и сохранить его вне цепи.
  3. Получить корень дерева Меркла и сохранить его в смарт-контракте NFT.
  4. Проверять адреса и количество пользователей на смарт-контракте NFT, когда они пытаются майнить. Если доказательство пользователя действительно, ему разрешается майнить.

Шаг 1: Создание дерева Меркла

Мы будем использовать merkletreejs, ethers и keccak256 для создания дерева Меркла, которое работает со смарт-контрактами Solidity. Вот код:

import { MerkleTree } from "merkletreejs";
import ethers from "ethers";
import keccak256 from "keccak256";
// inputs: array of users' addresses and quantity
// each item in the inputs array is a block of data
// Alice, Bob and Carol's data respectively
const inputs = [
  {
    address: "0x70997970C51812dc3A010C7d01b50e0d17dc79C8",
    quantity: 1,
  },
  {
    address: "0x3C44CdDdB6a900fa2b585dd299e03d12FA4293BC",
    quantity: 2,
  },
  {
    address: "0x90F79bf6EB2c4f870365E785982E1f101E93b906",
    quantity: 1,
  },
];
// create leaves from users' address and quantity
const leaves = inputs.map((x) =>
  ethers.utils.solidityKeccak256(
    ["address", "uint256"],
    [x.address, x.quantity]
  )
);
// create a Merkle tree
const tree = new MerkleTree(leaves, keccak256, { sort: true });
console.log(tree.toString());
Войти в полноэкранный режим Выйти из полноэкранного режима

В консоли мы видим наше дерево Меркла. Первый хэш — это корень дерева Меркла. Ниже — нелистовые узлы и листовые узлы.

cd1ce05417f11ebd5c23784283d21a968ac750e5ac2c2baa6b82835f4ea7caf7
   ├─ f92db5e3e1d6bed45d8e50fad47eddeb89c5453802b5cb6d944df2f3679da55c
   │  ├─ 3f68e79174daf15b50e15833babc8eb7743e730bb9606f922c48e95314c3905c
   │  └─ b783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7
   └─ d0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee
      └─ d0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee
Войти в полноэкранный режим Выход из полноэкранного режима

Вот диаграмма дерева Меркла, которое мы только что сгенерировали.

Коэффициент ветвления равен 2, но у нас есть 3 блока данных. Поэтому в ветви Carol каждый узел имеет только 1 дочерний узел.

Шаг 2: Получение доказательств Меркла

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

const proofs = leaves.map(leave=> tree.getHexProof(leaf))
Войдите в полноэкранный режим Выйдите из полноэкранного режима

Доказательства должны выглядеть следующим образом

[
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ],
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ],
 [
 '0xb783e75c6c50486379cdb997f72be5bb2b6faae5b2251999cae874bc1b040af7',
 '0xd0583fe73ce94e513e73539afcb4db4c1ed1834a418c3f0ef2d5cff7c8bb1dee'
 ]
]
Вход в полноэкранный режим Выход из полноэкранного режима

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

Шаг 3: Получить корень Меркла

const root = tree.getHexRoot();
Войдите в полноэкранный режим Выйти из полноэкранного режима 
0xcd1ce05417f11ebd5c23784283d21a968ac750e5ac2c2baa6b82835f4ea7caf7
Войти в полноэкранный режим Выйти из полноэкранного режима

Все просто! Мы сохраним корень на цепочке, когда развернем смарт-контракт.

Шаг 4: Верификация адреса и количества пользователей 

Подготовив доказательства Меркла и корень, мы можем проверить, находится ли пользователь в нашем белом списке. Сначала мы воссоздадим хэш узла из адреса пользователя и его количества с помощью keccak256 от Solidity. Затем мы можем вызвать MerkleProof.verify, чтобы проверить, существует ли хэш в нашем дереве Меркла. Если да, то пользователю разрешается продолжить.

 bytes32 node = keccak256(abi.encodePacked(msg.sender, quantity));
require(MerkleProof.verify(merkleProof, merkleRoot, node), 'invalid proof');
Вход в полноэкранный режим Выход из полноэкранного режима

Приведенные ниже коды являются модульными тестами для смарт-контракта. Дальше все должно быть понятно само собой.

import { loadFixture } from '@nomicfoundation/hardhat-network-helpers';
import { expect } from 'chai';
import { ethers } from 'hardhat';
import { makeMerkleTree } from '../utils/merkletree';
import { makeUsers } from '../utils/data';

describe('ExcitedApeYachtClub', function () {
  async function deployOneYearLockFixture() {
    const merkleTreeData = await makeMerkleTree();
    const { root } = merkleTreeData;

    const users = await makeUsers();

    const ExcitedApeYachtClub = await ethers.getContractFactory(
      'ExcitedApeYachtClub'
    );

    const excitedApeYachtClub = await ExcitedApeYachtClub.deploy(root);

    return { excitedApeYachtClub, merkleTreeData, users };
  }

  beforeEach(async function () {
    const { excitedApeYachtClub, users, merkleTreeData } = await loadFixture(
      deployOneYearLockFixture
    );
    this.excitedApeYachtClub = excitedApeYachtClub;
    this.users = users;
    this.merkleTreeData = merkleTreeData;
  });

  describe('Deployment', function () {
    it('Should return correct name and symbol', async function () {
      expect(await this.excitedApeYachtClub.name()).to.equal(
        'Excited Ape Yacht Club'
      );
      expect(await this.excitedApeYachtClub.symbol()).to.equal('EAYC');
    });
  });

  describe('mint', function () {
    beforeEach(async function () {
      await this.excitedApeYachtClub
        .connect(this.users.alice)
        .mint(1, this.merkleTreeData.proofs[0]);

      await this.excitedApeYachtClub
        .connect(this.users.bob)
        .mint(2, this.merkleTreeData.proofs[1]);
    });

    it('Should allow whitelisted users to mint', async function () {
      const aliceBalance = await this.excitedApeYachtClub.balanceOf(
        await this.users.alice.getAddress()
      );

      expect(aliceBalance).to.equal(1);

      const bobBalance = await this.excitedApeYachtClub.balanceOf(
        await this.users.bob.getAddress()
      );

      expect(bobBalance).to.equal(2);
    });

    it('Should revert when users try to mint over allowed quantity', async function () {
      try {
        await this.excitedApeYachtClub
          .connect(this.users.alice)
          .mint(2, this.merkleTreeData.proofs[1]);
      } catch (error: any) {
        expect(error.message).to.contains('invalid proof');
      }
    });

    it('Should revert when non-whitelisted users try to mint', async function () {
      try {
        await this.excitedApeYachtClub
          .connect(this.users.david)
          .mint(1, this.merkleTreeData.proofs[1]);
      } catch (error: any) {
        expect(error.message).to.contains('invalid proof');
      }
    });
  });
});
Вход в полноэкранный режим Выход из полноэкранного режима

Заключение

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

P/S: Я начал понимать пользу от ведения блога как разработчик. Я стараюсь писать как можно больше после своей работы. Это мой первый блог о программировании. Надеюсь, он вам понравится.
Спасибо, что читаете. Я ценю это.

Оцените статью
devanswers.ru
Добавить комментарий