Add secp validator key to enable pessimistic bridge

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

Adding SECP keys for the validators · near nearcore · Discussion #3807

For the "pessimistic" bridge we need validators to sign certain messages with SECP256K1 keys. Validators do not have such keys today, and here I propose one way to transition to a state in which va...

Adding secp signatures in addition to ed25519 signatures · near NEPs ·...

@SkidanovAlex mentioned that the bridge could benefit a lot from having secp signatures in block headers in addition to ed25519 signatures because it is cheaper to verify secp signatures on ethereu...

Pessimistic bridge gas estimations · Near-One rainbow-bridge · Discussion #447

UPDATE: updated the costs to account for 700gas/precompile The proposal: Make validators have SECP key in addition to ED25519, and use them to sign messages for the bridge. The signatures on the bl...

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

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.

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).

alexatnear:

(given that going forward Stake2Action should be used, and the SetValidatorExtraKeys is a temporary measure to support poolv1).

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.

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

evgenykuzyakov:

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.

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.

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

• Nomicon
• near-api-js for new action(s)
• NEAR CLI for using the new stake2 action
• writing a new staking pool contract in core-contracts/staking-pool at master · near/core-contracts · GitHub

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.

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

Bowen:

• The wallet team who may need to update the staking flow.

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.

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

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.

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?

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.

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.

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/berryclub@d78491b · GitHub

nearmax:

If no, then we would have to rollout BLS and remove ed25519 or secp at the same time.

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 ?

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

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

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.

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.

That does mean that we still have to support the old Stake action and then later deprecated it once the protocol upgrade is done. We also need to add support for Stake2 in all the tooling. I am fine with this and would like to hear what other people think

evgenykuzyakov:

I don’t think we should modify Stake action.

So what would be happening with the signatures for the bridge if subset of validators continue using Stake actions?

evgenykuzyakov:

The new contract will only have the upgrade method. No changes to the STATE.

That’s fine, given this migration should take more inputs we can indeed add method upgrade(new_code, migration_args).

Where validator would then call with new contract code and arguments that contain new secp and bls keys.

I think one important piece not discussed here is validator key management (not blocking for the main decision, but should be included in the scope of work). @eatmore mentioned potential issues with badly generated secp keys. It’s important to give tools to validators to manage all these keys well. Would be good to check if validators are doing anything outside of generating with generate-key tool and keeping file on disk. E.g. if they use seed phrase inference, hardware modules, etc.

illia:

So what would be happening with the signatures for the bridge if subset of validators continue using Stake actions?

Stake will be deprecated on the protocol level after we introduce Stake2 and people are ready to switch

Here is my feedback:

1. Regarding the way validators register their keys:
   In the long term, we should have Stake action and the corresponding host function accept a secp256k1 key in addition to an Ed25519 key. The proposed SetValidatorExtraKeys action may be suitable as a short-term kludge, but I would prefer a solution that avoids it.

2. Regarding the introduction of BLS keys:
   I am firmly against introducing BLS keys at this time. Currently, there is no signature scheme based on BLS keys that is nearly as popular as Ed25519 or the secp256k1-based ECDSA scheme. Without knowing which exact scheme we are going to use, we also don’t know how exactly the keys will look like. While ETH2 has come up with some specific BLS-based signature scheme, we may want to use a different one in the future. Only after we make this choice, we can introduce BLS keys.

3. Regarding what exactly is going to be signed using the secp256k1 keys:
   While this will probably be decided a bit later, I think that the specific data that is going to be signed with secp256k1 key (as written in the top post) is not optimal for the bridge use case. I think that a better choice will be to sign H(last_final_block_height, last_final_block_merkle_root, H(H(k[0], stake[0]), ..., H(k[n-1], stake[n-1]), total_stake)), where H is the Keccak variant used in Ethereum, and k[i], stake[i] and total_stake refer to the next epoch. Also, the current code for secp256k1 signatures, as implemented in nearcore, will hash any data passed to it using SHA-256. We would probably want to remove this and sign a Keccak hash directly.

Continuing the discussion from Add secp validator key to enable pessimistic bridge:

I’m with @eatmore on hashing. Please don’t forget that hashes are to be verified on the Ethereum side, which means that precompiles for them are not the ones that we have in NEAR.

Supporting the point of the upgradability of pool contracts by @illia and others.

Is there any way of introducing threshold signatures or aggregated signatures to drastically lower the block validation on Ethereum side? @Illia @eatmore @alexatnear

Also, I’m not sure that 34% of the stake will be enough for checks. If we have 50% of the adversarial pools, they still can sign anything and send it to Ethereum. The block won’t be even connected to the chain at all, though it would be treated as correct. So, unfortunately, 67% required. Am I missing something?

The last but not least:
From the bridge product perspective, pessimistic bridge is an upgrade to existing implementation. Our current goal is to make existing implementation work correctly and smoothly. Pessimistic bridge is not in the OKRs for Q1. So there’s no burning need to introduce this protocol upgrade as soon as possible. I believe we can take some additional time to figure out how to implement the upgrade in details and make a smooth transition for all the participants.

