Struct AuthenticatedBitMap 

pub struct AuthenticatedBitMap<D: Digest, const N: usize, S: State<D> = Clean<D>> { /* private fields */ }

A bitmap supporting inclusion proofs through Merkelization.

Merkelization of the bitmap is performed over chunks of N bytes. If the goal is to minimize proof sizes, choose an N that is equal to the size or double the size of the hasher’s digest.

Type States

The bitmap uses the type-state pattern to enforce at compile-time whether the bitmap has pending updates that must be merkleized before computing proofs. CleanBitMap represents a bitmap whose root digest has been computed and cached. DirtyBitMap represents a bitmap with pending updates. A dirty bitmap can be converted into a clean bitmap by calling DirtyBitMap::merkleize.

Warning

Even though we use u64 identifiers for bits, on 32-bit machines, the maximum addressable bit is limited to (u32::MAX * N * 8).

Implementations

impl<D: Digest, const N: usize, S: State<D>> BitMap<D, N, S>

pub const CHUNK_SIZE_BITS: u64 = PrunableBitMap<N>::CHUNK_SIZE_BITS

The size of a chunk in bits.

pub fn size(&self) -> Position

Return the size of the bitmap in bits.

pub const fn len(&self) -> u64

Return the number of bits currently stored in the bitmap, irrespective of any pruning.

pub const fn is_empty(&self) -> bool

Returns true if the bitmap is empty.

pub const fn pruned_bits(&self) -> u64

Return the number of bits that have been pruned from this bitmap.

pub fn last_chunk(&self) -> (&[u8; N], u64)

Return the last chunk of the bitmap and its size in bits. The size can be 0 (meaning the last chunk is empty).

pub fn get_chunk_containing(&self, bit: u64) -> &[u8; N]

Returns the bitmap chunk containing the specified bit.

Warning

Panics if the bit doesn’t exist or has been pruned.

pub fn get_bit(&self, bit: u64) -> bool

Get the value of a bit.

Warning

Panics if the bit doesn’t exist or has been pruned.

pub const fn get_bit_from_chunk(chunk: &[u8; N], bit: u64) -> bool

Get the value of a bit from its chunk. bit is an index into the entire bitmap, not just the chunk.

pub fn partial_chunk_root( hasher: &mut impl Hasher<Digest = D>, mmr_root: &D, next_bit: u64, last_chunk_digest: &D, ) -> D

Returns a root digest that incorporates bits that aren’t part of the MMR yet because they belong to the last (unfilled) chunk.

pub fn verify_bit_inclusion( hasher: &mut impl Hasher<D>, proof: &Proof<D>, chunk: &[u8; N], bit: u64, root: &D, ) -> bool

Verify whether proof proves that the chunk containing the given bit belongs to the bitmap corresponding to root.

pub async fn destroy<C: RStorage + Metrics + Clock>( context: C, partition: &str, ) -> Result<(), Error>

Destroy the bitmap metadata from disk.

impl<D: Digest, const N: usize> BitMap<D, N>

pub fn new(hasher: &mut impl Hasher<D>, pool: Option<ThreadPool>) -> Self

Return a new empty bitmap.

pub fn get_node(&self, position: Position) -> Option<D>

pub async fn restore_pruned<C: RStorage + Metrics + Clock>( context: C, partition: &str, pool: Option<ThreadPool>, hasher: &mut impl Hasher<D>, ) -> Result<Self, Error>

Restore the fully pruned state of a bitmap from the metadata in the given partition. (The caller must still replay retained elements to restore its full state.)

The metadata must store the number of pruned chunks and the pinned digests corresponding to that pruning boundary.

Returns an error if the bitmap could not be restored, e.g. because of data corruption or underlying storage error.

pub async fn write_pruned<C: RStorage + Metrics + Clock>( &self, context: C, partition: &str, ) -> Result<(), Error>

Write the information necessary to restore the bitmap in its fully pruned state at its last pruning boundary. Restoring the entire bitmap state is then possible by replaying the retained elements.

pub fn prune_to_bit(&mut self, bit: u64) -> Result<(), Error>

Prune all complete chunks before the chunk containing the given bit.

The chunk containing bit and all subsequent chunks are retained. All chunks before it are pruned from the bitmap and the underlying MMR.

If bit equals the bitmap length, this prunes all complete chunks while retaining the empty trailing chunk, preparing the bitmap for appending new data.

pub const fn root(&self) -> D

Return the cached root digest against which inclusion proofs can be verified.

Format

The root digest is simply that of the underlying MMR whenever the bit count falls on a chunk boundary. Otherwise, the root is computed as follows in order to capture the bits that are not yet part of the MMR:

hash(mmr_root || next_bit as u64 be_bytes || last_chunk_digest)

The root is computed during merkleization and cached, so this method is cheap to call.

pub async fn proof( &self, hasher: &mut impl Hasher<D>, bit: u64, ) -> Result<(Proof<D>, [u8; N]), Error>

Return an inclusion proof for the specified bit, along with the chunk of the bitmap containing that bit. The proof can be used to prove any bit in the chunk.

The bitmap proof stores the number of bits in the bitmap within the size field of the proof instead of MMR size since the underlying MMR’s size does not reflect the number of bits in any partial chunk. The underlying MMR size can be derived from the number of bits as leaf_num_to_pos(proof.size / BitMap<_, N>::CHUNK_SIZE_BITS).

Errors

Returns Error::BitOutOfBounds if bit is out of bounds.

pub fn into_dirty(self) -> DirtyBitMap<D, N>

Convert this clean bitmap into a dirty bitmap without making any changes to it.

impl<D: Digest, const N: usize> BitMap<D, N, Dirty>

pub fn push(&mut self, bit: bool)

Add a single bit to the end of the bitmap.

Warning

The update will not affect the root until merkleize is called.

pub fn set_bit(&mut self, bit: u64, value: bool)

Set the value of the given bit.

Warning

The update will not impact the root until merkleize is called.

pub fn dirty_chunks(&self) -> Vec<Location>

The chunks that have been modified or added since the last call to merkleize.

pub async fn merkleize( self, hasher: &mut impl Hasher<D>, ) -> Result<CleanBitMap<D, N>, Error>

Merkleize all updates not yet reflected in the bitmap’s root.