Benchmarking Flow implementations with Deviation and Delay

[smol-ninja]

I have crunched some benchmarks for different solutions that we had come up for Flow. The findings can be found in this google sheet. The data was generated using this code. A similar fuzz test has also been added through this PR, which ensures that the maximum deviation and deviation are within accepted bounds which is 0.6% for deviation and 6 hours for delay (these bounds are based on the sheet data).

Definitions

• A time interval $[t0, t1]$ is defined such that first withdrawal is made at $t > t0$ and last withdrawal is made at $t = t1$
• wc = count of withdrawals made in the above time range
• $rps_{18}$ = rate per second in 18 decimal format
• $f$ = scale factor, i.e. $10^{18 - decimal}$
• $wa_i$ = actual amount withdrawn in $i^{th}$ withdrawal
• $wt_i$ = time when $i^{th}$ withdrawal is made
• actual total amount withdrawn, $wa_{actual} = \sum_{i=1}^{i=wc} wa_i$
• desired total amount withdrawn $wa_{desired} = rps * (t1 - t0)$. This is what one would expect in the absence of precision error.

B-1: Stream deviation

Stream deviation represents how much actual total amount withdrawn differ from the desired total amount withdrawn after multiple withdrawals. For example, if a stream is expected to stream 100 tokens in 1 hour, but due to precision error, a user can only withdraw 90 tokens in 1 hour, then deviation is 10%.

$$deviation (\%) = \frac{(wa_{desired} - wa_{actual})}{wa_{desired}} \cdot 100$$

An important invariant is that $wa_{actual} <= wa_{desired}$, otherwise the implementation may lead to over streaming.

Any better solution would yield into a lower deviation.

B-2: Stream Delay

Stream Delay represents the time by which a stream would incur delay in streamed tokens due to precision error introduced by the divisions. In the above example, if instead of 1 hour, it takes 1.5 hours before user can withdraw 100 tokens, the delay is 0.5 hours.

$$delay(s) = \frac{(wa_{desired} - wa_{actual}) \cdot f}{rps_{18}}$$

where

• $f$ = scale factor. For USDC, is is $10^{12}$
• $rps_{18}$ = stream rps in 18 decimal format

Any better solution would yield into a lower delay.

Data

The code is run on USDC with 100,000 fuzz runs in foundry. Data can be found in this google sheet.

Findings

• On main branch, I discovered that, for USDC, with certain RPS, over multiple withdrawals, the delay can go as high as 266 hours with an average of 4 hours. In terms of deviation, it can go as high as 50% with an avg of 0.6%. on fix-precision, the same numbers are very low bringing it closer to a real stream.

• Before 7a80f4d1, the test resulted into the failure of $wa_{actual} <= wa_{desired}$ invariant on fix/precision-issue which means that for some values of $rps$, the solution was leading to over streaming, which is bad.

Explanation below:

1. _streams[streamId].snapshotTime += uint40(scaledDifference / rps)

$$snapshotTime_{stored} < snapshotTime_{real} \text{ due to rounding down by the division}$$

2. ongoingDebt = (elapsedTime * rps) / scaleFactor

$$ongoingDebt_{calculated} < ongoingDebt_{real} \text{ , note that we now have a } 2^{nd} \text{ division}$$

3. withdrawAmount = initialTotalDebt - ongoingDebt

$$withdrawAmount_{calculated} > withdrawAmount_{real} \text{ this is due to the subtraction with a smaller number which is ongoingDebt}$$

Thus it led to over streaming.

• This led me to a better solution which not only fix over-streaming but also minimized the deviation and delay for flow streams. The implementation can be found in 7a80f4d1. The solution is a simplified version of current solution and uses direct assignments which avoids multiple divisions. I will provide a formal proof of the same through a separate doc.

Conclusion

The difference that we thought can only be 1 or 2 can be much higher depending on the value of RPS. Thus, instead of asserting differences in the invariant, we should assert deviation and delay similar to #258.

Reference

• Explanation on precision by Andrei

[smol-ninja]

Here is the supporting maths behind the calculation of snapshot time and snapshot debt in 7a80f4d.

https://gist.github.com/smol-ninja/b26585e5514250f4b6099e8bd951112a

Sumamry

• We compensate for delay due to division by adding remainder debt to the snapshot debt.
• We did not have to modify withdraw amount.

cc @sablier-labs/solidity

PS: sorry for long post.

[PaulRBerg]

Wow, is Flow a monster or not.

[smol-ninja]

Definitely the big brother of Lockup.

[smol-ninja]

Closing this as well.

• Link to data