23 de maio de 2023
Introdução: uma árvore de Merkle, também conhecida como árvore de hash, é uma estrutura de dados comumente usada em criptografia e ciência da computação. É nomeada em homenagem a Ralph Merkle, que inventou o conceito no final de 1970.
A árvore de Merkle é construída usando uma estrutura hierárquica de nós, onde os nós das folhas representam os dados reais e os nós intermediários são criados por hash da concatenação de seus nós filhos. O processo continua recursivamente até que um único nó raiz, conhecido como raiz da Merkle, seja obtido.
Para melhor compreensão:
In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large data structure. A hash tree is a generalization of a hash list and a hash chain.
Passo 1: Configurando o Projeto
Crie um novo diretório para o seu projeto e navegue até ele usando uma interface de linha de comando.
Inicialize um novo projeto npm executando:
npm init -y
Instale as bibliotecas keccak256, merkletreejs e fs executando:
npm install keccak256 merkletreejs fs
Passo 2: Implementando a Árvore de Merkle
Crie um novo arquivo (por exemplo, MerkleTree.js) e importe a função keccak256 da biblioteca keccak256 e MerkelTree da merkletreejs.
const keccak256 = require("keccak256");
const { default: MerkleTree } = require("merkletreejs");
Depois de importar, crie um array de endereço da Ethereum.
const address = [
"0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
"0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
"0x5B38Da6a701c568545dCfcB03FcB875f56beddC4"
];
Eu utilizei meus três endereços da Ethereum para colocar este endereço na lista de permissões (whitelist). Ao invés desses endereços, você pode usar o endereço que deseja colocar na lista de permissões.
Agora vamos para o hashing de todas as folhas de forma individual e para a construção da árvore de Merkle.
// Hash De Todas As Folhas De Forma Individual
const leaves = address.map((leaf) => keccak256(leaf));
// Construção da árvore de Merkle
const tree = new MerkleTree(leaves, keccak256, {
sortPairs: true,
});
Agora escreva uma função utilitária para converter de buffer para hex e entre para obter a raiz da árvore de Merkle.
// Função Utilitária para Converter de Buffer para Hex
const buf2Hex = (x) => "0x" + x.toString("hex");
// Obter a Raiz da Árvore de Merkle
console.log(`Here is Root Hash: ${buf2Hex(tree.getRoot())}`);
Agora a criação de um objeto de lista de permissões que contém cada endereço de usuário da lista, folha e prova da lista de permissões.
let data = [];
// Colocando todas as provas e folhas no array de dados
address.forEach((address) => {
const leaf = keccak256(address);
const proof = tree.getProof(leaf);
let tempData = [];
proof.map((x) => tempData.push(buf2Hex(x.data)));
data.push({
address: address,
leaf: buf2Hex(leaf),
proof: tempData,
});
});
// Criar um objeto da Lista de Permissões para gravar um arquivo JSON
let whiteList = {
whiteList: data,
};
Agora, importe fs da biblioteca fs para gravar um arquivo .json para todos os usuários da lista de permissões.
const fs = require("fs");
Agora escreva um arquivo whiteList.json no diretório raiz.
// Objeto Stringify whiteList recebe o método stringfy (que converte valores em javascript para uma string JSON) e formatação
const metadata = JSON.stringify(whiteList, null, 2);
// Grava o arquivo whiteList.json no diretório raiz
fs.writeFile(`whiteList.json`, metadata, (err) => {
if (err) {
throw err;
}
});
Agora mescle todo o código.
Aqui está a MerkleTree.js atualizada.
const keccak256 = require("keccak256");
const { default: MerkleTree } = require("merkletreejs");
const fs = require("fs");
const address = [
"0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
"0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
"0x5B38Da6a701c568545dCfcB03FcB875f56beddC4"
];
// Hashing de todas as folhas de forma individual
const leaves = address.map((leaf) => keccak256(leaf));
// Construção da árvore de Merkle
const tree = new MerkleTree(leaves, keccak256, {
sortPairs: true,
});
// Função utilitária para converter de buffer para hex
const buf2Hex = (x) => "0x" + x.toString("hex");
// Obtém a raiz da árvore Merkle
console.log(`Here is Root Hash: ${buf2Hex(tree.getRoot())}`);
let data = [];
// Colocando todas as provas e folhas no array de dados
address.forEach((address) => {
const leaf = keccak256(address);
const proof = tree.getProof(leaf);
let tempData = [];
proof.map((x) => tempData.push(buf2Hex(x.data)));
data.push({
address: address,
leaf: buf2Hex(leaf),
proof: tempData,
});
});
// Cria um objeto da lista de permissões para gravar um arquivo JSON
let whiteList = {
whiteList: data,
};
// Objeto Stringify whiteList recebe o método stringfy (que converte valores em javascript para uma string JSON) e formatação
const metadata = JSON.stringify(whiteList, null, 2);
// Grava o arquivo whiteList.json no diretório raiz
fs.writeFile(`whiteList.json`, metadata, (err) => {
if (err) {
throw err;
}
});
Salve o arquivo e execute.
node merkleTree.js
Ele irá gerar um hash raiz e um arquivo whiteList.json.
e um .json como:
{
"whiteList": [
{
"address": "0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
"leaf": "0x04a10bfd00977f54cc3450c9b25c9b3a502a089eba0097ba35fc33c4ea5fcb54",
"proof": [
"0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb",
"0x5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229"
]
},
{
"address": "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
"leaf": "0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb",
"proof": [
"0x04a10bfd00977f54cc3450c9b25c9b3a502a089eba0097ba35fc33c4ea5fcb54",
"0x5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229"
]
},
{
"address": "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4",
"leaf": "0x5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229",
"proof": [
"0x39a01635c6a38f8beb0adde454f205fffbb2157797bf1980f8f93a5f70c9f8e6"
]
}
]
}
Neste .json você pode ver o endereço, a folha e a prova de Merkle.
Passo 3: Integrando a Árvore de Merkle em um Contrato Inteligente do Solidity
Agora estamos criando um contrato inteligente de contador e somente o usuário da lista de permissões pode incrementar a contagem. Para a criação de um contrato inteligente, abra o RemixIDE no navegador https://remix.ethereum.org/.
Crie um novo arquivo (por exemplo, MerkleTreeWhiteListCounter.sol) e importe MerkleProof.sol da biblioteca pública do Openzeppelin.
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.18;
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
Agora, crie um contrato com o nome MerkleTreeWhiteListCount e defina um construtor (constructor) com a entrada bytes32, esse é o seu hash raíz da árvore de Merkle (Merkle Tree RootHash). Inicialize-o em uma variável de estado e também defina uma variável de contagem.
contract MerkleTreeWhiteListCounter {
bytes32 public rootHash;
uint256 public count;
constructor(bytes32 _rootHash){
rootHash = _rootHash;
}
Neste momento, crie uma função com o nome isValidProof e certifique-se de que ela está definida como uma função privada. Essa função verificará se a prova é válida ou não. Isso levará a inserir, primeiro, uma Prova Merkle (MerkleProof) e, segundo, uma folha (leaf).
function isValidProof(bytes32[] calldata proof, bytes32 leaf) private view returns (bool) {
return MerkleProof.verify(proof, rootHash, leaf);
}
Agora, crie um modificador (modifier) com o nome isWhiteListedAddress.
modifier isWhiteListedAddress(bytes32[] calldata proof){
require(isValidProof(proof,keccak256(abi.encodePacked(msg.sender))),"Not WhiteListed Address");
_;
}
Este modificador pegará uma entrada, que é a MerkleProof, e chamará internamente a função isValidProof. Ele então passará a prova e gerará uma folha usando keccak256 e passará o remetente da mensagem (msg.sender) para garantir que está passando o (msg.sender). Caso você passe diretamente algum endereço, significa que não será mais apenas para usuários da lista de permissões, porque qualquer um pode entrar e chamar a função da lista de permissões usando a prova e o endereço Merkle de outro usuário.
Agora, crie uma função que seja chamada apenas por usuários da lista de permissões e use o modificador isWhiteListedAddress. Você precisa passar apenas a MerkleProof, não precisa passar a folha. A folha será gerada usando keccak256 usando msg.sender.
function whiteListIncrement(bytes32[] calldata proof) isWhiteListedAddress(proof) external {
count++;
}
Agora mescle todo o código.
Aqui está o MerkleTreeWhiteListCounter.sol atualizado.
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.18;
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
contract MerkleTreeWhiteListCounter {
bytes32 public rootHash;
uint256 public count;
constructor(bytes32 _rootHash){
rootHash = _rootHash;
}
modifier isWhiteListedAddress(bytes32[] calldata proof){
require(isValidProof(proof,keccak256(abi.encodePacked(msg.sender))),"Not WhiteListed Address");
_;
}
function isValidProof(bytes32[] calldata proof, bytes32 leaf) private view returns (bool) {
return MerkleProof.verify(proof, rootHash, leaf);
}
function whiteListIncrement(bytes32[] calldata proof) isWhiteListedAddress(proof) external {
count++;
}
}
Salve e implante o contrato inteligente MerkleTreeWhiteListCounter usando RemixIDE e passe a MerkleTree RootHash para o construtor.
Implante o contrato. Você verá o endereço do contrato abaixo.
Agora, chame a função whiteListIncrement com a prova válida e use o endereço da lista de permissões para chamá-lo.
E, então, você pode ver sua transação executada com sucesso.
Se você não usar uma prova ou endereço válidos, ele mostrará um erro.
Conclusão: a árvore de Merkle é uma estrutura de dados hierárquica amplamente utilizada em criptografia e ciência da computação. Ela fornece verificação eficiente da integridade dos dados, segurança contra adulteração e armazenamento eficiente de grandes conjuntos de dados. As árvores de Merkle são utilizadas em várias aplicações, incluindo a tecnologia blockchain, onde desempenham um papel crucial na garantia da imutabilidade e confiabilidade de transações e dados.
Revisão geral
A revisão geral do código da Lista de Permissões Usando a Árvore de Merkle em Solidity está no GitHub.
Esse artigo foi escrito por Shubham Yadav e traduzido por Isabela Curado Nehme. Seu original pode ser lido aqui.
Top comments (0)