Using a commit/contest method to scale validator set

[OliverNChalk]

Hello POA team,

I just wanted to air an idea I had in mind while talking with Marek from ethworks. To my knowledge, current validator sets for cross-chain bridges are fairly small due to the fact that transfer cost scales linearly with the amount of validators (due to each validator needing to vote on transfers).

In our discussions on how we could increase the size of this validator set without creating significant congestion or gas costs, an obvious solution was to use a commit / contest model.

The model is similar to other layer 2 solutions:

• You have a smaller subset of the validators (usually just 1) propose a transfer.
• If their proposal is valid, the dispute period will eventually expire and the token issuance will occur.
• If the proposal was invalid, any other validator will be able to initiate a dispute. Disputes will be resolved by majority quorum, utilizing the security of the full validator set.
• Missbehaving validators will be slashed and kicked out, while honest validators will be rewarded. There will also be a smaller penalty for incorrectly disputing valid transfers.

This model introduces some changes to the game-theory of cross-chain bridges and also increases the latency of transfers due to dispute periods. However, it should let the bridges significantly scale their validator set.

Interested in any feedback / thoughts.

[marekkirejczyk]

As @OliverNChalk mentioned we are considering scaling Bridge to tens or hundreds of validators (perhaps even more). The goal is increased security of the bridge.

I would add some implementation details to this proposal:

1. The current subset of validators is chosen by round-robin strategy or in the more advanced version in pseud-randomness. I would also consider bigger subsets (e.g. 3-5 validators).
2. The period needs to be fairly long (at least in minutes) so that there is enough time for propagation of transaction.
3. Dispute time is a trade-off between bridge latency and security (perhaps also measured in minutes)
4. Disputes, voting and staking as described. Honest validators rewarded needs to be relatively small in comparison to the slashed amount.

[akolotov]

Hi @OliverNChalk !

Nice to see your proposal. Thanks!

I would suggest to create an issues like this next time in the https://github.com/poanetwork/poa-bridge-contracts repo.

I have a few comments to your proposal, it will be great to continue discussion:

1. It could be a solution for the crosschain bridges where validators need to pay fees for transaction. In cases when the bridge validators are part of the chain infrastructure (like in xDai chain), they can send transactions with zero cost at least in one direction. Another direction still requires to pay fees, but only one validator is involved in the transfer. But even in this scenario his/her expenses could be covered by the bridge fees.

2. Is my understanding correct and the validator who proposed the transfer needs to send at the end of dispute period another transaction to confrim that no dispute appeared and tokens shoud be minted/unlocked? Sure, it could be done by a funds recipient but it not always possible. For example, if I transfer funds to a chain like xDai chain I could not send a withdrawal request since cannot pay for the transaction fee.

3. Latency in transfer transactions will include (if we consider the direction from the foreign chain to the home chain): finalization on the foreign network (e.g. 8 block for the Ethereum Mainnet means 2 minutes), inclusion of the validators transaction to the block on the Home side, time to get disputes and inclusion of the confirmation transaction (described above in no. 2) to the block. Moreover time to get possible disputes should be dynamic and depends on the network congestions. It requires to developing a mechanism that will notify the bridge contract about congestions to increase the dispute threshold.

4. Another point is that the dispute threshold depends on the number of validators which are online: it requires that majority of validators should have synchronized blockchain. So, for me it means that increasing of the number of validators should increase the threshold. The dependance is not linear but it does not mean that it should not be taken into account.

5. For this approach I see major security limitiation - it is mandatory to have lots of validators. So, it will be insecure to have the bridge with 3-5 validators since the risk of a DDoS attack is increasing. In order to compromise the bridge in the current model you need to control (have access to the private keys) the majority of the bridge validators. In the model you suggest you need to control just one validator and block others to send transactions. Blocking the validators is difficult but not impossible.

Please share your thoughts on this.

[akolotov]

Also an important moment is the independence of RPC providers for the bridge validators. In order to provide maximum of security all validators must have their own nodes synchronizing the foreign and home chains. Otherwise it is possible an attack to compromise RPC providers which is used by groups of validators.

From this point of view economical aspect of such kind of bridge should include expenses which are experiencing by the bridge validators to maintain the chain nodes. The token bridge oracle could be re-worked to use light nodes (and we did few experiments in the past) to reduce the chain nodes cost but it is still outstanding work.

[OliverNChalk]

Hey @akolotov , thanks for the quick response!

My thoughts on your questions:

