// Copyright 2021 MaidSafe.net limited.
//
// This SAFE Network Software is licensed to you under The General Public License (GPL), version 3.
// Unless required by applicable law or agreed to in writing, the SAFE Network Software distributed
// under the GPL Licence is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. Please review the Licences for the specific language governing
// permissions and limitations relating to use of the SAFE Network Software.
mod block;
mod branch;
mod deserialized;
pub mod error;
#[cfg(test)]
pub(crate) mod tests;
use itertools::Itertools;
use serde::{Deserialize, Serialize};
use std::{
cmp::Ordering,
collections::HashSet,
fmt::{self, Debug, Formatter},
iter, mem,
};
use self::{block::Block, branch::Branch, deserialized::Deserialized, error::Error};
/// Chain of BLS keys where every key is proven (signed) by its parent key, except the
/// first one.
///
/// # CRDT
///
/// The operations that mutate the chain ([`insert`](Self::insert) and [`merge`](Self::merge)) are
/// commutative, associative and idempotent. This means the chain is a
/// [CRDT](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type).
///
/// # Forks
///
/// It's possible to insert multiple keys that all have the same parent key. This is called a
/// "fork". The chain implements automatic fork resolution which means that even in the presence of
/// forks the chain presents the blocks in a well-defined unique and deterministic order.
///
/// # Block order
///
/// Block are ordered primarily according to their parent-child relation (parents always precede
/// children) and forks are resolved by additionally ordering the sibling blocks according to the
/// `Ord` relation of their public key. That is, "lower" keys precede "higher" keys.
#[derive(Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
#[serde(try_from = "Deserialized")]
pub struct SecuredLinkedList {
root: bls::PublicKey,
tree: Vec<Block>,
}
#[allow(clippy::len_without_is_empty)]
impl SecuredLinkedList {
/// Creates a new chain consisting of only one block.
pub fn new(root: bls::PublicKey) -> Self {
Self {
root,
tree: Vec::new(),
}
}
/// Insert new key into the chain. `parent_key` must exists in the chain and must validate
/// `signature`, otherwise error is returned.
pub fn insert(
&mut self,
parent_key: &bls::PublicKey,
key: bls::PublicKey,
signature: bls::Signature,
) -> Result<(), Error> {
let parent_index = self.index_of(parent_key).ok_or(Error::KeyNotFound)?;
let block = Block {
key,
signature,
parent_index,
};
if block.verify(parent_key) {
let _ = self.insert_block(block);
Ok(())
} else {
Err(Error::FailedSignature)
}
}
/// Merges two chains into one.
///
/// This succeeds only if the root key of one of the chain is present in the other one.
/// Otherwise it returns `Error::InvalidOperation`
pub fn join(&mut self, mut other: Self) -> Result<(), Error> {
let root_index = if let Some(index) = self.index_of(other.root_key()) {
index
} else if let Some(index) = other.index_of(self.root_key()) {
mem::swap(self, &mut other);
index
} else {
return Err(Error::InvalidOperation);
};
let mut reindex_map = vec![0; other.len()];
reindex_map[0] = root_index;
for (other_index, mut other_block) in other
.tree
.into_iter()
.enumerate()
.map(|(index, block)| (index + 1, block))
{
other_block.parent_index = reindex_map[other_block.parent_index];
reindex_map[other_index] = self.insert_block(other_block);
}
Ok(())
}
/// Creates a sub-chain from given `from` and `to` keys.
/// Returns `Error::KeyNotFound` if the given keys are not present in the chain.
pub fn get_proof_chain(
&self,
from_key: &bls::PublicKey,
to_key: &bls::PublicKey,
) -> Result<Self, Error> {
let from_index = self.index_of(from_key).ok_or(Error::KeyNotFound)?;
let mut chain = Self::new(if from_index == 0 {
self.root
} else {
self.tree[from_index - 1].key
});
let mut curr_index = self.index_of(to_key).ok_or(Error::KeyNotFound)?;
while curr_index != 0 && curr_index != from_index {
let block = &self.tree[curr_index - 1];
chain.tree.insert(
0,
Block {
key: block.key,
signature: block.signature.clone(),
parent_index: 0, // we'll update it afterwards
},
);
curr_index = block.parent_index;
}
if curr_index != from_index {
// the 'from_key' is not an ancestor in any chain containing 'to_key'
Err(Error::SubChainNotFound)
} else {
for (i, elem) in chain.tree.iter_mut().enumerate() {
elem.parent_index = i;
}
Ok(chain)
}
}
/// Creates a minimal sub-chain of `self` that contains all `required_keys`.
/// Returns `Error::KeyNotFound` if some of `required_keys` is not present in `self`.
///
/// Note: "minimal" means it contains the fewest number of blocks of all such sub-chains.
pub fn minimize<'a, I>(&self, required_keys: I) -> Result<Self, Error>
where
I: IntoIterator<Item = &'a bls::PublicKey>,
{
// Note: the returned chain is not always strictly minimal. Consider this chain:
//
// 0->1->3->4
// |
// +->2
//
// Then calling `minimize([1, 3])` currently returns
//
// 1->3
// |
// +->2
//
// Even though the truly minimal chain containing 1 and 3 is just
//
// 1->3
//
// This is because 2 lies between 1 and 3 in the underlying `tree` vector and so is
// currently included.
//
// TODO: make this function return the truly minimal chain in all cases.
let mut min_index = self.len() - 1;
let mut max_index = 0;
for key in required_keys {
let index = self.index_of(key).ok_or(Error::KeyNotFound)?;
min_index = min_index.min(index);
max_index = max_index.max(index);
}
// To account for forks, we also need to include the closest common ancestors of all the
// required keys. This is to maintain the invariant that for every key in the chain that is
// not the root its parent key is also in the chain.
min_index = self.closest_common_ancestor(min_index, max_index);
let mut chain = Self::new(if min_index == 0 {
self.root
} else {
self.tree[min_index - 1].key
});
for index in min_index..max_index {
let block = &self.tree[index];
chain.tree.push(Block {
key: block.key,
signature: block.signature.clone(),
parent_index: block.parent_index - min_index,
})
}
Ok(chain)
}
/// Returns a sub-chain of `self` truncated to the last `count` keys.
/// NOTE: a chain must have at least 1 block, so if `count` is 0 it is treated the same as if
/// it was 1.
pub fn truncate(&self, count: usize) -> Self {
let count = count.max(1);
let mut tree: Vec<_> = self.branch(self.tree.len()).take(count).cloned().collect();
let root = if tree.len() >= count {
tree.pop().map(|block| block.key).unwrap_or(self.root)
} else {
self.root
};
tree.reverse();
// Fix the parent indices.
for (index, block) in tree.iter_mut().enumerate() {
block.parent_index = index;
}
Self { root, tree }
}
/// Returns the smallest super-chain of `self` that would be trusted by a peer that trust
/// `trusted_key`. Ensures that the last key of the resuling chain is the same as the last key
/// of `self`.
///
/// Returns `Error::KeyNotFound` if any of `trusted_key`, `self.root_key()` or `self.last_key()`
/// is not present in `super_chain`.
///
/// Returns `Error::InvalidOperation` if `trusted_key` is not reachable from `self.last_key()`.
pub fn extend(&self, trusted_key: &bls::PublicKey, super_chain: &Self) -> Result<Self, Error> {
let trusted_key_index = super_chain
.index_of(trusted_key)
.ok_or(Error::KeyNotFound)?;
let last_key_index = super_chain
.index_of(self.last_key())
.ok_or(Error::KeyNotFound)?;
if !super_chain.has_key(self.root_key()) {
return Err(Error::KeyNotFound);
}
if super_chain.is_ancestor(trusted_key_index, last_key_index) {
super_chain.minimize(vec![trusted_key, self.last_key()])
} else {
Err(Error::InvalidOperation)
}
}
/// Iterator over all the keys in the chain in order.
pub fn keys(&self) -> impl DoubleEndedIterator<Item = &bls::PublicKey> {
iter::once(&self.root).chain(self.tree.iter().map(|block| &block.key))
}
/// Returns the root key of this chain. This is the first key in the chain and is the only key
/// that doesn't have a parent key.
pub fn root_key(&self) -> &bls::PublicKey {
&self.root
}
/// Returns the last key of this chain.
pub fn last_key(&self) -> &bls::PublicKey {
self.tree
.last()
.map(|block| &block.key)
.unwrap_or(&self.root)
}
/// Returns the parent key of the last key or the root key if this chain has only one key.
pub fn prev_key(&self) -> &bls::PublicKey {
self.branch(self.tree.len())
.nth(1)
.map(|block| &block.key)
.unwrap_or(&self.root)
}
/// Returns whether `key` is present in this chain.
pub fn has_key(&self, key: &bls::PublicKey) -> bool {
self.keys().any(|existing_key| existing_key == key)
}
/// Verify every BLS key in this chain is proven (signed) by its parent key,
/// except the first one.
pub fn self_verify(&self) -> bool {
self.tree.iter().all(|block| {
let parent_key = if block.parent_index > 0 {
&self.tree[block.parent_index - 1].key
} else {
&self.root
};
block.verify(parent_key)
})
}
/// Given a collection of keys that are already trusted, returns whether this chain is also
/// trusted. A chain is considered trusted only if at least one of the `trusted_keys` is on its
/// main branch.
///
/// # Explanation
///
/// Consider this chain that contains fork:
///
/// ```ascii-art
/// A->B->C
/// |
/// +->D
/// ```
///
/// Now if the only trusted key is `D`, then there is no way to prove the chain is trusted,
/// because this chain would be indistinguishable in terms of trust from any other chain with
/// the same general "shape", say:
///
/// ```ascii-art
/// W->X->Y->Z
/// |
/// +->D
/// ```
///
/// So an adversary is easily able to forge any such chain.
///
/// When the trusted key is on the main branch, on the other hand:
///
/// ```ascii-art
/// D->E->F
/// |
/// +->G
/// ```
///
/// Then such chain is impossible to forge because the adversary would have to have access to
/// the secret key corresponding to `D` in order to validly sign `E`. Thus such chain can be
/// safely considered trusted.
pub fn check_trust<'a, I>(&self, trusted_keys: I) -> bool
where
I: IntoIterator<Item = &'a bls::PublicKey>,
{
let trusted_keys: HashSet<_> = trusted_keys.into_iter().collect();
self.branch(self.tree.len())
.map(|block| &block.key)
.chain(iter::once(&self.root))
.any(|key| trusted_keys.contains(key))
}
/// Compare the two keys by their position in the chain. The key that is higher (closer to the
/// last key) is considered `Greater`. If exactly one of the keys is not in the chain, the other
/// one is implicitly considered `Greater`. If none are in the chain, they are considered
/// `Equal`.
pub fn cmp_by_position(&self, lhs: &bls::PublicKey, rhs: &bls::PublicKey) -> Ordering {
match (self.index_of(lhs), self.index_of(rhs)) {
(Some(lhs), Some(rhs)) => lhs.cmp(&rhs),
(Some(_), None) => Ordering::Greater,
(None, Some(_)) => Ordering::Less,
(None, None) => Ordering::Equal,
}
}
/// Returns the number of blocks in the chain. This is always >= 1.
pub fn len(&self) -> usize {
1 + self.tree.len()
}
/// Returns the number of block on the main branch of the chain - that is - the ones reachable
/// from the last block.
///
/// NOTE: this is a `O(n)` operation.
pub fn main_branch_len(&self) -> usize {
self.branch(self.tree.len()).count() + 1
}
fn insert_block(&mut self, new_block: Block) -> usize {
// Find the index into `self.tree` to insert the new block at so that the block order as
// described in the `SecuredLinkedList` doc comment is maintained.
let same_block = self
.tree
.iter()
.enumerate()
.skip(new_block.parent_index)
.find(|(_, block)| {
block.parent_index == new_block.parent_index && block.key == new_block.key
})
.map(|(index, _)| index);
// If the key already exists in the chain, do nothing but still return success to make the
// `insert` operation idempotent.
let insert_at = match same_block {
Some(index) => return index + 1,
None => self
.tree
.iter()
.enumerate()
.skip(new_block.parent_index)
.find(|(_, block)| {
block.parent_index != new_block.parent_index || block.key >= new_block.key
})
.map(|(index, _)| index)
.unwrap_or(self.tree.len()),
};
self.tree.insert(insert_at, new_block);
// Adjust the parent indices of the keys whose parents are after the inserted key.
for block in &mut self.tree[insert_at + 1..] {
if block.parent_index > insert_at {
block.parent_index += 1;
}
}
insert_at + 1
}
/// Returns the index of the given key. Returns `None` if not present.
pub fn index_of(&self, key: &bls::PublicKey) -> Option<usize> {
self.keys()
.rev()
.position(|existing_key| existing_key == key)
.map(|rev_position| self.len() - rev_position - 1)
}
fn parent_index_at(&self, index: usize) -> Option<usize> {
if index == 0 {
None
} else {
self.tree.get(index - 1).map(|block| block.parent_index)
}
}
// Is the key at `lhs` an ancestor of the key at `rhs`?
fn is_ancestor(&self, lhs: usize, rhs: usize) -> bool {
let mut index = rhs;
loop {
if index == lhs {
return true;
}
if index < lhs {
return false;
}
if let Some(parent_index) = self.parent_index_at(index) {
index = parent_index;
} else {
return false;
}
}
}
// Returns the index of the closest common ancestor of the keys in the *closed* interval
// [min_index, max_index].
fn closest_common_ancestor(&self, mut min_index: usize, mut max_index: usize) -> usize {
loop {
if max_index == 0 || min_index == 0 {
return 0;
}
if max_index <= min_index {
return min_index;
}
if let Some(parent_index) = self.parent_index_at(max_index) {
min_index = min_index.min(parent_index);
} else {
return 0;
}
max_index -= 1;
}
}
// Iterator over the blocks on the branch that ends at `index` in reverse order.
// Does not include the root block.
fn branch(&self, index: usize) -> Branch {
Branch { chain: self, index }
}
}
impl Debug for SecuredLinkedList {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{:?}", self.keys().format("->"))
}
}