How to decode merkle/transaction proof that Bitcoin SV software provides?

Question

How to decode merkle/transaction proof that Bitcoin SV software provides?

One can ask Bitcoin SV not to provide a proof that a given transaction was included in a block. E.g.:

➜ bitcoin-cli gettxoutproof '["ea32120687851afe3418ab3642af94a4c69684e4b87f8a529807489e09d74ec5"]'
00008020044b32cb5a9d9c5a4d8df9b7d3db277897cd3326900ffb0200000000000000009c34e7a224a4aab8df6a82bf29710a343e000ec5494348ff1a4cf028e55ec81035a1f85dbc10071870a3284fea2400000f98e8f40fdb92f5359abf62b6a56dc03adf7da95390635c2e5e4fafbbee3f753dc54ed7099e480798528a7fb8e48496c6a494af4236ab1834fe1a8587061232ea86f9873bc1bbb24ff46e666c5370ac4b51ca3f5a0ffd03e0713c7be7612e9f610f245966d85fa863a32038e349aaf1b63ccde8b89b395aa2494fa0540d11cf183ef019baee80e4f38fcf2fe3bc23619e3d6edec65dfd2ab452f186e922492ffb668dbc25e8be0c6050247399209dfdda4934cca52f02c399d0fd6dc97c23b4615d4e9ffb22c3de0b35e8dcecb3aa23007defa4ec8e105af05dc87108ded9dccc3b80e338ba14f4390cc5c775c7fba36590bd460f3601e64b8ab55cae0a71f1224f06f0b18a11596a37a49fab86c2a7764b92f114aacad9853b8bea7f23283076cefc60d6f7f600e8d1e32342e8169e49523917c6b9b8ad7931edff1f876ae7c0a149ee3ea75ba806c441f772cbd7fb326f4b0f13b891a364a7399805749bc38016016d6a64aefe4bc7fe48f4ca8bd6f766edb0fdb183d9ba0df7f58dd280692da7dd94048aab0b5b0ebfc83066e85cc8d2cabb133739b872fb4312db5fad41e6e7d55fb7d9addfd810a561ed49634225cd88d2a04638fdc8efaf0d6044e78bdf09455aab9b4d25a5c60cac2376237b064b10b88081f52d241fff4a2d35b464f504ffdf0000

Proof can be verified using the verifytxoutproof RPC command, but let’s say I would like to verify the proof in a custom application that does not have access to a Bitcoin node.

How can I decode the proof HEX blob? What data is part of it and how can I get block, merkle proof and transaction information from it?

Submit an answer See answers Share on Twitter Share on Facebook

Answer 1

Accepted Answer

Accepted: Here is the original code...

If that can help, take a look at the original code for the function gettxoutproof(), this is the function that takes a json array of txids and a block hash and returns a string that is a serialized, hex-encoded data for the proof. It will allow you to understand how the hex encoded version is constructed so you can do the opposite to decode it.

https://github.com/bitcoin/bitcoin/pull/5199/files#diff-52257e4c1cedbf5e302f183065cab880R197

And here you can find the code for the verifytxoutproof() function:

https://github.com/bitcoin/bitcoin/pull/5199/files#diff-52257e4c1cedbf5e302f183065cab880R277

You will also find a very good introduction with some ready-made code for merkle trees in this article:

https://hackernoon.com/merkle-tree-introduction-4c44250e2da7

Answer 2

For lazy people (like me:))

Thanks @Zhell for your answer, which allowed me to decode the proof. For anyone else that might be looking for this, the structure of the proof is the following:

Block header (80 bytes)
Number of transactions in the block (unsigned int, 4 bytes, little endian)
Number of hashes (varint, 1 - 3 bytes)
Hashes (N * 32 bytes, little endian)
Number of bytes of flag bits (varint, 1 - 3 bytes)
Flag bits (little endian)

Flag bits indicate which nodes in the merkle tree are relevant for the proof (depth-first). Hashes are also listed in a depth-first fashion. This is relevant for proofs that cover more than one transaction.

Example:

$ ./src/bitcoin-cli gettxoutproof '["1a5ef521d112853d01afed4c1bc7e2e0b1edd9e3195214a3fb14e5866519b1e3", "e8de2d2c2c8b0593a5e2fec218c5c2f38d17cdde045742482a1c4554a3cd1b14"]'
00004020e2ac770a4f511b7ed2f3b638fe12d39ff52b8ced104d360500000000000000006f5ca47842fdd12f46a274ce7060c701d0c1fcff294a826e19b88e8f3dcdbca8f560135e8b64051816587c9c1f0100000bc21da39408e165a8368a7df46a17af25b4c5e3778b45222e48da632412b3be56e3b1196586e514fba3145219e3d9edb1e0e2c71b4cedaf013d8512d121f55e1ae120e954338e4d63d0a446a466b4ec548704366a89c2513c0c47818e4f8af8fa141bcda354451c2a48425704decd178df3c2c518c2fee2a593058b2c2c2ddee80ebc68aa38c161fcbf32f336b9d06feb652893be3326b0fd755cf61e575a56d7cb6b4944a2e74e3fdb583885c9dd4849ab2fd974207d9693a3062d9ba5eb0ea1b7c2d9841297396526c43af19fa8e67f3a6c07f9c8333eda575556df0e8b86a65982f24022336589fae3d56d69d73474024ced4f3a63c7205623d5bd22daf8a58e69b4748539fcdc24e0241f8231278b560340a3eb112f2fd041dc7bd1a0f6ddc37b916c24b0f96a1e9e13b4ffc7ad9c3805cadb91520435821edd439ca70198c92187deb1dde075366006d963632a0fd1ca510b362bbd6cf1805ac70becd3d303ff2d00

is decoded as

Block header:
00004020e2ac770a4f511b7ed2f3b638fe12d39ff52b8ced104d360500000000000000006f5ca47842fdd12f46a274ce7060c701d0c1fcff294a826e19b88e8f3dcdbca8f560135e8b64051816587c9c

Number of transactions:
1f010000 # Decimal: 287

Number of hashes:
0b #  Decimal: 11

Hashes:
c21da39408e165a8368a7df46a17af25b4c5e3778b45222e48da632412b3be56
e3b1196586e514fba3145219e3d9edb1e0e2c71b4cedaf013d8512d121f55e1a
e120e954338e4d63d0a446a466b4ec548704366a89c2513c0c47818e4f8af8fa
141bcda354451c2a48425704decd178df3c2c518c2fee2a593058b2c2c2ddee8
0ebc68aa38c161fcbf32f336b9d06feb652893be3326b0fd755cf61e575a56d7
cb6b4944a2e74e3fdb583885c9dd4849ab2fd974207d9693a3062d9ba5eb0ea1
b7c2d9841297396526c43af19fa8e67f3a6c07f9c8333eda575556df0e8b86a6
5982f24022336589fae3d56d69d73474024ced4f3a63c7205623d5bd22daf8a5
8e69b4748539fcdc24e0241f8231278b560340a3eb112f2fd041dc7bd1a0f6dd
c37b916c24b0f96a1e9e13b4ffc7ad9c3805cadb91520435821edd439ca70198
c92187deb1dde075366006d963632a0fd1ca510b362bbd6cf1805ac70becd3d3

Number of bytes in flag  bits:
03 # Decimal: 3

Flag bits:
ff2d00

How to decode merkle/transaction proof that Bitcoin SV software provides?

Accepted: Here is the original code...

For lazy people (like me:))

Submit an Answer