A linked list
that branches.

use sha2::{Sha256, Digest};

type Hash = [u8; 32];

fn sha256d(data: &[u8]) -> Hash {
    // Bitcoin double-SHA256
    let first  = Sha256::digest(data);
    let second = Sha256::digest(&first);
    second.into()
}

fn sha256d_pair(left: &Hash, right: &Hash) -> Hash {
    let mut combined = [0u8; 64];
    combined[..32].copy_from_slice(left);
    combined[32..].copy_from_slice(right);
    sha256d(&combined)
}

// Compute Merkle root from transaction hashes.
// This is exactly what Bitcoin miners compute
// before placing the Merkle root in the block header.
fn merkle_root(mut hashes: Vec<Hash>) -> Hash {
    assert!(!hashes.is_empty());

    while hashes.len() > 1 {
        // if odd number: duplicate last hash (Bitcoin rule)
        if hashes.len() % 2 == 1 {
            let last = *hashes.last().unwrap();
            hashes.push(last);
        }

        // combine pairs: postorder bottom-up
        hashes = hashes.chunks(2)
            .map(|pair| sha256d_pair(&pair[0], &pair[1]))
            .collect();
        // each iteration halves the number of hashes
        // O(n) total hashing work
        // O(log n) levels
    }
    hashes[0]
    // this 32-byte value appears in every Bitcoin block header
    // as the merkle_root field
    // change any transaction: this value changes
    // the block header hash changes
    // proof of work invalidated
    // network rejects the block
}

// Merkle proof: prove one transaction is in the tree.
// Returns the sibling hashes needed for verification.
fn merkle_proof(tx_index: usize,
                mut hashes: Vec<Hash>) -> Vec<Hash> {
    let mut proof = Vec::new();
    let mut idx   = tx_index;

    while hashes.len() > 1 {
        if hashes.len() % 2 == 1 {
            let last = *hashes.last().unwrap();
            hashes.push(last);
        }
        // sibling: if idx is even, sibling is idx+1
        //          if idx is odd,  sibling is idx-1
        let sibling = if idx % 2 == 0 { idx + 1 } else { idx - 1 };
        proof.push(hashes[sibling]);

        hashes = hashes.chunks(2)
            .map(|pair| sha256d_pair(&pair[0], &pair[1]))
            .collect();
        idx /= 2;
    }
    proof
    // for 4096 transactions: proof has 12 hashes
    // 12 x 32 bytes = 384 bytes
    // vs downloading the full block: ~1 megabyte
    // O(log n) proof size. always.
}

#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <openssl/sha.h>

typedef uint8_t Hash[32];

static void sha256d(const uint8_t *data,
                    size_t len, Hash out) {
    uint8_t first[32];
    SHA256(data, len, first);
    SHA256(first, 32, out);
}

static void sha256d_pair(const Hash left,
                          const Hash right, Hash out) {
    uint8_t combined[64];
    memcpy(combined,      left,  32);
    memcpy(combined + 32, right, 32);
    sha256d(combined, 64, out);
}

/* Compute Merkle root in-place.
 * hashes: array of n transaction hashes.
 * Modifies hashes in place, reducing to 1.
 * Returns the root in hashes[0]. */
void merkle_root(Hash *hashes, size_t *n) {
    while (*n > 1) {
        /* duplicate last if odd */
        if (*n % 2 == 1)
            memcpy(hashes[*n], hashes[*n - 1], 32);

        size_t next = (*n + 1) / 2;
        for (size_t i = 0; i < next; i++)
            sha256d_pair(hashes[2*i],
                         hashes[2*i+1 < *n ? 2*i+1 : 2*i],
                         hashes[i]);
        *n = next;
    }
    /* hashes[0] is now the Merkle root */
    /* same 32 bytes that appear in the Bitcoin block header */
}