TSC Proof Format with Heights
Tone Engel (tone@kizmet.org), TonesNotes
Abstract
This is an argument for using block height as the standard for indexing block headers within merkle proofs.
It argues for a backward compatible protocol extension in the short term and through deprecation, a long term reduction in the space cost of a usable local copy of block headers by a factor of two.
The referenced specification, the "Spec": TSC Merkle proof standardised format
Motivation
The Spec implies that a compatible implementation support the capability to lookup block hash and merkle root values, to confirm that they correspond to actual mined blocks.
The Project Babbage team has implemented a block header management system called Chaintracks primarily to support validating merkle proofs as defined in the Spec.
We have a focus on space efficiency as we target the full range of client application deployment scenarios, including mobile and IoT.
You hear that a full set of block headers is only 50MB and only grows at 4MB per year - and this is true - but it refers to the serialized binary space required for just the headers, without the indices required to implement the Spec.
Because the required indices are hash values (merkle root and block header hash), which together make up 64 of the 80 block header bytes, it is likely unavoidable that any implementation will be approximately the size of the headers themselves: To turn a hash into a height, the indices must list all the hash values paired with their height values.
While it is possible to use partial indices and trade index size for IO operations, the indices are not actually needed at all. As Elon says, "the best part is no part."
Stepping Back: What's the Point of Merkle Proofs?
The purpose of a merkle proof is to prove that a particular bit of data, a bitcoin transaction, was recorded at a particular location in the block chain.
The nodes in the proof enable the computation of what the merkle root should be for a block containing the transaction at a particular index position.
To complete the proof, it must be verified that the computed merkle root matches the actual merkle root of the target block.
Being given a merkle root value as part of the proof does NOT complete the proof.
The only thing that completes the proof is to confirm from a trusted copy of block headers that one exists with the computed merkle root value.
Being given a merkle root, block hash, or block header as part of the proof is only useful as an identifier for which block header to check in the trusted copy. If a matching block header isn't found, the proof is invalid, no matter what additional target values are provided.
Furthermore, if the trusted copy includes a merkle root index, then proof can be completed directly from the computed merkle root value: Look it up in your own index, if it is found, the proof is valid and the block is identified.
It is therefore the case, that the existing target and targetType values in a proof per the Spec are unnecessary.
It may actually be the case, that the only useful targetType would be height. With a height value, no indices are needed at all, the target block header can be found directly since all headers are exactly 80 bytes long. The trusted copy does not require any indices.
Specification
1. Add height as a supported targetType
height as a supported targetTypeIn "Binary form", proofs reserve two bits of "flags" bytes (bits 1 and 2) to identify what the "JSON form" calls the targetType of the proof.
Here are the current and proposed values for targetType:
Block Hash
existing
0
'hash' (default)
32 bytes
64 hex chars
Block Header
existing
1
'header'
80 bytes
160 hex chars
Merkle Root
existing
2
'merkleRoot'
32 bytes
64 hex chars
Height
new
3
'height'
Bitcoin VarInt
integer
2. Deprecate targetType Other Than height
targetType Other Than heightAs discussed in Motivation above, the existing target types and target values are irrelevant to being able to complete a merkle proof given the remaining values.
Implementations
The Project Babbage Chaintracks package currently implements the Spec with this extension.
A comparison of Chaintracks and the Pulse block header packages is listed under References.
References
The "Spec": TSC Merkle proof standardised format
Last updated