Struct BitmapAccumulator

pub struct BitmapAccumulator { /* private fields */ }

The “bitmap accumulator” allows us to commit to a specific bitmap by splitting it into fragments and inserting these fragments into an MMR to produce an overall root hash. Leaves in the MMR are fragments of the bitmap consisting of 1024 contiguous bits from the overall bitmap. The first (leftmost) leaf in the MMR represents the first 1024 bits of the bitmap, the next leaf is the next 1024 bits of the bitmap etc.

Flipping a single bit does not require the full bitmap to be rehashed, only the path from the relevant leaf up to its associated peak.

Flipping multiple bits within a single chunk is no more expensive than flipping a single bit as a leaf node in the MMR represents a sequence of 1024 bits. Flipping multiple bits located close together is a relatively cheap operation with minimal rehashing required to update the relevant peaks and the overall MMR root.

It is also possible to generate Merkle proofs for these 1024 bit fragments, proving both inclusion and location in the overall “accumulator” MMR. We plan to take advantage of this during fast sync, allowing for validation of partial data.

Implementations

impl BitmapAccumulator

pub fn new() -> BitmapAccumulator

Crate a new empty bitmap accumulator.

pub fn init<T: IntoIterator<Item = u64>>( &mut self, idx: T, size: u64, ) -> Result<(), Error>

Initialize a bitmap accumulator given the provided idx iterator.

pub fn chunk_start_idx(idx: u64) -> u64

Find the start of the first “chunk” of 1024 bits from the provided idx. Zero the last 10 bits to round down to multiple of 1024.

pub fn apply<T, U>( &mut self, invalidated_idx: T, idx: U, size: u64, ) -> Result<(), Error>

where T: IntoIterator<Item = u64>, U: IntoIterator<Item = u64>,

Apply updates to the bitmap accumulator given an iterator of invalidated idx and an iterator of idx to be set to true. We determine the existing chunks to be rebuilt given the invalidated idx. We then rebuild given idx, extending the accumulator with new chunk(s) as necessary. Resulting bitmap accumulator will contain sufficient bitmap chunks to cover size. If size is 1 then we will have a single chunk. If size is 1023 then we will have a single chunk (bits 0 to 1023 inclusive). If the size is 1024 then we will have two chunks. TODO: first argument is an iterator for no good reason; might as well pass from_idx as first argument

pub fn append_chunk(&mut self, chunk: BitmapChunk) -> Result<u64, Error>

Append a new chunk to the BitmapAccumulator. Append parent hashes (if any) as necessary to build associated peak.

pub fn root(&self) -> Hash

The root hash of the bitmap accumulator MMR.

pub fn readonly_pmmr( &self, ) -> ReadonlyPMMR<'_, BitmapChunk, VecBackend<BitmapChunk>>

Readonly access to our internal data.

pub fn as_bitmap(&self) -> Result<Bitmap, Error>

Return a raw in-memory bitmap of this accumulator

Trait Implementations

impl Clone for BitmapAccumulator

fn clone(&self) -> BitmapAccumulator

Returns a copy of the value.

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

Performs copy-assignment from source.