Lab 3 Details for MPCS 56600

Each lab will consist of a small problem and details of how to proceed. Each lab is intended to give every student hands-on experience with the core concepts and technologies covered during the course.  A student may concentrate, as a team member, on one technology over another for the final project, but labs are designed to give each and every student exposure to all the technologies that come into play.  You need to submit labs to the TAs for grading--see submission instructions below.  Generally, unless otherwise specified, you will have one week to complete each assigned lab.

See the syllabus for information on grading.  Turning in lab assignments on time is required, without exception, and all late deliveries will be penalized, regardless of cause.  Submit your assignments to the subversion repository according to the directions on the syllabus page.

You may write these solutions in any programming language of your choice.  Our suggestion is now is not the time to learn a new programming language along with the concepts themselves.  So our suggestion is to use whatever programming language you  know best.

Lab 3   Due: 5:00 pm, Thursday, July 12, 2018

Problem 1:  Merkle Tree Algorithm laboratory: 

BACKGROUND:

Like all programming problems, learning a new technology is not an exercise in reading but rather an exercise in thinking and typing.  This lab is designed to give you more hands-on experience in some fundamental skills in cryptography.  You will generally find the References section below helpful in addition to the required and recommended reading. 

WHAT YOU NEED TO DO:

STEP 1:

You are to write a program in your programming language of choice (Java/haskell/C#/python/Go/ruby, etc.) that implements a tamper-proof Merkle Tree.  Note these instructions depend on your having successfully set up Testnet and that the blocks have all been downloaded to your Testnet environment locally.  You can verify this quite easily by typing (make sure you have bitd running Testnet):

$ bitc getblock 000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1

and see that you get a dump of that block (as opposed to an error).

Visit https://live.blockcypher.com/btc-testnet/block/000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1/ and obtain the transaction ids for that particular block.  There are 14 Transactions in that block, and they happen to be the same transactions we discussed in class when reviewing Merkle Trees.  You can also obtain the transactions by clicking on the "</> API Call" button (see the image below) and selecting and copying the transactions (just the strings of transaction IDs in the txids[] list!) and saving them to a file.

Note you can just as easily copy the Transaction IDs from the results from the getblock call you made at the command line (above) to verify your Testnet chain data. 

Once you have the transactions, code your program such that it creates a valid Merkle Tree that hashes to the Merkle Root in the above image, namely:  "a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef" (note this root is also in the API Call dump that you pulled the transactions from above).  Make sure you have read Chapter 9, "The Blockchain", in Antonopolous.  See the example merkle.cpp source file (~mark/pub/56600/src.lecture/lecture.3/merklebuilder) for an example of the algorithm to produce the tree. 

You can compile the file with the following command (you will need the libbitcoin core source installed):

g++ -o merkle merkle.cpp -std=c++11 $(pkg-config --cflags --libs libbitcoin)

Don't forget the -std=c++11.  If you do want to compile this, you will likely need to compile libbitcoin from source. 

At each stage of the hashing process, print out your progress, similar to this output (note this output is actual, you may use it to prove your code's solution at any tree depth).

You are free to design your program in any way you see fit as long as the functions and/or classes produce the correct Merkle Root, and the code you submit is not merkle.cpp.  Note you will have to mutz with big endian/little endian transformations along the way to get to the actual Merkle Root for this block, and we discussed this in the lecture when we worked through the block.hashing.py example program.  In some languages (Ruby, Python), this will essentially involve reversing the binary strings before and after hashing.  See the References section below and look through the example program block.hashing.py for an example on how to do this (in python).  Note that block.hashing.py relies on pybitcointools (https://github.com/vbuterin/pybitcointools) which you will need to install if you want to actually run the python code.  For pybitcointools, you will need to revert to git revision aeb0a2bbb8bbfe421432d776c649650eaeb882a5.  You can do this after downloading pybitcointools by changing into the pybitcointools subdirectory and typing:

git log | head

You should see the previous commit at aeb0a2bbb8bbfe421432d776c649650eaeb882a5.  That is the one you want.  Simply run:

git checkout aeb0a2bbb8bbfe421432d776c649650eaeb882a5

and build as normal.

STEP 2:

Once you have a functioning Merkle Tree solution, you are to write a Merkle Path proof function that takes in a new list (or dictionary...see below) as a parameter.  We discussed proving in the lecture.  See especially pages 203-204 of Antonopolous.  This new list will include ONLY (the minimal set of) those Transaction IDs and/or parental Transaction Hashes that are necessary to prove membership in the Merkle Tree for leaf Transaction ID cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50.  First, determine what Transaction IDs will be necessary to minimally validate the transaction (usually a sibling leaf node plus sibling parents).  Then, identify which parent Hashes must be provided to enable additional hashing as we validate up the tree to the root, and which parent Hashes you do not need that you can calculate on your way up to the Merkle root.  Remember,  you are trying to provide a minimalist set of hashes to get to the Merkle root.

We will leave it to you to come up with some method of distinguishing the depth level of your list or dictionary, so you will know at what parental depth a given hash is.  If you use a dictionary, the key could be the hash and the "value" could be the depth...just one of many possible solutions.

References:

You may find the following references helpful (in addition to the links from previous labs):

Bitcoin.org on Merkle Trees
Another Wiki on Merkle Trees
Wikipedia Article on Merkle Trees

On Endianness:
Learn me a bitcoin discussion
Bitcoin Wiki discussion
Bitcoin Developer discussion
Github discussion
Another description

Submitting:

Use the folder named "lab3" in your Subversion repository. See the syllabus for more info about submission using Subversion. Upload your Lab 3 code and any supporting materials to the repo. Please include a README text file to explain what parts of the work you are submitting, where the different parts of the work are located and please provide a little info on how to compile and run your code.