Ferramentas criptográficas 101 — Entenda funções hash e árvores de Merkle

Sobre o que é este artigo?

As blockchains permitem que as pessoas cheguem a um consenso sem precisar de intermediários. Em vez de depender da confiança, elas usam provas criptográficas. Primitivas criptográficas são usadas para fornecer essas provas. Mas o que elas são?

Neste artigo, analisamos duas primitivas criptográficas essenciais para as provas criptográficas em blockchains: funções hash e árvores de Merkle. Vamos explorar os principais mecanismos das funções hash, entender sua importância para as blockchains e aprender sobre ponteiros de hash. Depois, examinaremos árvores de Merkle tradicionais e concorrentes, destacando sua importância para a Solana.

O que é uma primitiva criptográfica?

Uma primitiva criptográfica é uma operação ou um algoritmo fundamental para a criação de protocolos e sistemas criptográficos. As primitivas criptográficas estão para os protocolos criptográficos assim como os átomos estão para as moléculas: são os componentes básicos de soluções mais complexas. Geradores de números aleatórios, esquemas de compromisso e criptografia de chave pública são exemplos de primitivas criptográficas.

Isoladamente, as primitivas criptográficas são bastante limitadas. Quando combinadas, elas fornecem funções básicas de segurança, como autenticação, confidencialidade e integridade. Combinar primitivas criptográficas é um processo muito delicado, que exige bastante planejamento e um entendimento profundo de como cada primitiva interage com as demais. Durante esse processo, você deve considerar cuidadosamente a segurança de acordo com os objetivos que deseja alcançar. Os métodos de combinação de primitivas criptográficas podem ser classificados, de forma geral, como:

• Composição sequencial: aplicação de uma primitiva após a outra (por exemplo, encadeamento de hashes)
• Composição paralela: uso de primitivas de forma simultânea e independente (por exemplo, criptografar e gerar o hash de dados simultaneamente)
• Composição hierárquica: uso de uma primitiva criptográfica dentro de outra (por exemplo, árvores de Merkle)

Entender o que é uma primitiva criptográfica, como ela funciona e as sutilezas envolvidas em sua combinação ajuda você a compreender e projetar sistemas seguros e eficientes. Uma das primitivas criptográficas mais usadas e combinadas é a função hash.

O que é uma função hash?

Uma função hash é uma função criptográfica que recebe dados de qualquer tamanho e retorna um valor de tamanho fixo. O valor retornado por essa função é chamado de resumo, ou hash. Entre os algoritmos de hashing mais conhecidos estão: SHA-1, SHA-2, SHA-3, MD5 e Argon2. As funções hash são usadas em toda parte nas blockchains, por isso é fundamental entender o que são e como funcionam.

Uma analogia simples

Imagine que você esteja fazendo um bolo de chocolate sofisticado. O bolo tem várias camadas, cada uma feita com seus próprios ingredientes. Enquanto você prepara o bolo, uma pessoa amiga envia uma mensagem perguntando o que você está fazendo. Dar uma explicação detalhada sobre como preparou o bolo e todos os ingredientes usados seria bastante trabalhoso. Em vez disso, você decide enviar uma foto do bolo de chocolate.

Nesse caso, a foto do bolo funciona como um hash: uma representação simples e compacta de algo muito mais complexo. Essa pessoa não saberá cada um dos ingredientes usados no bolo, mas terá uma boa ideia do que você acabou de preparar. Digamos que seu bolo de chocolate tenha framboesas por cima. Se você as removesse ou as substituísse por morangos, a foto do bolo seria completamente diferente do produto final. Da mesma forma, qualquer alteração nos dados processados produziria um novo valor de hash.

Propriedades de uma boa função hash criptográfica

É preciso admitir que a definição de função hash apresentada anteriormente pode induzir ao erro. Uma função hash poderia retornar um hash de tamanho variável. Ela também poderia retornar o mesmo hash para duas entradas diferentes. Além disso, poderia ser extremamente fácil para alguém fazer engenharia reversa do hash e descobrir a entrada original. A definição anterior descrevia uma boa função hash criptográfica. Mas o que faz uma função hash criptográfica ser considerada boa?

