From `Digest` to Bloom filter bits

Development
1

I’m trying to grasp the way from what I can see in an explorer for the MMR and active window of nullifiers / removal records to where they’re coming from. Am I correct that in the end of the day the removed records are represented in a block by Digest? Since it’s what in the (second) MMR. Then could you explain

Next question would be about chunks and what does the number of trials do exactly (is it about FRI, about Bloom, about something else?). But I found it quite hard to reason about without grasping the above.

Sorry if I missed some part of the docs or the article where this is explained. Direct me there then, pls.

2

The mutator set is our representation of the UTXO set – the set of UTXOs that have not been spent yet. The mutator set consists of two parts: A list of commits that represent the additions of UTXOs to the UTXO set, and a Bloom filter to represent the removal of UTXOs from the UTXO set. In order to represent these two lists using only very little data, both lists are converted into Merkle mountain ranges (MMR).

Am I correct that in the end of the day the removed records are represented in a block by Digest?

No. The removed records are represented by the bits that they flip in the (sliding window) Bloom filter. That’s the field absolute_indices on RemovalRecord. Which is nothing but an array of 45 u128 values.

I wouldn’t use the explorers as a reliable way to get insight into the architecture of Neptune Cash, they’re not yet developed enough for that yet.

ActiveWindow is just the last section of the current (sliding window) Bloom filter. It’s just a list of indices whose value should be interpreted as the position of set bits in a Bloom filter. They should also be interpreted as u128 values where the u32you see are offset by some big value that depends on how many times the window (in the sliding window Bloom filter) has slid.

3

Consider the Block structure

rust
pub struct Block {
    pub kernel: BlockKernel,
    pub proof: BlockProof,
}

pub struct BlockKernel {
    pub header: BlockHeader,
    pub body: BlockBody,
    pub(crate) appendix: BlockAppendix,
}

pub struct BlockBody {
    pub transaction_kernel: TransactionKernel,
    pub(super) mutator_set_accumulator: MutatorSetAccumulator,
    pub lock_free_mmr_accumulator: MmrAccumulator,
    pub block_mmr_accumulator: MmrAccumulator,
}

pub struct TransactionKernel {
    pub inputs: Vec<RemovalRecord>,
    pub outputs: Vec<AdditionRecord>,
    pub announcements: Vec<Announcement>,
    pub fee: NativeCurrencyAmount,
    pub coinbase: Option<NativeCurrencyAmount>,
    pub timestamp: Timestamp,
    pub mutator_set_hash: Digest,
    pub merge_bit: bool,
}

pub struct RemovalRecord {
    pub absolute_indices: AbsoluteIndexSet,
    pub target_chunks: ChunkDictionary,
}

pub struct AdditionRecord {
    pub canonical_commitment: Digest,
}

The inputs in the TransactionKernel structure above is where the removal records live. Each removal record is just a list of 45 u128values. But they carry around some extra data for the benefit of future light-clients.

So when the mutator set is updated with a new block, all the outputs of the block (outputs live in the `TransactionKernel`) are added to the AOCL, and the removal record’s Bloom filter indices are flipped in the Bloom filter. All complexity beyond this is just to compress the representations and to allow light clients (without access to all historical blocks) to manage their own membership proofs which they need to spend their UTXOs.

4

let me ask couple of smaller question to process this
also by “an explorer” I meant “just observing flowing the information” or “the final representation” – not a particular system

A state of the Bloom filter is represented via MmrAccumulator and Vec<u32>. From your reply I conclude that the vector holds the bits set by those [u128; 45], but what are Digest in the accumulator? That’s why I thought it’s just the stored digests from inputs.

Why neptune_cash::util_types::mutator_set::shared::NUM_TRIALS is called so; I mean what are the “trials”?

5

The entire Bloom filter is represented in two parts, the active window and the inactive part. The active window slides periodically, and whenever this happens, a new interval of bit-indices becomes inactive. The set of relative indices of set bits in this interval is called a Chunk. The inactive sliding window Bloom filter (SWBF) MMR accumulates hashes of Chunks.

Every sampled index gives rise to a test: is the bit set already? I guess I’m not super proud of the name but I wonder what else to call them if not “trials”. I’m happy to entertain counter-proposals. “Trial” is another word for “test” and using the different word helps to distinguish from other tests that are also being done. I certainly don’t want to call them “num indices” because we already have too many different types of indices and too many numbers of them in various data structures.

These indices relate to the Bloom filter.

1 Like
6

The MMR is a commitment to the inactive part of the Bloom filter. The actual state of the entire Bloom filter can only be read from the archival mutator set. In the mutator set membership proofs, the state of the Bloom filter relevant to a UTXO is tracked, along with the witness data (parts of the MMR) relevant for the UTXO.

In summary: Actual Bloom filter is a list of indices that are set (as opposed to not set). The Bloom filter is divided into an active and an inactive part. The inactive part is divided into “chunks”. The commitment to the inactive part of the Bloom filter is an MMR. And the leaves in this MMR are hashed chunks.

1 Like
7

Thank you, @sword-smith addressed exactly the things I still had after @aszepieniec explanation. :100:

As I go now in smaller questions: is the inactive part allowed to change? Or does all the nullifications happen only in the active part?

I’m often awful in naming entities. For me BLOOM_ITEM_BITS_LENGTH won’t raise the question I guess. And thanks again for the explanation!

8

Yes, the inactive part does change. In particular, it changes when someone spends an old UTXO – that is, a UTXO that was confirmed one or many window slides ago and has bits pointing into inactive Chunks. Those bits still need to be set!

1 Like