[Milestone] Cryptarchia (PPoS + consensus)

[Cofson]

Subproject Overview

This subproject is comprised of:

Research

• All research documentation is kept in Notion.
• Consensus: Cryptarchia is a derivative of Crypsinous (Ouroboros-type) with improvements to make it practical. The main points to tackle are:
  • Stake Relativization: Crypsinous defines relative stake (0,1), which is not a realistic setting. We need to either map the total stake of the system to a relative stake, or the other way around, modify Crypsinous to operate with absolute values. Deep analysis of this has been conducted (see here and here) and we have a fairly solid understanding of this problem at the moment.
  • Simplifications: For example, epochs may be an unnecessary complication in the protocol.
  • Network Level Protection: This will be discussed in the next subproject. Without this, privacy is not attainable.
• Economics of Private Proof of Stake: The PPoS part of Cryptarchia refers to understanding:
  • Wealth concentration effects analysis. This is work done in collaboration with the Tokenomics team.
  • Definition of a fork-choice rule (which affects the wealth concentration). This is done based on the results from the previous point.

Future Improvements

• Tagging Attack: Network anonymity is not enough to hide the winner of an election. Sender-initiated tagging attacks require specific mitigations, and it is critical for us to solve it to be able to claim that we have achieved PPoS.
• Finality Gadget: Ouroboros-like protocols do not have deterministic finality, and instead rely on probabilistic finality. A finality gadget would help achieve deterministic finality at certain points. This is an open question, and unlikely that we actually build it as it brings similar problems than full pBFT-like consensus (although is more relaxed as it can rely on the Ouroboros consensus).

Development

In the case of development, the main challenges are:

• Being able to develop the known parts while there are some unknown parts. A good example of this is requiring the Coordination Layer to be defined in order to implement the Proof of Leadership.
• Proper transition from specifications into an implementation that can be thoroughly tested. This point is relevant because it is expected that more time will be spent in hardening the implementation than in coding a first version of it.

Estimated Delivery Date

September 2024. The highest uncertainty comes from a dependency on the Coordination Layer, which is largely unexplored yet.

Resources Required

So far, the team has involved:

• Mathematical Analysis: Alexander
• PPoS and Consensus Improvements: Alexander, David, and Giacomo
• Executable Specs: David and Giacomo
• Implementation: Giacomo
• Tokenomics Modeling: Frederico

I do not foresee an increase in contributors dedicated to this subproject, as we have a clear path and sufficient expertise.

Deliverables

• Mathematical Analysis: Stake relativization (Intended audience: research team, for internal validation of our design.)
• Economical Analysis: Wealth concentration (Intended audience: research team, for internal validation of our design.)
• Executable Specs: Cryptarchia. (Intended audience: engineering team, for implementation.)
• Rust Implementation: Cryptarchia consensus algorithm. Important note: we intend to have a full implementation, but the largest uncertainty is related to the dependency on the Coordination Layer in order to implement the Proof of Leadership. This component might not be deliverable by the defined deadline. (Intended audience: node operators running the reference implementation in the future.)

Tracking Metrics

In progress:

• Notion specs
• Github commits (executable specs and node implementation)
• Weekly progress reports

Finalized:

• Code deployed in Testnet

Work Breakdown

These are the remaining subtasks identified so far to achieve a reasonable state of this subproject.

• Leadership proofs (cryptography implementation)
• Leader Lottery (VRF evaluation)
• Leader Coin Evolution, used to prevent linking slot leaders, we need to evolve the leader coin each time it’s been used.
• Block / Header definition
• Ledger State Transition. Details on how to transition the ledger state given a new block should be specified.
• Epoch State: the shared base state of an epoch between all nodes participating in consensus
• Fork Choice Rule, based on the economic analysis of wealth concentration.
• Fork maintenance: how to maintain the various chain forks.
• The chain may fork, and what to do with these abandoned forks has ramifications to the leader’s privacy. Each Leader proof reveals the nullifier of the leader coin.
• PoS Rewards.
• Key Erasure Scheme: The purpose of this scheme is to make the protocol resilient to adaptive corruption schemes.

Perceived Risks

The main risk is that we identify an impossibility to solve the tagging attack. This is unlikely though, since we have some potential solutions already.
All the other unknowns in this subproject pose low risk and aren't likely to be altering the roadmap. Additionally, we are quite confident that this is our best shot at Private Proof of Stake.