Reading the Ouroboros Praos paper, I am trying to identify potential issues that we should describe. Some improvements they made from the original algorithm were:
- Empty slots: some ‘election periods’ may pass without a new leader being elected. I assume the same thing could happen in our case, since for liveliness reasons, we want the delegate to actively claim the leadership position.
- Multiple leaders per slot
- Corruption, where an adversary can learn the identities of the slot leaders ahead of time and use that to corrupt the election.
My eyes glazed over when the paper got too deep into proofs, but I started thinking about what might be a simple election algoritm to start with.
So here’s one:
- An election starts with the production of a new key block on the parent chain
- Those who want to compete for leadership, commit a stake tx to some microblock in the generation. They of course can’t control which one.
- The next key block hash on the parent chain is used to elect a leader among the committers. The distribution is given by the stake amount of each committer, and the order in which the txs appear in the microblock sequence. Only the last commit tx for each delegate counts.
- All stake sizes are valid, but with a very small stake, your chance of winning is small.
This should be deterministic, and there is no way to predict the outcome unless you control the hash of the next key block. It would constrain the election rate to the key block rate of the parent chain.
A question would be what should happen if the winner doesn’t produce a key block. One might let the election produce an ordered set of candidates, where the no 2 waits until the first parent microblock in the new generation, and then produces a keyblock if one hasn’t yet arrived. There would be a possibility of a conflict, but the order of the candidates is fixed, and determines which block to use.