Epoch Commitment Chain (ECC)

The following document is a result of the work of the Virtual Milestone task force. It is a proposal for the commitments of the blocks, transactions, and state, supported by dividing the Tangle into epochs.

Note that the following names have changed:
confirmation → acceptance
finalization → confirmation
TSC → Fishing threshold
CTT → ATT
RCTT → RATT

Motivation

Regular checkpoints into the network are key for agreeing on a finalized state, so data can be compressed into a local snapshot and pruned. These checkpoints must also provide a mechanism to prove inclusion after the Tangle has been pruned. It was initially proposed to have “elected” Milestone creators that would be used by the rest of the network. This approach would require a consensus mechanism on its own to agree on who these creators are and it was therefore deemed impractical.
Instead, we propose that every node includes cryptographic commitments on acceptations as part of every block it issues. Those commitments then form chains, and nodes agree on the same ledger state by following the heavier one.

Epochs

Epoch is a time range of fixed duration EpochDuration. Epoch can be calculated based on the Genesis timestamp (or other agreed point in the snapshot) and provided Epoch Index (EI).

Bucket is used for Tangle segmentation. Buckets are created based on Epochs. A bucket is a part of the Tangle that belongs to a certain epoch or several consecutive epochs.
Given block and corresponding objects belong to a bucket if block timestamp falls into underlying epochs that define this bucket.

Usage:

  • Notation of buckets can be used in a storage solution that would allow for efficient pruning.
  • Epochs are used for Epoch Commitments. Commitments always compress all the information (blocks and accepted value payloads) of a certain epoch.

Parametes: EpochDuration, BucketSize

It is easy to derive the respective block EI knowing Genesis timestamp, EpochDuration, and block timestamp. The same in opposite direction, with Genesis timestamp, EpochDuration, and EI, the Epoch time range can be retrieved.

Transaction membership to an epoch is retrieved based on the timestamp of its attachments (accepted block that includes this transaction).

Time

  • Accepted Tangle Time (ATT):
    • the timestamp of the latest accepted block.
  • Confirmed Tangle Time (CTT):
    • the timestamp of the latest finalized block.
  • Relative Accepted Tangle Time (RATT):
    • the timestamp of the latest accepted block.
    • If ATT does not advance, tips are not invalidated: acceptations are not halted as the activity window keeps moving.
    • RATT = ATT + (wall clock - last time ATT was updated). Almost the same to wall clock when in sync, but relative to Tangle when syncing so the Tangle can be properly replayed.
    • RCTT = CTT + (wall clock - last time CTT was updated)

Fishing condition (formerly TSC)

To preserve acceptations liveness, the fishing condition uses ATT:

  • Let m(tip) be the oldest accepted block in the tip’s past cone that is directly referenced by an unaccepted approver.
  • The tip is considered valid if the difference between the timestamp of m(tip) and ATT is below a certain threshold.

Definitions

Acceptations are live, confirmations are safe (Ebb-and-Flow approach).

Acceptation of a block

A block is accepted according to an OTV mechanism using active cMana with an activity window calculated based on RATT clock.
Block is accepted if:

  • it has collected enough AW
  • it is not orphaned
    where block is orphaned if it contains a block in its past cone which satisfies the following:
    • it is in a committable epoch
    • it is not contained in your preferred epoch commitment for that epoch

This additional rule about block orphanage is needed in case of a situation when a node sees a block that in his perception of a Tangle has collected enough AW, however it is not a part of a preferred commitment.

Additionally, block acceptation:

  • Represents a local perception of a node.
  • is ‘reorgable’. In some extreme cases and during a network partition it might happen that an already accepted transaction will turn out to lose in favor of a conflicting one. With a fixed mana vector (based on commitments) we will not reorg but resync.
  • Pruning is not possible yet, since epoch acceptations are based on the local perception of the node about a reorgable attribute.

Acceptation of an epoch

