Add support for batch-signing requests

As documented in the Roughtime spec, servers can
batch together requests, only signing the root of a computed Merkle
tree, in order to increase efficiency.

Following the example of the reference Roughtime implementation,
the default batch size is set to 64. However, this value can be changed
in the config.

Two pieces of benchmark infrastructure are added - a simple
"benchmark mode" on the server, and a "stress test mode" on the client.
These features can be used to help pick an optimal batch size for the
server.

In "benchmark mode", the server does not log any requests. Instead,
it prints out the current request processing speed every second. This
helps to keep the output manageable when using the client's "stress
test" mode.

In "stress test mode", the client sends the same message to the server
in a loop. To prevent accidental flooding of the users's local network,
or a remote server, only loopback addresses are supported in this mode.

1 files changed, 174 insertions, 0 deletions

diff --git a/src/merkle.rs b/src/merkle.rs
new file mode 100644
index 0000000..623770f
--- /dev/null
+++ b/src/merkle.rs
@@ -0,0 +1,174 @@
+// Copyright 2018 int08h LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+extern crate ring;
+
+use super::{TREE_LEAF_TWEAK, TREE_NODE_TWEAK, HASH_LENGTH};
+use self::ring::digest;
+
+type Data = Vec<u8>;
+type Hash = Data;
+
+pub struct MerkleTree {
+    levels: Vec<Vec<Data>>,
+}
+
+impl MerkleTree {
+    pub fn new() -> MerkleTree {
+        MerkleTree {
+            levels: vec![vec![]]
+        }
+    }
+
+    pub fn push_leaf(&mut self, data: &[u8]) {
+        let hash = self.hash_leaf(data);
+        self.levels[0].push(hash);
+    }
+
+    pub fn get_paths(&self, mut index: usize) -> Vec<Hash> {
+        let mut paths = Vec::new();
+        let mut level = 0;
+
+        while !self.levels[level].is_empty() {
+            let sibling = if index % 2 == 0 {
+                index + 1
+            } else {
+                index - 1
+            };
+
+            paths.push(self.levels[level][sibling].clone());
+            level += 1;
+            index /= 2;
+        }
+        paths
+    }
+
+    pub fn compute_root(&mut self) -> Hash {
+        assert!(self.levels[0].len() > 0, "Must have at least one leaf to hash!");
+
+        let mut level = 0;
+        let mut node_count = self.levels[0].len();
+        while node_count > 1 {
+            level += 1;
+
+            if self.levels.len() < level + 1 {
+                self.levels.push(vec![]);
+            }
+
+            if node_count % 2 != 0 {
+                self.levels[level - 1].push(vec![0; HASH_LENGTH as usize]);
+                node_count += 1;
+            }
+
+            node_count /= 2;
+
+            for i in 0..node_count {
+                let hash = self.hash_nodes(&self.levels[level - 1][i*2], &self.levels[level - 1][(i*2)+1]);
+                self.levels[level].push(hash);
+            }
+        }
+        assert_eq!(self.levels[level].len(), 1);
+        self.levels[level].pop().unwrap()
+    }
+
+    pub fn reset(&mut self) {
+        for mut level in &mut self.levels {
+            level.clear();
+        }
+    }
+
+    fn hash_leaf(&self, leaf: &[u8]) -> Data {
+        self.hash(&[TREE_LEAF_TWEAK, leaf])
+    }
+
+    fn hash_nodes(&self, first: &[u8], second: &[u8]) -> Data {
+        self.hash(&[TREE_NODE_TWEAK, first, second])
+    }
+
+    fn hash(&self, to_hash: &[&[u8]]) -> Data {
+        let mut ctx = digest::Context::new(&digest::SHA512);
+        for data in to_hash {
+            ctx.update(data);
+        }
+        Data::from(ctx.finish().as_ref())
+    }
+}
+
+pub fn root_from_paths(mut index: usize, data: &[u8], paths: &[u8]) -> Hash {
+    let mut hash = {
+        let mut ctx = digest::Context::new(&digest::SHA512);
+        ctx.update(TREE_LEAF_TWEAK);
+        ctx.update(data);
+        Hash::from(ctx.finish().as_ref())
+    };
+
+    assert_eq!(paths.len() % 64, 0);
+
+    for path in paths.chunks(64) {
+        let mut ctx = digest::Context::new(&digest::SHA512);
+        ctx.update(TREE_NODE_TWEAK);
+
+        if index & 1 == 0 {
+            // Left
+            ctx.update(&hash);
+            ctx.update(path);
+        } else {
+            // Right
+            ctx.update(path);
+            ctx.update(&hash);
+        }
+        hash = Hash::from(ctx.finish().as_ref());
+
+        index >>= 1;
+    }
+    hash
+}
+
+#[cfg(test)]
+mod test {
+
+    use merkle::*;
+
+    fn test_paths_with_num(num: usize) {
+        let mut merkle = MerkleTree::new();
+
+        for i in 0..num {
+            merkle.push_leaf(&[i as u8]);
+        }
+
+        let root = merkle.compute_root();
+
+        for i in 0..num {
+            println!("Testing {:?} {:?}", num, i);
+            let paths: Vec<u8> = merkle.get_paths(i).into_iter().flat_map(|x| x).collect();
+            let computed_root = root_from_paths(i, &[i as u8], &paths);
+
+            assert_eq!(root, computed_root);
+        }
+    }
+
+    #[test]
+    fn power_of_two() {
+        test_paths_with_num(2);
+        test_paths_with_num(4);
+        test_paths_with_num(8);
+        test_paths_with_num(16);
+    }
+
+    #[test]
+    fn not_power_of_two() {
+        test_paths_with_num(1);
+        test_paths_with_num(20);
+    }
+}