Scaling Blockchain Privacy with 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.
Shards are organized by the last byte of sender addresses. Each shard has its own committee, randomly assigned by the beacon chain at the beginning of every epoch. A shard committee validates and prevents double-spending locally within the shard.
Every time a shard block is created, it includes a Shard-to-Beacon block that contains block header and controls messages (if any) and sends it to the beacon committee.
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 2. Shard Chains
The responsibility of the beacon chain is to coordinate shard chains. It is the global state of the entire network.
- Beacon chain confirms the height of each shard chain based on the Shard-to-Beacon block data. The validators of the beacon chain reach consensus on the heights of each shard chain, which is then confirmed on the beacon chain.
- Beacon chain confirms cross-shard information. Each shard-to-beacon 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 also is 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.
The implementation is mainly in the Blockchain 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.
- 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 a 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.
Next Topic: Consensus: A Combination of PoS, pBFT, and BLS
[Croman et al., 2016] Croman, K., Decker, C., Eyal, I., Gencer, A. E., Juels, A., Kosba, A., Miller, A., Saxena, P., Shi, E., Sirer, E. G., et al. (2016). On scaling decentralized blockchains. In International conference on financial cryptography and data security, pages 106-125. Springer.
[Li et al., 2018] Li, C., Li, P., Zhou, D., Xu, W., Long, F., and Yao, A. (2018). Scaling Nakamoto consensus to thousands of transactions per second. arXiv preprint arXiv: 1805.03870.
[Kokoris-Kogias et al., 2018] Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., and Ford, B. (2018). Omniledger: A secure, scale-out, decentralized ledger via sharding. In 2018 IEEE Symposium on Security and Privacy (SP), pages 583-598. IEEE.
[Zamani et al., 2018] Zamani, M., Movahedi, M., and Raykova, M. (2018). Rapidchain: A fast blockchain protocol via full sharding. IACR Cryptology ePrint Archive, 2018:460.
[Zilliqa, 2017] Zilliqa, T. (2017). The Zilliqa technical whitepaper. URL: https://docs.zilliqa.com/whitepaper.pdf.