Creator

Stebalien

Created

Mar 8, 2024 7:41 PM

Commitment Tree

Each F3 round commits to one or more values via a merkle-tree. This lets us extend the commitment with additional values (e.g., events) and/or alternative representations that may be better suited for different use-cases (e.g., a snark-friendly power-table representation).

These trees are simply inclusion proofs, not proper IPLD structures (they don’t use CIDs, CBOR, etc.). Many finality certificates will be proper IPLD (linking to committed values by CID), but validating these finality certificates will always require quite a bit of custom logic so using CIDs inside these commitments is overkill and unnecessary.

I’m proposing a simple, variable height binary Merkle tree:

Proofs in this tree are 32 * log2(max_key) bytes long and require log2(max_key) calls to the underlying hash function validate.

Unfortunately,

1. All committed values would have the proofs of the same length so there’s no way to give some values “smaller” proofs (e.g., because they’re more frequently validated in a system where proof length is critical).
2. We’d need to either commit to a height up-front or make it variable-height. If we make it variable height, proof validation logic will need to take this height into account and we’ll likely need to encode that height somewhere, complicating the algorithm a bit.

Option 2: Binary Tree with Inline Values (PROPOSED)

Given that all that, I’m proposing the following binary tree structure: a binary tree where each node has 3 32-byte words, the first two of which are left/right pointers (hashes) and the last is a value.

Specifically:

Where l/r are hashes of the left/right subtrees and the number in the third slot in each record indicates the record’s index.

We search according to the following algorithm (where we’re treating the l/r as pointers):

k := some_index
n := root_node
for x := k + 1; x > 1 && n != nil; x >>= 1 {
    n = n[x&1]
}
if n != nil {
    return n[2]
}
return nil

In English: Add 1 to the key, then walk the tree by reading the bits of the key LSB first until only a single 1 bit (MSB) remains. At that point, insert/retrieve the value in the third slot.

All-zero sub-trees hash to 0, all values default to 0.

Properties:

1. Fixed-size proofs for any given index, regardless of the number of elements in the tree.
2. Smaller keys have smaller proofs.
3. Merkle-proof validation (of any given index) can be unrolled and hard-coded without branches, if desired.

The downside is that proof sizes are approximately doubled for the largest keys when compared to a regular binary merkle-tree.

Option 3: Linked-List of Exponential Binary Trees

A final option is to have a linked-list of binary trees that double in size every time:

Proofs in this tree are 1 (32-byte) word more space efficient than the tree I’m proposing, but:

1. The proofs are deeper (require ~2x the number of calls into the hash function).
2. The tree is lopsided (and that offends me, what can I say).

Power Table Format

For now, the only commitment in the commitment tree is the power table in a single, simple format: a large CBOR object in tuple representation, sorted by storage power (to make finality certificate bitfields more efficient):

struct PowerTableEntry {
    actor_id: ActorID,
    public_key: RawBytes,
    power: StoragePower,
}
type PowerTable = Vec<PowerTableEntry>;

Each entry should be less than 100 bytes so, even with 5K entries, this entire table will still be under 500KiB.

Consensus Power Calculation

Instead of using the power directly, we scale all power values the range [0, 0xffff] as this gives us more flexibility in the future (efficient power table representations, possibly more efficient ZK proofs, etc.).

Precisely:

1. Sum the storage power listed in the power table.
2. Multiply each value by 0xffff
3. Divide each value by the total power (round down, integer division).

The drawback is that, given 5000 participants (F3 scalability constraint), we could technically lose up to ~7.6% of the power due to rounding errors. As we approach 20k participants (if we could support that), this scaling could prevent consensus from working.

Finality Certificate Format

The v0 finality certificate is DagCBOR (tuple encoding) with the following format (simplified from here):

struct FinalityCertificate {
  version: uint64,
  // begin signed payload
	instance: uint64,     // f3 parameter
	round: uint64,        // f3 parameter
	value: Vec<ECTipset>, // tipset (should this go in the commitment merkle-tree?)
	commitment: [u8; 32], // root hash of the commitment merkle-tree
	// end signed payload
	senders: Bitfield
	signature: BLSAggregateSignature
	powerTable: Cid
	powerTableInclusionProof: RawBytes,
	// ... in the future, we'll have diffs, snarks, etc.
	// but that might be in different finality certificate versions.
}

Note:

1. I’m dropping the “deltas” because the power table itself is likely small enough (500KiB) to just download it every time. For a chain snapshot, multiple finality power tables should compress very well so there’s little need to create an optimized diff format (yet).
2. I’m adding a version, but I’m not sure if this is the right way to handle this. We may also just want to take a protobuf-like approach where we can add fields as long as we don’t renumber them? Or just… don’t have it?

Honestly, I’m not happy with the extensibility here.