Epoch is committable (becomes ready for commitment) when:

  • The epoch is old enough.
    Epoch needs to be older than CommitableAgein reference to ATT clock. CommitableAge should be defined as a multiplayer Fishing condition:CommitableAge = X * Fishing threshold
    Epoch is old enough if: ATT - CommitableAge > Epoch End Time
  • A Pending Conflict Counter (PCC) associated with each epoch is equal to 0. Each node updates its Pending Conflict Counters locally when a new conflict is created and when they are resolved.

Additionally:

  • Acceptation of an Epoch is declared on the Tangle by each node when they issue a block including a commitment to this epoch.
  • You cannot prune yet at this stage

Confirmation of a block

Details on a block confirmation will be defined in a separate document regarding Confirmation Gadget.

  • A confirmation will happen on a level of blocks and should not depend on commitments and epochs, to allow for fast confirmation times.
  • Confirmed blocks can be pruned, as confirmation can never be undone on the protocol level - no reorgs are allowed.
  • Confirmation will represent global preception.

Confirmation of an epoch

Epoch is confirmed when there exists a single block containing a commitment to this epoch that has been confirmed.

Commitments

  • Epoch Index (EI): the epoch index to this commitment refers. A block should refer to the latest epoch a node sees as committable.

  • Each block contains:

Name Full name Definition
prevEC previous Epoch Commitment The commitment from the previous epoch that matches previous ECR used in the current ECR
ECR Epoch Commitment Root The Merkle Tree Root of all commitment elements
EI Epoch Index We specify it explicitly in the message for convenience.
ECI Epoch Confirmation Index Index of the last confirmed epoch
  • EC (Epoch Commitment) - can be determined implicitly with
    EC = Hash(prevEC+ECR+EI)
  • Similar to block header in blockchain and ECR is Merkle Root of transactions
  • As the EC has the reference to the previous epoch EC it forms an ECC chain.
  • ECI should not be part of EC as every node can have a different perception
  • The first commitment of a node for a given epoch shall be created without taking into account existing commitments on the Tangle.
    • The node can later change its preference to a heavier commitment in the subsequent blocks.

Epoch Commitment Root (ECR)

Each block has an Epoch Commitment Root. ECR is a Merkle tree calculated from:
Tangle Root, State Mutation Root, State Root, Mana Root

ECR Anatomy

A detailed explanation of ECR building blocks:

  • Tangle Root: a Merkle root of accepted blocks of the bucket of epoch EI.

    • Serves as a statement of what block the node sees as accepted in the Tangle.
    • Data Structure: Sparse Merkle Root of all possible block IDs
    • Usage: proving inclusion/absence of blocks.
  • State Root: a Merkle root of a sparse tree of all unspent UTXOs at the end of the epoch. Only changed leaves need to be recomputed.

    • Outputs that do not have any accepted consumer at the end of the epoch.
    • Data Structure: Sparse Merkle root of entire ledger state, all possible output IDs.
    • Usage: Can be used to validate snapshots.
  • State Mutation Root: a Sparse Merkle root of the accepted transactions of the bucket. Equivalent to the state-mutating root of Chrysalis’ Milestones.

    • It’s a mutation proof of the previous epoch commitment State Root to the current one. A State Root can be validated by applying the State Mutation Root to the State Root of the previous epoch.
    • Data Structure: sparse Merkle Tree of all possible transaction IDs.
    • Usage: proving inclusion of accepted value payloads. Proof that the transaction existed and got accepted. Proof of absence.
  • Mana Root: a Merkle root of a sparse tree of Node identities (key) and Mana balance (value) for all public keys.

    • An account-based Mana ledger at the end of the epoch.
    • Data Structure: Sparse Merkle Tree of all possible node identities
    • Usage: It can be used to prove the Mana balance of a validator.

Dealing with different ECCs

Upon a partition, as Tangles and acceptation grow apart from each other, different EC chains can start to form.
Nodes track ECC locally and follow the heavier ECC.

After the partition ends nodes will simply follow the heaviest chain.
We do not merge Tangles upon partition: we select who wins. The rest of the blocks would need to be reattached.

