Merkle tree

<?php

declare(strict_types=1);

/**
 * Minimal Merkle tree using SHA-256.
 * For odd number of leaves, the last one is duplicated (Bitcoin convention).
 */
final class MerkleTree
{
    /** @var list<string> Hex-encoded node hashes, bottom level first. */
    private array $levels = [];

    /**
     * @param list<string> $leavesData Raw leaf data (strings or serialized records).
     */
    public function __construct(array $leavesData)
    {
        if ($leavesData === []) {
            throw new \InvalidArgumentException('At least one leaf is required');
        }

        $current = array_map(fn(string $d): string => hash('sha256', $d), $leavesData);
        $this->levels[] = $current;

        while (count($current) > 1) {
            // Duplicate last if odd
            if (count($current) % 2 === 1) {
                $current[] = end($current);
            }

            $next = [];
            for ($i = 0; $i < count($current); $i += 2) {
                $next[] = hash('sha256', $current[$i] . $current[$i + 1]);
            }
            $this->levels[] = $next;
            $current = $next;
        }
    }

    public function root(): string
    {
        return $this->levels[count($this->levels) - 1][0];
    }

    /**
     * Proof of inclusion for leaf at index $leafIndex.
     * @return list<array{hash: string, position: 'left'|'right'}>
     */
    public function proof(int $leafIndex): array
    {
        $proof = [];
        $idx = $leafIndex;

        for ($level = 0; $level < count($this->levels) - 1; $level++) {
            $nodes = $this->levels[$level];
            $siblingIdx = $idx % 2 === 0 ? $idx + 1 : $idx - 1;

            if ($siblingIdx < count($nodes)) {
                $proof[] = [
                    'hash' => $nodes[$siblingIdx],
                    'position' => $idx % 2 === 0 ? 'right' : 'left',
                ];
            }
            $idx = intdiv($idx, 2);
        }

        return $proof;
    }

    /** Verify that leafData is included in a tree with given root using proof. */
    public static function verify(string $leafData, array $proof, string $root): bool
    {
        $h = hash('sha256', $leafData);
        foreach ($proof as $step) {
            $h = $step['position'] === 'right'
                ? hash('sha256', $h . $step['hash'])
                : hash('sha256', $step['hash'] . $h);
        }
        return hash_equals($h, $root);
    }
}

// Example: reconcile two replicas
// $treeA = new MerkleTree($replicaA->rows());
// $treeB = new MerkleTree($replicaB->rows());
// if ($treeA->root() !== $treeB->root()) {
//     // descend level by level to find diverging subtree
// }

package merkle

import (
	"crypto/sha256"
	"encoding/hex"
)

// Tree is a Merkle tree with SHA-256 hashes.
type Tree struct {
	// levels[0] = leaf hashes, levels[len-1] = [root]
	levels [][][]byte
}

// New builds a tree from raw leaf data.
func New(leaves [][]byte) *Tree {
	if len(leaves) == 0 {
		panic("at least one leaf required")
	}

	current := make([][]byte, len(leaves))
	for i, d := range leaves {
		h := sha256.Sum256(d)
		current[i] = h[:]
	}

	t := &Tree{levels: [][][]byte{current}}
	for len(current) > 1 {
		// Duplicate last if odd
		if len(current)%2 == 1 {
			current = append(current, current[len(current)-1])
		}
		next := make([][]byte, 0, len(current)/2)
		for i := 0; i < len(current); i += 2 {
			h := sha256.New()
			h.Write(current[i])
			h.Write(current[i+1])
			next = append(next, h.Sum(nil))
		}
		t.levels = append(t.levels, next)
		current = next
	}
	return t
}

// Root returns the hex-encoded root hash.
func (t *Tree) Root() string {
	return hex.EncodeToString(t.levels[len(t.levels)-1][0])
}

// ProofStep is a single hash+position on a Merkle path.
type ProofStep struct {
	Hash  []byte
	Right bool // true if the sibling is on the right
}

// Proof returns the inclusion proof for the leaf at given index.
func (t *Tree) Proof(leafIdx int) []ProofStep {
	proof := []ProofStep{}
	idx := leafIdx
	for level := 0; level < len(t.levels)-1; level++ {
		nodes := t.levels[level]
		var siblingIdx int
		if idx%2 == 0 {
			siblingIdx = idx + 1
		} else {
			siblingIdx = idx - 1
		}
		if siblingIdx < len(nodes) {
			proof = append(proof, ProofStep{
				Hash:  nodes[siblingIdx],
				Right: idx%2 == 0,
			})
		}
		idx /= 2
	}
	return proof
}

// Verify checks whether leafData belongs to tree with given root.
func Verify(leafData []byte, proof []ProofStep, rootHex string) bool {
	h := sha256.Sum256(leafData)
	cur := h[:]
	for _, step := range proof {
		hh := sha256.New()
		if step.Right {
			hh.Write(cur)
			hh.Write(step.Hash)
		} else {
			hh.Write(step.Hash)
			hh.Write(cur)
		}
		cur = hh.Sum(nil)
	}
	return hex.EncodeToString(cur) == rootHex
}

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

