MerkleProof learning purpose

merkle.ex

defmodule MerkleTree.Node do
  @moduledoc """
    This module implements a tree node abstraction.
  """

  defstruct [:value, :children, :height]

  @type t :: %__MODULE__{
    value: String.t,
    children: [MerkleTree.Node.t],
    height: non_neg_integer
  }
end

defmodule MerkleTree do
  @moduledoc """
    A hash tree or Merkle tree is a tree in which every non-leaf node is labelled
    with the hash of the labels or values (in case of leaves) of its child nodes.
    Hash trees are useful because they allow efficient and secure verification of
    the contents of large data structures.

      ## Usage Example

      iex> MerkleTree.new ['a', 'b', 'c', 'd']
      %MerkleTree{blocks: ['a', 'b', 'c', 'd'], hash_function: &MerkleTree.Crypto.sha256/1,
            root: %MerkleTree.Node{children: [%MerkleTree.Node{children: [%MerkleTree.Node{children: [], height: 0,
                 value: "ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb"},
                %MerkleTree.Node{children: [], height: 0, value: "3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d"}], height: 1,
               value: "62af5c3cb8da3e4f25061e829ebeea5c7513c54949115b1acc225930a90154da"},
              %MerkleTree.Node{children: [%MerkleTree.Node{children: [], height: 0,
                 value: "2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6"},
                %MerkleTree.Node{children: [], height: 0, value: "18ac3e7343f016890c510e93f935261169d9e3f565436429830faf0934f4f8e4"}], height: 1,
               value: "d3a0f1c792ccf7f1708d5422696263e35755a86917ea76ef9242bd4a8cf4891a"}], height: 2,
             value: "58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd"}}
  """

  defstruct [:blocks, :root, :hash_function]

  @number_of_children 2 # Number of children per node. Configurable.

  @type blocks :: [String.t, ...]
  @type hash_function :: (String.t -> String.t)
  @type root :: MerkleTree.Node.t
  @type t :: %MerkleTree{
    blocks: blocks,
    root: root,
    hash_function: hash_function
  }

  @doc """
    Creates a new merkle tree, given a `2^N` number of string blocks and an
    optional hash function.

    By default, `merkle_tree` uses `:sha256` from :crypto.
    Check out `MerkleTree.Crypto` for other available cryptographic hashes.
    Alternatively, you can supply your own hash function that has the spec
    ``(String.t -> String.t)``.
  """
  @spec new(blocks, hash_function) :: t
  def new(blocks, hash_function \\ &MerkleTree.Crypto.sha256/1)
  when blocks != [] do
    unless is_power_of_n(@number_of_children, Enum.count(blocks)), do: raise MerkleTree.ArgumentError

    root = build(blocks, hash_function)
    %MerkleTree{blocks: blocks, hash_function: hash_function, root: root}
  end

  @doc """
    Builds a new binary merkle tree.
  """
  @spec build(blocks, hash_function) :: root
  def build(blocks, hash_function) do
    starting_height = 0
    leaves = Enum.map(blocks, fn(block) ->
      %MerkleTree.Node{
        value: hash_function.(block),
        children: [],
        height: starting_height
      }
    end)
    _build(leaves, hash_function, starting_height)
  end

  defp _build([root], _, _), do: root # Base case
  defp _build(nodes, hash_function, previous_height) do # Recursive case
    children_partitions = Enum.chunk(nodes, @number_of_children)
    height = previous_height + 1
    parents = Enum.map(children_partitions, fn(partition) ->
      concatenated_values = partition
        |> Enum.map(&(&1.value))
        |> Enum.reduce("", fn(x, acc) -> acc <> x end)
      %MerkleTree.Node{
        value: hash_function.(concatenated_values),
        children: partition,
        height: height
      }
    end)
    _build(parents, hash_function, height)
  end

  @spec is_power_of_n(pos_integer, pos_integer) :: boolean
  defp is_power_of_n(n, x) do
    (:math.log2(x)/:math.log2(n)) |> is_integer_float
  end

  @spec is_integer_float(float) :: boolean
  defp is_integer_float(x) do
    (Float.ceil x) == (Float.floor x)
  end

end





