Operating System:
Big library: https://golang.org/pkg/math/big/Bytes library: https://golang.org/pkg/bytes/A full bitcoin database requires about 200 gigs of diskspace. In the last tutorial, we talked about how we can make it easier to traverse this data structure with the UTXO set, but there is another optimization mechanism that we can use for our transaction system. This optimization mechanism is called a Simplified Payment Verification (SPV). The SPV is a light version of the blockchain that relies on a full node to verify and sign blocks and transactions. For this SPV to work, we need a way of searching transactions without having to download entire blocks. This is where the idea of a Merkle Tree comes in.
Merkle Trees are basically large hash trees which get saved in the headers of a block. They are also used when the block is mined by the Proof of Work Algorithm. They are a unique representation of a block's transactions and just by reading the merkle tree's root hash, the SPV client should be able to know which transactions are in a block.
The image above is a visual representation of the Merkle Tree. The tree is made up of different leaf structures each which contains a hash. The bottom leaves contain the Sha256 hash of the transaction data. The Node above those leaves takes the two transactions connected to it and concatenates them together. Then another Sha256 Algorithm is run on this new value. This process of concatenation and hashing is repeated until there is a single hash which is the Merkle Root of the tree.
Simplified Payment Verification is the method that is used to verify that transactions in a block without downloading the entire block. This is done by downloading just the header of the block in the chain which contains the Merkle Root. Through the SPV nodes, the SPV client can check to see if a transaction has been verified by a set of miners.
In our code, the Merkle Tree is defined by way of two values, a Merkle Node reference and a slice of bytes which represents the data. The tree recursively references other Merkle Nodes until it becomes a one to one representation of the original serialized transactions. If there is an odd number of transactions in the Block, the last transaction is duplicated and then passed up the tree.
The Source Code for this video may be found here: https://github.com/tensor-programming/golang-blockchain/tree/part_8