Off-chain Node Operators keys storage

1

Off-chain Node Operators keys storage

At Lido protocol, the cost of adding BLS key pairs by Validators and depositing ETH is around 180000-190000 gas per key. With gas price 50 gwei and ETH price ~$2700 it is ~$25 per key, so Lido spends ~$780 per staked 1000 ETH. These costs can be optimized by taking BLS key pairs off-chain.

TLDR: checkout the Merkle tree section and go directly to Results where you can see that Merkle 4096 looks like the optimal setup making the deposit process ~4.7 times cheaper.

Lido stake delegation process consists of several steps:

  1. Node Operators generate locally a bunch of BLS key pairs and calculates deposit_data_root using withdrawal_credentials provided by Lido.
  2. Node Operators uploads this DepositData to the smart contract and awaiting approval.
  3. The protocol governance checks the public key uniqueness and that every deposit_data_root matches Lido withdrawal_credentials.
  4. After key approval deposit bot (or anybody who collect a quorum of 2/3 of the signatures of the deposit security committee members) could start delegation of the 32 buffered ether chunk to the next validator because the contract has all data prepared on-chain. If there are no unused and approved key+signature pairs, no ether gets delegated.

I’ve created a prototype to compare the current “Naive” approach with different off-chain storage strategies. In the best case adding and depositing one BLS key pair costs 40753 gas. With gas price 50 gwei and ETH price ~$2700 it is ~$6 or ~$166 per staked 1000 ETH, which is ~ 4.7 times less than the on-chain storage approach. But remember that these results captured on a simplified prototype, actual protocol results could be slightly differ.

Off-chain keys storage should fulfill three conditions:

  1. Only approved keys can be used for depositing.
  2. Keys reuse should be prohibited. It can be implemented by storing a counter for used keys inside a smart contract and indexing all keys. Along with each key, you should store an integer index of the key.
  3. Any number of keys can be used per one depositBufferedEther call. This requirement allows implementing automatic funds balancing between Node Operators in a round-robin fashion.

Possible optimizations

The main idea of all optimization approaches is taking key pairs off-chain and passing them to depositBufferedEther method. The smart contract only verifies that these keys were approved by DAO and hadn’t been used before.

Simple batch
The most straightforward approach is to concatenate keys into one string and store the hash of this string inside a smart contract. However, it allows depositing only a fixed amount of keys stored in a batch. There is a workaround, but it still requires sending all batched keys inside a transaction. Such workaround limits the batch size reducing the efficiency of such a solution.

Merkle tree
We can generate a Merkle tree from several keys and store only Merkle root on-chain. Merkle tree allows using any amount of keys which it contains per one depositBufferedEther call.

To prohibit keys reuse, the keys inside a tree have their index and, there is a counter inside the smart contract that increments and concatenated to the key before verification.

The keys are often used in a batch. Because we added strict order to the keys we can optimize the Merkle proof algorithm by reusing leafs and nodes of the Merkle tree. We only need to know the index of the first leaves in the Merkle tree slice.

Here is the “verify Merkle slice” implementation:

Python (simplified)
Python (memory-optimized)
Solidity

Let’s take a look at the example. Assume we have a tree storing 16 keys, and we already used the first five keys.

merkle1
merkle12416Ă—808 61.4 KB

For every single key, we need a proof consisting of 1 leaf hash and 3 node hashes, so for five keys, it would be 4*5 = 20 hashes. But because we know that these five keys are going in a row, we can calculate and reuse some hashes (blue) and reduce the overall proof size to 4 (yellow) hashes.

merkle2
merkle22342Ă—834 66.5 KB

In the best case, if the slice’s length is a power of two, proof length can be even smaller.

Merkle + Batch
It was interesting to find out can we save even more by combining prior approaches and using batches as Merkle tree leaves, but such a solution shows worse results than just a bigger Merkle tree and it also has some limitations on the number of keys per one depositBufferedEther call.
That’s why I am not recommending using this approach.

Results
The table below contains the gas cost for adding and depositing one key for every approach with different tree/batch sizes. Rows represent approaches, and columns show the number of keys used pre one depositBufferedEther call.

merkle3
merkle31920Ă—730 247 KB

Full test results

It seems that the cheapest way is storing 4096 keys inside the Merkle tree and deposit them in batches of 128 keys. Merkle trees bigger than 4096 differ negligibly in terms of cost per key. It can make more sense to have only one Merkle tree per one Node operator. One Merkle root per Node operator scheme is easier to implement and manage, and it still can be cost-effective and requires fewer actions from DAO.

