reproduce the bug

* use proof serialization

* remove cruft

* save current state

* fix most issues up to this point

* fix remaining build issues

* update the go.mod to use the right branch

* remove custom-defined set type

* update go-verkle to get merged PRs

* extract key, value data from proof

* only activate precomp calculations if this is a verkle chain

Co-authored-by: Jared Wasinger <j-wasinger@hotmail.com>

consensus/ethash/consensus.go

@@ -661,14 +661,19 @@ func accumulateRewards(config *params.ChainConfig, state *state.StateDB, header
 		r.Sub(r, header.Number)
 		r.Mul(r, blockReward)
 		r.Div(r, big8)
+
+		if state.Witness() != nil {
 			uncleCoinbase := utils.GetTreeKeyBalance(uncle.Coinbase.Bytes())
 			state.Witness().TouchAddress(uncleCoinbase, state.GetBalance(uncle.Coinbase).Bytes())
+		}
 		state.AddBalance(uncle.Coinbase, r)
 
 		r.Div(blockReward, big32)
 		reward.Add(reward, r)
 	}
+	if config.IsCancun(header.Number) {
 		coinbase := utils.GetTreeKeyBalance(header.Coinbase.Bytes())
 		state.Witness().TouchAddress(coinbase, state.GetBalance(header.Coinbase).Bytes())
+	}
 	state.AddBalance(header.Coinbase, reward)
 }

core/chain_makers.go

@@ -347,8 +347,8 @@ func GenerateVerkleChain(config *params.ChainConfig, parent *types.Block, engine
 					}
 				}
 				vtr.Hash()
-				_, err := vtr.ProveAndSerialize(keys, statedb.Witness().KeyVals())
-				//block.SetVerkleProof(p)
+				p, err := vtr.ProveAndSerialize(keys, statedb.Witness().KeyVals())
+				block.SetVerkleProof(p)
 				if err != nil {
 					panic(err)
 				}

core/evm.go

@@ -69,7 +69,6 @@ func NewEVMTxContext(msg Message) vm.TxContext {
 	return vm.TxContext{
 		Origin:   msg.From(),
 		GasPrice: new(big.Int).Set(msg.GasPrice()),
-		Accesses: types.NewAccessWitness(),
 	}
 }
 

core/state/state_object.go

@@ -365,15 +365,15 @@ func (s *stateObject) updateTrie(db Database) Trie {
 			}
 			s.db.StorageDeleted += 1
 		} else {
+			if !tr.IsVerkle() {
 				// Encoding []byte cannot fail, ok to ignore the error.
 				v, _ = rlp.EncodeToBytes(common.TrimLeftZeroes(value[:]))
 
-			if !tr.IsVerkle() {
 				s.setError(tr.TryUpdate(key[:], v))
 			} else {
 				k := trieUtils.GetTreeKeyStorageSlot(s.address[:], new(uint256.Int).SetBytes(key[:]))
 				// Update the trie, with v as a value
-				s.setError(tr.TryUpdate(k, v))
+				s.setError(tr.TryUpdate(k, value[:]))
 			}
 			s.db.StorageUpdated += 1
 		}

core/state/statedb.go

@@ -148,14 +148,16 @@ func New(root common.Hash, db Database, snaps *snapshot.Tree) (*StateDB, error)
 		journal:             newJournal(),
 		accessList:          newAccessList(),
 		hasher:              crypto.NewKeccakState(),
-		witness:             types.NewAccessWitness(),
 	}
