Provas de Merkle para integridade de dados offline

Introdução

Idealmente, gostaríamos de guardar tudo no armazenamento do Ethereum, que é armazenado em milhares de computadores e conta com uma disponibilidade extremamente alta (os dados não podem ser censurados) e integridade (os dados não podem ser modificados de forma não autorizada), sabendo que armazenar uma palavra de 32 bytes normalmente custa 20.000 gás. No momento em que estou escrevendo isto, o custo é equivalente a $6,60. A 21 centavos por byte, isso é bastante caro para muitas utilizações.

Para resolver esse problema, o ecossistema do Ethereum desenvolveu muitas formas alternativas de armazenar dados de forma descentralizada. Geralmente, elas envolvem um equilíbrio entre a disponibilidade e o preço. No entanto, a integridade é geralmente assegurada.

Neste artigo, você aprenderá como garantir a integridade dos dados sem armazenar os dados na blockchain, usando provas de Merkle(opens in a new tab).

Como isso funciona?

Em teoria, poderíamos apenas armazenar o hash dos dados na cadeia e enviar todos os dados em transações que precisam deles. No entanto, isso ainda é demasiado caro. Um byte de dados para uma transação custa cerca de 16 gás, atualmente cerca de meio centavo ou cerca de $5 por kilobyte. A $5.000 por megabyte, isso ainda é muito caro para várias utilizações, mesmo sem o custo adicional de hashing de dados.

A solução é fazer hash repetidamente de diferentes subconjuntos dos dados. Para os dados que você não precisa enviar, você pode apenas enviar um hash. Você pode fazer isso usando uma árvore de Merkle, uma estrutura de dados de árvore em que cada nó é um hash dos nós abaixo:

O hash raiz é a única parte que precisa ser armazenada na cadeia. Para comprovar um determinado valor, forneça todos os hashes que precisam ser combinados com ele para obter a raiz. Por exemplo, para provar C você fornece D, (H-B), e H(E-H).

Implementação

O código de exemplo é fornecido aqui(opens in a new tab).

Código fora da cadeia

Neste artigo, usamos JavaScript para os cálculos fora da cadeia. A maioria dos aplicativos descentralizados tem seu componente off-chain em JavaScript.

Criando a raiz Merkle

Primeiro, precisamos fornecer a raiz Merkle à cadeia.

1const ethers = require("ethers")

Usamos a função hash do pacote ethers(opens in a new tab).

1// The raw data whose integrity we have to verify. The first two bytes a
2// are a user identifier, and the last two bytes the amount of tokens the
3// user owns at present.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Codificar cada entrada em um único inteiro de 256 bits resulta em um código menos legível que o JSON, por exemplo. No entanto, isso significa um processamento significativamente menor para recuperar os dados contidos no contrato, portanto, custos de gás muito menores. Você pode ler o JSON na cadeia(opens in a new tab), porém, isso é uma má ideia e evite fazer isso se puder.

1// The array of hash values, as BigInts
2const hashArray = dataArray

Nesse caso, para começar, nossos dados têm um valor 256 bits. Portanto, não é necessário qualquer tipo de processamento. Se usarmos uma estrutura de dados mais complicada, como cadeias de caracteres, precisamos ter certeza de que fazemos primeiro o hash dos dados para obter uma matriz de hashes. Observe que isso também é devido ao fato de não nos importarmos se usuários conhecem as informações de outros usuários. Caso contrário, teríamos tido que fazer um hash, para que o usuário 1 não saiba o valor para o usuário 0, ao usuário 2 que não saberá o valor para o usuário 3, etc.

1// Convert between the string the hash function expects and the
2// BigInt we use everywhere else.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

A função hash de ethers espera obter uma cadeia de caracteres em JavaScript com um número hexadecimal, como 0x60A7, e responde com outra cadeia de caracteres com a mesma estrutura. No entanto, para o resto do código, é mais fácil usar BigInt, então convertemos em uma cadeia de caracteres hexadecimal e de volta novamente.

1// Symmetrical hash of a pair so we won't care if the order is reversed.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Essa função é simétrica (hash de um xor(opens in a new tab) b). Isto significa que quando verificamos a prova de Merkle, não precisamos nos preocupar se devemos colocar o valor da prova antes ou depois do valor calculado. A verificação da prova de Merkle é feita na cadeia, portanto, quanto menos precisarmos fazer lá, melhor.

Atenção: A criptografia é mais difícil do que parece. A versão inicial deste artigo tinha a função hash hash(a^b). Essa foi uma má ideia, porque significava que se você conhecesse os valores legítimos de a e de b, você poderia usar b' = a^b^a' para provar qualquer valor a' desejado. Com essa função, você teria que calcular b', de forma que hash(a') ^ hash(b') fosse igual a um valor conhecido (o próximo branch a caminho da raiz), o que é muito mais difícil.

1// The value to denote that a certain branch is empty, doesn't
2// have a value
3const empty = 0n

Quando o número de valores não é uma potência inteira de dois, precisamos lidar com branches vazios. O programa faz isso colocando zero como espaço reservado.

1// Calculate one level up the tree of a hash array by taking the hash of
2// each pair in sequence
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // To avoid over writing the input // Add an empty value if necessary (we need all the leaves to be // paired)
6
7  if (inp.length % 2 === 1) inp.push(empty)
8
9  for (var i = 0; i < inp.length; i += 2)
10    result.push(pairHash(inp[i], inp[i + 1]))
11
12  return result
13} // oneLevelUp
Exibir tudo

