Add secp validator key to enable pessimistic bridge

Staking validators
1

Currently validator keys are ed25519 keys and it is very expensive to verify ed25519 signatures on Ethereum. As a result, our bridge has to be optimistic on NEAR -> Eth side and rely on challenges to make sure that the block headers submitted are valid. This means that it suffers from the problems with optimistic approaches – the challenge period has to be sufficiently long to have practical security, which hinders usability significantly.

To address this, @alexatnear comes up with the following idea: we add an extra secp validator key to sign messages for the bridge. More specifically, block producers, when producing approvals, also sign the following message with their secp key:

(last_final_block_height, last_final_blocks_merkle_root, next_secp_merkle_root, next_total_stake)

and such signatures are added to the body of blocks instead of block headers.

Changes to the Bridge

Now say the block that is signed is B , and the last final block in its ancestry is F . last_final_block_height is the height of F , last_final_blocks_merkle_root is block_merkle_root of F , and next_secp_merkle_root is the merkle root of the SECP public keys and corresponding stakes of the validators in the next epoch.
Any final block can be relayed. The logic of the block relaying on ETH side is then (in pseudocode):

last_known_height
last_known_secp_merkle_root
last_known_total_stake
next_known_secp_merkle_root
next_known_total_stake
last_known_blocks_merkle_root
fn relay_block(block_height, blocks_merkle_root, cur_secp_merkle_root, cur_total_stake, next_secp_merkle_root, next_total_stake, signatures: Vec<public key, stake, signature, merkle proof>) {
   assert ((cur_secp_merkle_root == last_known_secp_merkle_root && cur_total_stake == last_known_total_stake) || (cur_secp_merkle_root == next_known_secp_merkle_root && cur_total_stake == next_known_total_stake));
   assert (last_known_height < block_height)

   signed_stake = 0
   for public_key, stake, signature, merkle_proof in signatures {
      assert merkle_root_matches((public_key, stake), merkle_path, cur_secp_merkle_root)
      assert signature validates(public_key, signature, (block_height, blocks_merkle_root, next_secp_merkle_root, next_total_stake))
      signed_stake += stake
   }
   assert signed_stake > total_stake * 2 / 3

   last_known_height = block_height
   last_known_secp_merkle_root = cur_secp_merkle_root
   next_known_secp_merkle_root = next_secp_merkle_root
   // same for stakes
   last_known_blocks_merkle_root = blocks_merkle_root
}

With this approach, we can calculate the new gas consumption on eth side assuming that we have 100 validators on NEAR and therefore merkle proof of size 7 * 32 bytes.

For each signature:
Call data of size (64 + 7 * 32 + 32 + 16) * 16 GAS = 5376
Signature verification = 3700
Merkle verification = 772 * 7 = 5404
Total: 14480

Some possible savings here: we don’t need to send the public key along, because ecrecover can recover it, it will save 32*16=512 gas per signature.

For 34 signatures: 492320 gas (474912 if we save those 512 gas / signature)

Cost of storage:
We overwrite 6 words: 6 * 5000 = 30000

Base call: 21000

Total: 543320 gas + some overhead for loops and arithmetic.
We can also save on not storing total stake, and instead committing to it as part of the secp_merkle_root, it will save another 10K gas, but will add a SHA256 and a bit more overhead.

So somewhere between 500K and 600K

When we switch to the new bridge design, the change will be to commit to the state merkle root, not to the blocks_merkle_root, but other than that it’s identical.

If a block contains most of the signatures (in particular, the signatures from the top validators that together have 34% of stake), the cost will be cheaper. E.g. today 10 signatures is enough to collect 34%, and thus the cost will be

30000 + 21000 + 14480 * 10 = 195800

Changes to the protocol

As mentioned above, we will need to change approvals and blocks. However, the bigger problem is that we need to modify the staking action. Current proposal is that we introduce a new staking action

StakeAction2 { stake: Balance, public_key: ED25519PublicKey, secp_key: SECP256K1PublicKey, bls_key: BLS12381PublicKey }

that stakes with multiple keys (we add bls key here just in case. It is not going to be used any time soon).

However, the problem is that the current staking pools, which are permissionless and do not have any access keys, will not be able to operate once we the new staking action kicks in. There are two options:

  1. We ask validators to migrate to new staking pools with the new staking action once it is introduced. This will create considerable amount of trouble for validators since all the delegation needs to be moved as well and given that validators most likely do not know all their delegators, this migration could be arduous.

  2. We introduce a new action SetValidatorExtraKeys { account_id: AccountId, validator_key: ED25519PublicKey, secp_key: SECP256K1PublicKey, bls_key: BLS12381PublicKey, signature: ED25519Signature }

