TTL Index serialization format

[kcalvinalvin]

TTL Index

What is it?

Time-to-live indexes map Spent-Transaction-Outputs to their time-to-live value. Time-to-live values are the value that a STXO lives for. For example, if a TXO was created in block 10 and was spent in block 50, that TXO would have a ttl value of 40.

TTL values are calculated by

TTL = Spend block height - Create block height

Why do we need it?

TTL values are extremely useful when caching UTXOs in the context of the Utreexo project. The Utreexo paper section 5.4 shows the drastic reduction in download when using a ttl based caching. While there has not been any attempts to implement this to the current Bitcoin UTXO set, it may also help with caching UTXOs for the current leveldb based UTXO set.

Serialization

There are two main ways of storing this information. Both use a key-value model with the ttl value as the key. However, they differ in what's used as the key.

1: Outpoint to TTL

<Outpoint><TTL>

Field  Type     Size
TXID   [32]byte 32
index  uint32   4
TTL    int32    4

40 Bytes per entry

2: TXO Block Index to TTL

TXO Block index is defined by:

The index of the TXO in context of all the TXOs in the creating block (with Unspendables and same block spend TXOs removed).

<Block height><TXO Block Index><TTL>

Field            Type   Size
Height           int32  4
TXO Block Index  int32  4
TTL              int32  4

12 Bytes per entry

1 is more straightforward but is a lot more space consuming. 2 is much more space efficient but is more tricky to implement as it is a more invasive change.

I guess the values could also be serialized with the variable length integer serialization format, saving on more space.

Implementation

Implementation is probably done easiest by incorporating it as a indexer in both utcd and bitcoind.

[dergoegge]

In 1. we could consider using only the first 8 bytes (not sure how many bytes would be good here @adiabat) of the txid in the outpoint. There should be almost no collisions here and even if there are, i would assume they don't have a huge impact on the caching.
With that 1. would be 16 byte per entry instead of 40.

[kcalvinalvin]

I don't think they happen just normally but if someone is looking to make a collision, it wouldn't be too hard. I guess the question is if its ok if there are collisions? This isn't consensus so at best someone will just make you download a bit more or keep a bit more.

Also updated (2) to include block height.

[kcalvinalvin]

Just another though but since all three fields for (2) is tiny, we'd save a lot of space if we use varint encoding. Maybe 5~8 bytes on average?