Design a new mechanism about stake and election

[hongda3141]

Design a new mechanism of stake and election for axon.
Here is my design draft:

A mechanism which can supports user-customizable

Provide traits to define the node type and election algorithm in election, and users can customize the specific implementation mechanism.

At the same time, several built-in schemes are provided for users to choose. For example, the combination of "nominator, verifier, supervisor" or "nominator, agent, election committee" is provided in the node type;
The election algorithm trait provides "weighted phragmen algorithm" or "Verifiable Random Number (VRF)" for developers to choose.

The election process would like this:

1. The app chain specifies parameters, including the pledge threshold, node type & election algorithm, epoch & slot interval.
2. Nodes pledge a certain amount to the ckb chain according to the rules.
3. According to the open role interface, select its node type.
4. If the candidate type is selected, the election will be carried out according to the election algorithm.
5. After determining the node type, the verification process is performed according to the configuration of epoch.
6. Repeat step 3.

Provided configurable options:

1. The number of cycles between epoch and slot, the range of epoch including slot is [16,32].
2. The choice of node type, the node type needs to provide the following classifications:
   Has a voting function;
   function as a validating node;
   It can function as a governance committee member to determine the election process and arbitration;
3. Provide the trait of the election algorithm;
   Algorithms that support weighted types;
   Algorithms that support verifiable random numbers;

Default built-in functions:

1. The data structure of historical state records:
   Considering that proof of non-existence may be required, use an SMT that readily provides this feature.
   The record content is:

1. The pledged amount.
2. Current node role, node role history, and corresponding block pledge information (used for tracking of disciplinary mechanisms).
3. Record the proposal history and "whether selected as an agent" information for rewards.
4. The history of the health state of the node is used for the investigation of security issues and the introduction of the node reputation function, and it is considered to be stored in a trusted node.

2. Staking plan:
   The pledge is on the CKB chain cell, and the pledge is managed using type script.
   Functions to be provided:

1. Pledge status (time, quantity, lock proposal information, etc.).
2. When the node does evil/violates the rules, it provides the seizure function.
3. Provide bonus function.

3. The scheme to prevent verification nodes from not producing blocks:
   Run the daemon process, when all the verifiers are not selected, or there is no block scenario, run a secondary, cyclic verifier selection algorithm in the background to avoid this situation, the verifier selected by this algorithm always generates secondary The secondary block will only take effect when the node does not produce a block.

4. Fork detection and fork accountability:
   Fork detection uses multiple full-node communications to determine whether there is a malicious node, and fork accountability is used to track and identify malicious behavior on the network.

upgrade:

1. Need to support hot upgrade.
2. Try to reduce the mechanism that relies on game theory to be effective.
   For example, the premise of "the more pledged, the more reliable the node" adjusts the weight of candidate nodes.
3. Upgrade technical details:
   Consider using snapshots to record information. When the upgrade proposal is passed, the upgrade is completed by starting a new daemon process.

demo case for abstract:

use ckb_std::{
    ckb_types::{bytes::Bytes, packed::*, prelude::*},
    high_level::{load_cell_data, load_script},
    traits::{HeaderProvider, SystemProgramProvider},
};

struct Candidate {
    name: String,
    votes: u64,
}

struct Election {
    candidates: Vec<Candidate>,
}

impl Election {
    fn new() -> Self {
        Self {
            candidates: Vec::new(),
        }
    }

    fn add_candidate(&mut self, name: String) {
        self.candidates.push(Candidate {
            name: name,
            votes: 0,
        });
    }

    fn vote_for_candidate(&mut self, name: &str) -> bool {
        for candidate in self.candidates.iter_mut() {
            if candidate.name == name {
                candidate.votes += 1;
                return true;
            }
        }
        false
    }

    fn get_winner(&self) -> Option<&str> {
        let mut max_votes = 0;
        let mut winner = None;
        for candidate in self.candidates.iter() {
            if candidate.votes > max_votes {
                max_votes = candidate.votes;
                winner = Some(candidate.name.as_str());
            }
        }
        winner
    }
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Error {
    InvalidInput,
    InvalidScript,
    InvalidData,
}

pub struct ElectionContract<'a, T: HeaderProvider + SystemProgramProvider> {
    pub header: T::Header,
    pub system_program: T::SystemProgram,
    pub script: Script,
    pub data: Bytes,
    pub election: &'a mut Election,
}

impl<'a, T: HeaderProvider + SystemProgramProvider> ElectionContract<'a, T> {
    pub fn new(
        header: T::Header,
        system_program: T::SystemProgram,
        script: Script,
        data: Bytes,
        election: &'a mut Election,
    ) -> Self {
        Self {
            header,
            system_program,
            script,
            data,
            election,
        }
    }

