Blockchain Consensus Mechanisms

import hashlib
import time
from typing import List, Tuple, Optional


# ── 1. PoW Mining Loop ─────────────────────────────────────────────────

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

def mine_block(header_bytes: bytes, target_bits: int) -> Tuple[int, bytes]:
    """
    Find nonce such that double_sha256(header || nonce) has target_bits leading zero bits.
    Returns (nonce, hash_bytes).
    """
    target = (1 << (256 - target_bits)) - 1
    nonce = 0
    while True:
        candidate = header_bytes + nonce.to_bytes(4, 'little')
        h = double_sha256(candidate)
        h_int = int.from_bytes(h, 'big')
        if h_int <= target:
            return nonce, h
        nonce = (nonce + 1) & 0xFFFFFFFF
        if nonce == 0:
            raise OverflowError("Exhausted 32-bit nonce space — change extraNonce")


# ── 2. Difficulty Adjustment ───────────────────────────────────────────

TARGET_TIMESPAN = 2016 * 600  # seconds (2 weeks)

def adjust_target(old_target: int, actual_timespan: int) -> int:
    """
    Recalculate PoW target after 2016 blocks.
    old_target: current target as 256-bit integer
    actual_timespan: seconds taken for last 2016 blocks
    Returns new target as 256-bit integer.
    """
    # Clamp timespan to [TARGET/4, TARGET*4]
    actual_timespan = max(TARGET_TIMESPAN // 4, min(actual_timespan, TARGET_TIMESPAN * 4))
    new_target = (old_target * actual_timespan) // TARGET_TIMESPAN
    # Enforce max target (genesis difficulty)
    MAX_TARGET = 0x00000000FFFF0000000000000000000000000000000000000000000000000000
    return min(new_target, MAX_TARGET)


# ── 3. Longest-Chain Selection ─────────────────────────────────────────

class Block:
    def __init__(self, height: int, prev_hash: str, work: int):
        self.height = height
        self.prev_hash = prev_hash
        self.work = work  # 1 / target for this block (as integer approximation)
        self.total_work = 0  # set when building chain

def compute_chain_work(tip: Block, blocks_by_hash: dict) -> int:
    """Walk backwards from tip summing work."""
    total = 0
    current = tip
    while current is not None:
        total += current.work
        current = blocks_by_hash.get(current.prev_hash)
    return total

def select_best_chain(tips: List[Block], blocks_by_hash: dict) -> Block:
    """Nakamoto consensus: pick chain with highest total work."""
    best_tip = None
    best_work = -1
    for tip in tips:
        work = compute_chain_work(tip, blocks_by_hash)
        if work > best_work:
            best_work = work
            best_tip = tip
    return best_tip


# ── 4. Simple BFT Round (Tendermint-style) ─────────────────────────────

def tendermint_round(
    validators: List[dict],
    proposed_block_hash: str,
    round_number: int
) -> Optional[str]:
    """
    Simplified single-round Tendermint simulation.
    validators: list of {'id': str, 'stake': int, 'honest': bool}
    Returns committed block hash or None if round fails.
    """
    total_stake = sum(v['stake'] for v in validators)
    quorum = (2 * total_stake) // 3 + 1

    # Prevote phase
    prevote_weight = sum(
        v['stake'] for v in validators
        if v['honest']  # honest validators prevote for valid proposal
    )
    if prevote_weight < quorum:
        print(f"Round {round_number}: Prevote failed — insufficient honest stake")
        return None

    # Precommit phase
    precommit_weight = prevote_weight  # simplification: same honest validators precommit
    if precommit_weight >= quorum:
        print(f"Round {round_number}: Block {proposed_block_hash[:8]}... committed!")
        return proposed_block_hash

    return None


# ── 5. Merkle Proof Validation ─────────────────────────────────────────

def merkle_hash(a: bytes, b: bytes) -> bytes:
    return double_sha256(a + b)

def verify_merkle_proof(
    tx_hash: bytes,
    proof: List[Tuple[bytes, bool]],  # (sibling_hash, sibling_is_on_right)
    merkle_root: bytes
) -> bool:
    """
    Verify that tx_hash is included in the Merkle tree with given root.
    proof: list of (sibling, is_right) pairs from leaf to root.
    """
    current = tx_hash
    for sibling, sibling_is_right in proof:
        if sibling_is_right:
            current = merkle_hash(current, sibling)
        else:
            current = merkle_hash(sibling, current)
    return current == merkle_root


# ── Example usage ──────────────────────────────────────────────────────
if __name__ == "__main__":
    # Mine a toy block (difficulty 18 bits → ~262k expected hashes)
    header = b"version=1|prev=abc|merkle=def|time=1700000000|bits=18"
    start = time.time()
    nonce, found_hash = mine_block(header, target_bits=18)
    elapsed = time.time() - start
    print(f"Found nonce={nonce}, hash={found_hash.hex()[:16]}..., time={elapsed:.3f}s")

    # Difficulty adjustment example
    old_target = 0x00000000FFFF << (256 - 32)  # toy target
    new_target = adjust_target(old_target, actual_timespan=12 * 24 * 3600)  # 12 days
    print(f"Target changed by factor {new_target / old_target:.4f} (expected ~1.167)")

// ── 1. PoW Mining (using Web Crypto SHA-256) ───────────────────────────

async function doubleSHA256(data) {
  const first  = await crypto.subtle.digest('SHA-256', data);
  const second = await crypto.subtle.digest('SHA-256', first);
  return new Uint8Array(second);
}

async function mineBlock(headerBytes, leadingZeroBits) {
  const nonce = new Uint8Array(4);
  const view  = new DataView(nonce.buffer);
  let attempts = 0;

  while (true) {
    const candidate = new Uint8Array(headerBytes.length + 4);
    candidate.set(headerBytes);
    candidate.set(nonce, headerBytes.length);

    const hash = await doubleSHA256(candidate);
    if (hasLeadingZeroBits(hash, leadingZeroBits)) {
      return { nonce: view.getUint32(0, true), hash, attempts };
    }
    const n = view.getUint32(0, true);
    view.setUint32(0, (n + 1) >>> 0, true);
    attempts++;
  }
}

function hasLeadingZeroBits(hashBytes, bits) {
  let remaining = bits;
  for (const byte of hashBytes) {
    if (remaining <= 0) break;
    if (remaining >= 8) {
      if (byte !== 0) return false;
      remaining -= 8;
    } else {
      const mask = 0xFF << (8 - remaining);
      if ((byte & mask) !== 0) return false;
      remaining = 0;
    }
  }
  return true;
}


// ── 2. Difficulty Adjustment ───────────────────────────────────────────

const TARGET_TIMESPAN = 2016 * 600; // 2 weeks in seconds

function adjustTarget(oldTargetHex, actualTimespanSec) {
  const oldTarget = BigInt('0x' + oldTargetHex);
  let timespan = BigInt(Math.max(
    TARGET_TIMESPAN / 4,
    Math.min(actualTimespanSec, TARGET_TIMESPAN * 4)
  ));
  const newTarget = (oldTarget * timespan) / BigInt(TARGET_TIMESPAN);
  return newTarget.toString(16).padStart(64, '0');
}


// ── 3. Longest-Chain Selection ─────────────────────────────────────────

function selectBestChain(tips, blockMap) {
  // tips: array of block hashes; blockMap: hash -> {work, prevHash}
  let bestTip = null, bestWork = 0n;

  for (const tip of tips) {
    let totalWork = 0n;
    let curr = tip;
    while (curr && blockMap[curr]) {
      totalWork += BigInt(blockMap[curr].work);
      curr = blockMap[curr].prevHash;
    }
    if (totalWork > bestWork) {
      bestWork = totalWork;
      bestTip = tip;
    }
  }
  return bestTip;
}


// ── 4. BFT Round Simulation ────────────────────────────────────────────

function tendermintRound(validators, proposedBlockHash) {
  const totalStake = validators.reduce((s, v) => s + v.stake, 0);
  const quorum = Math.floor(totalStake * 2 / 3) + 1;

  // Prevote: honest validators vote for valid block
  const prevoteWeight = validators
    .filter(v => v.honest)
    .reduce((s, v) => s + v.stake, 0);

  if (prevoteWeight < quorum) return null;

  // Precommit
  const precommitWeight = prevoteWeight; // same set in this simulation
  if (precommitWeight >= quorum) return proposedBlockHash;

  return null;
}


// ── 5. Merkle Proof Verification ───────────────────────────────────────

async function sha256(data) {
  const buf = await crypto.subtle.digest('SHA-256', data);
  return new Uint8Array(buf);
}

async function merkleHash(a, b) {
  const combined = new Uint8Array(a.length + b.length);
  combined.set(a); combined.set(b, a.length);
  const first = await sha256(combined);
  return sha256(first);
}

async function verifyMerkleProof(txHash, proof, merkleRoot) {
  // proof: [{sibling: Uint8Array, siblingIsRight: bool}]
  let current = txHash;
  for (const { sibling, siblingIsRight } of proof) {
    current = siblingIsRight
      ? await merkleHash(current, sibling)
      : await merkleHash(sibling, current);
  }
  return current.every((b, i) => b === merkleRoot[i]);
}

#include <stdint.h>
#include <string.h>
#include <stdio.h>
// Assumes sha256() writes 32 bytes to output buffer.
// (Use OpenSSL or a standalone SHA-256 implementation)
extern void sha256(const uint8_t *data, size_t len, uint8_t *out);

void double_sha256(const uint8_t *data, size_t len, uint8_t *out) {
    uint8_t tmp[32];
    sha256(data, len, tmp);
    sha256(tmp, 32, out);
}

/* ── PoW mining loop ─────────────────────────────────────────── */
int mine_block(const uint8_t *header, size_t header_len,
               int leading_zero_bytes, uint32_t *found_nonce)
{
    uint8_t buf[256], hash[32];
    memcpy(buf, header, header_len);

    for (uint32_t nonce = 0; ; nonce++) {
        uint32_t le = __builtin_bswap32(nonce);  // little-endian nonce
        memcpy(buf + header_len, &le, 4);
        double_sha256(buf, header_len + 4, hash);

        int ok = 1;
        for (int i = 0; i < leading_zero_bytes; i++) {
            if (hash[i] != 0) { ok = 0; break; }
        }
        if (ok) { *found_nonce = nonce; return 1; }
        if (nonce == 0xFFFFFFFF) return 0;  // exhausted
    }
}

/* ── Difficulty adjustment ───────────────────────────────────── */
#define TARGET_TIMESPAN (2016 * 600)  /* seconds */

void adjust_target(uint8_t target[32], int32_t actual_seconds) {
    /* clamp */
    if (actual_seconds < TARGET_TIMESPAN / 4) actual_seconds = TARGET_TIMESPAN / 4;
    if (actual_seconds > TARGET_TIMESPAN * 4) actual_seconds = TARGET_TIMESPAN * 4;

    /* multiply target by ratio using 256-bit big-endian arithmetic */
    /* (production code uses multi-precision integer library) */
    uint64_t ratio_num = (uint64_t)actual_seconds;
    uint64_t ratio_den = (uint64_t)TARGET_TIMESPAN;

    /* Simple 64-bit approximation using most-significant 8 bytes */
    uint64_t hi;
    memcpy(&hi, target, 8);
    hi = __builtin_bswap64(hi);
    hi = hi * ratio_num / ratio_den;
    hi = __builtin_bswap64(hi);
    memcpy(target, &hi, 8);
}

/* ── Merkle proof verification ───────────────────────────────── */
typedef struct { uint8_t hash[32]; int sibling_is_right; } ProofStep;

int verify_merkle_proof(const uint8_t *tx_hash, const ProofStep *proof,
                        int proof_len, const uint8_t *root)
{
    uint8_t current[32], combined[64], next[32];
    memcpy(current, tx_hash, 32);

    for (int i = 0; i < proof_len; i++) {
        if (proof[i].sibling_is_right) {
            memcpy(combined,      current,         32);
            memcpy(combined + 32, proof[i].hash,   32);
        } else {
            memcpy(combined,      proof[i].hash,   32);
            memcpy(combined + 32, current,         32);
        }
        double_sha256(combined, 64, next);
        memcpy(current, next, 32);
    }
    return memcmp(current, root, 32) == 0;
}

#include <array>
#include <cstdint>
#include <cstring>
#include <optional>
#include <vector>
#include <iostream>
// Requires a SHA-256 implementation (e.g., OpenSSL's EVP or standalone)
using Hash256 = std::array<uint8_t, 32>;
extern Hash256 sha256(const uint8_t* data, size_t len);

Hash256 double_sha256(const uint8_t* data, size_t len) {
    auto first = sha256(data, len);
    return sha256(first.data(), 32);
}

// ── PoW Mining ─────────────────────────────────────────────────────────
struct MineResult { uint32_t nonce; Hash256 hash; uint64_t attempts; };

std::optional<MineResult> mine(
    const std::vector<uint8_t>& header,
    int leading_zero_bytes)
{
    std::vector<uint8_t> buf(header.size() + 4);
    std::copy(header.begin(), header.end(), buf.begin());

    for (uint32_t nonce = 0; ; nonce++) {
        buf[header.size()    ] = nonce & 0xFF;
        buf[header.size() + 1] = (nonce >> 8)  & 0xFF;
        buf[header.size() + 2] = (nonce >> 16) & 0xFF;
        buf[header.size() + 3] = (nonce >> 24) & 0xFF;

        Hash256 h = double_sha256(buf.data(), buf.size());

        bool ok = true;
        for (int i = 0; i < leading_zero_bytes && ok; i++)
            ok = (h[i] == 0);

        if (ok) return MineResult{nonce, h, (uint64_t)nonce + 1};
        if (nonce == 0xFFFFFFFF) return std::nullopt;
    }
}

// ── Difficulty Adjustment ──────────────────────────────────────────────
constexpr int64_t TARGET_TIMESPAN = 2016LL * 600;

Hash256 adjust_target(Hash256 old_target, int64_t actual_seconds) {
    actual_seconds = std::max(TARGET_TIMESPAN / 4,
                     std::min(actual_seconds, TARGET_TIMESPAN * 4));
    // Big-integer multiply (simplified to leading 8 bytes here)
    Hash256 result = old_target;
    uint64_t hi = 0;
    for (int i = 0; i < 8; i++) hi = (hi << 8) | old_target[i];
    hi = static_cast<uint64_t>((__uint128_t)hi * actual_seconds / TARGET_TIMESPAN);
    for (int i = 7; i >= 0; i--) { result[i] = hi & 0xFF; hi >>= 8; }
    return result;
}

// ── Merkle Proof Verification ──────────────────────────────────────────
struct ProofStep { Hash256 sibling; bool sibling_is_right; };

bool verify_merkle_proof(
    const Hash256& tx_hash,
    const std::vector<ProofStep>& proof,
    const Hash256& root)
{
    Hash256 current = tx_hash;
    std::array<uint8_t, 64> combined;
    for (const auto& step : proof) {
        if (step.sibling_is_right) {
            std::copy(current.begin(), current.end(), combined.begin());
            std::copy(step.sibling.begin(), step.sibling.end(), combined.begin() + 32);
        } else {
            std::copy(step.sibling.begin(), step.sibling.end(), combined.begin());
            std::copy(current.begin(), current.end(), combined.begin() + 32);
        }
        current = double_sha256(combined.data(), 64);
    }
    return current == root;
}

import java.security.MessageDigest;
import java.util.Arrays;
import java.util.List;

public class NakamotoConsensus {

    // ── SHA-256 helpers ────────────────────────────────────────────────
    static byte[] sha256(byte[] data) throws Exception {
        return MessageDigest.getInstance("SHA-256").digest(data);
    }

    static byte[] doubleSha256(byte[] data) throws Exception {
        return sha256(sha256(data));
    }

    // ── PoW Mining Loop ────────────────────────────────────────────────
    record MineResult(int nonce, byte[] hash, long attempts) {}

    static MineResult mine(byte[] header, int leadingZeroBytes) throws Exception {
        byte[] buf = Arrays.copyOf(header, header.length + 4);

        for (int nonce = 0; nonce != -1; nonce++) {
            buf[header.length    ] = (byte)  (nonce        & 0xFF);
            buf[header.length + 1] = (byte) ((nonce >>  8) & 0xFF);
            buf[header.length + 2] = (byte) ((nonce >> 16) & 0xFF);
            buf[header.length + 3] = (byte) ((nonce >> 24) & 0xFF);

            byte[] hash = doubleSha256(buf);
            boolean ok = true;
            for (int i = 0; i < leadingZeroBytes && ok; i++)
                ok = (hash[i] == 0);

            if (ok) return new MineResult(nonce, hash, (long)nonce + 1);
        }
        throw new RuntimeException("Nonce space exhausted — change extraNonce");
    }

    // ── Difficulty Adjustment ──────────────────────────────────────────
    static final long TARGET_TIMESPAN = 2016L * 600;

    static double adjustDifficulty(double oldDifficulty, long actualSeconds) {
        actualSeconds = Math.max(TARGET_TIMESPAN / 4, Math.min(actualSeconds, TARGET_TIMESPAN * 4));
        return oldDifficulty * TARGET_TIMESPAN / actualSeconds;
    }

    // ── Longest-Chain Selection ────────────────────────────────────────
    record BlockInfo(String hash, String prevHash, long work) {}

    static String selectBestChain(List<String> tips, java.util.Map<String, BlockInfo> blockMap) {
        String bestTip = null;
        long bestWork = 0;
        for (String tip : tips) {
            long totalWork = 0;
            String curr = tip;
            while (curr != null && blockMap.containsKey(curr)) {
                BlockInfo b = blockMap.get(curr);
                totalWork += b.work();
                curr = b.prevHash();
            }
            if (totalWork > bestWork) { bestWork = totalWork; bestTip = tip; }
        }
        return bestTip;
    }

    // ── Merkle Proof Verification ──────────────────────────────────────
    record ProofStep(byte[] sibling, boolean siblingIsRight) {}

    static boolean verifyMerkleProof(byte[] txHash, List<ProofStep> proof,
                                     byte[] root) throws Exception {
        byte[] current = txHash;
        for (ProofStep step : proof) {
            byte[] combined = new byte[64];
            if (step.siblingIsRight()) {
                System.arraycopy(current,       0, combined,  0, 32);
                System.arraycopy(step.sibling(), 0, combined, 32, 32);
            } else {
                System.arraycopy(step.sibling(), 0, combined,  0, 32);
                System.arraycopy(current,        0, combined, 32, 32);
            }
            current = doubleSha256(combined);
        }
        return Arrays.equals(current, root);
    }

    public static void main(String[] args) throws Exception {
        // Toy example: mine with 2 leading zero bytes (~65k expected attempts)
        byte[] header = "v1|prev=abc|merkle=def|time=1700000000".getBytes();
        var result = mine(header, 2);
        System.out.printf("Found nonce=%d after %d attempts, hash=%s%n",
            result.nonce(), result.attempts(),
            bytesToHex(result.hash()).substring(0, 16) + "...");

        double newDiff = adjustDifficulty(50e12, 12 * 24 * 3600L);
        System.out.printf("New difficulty after 12-day period: %.2fT%n", newDiff / 1e12);
    }

    static String bytesToHex(byte[] b) {
        StringBuilder sb = new StringBuilder();
        for (byte x : b) sb.append(String.format("%02x", x & 0xFF));
        return sb.toString();
    }
}

package consensus

import (
	"crypto/sha256"
	"encoding/binary"
	"encoding/hex"
	"errors"
	"math/big"
)

// ── SHA-256 helpers ────────────────────────────────────────────────────

func doubleSHA256(data []byte) [32]byte {
	first  := sha256.Sum256(data)
	return sha256.Sum256(first[:])
}

// ── PoW Mining ─────────────────────────────────────────────────────────

type MineResult struct {
	Nonce    uint32
	Hash     [32]byte
	Attempts uint64
}

func MineBlock(header []byte, leadingZeroBytes int) (MineResult, error) {
	buf := make([]byte, len(header)+4)
	copy(buf, header)

	for nonce := uint32(0); ; nonce++ {
		binary.LittleEndian.PutUint32(buf[len(header):], nonce)
		h := doubleSHA256(buf)

		ok := true
		for i := range leadingZeroBytes {
			if h[i] != 0 {
				ok = false
				break
			}
		}
		if ok {
			return MineResult{Nonce: nonce, Hash: h, Attempts: uint64(nonce) + 1}, nil
		}
		if nonce == 0xFFFFFFFF {
			return MineResult{}, errors.New("nonce space exhausted")
		}
	}
}

// ── Difficulty Adjustment ──────────────────────────────────────────────

const targetTimespan = int64(2016 * 600) // 2 weeks in seconds

func AdjustTarget(oldTarget *big.Int, actualSeconds int64) *big.Int {
	// Clamp
	if actualSeconds < targetTimespan/4 {
		actualSeconds = targetTimespan / 4
	} else if actualSeconds > targetTimespan*4 {
		actualSeconds = targetTimespan * 4
	}

	newTarget := new(big.Int).Mul(oldTarget, big.NewInt(actualSeconds))
	newTarget.Div(newTarget, big.NewInt(targetTimespan))
	return newTarget
}

// ── Longest-Chain Selection ────────────────────────────────────────────

type BlockRecord struct {
	PrevHash string
	Work     *big.Int // proportional to 1/target
}

func SelectBestChain(tips []string, blockMap map[string]BlockRecord) string {
	bestTip := ""
	bestWork := new(big.Int)

	for _, tip := range tips {
		totalWork := new(big.Int)
		curr := tip
		for {
			b, ok := blockMap[curr]
			if !ok {
				break
			}
			totalWork.Add(totalWork, b.Work)
			curr = b.PrevHash
		}
		if totalWork.Cmp(bestWork) > 0 {
			bestWork = totalWork
			bestTip = tip
		}
	}
	return bestTip
}

// ── Merkle Proof Verification ──────────────────────────────────────────

type ProofStep struct {
	Sibling        [32]byte
	SiblingIsRight bool
}

func VerifyMerkleProof(txHash [32]byte, proof []ProofStep, root [32]byte) bool {
	current := txHash
	for _, step := range proof {
		var combined [64]byte
		if step.SiblingIsRight {
			copy(combined[:32], current[:])
			copy(combined[32:], step.Sibling[:])
		} else {
			copy(combined[:32], step.Sibling[:])
			copy(combined[32:], current[:])
		}
		current = doubleSHA256(combined[:])
	}
	return current == root
}

// ── Example main (in cmd/main.go) ─────────────────────────────────────
/*
func main() {
	header := []byte("v1|prev=abc|merkle=def|time=1700000000")
	result, err := consensus.MineBlock(header, 2)
	if err != nil { log.Fatal(err) }
	fmt.Printf("nonce=%d hash=%s... attempts=%d\n",
		result.Nonce, hex.EncodeToString(result.Hash[:8]), result.Attempts)
}
*/
_ = hex.EncodeToString // suppress unused import warning in snippet