Merkle Tree Implementation and Benchmark

Project Overview

This repository contains an individual project for the Blockchains and Cryptocurrencies (Blockchains e Criptomoedas) course at the Universidade da Beira Interior.

The primary goal was to modify a supplied Java implementation of a Merkle Tree to add new features, including visual tree printing, proof generation, proof verification, and a performance benchmark comparing Merkle verification against a brute-force search.

This was an Individual Assignment.

Assignment Requirements

The assignment specified the following tasks:

• (a) Use different Hash Functions, with the specific function (e.g., MurmurHash2, SHA-256) being selectable via a startup parameter.
• (b) Generate $2^n$ random, distinct transactions (e.g., $2^{10}$) instead of a small, fixed number.
• (c) Improve the console output of the Merkle Tree to make it visually "look like a tree".
• (d) Implement a function that, given a specific transaction (leaf), creates and outputs its Merkle proof.
• (e) Create a function that, given a transaction, its proof, and the Merkle root, verifies whether the proof is valid.
• (f) For a large number of transactions (e.g., $2^{10}$ or $2^{20}$), benchmark the time required to validate a transaction using the Merkle proof. Compare this time to a brute-force search (linear scan) and calculate the speedup.

Implementation Details

This project successfully implements all the above requirements in Java.

• Selectable Hash Functions (a): The Test.java class accepts a command-line argument (args[0]) to set the hashAlgorithm, which is then passed to the DigestUtils class.
• Random Transaction Generation (b): A Utils.genRandomTransactions(int count) function was created. It uses UUID.randomUUID() to generate an array of unique, random strings to serve as transaction IDs.
• Visual Tree Printing (c): The MerkleTree.printTree() method was implemented using a Breadth-First Search (BFS) approach with a Queue. It calculates the correct padding and spacing at each level to print a formatted, pyramid-like tree structure to the console.
• Merkle Proof Generation (d): The getMerkleProofForTrans(String tx) and getMerkleProofByIndex(int index) methods were implemented. This logic re-simulates the tree's bottom-up construction, collecting the necessary "sibling" hashes at each level to build the proof list.
• Proof Verification (e): The static boolean verifyMerkleProof(...) method takes the original transaction, its proof, and the known root hash. It re-calculates the root by hashing the leaf and iteratively combining it with the sibling hashes from the proof, ensuring the same concatenation order (Utils.compare) is used. It returns true if the calculated root matches the provided root.
• Performance Benchmark (f): A separate Benchmark.java class was created. This class measures the time to run the verify (Merkle) and brute (linear search) methods over a large number of repetitions (R) for a given number of transactions (N). It then prints the total times and the resulting speedup.

Benchmark Results & Conclusion

The benchmark (requirement f) demonstrates the core value of Merkle Trees. The verify method has a logarithmic complexity (O(log N)), as its time depends on the height of the tree (the proof size). The brute search has a linear complexity (O(N)), as its time depends on the number of transactions.

The results from the benchmark clearly confirm this:

N (Transactions)	verify Time (ms)	brute Time (ms)	Speedup (brute / verify)
$2^{10}$ (1,024)	0.289	1.425	4.94x
$2^{14}$ (16,384)	0.189	3.586	18.93x
$2^{18}$ (262,144)	0.494	12.638	25.60x
$2^{20}$ (1,048,576)	0.199	94.762	477.00x

As shown, the verify time remains nearly constant, while the brute search time grows linearly. At over one million transactions, the Merkle proof verification is ~477 times faster than a simple linear scan. This proves that Merkle Trees are a highly efficient and scalable solution for verifying data inclusion, which is essential for systems like blockchains.

How to Run

The project is built using Maven.

Run the main test (demonstrates a-e):

mvn exec:java -Dexec.mainClass="ubi.Test"

Syntax:

mvn exec:java -Dexec.mainClass="main.java.ubi.Benchmark" -Dexec.args="[N] [R]"

Example for N=2^20 (1,048,576) transactions and R=50 repetitions:

mvn exec:java -Dexec.mainClass="main.java.ubi.Benchmark" -Dexec.args="$((1<<20)) 50"