aboutsummaryrefslogtreecommitdiff
path: root/shard
diff options
context:
space:
mode:
authorAlex Auvolat <alex@adnab.me>2018-11-02 16:26:59 +0100
committerAlex Auvolat <alex@adnab.me>2018-11-02 16:26:59 +0100
commita26dd9284352000cca6338b68c03594dcd900494 (patch)
treeb51c1a9ba734d0fba9a7d4a97df4ddca85dafbca /shard
parent353769402b6fd2ca4ea1807c2733e161a768f85e (diff)
downloadshard-a26dd9284352000cca6338b68c03594dcd900494.tar.gz
shard-a26dd9284352000cca6338b68c03594dcd900494.zip
WIP for file upload (Merkle tree for signatures)
Diffstat (limited to 'shard')
-rw-r--r--shard/lib/app/file.ex114
-rw-r--r--shard/lib/data/data.ex6
-rw-r--r--shard/lib/data/merkletree.ex93
-rw-r--r--shard/lib/net/manager.ex2
-rw-r--r--shard/mix.exs1
-rw-r--r--shard/mix.lock1
-rw-r--r--shard/test/conn_test.exs58
-rw-r--r--shard/test/mkltree_test.exs27
8 files changed, 256 insertions, 46 deletions
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