Jan 1, 2025

After spending a good amount of time on a utxo accumulator in an attempt to parallelize confirmations, I've come to the conclusion that this is not really possible. The accumulation must be performed sequentially to be useful, even if it's performed in parallel by block and then rolled up - the roll up is at best log(n) by splitting sets of blocks into halves and rolling up. But each division increases the cost of the roll-up accordingly, so it amounts to the same. It's still linear in the chain to accumulate the outputs. And the accumulation is only useful at its current height, requiring all previous blocks accumulated. So if you have a milestone/checkpoint segment, you need to roll all of that up as well. That can take as long as the sync itself, or longer, just to obtain the previous outputs. I tested this by just querying to obtain the inputs and their previous outputs by uint64_t primary key (not hash IDs). Just querying to obtain all of these takes almost 2 hours on a machine where the sync take 50 minutes. The big part of this cost is associating the prevouts, since they are pointed to by the inputs points, which are natural keys [hash:index]. This is necessary due (1) download concurrency, and (2) write-only tables - which are why the sync is fast. We pay this cost once already, during validation, to obtain the prevouts for validation. Any implementation needs to do this - to search for the hashes to match up inputs to prevouts. But to perform confirmation we are doing it a second time (for the blocks that are not checkpoint/milestone, the ones we validate). So the idea of accumulation was that we could accumulate in the same (validation) stage, and roll up out of order. However that requires significant additional work for milestone/checkpoint runs in order to fully populate the accumulator. It also then requires total ordering, as described above...