Uma boa função hash é determinística: a mesma entrada sempre gera a mesma saída. Se eu calcular o hash da entrada “baseball”, essa função sempre produzirá o mesmo hash, independentemente do sistema. Isso também significa, em parte, que o hash terá o mesmo tamanho, independentemente do tamanho da entrada. Isso é importante para a eficiência do processamento e o armazenamento de dados. Saber que uma entrada única sempre produzirá uma saída única e que essas saídas sempre terão tamanho fixo é um indicador claro de uma boa função hash criptográfica.

Uma boa função hash é resistente à pré-imagem. Isso significa que é computacionalmente inviável fazer engenharia reversa do valor de entrada com base em seu hash. Portanto, se alguém fornecer um hash a você, não deverá ser possível descobrir quais dados o produziram. Isso também leva à ideia de que dois conjuntos de dados distintos não devem produzir o mesmo hash. Uma boa função hash é considerada resistente a colisões quando duas entradas quaisquer nunca produzem o mesmo hash.

Uma boa função hash segue o Efeito Avalanche: uma pequena alteração na entrada deve resultar em um hash drasticamente diferente. A alteração de um único caractere deve produzir um hash completamente diferente. Assim, a saída de um hash não deve revelar nenhuma informação sobre a entrada nem apresentar padrões reconhecíveis. Observe a diferença entre os hashes na figura acima. A raposa vermelha que “corre” gera um hash radicalmente diferente do produzido pela raposa vermelha que “caminha”. Também não há qualquer indicação de que esses dois hashes contenham informações quase idênticas.

Uma boa função hash deve ser rápida de calcular. Funções hash lentas não são práticas em situações que exigem computação em tempo real ou quase em tempo real, como a verificação de transações. Uma função hash lenta pode se tornar um gargalo grave, limitando o throughput e o desempenho da rede. Uma função hash rápida é necessária para um desempenho eficiente e seguro na blockchain.

Por que isso é importante para as blockchains?

Uma blockchain é um registro distribuído e descentralizado que armazena transações em toda a sua rede. Essas transações são agrupadas em blocos, que são vinculados com segurança por meio de uma função hash boa. Cada bloco contém dados de transações, um carimbo de data e hora e o hash do bloco anterior. Como o hash de cada bloco depende do hash do bloco anterior, qualquer alteração no conteúdo de um bloco mudaria seu hash e invalidaria todos os blocos seguintes. Esse processo de usar hashes anteriores na geração de um novo hash é conhecido como encadeamento de hashes.

A inclusão de um novo bloco em uma blockchain é conhecida como confirmação. Uma confirmação verifica e protege todas as transações do novo bloco, assim como todos os blocos anteriores. Isso acontece porque cada nova confirmação torna mais difícil alterar os blocos anteriores. Para alterar um bloco anterior, um invasor teria que recalcular todos os hashes anteriores. Assim, o encadeamento de hashes garante que seria inviável alterar a blockchain depois que um bloco recebesse uma quantidade considerável de confirmações.

Em termos simples, uma blockchain é uma cadeia de blocos protegida por funções hash. Mas como, exatamente, apontamos de um bloco para outro? Sim, uma função hash criptográfica é usada para encadear os blocos, mas como conseguimos consultar os dados dos blocos anteriores? Afinal, uma função hash criptográfica boa não deveria ser resistente à pré-imagem?

O que é um ponteiro de hash?

Um ponteiro é uma variável que armazena o local onde dados específicos estão guardados na memória. Os dados nesse endereço de memória podem ser acessados facilmente, pois o ponteiro “aponta para” a localização dos dados. Um ponteiro de hash é uma estrutura de dados semelhante a um ponteiro, mas que também contém um hash criptográfico dos dados referenciados. Assim, um ponteiro de hash informa onde acessar um dado específico e permite verificar a integridade dos dados acessados.

A estrutura de uma blockchain pode ser descrita com mais precisão como uma lista encadeada que usa ponteiros de hash. O hash do bloco anterior é um ponteiro de hash que aponta para um conjunto de transações e para um hash de todas essas transações. Os ponteiros de hash facilitam a vinculação dos blocos, garantem a integridade de cada bloco e permitem verificar se os blocos recém-adicionados sucedem corretamente os blocos anteriores.

