Building a Blockchain with Go - Part 8 - The Merkle Tree

Repository

https://github.com/golang/go

What Will I Learn?

• You will learn about Merkle Trees
• You will learn how to use a Merkle tree to optimize Transactions
• You will learn about the Simplified Payment Verification system
• You will learn about Recursive types in Go
• You will learn how to add Coinbase transactions to all blocks
• You will learn how to verify Coinbase Transactions

Requirements

System Requirements:

Operating System:

• FreeBSD 10.3 or later
• Linux 2.6.23 or later with glibc
• macOS 10.10 or later
• Windows 7, Server 2008R2 or later

Required Knowledge

• A little understanding of the Go programming language
• Go installed on your computer
• A text editor or IDE like Gogland (VS Code used)

Resources for Go and this Project:

• Awesome Go Github: https://github.com/avelino/awesome-go
• Golang Installation Page: https://golang.org/dl/
• Golang Home Page: https://golang.org/
• Golang Documentation Page: https://golang.org/doc/
• Documentation about the Big library: https://golang.org/pkg/math/big/
• Documentation about the Bytes library: https://golang.org/pkg/bytes/

• Information about Elliptic Curves: http://mathworld.wolfram.com/EllipticCurve.html
• Information about Base58: https://en.bitcoinwiki.org/wiki/Base58
• BadgerDB Documentation: https://godoc.org/github.com/dgraph-io/badger
• MermaidJS: https://mermaidjs.github.io/

Credits/Sources:

• Go Logo: https://golang.org/

Difficulty

• Advanced

Description

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.

Describing Transactions With Trees

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

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

Video Tutorial

Curriculum

• Building a Blockchain with Go - Go Modules and a Basic Blockchain - Part 1
• Building a Blockchain with Go - Refactor and Proof of Work - Part 2
• Building a Blockchain with Go - Persistence and Command Line - Part 3
• Building a Blockchain with Go - Adding Primitive Transactions - Part 4
• Building a Blockchain with Go - Part 5 - Building a Basic Wallet Module
• Building a Blockchain with Go - Part 6 - Adding Digital Signatures
• Building a Blockchain with Go - Part 7 - The UTXO Set and BadgerDB Iterators

Proof of Work Done

https://github.com/tensor-programming