Whitepaper 2.0

Introduction

Harmony:

Fully Scalable
Secure Sharding
Efficient and Fast Consensus
Adaptive-Thresholded PoS
Scalable Networking Infrastructure
Consistent Cross-Shard Transactions

‣

Consensus Mechanism

Determines how securely and quickly blockchain validators reach consensus on the next block

PBFT (Practical Byzantine Fault Tolerance) (https://mirror.xyz/imlearning.eth/0b-UwdYw1SmsLROdiCe2IOro3fXZKXLG7l8-HT4Egm0)

Prepare phase:

Leader broadcasts its proposal to all of the validators
Validators broadcast their votes to everyone else

Votes of each validator need to be counted by all other validators

Phase finished when $2f + 1$ consistent votes are seen

$f$ = number of malicious validators
$3f+1$ = total number of validators + leader

Commit phase:

Similar vote counting process
Consensus is reached when $2f+1$ consistent votes are seen

$O(n^2)$ due to the rebroadcasting → not scalable with hundreds of nodes

FBFT (Fast Byzantine Fault Tolerance)

Instead of rebroadcasting to ALL other validators, multi-sig signing process to collect validators’ votes in a $O(1)$ -sized multi-sig
Broadcasts it once collected
$O(N)$ because instead of receiving $O(N)$ signatures, each validator receives only one multi-sig

BLS (Boneh Lynn Chacham) multi-signature (Only require one round-trip of receiving the signatures)

Harmony’s FBFT:

Announce: The leader constructs the new block and broadcasts the header to all validators. Meanwhile, the leader broadcasts the content of the block w/ erasure coding.
Prepare (a): The validators check the validity of the block header, sign the block header with a BLS signature, and send the signature back to the leader.
Prepare (b): The leader waits for at least $2f+1$ valid signatures from validators (including the leader itself) and aggregates them into a BLS multi-sig. The the leader broadcasts the aggregated multi-sig along w/ a bitmap indicating which validators have signed.
Commit (a): The validators check that the multi-sig has at least $2f+1$ signers, verify the transactions in the block content from Step 1, sign the received message from Step 3, and send it back to the leader.
Commit (b): The leader waits for at least $2f+1$ valid signatures from Step 4, aggregates them together into a BLS multi-sig, and creates a bitmap logging all the signers. Finally, the leader commits the new block w/ all the multi-sig and bitmaps attached, and broadcasts the new block for all validators to commit.

Validators w/ more voting shares have more votes than others → NOT a one-signature-one vote

Instead of waiting for at least $2f+1$ signatures from validators, the leader waits for signatures from validators who collectively possess at least $2f+1$ voting shares

‣

Sharding

PoS based full sharding scheme that is: linearly scalable and provably secure

Beacon chain and multiple shard chains:

Beacon chain serves as the randomness beacon and identity register
Shard chains store separate blockchain states and process transactions concurrently

‣

Distributed Randomness Generation

Randomness-based sharding recognized as the most secure solution

Random number must have the following properties:

Unpredictable: No one should be able to predict the random number before it is generated
Unbiaseable: The process of generating the random number should not be biaseable by any participant
Verifiable: The validity of the generated number should be verifiable by any observer
Scalable: The algorithm of randomness generation should scale to a large number of participants

Scalable Randomness Generation w/ VRF and VDF

Harmony’s DRG protocol complexity is $O(N)$

Protocol:

A leader sends $init$ message with the hash of the last block $H(B_{n-1})$ to all validators.
For each validator $i$ , after receiving the $init$ message, a VRF is computed to create a random number $r_i$ and a proof $p_i: (r_i, p_i)=VRF(sk_i, H(B_{n-1}), v)$ , where $sk_i$ is the secrete key of each validator and $v$ is the current view number of consensus. Then, each validator sends back $(r_i, p_i)$ to the leader.
The leader waits until it receives at least $f+1$ valid random numbers and combines them with an $XOR$ operation to get the pre-image of the final randomness $pRnd$ .
The leaders runs BFT among all the validators to reach consensus on the $pRnd$ and commit it to block $B_n$ .
After $pRnd$ is committed, the leader starts computing the actual randomness $Rnd=VDR(pRnd, T)$ , where $T$ is the VDF difficulty and is set algorithmically such that the randomness can only be computed after $k$ blocks.
Once $Rnd$ is computed, the leader initiates a BFT among all validators to agree on the validity of $Rnd$ and finally commit the randomness into the blockchain.

Due to VDF, the leader won’t be able to know the actual randomness $Rnd$ before $pRnd$ is committed to the blockchain

By the time $Rnd$ is computed with the BDF, $pRnd$ is already committed in a previous block so the leader cannot manipulate it

Best a malicious leader can do is to either:

Blindly commit the randomness → Same as the honest behavior
Not commit $pRnd$ → Timeout mechanism will switch the leader and restart the protocol

‣

Epoch

An epoch is a predetermined time interval during which:

The sharding structure is fixed
Each shard continuously runs consensus with the same set of validators

At the beginning of the epoch, a random number will be generated using the DRG protocol and sharding structure will be determined by the randomness

Validators who want to validate transactions in epoch $e$ need to stake their tokens during $e-1$

Cutoff time for staking is before $pRng$ is committed into the chain

‣

Staking-based Sharding

Validator Registration

Participants have to stake a certain amount of tokens to be an eligible validator

Number of tokens will determine the number of voting shares assigned to the validator

Each voting share corresponds to one vote in the FBFT consensus

Sharding by Voting Shares

Amount of tokens for a voting share is algorithmically adjusted

At the beginning of each epoch, new validators’ voting shares will be randomly assigned to shards

The new validators join the shard where their voting shares get assigned

💡

Single validator can vote in multiple shards? Or are validators created proportional to the staked tokens?

The consensus in a shard is reached by validators who collectively possess at least $2f+1$ voting shares

To guarantee the security of a single shard, the amount of voting shares by malicious validators needs to be kept below $1/3$ of all voting shares in that shard

Assumption: Up to $1/4$ of all the staked tokens belong to malicious validators
if we shard by validators, given the assumption above, the single malicious validator will easily possess more than $1/3$ voting shares in that shard
The stakes at each shard is $m$ times less than the stakes of the whole network (for Harmony $m=4$ ) Large-Stake Attack

To prevent LSA, instead of sharding by validators, we shard by voting shares

After the $Rnd$ is revealed at the start of the current epoch, a random permutation (seeded with $Rnd$ ) on all the voting shares will divided evenly into $m$ buckets

The shard leader is determined as the validator who possess the first voting share in the bucket

Validators with larger stake have higher chance of being selected as the leader

Desirable because large stakers have more incentive to follow the protocol (slashing)
More likely to possess more powerful machines with fast and stable network

Adaptive-Threshold PoS

Harmony’s adaptive threshold PoS guarantees the security measure by adaptively adjusting the price small enough that malicious stakers can’t concentrate their voting power in a single shard

P_{vote} = \frac{{TS_{e-1}}}{NumShard*\lambda}

$\lambda$ is a security parameter and $TS_{e-1}$ is the total amount of tokens staked during epoch $e-1$

When $\lambda>600$ , the chance of a single shard having more than $1/3$ malicious voting shares is negligible

Given the defintion of $P_{vote}$ , the total number of voting shares will be $N=\frac{TS_{e-1}}{P_{vote}}=NumShard * \lambda$
The probability distribution of the number of malicious voting shares in each shard can be modeled as:

P(X=k)=\frac{\binom{K}{n}\binom{N-K}{n-k}}{\binom{N}{n}}

$N$ is the total number of voting shares
$K=\frac{N}{4}$ is the max number of malicious voting shares
$n=\frac{N}{NumShard}$ is the number of voting shares in each shard
$k$ is the number of malicious voting shares in a shard

TL;DR: When n is large enough, the probability that a shard contains more than $1/3$ tokens held by malicious entities is negligible

When $n=600$ , the probability a shard contains less than $1/3$ malicious voting shares is $P(X\leq200)=0.999997$ , shard failure (i.e. consensus cannot be reached) rate of “once in around 1000 years”

‣

Resharding

Harmony assumes the slowly adaptive corruption model

Slowly adaptive: where attackers can corrupt a subset of nodes over time during the epoch

Cuckoo-rule based resharding mechanism

After the end of an epoch, the validators who withdrew their stake will be evicted from the network
New validators who staked during epoch, get new voting shares
Voting shares will be randomly assigned to the shards that have more than the median of the total voting shares
Constant number of the voting shares from all shards will be randomly re-distributed to the other half of the shards who have less than the median of total voting shares

This resharding scheme keep the voting shares balanced while fulfilling the security req.

‣

Fast State Sync

Traditional way of downloading the blockchain history and reconstructing the current state is too slow for resharding to be possible

Downloading the current state within the time window of an epoch is feasible compared to the whole history

Verification required to ensure the current state of download is valid

New node downloads historical block headers and validates the headers by checking their signatures
Signature verification is costly thus the first block of each will include an additional hash pointer to the first block of the last epoch
New node can jump across the blocks within an epoch when tracing hash pointers to genesis block

‣

Shard Chain and Beacon Chain

‣

Shard Chain

Shard chain is a blockchain that processes and validates its own transactions and stores its own state

Cross-shard Communication

Breaks the barrier between shards and extends the utility of a single shard beyond itself

Shard-driven: Messages between shards are directly sent by the nodes in the shard w/out external help

Harmony adapts shard-drive for its simplicity and the absence of burden on clients

‣

Beacon Chain

In effect, the beacon chain is also a shard

Besides processing transactions, the beacon chain is in charge of two additional key functionalities:

Generating the random number
Accepting stakes, which means that the beacon chain is the chain where stakers deposit their tokens to become validators

Hash Link from Shard Chain

Beacon chain helps strengthen the security and consistency of the shard chains’ states by including the block header from each shard chain

After a new block is committed to a shard chain, its block header will be sent to the beacon chain

Beacon chain checks the validity of the block header by:

The hash of its previous block, which must have already been committed in the beacon chain
The signers of the block’s multi-sig, which must be the correct validators for that shard

Committed block headers at the beacon chain broadcasted to the whole network

Each shard will keep a chain of valid block headers for all other shards, used to check the validity of transactions from other shards

Adding the shard chains’ block headers into beacon chains serves two purposes:

Increases the difficulty of attacking a single shard Attackers have to corrupt both the shard chain and beacon chain
Reduce the network cost of broadcasting the block headers among shards $O(N^2)$ if each shard broadcast its headers separately $O(N)$ with the beacon chain as a central relay

‣

Blockchain State Sharding

Each shard chain contains its own account state and all the tokens in existence are spread among all the shard

An user account can have multiple balances at different shards

Can move balance between shards by issuing a cross-shard transaction

Smart contract account is limited to the specific shard where the contract was created

However, Dapps can instantiate multiple instances of the same smart contract in different shards and let each instance handle a subset of the incoming traffic

‣

Networking

‣

Incentive Model

‣

Consensus Rewards

After a successful commitment of a block, a protocol-defined number of new tokens will be rewarded to all validators who signed the block in proportion to their voting shares (similar logic for transaction fees)

‣

Stake Slashing

Certain amount of staked tokens will be slashed for any misbehaviors i.e. if a leader failed to finish the consensus process and triggered the leader change process, $P_{vote}$ staked tokens will be slashed

If validators are proven to sign a dishonest block, all of their stake under the same shard will be slashed

‣

Stake Withdrawal

‣

Fork

Chain split that occurs when changes are made to the blockchain’s protocol

Soft Fork

Software upgrade to bring new features or functionalities
Changes are backward-compatible with the pre-fork blocks
End result is a single blockchain

Hard Fork

New version is no longer backward-compatible with earlier blocks
Chain splits in two: the og and the new
Creates an entirely new cryptocurrency