Blocktree/crates/node/src/main.rs

// The dead code warnings create too much noise during wire-framing.
// TODO: Delete this prior to release.
#![allow(dead_code)]

use std::{
    collections::HashMap,
    convert::TryFrom,
    hash::Hash as Hashable,
    fmt::{self, Display, Formatter},
};
use serde::{Serialize, Deserialize};
use serde_big_array::BigArray;

#[cfg(test)]
mod test_helpers;

#[cfg(test)]
mod serde_tests;

mod crypto;
use crypto::{Hash, Signature, Key, Cryptotext};

/// A Block tagged with its version number.
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
enum VersionedBlock {
    V0(Block)
}

/// A container which binds together ciphertext along with the metadata needed to identify,
/// verify and decrypt it.
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
struct Block {
    /// Identifies this block and defines its location in the tree.
    path: Path,
    /// This field contains a collection of `ReadCap`s indexed by the principal who holds them.
    /// `ReadCap`s are envelopments of the key used to encrypt this block.
    read_caps: HashMap<Principal, Cryptotext<Key>>,
    /// This field is used to verify that the signer of this block had permission to write it.
    /// It contains a certificate chain that must lead back to the root key for the tree this block
    /// is part of.
    write_cap: WriteCap,
    /// The encrypted data contained in this block.
    body: Cryptotext<Vec<u8>>,
    /// The contents of the block are covered by a digital signature contained in this field.  
    signature: Signature
}

/// An envelopment of a key, which is tagged with the principal who the key is meant for.
#[derive(Debug, PartialEq, Serialize, Deserialize)]
struct ReadCap {
    /// The principal this `ReadCap` was issued to.
    issued_to: Principal,
    /// An encipherment of a block key using the public key of the principal.
    key: Cryptotext<Key>,
}

impl ReadCap {
    fn new(issued_to: Hash, key: Cryptotext<Key>) -> ReadCap {
        ReadCap { issued_to: Principal(issued_to), key }
    }
}

/// Verifies that a principal is authorized to write blocks in a tree.
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
struct WriteCap {
    /// The principal this `WriteCap` was issued to.
    issued_to: Principal,
    /// The path where this write caps's validity begins.
    path: Path,
    /// The point in time after which this write cap is no longer valid.
    expires: Epoch,
    /// The public key used to sign this write cap.
    signing_key: Key,
    /// A digital signature which covers all of the fields in the write cap except for next.
    signature: Signature,
    /// The next write cap in the chain leading back to the root.
    next: Option<Box<WriteCap>>,
}

/// Fragments are created from blocks using Erasure Encoding and stored with other nodes in the
/// network to provide availability and redundancy of data.
#[derive(Debug, PartialEq, Serialize, Deserialize)]
struct Fragment {
    /// The path to the block this fragment is from.
    path: Path,
    /// The serial number of this fragment.
    serial: FragmentSerial,
    /// The actual data.
    body: Vec<u8>,
}

impl Fragment {
    /// Create a new fragment with the given fields. If `path_str` cannot be parsed then a failed
    /// `Result` is returned containing a `PathError`.
    fn new(path_str: &str, serial_num: u32, body: Vec<u8>) -> Result<Fragment, PathError> {
        let result = Path::try_from(path_str);
        Ok(Fragment {
            path: result?,
            serial: FragmentSerial(serial_num),
            body
        })
    }
}

/// The body of every non-leaf node in a tree contains this data structure.
#[derive(Debug, PartialEq, Serialize, Deserialize)]
struct Directory {
    /// The nodes that are attached to the tree at this block.
    nodes: Vec<Principal>,
    /// This block's descendants.
    children: HashMap<String, HashMap<FragmentSerial, FragmentRecord>>,
}

/// Keeps track of which principal is storing a fragment.
#[derive(Debug, PartialEq, Serialize, Deserialize)]
struct FragmentRecord {
    /// The fragment serial number this record is for.
    serial: FragmentSerial,
    /// The principal who is storing this fragment.
    stored_by: Principal,
}

