Scaling Blockchain Privacy with Dynamic Sharding

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 ▸

Scaling Blockchain Privacy with Dynamic Sharding ▾

Low-throughput is one of the biggest obstacles facing the mass adoption of cryptocurrencies. Throughput is measured by the number of transactions per second (TPS) confirmed on a cryptonetwork. For example, Bitcoin can only process 7-10 TPS [Croman et al., 2016; Li et al., 2018], while Visa can process 24,000 TPS [Visa, 2018].

Privacy transactions are even slower because of extra proof generation and verification steps. Transaction sizes are large because of the extra privacy data. For example, Zcash, a fork of Bitcoin with privacy features, can only process 6 TPS with a block size of 2 MB, a target block interval of 150 seconds, and an average transaction size of 2000 bytes. This is a big drawback.

We implement sharding on privacy transactions to increase throughput for Incognito [Kokoris-Kogias et al., 2018; Zamani et al., 2018; Zilliqa, 2017]. Incognito throughput scales out linearly with the number of shards. The more shards we add, the more transactions it can handle.

Incognito is designed as a network of blockchains. It has a single beacon chain (the “coordinator”) and N shard chains (the “workers”), which produce blocks in parallel. All shards work in parallel and are synchronized by beacon block time, which is divided into equal epochs.

Figure 1. Sharding on privacy transactions. Incognito throughput scales out linearly with the number of shards.

Shard Chains

Shards are organized by the last byte of sender addresses. Each shard has its own committee, randomly assigned by the beacon chain. A shard committee validates and confirms transactions belonging to it.

Every time a shard block is created, the beacon committee will verify and insert the valid block header into the beacon chain. If the block is not valid, the beacon will send the proof to all other shards, to vote to slash the misbehaving shard committee.

Figure 2. Shard Chains

Beacon Chain

The responsibility of the beacon chain is to verify shard blocks and coordinate shard chains. It is the global state of the entire network.

  • Beacon chain verifies the validity of shard blocks.
  • Beacon chain confirms cross-shard information. Each shard block header includes cross-shard information, indicating which shard this block has cross-shard to. In addition to the height of each shard chain, this information is also included in the block body.
  • Beacon chain manages the candidate and validator list. Whenever a user stakes PRV to become a validator, this action will be recorded in the block header.
  • Beacon chain shuffles committees. When a new random number is generated, it is recorded in the beacon block header.
  • The beacon block stores the Merkle root of the candidate list and the validator list, of both the beacon chain and shard chains.

Cross shard transaction

For cross-shard transactions, the sender shard creates a receipt containing all transactions to the receiver shard, then sends this receipt to the receiver shard. A brief of cross-shard transactions is also sent to the beacon chain. The UTXOs in the sender shard are locked to make sure they cannot be double-spent. The receiver shard checks the validity of the receipt and waits for confirmation of cross-shard info from the beacon chain, before approving the corresponding UTXOs as spendable.

Figure 3. Cross shard transaction.

Dynamic Committee Size

At the beginning of an epoch:

  • Substitute list is 100-400% of the current committee size

Committee size remains unchanged, 10% of committee members are replaced at each epoch, in round-robin fashion.

  • Substitute list is > 400% of the current committee size

Increase committee size by 15% of the current committee size (after subtracting the slashed members in the previous epoch).

  • Substitute list is < 100% of the current committee size

Reduce committee size by 10%

Dynamic sharding

Incognito chain is initially implemented with 8 shards. The number of shards could dynamically increase, up to 256 shards. Let X be the last byte of the sender’s public keys. The shard with id = X % number_of_shards will handle this transaction.

Every shard has a maximum (M) of committee members. When the substitute list of all shards is greater than 5M, the chain will double the number of shards. In this case, each shard will be split into two 2 new shards, as per the scheme in Figure 4:

Figure 4. Increasing shards

Example:

In the case of 8 shards, public keys with lastbyte = 0, 8, 16, 24, 32, 40… 240, 248 belong to shard 0. I.e shard_id = lastbyte % number_of_shards.

