# 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,

- 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).
- 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:**

- Fixed-size proofs for any given index, regardless of the number of elements in the tree.
- Smaller keys have smaller proofs.
- 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:

- The proofs are deeper (require ~2x the number of calls into the hash function).
- 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.

**TODO:**Pick a key for this commitment.

# 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:

- Sum the storage power listed in the power table.
- Multiply each value by
`0xffff`

- 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:

- 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). - 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.