BABE and GRANDPA

[kwanCCC]

1.0 Abstract of PoS

In traditional PoS System, block production participation is dependent on token holdings as opposed to computational power.
Most project end up proposing some level of centralized operation. While the number of validator with full participation right has impact on the performance of consensus (ex. HoneyPBFT).

2.0 BABE

Actually BABE (Blind Assignment Blockchain Extension protocol) assigns block production using roughly the randomness cycle from Ouroboros Praos. But with two differences, one is called GRANDPA best chain selection and another is using a new Clock in distribution system instead of their own clock. In short BABE + GRANDPA == Hybrid Consensus

2.1 How did BABE work ?

There are sequential slots{s1, s2, s3, s4} which consist of a number of sequential block production and then blockchain group them into non-overlapping epoch{e1 = [s1, s2, s3, s4]}. At the beginning of an epoch, every party "rolls a die".They compute a hash with proof by VRF(It will be described later) and stop if it is blew threshold r which one is the hash of VRF values from the blocks in the epoch before last(N - 2).So by the way, the past randomness affects the current pendding randomness. The number of parties who had passed VRF Challenge would be zero, one or more than one sometimes.

• If Party_i and Party_j had passed challenge, they all have the right to broadcast a VRF block. The winner block is the one which had been accecpt by most of the paties firstly.At this point, it's a race full of luck under the same conditions.
• If there is no any paties had passed challenge, the block production running use a round-robin style validator selection algorithm in the background. It is called secondary block which has lower priority than the VRF block, so the secondary block would be ignore when a VRF block appeared in the same slot.

3.0 GRANDPA

GRANDPA(GHOST-based Recursive ANcestor Deriving Prefix Agreement) is the finality gadget.It run a protocol similar to other two-phase synchronousByzantine agreement algorithms. It works in a partially synchronous network as long as 2/3 of nodes are honest and cope with 1/5 Byzantine nodes.But it reach the agreement on chain rather than blocks. So where they would vote in the second phase on the exact value that over 2/3 of voters voted for in the first phase. Then GRANDPA search latest block on the first set of votes to find the longest common prefix that 2/3 of voters agree on and use that for second phase.Sometimes participants would not agree on the latest block but still agree on a long chain with earlier blocks.

• T: the network delay, V: prevote, C: precommit, r^' ≤ r, g(v): get latest block from v, B: latest block
• a voter v can start round r > 1 when round r-1 is completable and v has cast votes in all previous rounds where they are voters. Let t_r,v be the time v starts round r.
• At time t_r,v, if v is the primary of this round then they broadcast E_{r-1, v}(V_{r-1, v} ,C_{r-1, v})
• v waits until either it is at least time t_r,v+2T or round r is completable, then broadcast a prevote. They prevote for the head of longest containing E_{r-1, v}(V_{r-1, v} ,C_{r-1, v}) unless we received a block from primary and g(V_{r-1, v}) ≥ B > E_{r-1, v}(V_{r-1, v} ,C_{r-1, v}), in which case they use the best chain contains B instead.
• v wait until g(V_{r, v}) ≥ E(_{r-1, v}) and either it is at least time time t_r,v+4T or round r is completable, and then broadcast a precommit for g(V_{r, v})
• v sees a block B as finalised in round r if g(C_{r, v}) ≥ B

[keyvank]

@kwanCCC Maybe we can use https://github.com/filecoin-project/bls-signatures as the backend of our aggregated signatures (For GRANDPA).

[kwanCCC]

@keyvank , If we only keep one kind signature, the BLS is really a good choice. But I'm not sure there's a Elliptic Curve VRF which base on BLS. I just found schnorrkel in substrate which one implements Schnorr signature on Ristretto compressed Ed25519 points. There maybe multiple curves and each of them had different functions.

[kwanCCC]

@keyvank ,Oh I see what you mean. The validators in GRANDPA are usually signing the same thing. It make sense to optimize the protocol