In general I’m supporting the initiative.

alex.shevchenko:

Is there any way of introducing threshold signatures or aggregated signatures to drastically lower the block validation on Ethereum side? @Illia @eatmore @alexatnear

Currently, Ethereum doesn’t natively implement all the operations necessary for BLS signatures (EIP 2537 will change this once it is deployed). While it may be possible to implement some of them manually (like we did with Ed25519), this will require a lot of work, and the gas cost will probably be higher than that of Ed25519 (although it will be enough to validate just one signature instead of 100).

alex.shevchenko:

Also, I’m not sure that 34% of the stake will be enough for checks. If we have 50% of the adversarial pools, they still can sign anything and send it to Ethereum. The block won’t be even connected to the chain at all, though it would be treated as correct. So, unfortunately, 67% required. Am I missing something?

Per the consensus spec, the guarantees of soundness and liveness only hold if less then 1/3 of stake is malicious. So, we already have this assumption.

alex.shevchenko:

So there’s no burning need to introduce this protocol upgrade as soon as possible. I believe we can take some additional time to figure out how to implement the upgrade in details and make a smooth transition for all the participants.

Agree, we may better extend the discussion period.

eatmore:

Currently, Ethereum doesn’t natively implement all the operations necessary for BLS signatures (EIP 2537 will change this once it is deployed). While it may be possible to implement some of them manually (like we did with Ed25519), this will require a lot of work, and the gas cost will probably be higher than that of Ed25519 (although it will be enough to validate just one signature instead of 100).

ASFIK, threshold signatures can be implemented on top of many signatures schemes, including ECDSA. BLS is just simplifying the generation algorithm. But for us important only the checking phase, since it’s done on Ethereum. I must admit, that this increases the complexity of the solution, so it might take more time to do the audit.

The problem with implementing threshold signatures on top of ECDSA (and Ed25519) is that producing such a signature requires an interactive algorithm with multiple rounds of communication between all participants. Also, if one of the participants stops participating before the algorithm is finished, the entire process needs to be restarted. This makes it difficult to arrange with many validators any of which may go offline at any time.

I am with @eatmore (who is our only cryptography expert) on BLS: There are many BLS schemes, introduction of some BLS scheme into some clients does not mean it will be accepted, and even if it was decided by everyone does not mean it is going to be enabled. Here are two most recent historic cases:

• EIP-1057 was introduced in major Ethereum clients, however it is unlikely it is going to be enabled;
• EIP-1559 is almost accepted by everyone including Vitalik, but because of a minority of validators it might never be actually turned on;

So we don’t know which BLS scheme will eventually make it into Ethereum mainnet and whether it is going to be turned on at all. Given how much uncertainty we have around it, I think the potential small upside of rolling out BLS together with secp, instead of separately, is lower than the large risk of committing to wrong BLS scheme.

Summarizing what we have discussed so far:

• Everyone seems to be onboard with the necessity of adding validator secp key. However, there are some disagreements on the details.
• For bridge, the exact message to be signed by the secp key is not finalized and I think we can take some more time to mull over this @eatmore @alexatnear @alex.shevchenko
• For the protocol change, it seems that the consensus is that
  1. it is better to upgrade through runtime directly by swapping the contracts.
  2. There is some disagreement regarding whether we should directly modify Stake action or we should do it in a backward compatible way by introducing Stake2 action and deprecating Stake action later.
  3. We do not want to introduce any BLS key at this point.
• For changes in tools, it is mostly around near-api-js and near-cli and there is no need to change anything in wallet. The changes in near-api-js and near-cli are mostly around the change to Stake action (or adding Stake2 action).
• A new staking pool contract and a new staking pool factory contract needs to be written.

Please let me know if I missed something in my summary and we plan to finalize the decision tomorrow after the public meeting.

Recap what we discussed during the meeting today:

• There is consensus on the necessity of this change.
• We plan to upgrade through introducing a new Stake2 action and not modify Stake directly. The reason is that the amount of work needed is very similar and it is preferable to upgrade in a backward compatible way.
• Items that still need to be finalized
  1. The exact message that is signed by the secp key.
  2. The upgrade of the staking pool contract through runtime. We need to make sure that the new contract is also whitelisted and the upgrade process does not allow validators to arbitrarily modify the state.

Hi Bowen,

It’s Daniel from stakefish. Any other details we should be aware about regarding the items that still need to be finalized? Sounds like consensus to move forward is established here. Will the remaining items be blockers on that end?

From a validator perspective probably not at this point. We will finalize the details of the contract upgrade in the upcoming weeks and post the details then. The contract upgrade will likely require some minimal effort from validators (e.g. sending one transaction).

Just submitted a NEP on this topic

The need to introduce secp256k1 keys is not that urgent, since there’s a way how to speed up the token transfers