Skip to main content


Authors: Jeff Burdges, Fatemeh Shirazi, Alistair Stewart, Sergey Vasilyev

BADASS BABE is a constant-time block production protocol. It intends to ensure that there is exactly one block produced with constant-time intervals rather than multiple or none. It extends on BABE to address this shortcoming of BABE. While Jeff's Write-up describes the whole design space of constant-time block production, here we describe a practical instantiation of the protocol using zk-SNARKs to construct a ring-VRF.

Layman overview

We want to run a lottery to distribute the block production slots in an epoch, to fix the order validators produce blocks by the beginning of an epoch. Each validator signs the same on-chain randomness (VRF input) and publishes this signature (VRF output=[value, proof]). This value is their lottery ticket, that can be validated against their public key. The problem with this approach is that the lottery-winners are publicly known in advance and risk becoming targets of attacks. We aim to keep the block production order anonymous. The assignment of the validators to the slots should be fixed for the whole epoch, but noone besides the assigned validator should know whose a slot is. However, we can't validate the tickets prior the lottery using their public keys as it would deanonymize the validators. If tickets were not validated prior to the lottery then instead we can validate them after the lottery by an honest validator claiming their slots when producing blocks.

However, the problem is that anyone can submit fake tickets, and though they won't be able to produce a block, slots would be preassigned to them. Effectively, it results in empty slots, which defeats the goal of the protocol. To address this problem, we need a privacy-preserving way of validating a ticket. So an honest validator when submitting their ticket accompanies it with a SNARK of the statement: "Here's my VRF output that has been generated using the given VRF input and my secret key. I'm not telling you my keys, but my public key is among those of the nominated validators", that is validated before the lottery.

Now we have a way of making the ticket itself anonymous, we need a way to anonymously publish it to the chain. All ways of doing this with full anonymity are expensive. Fortunately, one of the simplest schemes is good enough for our purposes: a validator just sends each of their tickets to a random validator who later puts it on-chain as a transaction.


In an epoch eme_m we use BABE randomness rmr_m for the epoch as ring VRF inputs to produce a number of outputs and publish them on-chain. After they get finalized we sort them and their order defines the order of block production for the epoch em+2e_{m+2}.


VV - the set of nominated validators ss - number of slots per epoch, for an hour-long epoch with 6 second slots s=600s=600 xx - redundancy factor, for an epoch of ss slots we want to have xsxs tickets in expectation for block production. We set x=2x=2. aa - attempts number of tickets generated per validator in epoch LL - a bound on a number of tickets that can be gossiped, used for DoS resistance


In addition to their regular keys, we introduce for each validator a keypair on a SNARK-friendly curve Jubjub. We must ensure that the keys are generated before the randomness for an epoch they are used in is determined.

Given the security parameter λ\lambda and some randomness rr generate a key pair KeyGenRVRF:λ,rsk,pk\texttt{KeyGen}_{RVRF}:\lambda,r\mapsto sk, pk

As an optimization we introduce an aggregate public key apkapk (called a commitment in Jeff's writeup) for the whole set of validators, that is basically a Merkle root built upon the list of individual public keys. In conjuction to that we use the copath askvask_v to identify a public key in the tree as a private input to a SNARK. AggregateRVRF:v,{pkv}vVapk,askv\texttt{Aggregate}_{RVRF}: v, \{pk_v\}_{v\in V}\mapsto apk, ask_v


Here we describe the regular operation of the protocol starting from a new set of validators being nominated. Bootstrapping the protocol from the genesis or soft-forking Kusama is not described here.

1) Setup

Once per era, as a new set of validators VV gets nominated or some other parameter changes, we reinitialize the protocol with new values for the threshold TT and the aggregated public key apkapk.

Each validator vVv \in V

  1. Calculates the threshold T=xsaVT = \frac{xs}{a\mid V\mid} that prevents the adversary to predict how many more blocks a block producer is going to produce.
  2. Computes the aggregated public key and copath of vvs public key
    apk,spkv=AggregateRVRF(v,{pkv}vV)apk, spk_v = \texttt{Aggregate}_{RVRF}(v, \{pk_v\}_{v\in V})
  3. Obtains the SNARK CRS and checks for subversion if it has changed or vv hasn't done it earlier.

2) VRF generation Phase

