{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ex47-000",
   "metadata": {},
   "source": [
    "# Chapter 47 — Practical Exercises\n",
    "\n",
    "Companion sheet for [Chapter 47 — *Hash-Based Signatures*](ch47_hash_signatures.ipynb).\n",
    "Six exercises building from a one-line verifier to a state-reuse forgery.\n",
    "\n",
    "Click *\"Click to show\"* on any solution cell to reveal a fully commented\n",
    "reference implementation.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ex47-001",
   "metadata": {},
   "source": [
    "## Exercise 47.E1 — ★ Lamport verification\n",
    "\n",
    "**Goal.** Fill in `lamport_verify(pk, msg, sig)` so it returns `True` iff\n",
    "the signature is valid.\n",
    "\n",
    "**Theory.** [§47.2 — Lamport one-time signatures](ch47_hash_signatures.ipynb#lamport-one-time-signatures-1979).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ex47-002",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.891474Z",
     "iopub.status.busy": "2026-05-12T08:46:22.891362Z",
     "iopub.status.idle": "2026-05-12T08:46:22.896516Z",
     "shell.execute_reply": "2026-05-12T08:46:22.896137Z"
    }
   },
   "outputs": [],
   "source": [
    "import hashlib\n",
    "\n",
    "def H(x): return hashlib.sha256(x).digest()\n",
    "def bits(x):\n",
    "    out = []\n",
    "    for byte in x:\n",
    "        for j in range(8):\n",
    "            out.append((byte >> (7 - j)) & 1)\n",
    "    return out\n",
    "\n",
    "\n",
    "def lamport_verify(pk, msg, sig):\n",
    "    '''pk[i] is a 2-element list [H(s_{i,0}), H(s_{i,1})]; sig[i] is the revealed s.'''\n",
    "    # TODO: hash each sig[i] and check that it matches pk[i][h_i] where\n",
    "    # h = bits(H(msg)).  Return True if EVERY position checks out.\n",
    "    raise NotImplementedError('your turn')\n",
    "\n",
    "\n",
    "# Self-test.\n",
    "import os\n",
    "sk = [[os.urandom(32), os.urandom(32)] for _ in range(256)]\n",
    "pk = [[H(a), H(b)] for a, b in sk]\n",
    "msg = b'hello world'\n",
    "sig = [sk[i][b] for i, b in enumerate(bits(H(msg)))]\n",
    "# assert lamport_verify(pk, msg, sig) is True\n",
    "# assert lamport_verify(pk, b'hello WORLD', sig) is False\n",
    "# print('E1 OK')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ex47-003",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.897747Z",
     "iopub.status.busy": "2026-05-12T08:46:22.897668Z",
     "iopub.status.idle": "2026-05-12T08:46:22.900291Z",
     "shell.execute_reply": "2026-05-12T08:46:22.899899Z"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E1 OK\n"
     ]
    }
   ],
   "source": [
    "# Solution.\n",
    "#\n",
    "# Verification is symmetric to signing: we hash each revealed secret string and\n",
    "# compare against the precomputed public commitment for the bit selected by\n",
    "# the message hash.  All 256 positions must agree -- a single mismatch means\n",
    "# the signature is invalid.\n",
    "\n",
    "def lamport_verify(pk, msg, sig):\n",
    "    h = bits(H(msg))\n",
    "    return all(H(sig[i]) == pk[i][b] for i, b in enumerate(h))\n",
    "\n",
    "assert lamport_verify(pk, msg, sig) is True\n",
    "assert lamport_verify(pk, b'hello WORLD', sig) is False\n",
    "print('E1 OK')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ex47-004",
   "metadata": {},
   "source": [
    "## Exercise 47.E2 — ★★ Build a Merkle authentication path\n",
    "\n",
    "**Goal.** Given the level-by-level hashes of a binary Merkle tree\n",
    "`levels[0] = leaves, levels[1] = parents, ..., levels[-1] = [root]`, write\n",
    "`auth_path(levels, j)` returning the $h$ sibling hashes from leaf $j$ up\n",
    "to the root.\n",
    "\n",
    "**Theory.** [§47.4 — Merkle trees: one public key, many signatures](ch47_hash_signatures.ipynb#merkle-trees-one-public-key-many-signatures).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ex47-005",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.901429Z",
     "iopub.status.busy": "2026-05-12T08:46:22.901347Z",
     "iopub.status.idle": "2026-05-12T08:46:22.904194Z",
     "shell.execute_reply": "2026-05-12T08:46:22.903773Z"
    }
   },
   "outputs": [],
   "source": [
    "def build_merkle(leaves):\n",
    "    levels = [leaves[:]]\n",
    "    while len(levels[-1]) > 1:\n",
    "        cur = levels[-1]\n",
    "        nxt = [H(cur[i] + cur[i + 1]) for i in range(0, len(cur), 2)]\n",
    "        levels.append(nxt)\n",
    "    return levels\n",
    "\n",
    "\n",
    "def auth_path(levels, j):\n",
    "    '''Return the list of sibling hashes from leaf j up to the root.'''\n",
    "    # TODO: at each level (except the root), append the SIBLING hash to the\n",
    "    # path and update j -> j // 2.  Use j ^ 1 to flip the last bit (= sibling\n",
    "    # index).\n",
    "    raise NotImplementedError('your turn')\n",
    "\n",
    "\n",
    "def verify_merkle_path(root, leaf, j, path):\n",
    "    cur = leaf\n",
    "    for sib in path:\n",
    "        cur = H(cur + sib) if j % 2 == 0 else H(sib + cur)\n",
    "        j //= 2\n",
    "    return cur == root\n",
    "\n",
    "\n",
    "# Test.\n",
    "import os\n",
    "leaves = [H(os.urandom(8)) for _ in range(8)]\n",
    "levels = build_merkle(leaves)\n",
    "root   = levels[-1][0]\n",
    "# for j in range(8):\n",
    "#     p = auth_path(levels, j)\n",
    "#     assert verify_merkle_path(root, leaves[j], j, p), f'leaf {j} failed'\n",
    "# print('E2 OK')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ex47-006",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.905285Z",
     "iopub.status.busy": "2026-05-12T08:46:22.905191Z",
     "iopub.status.idle": "2026-05-12T08:46:22.907592Z",
     "shell.execute_reply": "2026-05-12T08:46:22.907183Z"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E2 OK\n"
     ]
    }
   ],
   "source": [
    "# Solution.\n",
    "#\n",
    "# The auth path is just the sibling hash at each level on the way to the root.\n",
    "# The bit-trick j ^ 1 flips the low bit (i.e. yields the sibling index of j),\n",
    "# and j //= 2 walks us up one level in the tree.\n",
    "#\n",
    "# The verify routine recombines: at each step, hash (current, sibling) in the\n",
    "# correct order depending on whether j was the LEFT or RIGHT child.  This is\n",
    "# §47.4 of the chapter.\n",
    "\n",
    "def auth_path(levels, j):\n",
    "    path = []\n",
    "    for lv in range(len(levels) - 1):\n",
    "        path.append(levels[lv][j ^ 1])\n",
    "        j //= 2\n",
    "    return path\n",
    "\n",
    "for j in range(8):\n",
    "    p = auth_path(levels, j)\n",
    "    assert verify_merkle_path(root, leaves[j], j, p), f'leaf {j} failed'\n",
    "print('E2 OK')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ex47-007",
   "metadata": {},
   "source": [
    "## Exercise 47.E3 — ★★★ The WOTS+ checksum\n",
    "\n",
    "**Goal.** Compute the Winternitz checksum digits given the message-hash\n",
    "digits.\n",
    "\n",
    "**Theory.** [§47.3 — Winternitz one-time signatures (WOTS+)](ch47_hash_signatures.ipynb#winternitz-one-time-signatures-wots).\n",
    "\n",
    "**Why this matters.** Without the checksum, an attacker can forge by\n",
    "*incrementing* a digit (which costs only further hashing). The checksum\n",
    "forces any digit increase to be matched by a *decrease* somewhere else,\n",
    "which is hard because the chain is preimage-resistant in that direction.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ex47-008",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.908774Z",
     "iopub.status.busy": "2026-05-12T08:46:22.908694Z",
     "iopub.status.idle": "2026-05-12T08:46:22.911217Z",
     "shell.execute_reply": "2026-05-12T08:46:22.910923Z"
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "W = 16                   # Winternitz digit alphabet size (4 bits per digit)\n",
    "WBITS = 4\n",
    "N = 32                   # SHA-256 output bytes\n",
    "LEN1 = (8 * N + WBITS - 1) // WBITS                  # = 64 message-hash digits\n",
    "LEN2 = (math.floor(math.log2(LEN1 * (W - 1))) // WBITS) + 1   # = 3 checksum digits\n",
    "\n",
    "\n",
    "def msg_to_digits(msg_hash):\n",
    "    '''Split a 32-byte hash into 64 base-16 digits.'''\n",
    "    out, buf, bits_in_buf = [], 0, 0\n",
    "    for byte in msg_hash:\n",
    "        buf = (buf << 8) | byte; bits_in_buf += 8\n",
    "        while bits_in_buf >= WBITS:\n",
    "            bits_in_buf -= WBITS\n",
    "            out.append((buf >> bits_in_buf) & (W - 1))\n",
    "    return out\n",
    "\n",
    "\n",
    "def wots_checksum(msg_digits):\n",
    "    '''Return the LEN2 checksum digits given the LEN1 message digits.'''\n",
    "    # TODO step 1: compute csum = sum_i (W - 1 - d_i) over message digits.\n",
    "    # TODO step 2: pack csum into LEN2 base-W digits.  Use big-endian byte\n",
    "    #              packing then call msg_to_digits on the bytes.\n",
    "    raise NotImplementedError('your turn')\n",
    "\n",
    "\n",
    "# Sanity test: each message digit is W-1 -> checksum is zero.\n",
    "# m = [W - 1] * LEN1\n",
    "# c = wots_checksum(m)\n",
    "# assert c[:LEN2] == [0] * LEN2, c\n",
    "# # And: each digit zero -> checksum is its maximum.\n",
    "# m0 = [0] * LEN1\n",
    "# c0 = wots_checksum(m0)\n",
    "# assert sum(c0[:LEN2]) > 0\n",
    "# print('E3 OK')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ex47-009",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.912355Z",
     "iopub.status.busy": "2026-05-12T08:46:22.912283Z",
     "iopub.status.idle": "2026-05-12T08:46:22.914568Z",
     "shell.execute_reply": "2026-05-12T08:46:22.914174Z"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E3 OK\n"
     ]
    }
   ],
   "source": [
    "# Solution.\n",
    "#\n",
    "# The checksum is sum_i (W - 1 - d_i).  Encoded in big-endian base-W and\n",
    "# truncated to LEN2 digits.  Hülsing 2013 gives the standard packing rule;\n",
    "# see chapter §47.3.\n",
    "\n",
    "def wots_checksum(msg_digits):\n",
    "    csum = sum((W - 1) - d for d in msg_digits)\n",
    "    csum_bytes = csum.to_bytes((LEN2 * WBITS + 7) // 8, 'big')\n",
    "    return msg_to_digits(csum_bytes)[:LEN2]\n",
    "\n",
    "m = [W - 1] * LEN1\n",
    "assert wots_checksum(m) == [0] * LEN2\n",
    "\n",
    "m0 = [0] * LEN1\n",
    "c0 = wots_checksum(m0)\n",
    "assert sum(c0) > 0\n",
    "print('E3 OK')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ex47-010",
   "metadata": {},
   "source": [
    "## Exercise 47.E4 — ★★★ Build a height-3 Merkle MSS\n",
    "\n",
    "**Goal.** Combine your Lamport from E1 + Merkle from E2 into a height-3\n",
    "many-time signature scheme. Sign the $j$-th of 8 messages and produce a\n",
    "*single* signature blob `(ots_sig, ots_pk, auth_path)` that the verifier\n",
    "can check using only the published root.\n",
    "\n",
    "**Theory.** [§47.4 — Merkle trees: one public key, many signatures](ch47_hash_signatures.ipynb#merkle-trees-one-public-key-many-signatures).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ex47-011",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.915573Z",
     "iopub.status.busy": "2026-05-12T08:46:22.915505Z",
     "iopub.status.idle": "2026-05-12T08:46:22.918467Z",
     "shell.execute_reply": "2026-05-12T08:46:22.918126Z"
    }
   },
   "outputs": [],
   "source": [
    "def lamport_keygen():\n",
    "    sk = [[os.urandom(32), os.urandom(32)] for _ in range(256)]\n",
    "    pk = [[H(a), H(b)] for a, b in sk]\n",
    "    return sk, pk\n",
    "\n",
    "\n",
    "def lamport_sign(sk, msg):\n",
    "    return [sk[i][b] for i, b in enumerate(bits(H(msg)))]\n",
    "\n",
    "\n",
    "def serialize_pk(pk):\n",
    "    return b''.join(b''.join(pair) for pair in pk)\n",
    "\n",
    "\n",
    "def mss_keygen(h):\n",
    "    n = 1 << h\n",
    "    leaf_keys = [lamport_keygen() for _ in range(n)]\n",
    "    leaves = [H(serialize_pk(pk)) for _, pk in leaf_keys]\n",
    "    levels = build_merkle(leaves)\n",
    "    return leaf_keys, levels[-1][0], levels    # secret leaf-keys + root + levels\n",
    "\n",
    "\n",
    "def mss_sign(leaf_keys, levels, j, msg):\n",
    "    # TODO: produce the triple (ots_sig, ots_pk, path).\n",
    "    raise NotImplementedError('your turn')\n",
    "\n",
    "\n",
    "def mss_verify(root, j, msg, blob):\n",
    "    ots_sig, ots_pk, path = blob\n",
    "    if not lamport_verify(ots_pk, msg, ots_sig): return False\n",
    "    leaf_hash = H(serialize_pk(ots_pk))\n",
    "    return verify_merkle_path(root, leaf_hash, j, path)\n",
    "\n",
    "\n",
    "# Test on a height-3 tree, 8 leaves, sign leaf 5.\n",
    "# leaf_keys, root, levels = mss_keygen(3)\n",
    "# blob = mss_sign(leaf_keys, levels, 5, b'pay 100 PLN')\n",
    "# assert mss_verify(root, 5, b'pay 100 PLN', blob)\n",
    "# assert not mss_verify(root, 5, b'pay 999 PLN', blob)\n",
    "# print('E4 OK')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ex47-012",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.919618Z",
     "iopub.status.busy": "2026-05-12T08:46:22.919555Z",
     "iopub.status.idle": "2026-05-12T08:46:22.927444Z",
     "shell.execute_reply": "2026-05-12T08:46:22.927079Z"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E4 OK\n"
     ]
    }
   ],
   "source": [
    "# Solution.\n",
    "#\n",
    "# Putting it together: at signing time we (a) extract the OTS sig with\n",
    "# lamport_sign on leaf j's secret key, (b) include leaf j's OTS public key\n",
    "# (the verifier needs to recompute the leaf hash), and (c) include the auth\n",
    "# path computed in E2.\n",
    "\n",
    "def mss_sign(leaf_keys, levels, j, msg):\n",
    "    sk_j, pk_j = leaf_keys[j]\n",
    "    ots_sig    = lamport_sign(sk_j, msg)\n",
    "    path       = auth_path(levels, j)\n",
    "    return ots_sig, pk_j, path\n",
    "\n",
    "leaf_keys, root, levels = mss_keygen(3)\n",
    "blob = mss_sign(leaf_keys, levels, 5, b'pay 100 PLN')\n",
    "assert mss_verify(root, 5, b'pay 100 PLN', blob)\n",
    "assert not mss_verify(root, 5, b'pay 999 PLN', blob)\n",
    "print('E4 OK')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ex47-013",
   "metadata": {},
   "source": [
    "## Exercise 47.E5 — ★★★★ State-reuse forgery (24-bit hash)\n",
    "\n",
    "**Goal.** Demonstrate the state-reuse catastrophe with a 24-bit truncated\n",
    "hash. Sign two distinct messages with the *same* Lamport key, then forge\n",
    "a third message such that its signature is verified by the public key.\n",
    "\n",
    "**Theory.** [§47.7 — The state-reuse catastrophe](ch47_hash_signatures.ipynb#the-state-reuse-catastrophe-demonstrated).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ex47-014",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.928536Z",
     "iopub.status.busy": "2026-05-12T08:46:22.928463Z",
     "iopub.status.idle": "2026-05-12T08:46:22.931323Z",
     "shell.execute_reply": "2026-05-12T08:46:22.931035Z"
    }
   },
   "outputs": [],
   "source": [
    "DEMO_BITS = 24\n",
    "\n",
    "def H_demo(x): return hashlib.sha256(x).digest()[: DEMO_BITS // 8]\n",
    "\n",
    "\n",
    "def demo_keygen():\n",
    "    sk = [[os.urandom(32), os.urandom(32)] for _ in range(DEMO_BITS)]\n",
    "    pk = [[H(a), H(b)] for a, b in sk]\n",
    "    return sk, pk\n",
    "\n",
    "\n",
    "def demo_sign(sk, msg):\n",
    "    h_bits = []\n",
    "    for byte in H_demo(msg):\n",
    "        for j in range(8): h_bits.append((byte >> (7 - j)) & 1)\n",
    "    return [sk[i][b] for i, b in enumerate(h_bits)]\n",
    "\n",
    "\n",
    "def demo_verify(pk, msg, sig):\n",
    "    h_bits = []\n",
    "    for byte in H_demo(msg):\n",
    "        for j in range(8): h_bits.append((byte >> (7 - j)) & 1)\n",
    "    return all(H(sig[i]) == pk[i][b] for i, b in enumerate(h_bits))\n",
    "\n",
    "\n",
    "def attack_after_two_sigs(pk, msg1, msg2, sig1, sig2):\n",
    "    '''Find a third message with a forged valid signature.'''\n",
    "    # TODO step 1: from (sig1, msg1) and (sig2, msg2) build a dictionary\n",
    "    #              `known[(i, b)] = secret` for every revealed secret string.\n",
    "    # TODO step 2: brute-force a salted message until every position of its\n",
    "    #              hash lands on a key that exists in `known`.  Then assemble\n",
    "    #              the forged signature.\n",
    "    raise NotImplementedError('your turn')\n",
    "\n",
    "\n",
    "# sk, pk = demo_keygen()\n",
    "# m1 = b'Pay 100 PLN to Alice.'\n",
    "# m2 = b'Pay 999 PLN to Bob.'\n",
    "# s1 = demo_sign(sk, m1); s2 = demo_sign(sk, m2)\n",
    "# m3, s3 = attack_after_two_sigs(pk, m1, m2, s1, s2)\n",
    "# print('forged for:', m3)\n",
    "# assert demo_verify(pk, m3, s3)\n",
    "# print('E5 OK')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ex47-015",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.932399Z",
     "iopub.status.busy": "2026-05-12T08:46:22.932328Z",
     "iopub.status.idle": "2026-05-12T08:46:22.935998Z",
     "shell.execute_reply": "2026-05-12T08:46:22.935632Z"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "forged for: b'Pay Mallory salt=212'\n",
      "E5 OK\n"
     ]
    }
   ],
   "source": [
    "# Solution.\n",
    "#\n",
    "# The attacker uses the two observed signatures to populate a partial secret\n",
    "# key.  Then they brute-force salted candidate messages until the message\n",
    "# hash happens to fall entirely on positions whose secrets are known.\n",
    "#\n",
    "# At 24 bits with two signatures, roughly half of the 24 hash positions\n",
    "# differ between m1 and m2 (so both secrets are revealed there); at the rest,\n",
    "# only one secret is known.  The success probability per random trial is\n",
    "# roughly (3/4)^24 ~= 1/1000.  We expect a forgery in a few thousand tries.\n",
    "\n",
    "def attack_after_two_sigs(pk, msg1, msg2, sig1, sig2):\n",
    "    bits1, bits2 = [], []\n",
    "    for byte in H_demo(msg1):\n",
    "        for j in range(8): bits1.append((byte >> (7 - j)) & 1)\n",
    "    for byte in H_demo(msg2):\n",
    "        for j in range(8): bits2.append((byte >> (7 - j)) & 1)\n",
    "    known = {}\n",
    "    for i, (a, b) in enumerate(zip(bits1, bits2)):\n",
    "        known[(i, a)] = sig1[i]\n",
    "        known[(i, b)] = sig2[i]\n",
    "    # Brute-force.\n",
    "    for trial in range(2_000_000):\n",
    "        cand = f'Pay Mallory salt={trial}'.encode()\n",
    "        h_bits = []\n",
    "        for byte in H_demo(cand):\n",
    "            for j in range(8): h_bits.append((byte >> (7 - j)) & 1)\n",
    "        if all((i, b) in known for i, b in enumerate(h_bits)):\n",
    "            return cand, [known[(i, b)] for i, b in enumerate(h_bits)]\n",
    "    raise RuntimeError('no forgery found')\n",
    "\n",
    "sk, pk = demo_keygen()\n",
    "m1 = b'Pay 100 PLN to Alice.'\n",
    "m2 = b'Pay 999 PLN to Bob.'\n",
    "s1 = demo_sign(sk, m1); s2 = demo_sign(sk, m2)\n",
    "m3, s3 = attack_after_two_sigs(pk, m1, m2, s1, s2)\n",
    "print('forged for:', m3)\n",
    "assert demo_verify(pk, m3, s3)\n",
    "print('E5 OK')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ex47-016",
   "metadata": {},
   "source": [
    "## Exercise 47.E6 — ★★★★★ Research: explore SLH-DSA-128s parameters\n",
    "\n",
    "**Goal.** Read FIPS 205 (NIST 2024) Algorithm 17 (`slh_sign`) and\n",
    "Algorithm 18 (`slh_verify`). Write a one-page memo explaining how the\n",
    "**SLH-DSA-SHA2-128s** parameter set fits its 7 856-byte signature size:\n",
    "how many WOTS+ signatures, FORS commitments, hyper-tree levels.\n",
    "\n",
    "**Then implement** the *outermost* hyper-tree layer: a single Merkle tree\n",
    "of height $h_{prime} = h / d$ that signs the root of the layer below\n",
    "using WOTS+. Verify your byte counts against the spec.\n",
    "\n",
    "**Theory.** [§47.6 — SLH-DSA / SPHINCS+](ch47_hash_signatures.ipynb#sphincs-slh-dsa-going-stateless).\n",
    "\n",
    "```{admonition} Parameter set SLH-DSA-SHA2-128s (FIPS 205 §10)\n",
    ":class: note\n",
    "$n = 16$, $h = 63$, $d = 7$, $h_{prime} = 9$, $a = 12$, $k = 14$, $w = 16$.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "ex47-017",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.936854Z",
     "iopub.status.busy": "2026-05-12T08:46:22.936796Z",
     "iopub.status.idle": "2026-05-12T08:46:22.938177Z",
     "shell.execute_reply": "2026-05-12T08:46:22.937885Z"
    }
   },
   "outputs": [],
   "source": [
    "# (Open-ended.) Sketch your reasoning here, then build the outer hyper-tree\n",
    "# layer.  The exercise is intentionally underspecified -- design choices\n",
    "# (recursive vs. iterative tree construction, in-memory layout, hash chain\n",
    "# parametrization) are part of the project.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ex47-018",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-05-12T08:46:22.938944Z",
     "iopub.status.busy": "2026-05-12T08:46:22.938886Z",
     "iopub.status.idle": "2026-05-12T08:46:22.941197Z",
     "shell.execute_reply": "2026-05-12T08:46:22.940869Z"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "WOTS+ chain count = 35  (=32 + 3)\n",
      "Predicted SLH-DSA-128s signature size = 7856 bytes\n",
      "E6 OK -- size matches FIPS 205 spec.\n"
     ]
    }
   ],
   "source": [
    "# Reference solution -- partial.\n",
    "#\n",
    "# A full SLH-DSA implementation is several hundred lines (see the SPHINCS+\n",
    "# reference at https://github.com/sphincs/sphincsplus).  Here we sketch the\n",
    "# size accounting for SLH-DSA-SHA2-128s and verify it against FIPS 205.\n",
    "#\n",
    "# - n = 16 bytes (output of internal hash)\n",
    "# - h = 63 (total hyper-tree height) split into d = 7 layers of h' = 9 each\n",
    "# - WOTS+ at each subtree node: w = 16 -> len = 35 chains of n bytes each\n",
    "# - FORS leaves at the bottom: k = 14 trees, each of height a = 12 with n-byte leaves\n",
    "#\n",
    "# Signature shape (per FIPS 205 Algorithm 17):\n",
    "#   1.  R           (n bytes)                              = 16\n",
    "#   2.  FORS sig    : k * (1 + a) * n  = 14 * 13 * 16     = 2912\n",
    "#   3.  HT sig      : d * (len + h') * n = 7 * (35+9) * 16= 4928\n",
    "#  Total                                                   = 7856  ✓\n",
    "n, h, d, hp, a, k, w = 16, 63, 7, 9, 12, 14, 16\n",
    "length = w - 1\n",
    "import math\n",
    "def wots_len_from_w(w, n):\n",
    "    len1 = math.ceil(8 * n / int(math.log2(w)))\n",
    "    len2 = math.floor(math.log2(len1 * (w - 1)) / math.log2(w)) + 1\n",
    "    return len1, len2, len1 + len2\n",
    "len1, len2, length = wots_len_from_w(w, n)\n",
    "print(f'WOTS+ chain count = {length}  (={len1} + {len2})')\n",
    "total = n + k * (1 + a) * n + d * (length + hp) * n\n",
    "print(f'Predicted SLH-DSA-128s signature size = {total} bytes')\n",
    "assert total == 7856, total\n",
    "print('E6 OK -- size matches FIPS 205 spec.')\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}