Struct Map 

pub struct Map<D, K, V>
where
    D: SupportedDigest,
    K: VisitBytes + Clone,
    V: VisitBytes + Clone,
{ /* private fields */ }

Immutable Map w/ Inclusion Proofs

Usage

Using a Map should feel similar to using a HashMap. All maps begin by creating an empty map and then populating it with items. Each time you insert to a map, it creates a new map derived from the prior map. Once items are inserted, you can get an inclusion proof that demonstrates the presence of a key/value in a tree.

use warg_transparency::map::Map;
use sha2::Sha256;

let a = Map::<Sha256, &str, &str>::default();
let b = a.insert("foo", "bar");
let c = b.extend([("baz", "bat"), ("foo", "qux")]);

let proof = c.prove(&"foo").unwrap();
assert_eq!(c.root().clone(), proof.evaluate(&"foo", &"qux"));

Design

A Map is a key/value store backed by a Merkle tree. Its values are stored in a binary tree. A cryptographic hash function is applied to the key and its resulting bits are interpreted as a path to descend the tree. This implies that the depth of the tree is n where n is the number of bits in the cryptographic hash function. Because this would cause the tree to have 2^(n+1) - 1 entries (far too many!), the tree is sparse and only creates nodes as necessary to represent the contents in the tree.

Hashing Strategy

Leaf Nodes

Leaf node hashes are calculated using the one-byte 0 prefix to prevent collisions with branch hashes.

hash(Leaf(value)) = hash(0x00 || <value>)

For leaf nodes that semantically “contain no value”, the <value> provided is empty i.e. the zero-length byte sequence.

Branch Nodes

Branch node hashes are calculated using the one-byte 1 prefix to prevent collisions with branch hashes.

hash(Branch(left, right)) = hash(0x01 || hash(<left>) || hash(<right>))

Implementations

impl<D, K, V> Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone + ?Sized, V: VisitBytes + Clone,

pub fn root(&self) -> &Hash<D>

The hash of the root of the tree.

This uniquely identifies the map and its contents.

pub fn len(&self) -> usize

The number of items in the map.

pub fn is_empty(&self) -> bool

Whether or not the map is empty.

pub fn prove(&self, key: K) -> Option<Proof<D, K, V>>

Gets the value for a given key and a proof of its presence in this map.

pub fn insert(&self, key: K, val: V) -> Self

Insert a value into the map, creating a new map.

This replaces any existing items with the same key.

pub fn extend(&self, iter: impl IntoIterator<Item = (K, V)>) -> Self

Inserts all key/value pairs into the map, creating a new map.

Trait Implementations

impl<D, K, V> Clone for Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone, V: VisitBytes + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<D, K, V> Debug for Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone, V: VisitBytes + Clone,

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

Formats the value using the given formatter.

impl<D, K, V> Default for Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone, V: VisitBytes + Clone,

fn default() -> Self

Returns the “default value” for a type.

impl<D, K, V> Hash for Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone, V: VisitBytes + Clone,

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, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<D, K, V> PartialEq for Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone, V: VisitBytes + Clone,

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<D, K, V> Eq for Map<D, K, V>

where D: SupportedDigest, K: VisitBytes + Clone, V: VisitBytes + Clone,