I would be happy to work on this and make a pull request into lido-dao repo but I need some input from lido DAO, community and developers first.

13 Likes
2

Hey! Super interesting work. I can see the gas price tests are done against mocks (notably DepositContractMocks) - can you either check against a real thing in mainnet-fork environment or add a baseline test with our current code depositing against same mocks? I currently don’t understand what would be an avg total cost per one validator deposit on the real mainnet with this approach.

3

Thank you:) I switched tests to actual DepositContract at mainet fork (commit) and got new results, it have ratio ~3.6, which is worse than ~4.7 with mock contract, but still pretty good.

3 Likes
4

Currently deposits cost us about 80k gas per deposit:
Ethereum Transaction Hash (Txhash) Details | Etherscan 1,613,698 gas per 20 deposits.

Means it’s a pretty significant improvement both on key submitting step and deposit step.

1 Like
5

Note that while the total savings are significant, adding keys (the operation NOs carry the cost of) becomes ~10x cheaper, allowing smaller NOs effectively enter the staking with way lower ops budget.

5 Likes
6

LEGO has decided to award the research with a retroactive grant! Thank you for the work!

7 Likes
7

Hey, wonderful work! I believe that your proposal looks comprehensive and promising for the Lido core protocol.

I would like to add some notes and speculations for possible keys limits.

  • I believe that we need to enforce a staked hard cap for each NO in the Lido registry for security purposes. So, let’s start with something like 1M ETH per single NO. This value corresponds to 32768 validators (i.e. keys). Nowadays, top Lido NOs have up to 8k total keys.
  • Speculating about the near future, ETH total supply is expected to be lower than 120M in coming years, while staked amount will grow drastically after the upcoming Merge hardfork. Let’s super-idealistically assume that half of the staked amount (~60M) will be deposited with Lido, this means that ~1,9M validators are needed to operate. Thus, at least ~60 NOs are required if each of them can hold up to 32768 keys. I presume, that such constraints are natural and desirable for network decentralization efforts.

To summarize: I propose to implement the off-chain NOs key storage for Lido protocol and enforce one merkle32768 tree root per single NO.

2 Likes
8

In general transferring as much “data” as possible to call data instead of storage is gonna get a lot cheaper so this is the right approach.

https://eips.ethereum.org/EIPS/eip-2028

2 Likes
9

I was inspired by lex’s work. Good job. The topic is very interesting, and I finally got around to putting my thoughts into code.

The purpose of this post is to improve and test under more realistic conditions the applicability of offchain key storage.

The key points I focused on:

  • The ability to make deposits (i.e., use operator keys) in any amount, regardless of the size of the batch. E.g., having a batch size of 4 keys, we can use only 1 key.
  • The ability to distribute any number of deposits to multiple operators in a single transaction.
  • The ability for the operator to have multiple sets of keys (Merkle roots), allowing the operator to dynamically add keys in the future.
  • Since the distribution of deposits goes to several operators, I tried to preserve the logic of key’s use balancing between operators at the time of deposit.

Repo is here: GitHub - krogla/lido-offchain-keys-test

From analyses and tests, it was found that only 15-25% of the Gas usage is spent on internal key processing and Merkle tree checking, and the rest of the Gas is spent directly on calls to the official Deposit contract. Due to that, there are not so many ways to make more optimizations.

The tests showed surprisingly approximately the same amount of gas consumed at the time of deposit per key, regardless of the number of keys, operators, trees and batch size.

  • Avg gas amount to add 1 root for operator: 150k (regardless of the size of the tree)
  • Avg gas amount to deposit 1 key : 50k (taking into account the balancing across multiple operators)

Also, no particular advantage was found in using “batches” instead of individual keys in the Merkle tree. There is a little logic in the test contracts that allows to universally test both single keys and batches. Not using batches will allow reducing the amount of code.

From my point of view, there is no need to add the key index to the leaf hashes and/or add IPFS hash (of the key tree) to the tree root hash. Thanks to proof checking algorithm handles keys in order and saves last used key’s index inside the contract, there is no situation where the key order could be manipulated maliciously. Any key order violation would simply fail to match the root hash.

To exclude abuse, it’s better to adapt the procedure to increase the key limit for operators, for example put to vote through Easytracks “increase the maximum number of trees”.
Or even better, make the procedure of adding a tree through Easytracks.

4 Likes
10

I wonder if having indexes would be useful to handle withdrawals.

2 Likes