Implementation of Merkle Tree used in Validation and WhiteListing, using Go (later done in Solidity for prod usage)

merkle.go

package main

import "crypto/sha256"

type Node struct {
	Left, Right *Node
	Hash        []byte
	IsLeaf      bool
}

func Hash(data []byte) []byte {
	hasher := sha256.New()
	hasher.Write(data)
	return hasher.Sum(nil)
}

func BuildTree(data []string) *Node {
	var nodes []*Node

	// Convert data to leaf nodes.
	for _, datum := range data {
		node := Node{
			Hash:   Hash([]byte(datum)),
			IsLeaf: true,
		}

		nodes = append(nodes, &node)
	}

	// Iteratively combine the nodes until there is only one root left.
	for len(nodes) > 1 {
		var newLevel []*Node

		for i := 0; i < len(nodes); i += 2 {
			// Handle odd number of nodes.
			if i+1 == len(nodes) {
				newLevel = append(newLevel, nodes[i])
				break
			}

			combinedHash := Hash(append(nodes[i].Hash, nodes[i+1].Hash...))
			parentNode := Node{
				Left:  nodes[i],
				Right: nodes[i+1],
				Hash:  combinedHash,
			}

			newLevel = append(newLevel, &parentNode)
		}

		nodes = newLevel
	}

	return nodes[0] // Root of the tree.
}

func GetProof(root *Node, data string) []*Node {
	var proof []*Node
	dataHash := Hash([]byte(data))

	var find func(*Node) bool
	find = func(node *Node) bool {
		if node.IsLeaf {
			return compareBytes(node.Hash, dataHash)
		}

		if node.Left != nil && find(node.Left) {
			if node.Right != nil { // Add sibling to proof if this is not a leaf
				proof = append(proof, node.Right)
			}
			return true
		} else if node.Right != nil && find(node.Right) {
			proof = append(proof, node.Left)
			return true
		}

		return false
	}

	find(root)
	return proof
}

func VerifyProof(data string, rootHash []byte, proof []*Node) bool {
	hash := Hash([]byte(data))
	for _, node := range proof {
		// Determine the order based on the proof structure
		hash = Hash(append(hash, node.Hash...))
	}

	return compareBytes(hash, rootHash)
}

func compareBytes(a, b []byte) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func main() {
	data := []string{"Data1", "Data2", "Data3", "Data4"}
	root := BuildTree(data)
	fmt.Println("Merkle Tree Root Hash:", hex.EncodeToString(root.Hash))

	for _, datum := range data {
		proof := GetProof(root, datum)
		verified := VerifyProof(datum, root.Hash, proof)
		fmt.Printf("Proof verified for %s: %t\n", datum, verified)
	}
}