Scaling Blockchain Privacy with Dynamic Sharding
Low throughput is a significant barrier to the widespread adoption of cryptocurrencies. Throughput, measured in transactions per second (TPS), reflects the network’s capacity to process and confirm transactions. For instance, Bitcoin can handle only 7–10 TPS [Croman et al., 2016; Li et al., 2018], while Visa processes up to 24,000 TPS [Visa, 2018].
Privacy-focused transactions, however, face even greater challenges due to the additional computational overhead required for proof generation and verification. These transactions also tend to be larger due to the inclusion of extra privacy-related data. Zcash, a privacy-focused Bitcoin fork, can process only 6 TPS due to its 2 MB block size, a 150-second target block interval, and average transaction sizes of 2000 bytes. Such constraints severely limit scalability.
Chameleon’s Solution: Sharding for Scalability
To address these throughput issues, the Chameleon Network implements sharding for privacy transactions, drawing inspiration from systems like Omniledger [Kokoris-Kogias et al., 2018], RapidChain [Zamani et al., 2018], and Zilliqa [Zilliqa, 2017]. Sharding allows for linear scalability, increasing throughput proportionally as more shards are added to the network.
The Chameleon Network is architected as a network of blockchains, consisting of:
- A Beacon Chain (acting as the “coordinator”)
- N Shard Chains (serving as the “workers”)
The shard chains operate in parallel, independently producing blocks at the same time. The beacon chain plays a crucial role in synchronizing these shard chains,
ensuring consistency and coordination across the network. The block production process is divided into equal epochs, with each epoch ensuring the synchronization of all shard chains. This design enables Chameleon to achieve high throughput while maintaining strong privacy guarantees for its transactions.
Shard Chains
Shards will be organized based on the last byte of sender addresses. Each shard will have its own committee, which will be randomly assigned by the beacon chain. This shard committee will be responsible for validating and confirming transactions within its shard.
Whenever a shard block is created, the beacon committee will verify the block’s validity and insert the valid block header into the beacon chain.
If the block is found to be invalid, the beacon chain will send proof to all other shards, prompting them to vote on slashing the misbehaving shard committee.
Beacon Chain
The responsibility of the beacon chain will be to verify shard blocks and coordinate shard chains, acting as the global state of the entire network.
- The beacon chain will verify the validity of shard blocks.
- It will confirm cross-shard information. Each shard block header will include cross-shard information, indicating which shard this block has interacted with. This will also include the height of each shard chain, which will be part of the block body.
- The beacon chain will manage the candidate and validator list. Whenever a user stakes CHML to become a validator, this action will be recorded in the block header.
- The beacon chain will shuffle committees. When a new random number is generated, it will be recorded in the beacon block header.
- The beacon block will store the Merkle root of the candidate list and the validator list, both for the beacon chain and the shard chains.
Cross shard transaction
For cross-shard transactions, the sender shard will generate a receipt detailing all transactions directed to the receiver shard and will forward this receipt to the receiver shard. A summary of the cross-shard transactions will also be sent to the beacon chain. To prevent double-spending, the UTXOs in the sender shard will be locked. The receiver shard will validate the receipt and will wait for confirmation of cross-shard information from the beacon chain before marking the corresponding UTXOs as spendable.
Dynamic Committee Size
At the start of an epoch:
- Substitute List at 100-400%: Committee size remains the same, but 10% of members are replaced in a round-robin manner.
- Substitute List > 400%: Committee size increases by 15% (adjusted for previously slashed members).
- Substitute List < 100%: Committee size decreases by 10%.
Dynamic Sharding
The Chameleon chain will initially be 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 the transaction.
Each shard will have a maximum (M) of committee members. When the substitute list of all shards exceeds 5M, the chain will double the number of shards. In this case, each shard will be split into two new 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.
Example Scenario:
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.
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 of the Chameleon architecture.
The code is going to be 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.
- Beacon: Beacon is also a subchain. A beacon’s job is to coordinate the shards and maintain the global state of the network.
- Synker: Synker ensures the node stays up to date among its peers and broadcasts the node status to its peers.
- Mempool: Mempool (memory pool) is a collection of transactions and blocks that are verified but not yet confirmed.
- Wallet: Software that will hold all your Chameleon keys. It will be used to send and receive Chameleon tokens.
- Database: Chameleon will use LevelDB to store block data.