A fingerprint for
anything.

// Cryptographic hashes are like map hashes, but stronger.
//
// Properties HashMap doesn't need but blockchains do:
//   1. Pre-image resistance: given H(x), can't find x.
//   2. Collision resistance: can't find x, y with H(x) == H(y).
//   3. Avalanche: flip one bit of x → ~half the bits of H(x) flip.
//
// The price is speed: SHA-256 takes ~10 ns per byte; FNV-1a takes
// fractions of a nanosecond. You'd never use SHA-256 in a HashMap.
use sha2::{Sha256, Digest};

fn main() {
    let block_data = b"prev_hash || merkle_root || nonce=42";
    let mut hasher = Sha256::new();
    hasher.update(block_data);
    let digest = hasher.finalize();

    // 32 bytes (256 bits) regardless of input length.
    println!("{:x}", digest);

    // Bitcoin block-mining loop, in 4 lines:
    //   for nonce in 0.. {
    //       let h = sha256(block_with(nonce));
    //       if h.starts_with_zero_bits(target) { break }
    //   }
}

/*
 * Cryptographic hash with OpenSSL.
 * Properties that HashMap hashes dont need
 * but blockchains require:
 *
 * 1. Pre-image resistance:
 *    given H(x), cannot find x
 *    would require 2^256 attempts for SHA-256
 *
 * 2. Collision resistance:
 *    cannot find x, y such that H(x) == H(y)
 *    would require 2^128 attempts
 *
 * 3. Avalanche:
 *    flip one input bit, ~half output bits flip
 *    chaotically and unpredictably
 *
 * The price is speed:
 * SHA-256: ~10 ns per byte
 * FNV-1a:  fractions of a nanosecond per byte
 * Never use SHA-256 in a HashMap.
 */
#include <stdio.h>
#include <string.h>
#include <openssl/sha.h>

void sha256_hex(const uint8_t *data,
                size_t len,
                char out[65]) {
    uint8_t digest[SHA256_DIGEST_LENGTH];
    SHA256(data, len, digest);
    for (int i = 0; i < SHA256_DIGEST_LENGTH; i++)
        sprintf(out + i*2, "%02x", digest[i]);
    out[64] = '\0';
}

int main(void) {
    const char *block = "prev_hash || merkle_root || nonce=42";
    char hex[65];
    sha256_hex((const uint8_t*)block,
               strlen(block), hex);
    printf("%s\n", hex);
    /* 32 bytes (256 bits) regardless of input length */

    /*
     * Bitcoin mining loop in C:
     *
     * uint32_t nonce = 0;
     * uint8_t  header[80];
     * uint8_t  hash[32];
     *
     * for (;;) {
     *     memcpy(header + 76, &nonce, 4);
     *     sha256d(header, 80, hash);
     *     if (leading_zeros(hash) >= target) break;
     *     nonce++;
     * }
     *
     * sha256d = SHA256(SHA256(data)). Bitcoin double-hashes.
     * The loop is the ENTIRE proof-of-work algorithm.
     * ASICs run this at ~100 terahashes per second.
     */
    return 0;
}

/*
 * Avalanche demo:
 * sha256("alice") = 2bd806c97f0e00af1a1fc3328fa763a9269723c8db8fac4f93af71db186d6e90
 * sha256("alicf") = 9ebbbe3e0f1875e0a0a1764ea42e6ae0c4e55d25e0b5af9f8a86c0fae68a3286
 * one character different, output unrecognisable
 */

// A tiny Merkle root, in 20 lines.
// Each leaf is hashed. Pairs of hashes are concatenated and hashed.
// Repeat until one hash remains: the root.
use sha2::{Sha256, Digest};

fn h(bytes: &[u8]) -> Vec<u8> {
    Sha256::digest(bytes).to_vec()
}

fn merkle_root(leaves: &[&[u8]]) -> Vec<u8> {
    // Hash all leaves.
    let mut layer: Vec<Vec<u8>> = leaves.iter().map(|l| h(l)).collect();

    // Combine pairs until only the root is left.
    while layer.len() > 1 {
        let mut next = Vec::with_capacity(layer.len() / 2 + 1);
        for pair in layer.chunks(2) {
            let mut combined = pair[0].clone();
            // If odd number of nodes, duplicate the last one (Bitcoin's rule).
            combined.extend_from_slice(pair.get(1).unwrap_or(&pair[0]));
            next.push(h(&combined));
        }
        layer = next;
    }
    layer.pop().unwrap()
}

// Change any leaf, even by one bit, and the root changes completely.
// That single 32-byte root is enough to prove the integrity of
// gigabytes of transactions underneath it.

/*
 * A Merkle root computed in C using OpenSSL.
 * Each leaf is SHA-256 hashed.
 * Pairs of hashes are concatenated and re-hashed.
 * Repeat until one hash remains: the Merkle root.
 *
 * Bitcoin uses double SHA-256: SHA256(SHA256(data)).
 * This implementation uses single SHA-256 for clarity.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <openssl/sha.h>

#define HASH_LEN SHA256_DIGEST_LENGTH  /* 32 bytes */

typedef uint8_t Hash[HASH_LEN];

void sha256(const uint8_t *data, size_t len, Hash out) {
    SHA256(data, len, out);
}

void merkle_root(const uint8_t **leaves,
                 size_t        *lens,
                 size_t         n,
                 Hash           out)
{
    if (n == 0) { memset(out, 0, HASH_LEN); return; }

    /* hash all leaves into a working layer */
    Hash *layer = malloc(n * sizeof(Hash));
    for (size_t i = 0; i < n; i++)
        sha256(leaves[i], lens[i], layer[i]);

    /* combine pairs until one hash remains */
    while (n > 1) {
        size_t next_n = (n + 1) / 2;
        Hash *next = malloc(next_n * sizeof(Hash));

        for (size_t i = 0; i < next_n; i++) {
            size_t l = 2 * i;
            size_t r = (2*i+1 < n) ? 2*i+1 : 2*i;
            /* duplicate last node if odd (Bitcoins rule) */

            uint8_t pair[2 * HASH_LEN];
            memcpy(pair,            layer[l], HASH_LEN);
            memcpy(pair + HASH_LEN, layer[r], HASH_LEN);
            sha256(pair, 2 * HASH_LEN, next[i]);
        }

        free(layer);
        layer = next;
        n = next_n;
    }

    memcpy(out, layer[0], HASH_LEN);
    free(layer);
    /*
     * Change any leaf by one bit and its hash changes.
     * Every hash on the path to the root changes.
     * The root becomes unrecognisable.
     * That 32-byte root proves the integrity of
     * gigabytes of transactions underneath it.
     */
}

int main(void) {
    const char *txns[] = { "tx1", "tx2", "tx3", "tx4" };
    const uint8_t *leaves[4];
    size_t lens[4];

    for (int i = 0; i < 4; i++) {
        leaves[i] = (const uint8_t *)txns[i];
        lens[i]   = strlen(txns[i]);
    }

    Hash root;
    merkle_root(leaves, lens, 4, root);

    printf("Merkle root: ");
    for (int i = 0; i < HASH_LEN; i++)
        printf("%02x", root[i]);
    printf("\n");
    return 0;
}