1. So is it correct that Ethereum -> xDai is just the user deposit on Ethereum. Then xDai -> Ethereum is one validator publishing the signatures on Ethereum? If this is the case, what is the cost of publishing and verifying those signatures. Does it scale with the amount of validators involved?
2. How would xDai know that there was no dispute? I believe the most likely model would be a validator starts a timer on the receiving chain. Then if that timer expires the proposed minting occurs.
3. I agree that time for dispute will be the trickiest parameter to get right.
4. I am not sure what you mean by dispute threshold? But basically it would at most take one validator to start a dispute. This means at most 1 validator needs to be online to prevent malicious behaviour.
5. If this is a major concern you can just use some simple incentives to overcome this. Simply attach a publicly available bounty to successful disputes. Require disputers to stake an amount that their dispute is legit. If their dispute was invalid, take their bond and give some to the user transferring and give the rest to the validators.
6. Public disputes may help with this? But I would have thought you would still need reliable RPC in a voting based model?

You were correct, those were some interesting questions :P

[akolotov]

So is it correct that Ethereum -> xDai is just the user deposit on Ethereum. Then xDai -> Ethereum is one validator publishing the signatures on Ethereum? If this is the case, what is the cost of publishing and verifying those signatures. Does it scale with the amount of validators involved?

Correct. One validator relays collected signatures to the Ethereum Mainnet. If you look at https://blockscout.com/eth/mainnet/tx/0xd8453479702a1c516e8250e1087cc5faddfc82aee20d739bdee614a23226bd7c you will see that it consumed ~129500 gas to confirm transfer by three signatures.

How would xDai know that there was no dispute? I believe the most likely model would be a validator starts a timer on the receiving chain. Then if that timer expires the proposed minting occurs.

Since the timer will be controlled by the bridge contract and any Ethereum contract has no ability to wake up by itself, someone needs to trigger the contract after the timer expiration.

I am not sure what you mean by dispute threshold?

For me, the dispute threshold is a time which the bridge contract will wait after the validator's proposal appearance before allowing to mint/unlock tokens.

basically it would at most take one validator to start a dispute. This means at most 1 validator needs to be online to prevent malicious behaviour.

Correct. But the contract knows nothing if a dispute is not arriving due to agreement of other validators or since they did not handle the corresponding block due to latency with synchronization. Moreover there is a nonzero chance that a dispute will not arrive since other validators are offline.

And things are getting more complex if we consider several possible scenarios.
For example,

1. A misbehaving validator sends a proposal. How long should we wait to get a dispute?
2. A well behaving validator sends a proposal. Another misbehaving validator sends a dispute. How long should we wait to get dispute reject from the rest of validators. Should we reset the timer every time when new information appears?

Simply attach a publicly available bounty to successful disputes. Require disputers to stake an amount that their dispute is legit. If their dispute was invalid, take their bond and give some to the user transferring and give the rest to the validators.

Not sure that understood entire flow properly. Who will attach the bounty? Will the bond be distributed among all validators or only among validators participated in the dispute?

Public disputes may help with this?

Could you clarify which statement this is for? I am quite lost.

But I would have thought you would still need reliable RPC in a voting based model?

Correct. But this model assumes to work with any (even small) number of validators. And bridging fees could (probably) cover at least part of expenses to maintain the RPC nodes. If we increase the number of validators the reward which every validator gets becomes smaller. So, incentive to be the bridge validator is questionable in the case of large number of validators.

And, in fact, these are general questions - what kind of the issue we would like to solve by increasing the number of validators? What motivation of the people or companies to be a bridge validator is?

[OliverNChalk]

Correct. One validator relays collected signatures to the Ethereum Mainnet. If you look at https://blockscout.com/eth/mainnet/tx/0xd8453479702a1c516e8250e1087cc5faddfc82aee20d739bdee614a23226bd7c you will see that it consumed ~129500 gas to confirm transfer by three signatures.

Okay, so the current model cannot scale to 100 validators.

Since the timer will be controlled by the bridge contract and any Ethereum contract has no ability to wake up by itself, someone needs to trigger the contract after the timer expiration.

Anyone can call this, probably the user wanting their tokens. Or we can incentivize validators to this automatically to improve UX.

Correct. But the contract knows nothing if a dispute is not arriving due to agreement of other validators or since they did not handle the corresponding block due to latency with synchronization. Moreover there is a nonzero chance that a dispute will not arrive since other validators are offline.

And things are getting more complex if we consider several possible scenarios.
For example,

A misbehaving validator sends a proposal. How long should we wait to get a dispute?
A well behaving validator sends a proposal. Another misbehaving validator sends a dispute. How long should we wait to get dispute reject from the rest of validators. Should we reset the timer every time when new information appears?

There seems to be a misunderstanding here. The process for commits and disputes are as follows:

1. User sends transfer to smart-contract on sending chain, validators see this.
2. A validator starts the minting process on receiving chain. The minting process has a dispute window attached to it, let's say 15 minutes.
3. If there are no disputes for 15 minutes (anyone can open a dispute), the minting will occur and the transfer will be successful.
4. If anyone starts a dispute, then the transaction will be frozen until one side reaches a super-majority.