Esta função “escala” um nível na árvore de Merkle, fazendo hash dos pares de valores na camada atual. Observe que esta não é a implementação mais eficiente. Poderíamos ter evitado copiar a entrada e apenas adicionar hashEmpty quando apropriado no loop, mas este código é otimizado para melhorar a legibilidade.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Climb up the tree until there is only one value, that is the // root. // // If a layer has an odd number of entries the // code in oneLevelUp adds an empty value, so if we have, for example, // 10 leaves we'll have 5 branches in the second layer, 3 // branches in the third, 2 in the fourth and the root is the fifth
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
Exibir tudo

Para obter a raiz, suba até que haja apenas um valor restante.

Criando uma prova de Merkle

Uma prova de Merkle é o conjunto de valores a fazer hash junto com o valor que está sendo provado para recuperar a raiz de Merkle. O valor a provar está frequentemente disponível a partir de outros dados, então eu prefiro fornecê-lo separadamente do que como parte do código.

1// A merkle proof consists of the value of the list of entries to
2// hash with. Because we use a symmetrical hash function, we don't
3// need the item's location to verify the proof, only to create it
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Until we reach the top
8    while (currentLayer.length > 1) {
9        // No odd length layers
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // If currentN is odd, add with the value before it to the proof
15            ? currentLayer[currentN-1]
16               // If it is even, add the value after it
17            : currentLayer[currentN+1])
18
Exibir tudo

Fazemos o hash (v[0],v[1]), (v[2],v[3]), etc. Portanto, para valores pares, precisamos do próximo e, para valores ímpares, precisamos do anterior.

1        // Move to the next layer up
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

Código on-chain

Por fim, temos o código que verifica a prova. O código on-chain é escrito em Solidity(opens in a new tab). A otimização é aqui muito mais importante, porque o gás é relativamente caro.

1//SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";
 Copiar

Escrevi isso usando o ambiente de desenvolvimento de hardware(opens in a new tab), que nos permite ter saída do console do Solidity(opens in a new tab) em desenvolvimento.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Extremely insecure, in production code access to
10    // this function MUST BE strictly limited, probably to an
11    // owner
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Exibir tudo
 Copiar

Configure e obtenha funções para a raiz de Merkle. Deixar que todo mundo atualize a raiz de Merkle é uma ideia extremamente má em um sistema de produção. Aqui, faço isso por uma questão de simplicidade no código de exemplo. Não faça isso em um sistema no qual a integridade de dados realmente importa.

1    function hash(uint _a) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a)));
3    }
4
5    function pairHash(uint _a, uint _b) internal pure returns(uint) {
6      return hash(hash(_a) ^ hash(_b));
7    }
 Copiar

Essa função gera um par de hashes. Ela é simplesmente a tradução do Solidity do código em JavaScript para hash e pairHash.

Observação: Este é outro caso de otimização para facilidade de leitura. Baseado em a definição da função(opens in a new tab), é possível armazenar os dados como um valor de bytes32(opens in a new tab) e evitar as conversões.

1    // Verify a Merkle proof
2    function verifyProof(uint _value, uint[] calldata _proof)
3        public view returns (bool) {
4      uint temp = _value;
5      uint i;
6
7      for(i=0; i<_proof.length; i++) {
8        temp = pairHash(temp, _proof[i]);
9      }
10
11      return temp == merkleRoot;
12    }
13
14}  // MarkleProof
Exibir tudo
 Copiar

Na notação matemática, a verificação pela prova de Merkle tem esta aparência: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(prova_1, H(prova_0, valor)...))). Este código implementa-o.

Provas de Merkle e rollups não se misturam

As provas de Merkle não funcionam bem com rollups. O motivo é que os rollups escrevem todos os dados da transação no L1, mas são processadas no L2. O custo para enviar uma prova de Merkle com uma média de transação a 638 gás por camada (atualmente, um byte nos dados de chamadas custa 16 gás se não for zero, e 4 se for zero). Se temos 1024 palavras de dados, uma prova de Merkle requer dez camadas, ou um total de 6380 gás.

Procurando um exemplo no Optimism(opens in a new tab), escrever custos de gás L1 custa cerca de 100 gwei e escrever custos de gás L2 custa 0,001 gwei (esse é o preço normal, que pode aumentar com o congestionamento). Portanto, pelo custo de um gás L1 podemos gastar cem mil gás no processamento L2. Supondo que não sobrescrevamos o armazenamento, isso significa que podemos escrever cerca de cinco palavras para armazenamento na L2 pelo preço de um gás L1. Para uma única prova de Merkle, podemos escrever todas as 1024 palavras para armazenamento (assumindo que elas podem ser calculadas em cadeia para começar, em vez de serem fornecidos em uma transação) e ainda restam a maior parte do gás.

Conclusão

Na vida real, você pode nunca implementar Merkle por conta própria. Existem bibliotecas conhecidas e auditadas que você pode usar e, de um modo geral, é melhor não implementar primitivos criptográficos por conta própria. Mas espero que agora você compreenda melhor as provas de Merkle e que possa decidir quando é que vale a pena utilizar.

Observe que, enquanto as provas de Merkle preservam a integridade, elas não preservam a disponibilidade __. Saber que mais ninguém pode tomar seus ativos é uma pequena consolação se o armazenamento de dados decidir impedir o acesso e você não pode construir uma Merkle para acessá-los também. Portanto, as árvores de Merkle são melhor usadas com algum tipo de armazenamento descentralizado, como IPFS.