Sharding for Scalability: A Comprehensive Comparison of RapidChain and Harmony

A comparative analysis of the RapidChain paper and Harmony’s current status, along with future plans.

RapidChain is a theoretical sharded blockchain proposed by Zamani et. al [1] in 2018. Some of Harmony’s protocol is based on RapidChain and this article aims to compare the two.

Message Complexity

Gossip

RapidChain builds on the information dispersal algorithm (IDA) to perform gossiping of large messages across the network, whereas Harmony’s whitepaper refers to the usage of RaptorQ fountain code to encode a message for broadcasting.

RapidChain introduces the IDA-Gossip protocol for broadcasting large messages (blocks and transactions) across the network. A message M is divided into equal chunks of size (1-)kwhere k is the number of chunks and is the fraction of malicious neighbors. An erasure coding scheme, such as Reed-Solomon, is applied to the chunks to obtain the additional chunk to have M1, M2, M3, ...., Mk parts. These parts, along with their Merkle proofs, are broadcasted to the rest of the network.

A simplified example of obtaining the additional chunk can be understood as follows. Given a polynomial f(x) of degree n, you need n+1 values of x and f(x) to obtain the coefficients for each degree of x. Using a polynomial of degree 1, f(x)=mx+c, the values of m and c can be obtained if two values of x and corresponding f(x) are known. If an additional combination (“chunk”) of (x, f(x)) is added, any two (out of three) pairs of these values can be used to determine m and c.

Currently, Harmony does not implement erasure coding, but instead proposes using the RaptorQ fountain code. Compared to Reed-Solomon, RaptorQ encodes a message into a (potentially) limitless fountain of symbols using a subset of which the message can be recovered with non-zero probability. The implementation of this is not planned at the moment.

Sparsification

RapidChain recommends avoidance of broadcasting repeated information by filtering chunks which are likely to contain repeated information. Since the Harmony whitepaper does not recommend usage of Merkle trees for broadcasting, no such repeated data can be avoided. 

When broadcasting a chunk hash, its Merkle hash and Merkle Proof, it is observed that the hashes near the root of the Merkle tree are sent to almost all of the nodes potentially multiple times. RapidChain proposes “sparsifying” this broadcasting process such that each digest is only sent to (1-)d of a node’s neighbors, where is the fraction of malicious nodes and d is the number of neighbors. Using this method, a node may not immediately receive all of the digests needed to validate a message, but if at least one honest node receives (and broadcasts) the intermediate digest, validation can proceed.

Harmony’s whitepaper [2] or implementation make no references to sparsification or similar approaches since a Merkle tree is not broadcasted.

Consensus

For each transaction that is broadcasted to the network, RapidChain allows a committee belonging to any shard to receive it. This adds an additional overhead of O(m log n ), where m is the size of the committee and n is that of the transaction. Harmony, on the other hand, does not allow this to occur but requires that each transaction be sent to its origin shard.

Secondly, each transaction that happens to be a cross-shard transaction has its UTXOs (Unspent Transaction Output) validated by members of other committees which adds O(m2/b) complexity where b is the block size on which this validation is amortized. In the case of Harmony, each transaction receipt is simply broadcasted to the corresponding shard’s committee for a total of O(m). The destination shard simply validates this receipt and adds the balance to the destination account.

Communication Rounds

RapidChain, due to the synchronous nature of its consensus protocol, has O(N2) complexity whereas Harmony reduces this to O(N) through signature aggregation.

For each block that is proposed, RapidChain runs four synchronous rounds. The propose round involves the leader gossiping the header, which is broadcasted to other nodes with an echo tag in the second round. The third round is a validation round and the fourth round is the acceptance round which involves validators accepting (and then broadcasting) the header. Each header, therefore, is broadcasted first by the leader, the validator (in the form of votes), and then again by the validator (in the form of accept). In other words, this consensus algorithm has O(N2)complexity.

As an improvement to this protocol, Harmony uses BLS signatures which can be aggregated by the leader in an O(1) manner upon receipt. It is called Fast Byzantine Fault Tolerance (FBFT). Consequently, each validator receives just one multi-signature and not O(N) signatures. It reduces the communication complexity from O(N2) to O(N).

Security

Sybil attack prevention

