utreexo block outline flow

[adiabat]

To help IBD we can hard-code 2 hashes into the node binary. This is sort of like how assumevalid says "there are no invalid signatures up to this hash", except it's even less trusted (whatever that means) because the node will still check everything.

The 2 hashes are both merkle roots. One that's a root of roots, committing to utreexo roots at previous block heights, so that nodes can do parallel block validation. That's to be described elsewhere.

The hash we're talking about here is the outline root.

type MsgOutline struct {
    BlockHash *chainhash.Hash // hash of the bitcoin block being outlined
    Height  int32
    NumAdds uint64
    Dels []uint64
}

BlockHash and Height are probably not needed; when sent over the wire we should know what block it's talking about already, so it's just numadds, numdels, and a bunch of dels. We should try compressing these because it's probably very compressible.

How the commitment is structured in the binary:

when building the binary, pick a recent-ish block. So if we're at block 871234 pick 850000 or so. Then in the binary, store:

blockhash : outlineRoot

00000000000000000002a0b5db2a7f8d9087464c2586b546be7bce8eb53b8187 : 68198a0ba6b6cdec063eafb4798331fd017f5503ca014bc327ba91722ae56df6

The first being blockhash of block 850000, the next being the merkle root for all the outlines from 1 to 850000. Unlike utreexo we don't have perfect trees so we need to define some kind of padding out to 1048575, the next power of 2.

Each leaf is the hash of the serialized outline; it should probably have the bitcoin blockhash in there as well just in case, as that's something everyone using the outline should already know, so no extra data transfer is needed.

Use

When a node starts IBD, it can get headers first and check all the PoW. Once it's done with headers, it can see if a header it got matches the hard-coded blockhash:outlineRoot mapping. (It should!) It then can download outlines to help cache and plan out proof download. The outline request message is not in an INV message, it doesn't really fit INV as you're requesting a sequence of things, so it's more like getHeaders. The message is

type MsgGetOutline struct {
    BlockHeight int32
    SubTreeHeight  uint8
}

We can get away without a version message; as later binaries are released, we'll put more trees in. So there can be a tree from 1 to 850000, then a year later a tree from 850000 to 920000 etc. As long as these trees don't overlap, whatever height you request will be in a single hard-coded tree.

BlockHeight is the bitcoin block height of the (first) block you want outlines for.

SubTreeHeight is how tall of a subtree you want to get at once. 0 means you just want the outline for the block indicated by BlockHeight. 1 means you want 2 outlines: BlockHeight and BlockHeight+1. 2 means you want 4 outlines, 8 means you want 256, etc. I guess the max should be something reasonable, not more than a couple megabytes, probably under 16.

The bits of BlockHeight should end with as many 0s as SubTreeHeight. That is,
(BlockHeight >> SubTreeHeight) << SubTreeHeight == BlockHeight. If not, the server can hang up.

The server responds by sending an outline batch message. Fully deserialized, this looks like

type MsgOutlineBatch struct {
    StartHeight int32
    SubTreeHeight uint8
    Proof []chainhash.Hash
    Payload []MsgOutline
}

But for the serialization, we should try compressing Payload with zstd or something. Hopefully it's not too hard for the server? If it is, maybe we constrain SubTeeHeight to be either 0 or 10, and can pre-compress runs of 1024 outlines on disk server side. It just seems like it will compress extremely well, and it's probably worth it; the total size of all the uncompressed outlines could be around ~10KB per block, or getting towards 10GB total. It would still be fine to do it uncompressed, but it's just so many zero bits, and so many adjacent uint64 that differ by 1 or 2 bits, that I bet it would compress down to a few hundred MB.