We aim to have at least ss VRF outputs (tickets) published on-chain (we can't really guarantee that, but the expected value will be xSxS).


At the epoch eme_m we use the randomness rmr_m as provided by BABE, namely

rm=H(rm1,m,ρ)r_m=H(r_{m-1}, m, \rho)

We use rmr_m to create inputs to the ring-VRF, and the corresponding tickets will be consumed in em+2e_{m+2}.

It's critical that ρ\rho is still the concatenation of regular BABE VRF outputs. It follows that we run regular VRFs and ring VRFs in parallel. This is because ring VRF outputs will be revealed in epoch eme_m and hence if we use ring VRF outputs for randomness rm+1r_{m+1} would be revealed too early. Thus we use VRFs that are unrevealed until the corresponding blocks are produced.

If we have a VDF, then all this would need to be determined an epoch prior i.e.

rm=VDF(H(rm2,m,ρ))r_m=VDF(H(r_{m-2}, m, \rho))

with ρ\rho being the concatenation of BABE VRFs from em2e_{m-2}. The VDF would be run at the start of em1e_{m-1} so that the output would be on-chain before eme_{m} starts.

VRF production

Each validator vVv \in V

  1. Given the randomness rmr_{m}, computes a bunch of aa VRF outputs for the inputs inm,i=(rm,i)in_{m,i}=(r_m, i), i=1,,ai = 1,\ldots,a:
outm,v,i=ComputeRVRF(skv,inm,i)out_{m,v,i}=\texttt{Compute}_{RVRF}(sk_v, in_{m, i})
  1. Selects the "winning" outputs that are below the threshold TT: bake(outm,v,i)<T\texttt{bake}(out_{m,v,i}) < T where bake()\texttt{bake()} is a function that effectively maps VRF outputs to the interval [0,1][0,1]. We call the set of ii corresponding to winning outputs IwinI_{win}.

  2. Uses its copath askvask_v generate proofs for the selected outputs iIwini \in I_{win},

    πm,v,i=ProveRVRF(skv,spkv,inm,i)\pi_{m,v,i} = \texttt{Prove}_{RVRF}(sk_v, spk_v, in_{m,i} )

    where ProveRVRF(skv,spkv,inm,j)\texttt{Prove}_{RVRF}(sk_v, spk_v, in_{m,j} ) consists of the SNARK and its public inputs cpk,icpk,i.

As the result of this phase every validator obtains a number, possibly 0, of winning tickets together with proofs of their validity (j,outm,v,j,πm,v,j)(j, out_{m, v,j}, \pi_{m,v,j}) that need to be published on-chain.

3) Publishing Phase

We want block producers for at least a large fraction of slots unknown in advance. Thus well-behaved validators should keep their tickets private. To this end validators dont publish their winning VRF outputs themselves immediately, but instead relay them to another randomly selected validator (proxy) who then publishes it.

Concretely, vv chooses another validator vv', based on the output outm,v,iout_{m,v,i} for iIwini \in I_{win}. To this end, the validator takes k=outm,v,imodVk=out_{m,v,i} \textrm{mod} |V| and sends its winning ticket to the kkth validator in a fixed ordering. Then the validator signs the message: (v,l,encv(outm,v,i,πm,v,i))(v, l, enc_v'(out_{m,v,i}, \pi_{m,v,i})) where endvend_{v'} refers to encrypted to a public key of vv'. We number the winning outputs using ll ranging from 00 up to L1L-1 and gossip them. If we have more than LL outputs below TT, we gossip only the lowest LL. This limitation is so that it is impossible for a validator to spam the network.

Once a valiaotr receives a messages it checks whether it has received a message with the same vv and ll and if so it discards the new message. Otherwise, the validator forwards (gossips) the message and decrypts it to find out whether the validator is the intended proxy. Validators gossip messages that are intended for them further to be secure against traffic correlation.

Once a validator decrypts a message with their private key they verify that they were the correct proxy, i.e. that outm,v,imodVout_{m,v,i} \textrm{mod} |V| corresponds to them. If so, then at some fixed block number, they send a transaction including (outm,v,i,πm,v,i))(out_{m,v,i}, \pi_{m,v,i})) for inclusion on-chain. Note that the validator might have been proxy for a number of tickets, in that case, it sends a number of transaction on designated block number.

If a validators vv ticket is not included on-chain before some later block number, either because the proxy is misbehaving or because they havent sent the winning ticket to any proxies, then vv publishes the transaction (outm,v,i,πm,v,i)(out_{m,v,i}, \pi_{m,v,i}) themselves. The reason why a validator would not send a winning ticket to any proxy is that it has more than LL winning tickets.

4) Verification

A transaction of this sort is valid for inclusion in a block if it can be verified as follows.

