title: A simple merkle-tree implementation in java
body: <p>I am attempting to write a <strong>very</strong> simple merkle-tree implementation in Java.</p>
  
  <p>I am using the values of the txids in <a href="https://www.blockchain.com/btc/block/00000000d1145790a8694403d4063f323d499e655c83426834d4ce2f8dd4a2ee" rel="nofollow noreferrer">block 170</a> on the bitcoin blockchain for reference, so I can see what the correct result should be.</p>
  
  <p>The txids corresponding with that block are as follows:</p>
  
  <pre><code>b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082
  </code></pre>
  
  <pre><code>f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16
  </code></pre>
  
  <p>It is my understanding that bitcoin's merkle-tree implementation works the following way:</p>
  
  <ol>
  <li>split the transactions in the block up into pairs</li>
  <li>byte-swap the txids</li>
  <li>concatenate the txids</li>
  <li>double hash the concatenated pairs</li>
  </ol>
  
  <p>With a caveat being:</p>
  
  <pre><code>If there's no additional pairs of txids, concatenate the result of the first pair after double hashing with itself and repeat
  </code></pre>
  
  <p>My code is within a switch statement which looks like this:</p>
  
  <pre><code>case "test merkle root": {
      // txid A
      String A = "b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082";
  
      // txid A byte-swapped
      String A_little = MainChain.swapEndianness(A);
  
      // txid B
      String B = "f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16";
  
      // txid B byte-swapped
      String B_little = MainChain.swapEndianness(B);
  
      // txid A + B concatenated
      String AB_little = A_little + B_little;
  
      // double hash of byte-swapped concatenated A+B
      String ABdoubleHash =  SHA256.generateSHA256Hash(SHA256.generateSHA256Hash(AB_little));
  
      // double hash concatenated with itself
      String ABAB_little = ABdoubleHash + ABdoubleHash;
  
      // double hash of self-concatenated double-hashed txid
      String merkleRootLittleEndian = SHA256.generateSHA256Hash(SHA256.generateSHA256Hash(ABAB_little));
  
      // print result byte-swapped back to big-endian
      System.out.println("Merkle root: " + MainChain.swapEndianness(merkleRootLittleEndian));
  }
  </code></pre>
  
  <p>The swapEndianness method I wrote is not a true 'byte level' swap, and instead just changes the order of the String, it looks like this:</p>
  
  <pre><code>public static String swapEndianness(String hash) {
          char[] hashAsCharArray = hash.toCharArray();
          StringBuilder sb = new StringBuilder();
          for (int i = hash.length() - 1; i &gt; 0; i-=2) {
              sb.append(hashAsCharArray[i - 1]);
              sb.append(hashAsCharArray[i]);
          }
          return sb.toString();
      }
  </code></pre>
  
  <p>The expected result for the merkle root of these two txid's is:</p>
  
  <pre><code>7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff
  </code></pre>
  
  <p>However, the result I end up with is:</p>
  
  <pre><code>3b40cab1157838cc41b08e27641f65d245957ab07b3504d94bc2d355abaed06c
  </code></pre>
  
  <p>Am I not getting the result I am expecting because I am cheating when I do the byte-swap, because I am missing a step, or because I have an error in my code (or some combination of these)? Any help would be appreciated!</p>