Hash-Based Signatures: The Only Crypto That Needs No Algebra

Introduction

Every digital signature you have ever verified — HTTPS certificates, software updates, code-signing — ultimately rests on mathematics that a quantum computer could tear apart. RSA relies on the hardness of factoring; ECDSA relies on the hardness of the elliptic-curve discrete logarithm. Shor's algorithm, running on a large enough quantum machine, breaks both in polynomial time.

Hash-based signatures take a radically different approach: they derive their security purely from the collision resistance of a hash function. No algebraic structure. No number theory. Just the assumption that it is hard to find two inputs that hash to the same output — an assumption that Grover's algorithm weakens only quadratically, not catastrophically.

The idea traces back to Leslie Lamport in 1979. Lamport showed that a one-time signature could be built from any one-way function. Ralph Merkle then layered a hash tree on top in his 1979 PhD thesis (published 1987), allowing a single public key to authenticate thousands of messages. Today, SPHINCS+ — a stateless hash-based scheme — is one of the four algorithms selected by NIST in 2024 as a post-quantum signature standard, alongside lattice-based schemes like CRYSTALS-Dilithium.

Build a Merkle Tree

The demo below builds a Merkle tree over four one-time key pairs. Each leaf is the hash of a one-time public key. Inner nodes are hashes of their two children. The root is the single public key published to the world.

Click Sign with leaf to sign a message using one leaf's private key. The signature includes the leaf's one-time signature plus the authentication path — the sibling hashes needed to recompute every node up to the root. Click Verify to walk that path and confirm the root matches.

<p class="hint">A Merkle tree with <b>4 leaves</b>. Each leaf holds a one-time key pair.
    Choose a leaf, then click <b>Sign with leaf</b> to sign the message below using that
    leaf's private key. The signature includes the one-time signature and the
    <b>authentication path</b> (sibling hashes) back to the root. Click <b>Verify</b>
    to walk the path and confirm the root matches.</p>
<div id="tree-vis"></div>
<div class="controls">
  <label>Message: <input id="msg" type="text" value="Hello, quantum world!" maxlength="60"></label>
  <div class="leaf-btns">
    <button id="s0" type="button">Sign with leaf 0</button>
    <button id="s1" type="button">Sign with leaf 1</button>
    <button id="s2" type="button">Sign with leaf 2</button>
    <button id="s3" type="button">Sign with leaf 3</button>
  </div>
  <button id="verify" type="button" disabled>Verify</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status"></div>