When this action is executed, it locates an existing validators and validator proposals matching the account_id and validator_key, validates that the signature is a valid signature on all the fields excluding signature concatenated using the validator public key, and stores the secp key and the bls key in the epoch manager.

If we introduce this new action, then validators do not need to migrate their staking pools. However, the downside is that we need to introduce yet another action, which complicates things even further. For example, this means that we cannot deprecate the old StakeAction and have to deal with it even after the protocol has switched to require secp signatures.

The upgrade process

The protocol upgrade shall be done in three steps:

  1. We introduce the protocol change to approvals and blocks to add secp signatures. At this step we do not enforce the presence of secp signatures.
  2. We introduce the new staking action StakeAction2. This step can be combined with step 1. If we choose to go with option 2 above, we also introduce SetValidatorExtraKeys.
  3. After 1 and 2 are done, we wait until all existing validators have set their secp key and then we upgrade to a new protocol that now requires the presence of secp signatures.

Drawbacks

We have mentioned above that this entire change is quite invasive and affects not only the protocol itself but also various aspects of our tooling. For example, we need to support all the new actions added, and, for new validators, we also need to implement a new version of the staking pool so that they do not have to endure the cumbersomeness of having to issue another transaction to add their secp key.

In addition, as @eatmore points out, this change implies that we tie the bridge to our protocol and if we need to change the message we sign for the bridge in the future, we have to perform a protocol upgrade just for that. Such tight coupling of bridge and the protocol is not optimal from a design perspective.

References

7 Likes
2

We are going to finalize the decision by January 29th. In the meantime, I am going to talk to the key stakeholders:

  • The chain team who is going to be responsible to make this change.
  • The bridge team who is going to be responsible to make the corresponding change to bridge to utilize the secp signatures.
  • Berry pickers who may need to deal with this on the tooling side.
  • The wallet team who may need to update the staking flow.
  • Validators who need to incorporate the new key into their infrastructure.

@evgenykuzyakov @mikedotexe @kendall @illia @alex.shevchenko

2 Likes
3

I still see issues with the SetValidatorExtraKeys being used in a next block after default StakeAction is used. The next block might happen in the next epoch. This seems to affect when the SECP key will be available.

4

As long as this epoch-boundary issue is documented, it seems acceptable (given that going forward Stake2Action should be used, and the SetValidatorExtraKeys is a temporary measure to support poolv1).

1 Like
5

That’s unlikely to happen, since moving entire stake from poolv1 is a big issue, including skipped rewards for the delegators and front-running for names on poolv2. So we should try to design a solution that doesn’t require migrating stake.

6

I have three observations:

  1. I suppose the design will take into account the SECP256k1 k generation problem and the risk of leaking the private key (here for more details)
  2. This is a good opportunity to make the existing staking pools upgradable (and potentially other smart contracts in the same condition), so I support the concept of a poolv2
  3. The Rainbow Bridge is not the only one that may benefit from using these signatures, and the Ethereum blockchain may be the first of many others
1 Like
7

I’m not suggesting to transfer the existing stake. I suspect that most of the eixsting poolv1 pools haven’t changed their ED25519 keys, so the SetValidatorExtraKeys is a one-off operation they need to perform.

Anyway, the worst that can happen if the SetValidatorExtraKeys indeed ended up in a different epoch is that the validator will miss the first two epochs of validation (by the virtue of being kicked out after the first epoch). Given that the pool operator can observe the progress of the epoch, and issue the Stake and SetValidatorExtraKeys actions with sufficient time buffer before the end of the epoch, I don’t think this is a deal breaker.

1 Like
8

To capture the tooling/docs side of what this change would mean, I believe this would require changes to:

9

To capture the tooling/docs side of what this change would mean, I believe this would require changes to:

I don’t think it should be responsibility of berry pickers team to add support for the new Actions. Our goal as a team is to fix/improve the existing tooling. But this request is to implement new features in the tools. So it would fall out of the scope for our goals.
We will communicate better to explain our role as a team.

1 Like
10

Okay. In that case, which team do you think should be responsible for this?

11

Not sure how would it affect wallet. Wallet is only allowing staking via delegating to the pool. I guess we’ll need to support displaying another action in transaction history / transaction signing flow if this is implemented with extra action.

