Chameleon Network will propose and implement a variant of pBFT (practical Byzantine Fault Tolerance) [Castro et al., 1999] at the consensus layer. We will further improve its efficiency by employing the BLS-based aggregate multi-signature scheme (AMSP) [Boneh et al., 2018].
Tendermint, a popular implementation of pBFT, requires participants to have the same view for every block minted. Nodes must sync their status at every block, which causes communication overhead. Chameleon will propose multiview pBFT, whereby a node makes decisions based on its best view and does not require the syncing status of other nodes in the committee. Find more details on multiview pBFT.
Validator Life Cycle
Common pool: new staking node, waiting to be assigned to a particular shard Sync pool: sync the assigned shard’s data
Substitute pool: node finished sync its data, queueing in the substitute list of its shard
Committee pool: validate and vote blocks
4 states: new (in common pool), candidate (in sync pool), substitute (in substitute pool), committee (in committee).
Slashing Rules
For Chameleon Network, we will prefer a light punitive approach when it comes to slashing — i.e., a slashing policy that does not deduct any CHML from the stake or rewards of the validators. However, the policy must effectively prevent misbehavior and unreliability.
For each shard:
- If MissingSig <= ExpectedShardBlock / 2, then the node will be forced to unstake.
- If MissingSig > ExpectedShardBlock / 2, then the node will not receive any penalty.
The ExpectedShardBlock is calculated as follows:
Let M be the mean number of blocks created by the shards in an epoch. For each shard:
- If the number of blocks confirmed is smaller than M, then M becomes the ExpectedShardBlock for that shard.
- Otherwise, the ExpectedShardBlock is the number of blocks confirmed by the Beacon chain.
If a node is slashed, the 1750 staked CHML would be returned to the node operator, who may choose to re-stake at a later time. Rewards from slashed nodes will be distributed evenly to the remaining validators in the committee.
BLS-based Aggregate Multi-Signatures from Pairing
As the number of validators grows, the total size of all validator signatures also increases, impacting the block size. To solve this problem, we implement the BLS-based aggregate multi-signature scheme (AMSP) [Boneh et al., 2018].
When the block proposer proposes a new block, all the validators in the current committee verify the block and broadcast their signatures. All of these signatures are then aggregated into a single aggregate signature. Regardless of the number of validators, the size of the aggregate signature remains only 32 bytes.
Implementation
The implementation is mainly in the Consensus component in the Chameleon architecture.
The code will be open-source on GitHub with links to specific packages to be provided in the future.
- Multiview-pBFT: For the consensus algorithm, Chameleon will implement the Multiview-pBFT (Practical Byzantine Fault Tolerance).
- BLS: For multi-signature aggregation, Chameleon will implement BLS Multi-Signatures.
- RNG: For random number generation, Chameleon will currently use Bitcoin block hash. Other RNG solutions will be explored in the future.
We are going to propose a new approach to scale privacy on cryptonetworks by applying sharding on privacy transactions to increase throughput for Chameleon. Chameleon’s throughput will scale out linearly with the number of shards. The more shards we add, the more transactions it will be able to handle.
Multiview: A New Approach for PBFT Implementation
Problem
Many well-known approaches to implementing the Proof of Stake consensus, such as Tendermint [1], Hotstuff [2], and PBFT [3], are bi-modal. These protocols typically consist of a simple normal path where a leader makes proposals and everyone votes. When the normal path fails, the protocol switches to a much more complicated fall-back mode, typically called a “view change.” During the view change phase, participants use the same communication process to reach an agreement on the new view before returning to the normal path of producing blocks.
Chameleon Network’s BFT (Byzantine Fault Tolerance) proposes a simpler approach. Instead of reaching an agreement on a single view, participants can observe multiple views; the communication process used during view changes in existing approaches is now leveraged to propose the new block. Participants may have multiple different views, but when the majority (more than ⅔ of participants) commits a new block, it indicates that they have achieved consensus on that view. If they continuously produce blocks based on this view, it becomes dominant and achieves finality.
Preliminaries
- The number of malicious nodes in the network cannot simultaneously equal or exceed ⅓ of the overall nodes in the system during a given window of vulnerability.
- Nodes must be deterministic and begin in the same state.
- The final result ensures that all honest nodes agree on the correct and longest chain.
Protocol
Multiview PBFT details:
The Multiview PBFT protocol used by Chameleon Network has the following phases:
PROPOSE PHASE
- The Block Proposer broadcasts the PROPOSE_MESSAGE along with the proposed block to all validators in the committee.
VOTE PHASE
-
Validators broadcast the VOTE_MESSAGE and collect valid VOTE_MESSAGE(s).
-
After a bounded time T, if the number of valid votes (|VOTE_MESSAGE(s)|) exceeds ⅔ of the committee size, the process moves to the Commit Phase.
-
If the required threshold is not met, the system waits for a new Propose Phase to begin.
COMMIT PHASE
- Validators combine the valid VALIDATOR_SIGNATURE(s) and include it in the block.
- The block is then committed to the chain.
- After committing, the protocol transitions to a new Propose Phase.
In a typical scenario, Chameleon Network’s PBFT protocol behaves similarly to other PBFT implementations. A node is selected as the proposer and will propose a block; other committee members vote to decide whether the block should be appended to the chain. Proposers are chosen in a round-robin fashion based on their ID in the committee.
If a failure occurs in the normal case (for example, due to:
- A Byzantine proposer not proposing a new block or proposing multiple blocks within the same round, or
- A failure to collect enough votes due to delayed vote messages),
the committee members may see multiple different views. To restore consensus, the following general rules are applied:
- Do not propose multiple different blocks at the same block height.
- Follow the majority group to ensure a common view.
Vote and Propose Rules
To achieve consensus without requiring agreement on a view change, nodes in Chameleon Network’s committee use the following Vote Rules and Propose Rules:
Two vote rules for:
- Branches with the same height
- Branches with different heights
Two Propose rules for:
- Branches with the same height
- Branches with different height
Lemma 1. (Finality 1) If two consecutive blocks B_(n) & B_(n+1) on the same branch are committed in two consecutive time slots, then block B_(n) is finality.
Proof:
When block n is committed at time slot t, and block (n+1) is proposed at time slot (t+1), this implies that block (n+1) is proposed for the first time. This also implies that more than 2/3 of the committee members have received, agreed upon, and voted for it. Therefore, any further proposed block with height (n+1) will not receive enough votes to be committed, in accordance with Vote Rule 1. Furthermore, following Vote Rule 2, no branch can grow longer than the one containing block n.
Lemma 2. (Finality 2)
If two consecutive blocks, B_n and B_(n+1), on the same branch are committed at time slots t and (t+i), respectively, where B_(n+1) is first proposed at time slot (t+1), and this block is re-proposed at every time slot from (t+2) to (t+i), then block B_n is considered final.
Proof:
Since block n is committed at time t, and block (n+1) is committed at (t+i), where block (n+1) is first proposed at time slot (t+1), this implies that block (n+1) with time slot (t+1) is the latest one. Furthermore, more than 2/3 of the committee members have received, agreed upon, and voted for it. This means that any further proposed block (n+1) will not receive enough votes to be committed, in accordance with Vote Rule 1. Additionally, during the time slots (t+1), (t+2), …, (t+i), no other blocks except for block (n+1) at time slot (t+1) are proposed or committed. Due to Vote Rule 2, no branch can grow any longer than this one.
Finality Theorem
- IF a block at height h is first proposed and committed in the same time slot, THEN it is finalized.
- IF a block at height h is first proposed in the time slot t, it is committed in time slot (t+n), for n > 1, and is re-proposed in the consecutive time slots: t+1, t+2, …, t+n, THEN it is finalized.
Proof:
- (i) By Proposing Rules 1 and 2, the proposed block at height h is always part of the longest chain.
- (ii) Following Vote Rule 1, any other block at height h cannot be committed because it will not be able to collect enough votes. In other words, no multiple branches can be created at height h.
- (iii) Therefore, in order to be committed, any newly proposed block must append to this block. No branch can grow any longer than this one.
Thus, (i), (ii), and (iii) imply the Finality Theorem.
ANALYSIS
Observation 1:
If block bn is finalized, then further blocks will be appended to the branch containing bn, and any other branch b’n becomes obsolete. If a new block is successfully appended to another branch, say b’n, this implies that more than 2/3 of the participants do not agree that bn is finalized. This leads to a contradiction.
Theorem 1 (Consistency Proof):
Let ch be the chain:
ch := b₁b₂…bₙbₙ₊₁
and ch’ be the chain:
ch’ := b’₁b’₂…b’ₙb’ₙ₊₁
where bn₊₁ and b’n₊₁ are finalized, and if bn₊₁ = b’n₊₁, then bi = b’i for all i ∈ [n].
Proof:
Since bn₊₁ and b’n₊₁ are finalized, it means bn and b’n are also finalized. If bn ≠ b’n, this either violates Observation 1 or the assumption that more than 2/3 of the participants are honest.
Theorem 2 (Liveness Proof):
If an honest participant receives some transactions, those transactions will eventually be included in all honest participants’ finalized chains.
Proof:
- Observation 2: The proposer is selected in a round-robin fashion. Eventually, every
participant will become a proposer. The proposer can then include the transaction in the proposed blocks.
- Observation 3: If two blocks at the same height are committed, the block proposed earlier must be committed later. Following Propose Rule 1, nodes will vote for the block with the smaller round number only. If more than 2/3 of the nodes vote for the first proposed block, they will not vote for the later block.
Worst-Case Scenario:
Consider the worst-case scenario where two chains grow indefinitely. For this to happen, the following conditions must be satisfied:
- More than 2/3 of the participants (the “weak participants”) do not collect enough votes to commit any block but may vote for both chains, as shown in Fig 4.
- The remaining 1/3 of participants (the “power participants”) could propose and commit new blocks.
Proposers in the 1/3 power participants group are divided into two subgroups, with each subgroup alternately selected to propose blocks on chain 1 and chain 2.
When a participant proposes a block, the next proposer in the round may not receive any messages from other participants, allowing them to propose a block on the other chain.
Let N be the number of participants. In cases of peak network traffic, assume the probability of successfully transmitting a message between two participants is 0.5. The probability of a
participant not receiving any messages in a single round is then (0.5^N)^2. This probability becomes negligible as N grows. Furthermore, the probability of a participant failing to receive any messages over x rounds is (0.5^N)^(2x), which decreases exponentially as the number of rounds increases.
Therefore, the above conditions are practically impossible to maintain over multiple rounds, guaranteeing the liveness property.
Multiview PBFT vs Tendermint [1]
Tendermint Multiview
| Aspect | Tendermint | Multiview |
|---|---|---|
| Total messages | n+2n^2 | n+n^2 |
| Number of phases to commit | 3 | 2 |
| Throughput (T being the delay in transferring a message) | 1/(3T) | 1/(2T) |
Conclusion
The Multiview PBFT approach is simple but offers many advantages over Tendermint:
- In normal cases, Multiview PBFT increases throughput by 33% compared to Tendermint, and the total number of exchanged messages is reduced by nearly 50%. Both Tendermint and Multiview PBFT can achieve instant finality in a single block.
- Network Peaking: In the Tendermint approach, if more than 1/3 of validator vote messages arrive late, participants will continuously communicate to switch to a new view, and no block can be committed. In contrast, Multiview PBFT allows a block to be committed and appended to the chain despite such issues.
The Multiview PBFT approach has a natural philosophy: it respects the majority group. The powerful node—capable of committing blocks during bursts of network traffic—can advance the chain to new heights, even during periods of heavy network traffic.
References