defmodule MerkleTree.Proof do
  @moduledoc """
    Generate and verify merkle proofs

      ## Usage Example
      iex> proof = MerkleTree.new(~w/a b c d/) |>
      ...> MerkleTree.Proof.prove(1)
      %MerkleTree.Proof{hash_function: &MerkleTree.Crypto.sha256/1,
       hashes: ["d3a0f1c792ccf7f1708d5422696263e35755a86917ea76ef9242bd4a8cf4891a",
        "ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb"]}
      iex> MerkleTree.Proof.proven?({"b", 1}, "58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd", proof)
      true

  """
  defstruct [:hashes, :hash_function]

  @type t :: %MerkleTree.Proof{
    hashes: [String.t, ...],
    # TODO: remove when deprecated MerkleTree.Proof.proven?/3 support ends
    hash_function: MerkleTree.hash_function
  }

  @doc """
  Generates proof for a block at a specific index
  """
  @spec prove(MerkleTree.t, non_neg_integer) :: t
  def prove(%MerkleTree{root: %MerkleTree.Node{height: height} = root} = tree,
            index) do
    %MerkleTree.Proof{
      hashes: _prove(root, binarize(index, height)),
      # TODO: remove when deprecated MerkleTree.Proof.proven?/3 support ends
      hash_function: tree.hash_function
    }
  end

  defp _prove(_, ""), do: []
  defp _prove(%MerkleTree.Node{children: children},
              index_binary) do
    {path_head, path_tail} = path_from_binary(index_binary)
    [child, sibling] = case path_head do
      1 -> Enum.reverse(children)
      0 -> children
    end
    [sibling.value] ++ _prove(child, path_tail)
  end

  @doc """
  Verifies proof for a block at a specific index
  """
  @spec proven?({String.t, non_neg_integer}, String.t, MerkleTree.hash_function, t) :: boolean
  def proven?({block, index}, root_hash, hash_function,
              %MerkleTree.Proof{hashes: proof}) do
    height = length(proof)
    root_hash == _hash_proof(block, binarize(index, height), proof, hash_function)
  end

  @doc false
  @deprecated "Use proven?/4 instead"
  # TODO: remove when deprecated MerkleTree.Proof.proven?/3 support ends
  def proven?({block, index}, root_hash,
              %MerkleTree.Proof{hashes: proof, hash_function: hash_function}) do
    height = length(proof)
    root_hash == _hash_proof(block, binarize(index, height), proof, hash_function)
  end

  defp _hash_proof(block, "", [], hash_function) do
    hash_function.(block)
  end
  defp _hash_proof(block, index_binary, [proof_head | proof_tail], hash_function) do
    {path_head, path_tail} = path_from_binary(index_binary)
    case path_head do
      1 -> hash_function.(
        proof_head <> _hash_proof(block, path_tail, proof_tail, hash_function)
      )
      0 -> hash_function.(
        _hash_proof(block, path_tail, proof_tail, hash_function) <> proof_head
      )
    end
  end

  @spec binarize(integer, integer) :: binary
  defp binarize(index, height) do
    <<index_binary::binary-unit(1)>> = <<index::unsigned-big-integer-size(height)>>
    index_binary
  end

  @spec path_from_binary(binary) :: {binary, binary}
  defp path_from_binary(index_binary) do
    <<path_head::unsigned-big-integer-unit(1)-size(1),
    path_tail::binary-unit(1)>> = index_binary
    {path_head, path_tail}
  end
end

defmodule MerkleTree.ArgumentError do
  defexception message: "MerkleTree.new requires a power of 2 (2^N) number of blocks." 
end

defmodule MerkleTree.Crypto do
  @moduledoc """
    This module defines some cryptographic hash functions used to hash block
    contents.
  """

  @type algorithm :: :md5 | :sha | :sha224 | :sha256 | :sha384 | :sha512

  @spec sha256(String.t) :: String.t
  def sha256(data) do
    hash(data, :sha256)
  end

  @spec hash(String.t, algorithm) :: String.t
  def hash(data, algorithm) do
    :crypto.hash(algorithm, data) |> Base.encode16(case: :lower)
  end
end








###########################
# MAIN
###########################

