Struct sn_routing::SectionChain

pub struct SectionChain { /* fields omitted */ }

Chain of section 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 SectionChain

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 merge(&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 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.

Returns Error::KeyNotFound if either trusted_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 has_key(&self, key: &PublicKey) -> bool

Returns whether key is present in this chain.

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.

Trait Implementations

impl Clone for SectionChain

fn clone(&self) -> SectionChain

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for SectionChain

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SectionChain

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

Deserialize this value from the given Serde deserializer.

impl Eq for SectionChain

impl Hash for SectionChain

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

impl PartialEq<SectionChain> for SectionChain

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

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

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

This method tests for !=.

impl Serialize for SectionChain

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

Serialize this value into the given Serde serializer.

impl StructuralEq for SectionChain

impl StructuralPartialEq for SectionChain