Hyperchain election process

I am creating a parallel thread to focus on the hardest part regarding Hyperchains: how a new leader is elected. Solving this is going to be fundamental for the whole process of development.

Delegates and Leaders

The role of the leader is a temporary one and closely resembles the BitcoinNG leader that produces microblocks for the duration of the generation. Once a new leader is elected, the old one is no more a leader. A subset of of all acounts in the child chain is eligable for being elected as the next leader. We call them delegates. Their child chain balances represent their stake in the child chain. In the initial version the delegates would be the topmost X accounts with a highest balances in the child chain. In later iterations child chain accounts could delegate their staking power to other accounts and increasing the staking power of the receiving account.

Delegates are provable only in the scope of the child chain. The parent chain has no knowledge for the child chain's mechanism for who is a delegate.

Commitments

Anyone can post a transaction on the parent chain. Delegates use that to provide a certain hash. This could be done using a Smart Contract deployed to the parent chain or by a simple spend transaction with a payload. This hash represents the delegate’s intention to become a leader and we call it a commitment.

Once a certain event happens on the parent chain - the child chain election mechanism takes over. Using all valid commitements and a source of entropy - a new child chain leader is electected deterministically and transparently by a provable function. The source of entropy could be anything.

Simple example: there are 4 commitements in the parent chain, 3 of which are by electable delegates. Once a keyblock is mined on the parent chain - all 3 are being fed to a function that also takes the parent chain's keyblock hash as a source of entropy. The result is who of the three delegates becomes a leader.

The leader must have incentive to continue from close-to-the-last block the previous leader had produced.

Important missing pieces of the Hyperchains’ puzzle:

  • what the commitment consists of - what do we hash? How do we validate it? It might include some relation with the child chain's chain as the delegate sees it. This could detect potential (network) splits between delegates and potential child chain forks. On the other hand - delegates should continue from where the last leader ended and not to discard all microblocks that were produced. If the commitement includes a hash of the previous blcok, though - delegates should post a new commitement as soon as they receive a new microblock in the child chain. We should probably find a compromise between the two or a neat solution.
  • leader incentives - delegates produce commitements in the parent chain but those come with fees included. We need a process to reimburse leaders in the child chain accordingly so they keep supporting the child chain in the first place.

This became a bit longer than expected but I wanted to make sure we are all on the same page. For the resulting discussion I summon @YaniUnchained @uwiger @bruteforce.chain @dincho.chain @Arthur @aleksandar.chain @hanssv.chain @philipp.chain @danielaivanova.chain @karol.chain @nikitafuchs.chain @michalzee and if I missed someone, please summon them as well.

8 Likes

Do we already have some slashing/proof of fraud ideas for punishing malicious behaviour of the delegates in the child chain ?

The result of todays’ call:

Commitments

Commitment consists of the hash of the last keyblock seen on the child chain. Once a generation is over, child chain nodes gather all commitments posted on the parent chain, they filter out the ones they consider invalid (ex. from non-eligable delegates, ones that commit to erroneous keyblock hash and etc.) and based on those - elect the next child chain leader. The newly elected leader provides a keyblock (TBD: does it contain the hash of its commitment on the parent chain?). Once participants receive the keyblock, they also get its hash and delegates can post to the parent chain their new commitments. It is worth noting that this would result in the child chain having the same pace of leader election the parent chain.

The reasoning behind publishing the keyblock’s hash opposed to the microblock is the following: it is supperior as it binds the leader to the same child chain generation but it does not specify a specific microblock. Thus commitments can be made in the child chain's generation start and those would be valid until it is over. One problem with PoW we had was that miner pools consider it to be expensive to restart their miners on every microblock they receive, thus microforking the last few microblocks of a generation. This would be improved with a PoS approach as there are no miners to restart. Also keeping the Bitcoin NG approach of splitting the fees reward 40/60, the new generation leader in the child chain receives more fees if one supports the previous generation’s micro blocks opposed to rejecting them in order to include them later on.

An interesting edge case would be if a leader does not produce a keyblock in the child chain. Then delegates shall wait for a while and start producing commitments with the oldest keyblock hash they’ve seen (basically republishing their previous commitments).

Important: With a bad connectivity between child chain nodes, this introduces a race condition - if a delegate does not receive the newly produced keyblock, it would republish a commitment with the previous keyblockhash and thus introducing the possibility of child chain.

Stakes

We want to keep knowledge for the child chain on the parent chain to the minimum. Hence we do not expect staking of tokens on the parent chain. There could be different approaches regarding staking in the child chain.

