How can I make this PHP merkle root script recursive?

Question

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 01 '16 at 11:06
You can use this library for Merkle trees: https://github.com/drupol/phpmerkle — Pol Dellaiera, Dec 02 '19 at 15:09

karimkorun · Accepted Answer · 2016-04-01T19:02:19.763

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;

Hi, you can use this library: https://github.com/drupol/phpmerkle — Pol Dellaiera, Dec 02 '19 at 15:09

score 0 · Answer 2 · answered Apr 01 '16 at 14:02

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.

C# is not pseudo and is valid programming language. This is not PHP-related. C# classes and methods just confuse against native PHP functions or PHP in general and does not conform with the OP. — WiiLF, May 04 '23 at 03:49

How can I make this PHP merkle root script recursive?

2 Answers2

Linked