impl FragmentRecord {
    /// Creates a new `FragmentRecord` whose `serial` and `stored_by` fields are set to
    /// the given values.
    fn new(serial: u32, stored_by: Hash) -> FragmentRecord {
        FragmentRecord {
            serial: FragmentSerial(serial),
            stored_by: Principal(stored_by),
        }
    }
}

/// An identifier for a security principal, which is any entity that can be authenticated.
#[derive(Debug, PartialEq, Eq, Serialize, Deserialize, Hashable, Clone)]
struct Principal(Hash);

/// An identifier for a block in a tree.
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
struct Path {
    owner: Principal,
    components: Vec<String>,
}

impl Path {
    /// The character that is used to separate path components.
    const SEP: char = '/';
    /// The limit, in bytes, of a `Path`'s length.
    const BYTE_LIMIT: usize = 4096;

    /// Returns a result which, when successful, contains the index after the last character in the
    /// current path component.
    fn component_end<I: Iterator<Item = (usize, char)>>(
        start: usize, first: char, pairs: &mut I
    ) -> Result<usize, PathError> {
        if first == Path::SEP {
            return Err(PathError::EmptyComponent);
        }
        let end;
        let mut last = start;
        loop {
            match pairs.next() {
                Some((index, Path::SEP)) => {
                    end = index;
                    break;
                },
                Some((index, _)) => last = index,
                None => {
                    end = last + 1;
                    break
                }
            }
        }
        if end == start {
            Err(PathError::EmptyComponent)
        }
        else {
            Ok(end)
        }
    }

    /// Asserts that the number of bytes in the given string is no more than `Path::BYTE_LIMIT`.
    fn assert_not_too_long(string: &str) -> Result<(), PathError> {
        let len = string.len();
        if len > Path::BYTE_LIMIT {
            return Err(PathError::PathTooLong(len))
        }
        Ok(())
    }

    /// Returns true if `other` is a subpath of this `Path`.
    fn contains(&self, other: &Path) -> bool {
        if self.owner != other.owner {
            return false;
        };
        // This path must be no longer than the other path.
        if self.components.len() > other.components.len() {
            return false;
        }
        // Skip the component containing the owner.
        let self_iter = self.components.iter().skip(1);
        let other_iter = other.components.iter().skip(1);
        for pair in self_iter.zip(other_iter) {
            if pair.0 != pair.1 {
                return false;
            }
        }
        true
    }
}

impl<'s> TryFrom<&'s str> for Path {
    type Error = PathError;

    fn try_from(string: &'s str) -> Result<Path, PathError> {
        Path::assert_not_too_long(string)?;
        let mut pairs = string.char_indices();
        let mut components = Vec::new();
        let mut last_end = 0;
        while let Some((start, c)) = pairs.next() {
            let end = Path::component_end(start, c, &mut pairs)?;
            last_end = end;
            let slice = &string[start..end];
            components.push(slice.to_string());
        }
        // An empty component is added to the end to indicate if there was a trailing slash.
        if string.len() - 1 == last_end {
            components.push("".to_string());
        }
        let leading = components.get(0).ok_or(PathError::InvalidLeadingComponent)?;
        let hash = Hash::try_from(leading.as_str())
            .map_err(|_| PathError::InvalidLeadingComponent)?;
        Ok(Path {
            owner: Principal(hash),
            components,
        })
    }
}

impl Display for Path {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.components.is_empty() {
            return write!(f, "");
        };
        let mut iter = self.components.iter();
        let first = iter.next().unwrap();
        let mut output = write!(f, "{}", first);
        for component in iter {
            output = write!(f, "{}{}", Path::SEP, component)
        }
        output
    }
}

/// Errors which can occur when converting a string to a `Path`.
#[derive(Debug, PartialEq)]
enum PathError {
    /// Occurs when the number of bytes in a string is greater than `Path::BYTE_LIMIT`.
    PathTooLong(usize),
    /// Indicates that a path string was empty.
    Empty,
    /// Occurs when a component in a path string was empty.
    EmptyComponent,
    /// Occurs when the leading component of a path is not in the correct format.
    InvalidLeadingComponent,
}

