Consensus: A Combination of iPoS, Multiview-pBFT, and BLS

dungtran · 17 May 2022 09:01

Sending Cryptocurrencies Confidentially: Ring Signature, Homomorphic Commitment, and Zero-Knowledge Range Proofs ▸

Privacy at Scale with Dynamic Sharding ▸

Consensus: A Combination of iPoS, Multiview-pBFT, and BLS ▾

Both beacon chain and shard chains use the same consensus mechanism to produce new blocks.

Incognito Proof-of-Stake (iPoS)

Incognito implements the more energy-efficient Proof-of-Stake [King and Nadal, 2012] in lieu of Proof-of-Work [Dwork and Naor, 1992; Juels, 1999].

In the first generation of POS, each staking node (validator) has one vote. The more validators, the more secure the chain. However, PoS is not a scalable consensus; communication overhead increases linearly with committee size. Research demonstrates that POS is only able to achieve a reasonable level of security when there are 600 validators or more in the committee [Luu et al. 2016]. A committee with 600 nodes faces real challenges in syncing statuses and exchanging messages in order to create a new block.

To overcome scaling-related communication problems, Delegate Proof of Stake (DPOS) was first proposed by Bitshares (https://bitshares.org/). This could be considered to be the second generation of POS. In DPOS, only a small group of validators are selected into the committee, where they have the right to propose and verify new blocks. This solves the communication problem of the POS approach, but it sacrifices properties of decentralization and trustlessness, specifically:

Staking nodes have to trust delegated nodes.
The smaller the committee size, the easier it can be compromised.
Only delegated nodes work (i.e propose & verify blocks), the staking node does nothing.

Incognito proposes iPOS which allows for both scale and trustlessness. Anyone can be a validator candidate by staking PRV. The beacon chain randomly assigns validators to each shard. At a moment, only a small group of validators in a shard is selected into the committee. The committee of each shard is responsible for proposing and verifying blocks. The committee rotates, so every validator has to put in an equal amount of work. As for decentralization, each shard block signed by the shard committee will be verified by the beacon committee. If any incorrect transaction such as airdrop or double spending is detected, the beacon will inform all other shards using the proof. All honest shards will vote to slash the byzantine shard’s committee.

Multiview Practical Byzantine Fault Tolerance (M_PBFT)

Incognito proposes and implements a variant of pBFT [Castro et al., 1999] at the consensus layer. We 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. Incognito proposes 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 here.

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

Figure 1. Life cycle

Slashing Rules

When it comes to slashing, we prefer a light punitive approach – i.e. a slashing policy that does not deduct any PRV from the stake/reward of the validators. However the policy must effectively prevent misbehavior and unreliability.

For each shard,

If MissingSig <= ExpectedShardBlock / 2 then the node will forced to unstake.
If MissingSig > ExpectedShardBlock / 2 then the node will not receive any kind of penalty.

The ExpectedShardBlock is calculated as follows:

Let M be the mean of 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 is the ExpectedShardBlock of the shard.
– Otherwise, the ExpectedShardBlock is the number of blocks confirmed by the Beacon chain.

If a node is slashed, the 1750 staked PRV would be returned back to the node operator and they may re-stake at a later time. Rewards from slashed nodes will be distributed evenly to remaining validators in a committee.

BLS-based Aggregate Multi-Signatures from Pairing

As the number of validators grows, the total size of all validator signatures also grows and impacts 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 is only 32 bytes.

Implementation

The implementation is mainly in the Consensus component in the Incognito architecture.

Figure 5. The layered Incognito architecture.

The code is open-source on Github with links to specific packages provided below.

Multiview-pBFT . For the consensus algorithm, Incognito implements the Multiview-pBFT (Practical Byzantine Fault Tolerance). Its code is in the blsbft package.
BLS. For multi-signature aggregation, Incognito implements BLS Multi-Signatures. Its code is in the blsmultisig package.
RNG. For random number generator, Incognito currently uses Bitcoin block hash. We’ll explore other RNG solutions in the future. Its code is in the btc package.

We have proposed a new approach to scale privacy on cryptonetworks by applying sharding on privacy transactions to increase throughput for Incognito. Incognito throughput scales out linearly with the number of shards. The more shards we add, the more transactions it can handle.

Incognito Software Stack: Navigating the Incognito Source Code ▸

Incognito Performance ▸

Network Incentive: Privacy (PRV) ▸

User-Created Privacy Coins ▸

Use Cases: Privacy Stablecoins, Privacy DEX, Confidential Crypto Payroll, and more ▸

Future Work: Smart Contracts, Confidential Assets, Confidential IP, and more ▸

Conclusions, Acknowledgments, and References ▸

Grant · 7 February 2020 08:16

There’s so much amazing tech in this project, I have massive respect for the researchers/cryptographers/devs who have pulled all these novel approaches into one project.

Is there an origin story? @duy, what was the turning point when you decided to build the Incognito product? Was all the development and research done in-house, or did we pull in experts who were working on it already?

0x123 · 7 February 2020 11:20

Small questions: is there a dedicated phase to elect new proposer? If not, why is it so and how do you manage it? Is there any trade-off between the 2 approaches?

Also, as I understand, the default pBFT algorithm has the property of instant-finality (a block once gathered enough votes won’t be reverted). Does Incognito also have this property?

dungtran · 17 February 2020 03:18

Small questions: is there a dedicated phase to elect new proposer?
If not, why is it so and how do you manage it? Is there any trade-off between the 2 approaches?

None, the proposer is selected in round robin fashion based on their id. The trade-off is that in this approach the next proposer is predictable, so it could be the target for DOS-like attack. However a node will play proposer role in a short time - max 40s - it’s a challenge for DOS attack. While we could save the election phase.

Also, as I understand, the default pBFT algorithm has the property of instant-finality (a block once gathered enough votes won’t be reverted). Does Incognito also have this property?

In Incognito pBFT, a block will achieve finality when one or more blocks appended to this block. This is because we solve the problem of timeout different from Tendermint, Hotstuff or PBFT. They synchronize the new view whenever they failed to commit a block, we instead store all commit block in a tree, the longer branch will win and finality. All honest committee won’t have chance to add any block to the shorter branch.

In our approach, we could not only save the communication of view change but also let the committee driven to the majority agreement group.

ruler · 13 February 2020 09:44

Every consensus algorithm basically solved forked issue in decentralized world. If there is something call instant-finality, in my opinion it’s not decentralized anymore. So the different between incognito’s pBFT consensus and PoW is:

Incognito: the longest chain (based on incognito’s convention) is absolutely finality, it can never be revert or replaced by another forked chain, it’s strict rule. Only if they break the code then incognito’s rule break
Bitcoin: the longest chain (chain with the highest sum of PoW) is probability finality, it can be replaced. Although it’s very hard for bitcoin or ethereum right now but consider bitcoin gold in the past. This is doable in bitcoin. Bitcoin code allow a forked chain to replace current longest chain.

0x123 · 14 February 2020 11:08

Hmmm, interesting… So Incognito’s consensus has probabilistic finality (like many other Nakamoto-based blockchains). The view change communication is minimal (just like another round of pBFT) and infrequent (since it’s rarely needed, only when a proposer failed to produce a block). Therefore, IMHO, the advantage of instant-finality far outweighs this added complexity. What’s your opinion on this?

Also, Bitcoin has a safe threshold of 6 confirmation to ensure a block is practically finalized. What is Incognito’s number?

dungtran · 14 February 2020 13:13

In the normal (happy) case, a block of Incognito got finality is when a new block appended to it (just one block later than other PBFT).

In case proposer failed to produce block (due to late vote msg arrival, off-line validator…), Tendermint, Hotstuff or other implementation of pBFT have to communicate to reach an agreement on a new view with new proposer, i.e. late vote message arrival will no longer valid since it’s in the old view. Incognito’s approach uses the same view, then it’s just continue to propose and commit new block. In this way, new appended blocks may create a tree, but the protocol let the committee to build new blocks only on the longer branch. This approach will make the system have more chance to commit block in the case the network traffic peaking.

ruler · 16 February 2020 05:23

I think something is misunderstand here. Incognito is absolutely finality, which mean when a block is finality then no other shorter brand can rewrite this block. Probabilistic mean, a block may finality at this time but might be not in the future.
Let’s me put it clear from the beginning. There are two seperate algorithm:

Producer new block (eth: POW)
Build longest chain (eth: GHOST protocol)
Blockchain use PoW algorithm like ethereum, use GHOST protocol to build a longest chain. For example: Assume that, the longest chain is now at 79 and we producer two 80 block, 80A and 80B. Block 80A is the longest chain at the time but later on some other block 80A may be come stale block and 80B is in the longest chain.

But Incognito is not like that, when 80A become the longest chain then it forever stay in the longest chain, there is not way 80B can kick 80A out. Incognito’s use pBFT to producer new block and also new block will get finality after it satisfy all the pre-defined rule. The rule is rather simple, after a new block (block A) is created, in the next view if just only one block is created in that view then block A is absolute finality. Block A can’t be revert or become stale

dungtran · 20 February 2020 18:31

For more detail about the different b/w view change approach (like Tendermint, Hotstuff,…) vs Incognito approach.

On common case, View Change Approach (VCA) block committed means finality, Incognito’s finality when having an appended block.
Failed to propose block in a block time.
a. >= 1/3 off-line validators: both approaches are failed to commit any new block.
b. Network peaking: late vote messages arrival, VCA continue to change to new view, no block could commit. Incognito Approach, block can be committed because messages arrive after timeout is counted.

Note that, in Incognito Approach, if it failed to commit a block in a round, new proposer in the new round is just to re-produce proposed block (in previous round) so the chain focus on one branch only.