From a26dd9284352000cca6338b68c03594dcd900494 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Fri, 2 Nov 2018 16:26:59 +0100 Subject: WIP for file upload (Merkle tree for signatures) --- shard/lib/app/file.ex | 114 +++++++++++++++++++++++++++++++++++++++++++ shard/lib/data/data.ex | 6 +++ shard/lib/data/merkletree.ex | 93 +++++++++++++++++++++++++++++++++++ shard/lib/net/manager.ex | 2 + shard/mix.exs | 1 + shard/mix.lock | 1 + shard/test/conn_test.exs | 58 +++++----------------- shard/test/mkltree_test.exs | 27 ++++++++++ 8 files changed, 256 insertions(+), 46 deletions(-) create mode 100644 shard/lib/app/file.ex create mode 100644 shard/lib/data/merkletree.ex create mode 100644 shard/test/mkltree_test.exs (limited to 'shard') diff --git a/shard/lib/app/file.ex b/shard/lib/app/file.ex new file mode 100644 index 0000000..a874222 --- /dev/null +++ b/shard/lib/app/file.ex @@ -0,0 +1,114 @@ +defmodule SApp.File do + @moduledoc""" + Shard application for a file identified by its infohash. The file cannot be modified. + + The infohash is the hash of an info struct containing: + + %Info{ + merkle_root: hash + file_hash: hash + size: int + mime_type: string + } + + The file is cut in blocks of 4kb that are collected in a 64-ary Merkle tree. + """ + + use GenServer + + require Logger + + alias SData.MerkleTree, as: MT + + defmodule Manifest do + @moduledoc""" + Manifest for a file. + The file is identified by the root hash of its Merkle tree and by its mime type. + """ + defstruct [:infohash] + + defimpl Shard.Manifest do + def module(_m), do: SApp.File + def is_valid?(m) do + byte_size(m.infohash) == 32 + end + end + end + + defmodule Info do + @moduledoc""" + A file info struct. + """ + defstruct [:merkle_root, :file_hash, :size, :mime_type] + end + + defmodule State do + defstruct [:infohash, :id, :manifest, :netgroup, :info, :infobin, :store, :missing, :path] + end + + def start_link(manifest) do + GenServer.start_link(__MODULE__, manifest) + end + + def init(manifest) do + %Manifest{infohash: infohash} = manifest + id = SData.term_hash manifest + + Shard.Manager.dispatch_to(id, nil, self()) + {infobin, info} = case Shard.Manager.load_state(id) do + nil -> {nil, nil} + infobin -> {infobin, SData.term_unbin infobin} + end + netgroup = %SNet.PubShardGroup{id: id} + SNet.Group.init_lookup(netgroup, self()) + + path = [Application.get_env(:shard, :data_path), "#{id|>Base.encode16}"] |> Path.join + + {:ok, store} = SApp.PageStore.start_link(id, :meta, netgroup) + + {:ok, %State{ + id: id, infohash: infohash, manifest: manifest, netgroup: netgroup, + infobin: infobin, info: info, store: store, missing: nil, path: path + }} + end + + def handle_cast({:init_with, file_path, infobin, mt}, state) do + info = SData.term_unbin(infobin) + for {k, v} <- mt.store do + {^k, _} = SData.PageStore.put(state.store, v) + end + File.copy!(file_path, state.path) + new_state = %{state | + infobin: infobin, + info: info, + } + {:noreply, new_state} + end + + # TODO networking etc + + # ========= + # INTERFACE + # ========= + + @doc""" + Create a File shard from a file path + """ + def create(path, mime_type) do + %File.Stat{size: size} = File.stat!(path) + mt = MT.create(path) + hash = SData.file_hash(path) + + info = %Info{ + merkle_root: mt.root, + file_hash: hash, + size: size, + mime_type: mime_type, + } + infobin = SData.term_bin(info) + infohash = SData.bin_hash(infobin) + manifest = %Manifest{infohash: infohash} + pid = Shard.Manager.find_or_start(manifest) + GenServer.cast(pid, {:init_with, path, infobin, mt}) + end +end diff --git a/shard/lib/data/data.ex b/shard/lib/data/data.ex index 78c73cd..33dca09 100644 --- a/shard/lib/data/data.ex +++ b/shard/lib/data/data.ex @@ -26,6 +26,12 @@ defmodule SData do :crypto.hash(algo, bin) end + def file_hash(path, algo \\ :sha256) do + File.stream!(path, [], 65536) + |> Enum.reduce(:crypto.hash_init(algo), &(:crypto.hash_update(&2, &1))) + |> :crypto.hash_final() + end + def term_unbin(bin) do :erlang.binary_to_term(bin, [:safe]) end diff --git a/shard/lib/data/merkletree.ex b/shard/lib/data/merkletree.ex new file mode 100644 index 0000000..90361a3 --- /dev/null +++ b/shard/lib/data/merkletree.ex @@ -0,0 +1,93 @@ +defmodule SData.MerkleTree do + @moduledoc""" + A Merkle tree structure for storing metadata for a big file. + """ + + alias SData.PageStore, as: Store + + @block_size 4096 + @tree_arity 64 + + defstruct [:root, :store] + + defmodule Page do + defstruct [:nblk, :child_nblk, :list] + + defimpl SData.Page do + def refs(page) do + if page.child_nblk == 1 do + [] + else + page.list + end + end + end + end + + @doc""" + Create a Merkle tree for indexing a file. + """ + def create(file, store \\ SData.LocalStore.new()) do + %File.Stat{size: size} = File.stat!(file) + nblk = div(size, @block_size) + (if rem(size, @block_size) == 0 do 0 else 1 end) + fh = File.open!(file, [:binary, :read]) + create_file_aux(fh, store, 0, nblk, @tree_arity) + end + + defp create_file_aux(fh, store, first_blk, nblk, divc) do + cond do + divc < nblk -> + create_file_aux(fh, store, first_blk, nblk, divc * @tree_arity) + divc == @tree_arity and nblk <= divc -> + hashes = for i <- first_blk .. (first_blk + nblk - 1) do + {:ok, blk} = :file.pread(fh, i * @block_size, @block_size) + :crypto.hash(:sha256, blk) + end + page = %Page{nblk: nblk, child_nblk: 1, list: hashes} + {hash, store} = Store.put(store, page) + %__MODULE__{root: hash, store: store} + divc > @tree_arity and nblk <= divc -> + sub_divc = div(divc, @tree_arity) + n_sub_minus_one = div(nblk, sub_divc) + {sub_hashes, store} = Enum.reduce(0..n_sub_minus_one, {[], store}, fn i, {sh, store} -> + sub_first = first_blk + i * sub_divc + sub_n = (if i == n_sub_minus_one do rem(nblk, sub_divc) else sub_divc end) + %__MODULE__{root: hash, store: store} = create_file_aux(fh, store, sub_first, sub_n, sub_divc) + {[hash | sh], store} + end) + page = %Page{nblk: nblk, child_nblk: sub_divc, list: Enum.reverse(sub_hashes)} + {hash, store} = Store.put(store, page) + %__MODULE__{root: hash, store: store} + end + end + + @doc""" + Get the number of blocks in the tree + """ + def block_count(mt) do + %Page{nblk: nblk} = Store.get(mt.store, mt.root) + nblk + end + + @doc""" + Get the hash of block number i + """ + def get(mt, i) do + %Page{child_nblk: cn, list: list} = Store.get(mt.store, mt.root) + if cn == 1 do + Enum.fetch!(list, i) + else + pos = div(i, cn) + subtree = %{mt | root: Enum.fetch!(list, pos)} + subpos = rem(i, cn) + get(subtree, subpos) + end + end + + @doc""" + Get the hashes of all blocks in a range + """ + def get_range(mt, range) do + range |> Enum.map(&(get(mt, &1))) # TODO: do this efficiently + end +end diff --git a/shard/lib/net/manager.ex b/shard/lib/net/manager.ex index 759c5f0..fb92f13 100644 --- a/shard/lib/net/manager.ex +++ b/shard/lib/net/manager.ex @@ -90,6 +90,8 @@ defmodule SNet.Manager do @doc""" Connect to a peer specified by ip address and port + + peer_info := {:inet, ip, port} """ def add_peer(peer_info, opts \\ []) do GenServer.call(__MODULE__, {:add_peer, peer_info, opts[:auth], opts[:callback]}) diff --git a/shard/mix.exs b/shard/mix.exs index 5adda9e..ec80c6b 100644 --- a/shard/mix.exs +++ b/shard/mix.exs @@ -26,6 +26,7 @@ defmodule Shard.MixProject do defp deps do [ {:excoveralls, "~> 0.10", only: :test}, + {:briefly, "~> 0.3", only: :test}, {:ex_doc, "~> 0.19", only: :dev, runtime: false}, {:enacl, git: "https://github.com/jlouis/enacl.git", tag: "0.16.0"}, diff --git a/shard/mix.lock b/shard/mix.lock index e849c04..662738e 100644 --- a/shard/mix.lock +++ b/shard/mix.lock @@ -1,4 +1,5 @@ %{ + "briefly": {:hex, :briefly, "0.3.0", "16e6b76d2070ebc9cbd025fa85cf5dbaf52368c4bd896fb482b5a6b95a540c2f", [:mix], [], "hexpm"}, "certifi": {:hex, :certifi, "2.3.1", "d0f424232390bf47d82da8478022301c561cf6445b5b5fb6a84d49a9e76d2639", [:rebar3], [{:parse_trans, "3.2.0", [hex: :parse_trans, repo: "hexpm", optional: false]}], "hexpm"}, "cowboy": {:hex, :cowboy, "1.1.2", "61ac29ea970389a88eca5a65601460162d370a70018afe6f949a29dca91f3bb0", [:rebar3], [{:cowlib, "~> 1.0.2", [hex: :cowlib, repo: "hexpm", optional: false]}, {:ranch, "~> 1.3.2", [hex: :ranch, repo: "hexpm", optional: false]}], "hexpm"}, "cowlib": {:hex, :cowlib, "1.0.2", "9d769a1d062c9c3ac753096f868ca121e2730b9a377de23dec0f7e08b1df84ee", [:make], [], "hexpm"}, diff --git a/shard/test/conn_test.exs b/shard/test/conn_test.exs index ae43d9d..42f4bc6 100644 --- a/shard/test/conn_test.exs +++ b/shard/test/conn_test.exs @@ -2,62 +2,28 @@ defmodule ShardTest.Conn do use ExUnit.Case doctest Shard.Application - require Salty.Box.Curve25519xchacha20poly1305, as: Box - require Salty.Sign.Ed25519, as: Sign - - test "crypto connection" do - {srv_pkey, srv_skey} = Shard.Identity.get_keypair - {:ok, sess_pkey, sess_skey} = Box.keypair - {:ok, challenge} = Salty.Random.buf 32 - {:ok, socket} = :gen_tcp.connect {127,0,0,1}, 4045, [:binary, packet: 2, active: false] - - hello = {srv_pkey, sess_pkey, challenge, 0} - :gen_tcp.send(socket, :erlang.term_to_binary hello) - {:ok, pkt} = :gen_tcp.recv(socket, 0) - {cli_pkey, cli_sess_pkey, cli_challenge, _his_port} = :erlang.binary_to_term(pkt, [:safe]) - - {:ok, cli_challenge_sign} = Sign.sign_detached(cli_challenge, srv_skey) - sendmsg(socket, cli_challenge_sign, cli_sess_pkey, sess_skey) - - challenge_sign = recvmsg(socket, cli_sess_pkey, sess_skey) - :ok = Sign.verify_detached(challenge_sign, challenge, cli_pkey) - - pkt = :erlang.binary_to_term(recvmsg(socket, cli_sess_pkey, sess_skey), [:safe]) - IO.puts (inspect pkt) - end - - defp sendmsg(sock, msg, pk, sk) do - {:ok, n} = Salty.Random.buf Box.noncebytes - {:ok, msg} = Box.easy(msg, n, pk, sk) - :gen_tcp.send(sock, n <> msg) - end - - defp recvmsg(sock, pk, sk) do - {:ok, pkt} = :gen_tcp.recv(sock, 0) - n = binary_part(pkt, 0, Box.noncebytes) - enc = binary_part(pkt, Box.noncebytes, (byte_size pkt) - Box.noncebytes) - {:ok, msg} = Box.open_easy(enc, n, pk, sk) - msg - end - test "set nickname" do - Shard.Identity.set_nickname "test bot" + pk = Shard.Keys.get_any_identity + pid = SApp.Identity.find_proc(pk) + info = SApp.Identity.get_info(pid) + new_info = %{info | nick: "test bot"} + SApp.Identity.set_info(pid, new_info) end test "connect to other instance" do - Shard.Manager.add_peer({127, 0, 0, 1}, 4045) + SNet.Manager.add_peer({:inet, {127, 0, 0, 1}, 4045}) receive do after 100 -> nil end end - @tag :skip test "connect to chat rooms" do - {:ok, pid1} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "test"}) - {:ok, pid2} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "other_test"}) - GenServer.cast(pid1, {:chat_send, "test msg 1"}) - GenServer.cast(pid2, {:chat_send, "test msg 2"}) + pk = Shard.Keys.get_any_identity + + pid1 = Shard.Manager.find_or_start %SApp.Chat.Manifest{channel: "test"} + pid2 = Shard.Manager.find_or_start %SApp.Chat.Manifest{channel: "other_test"} - {:error, :redundant} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "test"}) + SApp.Chat.chat_send(pid1, pk, "test msg 1") + SApp.Chat.chat_send(pid2, pk, "test msg 2") end end diff --git a/shard/test/mkltree_test.exs b/shard/test/mkltree_test.exs new file mode 100644 index 0000000..248a37f --- /dev/null +++ b/shard/test/mkltree_test.exs @@ -0,0 +1,27 @@ +defmodule ShardTest.MklTree do + use ExUnit.Case + doctest Shard.Application + + test "merkle tree" do + alias SData.MerkleTree, as: MT + + nblk = 14119 + + {:ok, path} = Briefly.create + fh = File.open!(path, [:write]) + hashes = for i <- 0..nblk do + block = :enacl.randombytes 4096 + :file.write(fh, block) + :crypto.hash(:sha256, block) + end + lastblock = :enacl.randombytes 128 + :file.write(fh, lastblock) + hashes = hashes ++ [:crypto.hash(:sha256, lastblock)] + :file.close fh + + mt = MT.create(path) + hashes2 = 0..(nblk+1) |> Enum.map(&(MT.get(mt, &1))) + + assert hashes == hashes2 + end +end -- cgit v1.2.3