06 — Post-Quantum Identity (W-OTS)

Status: Published

Last reviewed: August 2026

Scope

Pyramidion contains a hash-based signature scheme — a Winternitz one-time signature with a Merkle-compressed public key, referred to in the code as GigaWOTS. It is used in two places: the hardened backup lock (doc 05 §3) and a signature chain attached to a post-quantum identity.

This document describes the construction precisely enough to reimplement, and is direct about what it is: a custom scheme, not a standardized one. §7 is the part to read before relying on it.

Summary

1. One-time signatures, and what that means

A Winternitz signature key signs one message. Not "one message per session" or "one message ideally" — one, ever. Signing twice under the same key material reveals enough of the private chains to forge a third signature.

Everything structural about this scheme follows from that constraint: the leaf sets are derived per use, the identity chain publishes the next key inside each signature, and the backup lock advances an index every time it re-locks. §5 covers how distinctness is maintained and §7.4 covers what happens if it is not.

2. The construction

2.1 Private leaves are derived, not stored

Nothing is stored. Given the signing key and a 16-byte chain id, the leaves are regenerated deterministically:

wotsKey  = SHA-256( keyNonce(4 bytes) ‖ signingKey )
raw      = AES-256-CTR( wotsKey, chainId, 0x00 × leafSize² )
leaves   = per-32-byte-block SHA-256 of raw

leafSize² is 1,024 bytes for 256-bit mode — 32 leaves of 32 bytes. The checksum leaves come from a second encryption under the same key with the chain id's last two bytes replaced by the constant 65.

The security of every leaf therefore reduces to the signing key and the chain id. There is no entropy in the scheme beyond those.

2.2 The public key

Each private leaf is hashed 255 times. Those 34 chain tops (32 message + 2 checksum) become the leaves of a Merkle tree — pairwise hashed, odd nodes duplicated — and the root is the public key.

publicLeaf[i] = H^255( privateLeaf[i] )
publicKey     = merkleRoot( publicLeaf[0..33] )

Using a Merkle root rather than a concatenation keeps the public key one hash wide regardless of mode.

2.3 Signing

The message is hashed, and each byte of that hash selects a position on its own chain:

signature[i] = H^(255 - messageHash[i])( privateLeaf[i] )

A byte value of 255 releases the private leaf untouched; a byte of 0 releases a value one hash short of the public leaf.

2.4 The checksum, and why it is not optional

Chains only run one way. An attacker holding a signature can hash forward freely, so they can produce a valid-looking chain element for any message byte lower than the one that was signed. Without a checksum, every signature would be forgeable into a message with smaller bytes.

The checksum closes this:

checksum   = Σ (255 - messageHash[i])
checksumBytes = [checksum >> 8, checksum & 0xFF]
signature[32+j] = H^(255 - checksumBytes[j])( checksumLeaf[j] )

Lowering a message byte raises the checksum, which lowers 255 - checksumByte — meaning the forger would have to walk a checksum chain backwards, which is a preimage problem. Any forgery that becomes easier on one side becomes impossible on the other.

Two bytes are sufficient: the maximum checksum is 32 × 255 = 8,160 in 256-bit mode and 64 × 255 = 16,320 in 512-bit, both well inside 16 bits.

2.5 Verification recovers; it does not compare

Verification finishes each chain — hashing signature element i a further messageHash[i] times — rebuilds the Merkle root, and returns it. There is no internal comparison and no boolean.

publicLeaf[i] = H^(messageHash[i])( signature[i] )
recovered     = merkleRoot( publicLeaf[0..33] )

A correct signature over the correct message recovers exactly the public key. Anything else recovers a different value. What the caller does with that value is what distinguishes the two uses below — and in the backup lock's case it is what makes the scheme do double duty as a key derivation input.

3. Use one: the hardened backup lock

Covered in doc 05 §3. The recovered root is fed to PBKDF2 as the password, so there is no "if signature valid" branch to bypass — a tampered box recovers a different root, derives a different lock key, and fails the ordinary tag check.

One clarification worth making here. The lock signs with Kc, the generation key derived from the vault's own root key (doc 01 §2.6). So this is not a third-party-verifiable origin proof: anyone holding the vault's root key could regenerate the same private leaves. Its job is to be a tamper-evident commitment to the box whose output is unpredictable without the box — and for that, it works. Read it as integrity plus key derivation, not as a signature proving who made the backup.

4. Use two: the identity signature chain

A post-quantum identity carries a chain of signature blocks, each of type genesis, sign, or recovery. Verification walks it from the start and enforces three conditions per block:

1. Continuity of state — the block's previousHash equals the Merkle root of the previous block's signature.
2. Continuity of key — the block's topPublicKey equals the previous block's nextTopPublicKey.
3. Validity — recovering the root from the block's signature (§2.5) reproduces its declared topPublicKey.

The second condition is how a one-time scheme signs more than once: each signature commits, in its signed payload, to the public key of the key that will sign the next block. No key ever signs twice; the chain grows forward one key at a time. The genesis block must be at index 0, and a chain whose first block is anything else is rejected.

