Understanding bitcoin merkle tree construction at code level

[Bitcoin]

Understanding bitcoin merkle tree construction at code level

I have a high level understanding of how merkle trees are constructed for a Bitcoin block, but I am interested in building a little CLI tool in golang that actually takes a list of transactions for a block and reconstructs the merkle tree. I am doing this just for my own educational purposes. As I am going through this process I am realizing some details about the merkle tree construction which I do not understand.

I have the following code to construct the merkle tree from a list of transaction hashes

func buildTree(leafHashes []string, comboFn CombineHashFn) (*node, error) {
    if len(leafHashes) == 0 {
        return nil, errors.New("empty list of leaf node hashes provided, cannot construct tree")
    }
    currentLayer := make([]*node, len(leafHashes), len(leafHashes))
    for i := 0; i < len(leafHashes); i++ {
        currentLayer[i] = &node{
            hash:      leafHashes[i],
            left:      nil,
            right:     nil,
            duplicate: false,
        }
    }

    for len(currentLayer) > 1 {
        if len(currentLayer)%2 == 1 {
            lastNode := currentLayer[len(currentLayer)-1]
            duplicateNode := &node{
                hash:      lastNode.hash,
                left:      nil,
                right:     nil,
                duplicate: true,
            }
            currentLayer = append(currentLayer, duplicateNode)
        }

        nextLayerLen := len(currentLayer) / 2
        nextLayer := make([]*node, nextLayerLen, nextLayerLen)
        for i := 0; i < len(currentLayer); i += 2 {
            nextLayer[i/2] = &node{
                hash:      comboFn(currentLayer[i].hash, currentLayer[i+1].hash),
                left:      currentLayer[i],
                right:     currentLayer[i+1],
                duplicate: false,
            }
        }
        currentLayer = nextLayer
    }

    return currentLayer[0], nil
}

I am passing in a function to combine to node's hashes that looks like

func Sha256CombineHashFn(left string, right string) string {
    return fmt.Sprintf("%x", sha256.Sum256([]byte(left+right)))
}

I suspect my merkle tree logic is correct but my method for combining node's hashes is wrong. Based on some Googling I suspect the following things are wrong

1. I think I should not be representing the hashes as hex encoded strings, but instead should be using byte arrays.


2. I believe I should be doing a "double" hash.

Instead of guessing and checking if I was combining nodes correctly I instead just tried to read the Bitcoin merkle tree code. I found this code. I was hoping reading the code would unblock me, but I am just more confused for a few reasons.

1. It looks like two hashes are not being taken but instead some number of hashes are being taken that are proportional to the number of leaf nodes (reference code)


2. Understanding this line and this method implementation is going over my head. I expected this logic to be very simple, from my understanding all that needs to be done is take two node's hash values, combine them some how and then hash the result. Instead it looks like multiple hashes are being taken, it looks like the 0th index is used twice, and I do not see where hashes are combined.

If I wanted to write a simple function in go with the following function header

func Sha256CombineHashFn(left string, right string) string
// OR
func Sha256CombineHashFn(left []byte, right []byte) []byte

How might I do this to match the Bitcoin logic?

Source: Understanding bitcoin merkle tree construction at code level