merkle.fsx

open System
open System.Globalization
open System.Security.Cryptography

let bufferOfHex (hex : string) =
  hex.ToCharArray()
    |> Array.chunkBySize 2
    |> Array.map (fun nibbles -> Byte.Parse((String nibbles), NumberStyles.AllowHexSpecifier))

let hexOfBuffer (buffer : byte []) =
  buffer |> Array.map (fun x -> x.ToString("x2"))
         |> String.concat ""

let sha256 (buffer : byte []) =
  use hash = SHA256Managed.Create()
  hash.ComputeHash buffer

let sha256d = sha256 >> sha256

let balanceLength xs =
  if Seq.length xs % 2 = 0 then xs else Seq.append xs [Seq.last xs]

let rec merkleRoot hashes =
  if Seq.length hashes = 1 then Seq.head hashes
  else balanceLength hashes
    |> Seq.chunkBySize 2
    |> Seq.map (Array.concat >> sha256d)
    |> merkleRoot

let merkleRootLE = (Seq.map (Array.rev) >> merkleRoot >> Array.rev)

// Using tx hashes and expected merkle root from block #424328
let hashesLE = [
  bufferOfHex "8873f4e0179f3793f7057c061ab0d47ef88f0ac4bdf196db18bf8ebb595c2ee7"
  bufferOfHex "76d3724bb5ab9e2f6da7f0bb6d957f9741b804707b5ab5e959b82179a15f9cd2"
  bufferOfHex "8de666102756be4e5e6421ba545f1a4d751cc3fa5b525a4892f34ef32319bfc9"
  bufferOfHex "ade74bf39185afde6c9eff306cd979b7ce50921c38d7b5aabfa8954623e3c2a7"
  bufferOfHex "731dc0d08447feffef1de2a96fdf68fc201405b4e9083b0b8949845b93810862"
  bufferOfHex "f6f730aaab7a2c032cc6643cedf7bf9b496fe90d77d456a8333417b50183cbf7"
  bufferOfHex "d7775f6a9b955cc9f9606686b05ee837138c66a04eb8f5c59c281ed9ab7c8022"
  bufferOfHex "b9322e6588f1403dd82503fd398194410f46825f9d4ad62b34c1fd3414ba9e0c"
  bufferOfHex "f287b65f4b601dfb8e53b4183348e1583acf890ae8e0b86948fd30858d2de95d"
  bufferOfHex "660129cf91810f66280c47e092ac296d8c6118b65cf2cb60c0fab7fbed3af771"
  bufferOfHex "6fc53070af853023e5421ee0f383460b23f03dee1ed130b4f7368e83cbd38fed"
]
    
let expected = bufferOfHex "c7b70acf9c0fedd23cfaf6dd89ef9c65944b168ebf47569024854ee779ddf721"
let actual = merkleRootLE hashesLE
    
printfn "expected : %s" (hexOfBuffer expected)
printfn "actual   : %s" (hexOfBuffer actual)