[bitcoin-dev] The TXO bitfield

[Bram Cohen <bram@bittorrent.com>]

[-- Attachment #1: Type: text/plain, Size: 2831 bytes --]

Looking forward in node scaling we can envision a future in which blocks
are required to come with proofs of their validity and nodes can be run
entirely in memory and never have to hit disk. Ideally we'd like for proofs
to be able to be stored in client wallets which plan to spend their utxos
later, or at least be able to have a full node make a single not terribly
expensive disk access to form the proof which can then be passed along to
other peers.

Such proofs will probably be significantly larger than the blocks they
prove (this is merkle root stuff, not zero knowledge stuff), but if we
accept that as a given then this should be doable, although the details of
how to do it aren't obvious.

This vision can be implemented simply and efficiently by playing some games
with the semantics of the term 'proof'. A proof is a thing which convinces
someone of something. What we've discussed in the past for such proofs
mostly has to do with maintaining a hash root of everything and having
proofs lead to that. This is an extrema of complexity of the proof and
simplicity of the checker, at the expense of forcing the root to be
maintained at all times and the proof to be reasonably fresh. Some tricks
can be applied to keep that problem under control, but there's an
alternative approach where the amount of data necessary to do validation is
much larger but still entirely reasonable to keep in memory, and the sizes
of proofs and their required freshness is much smaller.

In the previous discussion on Merkle sets I commented that insertion
ordering's main practical utility may be that it allows for compression. It
turns out that a constant factor of 256 makes a big difference. Since
there's only really one bit stored for each txo (stored or not) once you
have an insertion ordering you can simply store a bitfield of all txos so
far, which is entirely reasonable to hold in memory, and can be made even
more reasonable by compactifying down the older, mostly spent portions of
it (how best to compress a bitfield while maintaining random access is an
interesting problem but entirely doable).

This approach meets all the design goals, even allowing wallets to remember
their own 'proofs', which are just proofs of insertion ordering. Those
don't even change once the risk of reorgs has passed, so they can be stored
for years without being maintained.

Proofs of insertion ordering can be made by having a canonical way of
calculating a root of position commitments for each block, and nodes
calculate those roots when evaluating the block history and store them all
in memory. A proof of position is a path to one of those roots.

I've intentionally skipped over most of the details here, because it's
probably best to have a high level discussion of this as a general approach
before getting lost in the weeds.

[-- Attachment #2: Type: text/html, Size: 3049 bytes --]