What the chain proves, and what it does not. It proves that every block after genesis descends unbroken from genesis — no insertions, no reordering, no substituted keys. It does not prove anything about genesis itself, whose topPublicKey is self-declared. The trust anchor has to arrive out of band; a chain verified in isolation is internally consistent, not authentic.

5. Keeping leaf sets distinct

Since leaves derive from (signing key, chain id), distinctness is entirely a question of never reusing a chain id under one key.

The backup lock builds its chain id as:

chainId = timestamp(6 bytes, ms) ‖ keyNonce(4) ‖ signatureIndex(4) ‖ 0x0000

reading keyNonce and signatureIndex from the lock already present on the backup and incrementing the index. Two independent guards therefore have to fail simultaneously — the same millisecond and the same index — before a leaf set repeats.

The identity chain relies on the published-next-key structure instead: a new key is generated for each block and its public key is committed in the previous one.

6. Why hash-based

Shor's algorithm breaks RSA and elliptic-curve signatures outright. Hash-based signatures rest only on the preimage and collision resistance of the underlying hash, for which the best known quantum attack is Grover's — a square-root speedup, answered by using a wide enough hash. SHA-256 chains retain roughly 128-bit preimage resistance against a quantum adversary; the 512-bit mode has correspondingly more margin.

Worth being clear about what this does and does not cover in this app. The vault's confidentiality was never quantum-threatened: AES-256 and PBKDF2 are symmetric and already have adequate margin. What is threatened is the asymmetric material — the secp256k1 signing key and the X25519 exchange key behind peer recovery (doc 05 §4). The post-quantum identity exists alongside those, not instead of them.

7. Limitations and non-goals

7.1 This is a custom construction. It is not XMSS (RFC 8391), not LMS (RFC 8554), not SLH-DSA/SPHINCS⁺ (FIPS 205), and not ML-DSA (FIPS 204). It resembles XMSS's WOTS+ with an L-tree, but it is not that scheme and has not been through standardization or third-party cryptanalysis. The components are individually conventional and the checksum logic is correct (§2.4), but "built from sound parts" is not the same guarantee as "analyzed as a whole". Anyone evaluating this app should weigh it accordingly, and anyone needing a signature scheme with published security proofs should not treat this as one.

7.2 The chains are unkeyed. XMSS's WOTS+ hashes each chain step with a position-dependent bitmask and key, which is what gives it a security reduction and resistance to multi-target attacks — an adversary attacking many keys at once cannot amortize work. This scheme iterates plain SHA-256 with no domain separation between positions, chains, or key instances. No concrete attack follows from that at these parameters, but it is the clearest structural difference from the standardized designs and the first thing a reviewer will notice.

7.3 The leaf obfuscation steps are not load-bearing. Before hashing, the raw keystream is folded with an XOR routine and each block is hashed. These steps are deterministic and public; they add no entropy and no proven strength. The leaves' unpredictability comes entirely from AES-256-CTR under a key derived from the signing key. Treat the extra steps as structure, not security.

7.4 Reuse is catastrophic and prevented only by convention. Two signatures under one leaf set expose, for every chain, the element at the lower of the two message bytes — from which every higher value is reachable by hashing forward. That is not a partial weakening; it is a full break of that key. Nothing in the scheme detects reuse, and nothing in the storage layer enforces uniqueness. The guards described in §5 are application logic.

7.5 Signatures are large. 1,088 bytes at 256-bit and 4,224 at 512-bit, against 64 for Ed25519. This is inherent to hash-based signatures rather than specific to this implementation, but it is why a hardened backup grows noticeably and why the identity chain's size scales with its length.

7.6 The genesis block is an unverifiable anchor. §4.

7.7 The backup lock is not an origin proof. §3.

8. Reproducing a verification

Given a signature, the message it covers, and the mode:

import hashlib

def H(b, bits):
    return hashlib.sha256(b).digest() if bits == 256 else hashlib.sha512(b).digest()

def chain(v, n, bits):
    for _ in range(n):
        v = H(v, bits)
    return v

def merkle_root(leaves, bits):
    level = list(leaves)
    while len(level) > 1:
        level = [H(level[i] + (level[i + 1] if i + 1 < len(level) else level[i]), bits)
                 for i in range(0, len(level), 2)]
    return level[0]

def recover(signature, message_hash, bits):
    """Returns the public key this signature+message pair implies."""
    n = len(message_hash)
    leaves = [chain(signature[i], c, bits) for i, c in enumerate(message_hash)]

    checksum = sum(255 - c for c in message_hash)
    cs_bytes = [checksum >> 8, checksum & 0xFF]
    leaves += [chain(signature[n + j], cs_bytes[j], bits) for j in range(2)]

    return merkle_root(leaves, bits)

The signature is the concatenated chain elements: n message elements followed by 2 checksum elements, each bits // 8 bytes. Mode is inferred from total length — 1,088 bytes is 256-bit, 4,224 is 512-bit.

Compare the returned value against the expected public key. Equality means the signature is valid for that exact message; inequality tells you nothing about which of the two was wrong.

Change log