Reading Time: 10 minutes

Blockchain

O bitcoin é o nome de batismo de uma criptomoeda que teve um enorme impacto quando foi libertada na Internet e também todo o conceito e tecnologia em seu redor foi alvo de pura análise e investigação nos últimos anos. A aceitação desta criptomoeda foi de tal maneira exponencial que se refletiu de imediato na sua crescente valorização no mercado [1].

Uma das tecnologias base do bitcoin é a blockchain, que representa uma solução efetiva para resolver o problema das transações duplicadas (double-spent) numa rede de pares (peer-to-peer ou p2p). No jargão do bitcoin, a blockchain não é mais que um ledger (um ‘livro-razão’) que guarda o registo de todas as transações ocorridas na rede. Esta tecnologia apareceu de facto na altura certa. Ela permite a implementação de sistemas descentralizados em redes p2p sem a necessidade de uma trusted third party como forma de validar transações ou ações num dado ecossistema. Ao invés disso, cada par na rede possui uma cópia do livro-razão onde consegue efetuar todas as validações necessárias sem a necessidade eminente desse terceiro nó de comunicação onde estaria localizado unicamente o “livro-razão”.

Por exemplo, quando o Bob decide efetuar uma transação de 50 BTCs (bitcoins) para a Alice, a transação fica registada na blockchain sem a necessidade de ter que passar por um “banco-central” validador. A transação é automaticamente auditada na rede por todos os nós que a compõem.

Essas transações são armazenadas na cadeia de  blocos. Esses blocos têm a seguinte estrutura [2].

Bitcoin is a digital cryptocurrency that had a large impact when it was released onto the Internet. All the concept and technology around it has been also subject of research in recent years. The acceptance of this cryptocurrency was enormous and that is observed in their growing market value [1].

Blockchain comprises the core of the bitcoin, which represents an effective solution to solve the problem of double-spent transactions in a peer-to-peer or p2p network. In the bitcoin jargon, blockchain is nothing more than a ledger that keeps track of all transactions that occur on the network. This technology appeared at the right time. It allows the implementation of decentralized systems in p2p networks without the need for a trusted third party as a way to validate transactions or all the actions in a given ecosystem. Instead, each pair in the network has a copy of the ledger and it (or they) can perform all necessary validations without a third node of communication (where the “ledger” would be located).

For example, when Bob sends a transaction of 50 BTCs (bitcoins) to Alice, the transaction will be registered in a block, without passing through the “central bank” validator. It is automatically audited on the network by all nodes that compose the system.

These transactions are stored in the blockchain. The blocks have the following structure [2].

 

FieldPurposeSize (Bytes)
VersionBlock version number4
hashPrevBlock256-bit hash of the previous block header (in little endian format)32
hashMerkleRoot256-bit hash based on all the transactions in the block32
TimeCurrent timestamp4
BitsCurrent target in compact format4
Nonce32-bit number (starts at 0)4

 

O campo hashPrevBlock guarda a hash do bloco anterior na notação little-endian (invertido). É um registo de 32 bytes que armazena uma hash de 256 bits. O campo hashMerlkeRoot é também um registo de 32 bytes, e armazena uma hash que representa a raiz da Merkle Tree (abordada a seguir). A Merkle Tree é uma árvore que guarda todas as hashes das transações do bloco. O time representa o timestamp de quando o bloco é criado. O campo bits representa a dificuldade do bloco, e por fim, o nonce é um valor incremental que permite aos nós da rede validar um novo bloco candidato para que ele seja adicionado à cadeia. Em seguida é apresentada uma figura que pretende ilustrar como os blocos estão ligados na blockchain.

The hashPrevBlock field stores the hash of the previous block in the little-endian notation (inverted). It is a 32-byte registry that stores a 256-bit hash. The hashMerlkeRoot field is also a 32-byte registry, and it stores a hash that represents the root of the Merkle Tree (discussed below). The Merkle Tree is a tree that holds all the transaction hashes of the block. The time represents the timestamp of the block. The field bits represents the block difficulty, and finally, the nonce is an incremental value added that allows validating a new candidate block. Next, a figure is presented to illustrate how the blocks are connected in the blockchain.

 

blockchain blocks

 

