Raiz de Merkle

Uma raiz de Merkle é criada hasheando pares de TXIDs para obter uma impressão digital curta e única de todas as transações de um bloco.

Essa raiz de Merkle é colocada no cabeçalho do bloco para impedir que o conteúdo do bloco seja adulterado depois. Então, se alguém tentar adicionar ou remover uma transação do bloco, a raiz de Merkle das transações dentro do bloco não vai mais bater com a raiz de Merkle dentro do cabeçalho.

Em outras palavras, a raiz de Merkle é o que conecta o cabeçalho do bloco às transações do bloco.

Merkle Root

Calcule a raiz de Merkle a partir de uma lista de TXIDs.

Exemplo aleatório

Bloco

Lista de TXIDs

Uma lista de TXIDs separados por espaços, vírgulas ou novas linhas. Aspas e colchetes são ignorados.

Os TXIDs devem ser inseridos na ordem de byte invertida (como aparecem nos exploradores), mas são convertidos para a ordem de byte natural antes de calcular a raiz de Merkle.

TXIDs (0)

Raiz de Merkle (Ordem de Byte Natural)

A ordem dos bytes como sai da função de hash

Raiz de Merkle (Ordem de Byte Invertida)

A ordem dos bytes como mostrada nos exploradores

Estrutura

Como você cria uma raiz de Merkle?

Uma raiz de Merkle é criada hasheando os TXIDs em uma estrutura de árvore:

1. Hasheie os TXIDs juntos, em pares.
   • Nota: se sobrar um único item, hasheie-o com ele mesmo.
2. Pegue os hashes resultantes e hasheie-os juntos, em pares.
3. Repita até sobrar um único hash.

require 'digest' # Necessário para a função de hash SHA256

# Função de hash usada na função da raiz de Merkle (e no bitcoin em geral)
def hash256(hex)
    binary = [hex].pack("H*")
    hash1 = Digest::SHA256.digest(binary)
    hash2 = Digest::SHA256.digest(hash1)
    result = hash2.unpack("H*")[0]
    return result
end

def merkleroot(txids)

  # Condição de saída: para a recursão quando sobra um único resultado de hash
  if txids.length == 1
    # Converte o resultado para string e o retorna
    return txids.join('')
  end

  # Mantém um array de resultados
  result = []

  # 1. Divide o array de hashes em pares
  txids.each_slice(2) do |one, two|
    # 2a. Concatena cada par
    if (two)
      concat = one + two
    # 2b. Concatena consigo mesmo se não houver par
    else
      concat = one + one
    end

    # 3. Faz o hash do par concatenado e adiciona ao array de resultados
    result << hash256(concat)
  end

  # Recursão: faz a mesma coisa de novo para estes resultados
  merkleroot(result)
end


# Teste (ex.: bloco 000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506)
txids = [
  "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
  "fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
  "6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
  "e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d"
]

# Os TXIDs precisam estar em ordem natural de bytes ao criar a raiz de Merkle
txids = txids.map {|x| x.scan(/../).reverse.join('') }

# Cria a raiz de Merkle
result = merkleroot(txids)

# Exibe o resultado em ordem de bytes invertida
puts result.scan(/../).reverse.join('') #=> f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766

Árvore de Merkle

Por que usamos uma raiz de Merkle?

Essa estrutura de hashear uma lista de itens juntos é conhecida como árvore de Merkle (merkle tree). Mas por que usá-la?

Nós poderíamos simplesmente hashear todos os TXIDs de uma vez. Isso criaria uma impressão digital de todas as transações do bloco, e funcionaria. Mas, mais tarde, se quiséssemos descobrir se um TXID específico foi usado para criar essa impressão, precisaríamos conhecer todos os outros TXIDs:

É aí que entram as árvores de Merkle. Se usarmos uma árvore de Merkle, só precisamos conhecer alguns dos ramos ao longo do caminho da árvore para verificar que um TXID foi usado para criar o hash da raiz:

Esse caminho é conhecido como prova de Merkle (merkle proof).

Então, usando uma árvore de Merkle, podemos descobrir se uma transação faz parte de um bloco sem ter que conhecer todos os outros TXIDs do bloco. Ou, em termos técnicos, uma árvore de Merkle fornece uma forma eficiente de provar que algo está em um conjunto, sem ter que conhecer o conjunto completo.

E, se você está lidando com blocos que têm 2.000+ transações, as árvores de Merkle se tornam muito mais eficientes do que hashear todos os TXIDs de uma vez.

