# ¶ Deterministic Sortition

This Deterministic Sortition procedure is used in the Succint Attestation consensus to select the block generator and the committee members. In particular, it is used in the Reduction and Agreement phases.

The deterministic procedure requires the set of active stakes $\mathbb{S}\mathbb\left\{S\right\}$, ordered in ascending order from oldest to newest, the latest global seed ${\sigma }^{s}\sigma^s$, current consensus round ${\kappa }^{r}\kappa^r$, and current consensus step ${\kappa }^{s}\kappa^s$.

The set of active stakes $\mathbb{S}\mathbb\left\{S\right\}$ consists of tuples $\left(v,pk\right)\left(v,pk\right)$, where $vv$ is the amount staked and $pkpk$ is the BLS public key corresponding to the stake.

## ¶ Procedure

During each consensus step requiring deterministic sortition, a node is required to map the contents of the set of active stakes following the procedure outlined in the example below:

Given $\mathbb{S}=\left(1000,p{k}_{1}\right),\left(2000,p{k}_{2}\right),\left(500,p{k}_{3}\right)\mathbb\left\{S\right\} = \left\{\left(1000,pk_1\right),\left(2000,pk_2\right),\left(500,pk_3\right)\right\}$, the stake mapping set $\mathbb{M}\mathbb\left\{M\right\}$ will be $\left(1000,3000,3500\right)\left(1000,3000,3500\right)$.

Given the counter $cc$ (instantiated at 1), the committee size $pp$, and the total amount staked $ss$, the extraction proceeds in following steps while $c\le pc\le p$ :

1. Compute $n←H\left({\sigma }^{s}\mid \mid {\kappa }^{r}\mid \mid {\kappa }^{s}\mid \mid c\right)n ← H\left(\sigma ^s\mid \mid \kappa ^r\mid \mid \kappa ^s\mid \mid c\right)$
2. Compute $d←n\phantom{\rule{0ex}{0ex}}\phantom{\rule{0.6666666666666666em}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}sd ← n \mod s$
3. Iterate through $\mathbb{M}\mathbb\left\{M\right\}$ until the value in the set is smaller than $dd$
4. Find the corresponding public key to the matching value in the set and append the public key to the committee set \mathbb
5. Subtract 1 from the value extracted and rebalance $\mathbb{M}\mathbb\left\{M\right\}$ accordingly
6. Iterate $cc$ Note: the public key can be extracted multiple times per committee.