No Block 2, nomeadamente no campo hashPrevBlock está armazenada a hash do bloco anterior e que permite também estabelecer ligação com os blocos adjacentes. Uma hash identificadora de um bloco é a hash do cabeçalho do bloco, nomeadamente dos campos já citados: Hash(Version, hashPrevBlock, hashMerkleRoot, Time, Bits e Nonce). Essa hash foi a primeira a ser gerada por um par na rede e que satisfazia o desafio colocado pela rede.

In the Block 2, hashPrevBlock field keeps the previous block hash and also allows to connect to the adjacent blocks. The hash of a block is the hash of the block header, namely the hash of the fields previously cited: Hash (Version, hashPrevBlock, hashMerkleRoot, Time, Bits and Nonce). It was the first to be generated by a network node that won the challenge placed by the network.

Merlke Tree

A discussão durante o resto do artigo centra-se no campo hashMerkleRoot do cabeçalho do bloco, que representa a raiz de uma árvore onde são armazenadas as hashes de todas as transações realizadas e associadas ao bloco (ver imagem a seguir), permitindo assim, assegurar também a integridade de todas as transações na cadeia.

The discussion during the rest of the article focuses on the hashMerkleRoot field of the block header, which represents the root of a tree where the hashes of all the transactions performed and associated with the block are stored (see image below). This ensures the integrity of all transactions in the blockchain.

 

blockchain blocks

 

As Merlke Tree’s foram inventadas em 1979 por Ralph Merkle. O objetivo inicial da sua criação foi introduzido junto das assinaturas de Lamport de tempo-único. Elas representam uma estrutura de dados que contém uma árvore de informações resumidas sobre um pedaço de dados ainda maior, por exemplo: um arquivo, e servem para validar o conteúdo de um arquivo. Elas são usadas para verificar a integridade dos registos, manuseados e transferidos entre computadores ou redes de computadores. Atualmente, o principal uso de Merkle Tree’s é para garantir que blocos de dados recebidos de outros pares em uma rede p2p são recebidos intactos e inalterados, e até mesmo para verificar se os outros pares não mentem e enviam blocos falsos.

Uma vez que a transparência é uma das propriedades desta tecnologia, é possível consultar toda a informação referente a blocos e transações de toda a rede desde o seu início (em 3 de janeiro de 2009 às 06:15:05 PM – ver primeiro block -denominado como bloco génesis: -o bloco de altura 0). Em seguida, vamos analisar o bloco com altura 100000 na blockchain, criado a 29 de dezembro de 2010 e identificado com a hash 000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506.

A URL é o seguinte:

https://blockchain.info/block/000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506

The Merkle Tree’s were invented in 1979 by Ralph Merkle. Their initial goal was introduced upon the Lamport signatures. They represent a data structure that contains the information about an even larger piece of data, for example, a file, and serve to validate the contents of a file. They are used to verify the integrity of records, handled and transferred between computers or computer networks. Currently, the main use of Merkle Tree’s is to ensure that blocks of data received from other peers in a p2p network are received intact and unchanged and even to verify that the other pairs do not lie and send fake blocks.

Transparency is one of the properties of this technology. Because of this, it is possible to access all the information regarding blocks and transactions of the entire network since its inception (on January 3, 2009, at 06:15:05 PM – see the first block – denominated as genesis block: -block of height 0). Next, let’s look at the block with height 100000 in the blockchain, created on December 29, 2010 and identified with the hash 000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506.

URL: https://blockchain.info/block/000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506

 

block 100000

 

O valor de hash referente à raiz da Merkle Tree é dado pelo seguinte valor de hash: 

f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766

Este valor é denominado por Merkle Root, e como já foi dito acima, identifica a raiz da árvore. Todas as transações na rede são identificadas através de uma hash. A raiz da árvore é formada pela hash da hash de todas as transações em forma de pirâmide. Apenas a Merkle Root é incluída no header do bloco, o que permite verificar a integridade de todas as transações aceites na blockchain. Qualquer alteração ou tentativa de alterar de uma transação anterior irá ser invalidada e rejeitada pela rede.

A seguir fica uma Merkle Tree [4], que tem como Merkle Root (HABCD) de uma lista de transações: Tx A, Tx B, Tx C e Tx D.

