accounts/abi/bind, internal/ethapi: binary search gas estimation (#3587)

Gas estimation currently mostly works, but can underestimate for more funky
refunds. This is because various ops (e.g. CALL) need more gas to run than they
actually consume (e.g. 2300 stipend that is refunded if not used). With more
intricate contract interplays, it becomes almost impossible to return a proper
value to the user.

This commit swaps out the simplistic gas estimation to a binary search approach,
honing in on the correct gas use. This does mean that gas estimation needs to
rerun the transaction log(max-price) times to measure whether it fails or not,
but it's a price paid by the transaction issuer, and it should be worth it to
support proper estimates.

1 files changed, 25 insertions, 3 deletions

diff --git a/accounts/abi/bind/backends/simulated.go b/accounts/abi/bind/backends/simulated.go
index c26662ea1..1c34ba0e7 100644
--- a/accounts/abi/bind/backends/simulated.go
+++ b/accounts/abi/bind/backends/simulated.go
@@ -201,10 +201,32 @@ func (b *SimulatedBackend) SuggestGasPrice(ctx context.Context) (*big.Int, error
 func (b *SimulatedBackend) EstimateGas(ctx context.Context, call ethereum.CallMsg) (*big.Int, error) {
 	b.mu.Lock()
 	defer b.mu.Unlock()
-	defer b.pendingState.RevertToSnapshot(b.pendingState.Snapshot())
 
-	_, gas, err := b.callContract(ctx, call, b.pendingBlock, b.pendingState)
-	return gas, err
+	// Binary search the gas requirement, as it may be higher than the amount used
+	var lo, hi uint64
+	if call.Gas != nil {
+		hi = call.Gas.Uint64()
+	} else {
+		hi = b.pendingBlock.GasLimit().Uint64()
+	}
+	for lo+1 < hi {
+		// Take a guess at the gas, and check transaction validity
+		mid := (hi + lo) / 2
+		call.Gas = new(big.Int).SetUint64(mid)
+
+		snapshot := b.pendingState.Snapshot()
+		_, gas, err := b.callContract(ctx, call, b.pendingBlock, b.pendingState)
+		b.pendingState.RevertToSnapshot(snapshot)
+
+		// If the transaction became invalid or used all the gas (failed), raise the gas limit
+		if err != nil || gas.Cmp(call.Gas) == 0 {
+			lo = mid
+			continue
+		}
+		// Otherwise assume the transaction succeeded, lower the gas limit
+		hi = mid
+	}
+	return new(big.Int).SetUint64(hi), nil
 }
 
 // callContract implemens common code between normal and pending contract calls.