To verify the published transactions (outm,v,i,πm,v,i)(out_{m, v,i}, \pi_{m,v,i}), we need to verify the SNARK. For this we need

  • the corresponding input inm,iin_{m,i}, which we can calculate from ii and rmr_m,
  • the published output outm,v,iout_{m,v,i}
  • the aggregate public key apkapk.

All of these are the public inputs in SNARK verification:

Verify(πm,v,i,apk,outm,v,i,inm,i)Verify(\pi_{m,v,i}, apk, out_{m,v,i}, in_{m,i})

5) Sorting

In the epoch em+2e_{m+2} we have the list {outm,k}k=1K\{out_{m,k}\}_{k=1}^{K} of KK verified VRF outputs generated during the epoch eme_m which are finalized on-chain. For each of these outputs, we combine the ouput with the randomness rr', with either r=rm+1r'=r_{m+1} if we do not have a VDF or r=rm+2r'=r_{m+2} if we do have a VDF. Then we compute outm,k=H(outm,kr)out'_{m,k}=H(out_{m,k} || r').

To determine the block production order for the epoch em+2e_{m+2}, each validator sorts the list of outm,kout'_{m,k} in ascending order and drops the largest sKs-K values if any: outm,1,,outm,lout'_{m,1},\ldots, out'_{m,l}, where lsl\leq s and outm,poutm,qout'_{m,p}\leq out'_{m,q} for 1p<ql1\leq p<q\leq l.

The tickets are assigned to slots in an "Outside-in" ordering as follows. If we number the outm,kout'_{m,k} from lowest to highest as outm,kout'_{m,k} from k=1k=1 to KK in increasing order, then the last slot is outm,1out'_{m,1}, the first slot is outm,2out'_{m,2}, the penultimate slot is outm,3out'_{m,3}, the second slot is outm,4out'_{m,4} etc.

Example of outsidein sorting: (1,2,3,4,5)->(2,4,5,3,1)

In the unlikely event that K<sK < s, there will be some unassigned slots in the middle of the epoch, and for these we use AuRa.

Concretely, for the algorithm for assiging lots that uses outside-in sorting, we take lists of even and odd numbered elements, reverse the list of odd elements, then concatenate the list of even elements, the list of aura slots and the reversed list of odd elements.

6) Claiming the slots

To produce a block in the assigned slot, the validator needs to include the ticket, a VRF output outm,v,iout_{m,v,i}, that corresponds to the slot together with a non-anonymous proof that this is the output of their VRF.

Thus we introduce RevealRVRF:skv,outτ\texttt{Reveal}_{RVRF}: sk_v, out\mapsto \tau and the corresponding CheckRVRF:τ,outtrue/false\texttt{Check}_{RVRF}: \tau, out\mapsto true/false calls that are basically Schnorr knowledge of exponent proofs (PoKE). When validating the block nodes verify these proofs.

The validator must also include a never before seen VRF output, called the BABE VRF above. This may be done with the existing (non-jubjub) key on the same input (r_m || i).

Probabilities and parameters.

The first parameter we consider is xx. We need that there is a very small probability of their being less than ss winning tickets, even if up to 1/31/3 of validators are offline. The probability of a ticket winning is T=xs/aVT=xs/a|V|. Let nn be the number of validators who actually participate and so 2V/3nV2|V|/3 \leq n \leq |V|. These nn validators make aa attempts each for a total of anan attempts. Let XX be the nimber of winning tickets.

Then it's expectation has E[X]=Tan=xsn/VE[X] = Tan = xsn/|V|. If we set x=2x=2, this is 4s/3\geq 4s/3. In this case, Var[X]=anT(1T)anT=xsn/V=2sn/V2sVar[X] = anT(1-T) \leq anT = xsn/|V| = 2sn/|V| \leq 2s.

Using Bernstein's inequality:

Pr[X<s]Pr[X<E[X]s/3]exp((s/3)2(Var[X]+s/3))exp(s/(9(2+1/3)))exp(s/21)\begin{align*} \Pr[X < s] & \leq \Pr[X < E[X]-s/3] \\ & \leq exp(-\frac{(s/3)^2}{(Var[X]+s/3)}) \\ & \leq exp(-s/(9(2+1/3))) \\ & \leq exp(-s/21) \end{align*}

For s=600s=600, this gives under 410134 * 10^{-13}, which is certainly small enough. We only need the Aura fallback to deal with censorship. On the other hand, we couldn't make xx smaller than 3/23/2 and still have tolerance against validators going offline. So x=2x=2 is a sensible choice, and we should never need the Aura fallback.

The next parameter we should set is aa. The problem here is that if a validator vv gets aa winning tickets in an epoch, then when the adversary sees these, they now know that there will be no more blocks from vv.