Lab 4 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 4   Due: 3:00 pm, Thursday, February 5, 2026

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 Mainnet and Testnet and that the blocks have all been downloaded to your Mainnet environment locally.  You can verify this quite easily by typing (make sure you have bitd-MAINNET running Mainnet):

$ bitc-MAINNET getblock 0000000000000221b9810493bdd20cf7a94f1a0bebdf1e470358dca521a8d8e6

and see that you get a dump of that block (as opposed to an error).  It should look a lot like this (# confirmations may vary, etc.):

{
  "hash": "0000000000000221b9810493bdd20cf7a94f1a0bebdf1e470358dca521a8d8e6",
  "confirmations": 734058,
  "height": 199956,
  "version": 1,
  "versionHex": "00000001",
  "merkleroot": "2f327045dae1c11601f0c697b0a8829fe00093a234401aad7288bb5899a520da",
  "time": 1348289602,
  "mediantime": 1348288419,
  "nonce": 3464708458,
  "bits": "1a05db8b",
  "target": "00000000000005db8b0000000000000000000000000000000000000000000000",
  "difficulty": 2864140.507810974,
  "chainwork": "00000000000000000000000000000000000000000000001ab8f059c23c15fd4c",
  "nTx": 14,
  "previousblockhash": "000000000000056c6ebf3822a4ebe30a96f1eebcf5dc52fee7533c188102fd43",
  "nextblockhash": "0000000000000037e18ab21acdc632ddb8eeb54ad613da23e49c848c61b83790",
  "strippedsize": 5388,
  "size": 5388,
  "weight": 21552,
  "tx": [
    "770d158dc23c52b152775ca543cb85b757f62b831e3fea86e7672edfb62f9133",
    "7449d01c662ecfcb44554def1ec1cb945e2b4db1c9856d2f943ddb07fc92527a",
    "4a7c4edf7dadb73ebf29091f3d3c71cfe991af34729d417bf8c52d9b7d9f532f",
    "33841e4e8392bf4d2645590c763e277f75f9705a6dc158a7bce06d0736b566d7",
    "0dcea573df86832be09f5752cb158a5603d0bdacfb90de8afc85f9fb3e0bea88",
    "ebffadfccdae539eedc0b1983d6f3c7885545bb5ccccd8dccec013ea8c19cefe",
    "85b55d8e777f41b31bb5e674f61ac268daed3c5529b5c5d699920c3c328d3ace",
    "d96410e960cbdb3e3f0c5cd53865078a4045168f459018ec0ed7b27d6d91b8e9",
    "66489999d1406ca0ee7e198aaa0e004de8f1d06b212ef2879b7f3db948174a99",
    "75565e7fc021d271b2fd1749841c3ce0e266a1b6de913c04240a55bf9f197022",
    "b18efbafb95fc05e40a7c768b2b5aab17024d69d6f00e59746d0355e5122d35e",
    "c3194be01d9b1371b05d225e8020af76762ccd0685f4c0fb35f8fd418a7c6a27",
    "4f939d7c976d2336862fb5dba9674f20b6e5d462afb70aae81d2bd86a1e94640",
    "ac6aea46443b0fdef58cb694cb7654424f40d5b476cec3a17767d709177a779e"
  ]
}

You may copy the transaction ids for that particular block from your output.  There are 14 Transactions in that block (nTx), and they happen to be the same transactions we discussed in class when reviewing Merkle Trees.  You can also obtain the transaction IDs by simply copying the "tx" output from your screen and saving them to a file.

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: 

"2f327045dae1c11601f0c697b0a8829fe00093a234401aad7288bb5899a520da"

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. 

At each stage of the hashing process, print out your progress, (very, very) 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 obtained off the internet or through an AI tool (ChatGPT, DallE2, Base44, Claude, etc.).  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.3.py example program (which tackled block #2 on Mainnet).  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.3.py for an example on how to do this (in python).

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, producing about log2(N) 32-byte hashes that constitute an authentication path.  We discussed proving in the lecture.  See especially pages 255-256 of Antonopolous (3rd. ed.).  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 ebffadfccdae539eedc0b1983d6f3c7885545bb5ccccd8dccec013ea8c19cefe. 

So, you are to prove that the maroon transaction below is in our Merkle Root (2f327045dae1c11601f0c697b0a8829fe00093a234401aad7288bb5899a520da):

"tx": [
    "770d158dc23c52b152775ca543cb85b757f62b831e3fea86e7672edfb62f9133",
    "7449d01c662ecfcb44554def1ec1cb945e2b4db1c9856d2f943ddb07fc92527a",
    "4a7c4edf7dadb73ebf29091f3d3c71cfe991af34729d417bf8c52d9b7d9f532f",
    "33841e4e8392bf4d2645590c763e277f75f9705a6dc158a7bce06d0736b566d7",
    "0dcea573df86832be09f5752cb158a5603d0bdacfb90de8afc85f9fb3e0bea88",
    "ebffadfccdae539eedc0b1983d6f3c7885545bb5ccccd8dccec013ea8c19cefe",
    "85b55d8e777f41b31bb5e674f61ac268daed3c5529b5c5d699920c3c328d3ace",
    "d96410e960cbdb3e3f0c5cd53865078a4045168f459018ec0ed7b27d6d91b8e9",
    "66489999d1406ca0ee7e198aaa0e004de8f1d06b212ef2879b7f3db948174a99",
    "75565e7fc021d271b2fd1749841c3ce0e266a1b6de913c04240a55bf9f197022",
    "b18efbafb95fc05e40a7c768b2b5aab17024d69d6f00e59746d0355e5122d35e",
    "c3194be01d9b1371b05d225e8020af76762ccd0685f4c0fb35f8fd418a7c6a27",
    "4f939d7c976d2336862fb5dba9674f20b6e5d462afb70aae81d2bd86a1e94640",
    "ac6aea46443b0fdef58cb694cb7654424f40d5b476cec3a17767d709177a779e"
  ]

To do this, 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.  You may "hard-code" the hashes which are required to be "given".

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

Submission:

For Labs:

Each student should submit their LabN files and any supporting materials to the repo. Please include a README text file that contains any instructions or additional details for the TAs to assist with grading.

Setup:

When you open the invitation URL in a browser tab, you will have to complete the following steps:

Github may ask you to grant permission for GitHub Classroom to have access to your GitHub account. If you are asked this question, you should say yes and grant access to Github Classroom.

You must click “Accept this assignment” or your repository will not actually be created. Do not skip this step!

If you run into any issues, please ask for help on Ed.