Skip to content
This repository has been archived by the owner on Feb 26, 2024. It is now read-only.

v2.5.4 - Gas Exactimation 📏

Compare
Choose a tag to compare
@davidmurdoch davidmurdoch released this 04 Apr 22:37
· 766 commits to develop since this release
v2.5.4
dbac77a

 Highlights    How to Upgrade    Changelog    Related Releases 


A long-standing issue with Ganache has been the fact that we haven't returned EIP-114 compliant gas estimations, AKA the "1/64ths rule". This caused our gas estimates to be too low in cases where a transaction executed opcodes that are subject to this EIP. This in turn was the cause of many frustrations, especially in situations where tools would use gas estimations in transactions without allowing the user to intercept or change the transaction's supplied gas.

Highlights

EIP-114 mandates that certain stackdepth-creating opcodes withhold 1/64th of remaining gas from the stack they create. This has two non-obvious effects:

  1. The gas required for a successful transaction can be greater than the actual gas spent. This is similar to how gas refunds behave.
  2. The extra gas required for a successful transaction varies depending on the transaction's initial gas amount!

Let's say we want to run the following example transaction (note: this transaction is nonsensical and is intended only to illustrate the 1/64ths rule):

DEPTH OPCODE OP FEE
0 PUSH1 3
0 CALL 700
1 ADD 3
1 EXPENSIVE 10000
1 RETURN 0
0 POP 2
0 STOP 0
  Total Gas: 10708

This transaction would cost exactly 10708 gas. However, if you attempted to run this transaction by supplying only 10708 gas it would fail with an "out of gas" exception when it gets to the EXPENSIVE opcode!

The reason for this failure is that the opcode CALL is subject to EIP-114. Here's a breakdown of how this gas is used:

DEPTH OPCODE GAS AVAILABLE OP FEE 1⁄64 WITHHELD
0 PUSH1 10708 3  
0 CALL 10705 700 156
1 ADD 9849 3  
1 EXPENSIVE 9846 10000  
  REVERT OOG    

Instead of 10005 gas available (10705 gas available − 700 op fee) at the ADD opcode,
only 9849 is actually available due to the "withheld" 1/64th: 10005 − FLOOR( 10005 ⁄ 64 ) = 9849; we are now 154 gas short!

All we need to do now is increase our supplied gas by 154, right? Let's see what happens now:

DEPTH OPCODE GAS AVAILABLE OP FEE 1⁄64 WITHHELD
0 PUSH1 10862 3  
0 CALL 10859 700 158
1 ADD 10001 3  
1 EXPENSIVE 9998 10000  
  REVERT OOG    

We still don't have enough gas! The amount withheld increased by 2 gas because the gas supplied to the transaction increased as well!

Because the 1/64ths rule gets applied to the gas remaining, which has increased since our first estimate, 2 more gas gets withheld, resulting in an OOG error!

Now, let's run the same transaction one more time, this time using the result of our new gas estimation algorithm:

DEPTH OPCODE GAS AVAILABLE OP FEE 1⁄64 WITHHELD
0 PUSH1 10864 3  
0 CALL 10861 700 158
1 ADD 10003 3  
1 EXPENSIVE 10000 10000  
1 RETURN 0 0 −158
0 POP 158 2  
0 STOP 156 0  
    156    

It works! Notice that 156 gas was unspent at the end of the transaction, but had we provided even 1 less gas the transaction would have resulted in an "out of gas" exception at EXPENSIVE opcode.


This series of simplified examples attempts to provide a high-level overview of the 1/64th gas estimation calculation. To correctly estimate gas on any contract, we must consider how the gas withheld at any nested stack depth/frame affects the gas needed outside of its execution context.

It's a tricky problem to solve. Some implementations of gas estimation after EIP-114 use interval halving (binary search) by running the transaction through the EVM until the gas estimation converges. This seemed like an unnecessarily CPU-intensive approach to the problem, and we set out to find a (theoretically) more performant, and perfectly accurate, way of estimating gas (which we now refer to as "gas exactimation" here at Truffle).

If you find that any of your transactions are running in to unexpected OOG errors please let us know by filing an issue.


We are especially proud of this algorithm, and we are even more proud of the brilliant minds that went into its creation. Thank you Nick Paterno (@nicholasjpaterno), Amal Sudama (@cds-amal), Chris Cowell (@ccowell), Mike Seese (@seesemichaelj), Benjamin Burns (@benjamincburns), and David Murdoch (@davidmurdoch) for all the work you've put in to this release!

We'll follow up with a detailed blog post on the algorithm itself in the coming weeks.

How to Upgrade

Upgrade to the latest version of ganache-core by running:

npm

npm uninstall ganache-core
npm install ganache-core@latest

yarn

yarn remove ganache-core
yarn add ganache-core@latest

Changelog

Bug Fixes

Documentation

Related Releases


💖 The Truffle Team