Struct SCertifiedBTreeMap 

pub struct SCertifiedBTreeMap<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes, V: StableType + AsFixedSizeBytes + AsHashTree> { /* private fields */ }

Merkle tree certified map on top of SBTreeMap

All logic, not related to the undelying Merkle tree is simply proxied from the underlying SBTreeMap, read its documentation for more details.

This Merkle tree provides various proofs in a form of [HashTree] data structure that is completely compatible with Dfinity’s ic-certified-map, which means that you can verify data, certified with SCertifiedBTreeMap using agent-js library.

Both K and V have to implement StableType and AsFixedSizeBytes traits. SCertifiedBTreeMap also implements both these traits, so you can nest it into other stable structures. K also has to implement AsHashableBytes trait. V also has to implement AsHashTree trait. SCertifiedBTreeMap also implements AsHashTree, so you can nest it into itself.

For a real-world example of how to use this data stucture, visit this repository.

Features:

1. You can nest multiple SCertifiedBTreeMaps into each other to create more complex Merkle trees.
2. O(logN) perfromance and proof size.
3. Batch API - modify the map multiple times, but recalculate the underlying Merkle tree only once.
4. Witnesses of a single key-value pair, range proofs and proofs of absence of key are supported.

Examples

// create a wrapping structure, to be able to implement custom traits
#[derive(StableType, AsFixedSizeBytes, Ord, PartialOrd, Eq, PartialEq, Debug)]
struct WrappedNumber(u64);

// implement borrow, to be able to use &u64 for search
impl Borrow<u64> for WrappedNumber {
    fn borrow(&self) -> &u64 {
        &self.0
    }
}

// implement AsHashableBytes to be able to use the type as a key
impl AsHashableBytes for WrappedNumber {
    fn as_hashable_bytes(&self) -> Vec<u8> {
        self.0.to_le_bytes().to_vec()
    }
}

// implement AsHashTree to be able to use the type as a value
impl AsHashTree for WrappedNumber {
    fn root_hash(&self) -> Hash {
        leaf_hash(&self.0.to_le_bytes())
    }

    fn hash_tree(&self) -> HashTree {
        leaf(self.0.to_le_bytes().to_vec())
    }
}

// create the map
let mut map = SCertifiedBTreeMap::<WrappedNumber, WrappedNumber>::new();

// insert some values in one batch
map.insert(
    WrappedNumber(1),
    WrappedNumber(1)
).expect("Out of memory");

map.insert(
    WrappedNumber(2),
    WrappedNumber(2)
).expect("Out of memory");

map.insert(
    WrappedNumber(3),
    WrappedNumber(3)
).expect("Out of memory");

// recalculate the Merkle tree
map.commit();

// prove that there is a value by "2" key
let witness = map.witness(&2);
assert_eq!(witness.reconstruct(), map.root_hash());

// prove that there is no key "5"
let absence_proof = map.prove_absence(&5);
assert_eq!(absence_proof.reconstruct(), map.root_hash());

// prove that all three keys are there
let range_proof = map.prove_range(&1, &3);
assert_eq!(range_proof.reconstruct(), map.root_hash());

Another example with nested maps

// same setup as in previous example
// create the outer map
let mut outer_map = SCertifiedBTreeMap::new();

// create a couple of nested maps
let mut map_1 = SCertifiedBTreeMap::<WrappedNumber, WrappedNumber>::new();
let mut map_2 = SCertifiedBTreeMap::<WrappedNumber, WrappedNumber>::new();

// nest maps
outer_map.insert(WrappedNumber(1), map_1)
    .expect("Out of memory");
outer_map.insert(WrappedNumber(2), map_2)
    .expect("Out of memory");

// insert some values into nested maps
// with_key() commits changes automatically
outer_map
    .with_key(&1, |val| {
        val
            .unwrap()
            .insert_and_commit(
                WrappedNumber(11),
                WrappedNumber(11),
            )
            .expect("Out of memory");
    });

outer_map
    .with_key(&2, |val| {
        val.unwrap()
        .insert_and_commit(
            WrappedNumber(22),
            WrappedNumber(22),
        )
        .expect("Out of memory");
    });

// create a witness for some key in a nested map using `witness_with()`
let witness = outer_map.witness_with(&2, |map_2| {
    map_2.witness(&22)
});

assert_eq!(witness.reconstruct(), outer_map.root_hash());

Implementations

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes, V: StableType + AsFixedSizeBytes + AsHashTree> SCertifiedBTreeMap<K, V>

pub fn new() -> Self

Creates a new SCertifiedBTreeMap

Allocates a small amount of heap memory.

pub fn insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)>

Inserts a new key-value pair into this SCertifiedBTreeMap, leaving it in the uncommited state, if the insertion was successful

• See also SCertifiedBTreeMap::commit
• See also SCertifiedBTreeMap::insert_and_commit
• See also SBTreeMap::insert

pub fn insert_and_commit( &mut self, key: K, value: V, ) -> Result<Option<V>, (K, V)>

Inserts a new key-value pair into this SCertifiedBTreeMap, immediately commiting changes to the underlying Merkle tree, if the insertion was successful

See also SCertifiedBTreeMap::insert

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Ord + ?Sized,

Removes a key-value pair from this SCertifiedBTreeMap, leaving it in the uncommited state, if the removal was successful

• See also SCertifiedBTreeMap::commit
• See also SCertifiedBTreeMap::remove_and_commit
• See also SBTreeMap::remove

pub fn remove_and_commit<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Ord + ?Sized,

