Replies: 3 comments
-
This is a good writeup Also I generally agree with (and assume that OZ did similar thinking based on their implementation) that:
Being specific about what can cause the gas cost to spike on the scale of individual mathematical operations, anything that involves jumps is going to ramp things up quickly, so It would be awesome if Solidity offered a way to have function pointer enums that could dispatch this kind of thing in O(1) but it doesn't afaik so instead we end up with if/else if/else if/else if/... when trying to use an enum to modify behaviour, this can really add up for longer enums found in tight loops (people will want to do basic math like "divide" inside loops, right?). I think this is just an unavoidable consequence of trying to decide something at runtime that we probably know at compile time (seems rare that rounding behaviour would need to be dynamic). As an implementation detail i'd recommend the enum variant ordering to match the OZ one where compatible, with at least the implied e.g. instead of enum Rounding {
Expand, // away from zero
Trunc // toward zero
} do this instead enum Rounding {
Trunc, // toward zero
Expand // away from zero
} For just two variants it probably doesn't matter, you're either going to have a single If the long term goal is to go audit all possible rounding modes found in the wild and implement "many" of them, then a more efficient dispatch strategy might be worth looking into at some point. Code size is another thing to consider (which somewhat contradicts what i just wrote about avoiding jumps 😅 ), for example, i already clocked log10 at |
Beta Was this translation helpful? Give feedback.
-
Also I wonder if an "all or nothing" approach and a major version is really needed here, the main current examples of where this is needed is the 4626 spec that literally specifies rounding and AMM/oracle pricing, and all that those both need is There's a very clear 80/20 here imo that could establish a convention/pattern for the lib, and then issues can be backfilled over time to hit the other functions listed above. Probably next tier of importance would be things like sqrt and inv, and then stuff like avg i find much harder to imagine an exploit due to not being able to round up, although i suppose it's possible. |
Beta Was this translation helpful? Give feedback.
-
Potentially relevant: https://github.com/crytic/roundme |
Beta Was this translation helpful? Give feedback.
-
Problem
At the moment, PRBMath supports only one rounding mode: toward zero. This is inconvenient for users who, due to security reasons, require more precise control over the rounding direction.
Small residual amounts (i.e. "dust") can cause functions to revert or lead to potential exploits, e.g. users obtaining something in exchange for nothing. One particular scenario of interest is ERC-4626, which recommends the use of distinct, opposing rounding directions when computing vault shares. In other applications, such as AMMs, the developer may want to round up the price quote to increase their profits.
In this discussion, we will explore the practical ways in which multiple rounding modes could be supported in PRBMath.
Solution
To start, we need to address the following questions:
Let's examine each question separately.
New Rounding Modes
The
Intl.NumberFormat V3
standard specifies nine rounding modes:The first four modes determine the direction of rounding, while the last five employ a rule that rounds to the nearest integer. This requires a tie-breaking rule when the fraction part is exactly 0.5.
For our purposes, we will focus on the direction of rounding and disregard nearest integer rounding (due to the complexity of implementation and gas cost considerations).
Consequently, we have to decide whether to support all possible directions of rounding or just a subset. I would be inclined to start small and iterate, for example, by initially supporting two rounding modes, "expand" and "trunc":
After crossing this first milestone, we can consider the usefulness of the
Ceil
andFloor
modes.Which rounding mode would you find useful?
Wrappers
We will implement rounding modes by introducing wrappers that overload existing functions. This approach is similar to what OpenZeppelin employed in their Math.sol library.
Here's a quick-and-dirty example for the
log2
function:To the extent possible, the existing functions should remain unchanged. We don't want to increase the gas cost for users who are happy with the default rounding mode (
Trunc
).Targets
Precision loss occurs only when dividing numbers. Therefore, to identify the targets that require updates to accommodate multiple rounding modes, we need to look for division operations (high-level
div
, assemblydiv
, and/
) and right shifts (>>
), since right-shifting is equivalent to dividing by a power of two.mulDiv
functions. It may be necessary to create a new variant ofmulDiv
that ceils the result, i.e.mulDivCeil
, and rename the current function tomulDivFloor
-
Common.mulDiv
(implicitlyUD60x18.div
andSD59x18.div
, too)Common.mulDiv18
(implicitlyUD60x18.mul
andSD59x18.mul
, too)Common.mulDivSigned
Common.sqrt
UD60x18.avg
UD60x18.avg
andSD59x18.avg
UD60x18.exp
andSD59x18.exp
SD59x18.exp2
UD60x18.inv
andSD59x18.inv
UD60x18.ln
andSD59x18.ln
SD59x18.log2
UD60x18.log10
andSD59x18.log10
UD60x18.pow
whenx
is lower than 1e18Exceptions
There are certain "in-flight" divisions for which adding rounding mode support is not practical or necessary. Here is a comprehensive list of these instances:
SD59x18.sqrt
.UD60x18.log2
andSD59x18.log2
. These must always round towards zero, as the logarithm computation would not function properly otherwise.y
and the repeated halvings (delta >>= 1
) inUD60x18.log2
andSD59x18.log2
. These variables are managed exclusively by the library and should not be influenced by the user. Additionally, incorporating rounding mode support for these calculations would significantly increase the gas cost of usinglog2
.y >>= 1
) inUD60x18.powu
andSD59x18.powu
. The same rationale as forlog2
applies in this case.Common.sqrt
. For these, the implicit accuracy is good enough since precision converges quadratically, doubling with each iteration.Next Steps
In terms of timeline, I cannot give any promises because this project will take a long time to implement. Also, a new major version (V5) may be needed if not all current implementations remain the same.
PRs welcome if anyone wants to take the lead. I can dedicate cycles to reviewing your work.
Related discussions and resources
Math.sol
library, which supports three rounding modes (down, up, and zero)Intl.NumberFormat V3
Beta Was this translation helpful? Give feedback.
All reactions