MT-20200224 - Blockchain Code Snippets

Problem Statement

You are tasked with implementing a simplified Merkle Tree structure in Python. Your implementation should include methods to add data elements, compute the root hash of the tree, and verify if a specific data element exists within the tree given its corresponding proof path.

The Merkle Tree will consist of leaf nodes containing hashes of data blocks and intermediate nodes that are parent nodes of other nodes. The root node is the topmost node in the tree and represents the single hash value summarizing all the data blocks.

Your implementation should handle an arbitrary number of leaves, even when this number is not a power of two, by appropriately padding with empty or zero hashes.

Concepts

hash functions
binary trees
data integrity

Constraints

Use SHA-256 as the hashing function
Ensure the tree handles an odd number of leaves by properly padding
Implement methods to add data, compute root hash, and verify inclusion

Security Notes

Be aware that using a fixed padding scheme can lead to vulnerabilities if not handled correctly
Consider how your implementation might be extended for use in a real-world application like a blockchain

Solutions

Csharp Solution

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

public class MerkleTree {
    private List<string> _leaves;
    private List<List<string>> _tree;

    // Constructor initializes the Merkle Tree with an empty list of leaves and tree levels.
    public MerkleTree() {
        _leaves = new List<string>();
        _tree = new List<List<string>>();
    }

    // Adds a data element to the Merkle Tree by hashing it and storing in the leaves list.
    public void AddData(string data) {
        var hash = ComputeHash(data);
        _leaves.Add(hash);
        BuildTree();
    }

    // Computes SHA-256 hash of a given string.
    private static string ComputeHash(string input) {
        using (SHA256 sha256 = SHA256.Create()) {
            byte[] bytes = sha256.ComputeHash(System.Text.Encoding.UTF8.GetBytes(input));
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < bytes.Length; i++) {
                builder.Append(bytes[i].ToString("x2"));
            }
            return builder.ToString();
        }
    }

    // Builds the Merkle Tree from the leaves list.
    private void BuildTree() {
        _tree.Clear();
        _tree.Add(_leaves);
        List<string> currentLevel = _leaves;
        while (currentLevel.Count > 1) {
            var nextLevel = new List<string>();
            for (int i = 0; i < currentLevel.Count; i += 2) {
                string left = currentLevel[i];
                // Handle odd number of leaves by padding with zero hash.
                string right = i + 1 < currentLevel.Count ? currentLevel[i + 1] : ComputeHash("");
                nextLevel.Add(ComputeHash(left + right));
            }
            _tree.Add(nextLevel);
            currentLevel = nextLevel;
        }
    }

    // Computes and returns the root hash of the Merkle Tree.
    public string GetRootHash() {
        return _tree.Last().First();
    }

    // Verifies if a specific data element exists within the tree given its corresponding proof path.
    public bool VerifyInclusion(string data, List<string> proof) {
        var currentHash = ComputeHash(data);
        foreach (var hash in proof) {
            // Concatenate current hash with proof hash and recompute hash based on order.
            if (String.Compare(currentHash, hash, StringComparison.Ordinal) < 0) {
                currentHash = ComputeHash(currentHash + hash);
            } else {
                currentHash = ComputeHash(hash + currentHash);
            }
        }
        return currentHash == GetRootHash();
    }
}

This C# implementation of a Merkle Tree includes methods to add data elements, compute the root hash of the tree, and verify if a specific data element exists within the tree given its corresponding proof path.
The MerkleTree class maintains a list of leaves (hashed data) and a list of levels in the tree. When adding data, it hashes the input using SHA-256 and adds it to the leaves list. The BuildTree method constructs the tree by iteratively combining pairs of nodes until only one node remains at the root level.
The ComputeHash method is responsible for hashing strings using SHA-256, ensuring cryptographic security. In cases where there's an odd number of leaves, a zero hash (hash of an empty string) is used to pad and maintain tree structure integrity.
GetRootHash returns the topmost node in the tree, representing a single hash value summarizing all data blocks. The VerifyInclusion method takes a piece of data and a proof path, rehashing through the path nodes to check if it leads back to the root hash, thus confirming data inclusion without needing full tree traversal.
This implementation is secure and ready for use in applications that require data integrity verification, such as blockchain systems. However, care should be taken with padding schemes to avoid potential vulnerabilities.