Certified Map

This package provides a map that can be used by Internet Computer canisters to implement certified queries.

Features

• Incremental certification. The canister can store thousands of entries while keeping the cost of certification relatively low.

• Proofs of absence. If the requested key is not present in the map, the returned tree structure allows the caller to verify that fact.

• Relatively small merkle proofs. The size overhead of the certificate is O(log N), where N is the number of entries in the map.

Implementation Details

The canister uses an augmented Red-Black binary search tree to store the entries. Each node of the search tree is annotated with the root hash of the hash tree built from the subtree rooted at this node. Each time the tree is rotated or modified, the corresponding hashes are recomputed in O(1) time.

lib.rs:

This package provides a map backed by a Merkle tree that can be used by Internet Computer canisters to implement certified queries.

You can certify your data by using the RbTree type as a map of known names to the values you want certified. After you record its root_hash into your canister's certified data, query calls can access a data certificate proving that the IC certified the hash, under the path /canister/<canister id>/certified_data. By providing this certificate, as well as a witness that the value exists in the hash, you can then prove to the caller that the IC certified the data.

Example

thread_local! {
    static COUNTER: Cell<i32> = Cell::new(0);
    static TREE: RefCell<RbTree<&'static str, Hash>> = RefCell::new(RbTree::new());
}

#[update]
fn inc() {
    let count = COUNTER.with(|counter| {
        let count = counter.get() + 1;
        counter.set(count);
        count
    });
    TREE.with(|tree| {
        let mut tree = tree.borrow_mut();
        tree.insert("counter", leaf_hash(&count.to_be_bytes()));
        ic_cdk::api::set_certified_data(&tree.root_hash());
    })
}

#[derive(CandidType)]
struct CertifiedCounter {
    count: i32,
    certificate: Vec<u8>,
    witness: Vec<u8>,
}

#[query]
fn get() -> CertifiedCounter {
    let certificate = ic_cdk::api::data_certificate().expect("No data certificate available");
    let witness = TREE.with(|tree| {
        let tree = tree.borrow();
        let mut witness = vec![];
        let mut witness_serializer = serde_cbor::Serializer::new(&mut witness);
        witness_serializer.self_describe();
        tree.witness(b"counter").serialize(&mut witness_serializer).unwrap();
        witness
    });
    let count = COUNTER.with(|counter| counter.get());
    CertifiedCounter {
        count,
        certificate,
        witness,
    }
}