MT-20200223 - Blockchain Code Snippets

Problem Statement

You are tasked with implementing a simple Merkle Tree for a list of transaction hashes in a blockchain system. A Merkle Tree is a binary tree in which every leaf node is labeled with the hash of a data block and every non-leaf node is labeled with the cryptographic hash of the labels of its child nodes. Your task includes:
1. Implementing a function to calculate the SHA-256 hash of a given string.
2. Building the Merkle Tree from a list of transaction hashes, ensuring that if the number of transactions is not even, you duplicate the last hash to balance the tree.
3. Writing a function to verify a transaction's inclusion in the block using its hash and the path (sibling hashes) up to the root.
The goal is to demonstrate how Merkle Trees can be used to efficiently verify that a set of transactions are part of the block without needing to store all the data.

Concepts

Hash Functions
Data Integrity
Efficient Data Verification

Constraints

Use SHA-256 as the hashing function
Handle an empty list of transaction hashes by returning a specific null hash (e.g., '0')

Security Notes

Ensure that the implementation is resistant against trivial attacks like hash collisions, even though SHA-256 is considered secure for this purpose.
Be aware that real-world applications require additional security measures beyond what is covered in this exercise.

Solutions

Csharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;

public class MerkleTree
{
    // Function to calculate the SHA-256 hash of a given string.
    public static string CalculateHash(string data)
    {
        using (SHA256 sha256 = SHA256.Create())
        {
            byte[] bytes = sha256.ComputeHash(Encoding.UTF8.GetBytes(data));
            StringBuilder builder = new StringBuilder();
            foreach (byte b in bytes)
            {
                builder.Append(b.ToString("x2"));
            }
            return builder.ToString();
        }
    }

    // Function to build the Merkle Tree from a list of transaction hashes.
    public static string BuildMerkleTree(List<string> transactions)
    {
        if (transactions == null || transactions.Count == 0)
        {
            return "0"; // Return a specific null hash for an empty list
        }

        List<string> currentLevel = new List<string>(transactions);
        while (currentLevel.Count > 1)
        {
            if (currentLevel.Count % 2 != 0)
            {
                currentLevel.Add(currentLevel.Last()); // Duplicate the last hash to balance the tree
            }

            List<string> nextLevel = new List<string>();
            for (int i = 0; i < currentLevel.Count; i += 2)
            {
                string combinedHash = CalculateHash(currentLevel[i] + currentLevel[i + 1]);
                nextLevel.Add(combinedHash);
            }

            currentLevel = nextLevel;
        }

        return currentLevel[0]; // Root hash of the Merkle Tree
    }

    // Function to verify a transaction's inclusion in the block.
    public static bool VerifyTransaction(string transactionHash, List<string> path, string root)
    {
        string currentNode = transactionHash;
        foreach (string siblingHash in path)
        {
            if (String.Compare(currentNode, siblingHash) < 0)
            {
                currentNode = CalculateHash(currentNode + siblingHash);
            }
            else
            {
                currentNode = CalculateHash(siblingHash + currentNode);
            }
        }

        return currentNode == root; // Check if the calculated hash matches the root hash
    }
}

This C# solution implements a simple Merkle Tree for verifying transaction hashes in a blockchain system. The code consists of three main functions:

1. `CalculateHash`: This function computes the SHA-256 hash of a given string using the .NET Cryptography library. It converts the input data into bytes, computes its hash, and returns it as a hexadecimal string.

2. `BuildMerkleTree`: This function constructs a Merkle Tree from a list of transaction hashes. If the number of transactions is not even, it duplicates the last hash to ensure that every level of the tree has an even number of nodes. The process continues until there's only one node left at the root, which represents the combined hash of all transactions.

3. `VerifyTransaction`: This function checks if a specific transaction hash is part of a block by using its path (sibling hashes) up to the Merkle Tree's root. It iteratively combines each transaction hash with its sibling hash, moving upwards through the tree until it reaches the root. If the calculated root matches the provided root, the transaction is verified as part of the block.

This implementation ensures data integrity and efficient verification without requiring all transaction details to be stored, adhering to the principles of blockchain technology.