One would be locking tokens a the contract. This could be done in a time locked fashion. This will make staking much more visible and easier to compute. It poses a small threat, though: the dictator problem - if leaders conspire to actively reject transaction that introduce new delegates. Assumption is that this will lower the trust in the child chain itself and reduce its value overall.

Another approach would be simply using the current balances of accounts in the child chain. A rule would be that in order for those to be considered as a stake - they must be locked for a certain period of time. This would be a bit harder to compute and adds some computational overhead.

Both of those approaches solve elegantly:

  • Nothing-at-stake problem
  • Stake grinding
2 Likes

Isn’t the commitment superfluous? If they child-chain can filter out non-eligible delegates, why bother with the commitment…

Posting to the parent chain binds the child chain to it: the finality of commitments results in a finality of the leader election of the child chain. Simply put: this results in the PoS child chain to piggyback on the PoW parent chain: using the same level of network security without putting all the work required in PoW.

This is the real gamechanger.

I suggest we take a particular look at the Ouroboros algorithm (Cardano), and see if we can adapt that.
That would basically mean that we define X number of generations as an epoch, let candidates claim an election based on a ‘random seed’ in the epoch election snapshot, and then include a proof in the keyblock.

Perhaps a sloppy description, but more detail can be found in the related work thread.

In this approach, the parent chain would provide time slots and randomness for the Ouroboros-style child chain.

2 Likes

What you need is a leader election function that piggyback on the parent chain and its PoW… If you can exclude delegates from the electable group on child-chain local data, then you could keep the group child-chain local as well?! Then just use the hash of the latest block from the parent-chain as seed for the LE-function?

It probably also makes sense to root the child-chain on the parent-chain by including its genesis block or something.

This will eliminate the commitments but we actually want them. They fix the issues stated above: namely nothing-at-stake-problem and stake grinding. As we introduce a commitment that comes with a fee, delegates are expected to behave well :slight_smile:

On the Cardano chain, the way to do this is via a “stake pool”, managed by some trusted node operator (see this guide). As far as I can tell, experiments on running this in a decentralized fashion are just getting started.

3 Likes

There is still a possibility of stake grinding, perhaps, unless we impose a restriction that it’s the first commitment inside a generation that counts, and subsequent commitments cannot be used to update the hash.

From the Ouroboros Praos paper:

So we shouldn’t allow delegates to stack the election by committing frequently to the parent chain.

1 Like

I don’t think there is a difference between the first or the last, just needs to be deterministic after the block gets mined. Just one.

1 Like

Yes, if we simply limit the commitement taken into account to just one - this kicks the stake grinding out of the window for good.

1 Like

I think I’ve identified an issue.

We have 5 delegates: Alice, Bob, Carol, Dave and Erik. Alice is the leader and she has to produce a (in the context of BitcoinNG) keyblock which hash then the new commitments will be based upon. Alice is malicious and produces not one but 3 different keyblocks with different hashes (1). Different delegates receive different keyblocks and start producing different commitments on the parent chain. This effectively splits the network.

Suggestion: issue arrises from the fact that the keyblock (hash) might not be deterministic so let’s make it deterministic. It might include a hash of the transaction in the parrent chain that includes the commitment. If there are a couple of transactions from the same delegate on the parent chain with the same commitment, then only the last one is being used. It could also include the blockhash being used a source of entropy. In the context of a BitcoinNG that would be the newly mined keyblock in the parent chain and in the case of traditional chain of blocks that would be the block that includes the transaction).

1 Like

So there is no gossip in this new chain? Otherwise the other delegates should quickly see that Alice is malicious and discard the whole generation?!

Also, why base your commitment on the last key-block, that is just begging for problems. You aren’t planning on having a commitment per delegate per generation I hope, that will not scale :wink:

Then there is a network split on top of that and Bob does not see the network as Carol does.

It doesn’t scale well yes, but currently that is the idea.

1 Like

Interesting… What happens if the parent chain is so busy (or just produces a very short generation) that no commitment makes it into a generation?

I guess this also limits a bit which chains can be used as the parent chain, Etherum will be too expensive (and too fast?), Bitcoin will also be borderline I guess…

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.

4 Likes

We get an empty generation, I guess. In the child chain the previous leader is still producing microblocks so we are safe. This is one of the perks the child chain using a BitcoinNG consesus: transaction flow is not interrupted. Then delegates decide it is time for a new election and they repost their commitments on the parent chain but this time in the newer parent chain generation.

Yes, in the case where the child chain uses BitcoinNG, this would be perfectly acceptable. If not, it may make sense to have runners-up.

2 Likes

My concern with runners up would be that we still need to prove in a non-disputable way that the first leader did not produce blocks in the child chain.

This by itself is an attack vector that we prefer to ignore saying that if delegates misbehave, they will get burnt as well.

1 Like