The hash for the root of the Merkle Tree is given by the following value:

f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766

This value is called Merkle Root, and as mentioned above, it identifies the root of the tree. All transactions on the network are identified through a hash. The root of the tree is formed by the hash of the hashes of all transactions. Only Merkle Root is included in the block header, which allows checking the integrity of all transactions accepted and included in the blockchain. Any change or attempt to change from a previous transaction will be invalidated and rejected by the network.

Next,  a Merkle Tree [4] is presented, which has as Merkle Root (HABCD) and a list of transactions: Tx A, Tx B, Tx C and Tx D.

 

 

merkle tree

 

As folhas são os quatro nós de baixo (Tx A, Tx B, Tx C e Tx D). Cada nó possui uma hash, a hash da transação Hash (Tx A)”. O nó superior concatena as hashes das folhas Hash(H(A) + H (B))”. O mesmo processo é aplicado as restantes folhas. A última concatenação de todas as hashes é definida como a raiz da árvore. Este algoritmo tem a forma de uma pirâmide de registos e é a maneira como é verificada a integridade dos blocos e das transações da blockchain.

Usando o exemplo do bloco com altura 100000 da rede bitcoin, as respetivas hashes da árvore são as seguintes:

The leaves are the four bottom nodes (Tx A, Tx B, Tx C and Tx D). Each node has a hash, the hash of the “Hash (Tx A)” transaction. The top node concatenates the hashes of the “Hash (H (A) + H (B))”. The same process is applied to the remaining leaves. The last concatenation of all hashes is defined as the root of the tree. This algorithm takes the form of a pyramid of records and is the way to validate the blocks integrity and associated transactions.

The hashes of the 100000 block of bitoin network are the following:

 

Tx A8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87

Tx Bfff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4

Tx C6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4

Tx De9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d

 

A disposição da árvore é então semelhante ao esquema explicado acima. Foi também verificado que a Merlke Root do bloco é dada pela seguinte hash:

f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766.

A seguir, vamos construir um pequeno programa na linguagem Python de forma a validar a implementação de Merlke Trees para o bloco de altura 100000 da rede, e verificar ainda se o resultado obtido, a Merkle Root, é exatamente o mesmo valor registado nesse bloco.

The arrangement of the tree is similar to the scheme explained above. It was also verified that the Merlke Root of the block is given by the following hash:

f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766.

Next, we will develop a program in the Python language in order to validate the Merlke Trees implementation for the 100000 height block of the bitcoin network, and also verify if the result obtained is exactly the same value stored in that block.

Implementação em Python / Laboratory (Python)

Para começar, é necessário adicionar a lista de transações. Ela contém as quatro transações do bloco 100000 da rede bitcoin.

To begin, you must add the list of transactions. It contains four transactions (from 100000 block of the bitcoin network).

transactions = [
"8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
"fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
"6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
"e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d",
]

 

Para implementar o algoritmo é necessário fazer o seguinte:

  1. Implementar uma função recursiva para construir a Merkle Tree (def MerkleTree(transactions)).
  2. A lista de transações, isto é, o vetor onde estão guardadas as transações. E será iterado com um salto de índice dois. Isto deve-se ao facto de cada ramo ter duas folhas associadas.
  3. Em seguida, é concatenado a hash da primeira transação com o da segunda e assim sucessivamente. De notar que, é necessário converter as hashes entre big-endian e little-endian. Esta é uma das muitas particularidade da tecnologia.
  4. No final a função retorna o somatório de duas hashes, e essa nova hash é adicionado à árvore “hash(hash(TxA) + hash(TxB)), e por aí em diante.

To implement this algorithm you need:

  1. Develop a recursive function to build the Merkle Tree (def MerkleTree (transactions)).
  2. The vector with all transactions. It is iterated with a jump = 2. Because is needed computing two hashes at the same time.
  3. Next, the hashes (hash of the first and second leaves) are concatenated. The same process for the other. Notice that is too necessary converting the hash values between big and little-endian. This is one of the many particularities of technology.
  4. In the end, the function returns the sum of two hashes. Next, these are added in the tree, and so on (“hash(hash(TxA) + hash(TxB))”).

 