hashed_txs = [
    "0xf901ed8208bc8501bf08eb008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea40000000000000000000000000000000000000000000000014d1120d7b160000000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b88090900000000000000000000000000000000000000000000000000000000000000530000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041c6fade033fd61d7718d0406382d6674f3abec1d7468a109d30a982ead19a0b786af692775b0aefdeb9555fd1acd273e57b72d70e1a3f5fffadd4d040df7e350a1c000000000000000000000000000000000000000000000000000000000000001ca0e4a7e448d0ed78e5f1ccc2a53a5faf566e4c6b3555b80176208eca72a0813549a054415c03916fd422a414eea6d638beeefcd5843731ffbe8ed082fe3198405769",
    "0xf901ed8208bb850165a0bc008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea40000000000000000000000000000000000000000000000007ad1841c5635000000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b85588300000000000000000000000000000000000000000000000000000000000000510000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041c831006d7d0a5033865a49ee9aa9ec668517861141fe654bcbdf1562e804c2f10ab7cea7c62b3849f25557807aedcc4aeb9f79565cc8e9130331c148dbbb25281c000000000000000000000000000000000000000000000000000000000000001ba092f917a1be972186d879d7018fbf8b56ec302622ff4df8fec6802798ea3fcc70a06739583db0f4f3cae93577af629ee2a90752b89d92a24d247834b7ae885183a6",
    "0xf901ed8208ba850165a0bc008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea400000000000000000000000000000000000000000000000029a2241af62c000000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b854a30000000000000000000000000000000000000000000000000000000000000004f000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004139300c7f19a323057effd05bbe48de9b1832053fc1c6aefeec9c13cb819570540798ca542ba3db61324b76e7805449d7b2f8e23975bec718939a9632a067c89d1c000000000000000000000000000000000000000000000000000000000000001ca05ba1ba081b11b88990f2cbace75a85ce484f1bb357b31687fa38a741bc6309aea0315d40c1d3ae62ac727aac87b834a7b89fe76472dba7f9e935fe7f204bf8f41a",
    "0xf901ec8208b9850165a0bc008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea4000000000000000000000000000000000000000000000002f0194631a67b140000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b84366c000000000000000000000000000000000000000000000000000000000000004d00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000413a1cf73f1bb449a9bd43c42cee85582348667df00773ddb0825af4326841a4df28a948276cbed6a7300c65f0f0b24bcd1c96a1898f736b869a2696c2cfbae89a1b000000000000000000000000000000000000000000000000000000000000001b9f3f396c8c59b69e22fc0476c70dd034d869ad5347e43769fedf401bacdca2a8a044ef50e86b0d04fcd799bb07dfdd1d01ecf3f5213a5633930b0484de16d1e4fa",
    "0xf901ed8208b8850165a0bc008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea400000000000000000000000000000000000000000000000460c5281d7c8c000000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b7ee244000000000000000000000000000000000000000000000000000000000000004c0000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041e343412b1fa20203224ec9dbf91a6f26ede71fb541f40f1d17998fadcf1f896e4af9295ec5d34ff913acc67ff1d3a274ce930b89d9ede5076d8a6a85b82d12df1c000000000000000000000000000000000000000000000000000000000000001ca06b29e056f11e24b67417cbbccd81897878931edada77bc416661920020b1c83aa010dc153a3c9537edbb526f47ab03159f2d8f7f1ec7052193bf0a6f9009dfafec",
    "0xf901ec8208a984b2d05e008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea4000000000000000000000000000000000000000000000000efcca21dfd3af00000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b57592a000000000000000000000000000000000000000000000000000000000000003d0000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041ad4c1e2e57e2b11054127a3a399833df3f2ee8a3075d80c854983a3ffa48152e32d17c8baf3e1f277584f4a85d92a055d908b56a9548ba1320db00c6e7e3870e1c000000000000000000000000000000000000000000000000000000000000001ba0c598b22a9397fbed332be1b7c1097ce41716d401c1e1ff0936c090d7140e61cda02249acbfa698f60b98ef8968dedb2de628fa166d634243fea4ddab2a0e15c7dc",
    "0xf901ec8208aa84c51fde008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea40000000000000000000000000000000000000000000000057c040afa7645000000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b587bbb000000000000000000000000000000000000000000000000000000000000003e0000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041eb3c008470398c368a9db8a5ee61137af489dd52bd1a32eddfa8c466289c8a637fb8310328d546ce2a2b7e5af98cedfcdc0b589dffded4d8c16dc39fcc4352fd1b000000000000000000000000000000000000000000000000000000000000001ba0555e8c9f23d5bb31624bd3c94fb1bcfa6b345c68d2ab9fa6ad4fa028181c8718a0225c6b2ef871e38822d69bbcab99e3302548240e6c0de1a4ef28faa4b632c668",
    "0xf901ec8208ab84bd8af3008307a12094a743d7c4f9fdf00bc8dd123c4eb8996bc71a02eb80b9018439125215000000000000000000000000435891f5515ba3a5fe0e3f048f769ab7a0d30ea40000000000000000000000000000000000000000000000037bc96189329a000000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000005b5a25af000000000000000000000000000000000000000000000000000000000000003f00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000413041273ad40253e0225b4b2a4f9ef89c32d88d2e8aa87fcaaf164d565a845e773f9b4f6cb12c29cdbf58c9a7ce156fa9bb475eb9bcfce3c810f92ab212a28b641b000000000000000000000000000000000000000000000000000000000000001ca0dcb13b05ba370f50435ed51ebaddbb66ab01e3975af4c189d419e2bf169ccfeba0376e71bebf6e04eb9ecf9a4005bcdce7ff29c5bb52b452423e506b632cf3f52f"
]
txindex = 0

mt = MerkleTree.new(hashed_txs)
proof = MerkleTree.Proof.prove(mt, txindex)

IO.puts "Proof:"
IO.inspect proof

IO.puts "Return true because txindex=0 and proven?'s 1st arg(=block) is 0th item"
IO.inspect MerkleTree.Proof.proven?({Enum.at(hashed_txs, 0), txindex}, mt.root.value, &MerkleTree.Crypto.sha256/1, proof)

IO.puts "Return false because txindex=0 and proven?'s 1st arg(=block) is 1st item"
IO.inspect MerkleTree.Proof.proven?({Enum.at(hashed_txs, 1), txindex}, mt.root.value, &MerkleTree.Crypto.sha256/1, proof)

# Args Format
https://github.com/omisego/elixir-omg/blob/66d7684925c2f02708b3987898edee155c8655cf/apps/omg_watcher/lib/challenger/core.ex#L38

# Test Env
https://www.jdoodle.com/execute-elixir-online

# proven? (a.k.a. checkMembership)
https://github.com/yosriady/merkle_tree/blob/master/lib/merkle_tree/proof.ex#L51-L64