// A single hash+position on a Merkle path.
public readonly record struct ProofStep(byte[] Hash, bool SiblingOnRight);

// Minimal Merkle tree using SHA-256.
// For an odd number of nodes the last one is duplicated (Bitcoin convention).
public sealed class MerkleTree
{
    // _levels[0] = leaf hashes, _levels[^1] = [root]
    private readonly List<List<byte[]>> _levels = [];

    public MerkleTree(IReadOnlyList<byte[]> leaves)
    {
        if (leaves.Count == 0)
        {
            throw new ArgumentException("At least one leaf is required", nameof(leaves));
        }

        var current = new List<byte[]>(leaves.Count);
        foreach (var leaf in leaves)
        {
            current.Add(SHA256.HashData(leaf));
        }
        _levels.Add(current);

        while (current.Count > 1)
        {
            if (current.Count % 2 == 1)
            {
                current.Add(current[^1]);
            }

            var next = new List<byte[]>(current.Count / 2);
            for (var i = 0; i < current.Count; i += 2)
            {
                next.Add(HashPair(current[i], current[i + 1]));
            }

            _levels.Add(next);
            current = next;
        }
    }

    public string Root => Convert.ToHexString(_levels[^1][0]).ToLowerInvariant();

    // Inclusion proof for the leaf at the given index: O(log n) hashes.
    public List<ProofStep> Proof(int leafIndex)
    {
        var proof = new List<ProofStep>();
        var idx = leafIndex;

        for (var level = 0; level < _levels.Count - 1; level++)
        {
            var nodes = _levels[level];
            var siblingIdx = idx % 2 == 0 ? idx + 1 : idx - 1;

            if (siblingIdx < nodes.Count)
            {
                proof.Add(new ProofStep(nodes[siblingIdx], SiblingOnRight: idx % 2 == 0));
            }

            idx /= 2;
        }

        return proof;
    }

    // Verify that leafData belongs to a tree with the given root.
    public static bool Verify(byte[] leafData, IEnumerable<ProofStep> proof, string rootHex)
    {
        var current = SHA256.HashData(leafData);
        foreach (var step in proof)
        {
            current = step.SiblingOnRight
                ? HashPair(current, step.Hash)
                : HashPair(step.Hash, current);
        }

        return CryptographicOperations.FixedTimeEquals(current, Convert.FromHexString(rootHex));
    }

    private static byte[] HashPair(byte[] left, byte[] right)
    {
        var buffer = new byte[left.Length + right.Length];
        left.CopyTo(buffer, 0);
        right.CopyTo(buffer, left.Length);
        return SHA256.HashData(buffer);
    }
}

from __future__ import annotations

import hashlib
import hmac
from dataclasses import dataclass
from typing import Iterable

@dataclass(frozen=True, slots=True)
class ProofStep:
    """A single hash+position on a Merkle path."""

    hash: bytes
    sibling_on_right: bool

def _sha256(data: bytes) -> bytes:
    return hashlib.sha256(data).digest()

class MerkleTree:
    """Minimal Merkle tree using SHA-256.

    For an odd number of nodes the last one is duplicated (Bitcoin convention).
    """

    def __init__(self, leaves: list[bytes]) -> None:
        if not leaves:
            raise ValueError("At least one leaf is required")

        current = [_sha256(leaf) for leaf in leaves]
        # levels[0] = leaf hashes, levels[-1] = [root]
        self._levels: list[list[bytes]] = [current]

        while len(current) > 1:
            if len(current) % 2 == 1:
                current = current + [current[-1]]

            current = [
                _sha256(current[i] + current[i + 1])
                for i in range(0, len(current), 2)
            ]
            self._levels.append(current)

    @property
    def root(self) -> str:
        return self._levels[-1][0].hex()

    def proof(self, leaf_index: int) -> list[ProofStep]:
        """Inclusion proof for the leaf at the given index: O(log n) hashes."""
        steps: list[ProofStep] = []
        idx = leaf_index

        for level in self._levels[:-1]:
            sibling_idx = idx + 1 if idx % 2 == 0 else idx - 1
            if sibling_idx < len(level):
                steps.append(ProofStep(level[sibling_idx], sibling_on_right=idx % 2 == 0))
            idx //= 2

        return steps

    @staticmethod
    def verify(leaf_data: bytes, proof: Iterable[ProofStep], root_hex: str) -> bool:
        """Check whether leaf_data belongs to a tree with the given root."""
        current = _sha256(leaf_data)
        for step in proof:
            current = (
                _sha256(current + step.hash)
                if step.sibling_on_right
                else _sha256(step.hash + current)
            )

        return hmac.compare_digest(current.hex(), root_hex)

# Example: reconcile two replicas
# tree_a = MerkleTree(replica_a.rows())
# tree_b = MerkleTree(replica_b.rows())
# if tree_a.root != tree_b.root:
#     ...  # descend level by level to find the diverging subtree