impl Display for PathError {
    fn fmt(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
       match self {
           PathError::PathTooLong(length) => formatter.write_fmt(format_args!(
                "path contained {} bytes, which is over the {} byte limit",
                length,
                Path::BYTE_LIMIT)
           ),
           PathError::Empty => formatter.write_str("path was empty"),
           PathError::EmptyComponent => formatter.write_str("component of path was empty"),
           PathError::InvalidLeadingComponent
            => formatter.write_str("invalid leading path component")
       }
    }
}

/// An instant in time represented by the number of seconds since January 1st 1970, 00:00:00 UTC.
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
struct Epoch(i64);

/// The serial number of a block fragment.
#[derive(Debug, PartialEq, Eq, Serialize, Deserialize, Hashable)]
struct FragmentSerial(u32);

fn main() {
    println!("Hello, world!");
}

#[cfg(test)]
mod tests {
    use super::*;
    use test_helpers::*;

    fn path_from_str_test_case(
        expected: Result<Path, PathError>, input: &str
    ) -> Result<(), PathError> {
        let result = Path::try_from(input);
        assert_eq!(expected, result);
        Ok(())
    }

    #[test]
    fn path_from_str_multiple_components_ok() -> Result<(), PathError> {
        let expected = make_path(vec!["red", "green", "blue"]);
        let input = format!("{}/red/green/blue", expected.owner.0);
        path_from_str_test_case(Ok(expected), input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_one_component_ok() -> Result<(), PathError> {
        let expected = make_path(vec![]);
        let input = expected.owner.0.to_string();
        path_from_str_test_case(Ok(expected), input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_trailing_slash_ok() -> Result<(), PathError> {
        // Notice the empty component at the end of this path due to the trailing slash.
        let expected = make_path(vec!["orange", "banana", "shotgun", ""]);
        let input = format!("{}/orange/banana/shotgun/", expected.owner.0);
        path_from_str_test_case(Ok(expected), input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_path_too_long_fail() -> Result<(), PathError> {
        let principal = make_principal();
        let input = format!("{}/{}", principal.0, "*".repeat(4097));
        let expected = Err(PathError::PathTooLong(input.len()));
        path_from_str_test_case(expected, input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_multiple_slashes_fail() -> Result<(), PathError> {
        let expected = Err(PathError::EmptyComponent);
        let input = format!("{}//orange", make_principal().0);
        path_from_str_test_case(expected, input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_leading_slash_fail() -> Result<(), PathError> {
        let expected = Err(PathError::EmptyComponent);
        let input = format!("/{}/orange/banana/shotgun", make_principal().0);
        path_from_str_test_case(expected, input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_round_trip() -> Result<(), PathError> {
        let expected = make_path(vec!["interstitial", "inter-related", "intersections"]);
        let actual = Path::try_from(expected.to_string().as_str())?;
        assert_eq!(expected, actual);
        Ok(())
    }

    #[test]
    fn path_contains_true() {
        let larger = make_path(vec!["apps"]);
        let smaller = make_path(vec!["apps", "bohdi"]);
        assert!(larger.contains(&smaller));
    }

    #[test]
    fn path_contains_true_only_owner() {
        let larger = make_path(vec![]);
        let smaller = make_path(vec![]);
        assert!(larger.contains(&smaller));
    }

    #[test]
    fn path_contains_false_self_is_longer() {
        let first = make_path(vec!["apps", "bohdi"]);
        let second = make_path(vec!["apps"]);
        assert!(!first.contains(&second));
    }

    #[test]
    fn path_contains_false_same_owners() {
        let first = make_path(vec!["apps"]);
        let second = make_path(vec!["nodes"]);
        assert!(!first.contains(&second));
    }

    #[test]
    fn path_contains_false_different_owners() {
        let first = make_path(vec!["apps"]);
        let mut second = make_path(vec!["apps"]);
        second.owner = Principal(Hash::Sha2_256(PRINCIPAL2));
        assert!(!first.contains(&second));
    }
}