Struct Bitmap 

pub struct Bitmap<H: CHasher, const N: usize> { /* 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.

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<H: CHasher, const N: usize> Bitmap<H, N>

pub const CHUNK_SIZE: usize = N

The size of a chunk in bytes.

pub const CHUNK_SIZE_BITS: u64

The size of a chunk in bits.

pub fn new() -> Self

Return a new empty bitmap.

pub fn size(&self) -> u64

pub fn get_node(&self, position: u64) -> Option<H::Digest>

pub async fn restore_pruned<C: RStorage + Metrics + Clock>( context: C, partition: &str, pool: Option<ThreadPool>, ) -> 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.

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 bit_count(&self) -> u64

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

pub fn pruned_bits(&self) -> u64

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

pub fn prune_to_bit(&mut self, bit_offset: u64)

Prune the bitmap to the most recent chunk boundary that contains the referenced bit.

Warning

• Panics if the referenced bit is greater than the number of bits in the bitmap.

• Panics if there are unprocessed updates.

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(&self, bit_offset: 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 append_chunk_unchecked(&mut self, chunk: &[u8; N])

Efficiently add a chunk of bits to the bitmap.

Warning

• The update will not impact the root until sync is called.

• Assumes we are at a chunk boundary (that is, self.next_bit is 0) and panics otherwise.

pub fn append_byte_unchecked(&mut self, byte: u8)

Efficiently add a byte’s worth of bits to the bitmap.

Warning

• The update will not impact the root until sync is called.

• Assumes self.next_bit is currently byte aligned, and panics otherwise.

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

Add a single bit to the bitmap.

Warning

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

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

Get the value of a bit.

Warning

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

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

Get the value of a bit from its chunk.

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

Set the value of the referenced bit.

Warning

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

pub fn is_dirty(&self) -> bool

Whether there are any updates that are not yet reflected in this bitmap’s root.

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

The chunks (identified by their number) that have been modified or added since the last sync.

pub async fn sync(&mut self, hasher: &mut impl Hasher<H>) -> Result<(), Error>

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

pub async fn root( &self, hasher: &mut impl Hasher<H>, ) -> Result<H::Digest, Error>

Return the 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)

Warning

Panics if there are unprocessed updates.

pub fn partial_chunk_root( hasher: &mut H, mmr_root: &H::Digest, next_bit: u64, last_chunk_digest: &H::Digest, ) -> H::Digest

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

pub async fn proof( &self, hasher: &mut impl Hasher<H>, bit_offset: u64, ) -> Result<(Proof<H::Digest>, [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.

Warning

Panics if there are unprocessed updates.

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

Verify whether proof proves that the chunk containing the referenced 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.

Trait Implementations

impl<H: CHasher, const N: usize> Default for Bitmap<H, N>

fn default() -> Self

Returns the “default value” for a type.

impl<H: CHasher, const N: usize> Storage<<H as Hasher>::Digest> for Bitmap<H, N>

fn size(&self) -> u64

Return the number of elements in the MMR.

async fn get_node(&self, position: u64) -> Result<Option<H::Digest>, Error>

Return the specified node of the MMR if it exists & hasn’t been pruned.