BRC ID
74
Discussion
Thanks for creating ths spec; I found the TSC spec quite dissatisfactory and it seems others did too.
My understanding is that the BUMP format is intended for use when SPV wallets share merkle proofs with each other during transaction negotiation, and also for when SPV wallets receive proofs from miners or third party services. It is also likely a useful format for a wallet to save proofs in its own database for later use. My comments below are with this is mind.
After digesting the spec, my first impression was that there should be no need for the flags parameter if approached a little differently. Further, the spec does not cover ambiguities, such as if an offset appears twice in a level, and an unknown flag. The included sample code, and reference implementation at https://github.com/libsv/go-bc, does not appear to handle some problematic scenarios. I haven't learnt the go language so please be kind if I have misunderstood the code!
First, the flags parameter. I cannot understand the distinction between client and non-client txids. A valid BUMP should be considered a proof for all transaction hashes in the first level. The hashes in other levels are obviously not transaction hashes. So why distinguish? Secondly, if the block transaction count is provided (similarly to the height), then it is always known if a given hash should be duplicated or not, removing the need for that flag too. Specifying the tx count makes the "tree height" entry redundant, so perhaps it should replace it? That was my initial idea. I believe in all cases this would make a more compact format (certainly in JSON, and almost certainly in binary too). The block transaction count can be useful metadata for a wallet too.
Next, as BUMPs are being provided to wallets from untrusted third parties, an implementation should be able to detect malicious or erroneous data; indeed the entire BUMP data structure should be verifiable. Implementations are helped if the spec indicates how ambiguities and corner cases should be handled (I give a list of these and my suggested handling below). The sample code does not appear to handle leaves in the BUMP that are unnecessary for the proof (and therefore are unchecked) or the same offset being present more than once with different hashes.
The spec discusses a merge operation; this is useful for a wallet merging BUMPs for different groups of transactions in the same block. Consider the combinePaths function shown in the spec, merging two bumps. Suppose at least one of them is a malicious BUMP, that proves what it was supposed to prove, but has ambiguous or extraneous leaves included, so its malicious nature is not initially apparent. I believe that merging the BUMPs as shown, because of the problem of ambiguous and/or conflicting leaves overriding each other, is likely to result in a BUMP that no longer correctly proves the full set of transaction hashes that A and B originally correctly proved separately. Further, resolving / detecting this during the merge operation is non-trivial.
A final thing to worry about is that of "phantom" merkle branches, possible because of Satoshi's unfortunate decision to duplicate the last hash when there is an odd number in a level. For example, a block with 6 transactions, and a wallet asking for proof of inclusion of the last transaction, can be fooled by someone creating a BUMP for an 8-transaction block with the same first 6 transacactions, and tx 7 a duplicate of tx 5 and tx 8 a duplicate of tx 6. This fake BUMP would give the correct merkle root and therefore I believe be accepted by the sample code. An implementation should be able to detect if it is being lied to like this. The TSC spec discusses this point and how to detect it.
Here are scenarios I think a wallet should detect, and my suggested handling:
- Offsets out of range in a level. REJECT
- An offset appearing more than once in a level. REJECT if the hashes differ, ACCEPT redundant duplicates but remove them.
- Presence of a phantom merkle branch. REJECT
- Leaves in the path that do not contribute to proving any of the tx hashes in the base level. REJECT the bump, unless the leaves are redundant in that they match the combined hash of the two hashes in the level below, in which case ACCEPT them but remove them from the bump.
- BUMP path of wrong depth: REJECT
In summary, I think it is best, and arguably necessary, for an implementation to fully validate the entirety of the data in the BUMP. I do not know, but I doubt, if that is possible with the current spec without a transaction count. If the transaction count is included, then it is possible to fairly easily verify everything in the BUMP and implement the handling I describe above.
In passing, as the 2nd point is sometimes missed, note a bump only proves inclusion of a tx in a block if
- the merkle root of the proof matches the merkle root of a block header (at the claimed height if it helps lookup)
- the tx is a valid bitcoin tx (so the hash isn't arbitrary), which proves the tree is not truncated
That leaves a final problem: how to prove the transaction count? The transaction count is proven (if the phantom branch check is implemented) by including the final transaction in the block in the proof of every BUMP. This renders the explicit tx count unnecessary in the format, as it is one plus the largest offset in the first row of the path, saving a few more bytes. However it adds more hashes to the BUMP if the final transaction is not one that was originally wanted (but likely only for a few levels). Considering the elimination of the flags, I suspect a BUMP in this format is not much different on average to a BUMP in the spec format (binary and JSON), and will compare increasingly favourably as the number of transactions in the BUMP rises.
To summarise, this is my suggested format - not too different to the current one:
- block height (as now), followed by
- the path: a list of levels. Each level: a varint count, followed by (offset, hash) pairs.
with the understanding that the last TX in the block is always included. Then the tx count is determined to be 1 plus the maximum offset in the first level of the path, which in turn determines the length of the path.
This suggestion has the benefit of being a simpler format, therefore likely a simpler implementation, and being robust to various attacks. It's main downside is it's not the existing spec, so not implemented in ref wallet, Arc, or typescript library 😃
I have written a fully-tested implementation in Python in the bitcoinX repo; the entire code is quite tight and about 270 lines. It includes all the verifications and checks I mention above, and can read / write to / from binary and JSON. It also includes code to create a BUMP given the tx hashes of a block and a desired subset. The merge operation is also implemented. See https://github.com/kyuupichan/bitcoinX/blob/master/bitcoinx/merkle.py
I will implement the spec as-is so I can compare sizes properly, but Daniel was pressuring me to comment more quickly :)