I think biggest problem with new action is that it’s going to affect Ledger app – we’ll need to add support explicitly and it takes forever to get new release out.

12

@Bowen are there alternatives to adding extra action? E.g. using method call instead?

13

I discussed with @evgenykuzyakov and we didn’t see a way around that. We need to make sure that new validators need to be able to join, so it seems that we have to add new actions.

14

I’m not 100% pro this version so it depends on how esoteric we want to go, but there is a way to update pool contracts without requiring to re-delegating and requiring extra actions added.

To do that, we would need mechanics to update contracts on the runtime level as part of the upgrade.

Then we just upgrade all pools together based on contract hash to the new contract code. Given in the storage it’s all stored in the single place - it’s going to be a single update and then every time an account with old contract hash is touched - it get updated to the new contract hash (view functions will need to get handled separately).

This would allow to directly upgrade both Stake action to take 3 arguments and all pools to use it that way and then require validators to call the method on the contract to update their keys.
Given no one uses Stake action directly (e.g. everything done via pool contract) on MainNet, Ledger and other tooling updates are less important.

While we there, as @StefanoPepe suggests, we should make these contracts upgradable easier (vs requiring protocol change).

Thoughts?

1 Like
15

This also feels suboptimal, but to me is better than the current approach since it does not involve introducing new actions. However, it seems that we have to change the contract storage given that we need to store the new secp key. This means that we need in the new contract, some method that rewrite what is stored under STATE. We need to make sure that this fits in the gas limit for one function call.

16

I support the concern of @eatmore and I don’t think we should be adding BLS signatures now. It is unclear what is our plan with BLS going to be, e.g. are there going to be any reasons to have validators use ed25519 or secp once we have BLS? If no, then we would have to rollout BLS and remove ed25519 or secp at the same time. The technical roadmap with BLS is unclear at this point.

Additionally, according @eatmore there are many more nuances and complexities to BLS than to secp and ed25519, and it is easy to implement incorrectly It does not sound to be as easy as just importing some BLS library into our codebase. For example, we already overlooked the nuances of the ed25519 signature, if we use the ed25519 library used in the wallet to verify signatures generated by Rust library that we use in the node, then AFAIU some of them might be rejected.

I would recommend to not do it now, and instead roll it out later, if needed, using the similar process as for secp.

1 Like
17

Not sure why there any gas concerns?
There is a way to do migration on the first contract call, where it loads the old state and updates to the new state. For example, like this Banana release · evgenykuzyakov/place@d78491b · GitHub

I don’t think you can actually do that at the same time. You will need to have a 2 step approach anyway, where first BLS would be added, that will be signed with ed25519 and later remove ed25519.

ETH2 Beacon chain is using BLS currently in production with tooling in various places starting to exist. There is Rust and other language implementations. They are security reviewed as far as I know as well. Are there any concerns with that codebase @eatmore ?

18

There is a way to do migration on the first contract call, where it loads the old state and updates to the new state

Yeah I am aware. I was just thinking whether there would be any gas issue with this step, but looks like no. Also I would like to hear what @evgenykuzyakov thinks about this approach

19

I thought a bit more about it and this approach will require changing near-api-js and near-cli in a non-backward-compatible way. In this case, as @illia suggested, the impact is minimal since no one on mainnet actually stakes directly. However, I wonder whether we want to make a precedence for non-backward-compatible change to begin with. @mikedotexe @vgrichina

20

Yeah I am aware. I was just thinking whether there would be any gas issue with this step, but looks like no. Also I would like to hear what @evgenykuzyakov thinks about this approach

Let’s do this trough 2 step upgrade.

  1. Swap contract on the protocol level. The new contract will only have the upgrade method. No changes to the STATE.
  2. Let owner of the contract to upgrade the contract using a newly introduced method to any of contract which hash is whitelisted in some other contract.

I thought a bit more about it and this approach will require changing near-api-js and near-cli in a non-backward-compatible way. In this case, as @illia suggested, the impact is minimal since no one on mainnet actually stakes directly. However, I wonder whether we want to make a precedence for non-backward-compatible change to begin with. @mikedotexe @vgrichina

I don’t think we should modify Stake action. There are tools on betanet and testnet that will be affected. I suggest we introduce Stake2 action through a protocol upgrade. We’ll have to add a new host method for the Stake2 action to wasm, in order to add it.