Função recursiva / Recursive function – Merkle Tree

def MerkleTree(transactions):
   global number_of_rounds
   number_of_rounds = number_of_rounds + 1
   if len(transactions) == 1:
       print("\nMerkle Root")
       return transactions[0]
   newTransactionList = []
   #Processing pairs with jump 2
   for i in range(0, len(transactions)-1, 2):
       newTransactionList.append(sum_hash(transactions[i], transactions[i+1]))
   if len(transactions) % 2 == 1: # odd, hash last item twice
       newTransactionList.append(sum_hash(transactions[-1], transactions[-1]))
   print "Round [", number_of_rounds, "] - Branches [", len(transactions), "]"
   return MerkleTree(newTransactionList)

Função para efetuar a soma da hash de duas folhas da Merkle Tree / Function to perform the sum of two hashes in the Merkle Tree

def sum_hash(hash1, hash2):
   #Reverse inputs before and after hashing (big-endian / little-endian)
   h1 = hash1.decode('hex')[::-1]
   h2 = hash2.decode('hex')[::-1]
   h = hashlib.sha256(hashlib.sha256(h1+h2).digest()).digest()
   return h[::-1].encode('hex')

 

Trecho de código completo / Full source-code 

#!/bin/python
import hashlib

number_of_rounds = 0

def MerkleTree(transactions):
   global number_of_rounds
   number_of_rounds = number_of_rounds + 1
   if len(transactions) == 1:
       print("\nMerkle Root")
       return transactions[0]
   newTransactionList = []
   #Processing pairs with jump 2
   for i in range(0, len(transactions)-1, 2):
       newTransactionList.append(sum_hash(transactions[i], transactions[i+1]))
   if len(transactions) % 2 == 1: # odd, hash last item twice
       newTransactionList.append(sum_hash(transactions[-1], transactions[-1]))
   print "Round [", number_of_rounds, "] - Branches [", len(transactions), "]"
   return MerkleTree(newTransactionList)

def sum_hash(hash1, hash2):
   #Reverse inputs before and after hashing (big-endian / little-endian)
   h1 = hash1.decode('hex')[::-1]
   h2 = hash2.decode('hex')[::-1]
   h = hashlib.sha256(hashlib.sha256(h1+h2).digest()).digest()
   return h[::-1].encode('hex')

transactions = [
 "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
 "fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
 "6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
 "e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d",
]

print(MerkleTree(transactions))

 

No final da execução do script o output deve ser exatamente o seguinte para a lista de transações indicadas:

The output should be the next for the transactions mencioned previously:

 

Round [ 1 ] – Branches [ 4 ]

Round [ 2 ] – Branches [ 2 ]

Merkle Root

f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766

 

No primeiro round, existiam 4 transações para adicionar a Merkle Tree ainda vazia. No segundo round, já só existiam dois. Em seguida, a função recursiva efetuou a última soma de hashes e retornou o valor da sua raiz, nomeadamente a Merkle Root. O esquema abaixo ajuda a perceber esta breve explicação.

In the first round, 4 transactions were added in the Merkle Tree. In the second there are two hashes. Next, the sum of this two hashes was performed and a new hash was obtained. This hash is designated by Merkle Root. The following schema helps to understand the explained process.

 

merkle tree final

 

Como foi possível verificar, o resultado obtido através da implementação de Merkle Tree’s aqui explicada é precisamente a mesma implementação (com algumas alterações) daquela existente na rede bitcoin e que permite guardar o registo das hashess das transações em cada bloco da cadeia. A implementação deste tipo de estrutura em árvore torna-se bastante útil quando é pretendido validar a integridade de um grande conjunto de dados de forma estruturada.

As you see, the results obtained through this implementation is the same of the bitcoin network (without a few details) and it also allows to store the hashes of all transactions of a block in an efficient manner. This kind of implementation (in a tree form) is used when it is intended to validate the integrity of a large set of data in a structured way.

 

Referências / References

[1] https://blockchain.info
[2] https://en.bitcoin.it/wiki/Block_hashing_algorithm
[3] https://pt.wikipedia.org/wiki/%C3%81rvores_de_Merkle
[4] http://chimera.labs.oreilly.com/books/1234000001802/ch07.html#merkle_trees