Committees per epoch in DAL (and Tenderbake?)

For the P2P protocol, having a DAL committee changes at every level
could create performances issues due to connections and
disconnections. A way to overcome would be to draw the DAL committee
every n levels where n is a constant that remains to be defined. A
period of time of n blocks will be called an epoch in this
document.

Likely, we would like to have that the number of blocks in a
epoch divides the number of blocks in a cycle.

Moreover, in the current implementation, the DAL committee is
taken as a sub-committee of the Tenderbake's. This
enables that an attestation (also called endorsement for the moment)
can be used at the same time to attest the validity of blocks and the
availibility of data for the DAL.

If the DAL committee is changed at each epoch, while the Tenderbake
committee is changed at every level, it may be possible that an
attestor cannot attest the availibility of some data because he was
not selected by the Tenderbake committe IF we use a single operation
to attest at the same time the validity of blocks (Tenderbake
consensus) and the availability of the data.

This leads to a design choice with three following possible solutions:

• A) We split the attestation operation into a DAL attestation and a
  Tenderbake attestation

• B) We keep one attestation operation with the outcome described above

• C) We propose a similar change for the Tenderbake committee so that
  there is one Tenderbake committee per epoch

The generalisation where there is one epoch for the Tenderbake
committee and one epoch for the DAL committee does not sound very
interesting. Hence, in the following we make the assumption that in
solution C, the epoch is the same for both committees.

In the remaining part of this document, we list the advantages and
distavanges of each solution.

Solution A

In this solution, there is a DAL committee for each epoch, and we
have two attestation operations: one for Tenderbake, one for attesting
data availability

Pros:

• No need to modify Tenderbake and the selection of Tenderbake committees
• All the shards can be attested at every level

Cons:

• Approximately, we will double the number of signature checks per
  block (maybe this could be mitigated if an attestor appears in the
  two committees, but it is not obvious how)

Solution B

In this solution, there is a DAL committee for each epoch, and we
have only one attestation operation.

Pros:

• No need to modify Tenderbake and the selection of Tenderbake committees
• Keep the same number of check signatures

Cons:

• Some shards cannot be attested at every level. The consequences are:

  ​​​​​​ - Some slots may not be attested while data is actually
  ​​​​​​   available and fetched by the attestors
  
  ​​​​​​ - This could have an implication of the attack model of the
  ​​​​​​   DAL. While the current design makes the DAL resilient to 80%
  ​​​​​​   of malicious bakers, with such a change, this is less clear.
  

Solution C

In this solution, there is a DAL committee and a Tenderbake committee for each epoch.

Pros:

• Keep the same number of checked signatures
• All the shards can be attested at every level
• Some RPCs will be faster to compute like endorsing_rights or
  baking_rights because there are less rights to compute.
• Even though it is not a limiting factor, it requires less
  computations from the L1

Cons:

• We need to modify Tenderbake and the selection of Tenderbake
  committees

• We must settle the number of blocks in an epoch so that an endorser
  with one roll will get the same rewards

Consequences of introducing an epoch for Tenderbake

The benefits related to introducing an epoch

$>1$ for Tenderbake are quite obvious. However, this may have some consequences:

• In term of security, it does not change the fact that
  $\frac{1}{3}$ of the stake can censor any operation on the network.

However, it may change the endorsing rewards of delegates. The purpose of the next section is to describe the incidence on this.

Endorsement rewards per cycle

The endorsement rewards depends on some parameters. The computations are done with the values of those parameters on mainnet at the time of this document was written (so during the stabilisation period of M):

• s is the number of Tenderbake slots per level (7000)
• c is the number of blocks per cycle (8192)
• e is the number of blocks per epoch (1); we assume that c mod e = 0
• t is the required minimum participation of a delegate (2/3)

At cycle

$544$ the total active stake is around 700_000_000 tez. The minimal stake possible to bake is 6_000 tez. Hence, the proportion of the stake for such a baker is

$f=\frac{6000}{700000000}$.

We use this stake (proportion) because this is the most pessimistic case.

At any level, the probability that such a delegate has at least one slot is given by

$1-(1-f{)}^s$.

Hence, it means that for such a delegate, the probability to have at least one slot is

$\approx 5,82$%. (That's a least a slot approximatively every 17 levels.)

Another computation gives that in average, such a delegate gets

$492$ slots per cycle.

We also recall that a delegate gets its endorsing rewards in a cycle if at least

$t=\frac{2}{3}$ of its expected slots in that cycle are included in blocks.

Probability that a delegate does not get its rewards

We compute, for two values of the theshold t (the current one, 2/3, and a smaller one, 60%), and for two values of c (8192 as for mainnet, 16384 as in Mumbai), the expected frequency of a delegate with minimal stake not getting its rewards.

A value x in the table means the event is expected to occur once every x years. A * in the table means the value is greater than 1000 years.

We assume the delegate does not miss endorsements; we could increase t with 1%, which is the observed rate of missed slots per cycle on mainnet.

Case t = 0.67, c = 8192:

$s$ \ $e$	1	2	4	8	16	32
7000	*	*	210	3.3	0.29	0.08
9000	*	*	*	9.8	0.52	0.11
11000	*	*	*	28	0.92	0.15
14000	*	*	*	210	3.3	0.29

Case t = 0.67, c = 16384:

$s$ \ $e$	1	2	4	8	16	32
7000	*	*	*	210	3.3	0.29
9000	*	*	*	*	9.8	0.52
11000	*	*	*	*	28	0.92
14000	*	*	*	*	210	3.3

Case t = 0.60, c = 8192:

$s$ \ $e$	1	2	4	8	16	32
7000	*	*	*	25	0.83	0.13
9000	*	*	*	112	2.4	0.32
11000	*	*	*	843	7.0	0.42
14000	*	*	*	*	25	0.83

Case t = 0.60, c = 16384:

$s$ \ $e$	1	2	4	8	16	32
7000	*	*	*	*	25	0.83
9000	*	*	*	*	112	2.4
11000	*	*	*	*	843	7.0
14000	*	*	*	*	*	25

Mathematical details

We consider the number of slots a delegate receives during a cycle.

Let

$n:=\frac{sc}{e}$.
The probability of a delegate not receiving its rewards is then computed as

$$p:=\sum _{i=0}^{\lfloor tnf\rfloor }(\genfrac{}{}{0ex}{}{n}{ei})f^{ei}(1-f{)}^{n-ei}$$

The "frequency" (that is, a value in the tables) is then computed as

$\frac{1}{p\cdot \mathit{cycles}\mathit{\_}\mathit{per}\mathit{\_}\mathit{year}}$, where

$\mathit{cycles}\mathit{\_}\mathit{per}\mathit{\_}\mathit{year}$ is

$365\cdot 24\cdot 60\cdot 2/8192$.

Further remarks

Let

$X$ the corresponding random variable. The result of

$X$ is

$e$ times the number of successes in

$s\cdot \frac{c}{e}$ independent coin flips, so

$X/e$ is

$B(\frac{sc}{e},f)$ (i.e. binomially) distributed.

Note that

$E[X]$ does not depend on

$e$:

$\mu =f\cdot s\cdot e\cdot \frac{c}{e}=fsc$.

The variance

$Var(X)=escf(1-f)$. So, to recover the same variance, we'd need

$e$ times more slots! However, this is not that relevant, because the rewards do not depend on the variance, but only the expected value, as long as the threshold, which itself depends on the variance is reached.

The standard deviation for

$e=1$ is

$21.5$ slots per cycle and it increases by

$\sqrt{e}$ with

$e$.