> For the complete documentation index, see [llms.txt](https://bsv.brc.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bsv.brc.dev/transactions/0074.md). # BSV Unified Merkle Path (BUMP) Format Darren Kellenschwiler (), Deggen\ Tone Engel (), TonesNotes\ Ty Everett ()\ Damian Orzepowski ()\ Arkadiusz Osowski () ## Abstract We propose the BSV Unified Merkle Path format in both binary and JSON encoding optimized for generation by transaction processors, and also happens to be convenient for proof validating clients. At a high level the format encodes a number of txids which all exist within one particular block, along with each of their merkle paths and the blockHeight. The blockHeight is encoded first, followed by level 0 of the Merkle tree, which includes the txids of interest, and their corresponding siblings. Thereafter we encode each level of the tree thereafter, but only include branches of the tree which are required to calculate the Merkle root the txids which are of interest to us. For example if we only have one txid of interest, we will include it and its sibling, followed by one leaf per level of the tree. ## Copyright This BRC is licensed under the Apache License 2.0. ## Visualization [BUMP Showcase](https://bitcoin-sv.github.io/showcase-merkle-paths/) can help form an understanding of how BUMP works to encode all necessary data. ## Motivation Several formats have made their own improvements to the original format which was returned by a Bitcoin node via json-rpc method `getmerkleproof`. Improvements include: * [BRC-10](/transactions/0010.md) a TSC creation which was subsequently returned by the node's json-rpc method `getmerkleproof2` * [BRC-11](/transactions/0011.md) removing the need for specifying targets, replacing with height to improve validation speed. * [BRC-58](/transactions/0058.md) removal of all extraneous data to minimize data size. * [BRC-61](/transactions/0061.md) introduction of a compound path encoding which allows representation of multiple paths within the same block. The purpose of defining this new specification is to capture the incremental improvements under one spec which encapsulates the pros of each, and removes the cons. This new spec should allow: * Inclusion of height makes lookup extremely fast while only adding maximum 9 bytes to the data size. * Multiple paths can be expressed in the same data model. * One format for everything, so that there is no need to convert from single to compound path. * Size optimization allowing us to skip encoding of far right leaves when duplication of working hash would suffice. ## Binary Encoding ### Global The top level encoding specifies a block height and a tree height. | Field | Description | Size | | ------------ | ---------------------------------------------------------------- | --------- | | block height | `VarInt` block height in which the transactions are encapsulated | 1-9 bytes | | tree height | The height of the Merkle Tree in this block, max 64 | 1 byte | ### Level Thereafter the number of leaves at the top height is specified, and the leaves for this height follow. | Field | Description | Size | | ------- | ---------------------------------------- | ----------------- | | nLeaves | `VarInt` number of leaves at this height | 1-9 bytes | | leaves | Each leaf encoded in the format below. | sum of leaf sizes | ### Leaf Once all leaves at this height have been specified, an implied increment of the height in the tree occurs and we specify the number of leaves in the next level up, and so on until we have specified the leaves at level (treeHeight - 1) at which point we stop. We do not need to encode the root hash as it is always calculable. | Field | Description | Size | | ------ | --------------------------------------------------------------------- | ------------- | | offset | `VarInt` offset from left hand side within tree | 1-9 bytes | | flags | Flags can be `00`, or `01`, or `02` - detailed meaning in table below | 1 byte | | hash | A hash representing a txid, sibling hash, or a branch | 0 or 32 bytes | ### Flags The first flag is to indicate whether or not to duplicate the working hash or use the following data. The second flag indicates whether the hash is a relevant txid or just a sibling hash. | bits | byte | meaning | | --------- | ---- | --------------------------------------- | | 0000 0000 | 00 | data follows, not a client txid | | 0000 0001 | 01 | nothing follows, duplicate working hash | | 0000 0010 | 02 | data follows, and is a client txid | ### Hex String This is the encoding the current `@bsv/sdk` `MerklePath` produces for this proof. `combine` finishes by calling `trim`, which omits nodes that can be calculated from the leaves already stored. Level 1 has no leaves: both of its nodes are parents of the level 0 pairs, so they are not stored. `computeRoot` reconstructs them. The format still accepts a BUMP that stores those nodes; this example is the trimmed form. ``` fe8a6a0c000c04fde80b0011774f01d26412f0d16ea3f0447be0b5ebec67b0782e321a7a01cbdf7f734e30fde90b02004e53753e3fe4667073063a17987292cfdea278824e9888e52180581d7188d8fdea0b025e441996fc53f0191d649e68a200e752fb5f39e0d5617083408fa179ddc5c998fdeb0b010001fdfb020101fd7c010093b3efca9b77ddec914f8effac691ecb54e2c81d0ab81cbc4c4b93befe418e8501bf01015e005881826eb6973c54003a02118fe270f03d46d02681c8bc71cd44c613e86302f8012e00e07a2bb8bb75e5accff266022e1e5e6e7b4d6d943a04faadcf2ab4a22f796ff30116008120cafa17309c0bb0e0ffce835286b3a2dcae48e4497ae2d2b7ced4f051507d010a00502e59ac92f46543c23006bff855d96f5e648043f0fb87a7a5949e6a9bebae430104001ccd9f8f64f4d0489b30cc815351cf425e0e78ad79a589350e4341ac165dbe45010301010000af8764ce7e1cc132ab5ed2229a005c87201c9a5ee15c0f91dd53eff31ab30cd4 ``` ### Bytewise Breakdown ```javascript fe8a6a0c00 // blockHeight (813706), VarInt 0c // treeHeight (12), byte // Level 0, client TXIDs and sibling TXIDs (TXIDs required only to compute internal tree hash). 04 // nLeaves, VarInt fde80b // offset, VarInt 00 // flags 11774f01d26412f0d16ea3f0447be0b5ebec67b0782e321a7a01cbdf7f734e30 // hash fde90b // offset VarInt 02 // flags = CLIENT_TXID 004e53753e3fe4667073063a17987292cfdea278824e9888e52180581d7188d8 // hash fdea0b // offset VarInt 02 // flags = CLIENT_TXID 5e441996fc53f0191d649e68a200e752fb5f39e0d5617083408fa179ddc5c998 // hash fdeb0b // offset VarInt 01 // flags = DUPLICATE_WORKING_HASH // Level 1, internal merkle tree hashes. // Both nodes at this height are computable from the level 0 children, so none are stored. 00 // nLeaves, VarInt // Level 2, internal merkle tree hashes 01 // nLeaves VarInt at level 2 fdfb02 // offset VarInt 01 // flags = DUPLICATE_WORKING_HASH // Level 3, internal merkle tree hashes 01 // nLeaves VarInt at level 3 fd7c01 // offset VarInt (three hundred and eighty) 00 // flags 93b3efca9b77ddec914f8effac691ecb54e2c81d0ab81cbc4c4b93befe418e85 // hash // Level 4, internal merkle tree hashes 01 // nLeaves VarInt at level 4 bf // offset VarInt 01 // flags = DUPLICATE_WORKING_HASH // Level 5, internal merkle tree hashes 01 // nLeaves VarInt at level 5 5e // offset VarInt 00 // flags 5881826eb6973c54003a02118fe270f03d46d02681c8bc71cd44c613e86302f8 // hash // Level 6, internal merkle tree hashes 01 // nLeaves VarInt at level 6 2e // offset VarInt 00 // flags e07a2bb8bb75e5accff266022e1e5e6e7b4d6d943a04faadcf2ab4a22f796ff3 // hash // Level 7, internal merkle tree hashes 01 // nLeaves VarInt at level 7 16 // offset VarInt 00 // flags 8120cafa17309c0bb0e0ffce835286b3a2dcae48e4497ae2d2b7ced4f051507d // hash // Level 8, internal merkle tree hashes 01 // nLeaves VarInt at level 8 0a // offset VarInt 00 // flags 502e59ac92f46543c23006bff855d96f5e648043f0fb87a7a5949e6a9bebae43 // hash // Level 9, internal merkle tree hashes 01 // nLeaves VarInt at level 9 04 // offset VarInt 00 // flags 1ccd9f8f64f4d0489b30cc815351cf425e0e78ad79a589350e4341ac165dbe45 // hash // Level 10, internal merkle tree hashes 01 // nLeaves VarInt at level 10 03 // offset VarInt 01 // flags = DUPLICATE_WORKING_HASH // Level 11, internal merkle tree hashes 01 // nLeaves VarInt at level 11 00 // offset VarInt 00 // flags af8764ce7e1cc132ab5ed2229a005c87201c9a5ee15c0f91dd53eff31ab30cd4 // hash ``` ## JSON Encoding In the JSON encoding - we start with a height of a block in which transactions from BUMP are mined. A path Array index corresponds to the height within the Merkle tree, so we start with level 0 which includes all of the txid's of interest to a client in this block and the txid's of additional transactions required to begin the merkle root computation. Within each array element we contain an array of one or more leaves which are specified as a leaf. Within the leaf itself we have am `offset` - the only required parameter, along with optional `hash`, `txid` and `duplicate`. The `hash` is a hex string encoding reversed bytes of the hash at this position in the Merkle tree, the `duplicate` true is a boolean and represents a "no data" for this position, this is to encode for the right hand side of the merkle tree. The expected behavior is for a parser to duplicate the working hash in this case, therefore no further data is required. A `txid` boolean is included if true - to indicate whether the hash in question is considered a relevant txid to the receiving party, rather than just a sibling hash needed to calculate the root. ### JSON Example Level 1 is an empty array for the same reason as in the binary example: `@bsv/sdk` does not store those two nodes. The path index is still the tree height, so the empty array stays at index 1. ```json { "blockHeight": 813706, "path": [ [ { "offset": 3048, "hash": "304e737fdfcb017a1a322e78b067ecebb5e07b44f0a36ed1f01264d2014f7711" }, { "offset": 3049, "txid": true, "hash": "d888711d588021e588984e8278a2decf927298173a06737066e43f3e75534e00" }, { "offset": 3050, "txid": true, "hash": "98c9c5dd79a18f40837061d5e0395ffb52e700a2689e641d19f053fc9619445e" }, { "offset": 3051, "duplicate": true } ], [], [ { "offset": 763, "duplicate": true } ], [ { "offset": 380, "hash": "858e41febe934b4cbc1cb80a1dc8e254cb1e69acff8e4f91ecdd779bcaefb393" } ], [ { "offset": 191, "duplicate": true } ], [ { "offset": 94, "hash": "f80263e813c644cd71bcc88126d0463df070e28f11023a00543c97b66e828158" } ], [ { "offset": 46, "hash": "f36f792fa2b42acfadfa043a946d4d7b6e5e1e2e0266f2cface575bbb82b7ae0" } ], [ { "offset": 22, "hash": "7d5051f0d4ceb7d2e27a49e448aedca2b3865283ceffe0b00b9c3017faca2081" } ], [ { "offset": 10, "hash": "43aeeb9b6a9e94a5a787fbf04380645e6fd955f8bf0630c24365f492ac592e50" } ], [ { "offset": 4, "hash": "45be5d16ac41430e3589a579ad780e5e42cf515381cc309b48d0f4648f9fcd1c" } ], [ { "offset": 3, "duplicate": true } ], [ { "offset": 0, "hash": "d40cb31af3ef53dd910f5ce15e9a1c20875c009a22d25eab32c11c7ece6487af" } ] ] } ``` ## Calculating the Merkle Root from a BUMP Parse the hex with `MerklePath` from `@bsv/sdk`. `fromHex` reads the binary encoding, `computeRoot` calculates the Merkle root for any level-0 hash in the path, and `toHex` writes it back. An empty level is not a missing sibling: `computeRoot` rebuilds a node when both of its children are present, and when a leaf is marked `duplicate`. ```ts import { MerklePath } from '@bsv/sdk' const bumpHex = 'fe8a6a0c000c04fde80b0011774f01d26412f0d16ea3f0447be0b5ebec67b0782e321a7a01cbdf7f734e30fde90b02004e53753e3fe4667073063a17987292cfdea278824e9888e52180581d7188d8fdea0b025e441996fc53f0191d649e68a200e752fb5f39e0d5617083408fa179ddc5c998fdeb0b010001fdfb020101fd7c010093b3efca9b77ddec914f8effac691ecb54e2c81d0ab81cbc4c4b93befe418e8501bf01015e005881826eb6973c54003a02118fe270f03d46d02681c8bc71cd44c613e86302f8012e00e07a2bb8bb75e5accff266022e1e5e6e7b4d6d943a04faadcf2ab4a22f796ff30116008120cafa17309c0bb0e0ffce835286b3a2dcae48e4497ae2d2b7ced4f051507d010a00502e59ac92f46543c23006bff855d96f5e648043f0fb87a7a5949e6a9bebae430104001ccd9f8f64f4d0489b30cc815351cf425e0e78ad79a589350e4341ac165dbe45010301010000af8764ce7e1cc132ab5ed2229a005c87201c9a5ee15c0f91dd53eff31ab30cd4' const bump = MerklePath.fromHex(bumpHex) bump.blockHeight // 813706 bump.path[1] // [] bump.computeRoot('304e737fdfcb017a1a322e78b067ecebb5e07b44f0a36ed1f01264d2014f7711') // '57aab6e6fb1b697174ffb64e062c4728f2ffd33ddcfa02a43b64d8cd29b483b4' bump.computeRoot('d888711d588021e588984e8278a2decf927298173a06737066e43f3e75534e00') // '57aab6e6fb1b697174ffb64e062c4728f2ffd33ddcfa02a43b64d8cd29b483b4' bump.computeRoot('98c9c5dd79a18f40837061d5e0395ffb52e700a2689e641d19f053fc9619445e') // '57aab6e6fb1b697174ffb64e062c4728f2ffd33ddcfa02a43b64d8cd29b483b4' bump.toHex() // bumpHex ``` ## Merging A note on compounding multiple BUMPs together. The first check should always be the blockHeight - ensure it matches. The second check is the root. Each BUMP calculates its root, and if they don't match - you cannot combine them. If they match then the process is a simple inclusion of all leaves, dropping duplicates. `MerklePath.combine` performs those checks. It then calls `trim`, which drops a stored node once both of its children are in the path. Each proof below still carries the level-1 sibling it cannot compute on its own. After `combine`, that level is empty and `toHex` matches the encoding above. ```ts import { MerklePath } from '@bsv/sdk' const blockHeight = 813706 const txid2 = 'd888711d588021e588984e8278a2decf927298173a06737066e43f3e75534e00' const txid3 = '98c9c5dd79a18f40837061d5e0395ffb52e700a2689e641d19f053fc9619445e' const root = '57aab6e6fb1b697174ffb64e062c4728f2ffd33ddcfa02a43b64d8cd29b483b4' const compound = MerklePath.fromHex( 'fe8a6a0c000c04fde80b0011774f01d26412f0d16ea3f0447be0b5ebec67b0782e321a7a01cbdf7f734e30fde90b02004e53753e3fe4667073063a17987292cfdea278824e9888e52180581d7188d8fdea0b025e441996fc53f0191d649e68a200e752fb5f39e0d5617083408fa179ddc5c998fdeb0b010001fdfb020101fd7c010093b3efca9b77ddec914f8effac691ecb54e2c81d0ab81cbc4c4b93befe418e8501bf01015e005881826eb6973c54003a02118fe270f03d46d02681c8bc71cd44c613e86302f8012e00e07a2bb8bb75e5accff266022e1e5e6e7b4d6d943a04faadcf2ab4a22f796ff30116008120cafa17309c0bb0e0ffce835286b3a2dcae48e4497ae2d2b7ced4f051507d010a00502e59ac92f46543c23006bff855d96f5e648043f0fb87a7a5949e6a9bebae430104001ccd9f8f64f4d0489b30cc815351cf425e0e78ad79a589350e4341ac165dbe45010301010000af8764ce7e1cc132ab5ed2229a005c87201c9a5ee15c0f91dd53eff31ab30cd4' ) const upper = compound.path.slice(2).map(level => level.map(leaf => ({ ...leaf }))) const proofOfTxid2 = new MerklePath(blockHeight, [ [ { offset: 3048, hash: '304e737fdfcb017a1a322e78b067ecebb5e07b44f0a36ed1f01264d2014f7711' }, { offset: 3049, txid: true, hash: txid2 } ], [ { offset: 1525, hash: '82520a4501a06061dd2386fb92fa5e9ceaed14747acc00edf34a6cecabcc2b26' } ], ...upper.map(level => level.map(leaf => ({ ...leaf }))) ]) const proofOfTxid3 = new MerklePath(blockHeight, [ [ { offset: 3050, txid: true, hash: txid3 }, { offset: 3051, duplicate: true } ], [ { offset: 1524, hash: '811ae75c80fecd27efff5ef272c2adf7edb6e535447f27a4087d23724f397106' } ], ...upper.map(level => level.map(leaf => ({ ...leaf }))) ]) proofOfTxid2.computeRoot(txid2) // root proofOfTxid3.computeRoot(txid3) // root proofOfTxid2.combine(proofOfTxid3) proofOfTxid2.path[1] // [] proofOfTxid2.computeRoot(txid2) // root proofOfTxid2.computeRoot(txid3) // root proofOfTxid2.toHex() // compound.toHex() ``` ## Implementations TypeScript - [`@bsv/sdk` in ts-stack](https://github.com/bsv-blockchain/ts-stack/tree/main/packages/sdk) Golang - [go-sdk](https://github.com/bsv-blockchain/go-sdk)\ Python - [py-sdk](https://github.com/bsv-blockchain/py-sdk) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation by asking a question. Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters: ``` GET https://bsv.brc.dev/transactions/0074.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.