Os ponteiros de hash são usados para encadear blocos com eficiência. Mas e as transações dentro do bloco? Se um bloco contivesse mil transações, não seria caro verificar cada uma delas individualmente?

O que é uma árvore de Merkle?

Uma árvore de Merkle é uma estrutura de dados usada para organizar e verificar grandes conjuntos de dados. Os dados são organizados em uma estrutura semelhante a uma árvore, na qual cada folha, ou nó, recebe como rótulo o hash de um conjunto de dados. Cada nó que não é folha contém um hash de seus nós filhos. As árvores de Merkle são usadas para verificar transações incluídas em blocos específicos que são propagados para a blockchain. Então, como isso funciona?

As transações são agrupadas em uma lista para formar um bloco. Cada transação da lista passa por uma função de hashing boa. Esses hashes formam os nós folha. Os nós folha são processados em pares para criar uma nova camada de hashes. Esse processo continua de forma iterativa até restar um único hash, conhecido como raiz de Merkle. A raiz de Merkle é armazenada no cabeçalho do bloco e funciona como uma impressão digital de todas as transações contidas nele. Também podemos chamar a raiz de Merkle de hash do bloco. Portanto, quando dizemos que um novo bloco é vinculado a um bloco anterior usando o blockhash do bloco anterior, queremos dizer que o bloco usa a raiz de Merkle do bloco anterior como parte do hash do novo bloco.

As árvores de Merkle tornam eficiente a verificação de transações individuais dentro de um bloco. Tradicionalmente, para verificar uma transação específica, seria necessário verificar cada transação, o que é caro e demorado. As árvores de Merkle oferecem um “atalho” criptográfico para ajudar nesse processo de verificação, conhecido como prova de Merkle. Uma prova de Merkle é um caminho que começa no nó folha da transação e vai até a raiz de Merkle. Usando a figura acima, pense nisso como um caminho entre Data A e a raiz de Merkle. Esse caminho também inclui seus nós irmãos, ou seja, as folhas adjacentes a cada nó do caminho, mas que não fazem parte do caminho em si. Um verificador pode calcular um hash usando o caminho da prova para conferir se o hash calculado corresponde à raiz de Merkle. Se o hash resultante corresponder, o verificador terá confiança de que a transação é legítima e não foi adulterada.

Uma folha pode ser alterada calculando o hash dos novos dados da folha e recalculando a raiz de Merkle. Essa nova raiz de Merkle é usada para verificar as alterações e invalida a prova anterior. Em uma rede de alto throughput como a Solana, os validadores podem receber solicitações de alteração em árvores de Merkle on-chain em rápida sucessão (por exemplo, dentro do mesmo slot). Cada alteração de dados precisaria ser recalculada sequencialmente. Caso contrário, cada solicitação de alteração seguinte seria invalidada pela solicitação anterior feita dentro do slot. Alterar os dados de uma folha e calcular uma nova raiz de Merkle é algo muito comum em blockchains. Então, como lidamos com alterações rápidas?

O que é uma árvore de Merkle concorrente?

Uma árvore de Merkle concorrente é uma árvore de Merkle otimizada para leituras e gravações simultâneas. Ela armazena um changelog seguro das alterações mais recentes, o hash raiz correspondente e a prova necessária para derivá-lo. Esse changelog fica armazenado on-chain em uma conta específica da árvore, com um número máximo de alterações que podem ocorrer enquanto a raiz de Merkle continua válida. Esse número máximo de alterações é conhecido como maxBufferSize. Assim, quando um validador recebe solicitações de alteração em uma árvore de Merkle on-chain em rápida sucessão, ele pode usar esse changelog como fonte da verdade, permitindo até maxBufferSize alterações na árvore dentro do mesmo slot.

As árvores de Merkle concorrentes aprimoram as árvores de Merkle tradicionais, tornando-as adequadas para ambientes de alto throughput, como a Solana. Para criar uma árvore de Merkle concorrente on-chain na Solana, existem três propriedades que afetam o tamanho da árvore, o custo de sua criação e o número de alterações simultâneas nela:

• Profundidade máxima
• Tamanho máximo do buffer
• Profundidade do canopy

A profundidade máxima se refere ao número máximo de saltos necessários para ir de qualquer folha até a raiz de Merkle. maxDepth é usado para determinar o número máximo de nós que serão armazenados na árvore. Isso pode ser calculado pela fórmula: numberOfNodes = 2 ^ maxDepth. A profundidade de uma árvore precisa ser definida durante sua criação. Portanto, é importante usar essa fórmula para determinar quantos dados você quer que a árvore armazene.

Como mencionado anteriormente, o tamanho máximo do buffer se refere ao número máximo de alterações que podem ser feitas em uma árvore sem invalidar sua raiz de Merkle.

A profundidade do canopy se refere a um subconjunto da árvore de Merkle armazenado on-chain. Essas provas em cache são usadas para comparar um hash com a raiz de Merkle on-chain. O caminho completo da prova deve ser usado para verificar a propriedade original de uma folha ao realizar uma gravação nela. Por exemplo, você precisaria gravar na árvore ao transferir um NFT. O canopy permite reduzir o tamanho da prova e evita que você use uma prova de tamanho maxDepth para verificar a árvore. Uma árvore com maxDepth igual a 20 exigiria uma prova de tamanho 20. Com um canopy de 15, basta enviar uma prova de tamanho 5 por transação de gravação. Portanto, uma profundidade maior do canopy exige um custo inicial mais alto para que você possa enviar provas menores posteriormente.

A profundidade do canopy é um dos principais fatores no custo de criação de uma árvore. Isso ocorre porque, quanto maior a profundidade do canopy, maior será a conta necessária. Os desenvolvedores podem usar o pacote @solana/spl-account-compression para calcular o espaço necessário para uma árvore de determinado tamanho e o custo de alocação desse espaço on-chain. Os desenvolvedores podem usar a função getConcurrentMerkleTreeAccountSize para calcular o espaço necessário para uma conta com base em seus parâmetros e aplicar getMinimumBalanceForRentExemption ao espaço necessário para obter o custo final em Lamports.

A Solana utiliza árvores de Merkle concorrentes para compressão de estado. A compressão de estado é o método de criar um hash de dados off-chain e armazená-lo on-chain para permitir uma verificação segura. O caso de uso mais conhecido da compressão de estado são os NFTs compactados, pois ela reduz drasticamente o custo de emissão. Por exemplo, emitir um bilhão de NFTs na Solana custaria 507 $SOL, em comparação com 12 000 000 $SOL usando NFTs “comuns”. Agora que você entende bem hashing e árvores de Merkle, vamos explorar os NFTs compactados em um artigo futuro!

Conclusão

Parabéns! Neste artigo, analisamos funções hash e árvores de Merkle, duas primitivas criptográficas essenciais para as blockchains. Entender blockchains não é uma tarefa simples: elas são sistemas distribuídos complexos que exigem um amplo conhecimento técnico. Muitas vezes, pressupõe-se que desenvolvedores, usuários ou investidores comuns já tenham esse conhecimento. Este artigo não pressupõe nenhum conhecimento prévio sobre primitivas criptográficas. Em vez disso, começamos pelo básico antes de avançar para discussões mais complexas sobre árvores de Merkle tradicionais e concorrentes. Ter essa compreensão fundamental é crucial enquanto nos preparamos para explorar temas mais complexos, como NFTs compactados. Com esse novo conhecimento, você está mais preparado para navegar por bases de código ou participar de discussões sobre primitivas criptográficas e soluções criptográficas mais complexas.

Se você leu até aqui, anon, muito obrigado!

Recursos adicionais / Leituras complementares

• Capítulo detalhado de um livro sobre primitivas criptográficas
• Artigo que compara algoritmos de hashing seguros
• Algoritmos de hashing e segurança — vídeo do Computerphile no YouTube
• Vídeo conciso no YouTube sobre árvores de Merkle
• Conheça a compactação de NFTs na Solana