Harmony requires PoS (which requires skin in the game, or staked coins) whereas RapidChain asks nodes who want to join or stay in the network to solve a PoW puzzle. Any new node that wishes to join the RapidChain system can request the randomness of the current epoch as a fresh PoW puzzle. The nodes that solve the puzzle send a transaction, with the solution and the public key, to the primary committee which marks such nodes as active if the solution is received before the end of the current epoch.

Random number generation

RapidChain and Harmony use different algorithms to generate randomness. The former uses verifiable secret sharing, which is an aggregation of multiple secrets / random numbers (similar to a commit reveal process). The latter uses a verifiable random function, which is a public-key pseudorandom function that provides proof that its outputs were calculated correctly.

RapidChain proposes using verifiable secret sharing (VSS) to generate randomness. It uses the combined secret shares as the resulting randomness. However, malicious nodes can broadcast inconsistent shares to different nodes making it biasable. On the other hand, Harmony proposes using a verifiable random function (VRF) and a verifiable delay function (VDF). The VRF is applied by each validator (with their private key as input) to generate a random number ri and corresponding proof pi and is sent to the leader. The leader combines all of these to generate a pre-randomness (and then applies BFT on this) which is included in the block. VDF is then applied to this which generates the random number - which is computationally difficult such that it can only be generated after k blocks. This delay is used to prevent the leader from selectively excluding certain ri from the XOR process to bias the result.

The current Harmony implementation of the VRF uses the previous block hash and the leader’s private key as input to output a random number proof (making it unbiasable since these two parameters are fixed and the result can be verified from the proof). It does not use the VDF at the moment, since the VRF is not obtained from biasable consensus on the validators’ random numbers and proofs. As opposed to the random number being generated each epoch, the implementation generates the random number at each block. As the core team works towards decentralization, the VRF implementation will be changed to match what is described in the whitepaper.

Shard failure

Both chains have similar security assumptions and use the same algorithm to prevent shard takeover. 

Harmony’s security assumption, with its 4 shards network, is that up to ¼ of staked tokens belong to malicious validators. To guarantee the security of a single shard, the amount of voting shares by a single validator must be below ⅓. Similarly, since RapidChain is a PoW blockchain it assumes that each validator has less than ⅓ of the computational power during each epoch. 

If Harmony shards by validators (i.e. assign one validator to one shard), it is certainly possible that, in the worst case, a set of colluding validators holding ¼ of the staked tokens can possess more than ⅓ of the voting shares in one shard. Note that, since the implementation of HIP-16, a single validator can occupy only 6.4% of the keys in one shard so this attack can only occur if multiple validators are involved. To prevent this collusion from taking place, Harmony shards by voting shares - that is, assign one voting share to one shard. Using the Rnd generated at the shart of each epoch the list of voting shares is permuted and divided into m buckets which is the number of shards.

However, this redistribution may result in validators changing shards frequently and loss of consensus during bootstrapping for the new shard. To prevent this, Harmony follows the Bounded Cuckoo Rule (same as RapidChain) which results in only a subset of validators changing shards at each epoch. It is proven that these reconfigured committees are balanced and honest.

Resharding is currently not implemented in the Harmony code but the team is making gradual progress towards this: first with the implementation of light clients followed by key rotation across shards.

Shard size

Since both chains are sharded and both have the same security assumptions, the shard size is equal for RapidChain and Harmony.

Shard size is set in such a manner that the probability of a shard failing is minimized. This is, of course, subject to resource constraints – a shard size cannot be infinite. In other words, shard size must be set at least high enough to keep the probability of a single validator controlling ⅓ the shard stake to a minimum.

The probability of a shard failure can be calculated as a hypergeometric distribution (random sampling without replacement).

Here N is the total number of shares, K=N/4 is the maximum number of malicious voting shares and k is the number of malicious voting shares in a shard, n = N / numShards is the number of voting shares in each shard.

When N is sufficiently large (4000), the cumulative distribution becomes binomial (random sampling with replacement) with p as the probability that each vote share is malicious (⅓). To keep the probability of a validator obtaining ⅓ shares in a shard low (~6.10-7) it can be calculated that n = 250.

References

[1] Zamani, M., Movanhedi, M., & Raykova, M. (2018). RapidChain: Scaling Blockchain via Full Sharding. International Association for Cryptologic Research.[2] Harmony Team (2021). Harmony Technical White Paper Version 2.0.