Visualization of the Tangle with many forked ECC.

:spiral_note_pad: Additional remarks regarding commitments:

  • A block commitment is not allowed to reference an epoch too far in the past, the block won’t be picked up in TSA.
  • The mechanism used to determine the winning chain is based on the same metric used for acceptation: active cMana (i.e. which chain shows the most liveness).
  • In congested regimes we cannot rely on eventual consistency: we would be breaking CC assumptions (i.e. we do not solidify the other Tangle to determine its weight).

Deciding on winning EC

Block is modified as follows:

  • Each block contains the signature of the node committing to a certain state.
  • Node signs: H(EC+timestamp+content)
  • Timestamp should be included in the hash of the block header along with EC
  • Content of a block contains all previous block fields, such as parent references, payload, nonce ect

Heaviest chain

Because each block commitment is signed, nodes can create virtual blocks (commitment - issuer list) with all node identities that are committed to a given epoch.
The next step is to calculate the heaviest chain based on this list and local perception of mana.

Local perception of mana can be defined as:

  • the mana from the forking point ( the last common commitment, last confirmed epoch)

  • or later can be based on the committee

:pencil: Note:

  • What if the sending node does not know about EC_0?
    • To always be able to proof EC_0, nodes cannot forward blocks with different commitments than their own
  • Nodes need to forward blocks with different commitments?

Proof

The proof can be generated as follows:

  • once a node receives a new different commitment EC_0 it asks the neighbor for proof of weight for EC_0
  • the node provides the proof as follows, based on any block issued in EC_0 by the top mana holders

Proof for EC_0:

NodeID Timestamp Hash(Content) Signature

Switching to the heavier chain

Upon determining a better ECC to follow, our Ledger State, including Mana, needs to be reset to the forking point and the ECC solidified backward and replayed.

Parameters

Name Value Comment
Fishing threshold 20s
Epoch old enough older than ATT - 2* Fishing threshold
Epoch Duration 20s
Oldest Commitable Epoch threshold 1 Epochs number in the past node is allowed to commit

Orphanage detection

The accepted parent counter represents the number of accepted parents, if the tip is orphaned (it has reached the Fishing condition) we walk the past cone and decrease the counter.
The orphaned block becomes unaccepted.
Orphanage event is triggered when:

  • tip reaches a Fishing condition
  • its accepted parent counter is 0

Idea: instead of doing the Fishing threshold lazily on tip selection (which might lead to delayed orphanage detection), we keep all blocks in a timed executor, and all blocks that are not accepted within the Fishing threshold and have the counter=0 are orphaned, including its future cone.
The time executor is queued on block’s solidification; so its fishing condition (and orphanage) is evaluated proactively and during tip selection.

Syncing

Bootstrapping:

  • Request an arbitrary block with correct commitment per epoch, from tips to Snapshot.
  • Verify that each Tangle Root includes the previous one: forming a chain.
  • Verify that each State Root corresponds to applying the State Mutation Root to the State Root of the previous epoch.
  • Verify that the oldest State Root corresponds to Snapshot.
  • Solidify the past cone of epoch block (oldest to newest).
  • We consider ourselves in sync if wall time - CTT is below a certain threshold (used only for informative purposes).
  • sync from the snapshot (past) to the future
  • Request blocks by whole epochs

Being in sync

  • A node does not fall out of sync (after it becomes synced during bootstrapping), since we can’t tell the difference between no blocks being sent, being eclipsed, or whatever. We can detect and report certain things, massive drop in cMana, connections broken, lost neighbors, etc.

  • Once you’re bootstrapped you should never stop issuing blocks.

5 Likes

Do we filter out epochs incorrect (although semantically valid) ECs when selecting tips? If not, then any epoch can easily be committed.

We select only blocks with the commitment we like, so the totally incorrect commitments should be orphaned, And the selected fragment is about epoch confirmation (previously finalization) not sure how this is connected to the question :slight_smile:

2 Likes