These are chat archives for ethereum/AllCoreDevs

11th
Aug 2018
ledgerwatch
@AlexeyAkhunov
Aug 11 2018 06:09
@sorpaas Great work - and coming up with the permutation testing
Martin Holst Swende
@holiman
Aug 11 2018 07:37
Yep, well done @sorpaas !
Noel Maersk
@veox
Aug 11 2018 10:21

Would it be sufficient to demonstrate only that the end results match?.. Can it be proven instead that

  • every transition in scheme A has a corresponding transition it scheme B, and
  • there are no other possible transitions (i.e., if A and B are reversed, the result is the same)?

Otherwise, one could imagine a case where (gas_used, gas_refund) during execution differed between the schemes, and caused an "out of gas" in one but not the other.

Noel Maersk
@veox
Aug 11 2018 10:57

EIP-1087 only increments only gas_used while executing a call frame; and increments gas_refund when post-processing the call frame.

EIP-1283 increments gas_used, and both increments and decrements gas_refund during execution; there is no call frame post-processing.

To prove that there is no difference in interim gas usage, it could be enough to examine gas_used only. Not sure...

Noel Maersk
@veox
Aug 11 2018 11:03
(Since OOG is hit when gas_used > gas_limit; gas_refund only figures in during transaction post-processing, which is present in both schemes (and in the status quo, too).)
Wei Tang
@sorpaas
Aug 11 2018 11:08
@veox Yes. There're many difference in interim gas usage. And if you check the test details, gas_used and gas_refund are different many times for EIP-1283 and EIP-1087. We only checked that gas_used - gas_refund is the same.
I think this "proof" is only trying to see whether EIP-1283 covers all of the use cases for net gas metering covered by EIP-1087. There're indeed some cases where in EIP-1283, we put more gases to refund counter than EIP-1087, but nonetheless, it never costs more gases compared to what we do right now. (So if a contract doesn't hit OOG right now, it won't hit OOG under any of the new schemes.)
Noel Maersk
@veox
Aug 11 2018 11:10
Yes, I understand.
Noel Maersk
@veox
Aug 11 2018 11:20
(FTR, a "flicking" case (like 0->1->0->1->...) seems a good example to empirically show a difference in interim gas use.)
Wei Tang
@sorpaas
Aug 11 2018 11:24

Yep. Here's what I get (for 0->1->0->1):

    println!("eip1283: {:?}", eip1283(&[0, 1, 0, 1]));
    println!("eip1087: {:?}", eip1087(&[0, 1, 0, 1]));
    println!("current: {:?}", current(&[0, 1, 0, 1]));

Gets me:

eip1283: Consumption { used: 40200, refund: 19800 }
eip1087: Consumption { used: 20400, refund: 0 }
current: Consumption { used: 45000, refund: 15000 }
Noel Maersk
@veox
Aug 11 2018 13:15
:thumbsup:
Noel Maersk
@veox
Aug 11 2018 13:41

(All IMO)

EIP-1087 more closely represents the work done (requiring a high price for the "first write" only); yet I like EIP-1283 for it not introducing a new data structure and a post-processing step, but getting away with existing counters and pay-as-you-go execution.

The resource consumption concerns (discussed in this channel two days ago) are dwarfed by these two conceptual peculiarities introduced in EIP-1087.

I've asked in the K Framework's chat if they'd present a challenge; also (still) wondering how much of an impact they would have for eWASM. (Not aware of any hardware implementations of the EVM, so "nothing to do".)

Paweł Bylica
@chfast
Aug 11 2018 14:31
This should not be a concern for Ewasm, it will follow EVM cost rules for storage. So far we had no proposals to diverge from it. Unless EIP-1283 / EIP-1087 could be replaced with simpler, but backward incompatible rules.
Noel Maersk
@veox
Aug 11 2018 18:33

Hmm, to ponder further - saying "introducing a new data structure" in reference to EIP-1087 only was incorrect on my side.

EIP-1087 introduces a map (of bools) for marking "dirty" storage, but doesn't make comparisons to the original values until the post-processing step. Post-processing can be delayed until a transaction's execution is complete, so that the refund logic can be applied outside the EVM.

EIP-1283 needs a "cache" (a map, most likely - of uint256s) of original storage values, so that it can determine gas_used when doing a write (20000 or 5000). This cache must now necessarily reside within the EVM. In other words:

EIP-1283 introduces a map (of uint256s) for "original" value look-ups.