    pub fn run(&mut self) -> Result<(), Error> {
        if !self.verify_input() {
            return Err(Error::InvalidInput);
        }

        let inputs = self.script.args().unpack();
        let outputs = self.script.code_hash().unpack();
        let data = self.data.as_slice().unpack::<(String, String)>()?;

        match data.0.as_str() {
            "add_candidate" => {
                self.election.add_candidate(data.1);
            }
            "vote_for_candidate" => {
                if !self.election.vote_for_candidate(data.1.as_str()) {
                    return Err(Error::InvalidData);
                }
            }
            "get_winner" => {
                if let Some(winner) = self.election.get_winner() {
                    self.data = Bytes::from(winner);
                } else {
                    self.data = Bytes::new();
                }
            }
            _ => return Err(Error::InvalidData),
        }
        Ok(())
    }

    fn verify_input(&self) -> bool {
        self.script
            .args()
            .verify_hash(self.data.as_slice(), self.script.code_hash())
    }
}

[hongda3141]

CKB chain:

stake and mint/award contract on one cell.
In the vote phase, the assets of the node stake are locked and unlocked after the view is over.
Unlock and distribute rewards after locking the candidate asset.view.

cross-chain(IBC):

{
"stake_number":"",
"node_key/nodeId":"",
"election_rule": {
// ckb contract use for stake/mint, no need to define election_rule
},
}

Axon chain:

election process (system contract);

contract Skeleton {
  function candidateList() public;
  function nodeHistory() public;
  function getTotalVoteCount() public;
  function getVoteCount(bytes32 nodeId) public;
  function vote(bytes32 nodeId) public;
  function registerNode(bytes32 nodeId) public;
}

election interface contract:

contract Rule {
  function rulesOfWeight() public;
  function rulesOfRole() public;
  function rulesOfRandom() public;
  function rulesOfpunishment() public;
  function rulesOfreputation() public;
}

[hongda3141]

The general idea now:
Refer to the election process of most projects on the market, most of them have the same process (1. Propose who to be the verification node 2. Candidates for the verification node run for election). The difference is mainly the specific algorithm of these two steps. So we could open the specific algorithm of these two steps into an interface, which will be implemented by axon users.
The specific algorithms of these two steps can be roughly classified into two categories: "weight calculation rules" and "definition of node functions", so the currently considered open interfaces are also these two categories.

Program interface design:

1. Customize the weight
2. Customize the roles and functions of nodes
3. Parameters of the election process can be customized

Q&A

1. Questions about the Election Commission:
   By examining several blockchain projects, the function of the election committee of most projects is almost the same as that of the verification node.
   Although there is a special case, Cardano's Election Committee, it is designed more for proposal management.
   Therefore, in this scheme, the election committee can play the same role as a set of verification nodes.
2. The solution of configuring leader for EVM multi-signature:
   Using a third-party daemon.
   The reason is that for engineering design considerations, it is not recommended to set a function inside the distributed nodes to allow them to monitor themselves, which will lead to many unpredictable problems.

[hongda3141]

The latest requirements indicate that both staking and election logic need to be placed on the L1.

[KaoImin]

Here is the latest version:

This document describes the validator selection procedure in Axon, which is critical for ensuring the security and stability of the network. Validators are in charge of participating in the consensus process. In essence, anyone can participate in the validator selection process, by either staking their AT tokens in the stake type script or delegating their tokens to another participant via the delegate type script, who acts as a validator candidate with the delegated tokens. Afterward, a metadata type script selects the stakers with the highest stakes to become future validators. We have also designed the corresponding incentive mechanism, encoded in checkpoint type script, to encourage the participants to act honestly.

Protocol Design

Protocol Participants

• Staker: Participants who wish to become validators. They stake Axon Token (AT) into the stake type script, either with their own tokens or with delegated tokens via delegate type script.
• Delegator: Participants who delegate their tokens to their selected stakers, to increase the latter’s chance to be selected as the validators and share the staker’s rewards.
• Validator: Participants of Axon’s consensus that is elected from stakers. The set of validators is selected as the top quorum stakers corresponding to the current epoch, which is defined next. The selection logic is defined in metadata type script. The validator set changes for every epoch.
• Seeder: The founder, who can create and issue AT, initialize the Axon chain.
• Kicker: A permissionless role that handles the following function:
  • Relay the out point of the latest metadata cell to Axon, and relay the latest checkpoint to CKB.
  • Update the metadata through subscribing the checkpoint cell、Stake SMT cell and Delegate SMT cell in CKB.
  • Update Stake SMT cell and Delegate SMT cell by applying Stake AT cells and Delegate AT cells.
  • Reboot the inactive Axon chain by re-staking and generating new metadata.

Key Concepts

