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

<p>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.</p>

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

<pre><code>&lt;?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) &gt; 0) {
        if (count($txids) &gt;= 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;
</code></pre>

CC BY-SA 4.0
2019-12-02T15:09:31.013Z
Hi, you can use this library: https://github.com/drupol/phpmerkle
Pol Dellaiera
CC BY-SA 3.0
2016-04-01T18:53:39.290Z
2016-04-01T19:02:19.763Z
2016-04-01T19:02:19.763Z
karimkorun
<p>Here is some pseudo code how it could work:</p>

<pre><code>List&lt;Hash&gt; hashList;     //Contains the transaction ids of all transactions in the block

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

List&lt;Hash&gt; pairHashes(List&lt;Hash&gt; hashList):
  List&lt;Hash&gt; listOfPairedHashes = new List&lt;Hash&gt;();
  for(int i = 0; i &lt; hashList.size(); i++) {
    if(i%2==0) {                                                  // Get every second element
      if(i+1 &lt; 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;
</code></pre>

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

CC BY-SA 4.0
2023-05-04T03:49:25.220Z
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
CC BY-SA 3.0
2016-04-01T14:02:30.533Z
2016-04-01T14:02:30.533Z
Murch
<p>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.</p>

<p>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.</p>

<p><a href="http://pastebin.com/1C6sSbeE" rel="nofollow">http://pastebin.com/1C6sSbeE</a></p>

CC BY-SA 3.0
2016-04-01T11:06:42.600Z
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
CC BY-SA 4.0
2019-12-02T15:09:53.730Z
You can use this library for Merkle trees: https://github.com/drupol/phpmerkle
Pol Dellaiera
<php><merkle-tree>
How can I make this PHP merkle root script recursive?
inersha
# How can I make this PHP merkle root script recursive?

(Asked by: username_0 on 2016-04-01)

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>

**Tags:** php, merkle-tree

> **Comments:**
> **username_0**: 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.  
> **username_1**: You can use this library for Merkle trees: https://github.com/drupol/phpmerkle  

---

## 2 answers

### Answer by username_2 on 2016-04-01. Score: 1 | Accepted answer

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;

```

> **Comments:**
> **username_1**: Hi, you can use this library: https://github.com/drupol/phpmerkle  

---

### Answer by username_3 on 2016-04-01. Score: 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.

> **Comments:**
> **username_4**: 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.  

---

