0

I've been trying to write my own merkle root script in PHP to help with my own understanding, but I've always struggled with recursion.

I've managed to write the function that will hash pairs of TXIDs, but I don't know how to make it keep calling itself so that I end up with only one hash left in the array.

http://pastebin.com/1C6sSbeE

  • Note: I realize this is a programming question, but I thought this merkle root code may prove to be helpful for others interested in trying the same thing. – inersha Apr 1 '16 at 11:06
1

Your script was a good attempt at this! I modified made it recursive with some very small changes.

Typically when designing a recursive function, it checks whether the state represents a complete computation, otherwise it runs some code and calls itself again. Your function was missing this part.

It also seemed to be computing the hashes incorrectly - the hashing operation is SHA256(SHA256($pair)). I refactored out the function binFlipByteOrder(), which only works on binary, so we can flip the hash before rendering it as hex.

<?php

function binFlipByteOrder($string) {
    return implode('', array_reverse(str_split($string, 1)));
}

function merkleroot($txids) {

    // Check for when the result is ready, otherwise recursion
    if (count($txids) === 1) {
        return $txids[0];
    }

    // Calculate the next row of hashes
    $pairhashes = [];
    while (count($txids) > 0) {
        if (count($txids) >= 2) {
            // Get first two
            $pair_first = $txids[0];
            $pair_second = $txids[1];

            // Hash them
            $pair = $pair_first.$pair_second;
            $pairhashes[] = hash('sha256', hash('sha256', $pair, true), true);

            // Remove those two from the array
            unset($txids[0]);
            unset($txids[1]);

            // Re-set the indexes (the above just nullifies the values) and make a new array without the original first two slots.
            $txids = array_values($txids);
        }

        if (count($txids) == 1) {
            // Get the first one twice
            $pair_first = $txids[0];
            $pair_second = $txids[0];

            // Hash it with itself
            $pair = $pair_first.$pair_second;
            $pairhashes[] = hash('sha256', hash('sha256', $pair, true), true);

            // Remove it from the array
            unset($txids[0]);

            // Re-set the indexes (the above just nullifies the values) and make a new array without the original first two slots.
            $txids = array_values($txids);
        }
    }

    return merkleroot($pairhashes);
}


$txids = array(
    'AB7ED423933FE5413DC51B1041A58FD8AF0CD70491B1CE607CB41DDDCE74A92B',
    'C763E59A79C9F1E626DDF1C3E9F20F234959C457FF82918F7B24E9D18A12DB99',
    '80EA3E647AEEF92973F5414E0CAA1721C7B42345B99ED161DD505ACC41F5516B',
    '1B72EEFD70CE0A362EC0CB48E2213274DF3C55F9DABD5806CDC087A335498CD3',
    '23E13370F6D59E2D7C7A9CA604B872312DE34A387BD7DECA2C8F4486F7E66173',
    '149A098D6261B7F9359A572D797C4A41B62378836A14093912618B15644BA402',
);

$txidsBEbinary = [];
foreach ($txids as $txidBE) {
    // covert to binary, then flip
    $txidsBEbinary[] = binFlipByteOrder(hex2bin($txidBE));
}
$root = merkleroot($txidsBEbinary);

echo bin2hex(binFlipByteOrder($root)) . PHP_EOL;
0

Here is some pseudo code how it could work:

List<Hash> hashList;     //Contains the transaction ids of all transactions in the block

Hash deriveMerkleRoot(List<Hash> hashList):
  while (hashList.size() > 1) {
    hashList = pairHashes(hashList);
  }
  return hashList[0];                                             // when only one hash is left, you've derived the merkle root

List<Hash> pairHashes(List<Hash> hashList):
  List<Hash> listOfPairedHashes = new List<Hash>();
  for(int i = 0; i < hashList.size(); i++) {
    if(i%2==0) {                                                  // Get every second element
      if(i+1 < hashList.size()) {
        listOfPairedHashes.put(hash(hashList[i], hashList[i+1])); // If there is one more, pair with it as partner
      } else {
        listOfPairedHashes.put(hash(hashList[i], hashList[i]));   // For last element pair with itself
      }
    }
  }
  return listOfPairedHashes;

You'll still need to add some checks for cases such as "hashList is empty" etc. of course.

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.