ic-certified-map

Crates.ioic-certified-map
lib.rsic-certified-map
version0.4.0
sourcesrc
created_at2021-06-04 18:09:34.564958
updated_at2023-07-13 22:32:04.904779
descriptionMerkleized map data structure.
homepagehttps://docs.rs/ic-certified-map
repositoryhttps://github.com/dfinity/cdk-rs
max_upload_size
id406222
size67,524
Adam Spofford (adamspofford-dfinity)

documentation

https://docs.rs/ic-certified-map

README

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.

Commit count: 313

cargo fmt