-	if sdb.snaps == nil && tr.IsVerkle() {
+	if tr.IsVerkle() {
+		sdb.witness = types.NewAccessWitness()
+		if sdb.snaps == nil {
 			sdb.snaps, err = snapshot.New(db.TrieDB().DiskDB(), db.TrieDB(), 1, root, false, true, false, true)
 			if err != nil {
 				return nil, err
 			}
 		}
+	}
 	if sdb.snaps != nil {
 		if sdb.snap = sdb.snaps.Snapshot(root); sdb.snap != nil {
 			sdb.snapDestructs = make(map[common.Hash]struct{})
@@ -182,7 +184,7 @@ func (s *StateDB) StartPrefetcher(namespace string) {
 		s.prefetcher.close()
 		s.prefetcher = nil
 	}
-	if s.snap != nil {
+	if s.snap != nil && !s.trie.IsVerkle() {
 		s.prefetcher = newTriePrefetcher(s.db, s.originalRoot, namespace)
 	}
 }
@@ -286,6 +288,24 @@ func (s *StateDB) GetBalance(addr common.Address) *big.Int {
 	return common.Big0
 }
 
+func (s *StateDB) GetNonceLittleEndian(address common.Address) []byte {
+	var nonceBytes [8]byte
+	binary.LittleEndian.PutUint64(nonceBytes[:], s.GetNonce(address))
+	return nonceBytes[:]
+}
+
+func (s *StateDB) GetBalanceLittleEndian(address common.Address) []byte {
+	var paddedBalance [32]byte
+	balanceBytes := s.GetBalance(address).Bytes()
+	// swap to little-endian
+	for i, j := 0, len(balanceBytes)-1; i < j; i, j = i+1, j-1 {
+		balanceBytes[i], balanceBytes[j] = balanceBytes[j], balanceBytes[i]
+	}
+
+	copy(paddedBalance[:len(balanceBytes)], balanceBytes)
+	return paddedBalance[:len(balanceBytes)]
+}
+
 func (s *StateDB) GetNonce(addr common.Address) uint64 {
 	stateObject := s.getStateObject(addr)
 	if stateObject != nil {
@@ -484,7 +504,8 @@ func (s *StateDB) updateStateObject(obj *stateObject) {
 	if err := s.trie.TryUpdateAccount(addr[:], &obj.data); err != nil {
 		s.setError(fmt.Errorf("updateStateObject (%x) error: %w", addr[:], err))
 	}
-	if len(obj.code) > 0 && s.trie.IsVerkle() {
+	if s.trie.IsVerkle() {
+		if len(obj.code) > 0 {
 			cs := make([]byte, 32)
 			binary.BigEndian.PutUint64(cs, uint64(len(obj.code)))
 			if err := s.trie.TryUpdate(trieUtils.GetTreeKeyCodeSize(addr[:]), cs); err != nil {
@@ -500,6 +521,12 @@ func (s *StateDB) updateStateObject(obj *stateObject) {
 					s.setError(err)
 				}
 			}
+		} else {
+			cs := []byte{0}
+			if err := s.trie.TryUpdate(trieUtils.GetTreeKeyCodeSize(addr[:]), cs); err != nil {
+				s.setError(fmt.Errorf("updateStateObject (%x) error: %w", addr[:], err))
+			}
+		}
 	}
 
 	// If state snapshotting is active, cache the data til commit. Note, this
@@ -713,7 +740,9 @@ func (s *StateDB) Copy() *StateDB {
 		preimages:           make(map[common.Hash][]byte, len(s.preimages)),
 		journal:             newJournal(),
 		hasher:              crypto.NewKeccakState(),
-		witness:             s.witness.Copy(),
+	}
+	if s.witness != nil {
+		state.witness = s.witness.Copy()
 	}
 	// Copy the dirty states, logs, and preimages
 	for addr := range s.journal.dirties {

core/state_processor.go

@@ -95,6 +95,9 @@ func (p *StateProcessor) Process(block *types.Block, statedb *state.StateDB, cfg
 func applyTransaction(msg types.Message, config *params.ChainConfig, bc ChainContext, author *common.Address, gp *GasPool, statedb *state.StateDB, blockNumber *big.Int, blockHash common.Hash, tx *types.Transaction, usedGas *uint64, evm *vm.EVM) (*types.Receipt, error) {
 	// Create a new context to be used in the EVM environment.
 	txContext := NewEVMTxContext(msg)
+	if config.IsCancun(blockNumber) {
+		txContext.Accesses = types.NewAccessWitness()
+	}
 	evm.Reset(txContext, statedb)
 
 	// Apply the transaction to the current state (included in the env).
@@ -128,7 +131,9 @@ func applyTransaction(msg types.Message, config *params.ChainConfig, bc ChainCon
 		receipt.ContractAddress = crypto.CreateAddress(evm.TxContext.Origin, tx.Nonce())
 	}
 
+	if config.IsCancun(blockNumber) {
 		statedb.Witness().Merge(txContext.Accesses)
+	}
 
 	// Set the receipt logs and create the bloom filter.
 	receipt.Logs = statedb.GetLogs(tx.Hash(), blockHash)

core/state_processor_test.go

@@ -377,7 +377,7 @@ func TestProcessStateless(t *testing.T) {
 	genesis := gspec.MustCommit(db)
 	blockchain, _ := NewBlockChain(db, nil, gspec.Config, ethash.NewFaker(), vm.Config{}, nil, nil)
 	defer blockchain.Stop()
-	chain, _ := GenerateVerkleChain(gspec.Config, genesis, ethash.NewFaker(), db, 1, func(_ int, gen *BlockGen) {
+	chain, _ := GenerateVerkleChain(gspec.Config, genesis, ethash.NewFaker(), db, 2, func(_ int, gen *BlockGen) {
 		tx, _ := types.SignTx(types.NewTransaction(0, common.Address{1, 2, 3}, big.NewInt(999), params.TxGas, big.NewInt(875000000), nil), signer, testKey)
 		gen.AddTx(tx)
 		tx, _ = types.SignTx(types.NewTransaction(1, common.Address{}, big.NewInt(999), params.TxGas, big.NewInt(875000000), nil), signer, testKey)

core/state_transition.go

@@ -28,7 +28,6 @@ import (
 	"github.com/ethereum/go-ethereum/core/vm"
 	"github.com/ethereum/go-ethereum/crypto"
 	"github.com/ethereum/go-ethereum/params"
-	trieUtils "github.com/ethereum/go-ethereum/trie/utils"
 )
 
 var emptyCodeHash = crypto.Keccak256Hash(nil)
@@ -261,6 +260,19 @@ func (st *StateTransition) preCheck() error {
 	return st.buyGas()
 }
 
+// tryConsumeGas tries to subtract gas from gasPool, setting the result in gasPool
+// if subtracting more gas than remains in gasPool, set gasPool = 0 and return false
+// otherwise, do the subtraction setting the result in gasPool and return true
+func tryConsumeGas(gasPool *uint64, gas uint64) bool {
+	if *gasPool < gas {
+		*gasPool = 0
+		return false
+	}
+
+	*gasPool -= gas
+	return true
+}
+
 // TransitionDb will transition the state by applying the current message and
 // returning the evm execution result with following fields.
 //
@@ -304,26 +316,34 @@ func (st *StateTransition) TransitionDb() (*ExecutionResult, error) {
 	if st.gas < gas {
 		return nil, fmt.Errorf("%w: have %d, want %d", ErrIntrinsicGas, st.gas, gas)
 	}
-	if st.evm.TxContext.Accesses != nil {
-		if msg.To() != nil {
-			toBalance := trieUtils.GetTreeKeyBalance(msg.To().Bytes())
-			pre := st.state.GetBalance(*msg.To())
-			gas += st.evm.TxContext.Accesses.TouchAddressAndChargeGas(toBalance, pre.Bytes())
+	if st.evm.ChainConfig().IsCancun(st.evm.Context.BlockNumber) {
+		var targetBalance, targetNonce, targetCodeSize, targetCodeKeccak, originBalance, originNonce []byte
 
-			// NOTE: Nonce also needs to be charged, because it is needed for execution
-			// on the statless side.
-			var preTN [8]byte
-			fromNonce := trieUtils.GetTreeKeyNonce(msg.To().Bytes())
-			binary.BigEndian.PutUint64(preTN[:], st.state.GetNonce(*msg.To()))
-			gas += st.evm.TxContext.Accesses.TouchAddressAndChargeGas(fromNonce, preTN[:])
+		targetAddr := msg.To()
+		originAddr := msg.From()
+
+		statelessGasOrigin := st.evm.Accesses.TouchTxOriginAndChargeGas(originAddr.Bytes())
+		if !tryConsumeGas(&st.gas, statelessGasOrigin) {
+			return nil, fmt.Errorf("insufficient gas to cover witness access costs")
+		}
+		originBalance = st.evm.StateDB.GetBalanceLittleEndian(originAddr)
+		originNonce = st.evm.StateDB.GetNonceLittleEndian(originAddr)
+		st.evm.Accesses.SetTxTouchedLeaves(originAddr.Bytes(), originBalance, originNonce)
+
+		if msg.To() != nil {
+			statelessGasDest := st.evm.Accesses.TouchTxExistingAndChargeGas(targetAddr.Bytes())
+			if !tryConsumeGas(&st.gas, statelessGasDest) {
+				return nil, fmt.Errorf("insufficient gas to cover witness access costs")
+			}
+			targetBalance = st.evm.StateDB.GetBalanceLittleEndian(*targetAddr)
+			targetNonce = st.evm.StateDB.GetNonceLittleEndian(*targetAddr)
+			targetCodeKeccak = st.evm.StateDB.GetCodeHash(*targetAddr).Bytes()
+
+			codeSize := uint64(st.evm.StateDB.GetCodeSize(*targetAddr))
+			var codeSizeBytes [32]byte
+			binary.LittleEndian.PutUint64(codeSizeBytes[:8], codeSize)
+			st.evm.Accesses.SetTxExistingTouchedLeaves(targetAddr.Bytes(), targetBalance, targetNonce, targetCodeSize, targetCodeKeccak)
 		}
-		fromBalance := trieUtils.GetTreeKeyBalance(msg.From().Bytes())
-		preFB := st.state.GetBalance(msg.From()).Bytes()
-		fromNonce := trieUtils.GetTreeKeyNonce(msg.From().Bytes())
-		var preFN [8]byte
-		binary.BigEndian.PutUint64(preFN[:], st.state.GetNonce(msg.From()))
-		gas += st.evm.TxContext.Accesses.TouchAddressAndChargeGas(fromNonce, preFN[:])
-		gas += st.evm.TxContext.Accesses.TouchAddressAndChargeGas(fromBalance, preFB[:])
 	}
 	st.gas -= gas
 

core/types/access_witness.go

@@ -19,6 +19,7 @@ package types
 import (
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/params"
+	"github.com/ethereum/go-ethereum/trie/utils"
 )
 
 // AccessWitness lists the locations of the state that are being accessed
@@ -45,6 +46,125 @@ func NewAccessWitness() *AccessWitness {
 	}
 }
 
+// TODO TouchAndCharge + SetLeafValue* does redundant calls to GetTreeKey*
+
+func (aw *AccessWitness) TouchAndChargeProofOfAbsence(addr []byte) uint64 {
+	var gas uint64
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeSize(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeKeccak(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(addr[:]), nil)
+	return gas
+}
+
+func (aw *AccessWitness) TouchAndChargeMessageCall(addr []byte) uint64 {
+	var gas uint64
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeSize(addr[:]), nil)
+	return gas
+}
+
+func (aw *AccessWitness) SetLeafValuesMessageCall(addr, codeSize []byte) {
+	var data [32]byte
+	aw.TouchAddress(utils.GetTreeKeyVersion(addr[:]), data[:])
+	aw.TouchAddress(utils.GetTreeKeyCodeSize(addr[:]), codeSize[:])
+}
+
+func (aw *AccessWitness) TouchAndChargeValueTransfer(callerAddr, targetAddr []byte) uint64 {
+	var gas uint64
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(callerAddr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(targetAddr[:]), nil)
+	return gas
+}
+
+func (aw *AccessWitness) SetLeafValuesValueTransfer(callerAddr, targetAddr, callerBalance, targetBalance []byte) {
+	aw.TouchAddress(utils.GetTreeKeyBalance(callerAddr[:]), callerBalance)
+	aw.TouchAddress(utils.GetTreeKeyBalance(targetAddr[:]), targetBalance)
+}
+
+// TouchAndChargeContractCreateInit charges access costs to initiate
+// a contract creation
+func (aw *AccessWitness) TouchAndChargeContractCreateInit(addr []byte) uint64 {
+	var gas uint64
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(addr[:]), nil)
+	return gas
+}
+
+func (aw *AccessWitness) SetLeafValuesContractCreateInit(addr, nonce []byte) {
+	var version [32]byte
+	aw.TouchAddress(utils.GetTreeKeyVersion(addr[:]), version[:])
+	aw.TouchAddress(utils.GetTreeKeyNonce(addr[:]), nonce)
+}
+
+// TouchAndChargeContractCreateCompleted charges access access costs after
+// the completion of a contract creation to populate the created account in
+// the tree
+func (aw *AccessWitness) TouchAndChargeContractCreateCompleted(addr []byte, withValue bool) uint64 {
+	var gas uint64
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(addr[:]), nil)
+	if withValue {
+		gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(addr[:]), nil)
+	}
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeSize(addr[:]), nil)
+	gas += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeKeccak(addr[:]), nil)
+	return gas
+}
+
+func (aw *AccessWitness) SetLeafValuesContractCreateCompleted(addr, codeSize, codeKeccak []byte) {
+	aw.TouchAddress(utils.GetTreeKeyCodeSize(addr[:]), codeSize)
+	aw.TouchAddress(utils.GetTreeKeyCodeKeccak(addr[:]), codeKeccak)
+}
+
+func (aw *AccessWitness) TouchTxAndChargeGas(originAddr, targetAddr []byte) uint64 {
+	var gasUsed uint64
+	var version [32]byte
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(originAddr[:]), version[:])
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(originAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(originAddr[:]), nil)
+
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(targetAddr[:]), version[:])
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(targetAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(targetAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeSize(targetAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeKeccak(targetAddr[:]), nil)
+	return gasUsed
+}
+
+func (aw *AccessWitness) TouchTxOriginAndChargeGas(originAddr []byte) uint64 {
+	var gasUsed uint64
+	var version [32]byte
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(originAddr[:]), version[:])
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(originAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(originAddr[:]), nil)
+	return gasUsed
+}
+
+func (aw *AccessWitness) TouchTxExistingAndChargeGas(targetAddr []byte) uint64 {
+	var gasUsed uint64
+	var version [32]byte
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyVersion(targetAddr[:]), version[:])
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyBalance(targetAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyNonce(targetAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeSize(targetAddr[:]), nil)
+	gasUsed += aw.TouchAddressAndChargeGas(utils.GetTreeKeyCodeKeccak(targetAddr[:]), nil)
+	return gasUsed
+}
+
+func (aw *AccessWitness) SetTxTouchedLeaves(originAddr, originBalance, originNonce []byte) {
+	aw.TouchAddress(utils.GetTreeKeyBalance(originAddr[:]), originBalance)
+	aw.TouchAddress(utils.GetTreeKeyNonce(originAddr[:]), originNonce)
+}
+
+func (aw *AccessWitness) SetTxExistingTouchedLeaves(targetAddr, targetBalance, targetNonce, targetCodeSize, targetCodeHash []byte) {
+	aw.TouchAddress(utils.GetTreeKeyBalance(targetAddr[:]), targetBalance)
+	aw.TouchAddress(utils.GetTreeKeyNonce(targetAddr[:]), targetNonce)
+	aw.TouchAddress(utils.GetTreeKeyCodeSize(targetAddr[:]), targetCodeSize)
+	aw.TouchAddress(utils.GetTreeKeyCodeKeccak(targetAddr[:]), targetCodeHash)
+}
+
 // TouchAddress adds any missing addr to the witness and returns respectively
 // true if the stem or the stub weren't arleady present.
 func (aw *AccessWitness) TouchAddress(addr, value []byte) (bool, bool) {

core/vm/analysis.go

@@ -61,8 +61,8 @@ func (bits bitvec) set16(pos uint64) {
 	bits[pos/8+2] = ^a
 }
 
-// codeSegment checks if the position is in a code segment.
-func (bits *bitvec) codeSegment(pos uint64) bool {
+// IsCode checks if the position is in a code segment.
+func (bits *bitvec) IsCode(pos uint64) bool {
 	return ((*bits)[pos/8] & (0x80 >> (pos % 8))) == 0
 }
 

core/vm/common.go

@@ -63,6 +63,18 @@ func getData(data []byte, start uint64, size uint64) []byte {
 	return common.RightPadBytes(data[start:end], int(size))
 }
 
+func getDataAndAdjustedBounds(data []byte, start uint64, size uint64) (codeCopyPadded []byte, actualStart uint64, sizeNonPadded uint64) {
+	length := uint64(len(data))
+	if start > length {
+		start = length
+	}
+	end := start + size
+	if end > length {
+		end = length
+	}
+	return common.RightPadBytes(data[start:end], int(size)), start, end
+}
+
 // toWordSize returns the ceiled word size required for memory expansion.
 func toWordSize(size uint64) uint64 {
 	if size > math.MaxUint64-31 {

core/vm/contract.go

@@ -28,6 +28,13 @@ type ContractRef interface {
 	Address() common.Address
 }
 
+// AnalyzedContract is an interface for a piece of contract
+// code that has undegone jumpdest analysis, and whose bytecode
+// can be queried to determine if it is "contract code"
+type AnalyzedContract interface {
+	IsCode(dest uint64) bool
+}
+
 // AccountRef implements ContractRef.
 //
 // Account references are used during EVM initialisation and
@@ -58,6 +65,9 @@ type Contract struct {
 	CodeAddr *common.Address
 	Input    []byte
 
+	// is the execution frame represented by this object a contract deployment 
+	IsDeployment bool
+
 	Gas   uint64
 	value *big.Int
 }
@@ -101,7 +111,7 @@ func (c *Contract) validJumpdest(dest *uint256.Int) bool {
 func (c *Contract) IsCode(udest uint64) bool {
 	// Do we already have an analysis laying around?
 	if c.analysis != nil {
-		return c.analysis.codeSegment(udest)
+		return c.analysis.IsCode(udest)
 	}
 	// Do we have a contract hash already?
 	// If we do have a hash, that means it's a 'regular' contract. For regular
@@ -117,7 +127,7 @@ func (c *Contract) IsCode(udest uint64) bool {
 		}
 		// Also stash it in current contract for faster access
 		c.analysis = analysis
-		return analysis.codeSegment(udest)
+		return analysis.IsCode(udest)
 	}
 	// We don't have the code hash, most likely a piece of initcode not already
 	// in state trie. In that case, we do an analysis, and save it locally, so
@@ -126,7 +136,7 @@ func (c *Contract) IsCode(udest uint64) bool {
 	if c.analysis == nil {
 		c.analysis = codeBitmap(c.Code)
 	}
-	return c.analysis.codeSegment(udest)
+	return c.analysis.IsCode(udest)
 }
 
 // AsDelegate sets the contract to be a delegate call and returns the current

core/vm/evm.go

@@ -125,14 +125,12 @@ type EVM struct {
 	// available gas is calculated in gasCall* according to the 63/64 rule and later
 	// applied in opCall*.
 	callGasTemp uint64
-
-	accesses map[common.Hash]common.Hash
 }
 
 // NewEVM returns a new EVM. The returned EVM is not thread safe and should
 // only ever be used *once*.
 func NewEVM(blockCtx BlockContext, txCtx TxContext, statedb StateDB, chainConfig *params.ChainConfig, config Config) *EVM {
-	if txCtx.Accesses == nil {
+	if txCtx.Accesses == nil && chainConfig.IsCancun(blockCtx.BlockNumber) {
 		txCtx.Accesses = types.NewAccessWitness()
 	}
 	evm := &EVM{
@@ -170,6 +168,19 @@ func (evm *EVM) Interpreter() *EVMInterpreter {
 	return evm.interpreter
 }
 
+// tryConsumeGas tries to subtract gas from gasPool, setting the result in gasPool
+// if subtracting more gas than remains in gasPool, set gasPool = 0 and return false
+// otherwise, do the subtraction setting the result in gasPool and return true
+func tryConsumeGas(gasPool *uint64, gas uint64) bool {
+	if *gasPool < gas {
+		*gasPool = 0
+		return false
+	}
+
+	*gasPool -= gas
+	return true
+}
+
 // Call executes the contract associated with the addr with the given input as
 // parameters. It also handles any necessary value transfer required and takes
 // the necessary steps to create accounts and reverses the state in case of an
@@ -191,6 +202,10 @@ func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas
 
 	if !evm.StateDB.Exist(addr) {
 		if !isPrecompile && evm.chainRules.IsEIP158 && value.Sign() == 0 {
+			if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+				// proof of absence
+				tryConsumeGas(&gas, evm.Accesses.TouchAndChargeProofOfAbsence(caller.Address().Bytes()))
+			}
 			// Calling a non existing account, don't do anything, but ping the tracer
 			if evm.Config.Debug {
 				if evm.depth == 0 {
@@ -205,6 +220,11 @@ func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas
 		}
 		evm.StateDB.CreateAccount(addr)
 	}
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) && value.Sign() != 0 {
+		callerBalanceBefore := evm.StateDB.GetBalanceLittleEndian(caller.Address())
+		targetBalanceBefore := evm.StateDB.GetBalanceLittleEndian(addr)
+		evm.Accesses.SetLeafValuesValueTransfer(caller.Address().Bytes()[:], addr[:], callerBalanceBefore, targetBalanceBefore)
+	}
 	evm.Context.Transfer(evm.StateDB, caller.Address(), addr, value)
 
 	// Capture the tracer start/end events in debug mode
@@ -229,24 +249,22 @@ func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas
 		// Initialise a new contract and set the code that is to be used by the EVM.
 		// The contract is a scoped environment for this execution context only.
 		code := evm.StateDB.GetCode(addr)
+		if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+			codeSize := uint64(len(code))
+			var codeSizeBytes [32]byte
+			binary.LittleEndian.PutUint64(codeSizeBytes[:8], codeSize)
+			evm.Accesses.SetLeafValuesMessageCall(addr[:], codeSizeBytes[:])
+		}
+
 		if len(code) == 0 {
 			ret, err = nil, nil // gas is unchanged
 		} else {
-			// Touch the account data
-			var data [32]byte
-			evm.Accesses.TouchAddress(utils.GetTreeKeyVersion(addr.Bytes()), data[:])
-			binary.BigEndian.PutUint64(data[:], evm.StateDB.GetNonce(addr))
-			evm.Accesses.TouchAddress(utils.GetTreeKeyNonce(addr[:]), data[:])
-			evm.Accesses.TouchAddress(utils.GetTreeKeyBalance(addr[:]), evm.StateDB.GetBalance(addr).Bytes())
-			binary.BigEndian.PutUint64(data[:], uint64(len(code)))
-			evm.Accesses.TouchAddress(utils.GetTreeKeyCodeSize(addr[:]), data[:])
-			evm.Accesses.TouchAddress(utils.GetTreeKeyCodeKeccak(addr[:]), evm.StateDB.GetCodeHash(addr).Bytes())
-
 			addrCopy := addr
 			// If the account has no code, we can abort here
 			// The depth-check is already done, and precompiles handled above
 			contract := NewContract(caller, AccountRef(addrCopy), value, gas)
 			contract.SetCallCode(&addrCopy, evm.StateDB.GetCodeHash(addrCopy), code)
+			contract.IsDeployment = true
 			ret, err = evm.interpreter.Run(contract, input, false)
 			gas = contract.Gas
 		}
@@ -302,6 +320,12 @@ func (evm *EVM) CallCode(caller ContractRef, addr common.Address, input []byte,
 	if p, isPrecompile := evm.precompile(addr); isPrecompile {
 		ret, gas, err = RunPrecompiledContract(p, input, gas)
 	} else {
+		if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+			codeSize := uint64(evm.StateDB.GetCodeSize(addr))
+			var codeSizeBytes [32]byte
+			binary.LittleEndian.PutUint64(codeSizeBytes[:8], codeSize)
+			evm.Accesses.SetLeafValuesMessageCall(addr.Bytes()[:], codeSizeBytes[:])
+		}
 		addrCopy := addr
 		// Initialise a new contract and set the code that is to be used by the EVM.
 		// The contract is a scoped environment for this execution context only.
@@ -346,6 +370,12 @@ func (evm *EVM) DelegateCall(caller ContractRef, addr common.Address, input []by
 	if p, isPrecompile := evm.precompile(addr); isPrecompile {
 		ret, gas, err = RunPrecompiledContract(p, input, gas)
 	} else {
+		if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+			codeSize := uint64(evm.StateDB.GetCodeSize(addr))
+			var codeSizeBytes [32]byte
+			binary.LittleEndian.PutUint64(codeSizeBytes[:8], codeSize)
+			evm.Accesses.SetLeafValuesMessageCall(addr.Bytes()[:], codeSizeBytes[:])
+		}
 		addrCopy := addr
 		// Initialise a new contract and make initialise the delegate values
 		contract := NewContract(caller, AccountRef(caller.Address()), nil, gas).AsDelegate()
@@ -398,6 +428,12 @@ func (evm *EVM) StaticCall(caller ContractRef, addr common.Address, input []byte
 	if p, isPrecompile := evm.precompile(addr); isPrecompile {
 		ret, gas, err = RunPrecompiledContract(p, input, gas)
 	} else {
+		if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+			codeSize := uint64(evm.StateDB.GetCodeSize(addr))
+			var codeSizeBytes [32]byte
+			binary.LittleEndian.PutUint64(codeSizeBytes[:8], codeSize)
+			evm.Accesses.SetLeafValuesMessageCall(addr.Bytes()[:], codeSizeBytes[:])
+		}
 		// At this point, we use a copy of address. If we don't, the go compiler will
 		// leak the 'contract' to the outer scope, and make allocation for 'contract'
 		// even if the actual execution ends on RunPrecompiled above.
@@ -435,6 +471,13 @@ func (c *codeAndHash) Hash() common.Hash {
 
 // create creates a new contract using code as deployment code.
 func (evm *EVM) create(caller ContractRef, codeAndHash *codeAndHash, gas uint64, value *big.Int, address common.Address, typ OpCode) ([]byte, common.Address, uint64, error) {
+	var zeroVerkleLeaf [32]byte
+	var balanceBefore []byte
+
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		evm.Accesses.SetLeafValuesContractCreateInit(address.Bytes()[:], zeroVerkleLeaf[:])
+	}
+
 	// Depth check execution. Fail if we're trying to execute above the
 	// limit.
 	if evm.depth > int(params.CallCreateDepth) {
@@ -464,12 +507,21 @@ func (evm *EVM) create(caller ContractRef, codeAndHash *codeAndHash, gas uint64,
 	if evm.chainRules.IsEIP158 {
 		evm.StateDB.SetNonce(address, 1)
 	}
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		// note: assumption is that the nonce, code size, code hash
+		// will be 0x0000...00 at the target account before it is created
+		// otherwise would imply contract creation collision which is
+		// impossible if self-destruct is removed
+		balanceBefore = evm.StateDB.GetBalanceLittleEndian(address)
+	}
+
 	evm.Context.Transfer(evm.StateDB, caller.Address(), address, value)
 
 	// Initialise a new contract and set the code that is to be used by the EVM.
 	// The contract is a scoped environment for this execution context only.
 	contract := NewContract(caller, AccountRef(address), value, gas)
 	contract.SetCodeOptionalHash(&address, codeAndHash)
+	contract.IsDeployment = true
 
 	if evm.Config.NoRecursion && evm.depth > 0 {
 		return nil, address, gas, nil
@@ -520,6 +572,18 @@ func (evm *EVM) create(caller ContractRef, codeAndHash *codeAndHash, gas uint64,
 		}
 	}
 
+	if err == nil && evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		if !contract.UseGas(evm.Accesses.TouchAndChargeContractCreateCompleted(address.Bytes()[:], value.Sign() != 0)) {
+			evm.StateDB.RevertToSnapshot(snapshot)
+			err = ErrOutOfGas
+		} else {
+			evm.Accesses.SetLeafValuesContractCreateCompleted(address.Bytes()[:], zeroVerkleLeaf[:], zeroVerkleLeaf[:])
+			if value.Sign() != 0 {
+				evm.Accesses.TouchAddress(utils.GetTreeKeyBalance(address.Bytes()[:]), balanceBefore)
+			}
+		}
+	}
+
 	if evm.Config.Debug {
 		if evm.depth == 0 {
 			evm.Config.Tracer.CaptureEnd(ret, gas-contract.Gas, time.Since(start), err)

core/vm/gas_table.go

@@ -21,9 +21,9 @@ import (
 
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/common/math"
+	"github.com/ethereum/go-ethereum/log"
 	"github.com/ethereum/go-ethereum/params"
 	trieUtils "github.com/ethereum/go-ethereum/trie/utils"
-	"github.com/holiman/uint256"
 )
 
 // memoryGasCost calculates the quadratic gas for memory expansion. It does so
@@ -88,17 +88,6 @@ func memoryCopierGas(stackpos int) gasFunc {
 	}
 }
 
-func gasExtCodeSize(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {
-	usedGas := uint64(0)
-	slot := stack.Back(0)
-	if evm.accesses != nil {
-		index := trieUtils.GetTreeKeyCodeSize(slot.Bytes())
-		usedGas += evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
-	}
-
-	return usedGas, nil
-}
-
 var (
 	gasCallDataCopy        = memoryCopierGas(2)
 	gasCodeCopyStateful    = memoryCopierGas(2)
@@ -106,9 +95,20 @@ var (
 	gasReturnDataCopy      = memoryCopierGas(2)
 )
 
+func gasExtCodeSize(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {
+	usedGas := uint64(0)
+	slot := stack.Back(0)
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		index := trieUtils.GetTreeKeyCodeSize(slot.Bytes())
+		usedGas += evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
+	}
+
+	return usedGas, nil
+}
+
 func gasCodeCopy(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {
 	var statelessGas uint64
-	if evm.accesses != nil {
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
 		var (
 			codeOffset = stack.Back(1)
 			length     = stack.Back(2)
@@ -117,21 +117,12 @@ func gasCodeCopy(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memory
 		if overflow {
 			uint64CodeOffset = 0xffffffffffffffff
 		}
-		uint64CodeEnd, overflow := new(uint256.Int).Add(codeOffset, length).Uint64WithOverflow()
+		uint64Length, overflow := length.Uint64WithOverflow()
 		if overflow {
-			uint64CodeEnd = 0xffffffffffffffff
+			uint64Length = 0xffffffffffffffff
 		}
-		addr := contract.Address()
-		chunk := uint64CodeOffset / 31
-		endChunk := uint64CodeEnd / 31
-		// XXX uint64 overflow in condition check
-		for ; chunk < endChunk; chunk++ {
-
-			// TODO make a version of GetTreeKeyCodeChunk without the bigint
-			index := trieUtils.GetTreeKeyCodeChunk(addr[:], uint256.NewInt(chunk))
-			statelessGas += evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
-		}
-
+		_, offset, nonPaddedSize := getDataAndAdjustedBounds(contract.Code, uint64CodeOffset, uint64Length)
+		statelessGas = touchEachChunksAndChargeGas(offset, nonPaddedSize, contract.Address().Bytes()[:], nil, nil, evm.Accesses)
 	}
 	usedGas, err := gasCodeCopyStateful(evm, contract, stack, mem, memorySize)
 	return usedGas + statelessGas, err
@@ -139,30 +130,27 @@ func gasCodeCopy(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memory
 
 func gasExtCodeCopy(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {
 	var statelessGas uint64
-	if evm.accesses != nil {
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
 		var (
-			a          = stack.Back(0)
 			codeOffset = stack.Back(2)
 			length     = stack.Back(3)
+			targetAddr = stack.Back(0).Bytes20()
 		)
 		uint64CodeOffset, overflow := codeOffset.Uint64WithOverflow()
 		if overflow {
 			uint64CodeOffset = 0xffffffffffffffff
 		}
-		uint64CodeEnd, overflow := new(uint256.Int).Add(codeOffset, length).Uint64WithOverflow()
+		uint64Length, overflow := length.Uint64WithOverflow()
 		if overflow {
-			uint64CodeEnd = 0xffffffffffffffff
+			uint64Length = 0xffffffffffffffff
 		}
-		addr := common.Address(a.Bytes20())
-		chunk := uint64CodeOffset / 31
-		endChunk := uint64CodeEnd / 31
-		// XXX uint64 overflow in condition check
-		for ; chunk < endChunk; chunk++ {
-			// TODO(@gballet) make a version of GetTreeKeyCodeChunk without the bigint
-			index := trieUtils.GetTreeKeyCodeChunk(addr[:], uint256.NewInt(chunk))
-			statelessGas += evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
-		}
-
+		// note:  we must charge witness costs for the specified range regardless of whether it
+		// is in-bounds of the actual target account code.  This is because we must charge the cost
+		// before hitting the db to be able to now what the actual code size is.  This is different
+		// behavior from CODECOPY which only charges witness access costs for the part of the range
+		// which overlaps in the account code.  TODO: clarify this is desired behavior and amend the
+		// spec.
+		statelessGas = touchEachChunksAndChargeGas(uint64CodeOffset, uint64Length, targetAddr[:], nil, nil, evm.Accesses)
 	}
 	usedGas, err := gasExtCodeCopyStateful(evm, contract, stack, mem, memorySize)
 	return usedGas + statelessGas, err
@@ -171,11 +159,11 @@ func gasExtCodeCopy(evm *EVM, contract *Contract, stack *Stack, mem *Memory, mem
 func gasSLoad(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {
 	usedGas := uint64(0)
 
-	if evm.accesses != nil {
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
 		where := stack.Back(0)
 		addr := contract.Address()
 		index := trieUtils.GetTreeKeyStorageSlot(addr[:], where)
-		usedGas += evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
+		usedGas += evm.Accesses.TouchAddressAndChargeGas(index, nil)
 	}
 
 	return usedGas, nil
@@ -207,7 +195,6 @@ func gasSStore(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySi
 			return params.SstoreResetGas + accessGas, nil
 		}
 	}
-
 	// The new gas metering is based on net gas costs (EIP-1283):
 	//
 	// 1. If current value equals new value (this is a no-op), 200 gas is deducted.
@@ -422,13 +409,6 @@ func gasCall(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize
 		transfersValue = !stack.Back(2).IsZero()
 		address        = common.Address(stack.Back(1).Bytes20())
 	)
-	if evm.accesses != nil {
-		// Charge witness costs
-		for i := trieUtils.VersionLeafKey; i <= trieUtils.CodeSizeLeafKey; i++ {
-			index := trieUtils.GetTreeKeyAccountLeaf(address[:], byte(i))
-			gas += evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
-		}
-	}
 
 	if evm.chainRules.IsEIP158 {
 		if transfersValue && evm.StateDB.Empty(address) {
@@ -456,6 +436,21 @@ func gasCall(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize
 	if gas, overflow = math.SafeAdd(gas, evm.callGasTemp); overflow {
 		return 0, ErrGasUintOverflow
 	}
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		if _, isPrecompile := evm.precompile(address); !isPrecompile {
+			gas, overflow = math.SafeAdd(gas, evm.Accesses.TouchAndChargeMessageCall(address.Bytes()[:]))
+			if overflow {
+				return 0, ErrGasUintOverflow
+			}
+		}
+		if transfersValue {
+			gas, overflow = math.SafeAdd(gas, evm.Accesses.TouchAndChargeValueTransfer(contract.Address().Bytes()[:], address.Bytes()[:]))
+			if overflow {
+				return 0, ErrGasUintOverflow
+			}
+		}
+	}
+
 	return gas, nil
 }
 
@@ -481,6 +476,15 @@ func gasCallCode(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memory
 	if gas, overflow = math.SafeAdd(gas, evm.callGasTemp); overflow {
 		return 0, ErrGasUintOverflow
 	}
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		address := common.Address(stack.Back(1).Bytes20())
+		if _, isPrecompile := evm.precompile(address); !isPrecompile {
+			gas, overflow = math.SafeAdd(gas, evm.Accesses.TouchAndChargeMessageCall(address.Bytes()))
+			if overflow {
+				return 0, ErrGasUintOverflow
+			}
+		}
+	}
 	return gas, nil
 }
 
@@ -497,6 +501,15 @@ func gasDelegateCall(evm *EVM, contract *Contract, stack *Stack, mem *Memory, me
 	if gas, overflow = math.SafeAdd(gas, evm.callGasTemp); overflow {
 		return 0, ErrGasUintOverflow
 	}
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		address := common.Address(stack.Back(1).Bytes20())
+		if _, isPrecompile := evm.precompile(address); !isPrecompile {
+			gas, overflow = math.SafeAdd(gas, evm.Accesses.TouchAndChargeMessageCall(address.Bytes()))
+			if overflow {
+				return 0, ErrGasUintOverflow
+			}
+		}
+	}
 	return gas, nil
 }
 
@@ -513,6 +526,15 @@ func gasStaticCall(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memo
 	if gas, overflow = math.SafeAdd(gas, evm.callGasTemp); overflow {
 		return 0, ErrGasUintOverflow
 	}
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		address := common.Address(stack.Back(1).Bytes20())
+		if _, isPrecompile := evm.precompile(address); !isPrecompile {
+			gas, overflow = math.SafeAdd(gas, evm.Accesses.TouchAndChargeMessageCall(address.Bytes()))
+			if overflow {
+				return 0, ErrGasUintOverflow
+			}
+		}
+	}
 	return gas, nil
 }
 
@@ -533,6 +555,12 @@ func gasSelfdestruct(evm *EVM, contract *Contract, stack *Stack, mem *Memory, me
 		}
 	}
 
+	if evm.chainConfig.IsCancun(evm.Context.BlockNumber) {
+		// TODO turn this into a panic (when we are sure this method
+		// will never execute when verkle is enabled)
+		log.Warn("verkle witness accumulation not supported for selfdestruct")
+	}
+
 	if !evm.StateDB.HasSuicided(contract.Address()) {
 		evm.StateDB.AddRefund(params.SelfdestructRefundGas)
 	}

core/vm/instructions.go

@@ -19,6 +19,7 @@ package vm
 import (
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/core/types"
+	"github.com/ethereum/go-ethereum/crypto"
 	"github.com/ethereum/go-ethereum/params"
 	trieUtils "github.com/ethereum/go-ethereum/trie/utils"
 	"github.com/holiman/uint256"
@@ -343,9 +344,10 @@ func opReturnDataCopy(pc *uint64, interpreter *EVMInterpreter, scope *ScopeConte
 func opExtCodeSize(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]byte, error) {
 	slot := scope.Stack.peek()
 	cs := uint64(interpreter.evm.StateDB.GetCodeSize(slot.Bytes20()))
-	if interpreter.evm.accesses != nil {
+	if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
 		index := trieUtils.GetTreeKeyCodeSize(slot.Bytes())
-		interpreter.evm.TxContext.Accesses.TouchAddress(index, uint256.NewInt(cs).Bytes())
+		statelessGas := interpreter.evm.Accesses.TouchAddressAndChargeGas(index, uint256.NewInt(cs).Bytes())
+		scope.Contract.UseGas(statelessGas)
 	}
 	slot.SetUint64(cs)
 	return nil, nil
@@ -368,63 +370,88 @@ func opCodeCopy(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([
 	if overflow {
 		uint64CodeOffset = 0xffffffffffffffff
 	}
-	uint64CodeEnd, overflow := new(uint256.Int).Add(&codeOffset, &length).Uint64WithOverflow()
-	if overflow {
-		uint64CodeEnd = 0xffffffffffffffff
-	}
-	if interpreter.evm.accesses != nil {
-		copyCodeFromAccesses(scope.Contract.Address(), uint64CodeOffset, uint64CodeEnd, memOffset.Uint64(), interpreter, scope)
-	} else {
-		codeCopy := getData(scope.Contract.Code, uint64CodeOffset, length.Uint64())
-		scope.Memory.Set(memOffset.Uint64(), length.Uint64(), codeCopy)
 
-		touchEachChunks(uint64CodeOffset, uint64CodeEnd, codeCopy, scope.Contract, interpreter.evm)
+	paddedCodeCopy, copyOffset, nonPaddedCopyLength := getDataAndAdjustedBounds(scope.Contract.Code, uint64CodeOffset, length.Uint64())
+	if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
+		touchEachChunksAndChargeGas(copyOffset, nonPaddedCopyLength, scope.Contract.Address().Bytes()[:], scope.Contract.Code, scope.Contract, interpreter.evm.Accesses)
 	}
-
+	scope.Memory.Set(memOffset.Uint64(), uint64(len(paddedCodeCopy)), paddedCodeCopy)
 	return nil, nil
 }
 
-// Helper function to touch every chunk in a code range
-func touchEachChunks(start, end uint64, code []byte, contract *Contract, evm *EVM) {
-	for chunk := start / 31; chunk <= end/31 && chunk <= uint64(len(code))/31; chunk++ {
-		index := trieUtils.GetTreeKeyCodeChunk(contract.Address().Bytes(), uint256.NewInt(chunk))
-		count := uint64(0)
-		end := (chunk + 1) * 31
+// touchEachChunksAndChargeGas is a helper function to touch every chunk in a code range and charge witness gas costs
+func touchEachChunksAndChargeGas(offset, size uint64, address []byte, code []byte, contract AnalyzedContract, accesses *types.AccessWitness) uint64 {
+	// note that in the case where the copied code is outside the range of the
+	// contract code but touches the last leaf with contract code in it,
+	// we don't include the last leaf of code in the AccessWitness.  The
+	// reason that we do not need the last leaf is the account's code size
+	// is already in the AccessWitness so a stateless verifier can see that
+	// the code from the last leaf is not needed.
+	if contract != nil && (size == 0 || offset > uint64(len(code))) {
+		return 0
+	}
+	var (
+		statelessGasCharged uint64
+		startLeafOffset     uint64
+		endLeafOffset       uint64
+		startOffset         uint64
+		endOffset           uint64
+		numLeaves           uint64
+		index               [32]byte
+	)
+	// startLeafOffset, endLeafOffset is the evm code offset of the first byte in the first leaf touched
+	// and the evm code offset of the last byte in the last leaf touched
+	startOffset = offset - (offset % 31)
+	if contract != nil && startOffset+size > uint64(len(code)) {
+		endOffset = uint64(len(code))
+	} else {
+		endOffset = startOffset + size
+	}
+	endLeafOffset = endOffset + (endOffset % 31)
+	numLeaves = (endLeafOffset - startLeafOffset) / 31
+	chunkOffset := new(uint256.Int)
+	treeIndex := new(uint256.Int)
 
+	for i := 0; i < int(numLeaves); i++ {
+		chunkOffset.Add(trieUtils.CodeOffset, uint256.NewInt(uint64(i)))
+		treeIndex.Div(chunkOffset, trieUtils.VerkleNodeWidth)
+		var subIndex byte
+		subIndexMod := chunkOffset.Mod(chunkOffset, trieUtils.VerkleNodeWidth).Bytes()
+		if len(subIndexMod) == 0 {
+			subIndex = 0
+		} else {
+			subIndex = subIndexMod[0]
+		}
+		treeKey := trieUtils.GetTreeKey(address, treeIndex, subIndex)
+		copy(index[0:31], treeKey)
+		index[31] = subIndex
+
+		var value []byte
+		if len(code) > 0 {
+			// the offset into the leaf that the first PUSH occurs
+			var firstPushOffset uint64 = 0
 			// Look for the first code byte (i.e. no pushdata)
-		for ; count < 31 && end+count < uint64(len(contract.Code)) && !contract.IsCode(chunk*31+count); count++ {
+			for ; firstPushOffset < 31 && firstPushOffset+uint64(i)*31 < uint64(len(code)) && !contract.IsCode(uint64(i)*31+firstPushOffset); firstPushOffset++ {
 			}
-		var value [32]byte
-		value[0] = byte(count)
-		if end > uint64(len(code)) {
-			end = uint64(len(code))
+			curEnd := (uint64(i) + 1) * 31
+			if curEnd > endOffset {
+				curEnd = endOffset
 			}
-		copy(value[1:], code[chunk*31:end])
-		evm.Accesses.TouchAddress(index, value[:])
+			valueSize := curEnd - (uint64(i) * 31)
+			value = make([]byte, 32, 32)
+			value[0] = byte(firstPushOffset)
+
+			copy(value[1:valueSize+1], code[i*31:curEnd])
+			if valueSize < 31 {
+				padding := make([]byte, 31-valueSize, 31-valueSize)
+				copy(value[valueSize+1:], padding)
 			}
 		}
 
-// copyCodeFromAccesses perform codecopy from the witness, not from the db.
-func copyCodeFromAccesses(addr common.Address, codeOffset, codeEnd, memOffset uint64, in *EVMInterpreter, scope *ScopeContext) {
-	chunk := codeOffset / 31
-	endChunk := codeEnd / 31
-	start := codeOffset % 31 // start inside the first code chunk
-	offset := uint64(0)      // memory offset to write to
-	// XXX uint64 overflow in condition check
-	for end := uint64(31); chunk < endChunk; chunk, start = chunk+1, 0 {
-		// case of the last chunk: figure out how many bytes need to
-		// be extracted from the last chunk.
-		if chunk+1 == endChunk {
-			end = codeEnd % 31
+		statelessGasCharged += accesses.TouchAddressAndChargeGas(index[:], value)
 	}
 
-		// TODO make a version of GetTreeKeyCodeChunk without the bigint
-		index := common.BytesToHash(trieUtils.GetTreeKeyCodeChunk(addr[:], uint256.NewInt(chunk)))
-		h := in.evm.accesses[index]
-		//in.evm.Accesses.TouchAddress(index.Bytes(), h[1+start:1+end])
-		scope.Memory.Set(memOffset+offset, end-start, h[1+start:end])
-		offset += 31 - start
-	}
+	return statelessGasCharged
 }
 
 func opExtCodeCopy(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]byte, error) {
@@ -439,18 +466,16 @@ func opExtCodeCopy(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext)
 	if overflow {
 		uint64CodeOffset = 0xffffffffffffffff
 	}
-	uint64CodeEnd, overflow := new(uint256.Int).Add(&codeOffset, &length).Uint64WithOverflow()
-	if overflow {
-		uint64CodeEnd = 0xffffffffffffffff
-	}
 	addr := common.Address(a.Bytes20())
-	if interpreter.evm.accesses != nil {
-		copyCodeFromAccesses(addr, uint64CodeOffset, uint64CodeEnd, memOffset.Uint64(), interpreter, scope)
+	if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
+		code := interpreter.evm.StateDB.GetCode(addr)
+		paddedCodeCopy, copyOffset, nonPaddedCopyLength := getDataAndAdjustedBounds(code, uint64CodeOffset, length.Uint64())
+		cb := codeBitmap(code)
+		touchEachChunksAndChargeGas(copyOffset, nonPaddedCopyLength, addr[:], code, &cb, interpreter.evm.Accesses)
+		scope.Memory.Set(memOffset.Uint64(), length.Uint64(), paddedCodeCopy)
 	} else {
 		codeCopy := getData(interpreter.evm.StateDB.GetCode(addr), uint64CodeOffset, length.Uint64())
 		scope.Memory.Set(memOffset.Uint64(), length.Uint64(), codeCopy)
-
-		touchEachChunks(uint64CodeOffset, uint64CodeEnd, codeCopy, scope.Contract, interpreter.evm)
 	}
 
 	return nil, nil
@@ -579,10 +604,11 @@ func opSload(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]by
 	hash := common.Hash(loc.Bytes32())
 	val := interpreter.evm.StateDB.GetState(scope.Contract.Address(), hash)
 	loc.SetBytes(val.Bytes())
-	// Get the initial value as it might not be present
 
+	if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
 		index := trieUtils.GetTreeKeyStorageSlot(scope.Contract.Address().Bytes(), loc)
-	interpreter.evm.TxContext.Accesses.TouchAddress(index, val.Bytes())
+		interpreter.evm.Accesses.TouchAddressAndChargeGas(index, val.Bytes())
+	}
 	return nil, nil
 }
 
@@ -642,6 +668,13 @@ func opCreate(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]b
 		input        = scope.Memory.GetCopy(int64(offset.Uint64()), int64(size.Uint64()))
 		gas          = scope.Contract.Gas
 	)
+	if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
+		contractAddress := crypto.CreateAddress(scope.Contract.Address(), interpreter.evm.StateDB.GetNonce(scope.Contract.Address()))
+		statelessGas := interpreter.evm.Accesses.TouchAndChargeContractCreateInit(contractAddress.Bytes()[:])
+		if !tryConsumeGas(&gas, statelessGas) {
+			return nil, ErrExecutionReverted
+		}
+	}
 	if interpreter.evm.chainRules.IsEIP150 {
 		gas -= gas / 64
 	}
@@ -684,6 +717,14 @@ func opCreate2(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]
 		input        = scope.Memory.GetCopy(int64(offset.Uint64()), int64(size.Uint64()))
 		gas          = scope.Contract.Gas
 	)
+	if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
+		codeAndHash := &codeAndHash{code: input}
+		contractAddress := crypto.CreateAddress2(scope.Contract.Address(), salt.Bytes32(), codeAndHash.Hash().Bytes())
+		statelessGas := interpreter.evm.Accesses.TouchAndChargeContractCreateInit(contractAddress.Bytes()[:])
+		if !tryConsumeGas(&gas, statelessGas) {
+			return nil, ErrExecutionReverted
+		}
+	}
 
 	// Apply EIP150
 	gas -= gas / 64
@@ -907,9 +948,11 @@ func opPush1(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]by
 	*pc += 1
 	if *pc < codeLen {
 		scope.Stack.push(integer.SetUint64(uint64(scope.Contract.Code[*pc])))
+
+		if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) && *pc%31 == 0 {
 			// touch next chunk if PUSH1 is at the boundary. if so, *pc has
 			// advanced past this boundary.
-		if *pc%31 == 0 {
+
 			// touch push data by adding the last byte of the pushdata
 			var value [32]byte
 			chunk := *pc / 31
@@ -924,7 +967,8 @@ func opPush1(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]by
 			}
 			copy(value[1:], scope.Contract.Code[chunk*31:endMin])
 			index := trieUtils.GetTreeKeyCodeChunk(scope.Contract.Address().Bytes(), uint256.NewInt(chunk))
-			interpreter.evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
+			statelessGas := interpreter.evm.Accesses.TouchAddressAndChargeGas(index, nil)
+			scope.Contract.UseGas(statelessGas)
 		}
 	} else {
 		scope.Stack.push(integer.Clear())
@@ -947,43 +991,15 @@ func makePush(size uint64, pushByteSize int) executionFunc {
 			endMin = startMin + pushByteSize
 		}
 
+		if interpreter.evm.chainConfig.IsCancun(interpreter.evm.Context.BlockNumber) {
+			statelessGas := touchEachChunksAndChargeGas(uint64(startMin), uint64(pushByteSize), scope.Contract.Address().Bytes()[:], scope.Contract.Code, scope.Contract, interpreter.evm.Accesses)
+			scope.Contract.UseGas(statelessGas)
+		}
+
 		integer := new(uint256.Int)
 		scope.Stack.push(integer.SetBytes(common.RightPadBytes(
 			scope.Contract.Code[startMin:endMin], pushByteSize)))
 
-		// touch push data by adding the last byte of the pushdata
-		var value [32]byte
-		chunk := uint64(endMin-1) / 31
-		count := uint64(0)
-		// Look for the first code byte (i.e. no pushdata)
-		for ; count < 31 && !scope.Contract.IsCode(chunk*31+count); count++ {
-		}
-		value[0] = byte(count)
-		copy(value[1:], scope.Contract.Code[chunk*31:endMin])
-		index := trieUtils.GetTreeKeyCodeChunk(scope.Contract.Address().Bytes(), uint256.NewInt(chunk))
-		interpreter.evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
-
-		// in the case of PUSH32, the end data might be two chunks away,
-		// so also get the middle chunk. There is a boundary condition
-		// check (endMin > 2) in the case the code is a single PUSH32
-		// insctruction, whose immediate are just 0s.
-		if pushByteSize == 32 && endMin > 2 {
-			chunk = uint64(endMin-2) / 31
-			count = uint64(0)
-			// Look for the first code byte (i.e. no pushdata)
-			for ; count < 31 && !scope.Contract.IsCode(chunk*31+count); count++ {
-			}
-			value[0] = byte(count)
-			end := (chunk + 1) * 31
-			if end > uint64(len(scope.Contract.Code)) {
-				end = uint64(len(scope.Contract.Code))
-			}
-			copy(value[1:], scope.Contract.Code[chunk*31:end])
-			index := trieUtils.GetTreeKeyCodeChunk(scope.Contract.Address().Bytes(), uint256.NewInt(chunk))
-			interpreter.evm.TxContext.Accesses.TouchAddressAndChargeGas(index, nil)
-
-		}
-
 		*pc += size
 		return nil, nil
 	}

core/vm/interface.go

@@ -47,6 +47,9 @@ type StateDB interface {
 	GetState(common.Address, common.Hash) common.Hash
 	SetState(common.Address, common.Hash, common.Hash)
 
+	GetBalanceLittleEndian(address common.Address) []byte
+	GetNonceLittleEndian(address common.Address) []byte
+
 	Suicide(common.Address) bool
 	HasSuicided(common.Address) bool
 

core/vm/interpreter.go

@@ -17,15 +17,12 @@
 package vm
 
 import (
-	"errors"
 	"hash"
 	"sync/atomic"
 
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/common/math"
 	"github.com/ethereum/go-ethereum/log"
-	trieUtils "github.com/ethereum/go-ethereum/trie/utils"
-	"github.com/holiman/uint256"
 )
 
 // Config are the configuration options for the Interpreter
@@ -194,51 +191,16 @@ func (in *EVMInterpreter) Run(contract *Contract, input []byte, readOnly bool) (
 			logged, pcCopy, gasCopy = false, pc, contract.Gas
 		}
 
+		if in.evm.ChainConfig().IsCancun(in.evm.Context.BlockNumber) && !contract.IsDeployment {
 			// if the PC ends up in a new "page" of verkleized code, charge the
 			// associated witness costs.
-		inWitness := false
-		var codePage common.Hash
-		if in.evm.chainRules.IsCancun {
-			index := trieUtils.GetTreeKeyCodeChunk(contract.Address().Bytes(), uint256.NewInt(pc/31))
-
-			var value [32]byte
-			if in.evm.accesses != nil {
-				codePage, inWitness = in.evm.accesses[common.BytesToHash(index)]
-				// Return an error if we're in stateless mode
-				// and the code isn't in the witness. It means
-				// that if code is read beyond the actual code
-				// size, pages of 0s need to be added to the
-				// witness.
-				if !inWitness {
-					return nil, errors.New("code chunk missing from proof")
-				}
-				copy(value[:], codePage[:])
-			} else {
-				// Calculate the chunk
-				chunk := pc / 31
-				end := (chunk + 1) * 31
-				if end >= uint64(len(contract.Code)) {
-					end = uint64(len(contract.Code))
-				}
-				count := uint64(0)
-				// Look for the first code byte (i.e. no pushdata)
-				for ; chunk*31+count < end && count < 31 && !contract.IsCode(chunk*31+count); count++ {
-				}
-				value[0] = byte(count)
-				copy(value[1:], contract.Code[chunk*31:end])
-			}
-			contract.Gas -= in.evm.TxContext.Accesses.TouchAddressAndChargeGas(index, value[:])
+			contract.Gas -= touchEachChunksAndChargeGas(pc, 1, contract.Address().Bytes()[:], contract.Code, contract, in.evm.TxContext.Accesses)
 		}
 
-		if inWitness {
-			// Get the op from the tree, skipping the header byte
-			op = OpCode(codePage[1+pc%31])
-		} else {
+		// TODO how can we tell if we are in stateless mode here and need to get the op from the witness
 		// If we are in witness mode, then raise an error
 		op = contract.GetOp(pc)
 
-		}
-
 		// Get the operation from the jump table and validate the stack to ensure there are
 		// enough stack items available to perform the operation.
 		operation := in.cfg.JumpTable[op]

eth/backend.go

@@ -56,6 +56,7 @@ import (
 	"github.com/ethereum/go-ethereum/params"
 	"github.com/ethereum/go-ethereum/rlp"
 	"github.com/ethereum/go-ethereum/rpc"
+	"github.com/gballet/go-verkle"
 )
 
 // Config contains the configuration options of the ETH protocol.
@@ -139,6 +140,13 @@ func New(stack *node.Node, config *ethconfig.Config) (*Ethereum, error) {
 	}
 	log.Info("Initialised chain configuration", "config", chainConfig)
 
+	// Start the precomputation of Lagrange points
+	// if this config supports verkle trees.
+	if chainConfig.CancunBlock != nil {
+		log.Info("Detected the use of verkle trees, rebuilding the cache")
+		verkle.GetConfig()
+	}
+
 	if err := pruner.RecoverPruning(stack.ResolvePath(""), chainDb, stack.ResolvePath(config.TrieCleanCacheJournal)); err != nil {
 		log.Error("Failed to recover state", "error", err)
 	}

go.mod

@@ -16,6 +16,7 @@ require (
 	github.com/cespare/cp v0.1.0
 	github.com/cloudflare/cloudflare-go v0.14.0
 	github.com/consensys/gnark-crypto v0.4.1-0.20210426202927-39ac3d4b3f1f
+	github.com/crate-crypto/go-ipa v0.0.0-20220120174240-fe21866d2ad5
 	github.com/davecgh/go-spew v1.1.1
 	github.com/deckarep/golang-set v0.0.0-20180603214616-504e848d77ea
 	github.com/deepmap/oapi-codegen v1.8.2 // indirect
@@ -25,7 +26,7 @@ require (
 	github.com/fatih/color v1.7.0
 	github.com/fjl/memsize v0.0.0-20190710130421-bcb5799ab5e5
 	github.com/gballet/go-libpcsclite v0.0.0-20190607065134-2772fd86a8ff
-	github.com/gballet/go-verkle v0.0.0-20211108173141-3d812b8722d3 // indirect
+	github.com/gballet/go-verkle v0.0.0-20220121105610-351986d619a8
 	github.com/go-ole/go-ole v1.2.1 // indirect
 	github.com/go-stack/stack v1.8.0
 	github.com/golang/protobuf v1.4.3
@@ -65,7 +66,7 @@ require (
 	golang.org/x/crypto v0.0.0-20210322153248-0c34fe9e7dc2
 	golang.org/x/net v0.0.0-20210805182204-aaa1db679c0d // indirect
 	golang.org/x/sync v0.0.0-20210220032951-036812b2e83c
-	golang.org/x/sys v0.0.0-20211112143042-c6105e7cf70d
+	golang.org/x/sys v0.0.0-20220114195835-da31bd327af9
 	golang.org/x/text v0.3.6
 	golang.org/x/time v0.0.0-20210220033141-f8bda1e9f3ba
 	gopkg.in/natefinch/npipe.v2 v2.0.0-20160621034901-c1b8fa8bdcce

go.sum

@@ -104,8 +104,15 @@ github.com/consensys/bavard v0.1.8-0.20210406032232-f3452dc9b572/go.mod h1:Bpd0/
 github.com/consensys/gnark-crypto v0.4.1-0.20210426202927-39ac3d4b3f1f h1:C43yEtQ6NIf4ftFXD/V55gnGFgPbMQobd//YlnLjUJ8=
 github.com/consensys/gnark-crypto v0.4.1-0.20210426202927-39ac3d4b3f1f/go.mod h1:815PAHg3wvysy0SyIqanF8gZ0Y1wjk/hrDHD/iT88+Q=
 github.com/cpuguy83/go-md2man/v2 v2.0.0-20190314233015-f79a8a8ca69d/go.mod h1:maD7wRr/U5Z6m/iR4s+kqSMx2CaBsrgA7czyZG/E6dU=
-github.com/crate-crypto/go-ipa v0.0.0-20211107182441-1aeb67f49de7 h1:P6yxenBOOu4RF26bRLiWG+zrwQ1kPAaz71sDmX6b76I=
 github.com/crate-crypto/go-ipa v0.0.0-20211107182441-1aeb67f49de7/go.mod h1:gFnFS95y8HstDP6P9pPwzrxOOC5TRDkwbM+ao15ChAI=
+github.com/crate-crypto/go-ipa v0.0.0-20211211194659-8730b6787450 h1:FW8SSFr58vgCbvNAWHUgigf6BYG1uIcwgZA8z539RLE=
+github.com/crate-crypto/go-ipa v0.0.0-20211211194659-8730b6787450/go.mod h1:gFnFS95y8HstDP6P9pPwzrxOOC5TRDkwbM+ao15ChAI=
+github.com/crate-crypto/go-ipa v0.0.0-20211223165939-ab3f49447206 h1:nMTTM1b+4WtWrb43nmTUV/FJz7M0M2g5fioLmd4QzUQ=
+github.com/crate-crypto/go-ipa v0.0.0-20211223165939-ab3f49447206/go.mod h1:gFnFS95y8HstDP6P9pPwzrxOOC5TRDkwbM+ao15ChAI=
+github.com/crate-crypto/go-ipa v0.0.0-20220114181434-991b62f9b1da h1:2luwsOSyUPVE67DmD7s2nKM+JbxaRuOCu6Y82qBTdnI=
+github.com/crate-crypto/go-ipa v0.0.0-20220114181434-991b62f9b1da/go.mod h1:gFnFS95y8HstDP6P9pPwzrxOOC5TRDkwbM+ao15ChAI=
+github.com/crate-crypto/go-ipa v0.0.0-20220120174240-fe21866d2ad5 h1:BsLconJDsODyRO72xjBHhxZKPCuY/kBgZdPeV4GFNlU=
+github.com/crate-crypto/go-ipa v0.0.0-20220120174240-fe21866d2ad5/go.mod h1:gFnFS95y8HstDP6P9pPwzrxOOC5TRDkwbM+ao15ChAI=
 github.com/creack/pty v1.1.9/go.mod h1:oKZEueFk5CKHvIhNR5MUki03XCEU+Q6VDXinZuGJ33E=
 github.com/cyberdelia/templates v0.0.0-20141128023046-ca7fffd4298c/go.mod h1:GyV+0YP4qX0UQ7r2MoYZ+AvYDp12OF5yg4q8rGnyNh4=
 github.com/dave/jennifer v1.2.0/go.mod h1:fIb+770HOpJ2fmN9EPPKOqm1vMGhB+TwXKMZhrIygKg=
@@ -144,8 +151,18 @@ github.com/fsnotify/fsnotify v1.4.9 h1:hsms1Qyu0jgnwNXIxa+/V/PDsU6CfLf6CNO8H7IWo
 github.com/fsnotify/fsnotify v1.4.9/go.mod h1:znqG4EE+3YCdAaPaxE2ZRY/06pZUdp0tY4IgpuI1SZQ=
 github.com/gballet/go-libpcsclite v0.0.0-20190607065134-2772fd86a8ff h1:tY80oXqGNY4FhTFhk+o9oFHGINQ/+vhlm8HFzi6znCI=
 github.com/gballet/go-libpcsclite v0.0.0-20190607065134-2772fd86a8ff/go.mod h1:x7DCsMOv1taUwEWCzT4cmDeAkigA5/QCwUodaVOe8Ww=
-github.com/gballet/go-verkle v0.0.0-20211108173141-3d812b8722d3 h1:YuCllCO2PQ1U2RXeJBbWEd5LLJCk+Ha4FRo+j7reX78=
-github.com/gballet/go-verkle v0.0.0-20211108173141-3d812b8722d3/go.mod h1:BASlDXGXxlAP/xls4A48nC+QVn3jLiP0s4RTmMgh/IE=
+github.com/gballet/go-verkle v0.0.0-20211221174846-e7cddd97495c h1:d34wNrUBGD6s2OCWQd31nqjkPWt+YbXUm8FAJ+7+tHM=
+github.com/gballet/go-verkle v0.0.0-20211221174846-e7cddd97495c/go.mod h1:6hL9IP6wLByFGqj1VDbruVAjfa8DghWD96o8kuNMDCA=
+github.com/gballet/go-verkle v0.0.0-20220113152809-0c00dbeef550 h1:uyv9x+hIyWF6Jrlz9pg/PtIhQS/lPGwVl5Rkp04m/Ik=
+github.com/gballet/go-verkle v0.0.0-20220113152809-0c00dbeef550/go.mod h1:2ObZwG6QCVAzvnUrsezVfjEL28O+e1cSA9xV/PB7IME=
+github.com/gballet/go-verkle v0.0.0-20220119102938-379d70afb801 h1:XoZ7eOVOdDXeVz05t3hO4JtRWXYvZa8lGm9zoPhSyEc=
+github.com/gballet/go-verkle v0.0.0-20220119102938-379d70afb801/go.mod h1:e1m+0UuY3AFFTubxZZ3ePf4yO/rHMAeTb7udhUAJduk=
+github.com/gballet/go-verkle v0.0.0-20220119112812-69e1c35fb0e0 h1:OQ2MGbAcc9X/51/llMp1CozPwc3ryRyXSQ19E2mbI2k=
+github.com/gballet/go-verkle v0.0.0-20220119112812-69e1c35fb0e0/go.mod h1:e1m+0UuY3AFFTubxZZ3ePf4yO/rHMAeTb7udhUAJduk=
+github.com/gballet/go-verkle v0.0.0-20220119205306-b466d7bff5ba h1:iOhT1XFktDNN72Ly2GUI/UTj2dnA1qI7+kyYqdpSCCk=
+github.com/gballet/go-verkle v0.0.0-20220119205306-b466d7bff5ba/go.mod h1:e1m+0UuY3AFFTubxZZ3ePf4yO/rHMAeTb7udhUAJduk=
+github.com/gballet/go-verkle v0.0.0-20220121105610-351986d619a8 h1:6fW03c2tXGttQv1b3mt9zmcXw4/srV62DltEER5mp/U=
+github.com/gballet/go-verkle v0.0.0-20220121105610-351986d619a8/go.mod h1:e1m+0UuY3AFFTubxZZ3ePf4yO/rHMAeTb7udhUAJduk=
 github.com/getkin/kin-openapi v0.53.0/go.mod h1:7Yn5whZr5kJi6t+kShccXS8ae1APpYTW6yheSwk8Yi4=
 github.com/getkin/kin-openapi v0.61.0/go.mod h1:7Yn5whZr5kJi6t+kShccXS8ae1APpYTW6yheSwk8Yi4=
 github.com/ghodss/yaml v1.0.0/go.mod h1:4dBDuWmgqj2HViK6kFavaiC9ZROes6MMH2rRYeMEF04=
@@ -540,12 +557,12 @@ golang.org/x/sys v0.0.0-20210316164454-77fc1eacc6aa/go.mod h1:h1NjWce9XRLGQEsW7w
 golang.org/x/sys v0.0.0-20210324051608-47abb6519492/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210420205809-ac73e9fd8988/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210423082822-04245dca01da/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
-golang.org/x/sys v0.0.0-20210816183151-1e6c022a8912 h1:uCLL3g5wH2xjxVREVuAbP9JM5PPKjRbXKRa6IBjkzmU=
-golang.org/x/sys v0.0.0-20210816183151-1e6c022a8912/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20211020174200-9d6173849985/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20211107104306-e0b2ad06fe42/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
-golang.org/x/sys v0.0.0-20211112143042-c6105e7cf70d h1:jp6PtFmjL+vGsuzd86xYqaJGv6eXdLvmVGzVVLI6EPI=
-golang.org/x/sys v0.0.0-20211112143042-c6105e7cf70d/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20211216021012-1d35b9e2eb4e h1:fLOSk5Q00efkSvAm+4xcoXD+RRmLmmulPn5I3Y9F2EM=
+golang.org/x/sys v0.0.0-20211216021012-1d35b9e2eb4e/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20220114195835-da31bd327af9 h1:XfKQ4OlFl8okEOr5UvAqFRVj8pY/4yfcXrddB8qAbU0=
+golang.org/x/sys v0.0.0-20220114195835-da31bd327af9/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/term v0.0.0-20201117132131-f5c789dd3221/go.mod h1:Nr5EML6q2oocZ2LXRh80K7BxOlk5/8JxuGnuhpl+muw=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1 h1:v+OssWQX+hTHEmOBgwxdZxK4zHq3yOs8F9J7mk0PY8E=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=

miner/worker.go

@@ -1043,10 +1043,10 @@ func (w *worker) commit(uncles []*types.Header, interval func(), update bool, st
 		vtr := tr.(*trie.VerkleTrie)
 		// Generate the proof if we are using a verkle tree
 		p, err := vtr.ProveAndSerialize(s.Witness().Keys(), s.Witness().KeyVals())
-		w.current.header.VerkleProof = p
 		if err != nil {
 			return err
 		}
+		block.SetVerkleProof(p)
 	}
 	if w.isRunning() && !w.merger.TDDReached() {
 		if interval != nil {

miner/worker_test.go

@@ -116,7 +116,7 @@ type testWorkerBackend struct {
 	uncleBlock *types.Block
 }
 
-func newTestWorkerBackend(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine, db ethdb.Database, n int) *testWorkerBackend {
+func newTestWorkerBackend(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine, db ethdb.Database, n int, isVerkle bool) *testWorkerBackend {
 	var gspec = core.Genesis{
 		Config: chainConfig,
 		Alloc:  core.GenesisAlloc{testBankAddress: {Balance: testBankFunds}},
@@ -151,9 +151,17 @@ func newTestWorkerBackend(t *testing.T, chainConfig *params.ChainConfig, engine
 	if n > 0 {
 		parent = chain.GetBlockByHash(chain.CurrentBlock().ParentHash())
 	}
-	blocks, _ := core.GenerateChain(chainConfig, parent, engine, db, 1, func(i int, gen *core.BlockGen) {
+	var blocks []*types.Block
+
+	if isVerkle {
+		blocks, _ = core.GenerateVerkleChain(chainConfig, parent, engine, db, 1, func(i int, gen *core.BlockGen) {
 			gen.SetCoinbase(testUserAddress)
 		})
+	} else {
+		blocks, _ = core.GenerateChain(chainConfig, parent, engine, db, 1, func(i int, gen *core.BlockGen) {
+			gen.SetCoinbase(testUserAddress)
+		})
+	}
 
 	return &testWorkerBackend{
 		db:         db,
@@ -183,6 +191,22 @@ func (b *testWorkerBackend) newRandomUncle() *types.Block {
 	return blocks[0]
 }
 
+func (b *testWorkerBackend) newRandomVerkleUncle() *types.Block {
+	var parent *types.Block
+	cur := b.chain.CurrentBlock()
+	if cur.NumberU64() == 0 {
+		parent = b.chain.Genesis()
+	} else {
+		parent = b.chain.GetBlockByHash(b.chain.CurrentBlock().ParentHash())
+	}
+	blocks, _ := core.GenerateVerkleChain(b.chain.Config(), parent, b.chain.Engine(), b.db, 1, func(i int, gen *core.BlockGen) {
+		var addr = make([]byte, common.AddressLength)
+		rand.Read(addr)
+		gen.SetCoinbase(common.BytesToAddress(addr))
+	})
+	return blocks[0]
+}
+
 func (b *testWorkerBackend) newRandomTx(creation bool) *types.Transaction {
 	var tx *types.Transaction
 	gasPrice := big.NewInt(10 * params.InitialBaseFee)
@@ -194,8 +218,8 @@ func (b *testWorkerBackend) newRandomTx(creation bool) *types.Transaction {
 	return tx
 }
 
-func newTestWorker(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine, db ethdb.Database, blocks int) (*worker, *testWorkerBackend) {
-	backend := newTestWorkerBackend(t, chainConfig, engine, db, blocks)
+func newTestWorker(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine, db ethdb.Database, blocks int, isVerkle bool) (*worker, *testWorkerBackend) {
+	backend := newTestWorkerBackend(t, chainConfig, engine, db, blocks, isVerkle)
 	backend.txPool.AddLocals(pendingTxs)
 	w := newWorker(testConfig, chainConfig, engine, backend, new(event.TypeMux), nil, false, consensus.NewMerger(rawdb.NewMemoryDatabase()))
 	w.setEtherbase(testBankAddress)
@@ -226,7 +250,7 @@ func testGenerateBlockAndImport(t *testing.T, isClique bool) {
 	}
 
 	chainConfig.LondonBlock = big.NewInt(0)
-	w, b := newTestWorker(t, chainConfig, engine, db, 0)
+	w, b := newTestWorker(t, chainConfig, engine, db, 0, false)
 	defer w.close()
 
 	// This test chain imports the mined blocks.
@@ -265,6 +289,59 @@ func testGenerateBlockAndImport(t *testing.T, isClique bool) {
 	}
 }
 
+func TestGenerateBlocksAndImportVerkle(t *testing.T) {
+	var (
+		engine      consensus.Engine
+		chainConfig *params.ChainConfig
+		db          = rawdb.NewMemoryDatabase()
+	)
+	chainConfig = params.VerkleChainConfig
+	engine = ethash.NewFaker()
+
+	w, b := newTestWorker(t, chainConfig, engine, db, 0, true)
+	defer w.close()
+
+	// This test chain imports the mined blocks.
+	db2 := rawdb.NewMemoryDatabase()
+	b.genesis.MustCommit(db2)
+	chain, _ := core.NewBlockChain(db2, nil, b.chain.Config(), engine, vm.Config{}, nil, nil)
+	defer chain.Stop()
+
+	// Ignore empty commit here for less noise.
+	/*
+	w.skipSealHook = func(task *task) bool {
+		return len(task.receipts) == 0
+	}
+	*/
+
+	// Wait for mined blocks.
+	sub := w.mux.Subscribe(core.NewMinedBlockEvent{})
+	defer sub.Unsubscribe()
+
+	// Start mining!
+	w.start()
+
+	for i := 0; i < 5; i++ {
+		b.txPool.AddLocal(b.newRandomTx(true))
+		b.txPool.AddLocal(b.newRandomTx(false))
+		w.postSideBlock(core.ChainSideEvent{Block: b.newRandomVerkleUncle()})
+		w.postSideBlock(core.ChainSideEvent{Block: b.newRandomVerkleUncle()})
+
+		select {
+		case ev := <-sub.Chan():
+			block := ev.Data.(core.NewMinedBlockEvent).Block
+			if block.Header().VerkleProof == nil {
+				t.Fatalf("expected Verkle proof in mined block header")
+			}
+			if _, err := chain.InsertChain([]*types.Block{block}); err != nil {
+				t.Fatalf("failed to insert new mined block %d: %v", block.NumberU64(), err)
+			}
+		case <-time.After(3 * time.Second): // Worker needs 1s to include new changes.
+			t.Fatalf("timeout")
+		}
+	}
+}
+
 func TestEmptyWorkEthash(t *testing.T) {
 	testEmptyWork(t, ethashChainConfig, ethash.NewFaker())
 }
@@ -275,7 +352,7 @@ func TestEmptyWorkClique(t *testing.T) {
 func testEmptyWork(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine) {
 	defer engine.Close()
 
-	w, _ := newTestWorker(t, chainConfig, engine, rawdb.NewMemoryDatabase(), 0)
+	w, _ := newTestWorker(t, chainConfig, engine, rawdb.NewMemoryDatabase(), 0, false)
 	defer w.close()
 
 	var (
@@ -321,7 +398,7 @@ func TestStreamUncleBlock(t *testing.T) {
 	ethash := ethash.NewFaker()
 	defer ethash.Close()
 
-	w, b := newTestWorker(t, ethashChainConfig, ethash, rawdb.NewMemoryDatabase(), 1)
+	w, b := newTestWorker(t, ethashChainConfig, ethash, rawdb.NewMemoryDatabase(), 1, false)
 	defer w.close()
 
 	var taskCh = make(chan struct{})
@@ -379,7 +456,7 @@ func TestRegenerateMiningBlockClique(t *testing.T) {
 func testRegenerateMiningBlock(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine) {
 	defer engine.Close()
 
-	w, b := newTestWorker(t, chainConfig, engine, rawdb.NewMemoryDatabase(), 0)
+	w, b := newTestWorker(t, chainConfig, engine, rawdb.NewMemoryDatabase(), 0, false)
 	defer w.close()
 
 	var taskCh = make(chan struct{})
@@ -439,7 +516,7 @@ func TestAdjustIntervalClique(t *testing.T) {
 func testAdjustInterval(t *testing.T, chainConfig *params.ChainConfig, engine consensus.Engine) {
 	defer engine.Close()
 
-	w, _ := newTestWorker(t, chainConfig, engine, rawdb.NewMemoryDatabase(), 0)
+	w, _ := newTestWorker(t, chainConfig, engine, rawdb.NewMemoryDatabase(), 0, false)
 	defer w.close()
 
 	w.skipSealHook = func(task *task) bool {

trie/utils/verkle.go

@@ -17,7 +17,8 @@
 package utils
 
 import (
-	"crypto/sha256"
+	"github.com/crate-crypto/go-ipa/bandersnatch/fr"
+	"github.com/gballet/go-verkle"
 
 	"github.com/holiman/uint256"
 )
@@ -40,15 +41,23 @@ var (
 )
 
 func GetTreeKey(address []byte, treeIndex *uint256.Int, subIndex byte) []byte {
-	digest := sha256.New()
-	digest.Write(address)
-	treeIndexBytes := treeIndex.Bytes()
-	var payload [32]byte
-	copy(payload[:len(treeIndexBytes)], treeIndexBytes)
-	digest.Write(payload[:])
-	h := digest.Sum(nil)
-	h[31] = subIndex
-	return h
+	var poly [256]fr.Element
+	verkle.FromLEBytes(&poly[0], []byte{1})
+	verkle.FromLEBytes(&poly[0], []byte{2, 63})
+	verkle.FromLEBytes(&poly[1], address[:16])
+	verkle.FromLEBytes(&poly[2], address[16:])
+	var index [32]byte
+	copy(index[:], treeIndex.Bytes())
+	verkle.FromLEBytes(&poly[3], index[:16])
+	verkle.FromLEBytes(&poly[4], index[16:])
+	for i := 5; i < len(poly); i++ {
+		verkle.CopyFr(&poly[i], &verkle.FrZero)
+	}
+
+	ret := verkle.GetConfig().CommitToPoly(poly[:], 0)
+	retb := ret.Bytes()
+	return retb[:]
+
 }
 
 func GetTreeKeyAccountLeaf(address []byte, leaf byte) []byte {

trie/verkle.go

@@ -24,7 +24,6 @@ import (
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/core/types"
 	"github.com/ethereum/go-ethereum/ethdb"
-	"github.com/ethereum/go-ethereum/rlp"
 	"github.com/ethereum/go-ethereum/trie/utils"
 	"github.com/gballet/go-verkle"
 )
@@ -118,6 +117,16 @@ func (trie *VerkleTrie) Commit(onleaf LeafCallback) (common.Hash, int, error) {
 	flush := make(chan verkle.VerkleNode)
 	go func() {
 		trie.root.(*verkle.InternalNode).Flush(func(n verkle.VerkleNode) {
+			if onleaf != nil {
+				if leaf, isLeaf := n.(*verkle.LeafNode); isLeaf {
+					for i := 0; i < verkle.NodeWidth; i++ {
+						if leaf.Value(i) != nil {
+							comm := n.ComputeCommitment().Bytes()
+							onleaf(nil, nil, leaf.Value(i), common.BytesToHash(comm[:]))
+						}
+					}
+				}
+			}
 			flush <- n
 		})
 		close(flush)
@@ -135,7 +144,6 @@ func (trie *VerkleTrie) Commit(onleaf LeafCallback) (common.Hash, int, error) {
 		}
 	}
 
-	// XXX onleaf hasn't been called
 	return trie.Hash(), commitCount, nil
 }
 
@@ -171,33 +179,20 @@ type KeyValuePair struct {
 	Value []byte
 }
 
-type verkleproof struct {
-	Proof *verkle.Proof
-
-	Cis     []*verkle.Point
-	Indices []byte
-	Yis     []*verkle.Fr
-
-	Leaves []KeyValuePair
-}
-
 func (trie *VerkleTrie) ProveAndSerialize(keys [][]byte, kv map[common.Hash][]byte) ([]byte, error) {
-	proof, cis, indices, yis := verkle.MakeVerkleMultiProof(trie.root, keys)
-	vp := verkleproof{
-		Proof:   proof,
-		Cis:     cis,
-		Indices: indices,
-		Yis:     yis,
+	proof, _, _, _ := verkle.MakeVerkleMultiProof(trie.root, keys)
+	return verkle.SerializeProof(proof)
 }
-	for key, val := range kv {
-		var k [32]byte
-		copy(k[:], key[:])
-		vp.Leaves = append(vp.Leaves, KeyValuePair{
-			Key:   k[:],
-			Value: val,
-		})
+
+type set = map[string]struct{}
+
+func hasKey(s set, key []byte) bool {
+	_, ok := s[string(key)]
+	return ok
 }
-	return rlp.EncodeToBytes(vp)
+
+func addKey(s set, key []byte) {
+	s[string(key)] = struct{}{}
 }
 
 func DeserializeAndVerifyVerkleProof(serialized []byte) (map[common.Hash]common.Hash, error) {
@@ -212,17 +207,89 @@ func DeserializeAndVerifyVerkleProof(serialized []byte) (map[common.Hash]common.
 	return leaves, nil
 }
 
-func deserializeVerkleProof(proof []byte) (*verkle.Proof, []*verkle.Point, []byte, []*verkle.Fr, map[common.Hash]common.Hash, error) {
-	var vp verkleproof
-	err := rlp.DecodeBytes(proof, &vp)
+func deserializeVerkleProof(serialized []byte) (*verkle.Proof, []*verkle.Point, []byte, []*verkle.Fr, map[common.Hash]common.Hash, error) {
+	var (
+		indices           []byte       // List of zis
+		yis               []*verkle.Fr // List of yis
+		seenIdx, seenComm set          // Mark when a zi/yi has already been seen in deserialization
+		others            set          // Mark when an "other" stem has been seen
+	)
+
+	proof, err := verkle.DeserializeProof(serialized)
 	if err != nil {
 		return nil, nil, nil, nil, nil, fmt.Errorf("verkle proof deserialization error: %w", err)
 	}
-	leaves := make(map[common.Hash]common.Hash, len(vp.Leaves))
-	for _, kvp := range vp.Leaves {
-		leaves[common.BytesToHash(kvp.Key)] = common.BytesToHash(kvp.Value)
+
+	for _, stem := range proof.PoaStems {
+		addKey(others, stem)
 	}
-	return vp.Proof, vp.Cis, vp.Indices, vp.Yis, leaves, nil
+
+	keyvals := make(map[common.Hash]common.Hash)
+	for i, key := range proof.Keys {
+		keyvals[common.BytesToHash(key)] = common.BytesToHash(proof.Values[i])
+	}
+
+	if len(proof.Keys) != len(proof.Values) {
+		return nil, nil, nil, nil, nil, fmt.Errorf("keys and values are of different length %d != %d", len(proof.Keys), len(proof.Values))
+	}
+	if len(proof.Keys) != len(proof.ExtStatus) {
+		return nil, nil, nil, nil, nil, fmt.Errorf("keys and values are of different length %d != %d", len(proof.Keys), len(proof.Values))
+	}
+
+	// Rebuild the tree, creating nodes in the lexicographic order of their path
+	lastcomm, lastpoa := 0, 0
+	root := verkle.NewStateless()
+	for i, es := range proof.ExtStatus {
+		depth := es & 0x1F
+		status := es >> 5
+		node := root
+		stem := proof.Keys[i]
+
+		// go over the stem's bytes, in order to rebuild the internal nodes
+		for j := byte(0); j < depth; j++ {
+			// Recurse into the tree that is being rebuilt
+			if node.Children()[stem[j]] == nil {
+				node.SetChild(int(stem[j]), verkle.NewStatelessWithCommitment(proof.Cs[lastcomm]))
+				lastcomm++
+			}
+
+			node = node.Children()[stem[j]].(*verkle.StatelessNode)
+
+			// if that zi hasn't been encountered yet, add it to
+			// the list of zis sorted by path.
+			if !hasKey(seenIdx, stem[:j]) {
+				addKey(seenIdx, stem[:j])
+				indices = append(indices, stem[j])
+			}
+
+			// same thing with a yi
+			if !hasKey(seenComm, stem[:j]) {
+				addKey(seenComm, stem[:j])
+				yis = append(yis, node.ComputeCommitment())
+			}
+		}
+
+		// Reached the end, add the extension-and-suffix tree
+		switch status {
+		case 0:
+			// missing stem, leave it as is
+			break
+		case 1:
+			// another stem is found, build it
+			node.SetStem(proof.PoaStems[lastpoa])
+			lastpoa++
+			break
+		case 2:
+			// stem is present
+			node.SetStem(stem[:31])
+			break
+		default:
+			return nil, nil, nil, nil, nil, fmt.Errorf("verkle proof deserialization error: invalid extension status %d", status)
+		}
+
+	}
+
+	return proof, proof.Cs, indices, yis, keyvals, nil
 }
 
 // Copy the values here so as to avoid an import cycle

trie/verkle_iterator.go

@@ -105,7 +105,7 @@ func (it *verkleNodeIterator) Next(descend bool) bool {
 		if err != nil {
 			panic(err)
 		}
-		it.current, err = verkle.ParseNode(data, len(it.stack)-1)
+		it.current, err = verkle.ParseNode(data, byte(len(it.stack)-1))
 		if err != nil {
 			panic(err)
 		}