EVM arbitrary precision decimal math
相关视频
正文
Abstract
This EIP adds arbitrary precision decimal float OPCODEs for arithmetic via DECADD, DECNEG, DECMUL, DECINV and expression of all elementary functions via DECEXP, DECLN, DECSIN. All decimal values upto the maximal precision allowed by a int256 coefficient and exponent are represented exactly, as c*10^q. All implemented algorithms converge for all inputs given enough precision, as chosen by the user. All calculations are deterministic and gas is precisely embedded bottom-up. Allowing arbitrary precision decimal elementary functions invites the worlds of mathematical finance, machine learning, science, digital art, games and others to Ethereum. The implementation is functional.
Motivation
Currently, to take a power, a^b, of non integer values, requires vast amounts of Solidity code. The simplest task in trading e.g. is to convert volatilities from yearly to daily, which involves taking the 16th root.
Giving users/devs the same ability that scientific calculators have allows for the creation of apps with higher complexity.
The files BlackScholes.yul and Neuron.yul demonstrate how these OPCODEs simplify numerical smart contract code.
Why decimal?
To represent a simple value like 0.1 in binary requires infinite many digits and is therefore not exactly represently in a finite binary machine. Decimal types are much closer to the vast majority of numerical calculations run by humans.
eVm
The EVM is a virtual machine and thereby not restricted by hardware. Usually, assembly languages provide OPCODES that are mimic the ability of hardware. In a virtual machine, we have no such limitations and nothing stops us from adding more complex OPCODEs, as long as fair gas is provided. At the same time, we do not want to clutter the OPCODEs library. EXP, LN and SIN are universal functions that open the path to: powers, trigonometry, integrals, differential equations, machine learning, digital art, etc.
Specification
Decimal
A decimal is defined as
c * 10^q
where c and q are int256.
Notationwise: a = ac * 10^aq b = bc * 10^bq etc.
OPCODE defs
0xd0 DECADD a+b -> c : (ac, aq, bc, bq, precision) -> (cc, cq) 0xd1 DECNEG -a -> b : (ac, aq) -> (bc, bq) 0xd2 DECMUL a*b -> c : (ac, aq, bc, bq, precision) -> (cc, cq) 0xd3 DECINV 1/a -> b : (ac, aq, precision) -> (bc, bq) 0xd4 DECEXP exp(a) -> b : (ac, aq, precision, steps) -> (bc, bq) 0xd5 DECLN ln(a) -> b : (ac, aq, precision, steps) -> (bc, bq) 0xd6 DECSIN sin(a) -> b : (ac, aq, precision, steps) -> (bc, bq)
precision
is the # of digits kept during all calculations. steps
for DECEXP and DECSIN are the # of Taylor expansion steps. steps
for DECLN is the depth of the continued fractions expansion.
Why these functions?
The proposed functions (+,-,*,/,exp,ln,sin) form a small set that combined enable all calculation of all elementary functions, which includes the sets of sums, products, roots and compositions of finitely many polynomial, rational, trigonometric, hyperbolic, and exponential functions, including their inverse functions.
a^b = exp(b * ln(a)) gives us powers and polynomials. cos(a) = sin(tau/4-a), tan(a)=sin(a)/cos(a), etc., gives us all of trigonometry.
Together with arithmetic, we get all elementary functions.
DECNEG instead of DECSUB
Negation is a more general operation vs subtraction. OPCODEs should be as fundamental as possible and as complex as desirable. For the same reason, we have DECINV instead of DECDIV.
DECSUB(a,b) = DECADD(a,DECNEG(b)) DECDIV(a,b) = DECMUL(a,DECINV(b))
DECEXP, DECSIN via Taylor series
The Taylor series of exp and sin converge everywhere and fast. The error falls as fast as the factorial of steps.
DECLN via continued fractions
Ln converges fast using continued fractions within the interval ]0,2]. The implementation scales the input into this interval and scales the result back correctly.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 and RFC 8174.
Rationale
gas
All the above OPCODEs are deterministic, hence the gas cost can be determined. At the same time, the calculations are complex and depend on the input.
It is crucial to have accurate gas costs to avoid energy attacks on nodes.
To this end, the underlying uint256 lib can be wrapped with gas accumulation, as found in the reference implementation in ../assets/eip-EVM+/uint256_wrapped.go. This gives a bottom-up approach to calculating gas, by running the OPCODE.
Because the EVM interprator expects the gas cost before actually running the OPCODE, we are running the OPCODE twice. the first run, identical to the second, is to get the bottom-up gas cost, which is then doubled to account for the actual run plus the gas calculation. On top, we add a fixed emulation cost.
This gives an embedded gas calculation, which works well for complex OPCODEs (see gasEVMPlusEmulate in ../assets/eip-EVM+/gasEVMPlusEmulate.go).
To remove the double gas, we could find an upper bound on gas usage dependent on the function inputs. Alternatively, a future EIP would suggest the following: allow contract code to run whilst accumulating gas (at runtime) and panicking in case of limit breach, without requiring the cost in advance. This only works for contract code that is pure, defined as code that only depends on the user input and the inner bytecode of the contract. Pure contracts cannot use state from the chain, nor make calls to other contracts. pure mathematical functions would e.g. be pure contracts. pure contracts are fully deterministic given the input, allowing a user to estimate gas costs offline (cheaper) and the EVM to panic at runtime, without knowing gas in advance.
Since the costs depend on the input, a fuzzing would give us close to the worst cases (TODO).
Backwards Compatibility
No backward compatibility issues found.
Since the EVM allows contracts to deploy with invalid code, there could be previously invalid code that becomes valid when adding a new OPCODE. The EVM could be designed to expect a version tag at the beginning of all bytecode or (not xor) to only deploy valid code. This is an issue for any new OPCODE.
Test Cases
../assets/eip-EVM+/decimal_float_test.go
Reference Implementation
The reference implementation is found in ../assets/eip-EVM+/decimal_float.go
Security Considerations
There are no security considerations, as long as numerical correctness is guaranteed and gas is collected fairly.
Copyright
Copyright and related rights waived via CC0.