3

The below text is copied from the Bitcoin Developer Reference at bitcoin.org:

If a block has three or more transactions, intermediate merkle tree rows are formed. The TXIDs are placed in order and paired, starting with the coinbase transaction’s TXID. Each pair is concatenated together as 64 raw bytes and SHA256(SHA256()) hashed to form a second row of hashes. If there are an odd (non-even) number of TXIDs, the last TXID is concatenated with a copy of itself and hashed. If there are more than two hashes in the second row, the process is repeated to create a third row (and, if necessary, repeated further to create additional rows). Once a row is obtained with only two hashes, those hashes are concatenated and hashed to produce the merkle root.

I'm trying to use this logic to recreate the merkle root for block #100000. There are 4 transactions in this block. I start by copying the transaction hash for the coinbase transaction and the one following back-to-back into a Sha256 calculator to get the hash. Then I hash that hash one more time: Sha256(sha256()). I repeat that procedure one more time with the second two transactions in the block. Finally, I repeat the procedure again using the resulting hashes to obtain the Merkle Root. Unfortunately, this doesn't tie to the Merkle Root shown in the block header at blockchain.info.

Can someone explain where I went wrong?

Thanks.

  • 1
    Perhaps include the intermediate hashes you're getting? That may give people a hint where you went wrong. – Pieter Wuille Jan 5 '18 at 22:09
  • I suspect you are hashing the transaction ID as a string rather than as bytes – MeshCollider Jan 5 '18 at 22:14
  • Yes, @MeshCollider you are right. Is there a way to easily convert to bytes? – Adam Smith Jan 7 '18 at 1:35
  • I doubt there are websites which take bytes input to sha256, best approach is to use python or another language and convert the string to bytes before input to the sha256 – MeshCollider Jan 7 '18 at 2:11
1

You have to byte-swap the transaction ID's before hashing them, hash each child node, and byte-swap the final hashed hex value.

Transaction 1 (Coibase Transaction) 8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87

To Byteswap it you can use:

a = "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87" "".join(reversed([a[i:i+2] for i in range(0, len(a), 2)])) @Greg Hewgill

Byteswapped = 876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148c

Transaction 2 fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4 Byteswapped = c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff

You want to concatenate the byte-swapped transaction values of 1 and 2. Transaction 1 goes first.

876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff

To hash this hex string you can use the following code running Python in your command terminal:

import hashlib

transaction12_hex = "876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff"

transaction12_bin = transaction12_hex.decode('hex')

hash = hashlib.sha256(hashlib.sha256(transaction12_bin).digest()).digest()

hash.encode('hex_codec')

15b88c5107195bf09eb9da89b83d95b3d070079a3c5c5d3d17d0dcd873fbdacc

Transaction 3 6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4 Byteswapped = c46e239ab7d28e2c019b6d66ad8fae98a56ef1f21aeecb94d1b1718186f05963

Transaction 4 e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d Byteswapped = 1d0cb83721529a062d9675b98d6e5c587e4a770fc84ed00abc5a5de04568a6e9

If you do the same thing for transaction 3 and 4 the final hash is: 49aef42d78e3e9999c9e6ec9e1dddd6cb880bf3b076a03be1318ca789089308e

Our last step is to combine the final hashed value of 1 & 2 and 3 & 4 and double hash it and byte-swap it.

Our answer is f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766 the Merkle Root.

  • My answer is not coming. I converted this 876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff to binary and double hashed it using passwordsgenerator.net/sha256-hash-generator – Suraj Jain Jul 13 '18 at 12:59
  • Unfortunately using an online SHA generator doesn't seem to work for double hashing and I'm trying to figure out why. I will keep you in the loop. I think it has to do with how it's encoding and decoding data. – Ben Stolman Jul 14 '18 at 1:04
  • because they maybe do not do it byte wise, 87, is one byte, and sha 256 input byte wise, but they might turn 8 into one byte (as it is a char) and so on. – Suraj Jain Jul 14 '18 at 9:36
  • That very well could be - I just asked threw out the question to the masses and I'm awaiting a response....bitcoin.stackexchange.com/questions/77208/… – Ben Stolman Jul 14 '18 at 17:42
  • @ Suraj Jain bitcoin.stackexchange.com/questions/5671/…... if you are going to use an online generator use anyhash.com/sha256?hello... and checkmark the hex box. I didn't completely understand the more formal answer. – Ben Stolman Jul 14 '18 at 21:01
0

I think the errors is the building the hash correctly and I was a same problem, now I want shared the my experience.

For build the hash I have used this good library c++/java.

I will try to explain myself with simple code.

This is the hash of transaction the genesis block

string versionRawTransaction = "01000000";
string numbarTransactionInput = "01";
string output = "0000000000000000000000000000000000000000000000000000000000000000ffffffff";
string scriptLenght = "4d";
string scriptSing = "04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73";
string sequences = "ffffffff";
string numbarTransactionOutput = "01";
string cAmmount = "00f2052a01000000";
string publicKeyScriptLenght = "43";
string publicKeyScript = "4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac";
string lockTime = "00000000";

The complete hash is 01000000010000000000000000000000000000000000000000000000000000000000000000FFFFFFFF4D04FFFF001D0104455468652054696D65732030332F4A616E2F32303039204368616E63656C6C6F72206F6E206272696E6B206F66207365636F6E64206261696C6F757420666F722062616E6B73FFFFFFFF0100F2052A01000000434104678AFDB0FE5548271967F1A67130B7105CD6A828E03909A67962E0EA1F61DEB649F6BC3F4CEF38C4F35504E51EC112DE5C384DF7BA0B8D578A4C702B6BF11D5FAC00000000

Whent you calculate the hash. can me get this hash 4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b

up to here everything is simple

The value bitcoin is converted to big endian convention but whent the hash is calculate the single type was converted to little endian.

Whi the real form transaction can me execute this passage

  1. convert the value form big-endian to little-endian
  2. Convert the value into Hex
  3. join all the propieties hex form in the correcto order
  4. Convert to the binary form the big string
  5. Apply the sha256
  6. convert the result to big-endian

I used the C++ and this operation they managed to do it thanks to the bitcoin libraries but if you used python you can use this example for calculate the hash.

to build the tree the steps are simple, just make sure you calculate the hash correctly, so I suggest you test first on the hash functions and then on the tree construction, to avoid unnecessary loss of time in trivial errors

ps: If you have the transaction script in raw format (if you read the information from the blk files) they are already converted to little-endian and therefore should not be converted any further. (depends on your deserialization process)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.