Noel Maersk
@veox
Aug 11 2018 18:38
(The above might not make sense depending on how your favourite implementation delineates "inside the EVM". Or maybe I'm battling a chimera here, to understand the trade-offs. Sorry if noise.)
Wei Tang
@sorpaas
Aug 11 2018 18:42
@veox Not quite the case, actually. EIP-1283's "map" is needed to be kept for every client right now -- all clients already have this information because they need to handle it in case a transaction reverts. Just like a storage slot's current value and new value, most clients won't need any new extra structs to fetch that info.
The issue with EIP-1087 is that the "dirty map" concept is in conflict with one of the optimization we do after EIP-658, so for parity-ethereum, we can't have that without getting an extra struct.

So you may say:

  • EIP-1087 needs a map (of uint256s) for "original" value look-ups, and introduces a map (of bools) for marking "dirty" storage.
  • EIP-1283 needs a map (of uint256s) for "original" value look-ups.

The first is needed any way by other operations as well.

Noel Maersk
@veox
Aug 11 2018 18:47
@sorpaas Yes, I understand this point of view. :) Which is why "depending on how your favourite implementation delineates "inside the EVM"". :)
Paweł Bylica
@chfast
Aug 11 2018 18:56
@veox I already have an API to inform what the effect SSTORE has caused ethereum/evmc#52
Martin Holst Swende
@holiman
Aug 11 2018 20:42

So you may say:

EIP-1087 needs a map (of uint256s) for "original" value look-ups, and introduces a map (of bools) for marking "dirty" storage.
EIP-1283 needs a map (of uint256s) for "original" value look-ups.

Hm, not sure it's quite so simple. For geth, which uses a journal, implementing 1283 means that we either perform a journal iteration back to the latest 'snapshot' to obtain the 'original' value, or maintain a dirty-map for each snapshot. So each new call-context, would create a new empty dirty-map.

Afaict, for geth, it would have been easier to implement 1283 with original specified as "what's committed to the the trie right now"a.k.a state of the slot if the outer transaction did a revert -- instead of having it call-context based.

That being said, I've just spent a little bit of time implementing it, and maybe I missed some easier way to get it done

all clients already have this information because they need to handle it in case a transaction reverts.

That is true -- but it's not cheap, since it requires a journal rollback. And 1283 would make every SSTORE force a roll-back/iteration, whereas 1087 would only require one iteration per transaction. (hence the need for a per-context dirty-map)

Wei Tang
@sorpaas
Aug 11 2018 20:47
@holiman Yes. That's Version II (please read downward for the second "Specification" section). And I think Version II is indeed better (and I would recommend we use that). All the above analysis (like the one I did for the informal proof of equivalence) is based on Version II.
TBH, I'm thinking that maybe I should consider removing Version I from the spec. I'm more and more convinced that Version I provided no additional benefits compared with Version II.
Martin Holst Swende
@holiman
Aug 11 2018 20:48
I saw that version II the first time I looked, but today I couldn't find it on the EIP anymore -- so I assumed you had scrapped that ?
Wei Tang
@sorpaas
Aug 11 2018 20:51
Ah that one from sorpaas/EIPs looks like an older version.
Martin Holst Swende
@holiman
Aug 11 2018 20:52
Ok, then I'll continue my implementation attempt later on, and use version II. I believe that will be pretty straight-forward.
Wei Tang
@sorpaas
Aug 11 2018 20:52
:thumbsup:
ledgerwatch
@AlexeyAkhunov
Aug 11 2018 21:45
@veox map of "original" values would be required for both EIP-1087, EIP-1283, with the difference that in EIP-1087 it would be accessed at the post-processing state at the end of transaction, whereas in EIP-1283 it would be accessed at every SSTORE. If in some implementations, the storage modifications are cached throughout the whole block (like in Parity), they would still need to have checkpoints in order to be able to revert transaction efficiently. These checkpoints are probably the source of these "original" values in such cases. One important thing is that "original" values map does not need to be traversable, whereas "dirty" map needs to be.
Wei Tang
@sorpaas
Aug 11 2018 22:34
FYI, I just removed Version I from EIP-1283's specification. The current EIP-1283 specification is the same as the old EIP-1283 specification Version II. Hopefully this will bring less confusions!
https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1283.md
Wei Tang
@sorpaas
Aug 11 2018 22:41
Version II is the version mentioned above, which sets original value to be the storage slot value if a reversion happens for the outer transaction. This should be straightforward for clients that had no issue implementing EIP-1087, and shouldn't incur any additional runtime cost.