# [DRAFT] On withdrawal request finalization rate
The document describes the principles and algorithm for calculating the amount of Ether for stETH withdrawal requests finalization. A high-level description of the Lido on Ethereum protocol logic with withdrawals enabled is provided in the [Withdrawals Landscape post](https://hackmd.io/@lido/SyaJQsZoj?type=view#Withdrawal-request-fulfillment-mechanics).

## stETH and shares mechanics

Lido on Ethereum protocol is a staking pool which anyone can submit their Ether and gets stETH in return. stETH is a ERC20 token that represents a holders' share in the staking pool, but the share mechanics is hidden underneath, while the balance of the token are dynamic and reflects the amount of Ether of the corresponding share at the moment. If the staking pool earns rewards or suffers losses, each holder's balance changes accordingly.


As you can see on the picture, shares aren't normalized, so the contract also stores the sum of all shares to be able to calculate each account's balance. When a new holder submits their ETH, the new shares get minted to reflect what share of the protocol controlled ether has been added to the pool.

Normally share rate changes after the consensus layer oracle report comes in and total pooled ether has been rewrited by the up to date value.

You can see that holders who entered the pool with same Ether at different share prices gets minted different amounts of shares:

1) Assume `totalPooledEther = 100` and `totalShares = 100`
2) Holder `0x1` submits `10 ETH` and gets `10 shares` of stETH minted
3) Suppose, the pool registers rewards and `totalPooledEther = 220 ETH`
4) Now `shareRate = 220 ETH / 110 shares = 2 ETH`
5) Holder `0x2` submits `10 ETH` and gets `5 shares` of stETH minted
6) Holder `0x1` has 20 stETH in the wallet, and `0x2` has 10 stETH.

Indeed, the real representation of holder share in the staking pool is `sharesOf(address)` and dynamic `balanceOf(address)` is a UX friendly helper that converts shares to corresponded amount of Ether.

## Withdrawal queue mechanics

Due to the async nature of Ethereum withdrawals, withdrawal requests in Lido on Ethereum protocol are oraganized as a queue. When a holder decides to redeem their stETH, they can lock the stETH token in the Withdrawal Queue contract. Once the Lido protocol on Ethereum completes processing the request, the user can claim the withdrawn ETH.

Processing of the withdrawal queue is possible only at the moment of the oracle report, since only at these moments the exact share rate is known.

During the processing time, the requested Ether is at risk of being slashed. Therefore, it is not fair to give the user Ether according to the amount of the locked stETH. Instead, when a request can be finalized, it is done so according to the current protocol share rate. Also, [an additional rule is enforced at the time of finalization](https://hackmd.io/@lido/SyaJQsZoj?type=view#Main-flow): the redemption rate for fulfilling the request cannot be better than the redemption rate at the time of request creation.

Therefore, each withdrawal request store amount of locked stETH in the moment of request sumbission and shares amount.

Thus, in each withdrawal request, the actual share rate is preserved at the time of queuing. However, due to [rounding issues related to the stETH shares mechanic](https://docs.lido.fi/guides/steth-integration-guide#1-wei-corner-case), the share rate between requests for the same oracle frame can differ by several weis. This is a minor detail that should be taken into account later.

Let's consider an example of a withdrawal queue with requests created at different times when the share rates were different. We will also assume that no requests have been finalized yet, all requests are eligible for finalization in the current oracle report, and there are 1.8 ethers per share.


To calculate the amount of Ether required to finalize a batch of withdrawal requests, we need to sum up the amount of Ether necessary for each request's finalization. This can be calculated as the current share rate multiplied by the number of shares locked in each request, but not more than the number of stETH tokens that were locked at the time of request submission.

# withdrawal_queue = [(1, 1), (2, 4), (3, 7), (2, 3), (1, 1.5), (3, 6), (4, 8)]
# share_rate = 1.8
eth_amount = sum(min(share_rate * sh, bal) for sh, bal in withdrawal_queue)

In this formula, the min function ensures that we don't withdraw more Ether than there were stETH tokens at the time of request submission.


For the case when the share rate in the staking pool only grows, the amount of Ether required for finalization is equal to the sum of stETH tokens snapshoted in the withdrawal requests.

However, for cases where there are requests with a share rate higher and lower than the current one, we cannot rely on the sum of the snapshotted stETH or the sum of shares for all requests multiplied by the current share rate.

To fulfill withdrawal requests at the current share rate, there may be an edge case scenario where an oracle report is missed for some reason, and the next report finalizes requests at a lower rate than the missed one. This situation may have implications for users, but the development team suggests sticking with this design and taking the associated risk. An alternative implementation would require additional complexity for on-chain validation of the amount to be redeemed for requests.

## Finalization algorithm

Withdrawals requests are finalized during accounting oracle report. Each report, it decides how many requests to finalize and at what rate. Requests are finalized in the order in which they were created by moving the cursor to the last finalized request. Oracle must take two things into account:

1. Available ETH and share rate
2. Safe requests finalisation border

To simplify, the logic of calculating the index of the request to which the queue can be finalized is moved to the view function of WQ contract. The accounting oracle calculates the finalization border timestamp, obtains from the smart contract the amount of ether available for the finalization of applications, and also calculates the share rate based on the current CL-balances of the validators and the balance of the withdrawals vault. Further, these three numbers are passed to the view function, which returns the `lastFinalizationRequestIndex` for the current frame.

During the report process, the smart contract burns the number of shares corresponding to the segment being processed. This is possible due to the fact that requests store accumulative amounts instead of values. Additionally, the transferred amount of ether is locked in WQ contract. It is important that the transferred amount is consistent with the value that each user can then request. Otherwise the oracle can send less ether than required to WQ and effectively organise DOS for some holders.

Additionally, the view function returns an array of withdrawal request indexes that specifies the breakdown of the processed segment of the queue to be broken into batches. This array will then be passed to the oracle report so that the smart contract can verify that the final oracle process the next segment of the queue by transferring enough ether.

For the case when the current share rate is higher than all the requests in the queue, it is very easy to build a check, it is enough to calculate the sum of the values of the snapshotted stETHs. In the previous section, it was highlighted that in the case when the share rate is arbitrary, this principle does not work and it is necessary to iterate over all orders to calculate the total amount of ether.


It can be seen that any segment of the withdrawal queue can be divided into batches for which the complexity of calculating the ether for finalization is proportional to a constant (due to the storage of partial amounts of share and step in each request). In practice, the number of such batches will be small enough that counting the amount of ether as the sum of batches is practical for a smart contract.

Thus, at the report stage, the oracle must transfer the breakdown of the segment into batches, and the smart contract must carry out verification. However, for this, the smart contract must store all local extrema of the share rates of all withdrawal requests.


The situation is complicated by the already mentioned rounding error, which generates many false positibe local extrema. The second difficulty is that a smart contract can process only a limited number of batches and local extremes of queue segments associated with the data. The first difficulty can be circumvented by storing the frame index alonw with each withdrawal request. The second difficulty will have to be accepted and kept in mind that in extreme situations the oracle will have to finalize fewer applications than is possible.