Exemplo de Prova de Merkle

Digamos que temos o cabeçalho de um bloco (e, portanto, a raiz de Merkle) do bloco 00000000000000000027ad67588ebcf18eabe2250c411e6b79ad1c009b4cb54f.

Agora digamos que queremos verificar se a transação f66f6ab609d242edf266782139ddd6214777c4e5080f017d15cb9aa431dda351 está dentro deste bloco.

Aqui está a prova de Merkle que comprova que a transação está dentro do bloco:

txid
----
f66f6ab609d242edf266782139ddd6214777c4e5080f017d15cb9aa431dda351 (ordem de bytes invertida)

prova de merkle
---------------
50ba87bdd484f07c8c55f76a22982f987c0465fdc345381b4634a70dc0ea0b38 esquerda
96b8787b1e3abed802cff132c891c2e511edd200b08baa9eb7d8942d7c5423c6 direita
65e5a4862b807c83b588e0f4122d4ca2d46691d17a1ec1ebce4485dccc3380d4 esquerda
1ee9441ddde02f8ffb910613cd509adbc21282c6e34728599f3ae75e972fb815 esquerda
ec950fc02f71fc06ed71afa4d2c49fcba04777f353a001b0bba9924c63cfe712 esquerda
5d874040a77de7182f7a68bf47c02898f519cb3b58092b79fa2cff614a0f4d50 esquerda
0a1c958af3e30ad07f659f44f708f8648452d1427463637b9039e5b721699615 esquerda
d94d24d2dcaac111f5f638983122b0e55a91aeb999e0e4d58e0952fa346a1711 esquerda
c4709bc9f860e5dff01b5fc7b53fb9deecc622214aba710d495bccc7f860af4a esquerda
d4ed5f5e4334c0a4ccce6f706f3c9139ac0f6d2af3343ad3fae5a02fee8df542 esquerda
b5aed07505677c8b1c6703742f4558e993d7984dc03d2121d3712d81ee067351 esquerda
f9a14bf211c857f61ff9a1de95fc902faebff67c5d4898da8f48c9d306f1f80f esquerda

raiz de merkle
--------------
17663ab10c2e13d92dccb4514b05b18815f5f38af1f21e06931c71d62b36d8af (ordem de bytes invertida)

Essa prova de Merkle contém uma lista dos ramos ao longo da árvore de Merkle de que precisamos para chegar à raiz. Esses ramos também indicam se estão à "esquerda" ou à "direita", para que você possa concatenar cada par na ordem correta ao hasheá-los.

Para verificar se o TXID faz parte da raiz de Merkle, basta começar pelo TXID e então concatenar e hashear recursivamente ao longo desta prova de Merkle, para confirmar que chegamos ao mesmo resultado da raiz de Merkle encontrada no cabeçalho do bloco.

Carteiras Leves

Graças às árvores de Merkle, você pode criar carteiras leves (ou "thin nodes") que conseguem verificar quando uma transação entrou em um bloco, sem o custo de ter que baixar e armazenar a blockchain inteira.

Essas carteiras apenas baixam e armazenam cabeçalhos de bloco (80 bytes cada, em vez de blocos de 1 MB+) e usam as raízes de Merkle dentro deles (junto com provas de Merkle que recebem de nós completos de arquivo) para verificar que uma transação entrou em um bloco.

Um exemplo popular de carteira leve é o Electrum.

Eu não tenho experiência com elas, então aqui estão alguns links interessantes:

• https://bitcoin.stackexchange.com/questions/32529/what-is-a-thin-client
• https://bitcoin.stackexchange.com/questions/11054/how-do-spv-simple-payment-verification-wallets-learn-about-incoming-transactio

Por que se chama raiz de "Merkle"?

Porque Ralph Merkle patenteou a ideia em 1979.

Equívoco comum.

Recursos

• James D'Angelo explicando raízes de Merkle
• Understanding Merkle Trees — Why Use Them, Who Uses Them, and How to Use Them

Agradecimentos

• Obrigado a Gabriele Semeraro por apontar um erro no código Ruby. Eu tinha a condição de saída para retornar o resultado depois da parte em que os pares de TXIDs são hasheados. Mas, se você só tem um item restante, basta retorná-lo sem fazer mais trabalho. Em outras palavras, se há apenas uma transação em um bloco, a raiz de Merkle é igual ao TXID.