Current section
7 Versions
Jump to
Current section
7 Versions
Compare versions
3
files changed
+31
additions
-20
deletions
| @@ -14,4 +14,4 @@ | |
| 14 14 | {<<"optional">>,false}, |
| 15 15 | {<<"repository">>,<<"hexpm">>}, |
| 16 16 | {<<"requirement">>,<<"~> 0.4.0">>}]]}. |
| 17 | - {<<"version">>,<<"0.4.0">>}. |
| 17 | + {<<"version">>,<<"0.5.0">>}. |
| @@ -4,7 +4,7 @@ defmodule MerkleFun do | |
| 4 4 | def new(input, sort_pairs \\ true) do |
| 5 5 | leaves = |
| 6 6 | input |
| 7 | - |> Enum.map(fn x -> Base.decode16!(x, case: :mixed) |> hash() end) |
| 7 | + |> Enum.map(&hash_leaf/1) |
| 8 8 | |> Enum.sort() |
| 9 9 | |
| 10 10 | leaves = leaves ++ add_padding_rows(leaves) |
| @@ -12,7 +12,7 @@ defmodule MerkleFun do | |
| 12 12 | _build_tree(leaves, [], sort_pairs) |> List.to_tuple() |
| 13 13 | end |
| 14 14 | |
| 15 | - def root(tree), do: bytes_to_string(elem(tree, 0)) |
| 15 | + def root(tree), do: bytes_to_string(elem(tree, 0)) |> add_0x() |
| 16 16 | |
| 17 17 | def print(tree) do |
| 18 18 | tree |
| @@ -22,10 +22,7 @@ defmodule MerkleFun do | |
| 22 22 | end |
| 23 23 | |
| 24 24 | def proof(tree, leaf) do |
| 25 | - leaf_hash = |
| 26 | - leaf |
| 27 | - |> Base.decode16!(case: :mixed) |
| 28 | - |> hash() |
| 25 | + leaf_hash = hash_leaf(leaf) |
| 29 26 | |
| 30 27 | idx = |
| 31 28 | tree |
| @@ -34,19 +31,17 @@ defmodule MerkleFun do | |
| 34 31 | |
| 35 32 | _proof(tree, idx) |
| 36 33 | |> Enum.map(&bytes_to_string/1) |
| 34 | + |> Enum.reject(fn x -> x == 1 end) |
| 37 35 | |> Enum.map(&add_0x/1) |
| 38 36 | end |
| 39 37 | |
| 40 | - def verify(proof, node) do |
| 41 | - node = node |
| 42 | - |> Base.decode16!(case: :mixed) |
| 43 | - |> hash() |
| 38 | + def verify(proof, leaf) do |
| 39 | + leaf_hash = hash_leaf(leaf) |
| 44 40 | |
| 45 | - proof = proof |
| 41 | + proof |
| 46 42 | |> Enum.map(&remove_0x/1) |
| 47 43 | |> Enum.map(fn s -> Base.decode16!(s, case: :mixed) end) |
| 48 | - |
| 49 | - Enum.reduce(proof, node, fn x, y -> hash(x, y, true) end) |
| 44 | + |> Enum.reduce(leaf_hash, fn x, y -> hash(x, y, true) end) |
| 50 45 | |> bytes_to_string() |
| 51 46 | |> add_0x() |
| 52 47 | end |
| @@ -72,6 +67,8 @@ defmodule MerkleFun do | |
| 72 67 | |> Enum.chunk_every(2) |
| 73 68 | |> Enum.map(fn |
| 74 69 | [x, 1] -> x |
| 70 | + # needs test |
| 71 | + [1, x] -> x |
| 75 72 | [x, y] -> hash(x, y, sort_pairs) |
| 76 73 | end) |
| 77 74 | |
| @@ -79,8 +76,10 @@ defmodule MerkleFun do | |
| 79 76 | end |
| 80 77 | |
| 81 78 | defp hash(data), do: data |> ExKeccak.hash_256() |
| 79 | + |
| 82 80 | defp hash(x, y, sort) do |
| 83 | - [x, y] = if sort do |
| 81 | + [x, y] = |
| 82 | + if sort do |
| 84 83 | [x, y] |> Enum.sort() |
| 85 84 | else |
| 86 85 | [x, y] |
| @@ -89,6 +88,13 @@ defmodule MerkleFun do | |
| 89 88 | ExKeccak.hash_256(x <> y) |
| 90 89 | end |
| 91 90 | |
| 91 | + defp hash_leaf(leaf) do |
| 92 | + leaf |
| 93 | + |> remove_0x() |
| 94 | + |> Base.decode16!(case: :mixed) |
| 95 | + |> hash() |
| 96 | + end |
| 97 | + |
| 92 98 | defp sibling_idx(idx) do |
| 93 99 | if Integer.is_even(idx) do |
| 94 100 | idx - 1 |
| @@ -97,18 +103,23 @@ defmodule MerkleFun do | |
| 97 103 | end |
| 98 104 | end |
| 99 105 | |
| 100 | - defp bytes_to_string(bytes), do: Base.encode16(bytes, case: :lower) |
| 106 | + defp bytes_to_string(1), do: 1 |
| 107 | + |
| 108 | + defp bytes_to_string(bytes) do |
| 109 | + Base.encode16(bytes, case: :lower) |
| 110 | + end |
| 101 111 | |
| 102 112 | defp add_0x(s), do: "0x#{s}" |
| 103 113 | defp remove_0x("0x" <> s), do: s |
| 114 | + defp remove_0x("0X" <> s), do: s |
| 104 115 | defp remove_0x(s), do: s |
| 105 116 | |
| 106 117 | defp add_padding_rows(leaves) do |
| 107 118 | size = length(leaves) |
| 108 119 | num = :math.log2(size) |> ceil |
| 109 120 | num = 2 ** num |
| 110 | - num = num - size |
| 111 | - # pad with 1, uses less space |
| 112 | - List.duplicate(1, num) |
| 121 | + padding_num = num - size |
| 122 | + |
| 123 | + List.duplicate(1, padding_num) |
| 113 124 | end |
| 114 125 | end |
| @@ -6,7 +6,7 @@ defmodule MerkleFun.MixProject do | |
| 6 6 | def project do |
| 7 7 | [ |
| 8 8 | app: :merkle_fun, |
| 9 | - version: "0.4.0", |
| 9 | + version: "0.5.0", |
| 10 10 | description: "Merkle Tree implementation", |
| 11 11 | name: "Merkle Fun", |
| 12 12 | package: package(), |