<div id="sig-box" class="sig-box"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#tree-vis { margin: .5rem 0 .8rem; display: flex; flex-direction: column; align-items: center; gap: 6px; }
.tree-row { display: flex; gap: 10px; align-items: center; }
.node { display: flex; align-items: center; justify-content: center; border-radius: 6px;
        font: 600 11px ui-monospace, monospace; padding: 4px 6px; border: 1.5px solid #adb1b8;
        background: #e8eef3; color: #1d3557; white-space: nowrap; min-width: 120px; }
.node.leaf { background: #c9ccd1; border-color: #adb1b8; }
.node.leaf.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.node.root { background: #457b9d; color: #fff; border-color: #1d3557; min-width: 250px; }
.node.root.match { background: #0a7d33; border-color: #0a7d33; }
.node.root.mismatch { background: #c92f3c; border-color: #c92f3c; }
.node.auth { background: #ffc14d; border-color: #e6a820; color: #333; }
.connector { font-size: 18px; color: #aaa; user-select: none; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
.controls label { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; font-weight: 600; }
#msg { flex: 1; min-width: 180px; padding: .3rem .5rem; border: 1px solid #aaa; border-radius: 6px; font-size: .9rem; }
.leaf-btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-weight: 700; margin: .3rem 0; min-height: 1.2em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #457b9d; }
.sig-box { font: .8rem ui-monospace, monospace; background: #f0f4f8; border: 1px solid #cdd9e3;
           border-radius: 6px; padding: .5rem .7rem; white-space: pre-wrap; word-break: break-all;
           max-height: 130px; overflow-y: auto; color: #333; display: none; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy Merkle-tree signature demo.
// Security note: we use a simple polynomial hash (djb2-variant) for DISPLAY purposes.
// In a real system you would use SHA-256 or SHA3-256.
// The STRUCTURE of signing and verification is identical to XMSS / SPHINCS+.

// ── Tiny deterministic "hash" (good enough for a visual demo) ─────────────
function djb2(str) {
  let h = 5381;
  for (let i = 0; i < str.length; i++) h = ((h << 5) + h + str.charCodeAt(i)) >>> 0;
  return h.toString(16).padStart(8, '0');
}
function hash(a, b) { return djb2(a + '|' + b).padStart(8, '0'); }
function longHash(str) {
  // 32-char toy hash: 4 × djb2 with different salts
  return ['s1','s2','s3','s4'].map(s => djb2(s + str)).join('');
}

// ── Key generation ────────────────────────────────────────────────────────
// Each leaf i has:
//   privateKey[i][j] = longHash(’priv’+i+j)   (two halves: bit=0 and bit=1)
//   publicKey[i][j]  = hash of privateKey
//   leafHash[i]      = hash(concat of publicKey[i])
const N = 4; // leaves
const OTS_BITS = 4; // we sign 4 bits of the message hash for brevity

const priv = [], pub = [], leafHash = [];
for (let i = 0; i < N; i++) {
  priv[i] = []; pub[i] = [];
  for (let j = 0; j < OTS_BITS; j++) {
    priv[i][j] = [longHash('priv' + i + j + '0'), longHash('priv' + i + j + '1')];
    pub[i][j]  = [hash(priv[i][j][0], 'pk'), hash(priv[i][j][1], 'pk')];
  }
  leafHash[i] = longHash(pub[i].map(p => p[0] + p[1]).join(''));
}

// ── Merkle tree (8 nodes: leaves 0-3, internals 4-5, root 6) ─────────────
// Layer 0 (leaves): nodes[0..3] = leafHash
// Layer 1:         nodes[4] = hash(nodes[0],nodes[1]), nodes[5] = hash(nodes[2],nodes[3])
// Root:            nodes[6] = hash(nodes[4],nodes[5])
const nodes = [...leafHash];
nodes[4] = hash(nodes[0], nodes[1]);
nodes[5] = hash(nodes[2], nodes[3]);
nodes[6] = hash(nodes[4], nodes[5]);
const ROOT = nodes[6];

// ── Authentication path for leaf i ───────────────────────────────────────
// path[i] = list of sibling hashes from leaf to root
function authPath(i) {
  const path = [];
  // sibling at leaf level
  path.push({ idx: i ^ 1, hash: nodes[i ^ 1] });
  // sibling at internal level
  const parent = 4 + Math.floor(i / 2);
  const sibParent = parent ^ 1;
  path.push({ idx: sibParent, hash: nodes[sibParent] });
  return path;
}

// ── Message bit extraction (toy: 4 bits from hash) ────────────────────────
function msgBits(msg) {
  const h = longHash(msg);
  return Array.from({ length: OTS_BITS }, (_, j) => parseInt(h[j], 16) & 1);
}

// ── State ─────────────────────────────────────────────────────────────────
let currentSig = null;
let activeLeaf = -1;

// ── Rendering ─────────────────────────────────────────────────────────────
function short(s) { return s.slice(0, 8) + '…'; }

function renderTree(state) {
  // state: { activeLeaf, authIdxSet, rootState }
  const vis = document.getElementById('tree-vis');
  vis.innerHTML = '';

  const rowRoot = document.createElement('div'); rowRoot.className = 'tree-row';
  const rNode = document.createElement('div');
  rNode.className = 'node root' + (state.rootState === 'match' ? ' match' : state.rootState === 'mismatch' ? ' mismatch' : '');
  rNode.title = fmt(`Root: %ROOT%`, { ROOT: ROOT });
  rNode.textContent = fmt(`Root: %short%`, { short: short(ROOT) });
  rowRoot.appendChild(rNode);
  vis.appendChild(rowRoot);

  // connectors
  const conn = document.createElement('div'); conn.className = 'tree-row';
  conn.innerHTML = '<span class="connector">╱   ╲</span>'; vis.appendChild(conn);

  const rowInner = document.createElement('div'); rowInner.className = 'tree-row';
  [4, 5].forEach(idx => {
    const nd = document.createElement('div');
    nd.className = 'node' + (state.authIdxSet && state.authIdxSet.has(idx) ? ' auth' : '');
    nd.title = fmt(`Node %idx%: %v%`, { idx: idx, v: nodes[idx] });
    nd.textContent = 'N' + idx + ': ' + short(nodes[idx]);
    rowInner.appendChild(nd);
  });
  vis.appendChild(rowInner);

  const conn2 = document.createElement('div'); conn2.className = 'tree-row';
  conn2.innerHTML = '<span class="connector">╱╲ ╱╲</span>'; vis.appendChild(conn2);

  const rowLeaves = document.createElement('div'); rowLeaves.className = 'tree-row';
  for (let i = 0; i < N; i++) {
    const nd = document.createElement('div');
    let cls = 'node leaf';
    if (i === state.activeLeaf) cls += ' active';
    else if (state.authIdxSet && state.authIdxSet.has(i)) cls += ' auth';
    nd.className = cls;
    nd.title = fmt(`Leaf %i%: %v%`, { i: i, v: nodes[i] });
    nd.textContent = 'L' + i + ': ' + short(nodes[i]);
    rowLeaves.appendChild(nd);
  }
  vis.appendChild(rowLeaves);
}

function setStatus(txt, cls) {
  const s = document.getElementById('status');
  s.textContent = txt; s.className = 'status ' + (cls || '');
}

function showSig(sig) {
  const box = document.getElementById('sig-box');
  if (!sig) { box.style.display = 'none'; return; }
  box.style.display = 'block';
  box.textContent =
    fmt(`Leaf index : %leafIdx%
OTS sig    : [%map%]
Auth path  : [
%map2%
]`, { leafIdx: sig.leafIdx, map: sig.otsSig.map(short).join(', '), map2: sig.path.map(p => '  ' + short(p.hash)).join(',\n') });
}

// ── Actions ───────────────────────────────────────────────────────────────
function doSign(i) {
  const msg = document.getElementById('msg').value;
  const bits = msgBits(msg);
  // OTS: reveal priv[i][j][bit] for each bit j
  const otsSig = bits.map((b, j) => priv[i][j][b]);
  const path = authPath(i);
  currentSig = { leafIdx: i, otsSig, path, msg };
  activeLeaf = i;

  const authSet = new Set(path.map(p => p.idx));
  renderTree({ activeLeaf: i, authIdxSet: authSet, rootState: '' });
  setStatus(fmt(`Signed with leaf %i%. Auth path highlighted in orange. Click Verify.`, { i: i }), 'info');
  showSig(currentSig);
  document.getElementById('verify').disabled = false;
}

function doVerify() {
  if (!currentSig) return;
  const { leafIdx, otsSig, path, msg } = currentSig;
  const bits = msgBits(msg);

  // 1. Recompute each OTS public-key half from the revealed private value
  const recoveredPub = otsSig.map((sk, j) => hash(sk, 'pk'));
  // Check against stored pub (toy: we just verify the hash matches)
  const pubOK = recoveredPub.every((h, j) => h === pub[leafIdx][j][bits[j]]);

  // 2. Recompute leaf hash from OTS public keys
  const recoveredLeaf = longHash(
    Array.from({ length: OTS_BITS }, (_, j) => pub[leafIdx][j][0] + pub[leafIdx][j][1]).join('')
  );

  // 3. Walk authentication path to root
  let cur = recoveredLeaf;
  for (const step of path) {
    if (step.idx % 2 === 0 || (step.idx >= 4 && step.idx % 2 === 0)) {
      cur = hash(nodes[step.idx], cur); // sibling is left
    } else {
      cur = hash(cur, nodes[step.idx]); // sibling is right
    }
  }
  // Simpler: use parity of the leaf index to determine ordering
  // Redo with correct ordering:
  cur = recoveredLeaf;
  const li = leafIdx;
  // Step 1: combine with leaf sibling
  cur = li % 2 === 0 ? hash(cur, path[0].hash) : hash(path[0].hash, cur);
  // Step 2: combine with internal sibling
  const parentIdx = 4 + Math.floor(li / 2);
  cur = parentIdx % 2 === 0 ? hash(cur, path[1].hash) : hash(path[1].hash, cur);

  const rootMatch = cur === ROOT;
  const authSet = new Set(path.map(p => p.idx));

  renderTree({ activeLeaf: leafIdx, authIdxSet: authSet, rootState: rootMatch ? 'match' : 'mismatch' });
  if (rootMatch && pubOK) {
    setStatus(`✓ Verification OK — recomputed root matches the public key!`, 'ok');
    console.log(`Verification passed: recomputed root =`, cur, `| stored root =`, ROOT);
  } else {
    setStatus(`✗ Verification FAILED — root mismatch or bad OTS signature!`, 'bad');
    console.log(`Recomputed root:`, cur, `| stored root =`, ROOT);
  }
}

function doReset() {
  currentSig = null; activeLeaf = -1;
  renderTree({ activeLeaf: -1, authIdxSet: new Set(), rootState: '' });
  setStatus('');
  showSig(null);
  document.getElementById('verify').disabled = true;
}

// ── Init ──────────────────────────────────────────────────────────────────
for (let i = 0; i < N; i++) {
  document.getElementById('s' + i).addEventListener('click', () => doSign(i));
}
document.getElementById('verify').addEventListener('click', doVerify);
document.getElementById('reset').addEventListener('click', doReset);
renderTree({ activeLeaf: -1, authIdxSet: new Set(), rootState: '' });
setStatus(`Select a leaf to sign the message.`, 'info');
console.log(`Merkle root (public key):`, ROOT);
console.log(`Leaf hashes:`, leafHash);
console.log(`Internal nodes:`, nodes[4], nodes[5]);

<p class="hint">A Merkle tree with <b>4 leaves</b>. Each leaf holds a one-time key pair.
    Choose a leaf, then click <b>Sign with leaf</b> to sign the message below using that
    leaf's private key. The signature includes the one-time signature and the
    <b>authentication path</b> (sibling hashes) back to the root. Click <b>Verify</b>
    to walk the path and confirm the root matches.</p>
<div id="tree-vis"></div>
<div class="controls">
  <label>Message: <input id="msg" type="text" value="Hello, quantum world!" maxlength="60"></label>
  <div class="leaf-btns">
    <button id="s0" type="button">Sign with leaf 0</button>
    <button id="s1" type="button">Sign with leaf 1</button>
    <button id="s2" type="button">Sign with leaf 2</button>
    <button id="s3" type="button">Sign with leaf 3</button>
  </div>
  <button id="verify" type="button" disabled>Verify</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status"></div>
<div id="sig-box" class="sig-box"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#tree-vis { margin: .5rem 0 .8rem; display: flex; flex-direction: column; align-items: center; gap: 6px; }
.tree-row { display: flex; gap: 10px; align-items: center; }
.node { display: flex; align-items: center; justify-content: center; border-radius: 6px;
        font: 600 11px ui-monospace, monospace; padding: 4px 6px; border: 1.5px solid #adb1b8;
        background: #e8eef3; color: #1d3557; white-space: nowrap; min-width: 120px; }
.node.leaf { background: #c9ccd1; border-color: #adb1b8; }
.node.leaf.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.node.root { background: #457b9d; color: #fff; border-color: #1d3557; min-width: 250px; }
.node.root.match { background: #0a7d33; border-color: #0a7d33; }
.node.root.mismatch { background: #c92f3c; border-color: #c92f3c; }
.node.auth { background: #ffc14d; border-color: #e6a820; color: #333; }
.connector { font-size: 18px; color: #aaa; user-select: none; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
.controls label { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; font-weight: 600; }
#msg { flex: 1; min-width: 180px; padding: .3rem .5rem; border: 1px solid #aaa; border-radius: 6px; font-size: .9rem; }
.leaf-btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-weight: 700; margin: .3rem 0; min-height: 1.2em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #457b9d; }
.sig-box { font: .8rem ui-monospace, monospace; background: #f0f4f8; border: 1px solid #cdd9e3;
           border-radius: 6px; padding: .5rem .7rem; white-space: pre-wrap; word-break: break-all;
           max-height: 130px; overflow-y: auto; color: #333; display: none; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy Merkle-tree signature demo.
// Security note: we use a simple polynomial hash (djb2-variant) for DISPLAY purposes.
// In a real system you would use SHA-256 or SHA3-256.
// The STRUCTURE of signing and verification is identical to XMSS / SPHINCS+.

// ── Tiny deterministic "hash" (good enough for a visual demo) ─────────────
function djb2(str) {
  let h = 5381;
  for (let i = 0; i < str.length; i++) h = ((h << 5) + h + str.charCodeAt(i)) >>> 0;
  return h.toString(16).padStart(8, '0');
}
function hash(a, b) { return djb2(a + '|' + b).padStart(8, '0'); }
function longHash(str) {
  // 32-char toy hash: 4 × djb2 with different salts
  return ['s1','s2','s3','s4'].map(s => djb2(s + str)).join('');
}

// ── Key generation ────────────────────────────────────────────────────────
// Each leaf i has:
//   privateKey[i][j] = longHash(’priv’+i+j)   (two halves: bit=0 and bit=1)
//   publicKey[i][j]  = hash of privateKey
//   leafHash[i]      = hash(concat of publicKey[i])
const N = 4; // leaves
const OTS_BITS = 4; // we sign 4 bits of the message hash for brevity

const priv = [], pub = [], leafHash = [];
for (let i = 0; i < N; i++) {
  priv[i] = []; pub[i] = [];
  for (let j = 0; j < OTS_BITS; j++) {
    priv[i][j] = [longHash('priv' + i + j + '0'), longHash('priv' + i + j + '1')];
    pub[i][j]  = [hash(priv[i][j][0], 'pk'), hash(priv[i][j][1], 'pk')];
  }
  leafHash[i] = longHash(pub[i].map(p => p[0] + p[1]).join(''));
}

// ── Merkle tree (8 nodes: leaves 0-3, internals 4-5, root 6) ─────────────
// Layer 0 (leaves): nodes[0..3] = leafHash
// Layer 1:         nodes[4] = hash(nodes[0],nodes[1]), nodes[5] = hash(nodes[2],nodes[3])
// Root:            nodes[6] = hash(nodes[4],nodes[5])
const nodes = [...leafHash];
nodes[4] = hash(nodes[0], nodes[1]);
nodes[5] = hash(nodes[2], nodes[3]);
nodes[6] = hash(nodes[4], nodes[5]);
const ROOT = nodes[6];

// ── Authentication path for leaf i ───────────────────────────────────────
// path[i] = list of sibling hashes from leaf to root
function authPath(i) {
  const path = [];
  // sibling at leaf level
  path.push({ idx: i ^ 1, hash: nodes[i ^ 1] });
  // sibling at internal level
  const parent = 4 + Math.floor(i / 2);
  const sibParent = parent ^ 1;
  path.push({ idx: sibParent, hash: nodes[sibParent] });
  return path;
}

// ── Message bit extraction (toy: 4 bits from hash) ────────────────────────
function msgBits(msg) {
  const h = longHash(msg);
  return Array.from({ length: OTS_BITS }, (_, j) => parseInt(h[j], 16) & 1);
}

// ── State ─────────────────────────────────────────────────────────────────
let currentSig = null;
let activeLeaf = -1;

// ── Rendering ─────────────────────────────────────────────────────────────
function short(s) { return s.slice(0, 8) + '…'; }

function renderTree(state) {
  // state: { activeLeaf, authIdxSet, rootState }
  const vis = document.getElementById('tree-vis');
  vis.innerHTML = '';

  const rowRoot = document.createElement('div'); rowRoot.className = 'tree-row';
  const rNode = document.createElement('div');
  rNode.className = 'node root' + (state.rootState === 'match' ? ' match' : state.rootState === 'mismatch' ? ' mismatch' : '');
  rNode.title = fmt(`Root: %ROOT%`, { ROOT: ROOT });
  rNode.textContent = fmt(`Root: %short%`, { short: short(ROOT) });
  rowRoot.appendChild(rNode);
  vis.appendChild(rowRoot);

  // connectors
  const conn = document.createElement('div'); conn.className = 'tree-row';
  conn.innerHTML = '<span class="connector">╱   ╲</span>'; vis.appendChild(conn);

  const rowInner = document.createElement('div'); rowInner.className = 'tree-row';
  [4, 5].forEach(idx => {
    const nd = document.createElement('div');
    nd.className = 'node' + (state.authIdxSet && state.authIdxSet.has(idx) ? ' auth' : '');
    nd.title = fmt(`Node %idx%: %v%`, { idx: idx, v: nodes[idx] });
    nd.textContent = 'N' + idx + ': ' + short(nodes[idx]);
    rowInner.appendChild(nd);
  });
  vis.appendChild(rowInner);

  const conn2 = document.createElement('div'); conn2.className = 'tree-row';
  conn2.innerHTML = '<span class="connector">╱╲ ╱╲</span>'; vis.appendChild(conn2);

  const rowLeaves = document.createElement('div'); rowLeaves.className = 'tree-row';
  for (let i = 0; i < N; i++) {
    const nd = document.createElement('div');
    let cls = 'node leaf';
    if (i === state.activeLeaf) cls += ' active';
    else if (state.authIdxSet && state.authIdxSet.has(i)) cls += ' auth';
    nd.className = cls;
    nd.title = fmt(`Leaf %i%: %v%`, { i: i, v: nodes[i] });
    nd.textContent = 'L' + i + ': ' + short(nodes[i]);
    rowLeaves.appendChild(nd);
  }
  vis.appendChild(rowLeaves);
}

function setStatus(txt, cls) {
  const s = document.getElementById('status');
  s.textContent = txt; s.className = 'status ' + (cls || '');
}

function showSig(sig) {
  const box = document.getElementById('sig-box');
  if (!sig) { box.style.display = 'none'; return; }
  box.style.display = 'block';
  box.textContent =
    fmt(`Leaf index : %leafIdx%
OTS sig    : [%map%]
Auth path  : [
%map2%
]`, { leafIdx: sig.leafIdx, map: sig.otsSig.map(short).join(', '), map2: sig.path.map(p => '  ' + short(p.hash)).join(',\n') });
}

// ── Actions ───────────────────────────────────────────────────────────────
function doSign(i) {
  const msg = document.getElementById('msg').value;
  const bits = msgBits(msg);
  // OTS: reveal priv[i][j][bit] for each bit j
  const otsSig = bits.map((b, j) => priv[i][j][b]);
  const path = authPath(i);
  currentSig = { leafIdx: i, otsSig, path, msg };
  activeLeaf = i;

  const authSet = new Set(path.map(p => p.idx));
  renderTree({ activeLeaf: i, authIdxSet: authSet, rootState: '' });
  setStatus(fmt(`Signed with leaf %i%. Auth path highlighted in orange. Click Verify.`, { i: i }), 'info');
  showSig(currentSig);
  document.getElementById('verify').disabled = false;
}

function doVerify() {
  if (!currentSig) return;
  const { leafIdx, otsSig, path, msg } = currentSig;
  const bits = msgBits(msg);

  // 1. Recompute each OTS public-key half from the revealed private value
  const recoveredPub = otsSig.map((sk, j) => hash(sk, 'pk'));
  // Check against stored pub (toy: we just verify the hash matches)
  const pubOK = recoveredPub.every((h, j) => h === pub[leafIdx][j][bits[j]]);

  // 2. Recompute leaf hash from OTS public keys
  const recoveredLeaf = longHash(
    Array.from({ length: OTS_BITS }, (_, j) => pub[leafIdx][j][0] + pub[leafIdx][j][1]).join('')
  );

  // 3. Walk authentication path to root
  let cur = recoveredLeaf;
  for (const step of path) {
    if (step.idx % 2 === 0 || (step.idx >= 4 && step.idx % 2 === 0)) {
      cur = hash(nodes[step.idx], cur); // sibling is left
    } else {
      cur = hash(cur, nodes[step.idx]); // sibling is right
    }
  }
  // Simpler: use parity of the leaf index to determine ordering
  // Redo with correct ordering:
  cur = recoveredLeaf;
  const li = leafIdx;
  // Step 1: combine with leaf sibling
  cur = li % 2 === 0 ? hash(cur, path[0].hash) : hash(path[0].hash, cur);
  // Step 2: combine with internal sibling
  const parentIdx = 4 + Math.floor(li / 2);
  cur = parentIdx % 2 === 0 ? hash(cur, path[1].hash) : hash(path[1].hash, cur);

  const rootMatch = cur === ROOT;
  const authSet = new Set(path.map(p => p.idx));

  renderTree({ activeLeaf: leafIdx, authIdxSet: authSet, rootState: rootMatch ? 'match' : 'mismatch' });
  if (rootMatch && pubOK) {
    setStatus(`✓ Verification OK — recomputed root matches the public key!`, 'ok');
    console.log(`Verification passed: recomputed root =`, cur, `| stored root =`, ROOT);
  } else {
    setStatus(`✗ Verification FAILED — root mismatch or bad OTS signature!`, 'bad');
    console.log(`Recomputed root:`, cur, `| stored root =`, ROOT);
  }
}

function doReset() {
  currentSig = null; activeLeaf = -1;
  renderTree({ activeLeaf: -1, authIdxSet: new Set(), rootState: '' });
  setStatus('');
  showSig(null);
  document.getElementById('verify').disabled = true;
}

// ── Init ──────────────────────────────────────────────────────────────────
for (let i = 0; i < N; i++) {
  document.getElementById('s' + i).addEventListener('click', () => doSign(i));
}
document.getElementById('verify').addEventListener('click', doVerify);
document.getElementById('reset').addEventListener('click', doReset);
renderTree({ activeLeaf: -1, authIdxSet: new Set(), rootState: '' });
setStatus(`Select a leaf to sign the message.`, 'info');
console.log(`Merkle root (public key):`, ROOT);
console.log(`Leaf hashes:`, leafHash);
console.log(`Internal nodes:`, nodes[4], nodes[5]);

Result

Console

Notice: verification just hashes its way up the tree — fast and obvious. Forging a signature would require finding a collision in the hash function, which no known algorithm does efficiently, classically or quantum.

The Real Complexity

Hash-based signatures occupy a special place in cryptography because their security reduction is the tightest of any signing scheme:

Security assumption: collision resistance of the underlying hash (e.g., SHA-256 or SHA3-256). If the hash is secure, the signature is secure. No other assumption is needed.
Quantum threat: Grover's algorithm gives a quadratic speedup for finding preimages and collisions. A 256-bit hash retains roughly 128 bits of quantum security — still far beyond any foreseeable attack. Doubling the hash output (e.g., SHA3-512) restores the full classical margin.
The state problem: Lamport and Merkle's original schemes are stateful — each one-time key must never be reused. Reusing a Lamport key leaks the private key immediately. XMSS (RFC 8391, standardized 2018) manages state carefully and is suitable for hardware security modules.
Stateless schemes: SPHINCS+ (NIST PQC standard, 2024) eliminates state by signing a random index into a huge virtual tree. The signature is larger (~8–50 KB depending on parameters), but there is no reuse risk.
Signature size: the main cost of hash-based schemes. SPHINCS+ signatures dwarf RSA-2048 signatures (~256 bytes) — a deliberate trade-off for the strongest possible security guarantee.

In terms of P vs NP and complexity theory, collision resistance is a one-way function assumption: we believe inverting a cryptographic hash is not in P, but we cannot prove it. The scheme's security is conditional — as with all of cryptography — but the condition is the most conservative and best-studied one available.

Where It Matters

Hash-based signatures are the conservative choice for anything that must remain secure for decades or that handles a bounded number of signings:

Firmware and OS updates: a device shipped today may need its update chain to stay secure in 2045. Hash-based signatures provide a credible 20-year guarantee that algebraic schemes cannot.
Certificate authorities: the root CA key signs only a handful of intermediate certificates per year — a perfect fit for a stateful scheme like XMSS, where state management is tractable.
Code signing for open-source software: projects like OpenSSH and GnuPG have already begun testing SPHINCS+ support.
Blockchain anchoring: a blockchain transaction can commit a Merkle root to a public ledger, enabling compact audit trails for large sets of documents.
Post-quantum migration: NIST's 2024 selection of SPHINCS+ alongside lattice-based schemes means governments and standards bodies worldwide are already writing migration guides. Hash-based signatures are the fallback fallback: if lattice cryptography turns out to be breakable, SPHINCS+ still stands.

The scheme's drawback — large signatures — matters less every year as bandwidth grows and storage costs fall. For high-value, low-frequency signings, hash-based schemes are today's gold standard for post-quantum security.

Conclusion

Hash-based signatures are a rare thing in cryptography: a scheme whose security proof requires almost nothing. Lamport showed in 1979 that a one-way function is sufficient to sign one message. Merkle showed that a hash tree turns that into a practical system. Half a century later, that lineage is a NIST standard.

The price is signature size. The reward is a guarantee untouched by quantum algorithms or unexpected breakthroughs in algebra. If every lattice problem turns out to be easy, hash-based signatures still stand — they just need collisions to be hard.

In a world racing to migrate cryptographic infrastructure before quantum computers arrive, that kind of unconditional conservatism is not timidity. It is engineering wisdom. The same lesson applies across all of post-quantum cryptography: the assumption you trust least is the one you should minimize.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hash-based-signatures/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Hash-Based Signatures

When collision resistance is all you need