Not sure that understood entire flow properly. Who will attach the bounty? Will the bond be distributed among all validators or only among validators participated in the dispute?

Well the proposing validator has a bond associated with their stay as a validator. So if their transaction was indeed fraudulent, their bond will be confiscated and can fund the bounty among other things.

Correct. But this model assumes to work with any (even small) number of validators. And bridging fees could (probably) cover at least part of expenses to maintain the RPC nodes. If we increase the number of validators the reward which every validator gets becomes smaller. So, incentive to be the bridge validator is questionable in the case of large number of validators.

Ideally, validators would already have access to a trustworthy Ethereum node, or they simply run one alongside their PoA node due to the huge economic benefits of doing so. Running two nodes will support hundreds of tokens among critical ones like stablecoins.

And, in fact, these are general questions - what kind of the issue we would like to solve by increasing the number of validators? What motivation of the people or companies to be a bridge validator is?

I think a 3 or 5 validators is not sufficiently decentralized to support moving a million DAI to another chain. Due to the chance for collusion and lack of fault tolerance, with my proposed model you can scale bridges easily alongside scaling the chain's PoA set. As an example, some POA chains are targeting 101 validators, this model would allow bridges to integrate nicely with the existing model.

[akolotov]

Thanks @OliverNChalk for detailed explanation! This is a good brainstorm to understand social and technical issues which could appear in running such service.

Okay, so the current model cannot scale to 100 validators.

:) Definitely not. And I am looking at https://forum.poa.network/c/xdai-chain/validators-intro have some skepticism if it is achievable in practice. Things could be even worse if it is mandatory for the validator to setup the mainnet node as the RPC provider for the bridge oracle.

Anyone can call this, probably the user wanting their tokens.

As I said above, in some scenarios the user has no funds to cover transaction fee to finish minting/unlocking process.

Or we can incentivize validators to this automatically to improve UX.

Correct. It should be the part of the model.

The process for commits and disputes are as follows:

This is my understanding too. I could clarify my previous question in the context of your example:

1. Let's assume that there is no transfer request from a user, but the misbehaving validator sends a transfer proposal. What decision other validators should make? Send a dispute? But before this they need to make sure that they have fully the synchronized chain on their nodes and the chain is on the same head. Otherwise they will send false alarm in the dispute. Even if the head block number and the head block hash are parts of the transfer proposal the misbehaving validator could send very huge block number so others will think that they are not synchronized still.
2. Another scenario is again for the case when there is no transfer request from a user, but there is a high traffic in the chain as so the misbehaving validator sends a transfer proposal with the high gas price as so the transaction included in the block immediately. Even if other validators send disputes their transactions could be still in pending state till the end of the dispute timeout since the lower gas price and the traffic congestion. In December of 2017 regular transactions (when CryptoKitties were the hype) waited for few hours before were included to any block.
3. The third case could be considered for a valid transfer proposal: the validator sends a proposal for a valid transfer request. The misbehaving validator waits for the expiration of the dispute timeout and sends a dispute request. Now the bridge contract should wait for dispute rejects from majority of validators. Hopefully, the fees for bridging a transaction and a bond required to be staked when a dispute is opened are big enough to motivate validators to stay online. Otherwise the new question appear: should we wait for majority of validators votes or we need another timeout how long dispute can be opened which will be applied for the cases when majority of votes cannot be achieved due to absence of online validators to avoid the deny of service attack.

Another thing which came into my mind if the bond confiscation in case of failed dispute could incentivize validators to fail a dispute intentionally. For example, if the validators are anonymous (no KYC procedure is applied) they could fail a dispute in order to get short term profit even if they are excluded from the list of bridge validators after that. In case of high traffic through the bridge assuming that cheating will not be discovered instantly this strategy could cover the amount of the bond staked by an account to be the bridge validator.

Ideally, validators would already have access to a trustworthy Ethereum node, or they simply run one alongside their PoA node due to the huge economic benefits of doing so.

OK. I see. The assumption here is that the network validators should play the role of the bridge validator as well, isn't it? And it means that KYC will be applied for all network validators to be an authority. If so, it could motivate the validators to maintain full node for another chain since otherwise they are under the risk to lose their authority in the PoA chain due to incorrect bridge transaction validation.

I think a 3 or 5 validators is not sufficiently decentralized to support moving a million DAI to another chain.

If 101 validators use their own trustworthy Ethereum nodes as RPC providers it is definitely good. If they use the same RPC provider like INFURA we cannot talk about decentralization.

[OliverNChalk]

OK. I see. The assumption here is that the network validators should play the role of the bridge validator as well, isn't it? And it means that KYC will be applied for all network validators to be an authority. If so, it could motivate the validators to maintain full node for another chain since otherwise they are under the risk to lose their authority in the PoA chain due to incorrect bridge transaction validation.