If doubled to 16 shards, shard 0 will be split into shard 0 and shard 8, which are called sibling shards. The public keys with lastbyte = 0, 16, 32,… 240 are in shard 0, and public keys with lastbyte = 8, 24, 40,… 248 are in shard 8.

The current committee and substitute nodes in shard 0 will be split equally into shards 0 and shard 8. This way, all committee members already have a full database to confirm any new transactions belonging to them.

If the committee size is smaller than the minimum committee size threshold, two sibling shards will be merged into one shard.

Analysis

When a shard is compromised, it might produce airdrop or double spent transactions. The beacon committee detects this and gives the proofs to other shards. If ⅔ of shards agree with the proofs, the compromised committee will be penalized. Therefore, an attacker needs to conquer at least ⅔ of shards in order to conquer the chain.

Let H be the number of honorable validators in a shard

B be the number of byzantine validators in a shard

Let n be the size of the committee

Let X be the number of byzantine validators in a committee

Then the probability of k byzantine validators in the committee of a shard, where 0<= k <= B, is

and, the probability of >=k byzantine validators in the committee of a shard is

Let S be the number of shards. As an attacker needs to conquer at least ⅔ of shards in order to conquer the chain, probability is

For example, let’s look at a scenario where there are 8 shards, a committee size of 50, and 200 nodes in the substitute list. Table 1 summarizes the probability of conquering the chain, given the percentage of nodes owned by the attacker.

Percentage of byzantine validators 20% 25% 30% 35% 40%
Probability of conquering the chain (8 shards) 2.04E-107 2.4439E-76 9.6104E-56 9.583E-41 2.4814E-29
Probability of conquering the chain (16 shards) 4.163E-214 5.973E-152 9.236E-11 9.1834E-81 6.1575E-58

Table 1. Probability of the attacker conquering the chain.

The probability of conquering the chain is extremely low, even if an individual owns 40% of validators.

Implementation

The implementation is mainly in the Blockchain 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.

  • Shards. Shards are subchains. A subchain is a Proof-of-Stake blockchain with its own committee of N nodes. A shard’s job is to produce new blocks via the Multiview Practical Byzantine Fault Tolerance (pBFT) consensus algorithm. Its code is in the blockchain package.
  • Beacon . Beacon is also a subchain. A beacon’s job is to coordinate the shards and maintain the global state of the network. Its code is in the blockchain package.
  • Synker. Synker makes sure the node is up to date among its peers and also broadcasts the node status to its peers. Its code is in the blockchain package.
  • Mempool . Mempool (memory pool) is a collection of transactions and blocks that have been verified but are not yet confirmed. Its code is in the mempool package.
  • Wallet. Software that holds all your Incognito keys. Use it to send and receive your Incognito tokens. Its code is in the wallet package.
  • Database . Incognito uses LevelDB to store block data. Its code is in the database package.

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

Multiview PBFT ▸

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 ▸

25 Likes

I keep coming back to this post. There is a lot of good technical information here I am trying to wrap my head around.

Thank you for this :+1:

4 Likes

:+1: :+1: :+1:

1 Like

@dungtran I think your analysis is wrong. Basically, if the proof needs > 2/3 agreements, then the attack only needs to conquer > 1/3 of the shards (to make sure that less than 2/3 of the shards confirm the proof => the proof is invalid).

You only mentioned the probability of compromising shards, what about the beacon chain? It’s much easier to attack this single committee, am I wrong?

1 Like

I still wonder how the proof is generated, and how other shards have enough information to validate this proof.

2 Likes

Hi AloneWalker,

I still wonder how the proof is generated, and how other shards have enough information to validate this proof.

The proof of a faulty tx consists of two blocks: the block containing the faulty tx and the block where its input is referenced to. Any validator could send out the proof of faulty tx. Validators from other shards only need to download 2 blocks to verify the correctness of the proof.

@dungtran I think your analysis is wrong. Basically, if the proof needs > 2/3 agreements, then the attack only needs to conquer > 1/3 of the shards (to make sure that less than 2/3 of the shards confirm the proof => the proof is invalid).

