Consensus: A Combination of PoS, pBFT, and BLS

Introduction: A Platform of Decentralized Privacy Coins ▸

Shielding Cryptocurrencies: Turning Any Cryptocurrency Into a Privacy Coin ▸

Trustless Custodians: A Decentralized Approach to Cryptocurrency Custodianship ▸

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

Privacy at Scale with Sharding ▸

Consensus: A Combination of PoS, pBFT, and BLS ▾

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

Proof-of-Stake (PoS)

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]. Anyone can be a validator candidate by staking PRV. The minimum stake is 1,750 PRV. The beacon chain randomly assigns validators for each shard.

Each validator has one vote. A block is considered valid if it collects more than ⅔ valid signatures from the validator committee.

Practical Byzantine Fault Tolerance (pBFT)

Incognito 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].

At the beginning of each round, the smallest id validator is the first proposer. The proposer proposes the block and broadcasts it to the shard committee. Proposers take turns in a round-robin fashion, based on their id in the current committee setup.

image%20(24)

If a proposer fails to propose its block in less than the time taken to build the last three blocks, the next validator will be elected as the new proposer. If a proposer fails to propose its block on time, it will lose its reward for that epoch. If a proposer fails to propose its block three times in an epoch, it cannot be a committee member for the next three epochs.

Figure 3. Incognito implements a variant of Practical Byzantine Fault Tolerance.

Validators

Validators play an important role in the consensus mechanism. They collectively verify transactions and earn rewards in return.

Incentives

Validators earn Privacy (PRV), the native coin of the Incognito network, for every block created (Section 8).

When someone makes a privacy transaction (say, in pBTC or pDAI), validators also earn transaction fees in that currency.

Validator Lifecycle

We introduce a few parameters to explain the validator life cycle. These parameters are fine-tuned over time, as parameter fine-tuning is a crucial part of Incognito mechanism design.

PARAMETER DESCRIPTION DEFAULT
X The staking amount 1750 PRV
P The maximum number of substitutes per shard P=A*K
M The maximum number of validators per shards 32
K The maximum number of substitutions per shard in an epoch M/10
A The ratio between substitutes and substitutions 2
N The number of shards 8
B The block time 40s
T The number of blocks in an epoch 350

Table 1. Validator parameters.

The life cycle of a validator is as follows:

  • The user stakes X to become a candidate and waits until the next epoch for random selection. The maximum waiting time is T.
  • The candidate is randomly selected by the beacon chain to become a substitute for a specific shard Si with i ∈ [0, N).
    • If the number of current substitutes is less than P, the candidate automatically becomes a new substitute for shard Si.
    • Otherwise, the candidate will wait until the next epoch for the next random selection.
  • The substitute must sync all block data of shard Si in advance.
    • If the number of current validators in shard Si is less than M, the substitute automatically becomes a new validator for shard Si at the next epoch.
    • Otherwise, the substitute will replace an existing validator in shard Si at the next epoch.
  • The new validator starts producing blocks for shard Si.
  • The ex-validator becomes a normal user and can stake again (go back to the beginning of the life cycle).

Figure 4. The life cycle of a validator

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.

image%20(25)

Figure 5. The layered Incognito architecture.

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

  • pBFT . For the consensus algorithm, Incognito implements a variant of 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 ▸

4 Likes

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?

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?

1 Like

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.

3 Likes

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.
1 Like

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?

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.

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:

  1. Producer new block (eth: POW)
  2. 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

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

  1. On common case, View Change Approach (VCA) block committed means finality, Incognito’s finality when having an appended block.

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