That is correct, this design would be targeted at having the network validators run the node. This means the validators will be public entities and in some cases KYCd / have a network bond staked.

Let's assume that there is no transfer request from a user, but the misbehaving validator sends a transfer proposal. What decision other validators should make? Send a dispute? But before this they need to make sure that they have fully the synchronized chain on their nodes and the chain is on the same head. Otherwise they will send false alarm in the dispute. Even if the head block number and the head block hash are parts of the transfer proposal the misbehaving validator could send very huge block number so others will think that they are not synchronized still.

This is a valid point, it is easy to prove a transaction was not included in the past. However, it is much harder to prove that you are at the head of the chain.

I feel it is quite unlikely that no validator / member of the public will pull the trigger (in a sufficient dispute period). In fact it will create a nice balance between risk and reward. Which would hopefully result in people sending disputes at different times as it becomes clearer. If this is a more serious issue than I am acknowledging, there are various mechanisms we can implement to further address it.

Another scenario is again for the case when there is no transfer request from a user, but there is a high traffic in the chain as so the misbehaving validator sends a transfer proposal with the high gas price as so the transaction included in the block immediately. Even if other validators send disputes their transactions could be still in pending state till the end of the dispute timeout since the lower gas price and the traffic congestion. In December of 2017 regular transactions (when CryptoKitties were the hype) waited for few hours before were included to any block.

So for this scenario, we have two cases:

• Ethereum is congested. Withdrawing from POA chain to Ethereum could be gamed.
• POA is congested. Depositing to POA from Ethereum could be gamed.

If we assume that the POA chain has higher throughput and is generally less likely to be congested (and would cost more to spam than Ethereum). Then it would make sense to adjust the confirmation time accordingly (i.e. depositing can be faster than withdrawing, which would help onboarding).

Another thing to consider, on the POA chain validators can include their own transactions. As such, if the POA chain is not byzantine we can guarantee that disputes will make it in (if we assume bridge and validator set overlap).

This means our main concern is withdrawing to Ethereum from POA. This is because spamming Ethereum is less costly than spamming POA and POA validators are not miners and thus cannot guarantee transaction inclusion. We also need to assume Ethereum miners are not byzantine. This leads me two thoughts:

1. Miners / mining pools can add as watchtowers/fishermen. We already see this with front-running and arbitraging DEXs, so there could be a scenario where miners include their own dispute transactions. (They would need RPC access to POA).
2. We design the economics appropriately, so that it becomes unprofitable to spam the chain and natural congestion becomes much less of a threat.

For point 2, it's important to note that 10K gas at 100 GWEI cost 0.001 Ether. If we assume disputes can be started with 70K gas, that's a cost of 0.007 Ether per 100 GWEI. This would mean that if the bond was 0.1 Ether we would theoretically have up to 1400 GWEI to play with, if the entire bond went to the disputer.

For the topic of setting the bond, I currently see two options:

1. Validator bonds that sufficiently guarantee security, while ensuring disputers can reasonably afford thousands of GWEI on Ethereum.
2. Transaction based bonds, where the bond is a portion of the transaction (with some minimum). So that it is highly likely that attacking the bridge through chain spam will result in a loss for the attacker (even if they are successful).

The third case could be considered for a valid transfer proposal: the validator sends a proposal for a valid transfer request. The misbehaving validator waits for the expiration of the dispute timeout and sends a dispute request. Now the bridge contract should wait for dispute rejects from majority of validators. Hopefully, the fees for bridging a transaction and a bond required to be staked when a dispute is opened are big enough to motivate validators to stay online. Otherwise the new question appear: should we wait for majority of validators votes or we need another timeout how long dispute can be opened which will be applied for the cases when majority of votes cannot be achieved due to absence of online validators to avoid the deny of service attack.

I think we should prioritize security over latency. If a dispute is initiated, then the transaction will be slowed until the dispute is properly resolved (we can discuss how to most securely properly resolve a dispute).

This then opens the questions of: Can this mechanism be abused to slow down transfer times and degrade UX?

On this point, I personally think that a proper dispute bond will ensure that there is little chance of this happening on a common basis. We can even explore distributing a portion of the dispute bond to the affected user. Do you foresee any issues caused by targeted slowing down of cross-chain transfer beyond UX.

[akolotov]

Thanks! At this moment I see few assumptions and uncertainties. Do you think it is better to prepare a document like a whitepaper draft in order to get more clear model?

[OliverNChalk]

I don't think I have seen any issues yet, so it might make sense to formalize this a bit to make it easier to digest. I will try to get on to this

[OliverNChalk]

https://github.com/OliverNChalk/commit-reveal-bridge/tree/master - I plan to use this as a working doc, it currently lacks details but do you see any issues with this proposal (beyond needing more details)?