Jan 1, 2025

So I'm planning to use some disk space for optimization of this expensive navigation. During validation, when validated prevouts are necessarily navigated, we can obtain the full set of output primary keys in order, for the given block. We can then store these in an array table contiguously (5 bytes each). The offset to the start of this set is an array index in the table, which is also 5 bytes, since there's one element for each of 2.6 billion inputs (ceiling(log2(2.8b)) = 32 and one more byte is required for growth). This implies a main table of 12.2GiB to hold the prevout primary keys in groups by block. Since blocks are validated out of order, which is where we obtain this set, we write the set in the validation chaser. The sets are written out of order and require an ordered index. We don't want to be searching for them, as that's the original problem. So we don't simply append to a hash table using the block primary key. Instead we bend one of our rules and then compensate for it. The prevout table is an array with a trivial (empty) head. We then provide a small array index, very much like the candidate and confirmed indexes, where the entry in the index is the prevout table PK for the block, and the array offset of the index is the candidate block height. This provides direct navigation from the block height to the set of prevout (output) primary keys. From this there is also direct navigation to the tx and direct access to the output index, value, and script. We can then search the tx PK in the strong_tx table for ordered confirmedness. However we also need to know which of the outputs are of the coinbase. These will always be first, but the count must be known, since a CB can have any number of outputs. Instead of marking every one of billions of entries with a 1 byte boolean (2.4GiB) we add the a byte count to the index entry (2.4 MiB). We could also merge a 1 bit flag into every output PK, which would be free apart from trivial processing. But we also need the height and mtp of the prevout.tx.header (prevout's block) so that we can perform maturity checks (coinbase maturity and bip68 relative locktime). We could possibly perform these during validation, though that requires some denormalization, since these take a dependency on the prevout's tx/block, which are not referenced in validation. This can be resolved by storing the header PK (3 bytes) with the prevout PK. This bumps us up from 12.2GiB to 19.4GiB, so not trivial. This could be optimized out by the denormalization. Also the coinbase outputs can be derived from the block's first tx, but that's more costly than saving the bits is worth. The minimum cost for the scheme is about 12.2GiB.