Removes a key-value pair from this SCertifiedBTreeMap, immediately commiting changes to the underlying Merkle tree, if the removal was successful

• See also SCertifiedBTreeMap::remove

pub fn clear(&mut self)

Removes all key-value pairs from this map, swapping the underlying Merkle with a fresh one and leaving it in the commited state

pub fn get<Q>(&self, key: &Q) -> Option<SRef<'_, V>>

where K: Borrow<Q>, Q: Ord + ?Sized,

See SBTreeMap::get

pub fn get_random_key(&self, seed: u32) -> Option<SRef<'_, K>>

See SBTreeMap::get

pub fn with_key<Q, R, F: FnOnce(Option<SRefMut<'_, V>>) -> R>( &mut self, key: &Q, f: F, ) -> R

where K: Borrow<Q>, Q: Ord + ?Sized,

Allows mutation of the value stored by the provided key, accepting a lambda to perform it

This method recomputes the underlying Merkle tree, if the key-value pair is found

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: Ord + ?Sized,

See SBTreeMap::contains_key

pub fn len(&self) -> u64

See SBTreeMap::len

pub fn is_empty(&self) -> bool

See SBTreeMap::is_empty

pub fn iter(&self) -> SBTreeMapIter<'_, K, V>

See SBTreeMap::iter

pub fn commit(&mut self)

Commits all uncommited changes to this data structure, recalculating the underlying Merkle tree

Merkle tree recomputation is a very expensive operation. But you can save a lot of cycles, if you’re able to commit changes in batches.

While SCertifiedBTreeMap is in the uncommited state, every call that touches the underlying Merkle tree will panic (SCertifiedBTreeMap::prove_absence, SCertifiedBTreeMap::witness_with, SCertifiedBTreeMap::prove_range, [SCertifiedBTreeMap::as_hash_tree]).

pub fn prove_absence<Q>(&self, index: &Q) -> HashTree

where K: Borrow<Q>, Q: Ord + ?Sized,

Constructs a Merkle proof that is enough to be sure that the requested key is not present in this SCertifiedBTreeMap

This proof is simply a proof that two keys around the requested one (remember, this is a BTree, keys are arranged in the ascending order) don’t have anything in between them.

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

Panics

Panics if this map is the uncommited state. Panics if the key is actually present in this map.

pub fn prove_range<Q>(&self, from: &Q, to: &Q) -> HashTree

where K: Borrow<Q>, Q: Ord + ?Sized,

Constructs a Merkle proof that includes all keys of the requested range

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

Panics

Panics if this map is the uncommited state.

pub fn witness_with<Q, Fn: FnMut(&V) -> HashTree>( &self, index: &Q, f: Fn, ) -> HashTree

where K: Borrow<Q>, Q: Ord + ?Sized,

Proves that the key-value pair is present in this SCertifiedBTreeMap, revealing the value itself

This method accepts a lambda, so it is possible to witness nested SCertifiedBTreeMaps.

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

Panics

Panics if this map is the uncommited state.

pub fn witness<Q>(&self, index: &Q) -> HashTree

where K: Borrow<Q>, Q: Ord + ?Sized,

Same as SCertifiedBTreeMap::witness_with, but uses AsHashTree::hash_tree as lambda

Use to witness non-nested maps

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes + Debug, V: StableType + AsFixedSizeBytes + AsHashTree + Debug> SCertifiedBTreeMap<K, V>

pub fn debug_print(&self)

Trait Implementations

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes, V: StableType + AsFixedSizeBytes + AsHashTree> AsFixedSizeBytes for SCertifiedBTreeMap<K, V>

const SIZE: usize = 16usize

Size of self when encoded

type Buf = <SBTreeMap<K, V> as AsFixedSizeBytes>::Buf

Buffer that is used to encode this value into

fn as_fixed_size_bytes(&self, buf: &mut [u8])

Encodes itself into a slice of bytes.

fn from_fixed_size_bytes(buf: &[u8]) -> Self

Decodes itself from a slice of bytes.

fn as_new_fixed_size_bytes(&self) -> Self::Buf

Encodes itself into a new Self::Buf of size == Self::SIZE

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes, V: StableType + AsFixedSizeBytes + AsHashTree> AsHashTree for SCertifiedBTreeMap<K, V>

fn hash_tree(&self) -> HashTree

Returns the entire Merkle tree of this SCertifiedBTreeMap, without revealing values

Important

This method can make your canister easily reach cycles message limit and is present entirely because of compatibility with Dfinity’s RBTree. Only use it with small enough trees.

Panics

Panics if this map is the uncommited state.

fn root_hash(&self) -> Hash

Returns the root hash of the tree without constructing it. Must be equivalent to [HashTree::reconstruct].

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes + Debug, V: StableType + AsFixedSizeBytes + AsHashTree + Debug> Debug for SCertifiedBTreeMap<K, V>

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

Formats the value using the given formatter.

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes, V: StableType + AsFixedSizeBytes + AsHashTree> Default for SCertifiedBTreeMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: StableType + AsFixedSizeBytes + Ord + AsHashableBytes, V: StableType + AsFixedSizeBytes + AsHashTree> StableType for SCertifiedBTreeMap<K, V>

unsafe fn stable_drop_flag_on(&mut self)

Should set stable drop flag to on position, if it is applicable

unsafe fn stable_drop_flag_off(&mut self)

Sets stable drop flag to off position, if it is applicable

fn should_stable_drop(&self) -> bool

Should return the value of the stable drop flag

unsafe fn stable_drop(&mut self)

Performs stable drop, releasing all underlying stable memory of this data structure