• CKB: The underlying layer 1 design of Axon.
• Epoch: The tenure of a validator set, lasting a fixed number of x Axon blocks.
• Period: A fixed interval (y Axon blocks) after which one of the validators must submit the latest Axon state to CKB. When choosing the parameters, we ensure that:
  1. x is divisible by y, i.e., y|x , so that an epoch is consist of some checkpoints exactly
  2. (x / y) mod validator_len must be 0.
• Metadata: some basic and important information of Axon, such as: validators’ list, proposal count history of validators, consensus configuration. It is stored in metadata cell in CKB and will be updated at the start of each epoch.
• Checkpoint: the latest status of Axon, such as: state root, block hash, proposal count, BLS signature. It is submitted by an Axon node to a kicker at the end of each period.
• Dividend Ratio (per validator): the staker and delegators assign a percentage of the block reward based on the AT amount.
• Delegate threshold (per validator): The minimum amount of delegated token that a staker accepts from each delegator, set by the staker.
• Quorum: the max number of validators in an epoch.
• SMT: Stands for Sparse Merkle Tree. For axon, only SMT root is stored in Cell to reduce the capacity cost in CKB. It is applied in Stake, Delegate and Reward.

Overview

We describe the entire protocol as five sub-protocols—Initiation, Stake, Delegation, Validator Selection, Checkpoint Record, and Reward Distribution, according to their functionalities. Initiation is executed only at the beginning of Axon’s lifecycle, while the other five are executed continuously or repeatedly.

Initiation. The founder prescribes the metadata of the first two epochs and initiates the Axon chain. The metadata is recorded in metadata cell, and it is written the genesis of Axon.

Stake. The participant stakes AT to the stake type script. The kicker will apply all Stakers’ stake infos to Stake SMT cell periodically. Once staked, the participant becomes a staker and can participate in the validator selection process for the Axon validators. Stakers can increase their probability of becoming a validator by staking additional AT at any time, and can also redeem their staked AT. All these operations will take effort after two epochs. If a staker loses in the election process, their AT tokens will be promptly refunded.

Delegation. The participant delegates or redeems AT to a staker. Similar to staking protocol, the operation will take effort after two epochs. And, the kicker will apply all Delegator’ stake infos to Delegate SMT cell periodically.

Validator Selection. The process can be triggered by either the founder or a kicker. Both parties share the responsibility of updating the metadata at the beginning of each epoch. The metadata includes important information such as the basic configuration and the list of validators. The logic for calculating the new list of validators is encoded in a metadata type script. This script calculates the sum of tokens staked and delegated by each staker, using a fixed weight. Additionally, it verifies the delegate_cell_type_code_hash to ensure the delegate script is valid. The top quorum of stakers with the highest sum of tokens will be elected as the new validators.

Checkpoint Record. The axon validators update the checkpoint at the end of each period. Therefore, the checkpoint cell record the latest status of Axon.

Reward Distribution. There is no explicit distribution process as all information needed for reward are stored on chain. Users(Staker or Delegator) can claim their reward any time they want if the reward’s lock time has expired. The claim history is recored in Reward SMT cell. Remember, users must claim their reward in one year. Otherwise, the expired reward will be cleared automatically.

Protocol in Detail

Initiation

This stage is initiated by the seeder. The seeder creates the following cells:

• issuance cell
• selection cell
• metadata cell
• stake SMT cell
• delegate SMT cell
• reward SMT cell

Once these cells are created, the seeder can start the Axon chain. The cells’ details are explained in the following section.

Stake

Assume the quorum is 1, a part of stake process is as follows:

Any holder of AT can participate in staking by locking the token. All staking information related to the Axon chain is recorded in off-chain server in the form of SMT. While only the SMT root is stored in Stake SMT cell to reduce capacity cost. Every Axon-Based chain needs to created a unique Stake SMT cell.

To ensure the stability of the staking information and prevent it from being altered, the staking operation will only become active after a minimum of two epochs, which will depend on the configuration at the time of staking. Stake within the same inauguration epoch by the same staker in one epoch will be merged and recorded. Besides, there is at most 3 * quorum record info in an epoch.

Delegate

A delegate cell will be created every time a participant successfully stakes AT. This cell will store information about the delegation and the dividend ratio. Each staker needs create an unique delegate cell.
People who hold AT can delegate their tokens to the staker. All delegating information related to the Axon chain is recorded in off-chain server in the form of SMT. While only the SMT root is stored in Delegate SMT cell to reduce capacity cost. Every Axon-Based chain needs to created a unique Delegate SMT cell.
Delegators can add or withdraw their AT at any time. Just like staking tokens, the delegation will become effective after a minimum of two epochs. In the event that the corresponding staker fails to be selected as a validator, the delegator needs to send transaction to withdraw their tokens mannually.

Checkpoint Record

