Pessimistic bridge gas estimations

[SkidanovAlex]

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 blocks, approvals do not change. The change includes the following:

a) Change to the staking action, now it requires supplying both the ED25519 and SECP key
b) On signing the approval, the block producer additionally signs with SECP key some information needed for the bridge (see below).
c) Only the ED25519 signature on the block approval is included into the header. SECP signature is included in the block, and is only validated during the full block validation (thus, e.g. header sync is not affected).

Specific message that is signed with the secp key for the current bridge:

(last_final_block_height, last_final_blocks_merkle_root, next_secp_merkle_root, next_total_stake)

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
}

I assume 100 block producers, and thus merkle proofs of length 7 * 32 bytes, and signatures of length 64.
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

Thoughts?

[MaksymZavershynskyi]

From my understanding, the biggest difficulty in implementing this change is not in modifying Solidity contracts or even rolling out the new protocol version, but all the logistics and coordination involved with propagating the need of secp keys to the validators, devops, changes to wallet and explorer.

[SkidanovAlex]

There's no changes to wallet and explorer. For validators, all of them are in a telegram channel. The change can be easily rolled out in two consecutive upgrades:

First introduces the new staking action, and stores the secp key. The second introduces the rest of the change (extra field in approvals, extra checks in block verification, extra steps in block creation). Then we roll out the first, and give the validators two weeks to re-issue the staking action, before rolling out the latter.

[MaksymZavershynskyi]

AFAIU explorer needs to update to show the new staking action, the upgrade also needs to be done for indexer, near-cli, and the testing infrastructure that exercises various staking scenarios.

Also, are we going to disable the first type of staking action with the second upgrade?

[SkidanovAlex]

@nearmax the exact approach to changing the staking action is open to discussion: we can either add a new one and fully deprecate (e.g. make it always panic) the old one, or just change the old one once the protocol version changes.

[bowenwang1996]

There was a discussion in another repo on the same topic near/NEPs#140 where @ilblackdragon suggests some way of adding the secp key that I don't yet understand.

[bowenwang1996]

UPD: according to @SkidanovAlex it doesn't work

[alexauroradev]

Just to mention, the current NEAR block relaying cost is around 700k gas.

@abacabadabacaba , can you please do the rough estimation of the gas costs of the new version of the bridge?

[alexauroradev]

This is not corect. The current bridge gas costs are around 6M+

[abacabadabacaba]

I don't like this approach (pessimistic bridge) because it means hardcoding too much Ethereum into our consensus protocol and limiting the ways we can change the protocol in the future. While secp256k1 keys are used in a few other blockchains in addition to Ethereum, the Keccak variant used in Ethereum is hardly ever used anywhere else.

Also, the bridge will have to verify Merkle proofs for some of the trees within NEAR blocks (such as state trie). Currently these trees are using SHA-256, but we may want to change it to some more efficient hash function such as BLAKE-3 (this was proposed during NEARcon Zero). This will break pessimistic verification, however, unless we make a version of each internal tree using Keccak (or another hash supported by EVM) and sign that using secp256k1 keys. This may be difficult to achieve because state trie can be large.

Another approach proposed by @SkidanovAlex was to use secp256k1 keys sign a specific value stored by the bridge contract (the root of its internal Merkle tree) instead of the block hash or block Merkle tree root. But this means that we hardcode this specific bridge instance into the protocol. This also means that we won't be able to implement bridges to other chains as easily, unless we hardcode them as well.

In general, I don't like these approaches because I want to see NEAR as an independent blockchain rather than an extension of Ethereum. So, I would prefer other approaches (such as optimistic or ZK verification).

[SkidanovAlex]

@abacabadabacaba I updated the cost to account for 700 gas / call. It bumped the total cost from ~300K to ~600K, and ~200K if 10 signatures are enough.

[bowenwang1996]

Consolidated discussions in https://gov.near.org/t/add-secp-validator-key-to-enable-pessimistic-bridge/401