Attacking a shard needs ⅔ of its committee members to commit a faulty block. However, this block’s header will not be added to beacon chain or any other shards if ⅔ of beacon or other shards don’t agree. ⅓ committee size is able to stop producing a block, but it’s not able to commit a block.

You only mentioned the probability of compromising shards, what about the beacon chain? It’s much easier to attack this single committee, am I wrong?

An attacker needs ⅔ committee size to compromise a shard/beacon. However, what they could do is suspend tx from confirmation, the faulty tx could be committed in a single shard block, without the approval of beacon then the faulty committee could not produce the next block (because they need beacon block’s header in every shard block), i.e the faulty block could not get finality (check out the Multiview-PBFT).

8 Likes

Oh, this is clear to me.

This makes sense.

As far as I understand, the beacon chain is way more powerful than shard chains. It can assign which committee members to which shards. So, if an attacker compromises the beacon chain, he can then manipulate everything on the network. Is that true or did I misunderstand somehow?

2 Likes

As far as I understand, the beacon chain is way more powerful than shard chains. It can assign which committee members to which shards. So, if an attacker compromises the beacon chain, he can then manipulate everything on the network. Is that true or did I misunderstand somehow?

Not really, beacon takes responsibility for assigning shards’ committee only, it does not respond for confirming tx. Since all shards know the candidate list, and all shards could verify the random number used in the committee selection for each shard. If the beacon’s committee manipulates a shard’s committee, ⅔ of all shards could vote to change the byzantine beacon’s committee.

5 Likes

If the shards themselves can assign their committees using the random number (which is publicly accessible), why do we need the beacon chain to do that for them anyway?

1 Like

Basically, only beacon chain stores the committees for all shards/beacon on chain, however shards’ validators could verify whether beacon respects the committee assignment protocol or not.

3 Likes

Still a bit confused. If in case the beacon chain is down, are the shard chains able to vote for their committees?

In case the beacon chain is down, the next beacon committee will be selected by the protocol. Shards’ validators could verify the correctness of the protocol.

4 Likes

I’d like to use this place to express my appreciation for the knowledge of our devs, and the level of interest some users have for the technical side of how things work in the Incognito environment.

In general, don’t hesitate to ask, but also, keep an open mind and wait for an answer. Just because something is not clear at first glance doesn’t mean it is faulty, scammy, or wrong.

6 Likes

Hmm, not really agree. For me, explaining things should be as clear as doing the math. If you infer something (say, B) from A, then make sure that A, B are directly linkable. In this case

if 2/3 of the shards agree with the proof then the compromised committee will be penalized => an attacker only needs to compromise > 1/3 of the shards to make sure the proof is invalid, and thus he will not be penalized. So my question is valid.

The analysis in this table

is for this explanation

not this one

2 Likes

We get a lot of people who assume things work the same way they do on other chains, assume Incognito is based on Ethereum chain instead of running on its own, developed from scratch, chain and so on. Without doing some reading, they attack the system from being wrong, faulty, or a scam.

I was referring to that, and still stand by it. An “in general”, not “personal” observation.

2 Likes

Am I included in your “a lot of people”?
I want to know more about the system, how it works, which techniques they use to enhance privacy.

I did read the whitepaper, looked through the forum. And I think that all of my questions are valid.

It’s only you, who is the attacker here. You keep saying about trust, trust and trust. If trust is what people have to do, they will not need blockchain anyway. If you feel uncomfortable with my comments, just leave them there. They’re none of your business.

2 Likes

if 2/3 of the shards agree with the proof then the compromised committee will be penalized => an attacker only needs to compromise > 1/3 of the shards to make sure the proof is invalid, and thus he will not be penalized. So my question is valid.

The chain won’t get enough votes to penalize the compromised shard’s committee right away. However the proper validators with proof of faulty or full validation nodes could not append those invalid blocks in their chain, and healthy shards will not be able to accept invalid cross-shard tx. The chain would be blocked until the epoch in which >⅔ shards are healthy.

1 Like

You are taking things way too personal. “you/they”, means “you/they” in general.

1 Like