In the Axon blockchain, the responsibility of submitting a checkpoint rotates among the nodes after each period ends. This ensures that the task of checkpointing is distributed among the nodes and helps to prevent any single node from having too much control over the process. A checkpoint refers to a stored record of the latest state of the Axon chain along with a proof of the latest block, which includes:

• version
• state root
• latest period number
• epoch number
• latest block hash
• proposal count
• BLS signature
• AT type hash
• stake cell lock hash
• delegate cell lock hash
• withdrawal lock code hash
• timestamp

The latest status, excluding the proposed count, can be confirmed using proof. The proposed count can be verified through the state root. This serves to ensure the integrity and consistency of the blockchain and protect against any potential malicious attacks.

The submission process is permissionless and non-rewarding. The process is a validator submits the latest status to a kicker, then the kicker builds the checkpoint-update transaction and sends it to CKB. The validation of checkpoint submissions is critical to ensure the liveness of the Axon chain. If the validators fail to submit, the Axon will be considered inactive.

Reward Distribution

At the end of each epoch, the kicker will update metadata cell to store the propose counts of this epoch’s validators. As the Stake SMT cell and Delegate SMT cell all containes the history infos, we don’t need to distribute rewards at the end of every epoch. Instead, we only need to record the claim history of every user in Reward SMT cell. Because we can calculate every epoch’s reward of every user by referencing Stake SMT cell、Delegate SMT cell、Delegate Cells.

Validator Selection

At the start of epoch n, the metadata for epoch n + 1 can be updated by anyone, provided that the epoch_len or period_len is not changed. However, if there is a change in epoch_len or period_len, the founder script must be signed.

At this moment a metadata script elects the top n nodes with the highest amount of staking as the validator list of the next epoch. The amount of staking is determined by the sum of staking and delegate amounts, each with a different weight. According to the description in stake token, there are at most 4 * quorum of valid staking info when update metadata. The 4 * quorum staking info is consist of the previous validators and at most 3 * quorum new stakers. Therefore, about 3 * quorum stakers will fail to be elected. The tokens of the lose-election stakers and those who delegate will be unlocked.

Kicker Process

The kicker is permissionless that can be deployed by anyone. A kicker has some functions:

1. Kickers should subscribe to the metadata cell in CKB and transmit the latest metadata cell out point to Axon when it is updated.
2. Kickers are responsible for constructing and submitting checkpoint transactions. They periodically check Axon's height to determine if a checkpoint needs to be submitted. In case of an inactive node, the kicker will request the checkpoint from other nodes and submit it.
3. When the latest checkpoint of an epoch is submitted, a kicker will build the metadata update transaction and the reward distribution transaction.
4. If the Axon lose liveness, a kicker can punish the validators and originate a novel staking process for the purpose of selecting a fresh cohort of validators.

---

Detail Implementation

2-layer smt

We are taking stake as an example, the same argument applys to delegate as well.

SMT pattern

For every Axon-Chain, there will be dozens of stakers. If we store the infos of stakers on CKB, it will cost lots of CKB capacity which may worth lots of money. Thanks to the flexibility of CKB, we can utilize the so called SMT pattern to reduce space consumption. Instead of storing all data, we just need to store the SMT root of these data. To implement this idea, the Axon-chain developer needs to create a stake SMT cell to store the root.

Moreover, we want to reduce staker‘s burden of claiming rewards，so we store the stake info of all epoches. Like the smt pattern mentioned above, we can implement a 2-layer smt to store the meta info on CKB. The layer2 smt root stored in Stake SMT cell is calculated like following:

The key of layer 2 smt is epoch, value is smt root of layer 1 smt. The key of layer1 smt is account, value is stake token amount.

The followint process is am example of verifying staker 1 have staked 100 AT in epoch 1.

1. get smt root of epoch 1 from witness, denoted as smt_root_epoch1; get its smt existence proof from witness, denoted as smt_proof_l2; get layer2 smt root from Stake SMT cell, denoted as smt_root_l2.
2. verify smt_root_epoch1 is in smt_root_l2 by providing smt_proof_l2.
3. get stake amount of staker1 from witness, denoted as stake1_amount; get its smt existence proof from witness, denoted as smt_proof_l1; we have gotten its smt root smt_root_epoch1.
4. verify amount is in smt of layer1. then we can prove that staker1 did actually staked 100 AT at epoch 1.

Remember, to create a transaction of this kind, there must be a off-chain server storing this 2-layer smt.

mitigate SMT cell competition

Because there are so many stakers, if we let each staker change root in Stake SMT cell. Then there might be fierce competition for Stake SMT cell which leads to high possibility of stake failure. The staker may have to sign the stake transaction again and again. To mitigate this pain, the stake tx signed by users will only update their own Stake AT cell. A kicker will aggregate lots stake infos of all stakers to update Stake SMT cell. This kind of batch update will reduce cell competition by a large margin(especially for delegation).