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

in #utopian-io6 years ago

golang.jpg

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:

Credits/Sources:

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.

mt.png

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.

merkle.png

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

Proof of Work Done

https://github.com/tensor-programming

Sort:  

Hello @tensor,

Thank you again for making this series of tutorial of building a blockchain with Go. I like your flow chart and the step by step of moving your learners forward from one concept to the next.

I like those large fonts too.

Your contribution has been evaluated according to Utopian policies and guidelines, as well as a predefined set of questions pertaining to the category.

To view those questions and the relevant answers related to your post, click here.


Need help? Write a ticket on https://support.utopian.io/.
Chat with us on Discord.
[utopian-moderator]

Thank you for your review, @rosatravels! Keep up the good work!

Hi, @tensor!

You just got a 6.69% upvote from SteemPlus!
To get higher upvotes, earn more SteemPlus Points (SPP). On your Steemit wallet, check your SPP balance and click on "How to earn SPP?" to find out all the ways to earn.
If you're not using SteemPlus yet, please check our last posts in here to see the many ways in which SteemPlus can improve your Steem experience on Steemit and Busy.

Hi @tensor!

Your post was upvoted by @steem-ua, new Steem dApp, using UserAuthority for algorithmic post curation!
Your post is eligible for our upvote, thanks to our collaboration with @utopian-io!
Feel free to join our @steem-ua Discord server

Hey, @tensor!

Thanks for contributing on Utopian.
We’re already looking forward to your next contribution!

Get higher incentives and support Utopian.io!
Simply set @utopian.pay as a 5% (or higher) payout beneficiary on your contribution post (via SteemPlus or Steeditor).

Want to chat? Join us on Discord https://discord.gg/h52nFrV.

Vote for Utopian Witness!

Thank you for your posts about Golang. 👍

Coin Marketplace

STEEM 0.17
TRX 0.15
JST 0.028
BTC 57527.13
ETH 2375.07
USDT 1.00
SBD 2.42