Struct secured_linked_list::SecuredLinkedList

pub struct SecuredLinkedList { /* private fields */ }

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 and merge) are commutative, associative and idempotent. This means the chain is a CRDT.

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.

Implementations

impl SecuredLinkedList

pub fn new(root: PublicKey) -> Self

Creates a new chain consisting of only one block.

pub fn insert(
    &mut self,
    parent_key: &PublicKey,
    key: PublicKey,
    signature: Signature
) -> Result<(), Error>

Insert new key into the chain. parent_key must exists in the chain and must validate signature, otherwise error is returned.

pub fn join(&mut self, other: Self) -> Result<(), Error>

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 get_proof_chain(
    &self,
    from_key: &PublicKey,
    to_key: &PublicKey
) -> Result<Self, Error>

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 minimize<'a, I>(&self, required_keys: I) -> Result<Self, Error> where
    I: IntoIterator<Item = &'a PublicKey>, 

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 truncate(&self, count: usize) -> Self

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 extend(
    &self,
    trusted_key: &PublicKey,
    super_chain: &Self
) -> Result<Self, Error>

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 keys(&self) -> impl DoubleEndedIterator<Item = &PublicKey>

Iterator over all the keys in the chain in order.

pub fn root_key(&self) -> &PublicKey

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 last_key(&self) -> &PublicKey

Returns the last key of this chain.

pub fn prev_key(&self) -> &PublicKey

Returns the parent key of the last key or the root key if this chain has only one key.

pub fn has_key(&self, key: &PublicKey) -> bool

Returns whether key is present in this chain.

pub fn self_verify(&self) -> bool

Verify every BLS key in this chain is proven (signed) by its parent key, except the first one.

pub fn check_trust<'a, I>(&self, trusted_keys: I) -> bool where
    I: IntoIterator<Item = &'a PublicKey>, 

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:

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:

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:

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 cmp_by_position(&self, lhs: &PublicKey, rhs: &PublicKey) -> Ordering

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 len(&self) -> usize

Returns the number of blocks in the chain. This is always >= 1.

pub fn main_branch_len(&self) -> usize

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 index_of(&self, key: &PublicKey) -> Option<usize>

Returns the index of the given key. Returns None if not present.

Trait Implementations

impl Clone for SecuredLinkedList

fn clone(&self) -> SecuredLinkedList

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SecuredLinkedList

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SecuredLinkedList

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl Hash for SecuredLinkedList

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl PartialEq<SecuredLinkedList> for SecuredLinkedList

fn eq(&self, other: &SecuredLinkedList) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &SecuredLinkedList) -> bool

This method tests for !=.

impl Serialize for SecuredLinkedList

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl Eq for SecuredLinkedList

impl StructuralEq for SecuredLinkedList

impl StructuralPartialEq for SecuredLinkedList