This series “Smart Contract Patterns” will explore a number of these, diving into their origins, applications, and rationale. We’ll explore in-depth how traditional architecture & development principles translate into the world of smart contracts.

Each new pattern is a tool, one that can be used to aid you in building & maintaining decentralised applications.

Before we delve into these patterns, an extremely useful pre-requisite is a solid understanding of the EVM. Our previous series “EVM Deep Dives” explores the low-level implementation of the EVM and I would highly recommend reading that before starting.

Now let’s kick off the series with one of the most common patterns in smart contract development, “The Proxy”.

Subscribe now

History

Understanding the history behind a given “Smart Contract Pattern” is extremely valuable. It sheds light on why it emerged, the specific problem it solved, and the design trade-offs made along the way.

Why Does This Pattern Exist?

For every pattern, we should start with a simple question.

“Why?”.

Why was this pattern created and what problem did it solve?

For “The Proxy” the why came from the immutability of smart contracts. Contracts are immutable by design, which prevents any updates to the business logic once the contract is deployed. This raised an obvious question.

This question was initially solved with “contract migrations”. A new version of the contract would be deployed and all state and balances would be transferred to this new instance.

One obvious drawback of this was that the new deployment resulted in a new contract address. For applications integrated into wider ecosystems, it would require all third parties to also update their codebase to point at the new contract.

Another drawback was the operational complexity of transferring the state and balances to this new instance. Not only would this be very expensive from a gas perspective it would also be a very sensitive operation. Incorrectly updating the state of the new contract could break functionality and lead to security vulnerabilities.

The need for a simpler solution was apparent. How could we update the underlying logic of a contract without changing its address? How could we minimise the operational overhead?

From these questions “The Proxy Pattern” was formed.

The Original Proxy (The Delegate Proxy)

The original proxy, known as the delegate proxy used a few simple ideas to answer these questions.

First, we needed to separate the business logic and data storage into separate contracts. This was achieved with two contracts, “The Proxy Contract” for the data and “The Implementation Contract” (also known as the logic contract) for the business logic.

Next, we could utilise a delegate call from “The Proxy Contract” to access and use the business logic within “The Implementation Contract” in the context of “The Proxy’s” storage.

The fallback function within “The Proxy” would facilitate this delegate call. A fallback function is a function that executes when a non-existent function is called on the contract. This allows the contract to respond to arbitrary Ethereum transactions.

With this, we could access function signatures not defined in “The Proxy” and still use the “The Proxy” storage.

If you are unfamiliar with delegate call please refer to this article for an in-depth overview, a deep understanding of it is essential to understand the proxy pattern.

In short delegate call allowed us to use “The Implementation Contract” in the same way a Web2 app uses a library. This separation allows “The Proxy” to upgrade its business logic akin to updating a package version.

The image below shows these 2 contracts and a function call from a user to them. First with the v1 implementation and then with the v2 implementation.

The Delegate Proxy was a big step forward however it was not without its challenges

Problems With The Delegate Proxy

Several issues came from the new proxy architecture. Two key ones focused on collisions between the 2 contracts. Storage slot collisions and function signature collisions.

Storage Collisions

In Solidity, the storage layout is determined by the order of your variable declarations in your code. Alterations to this ordering during upgrades can lead to storage collisions - a critical issue where data is incorrectly read or overwritten.

If you’re unfamiliar with storage slots read this article for a deep dive.

Broadly these collisions could be broken into 2 types:

• Storage collisions between “The Proxy” and “The Implementation”

• Storage collisions between different versions of “The Implementation”

Proxy and Implementation Storage Collisions

The proxy pattern requires “The Proxy” and its “Implementation Contract” to share the same storage layout. If there's a mismatch it can lead to storage collisions.

A storage collision is where 2 different variables are assigned the same storage slot across 2 contracts. This can lead to a variable being incorrectly read or overwritten.

Say “The Proxy” has varA at storage slot 0 while “The Implementation” has varB at storage slot 0. You can see how this could cause issues when a delegate call is made from “The Proxy” to “The Implementation”.

This isn’t an unlikely scenario, “The Proxy” will likely have variables that “The Implementation” does not. For example, “The Proxy” needs to store the address of “The Implementation” contract at some storage slot.

It’s key that “The Implementation” contract doesn’t overwrite the implementation address slot, if it does it will have effectively broken “The Proxy”.

This was such a common problem that a standard, ERC-1967, was created.

This defined a specific storage slot (one guaranteed to be never allocated by a compiler) where “The Implementation” address should be stored.

Implementation Version Storage Collisions

When upgrading “The Implementation” contract, changes in the order or types of state variables can cause storage slots to be reassigned.

Take a look at the below example.

Original Contract Storage Layout:

address owner; // Slot 0
uint256 totalSupply; // Slot 1
mapping(address => uint256) balances; // Slot 2 (starting point of a dynamic mapping)


Upgraded Contract: 

uint256 rewardMultiplier; // Now at Slot 0
address owner; // Moved to Slot 1
uint256 totalSupply; // Moved to Slot 2
mapping(address => uint256) balances; // Slot 3 (starting point of the dynamic mapping has shifted)

It’s easy to see how this slot reassignment could cause havoc for this contract and open many security vulnerabilities. One obvious example is the moving of the owner variable to a new slot.

If the contract logic attempts to access “owner” using its original slot 0, it would mistakenly interact with “rewardMultiplier” instead.

Care needs to be taken when upgrading “The Implementation” to ensure the storage layout isn’t compromised.

Function Collisions

Another major issue was function signature collisions.

To understand function signature collisions first you must understand how the EVM interprets function calls to a solidity contract.

An in-depth overview of this can be found here if you need a refresher.

In summary, function selection within a contract is determined by the 4-byte function signature. These are derived from the name of the function and its input types.

Collisions of these signatures can occur, leading to ambiguity in function calls and security vulnerabilities. Let’s highlight one of these vulnerabilities.

Proxy Contract:

function collate_propagate_storage(bytes16) external {
        implementation.delegatecall(abi.encodeWithSignature(
            "transfer(address,uint256)", proxyOwner, 1000
        ));
}


Implementation Contract: 

function burn(uint256 value) public virtual {
        _burn(_msgSender(), value);
}

function transfer(address to, uint256 value) public virtual returns (bool) {
        address owner = _msgSender();
        _transfer(owner, to, value);
        return true;
}

The above highlights certain functions in “The Proxy” and “The Implementation” contracts.

The setup for this vulnerability is that an untrustworthy proxy is pointing to a trusted implementation contract.

This untrustworthy proxy has implemented a new function collate_propagate_storage(bytes16) in “The Proxy” contract.

A user comes along to interact with “The Proxy”, let’s say they heard there was an associated airdrop if they used it. They focus on checking “The Implementation” to verify it isn’t doing anything malicious, this is where all business logic is located.

“The Implementation” uses a standard OpenZepplin contract which is trusted and has been thoroughly tested. They notice collate_propagate_storage(bytes16) in “The Proxy” but think nothing of it. It is not the function or code they will be interacting with.

The user now satisfied calls burn(1) on “The Proxy” to burn one of their tokens. When the transaction lands on-chain they see that instead of burning 1 token they have transferred 1000 tokens to another unknown account.

What just happened?

Let’s look at the function signatures of burn and collate_propagate_storage.

• burn(uint256) = 0x42966c68

• collate_propagate_storage(bytes16) = 0x42966c68

You can check these out for yourself here, paste the function name and input types above into the keccak256 simulator and see the resulting hash.

Note that the full hash is different but it doesn’t matter since we only need the first 4 bytes to match.

When the user called burn(uint256) the following occurred:

• The EVM didn’t see a call to burn(uint256) it saw a function call to 0x42966c68.

• Since this function signature existed in “The Proxy” as collate_propagate_storage(bytes16) the call wasn’t passed to the fallback function.

• Instead, it was passed to collate_propagate_storage(bytes16). This in turn called a transfer of 1000 tokens to the proxyOwner.

(See here for a deeper breakdown by tincho).

While the example above highlights an exploit the same is true when “The Proxy” and “The Implementation” have functions with identical signatures for non-malicous valid reasons.

Say both contracts have an updateSettings() function. When a user tries to invoke this function how does the contract know which function you are intending to call, “The Proxy” or “The Implementation”?

This ambiguity can lead to unintended errors or even malicious exploits.

It was such a serious problem that a new proxy was created to solve this exact issue, the transparent proxy.

The Transparent Proxy

The core idea of the transparent proxy was to have 2 different execution paths for admin and non-admin users.

If the admin was calling the contract “The Proxy” functions would be available. For anyone else, all calls would be delegated to “The Implementation” via the fallback even if there was a matching function signature.

This removed the ambiguity, admins could interact with “The Proxy” functions and non-admins could only interact with the “The Implementation” functions.

One drawback of this setup was that normal users would no longer be able to access the read methods on “The Proxy”. For example, accessing the getter for “The Implementation” address.

Instead, they would have to use web3.eth.getStorageAt( ) and the problem with getStorageAt( ) is that you need to know where in the storage to look.

ERC-1967

Before ERC-1967, the standard we mentioned earlier, various proxies would implement different storage locations for “The Implementation” address.

This meant third-party apps like Etherscan couldn’t identify which slot to check to get information about “The Implementation”.

ERC-1967 solved this by providing a pre-defined storage slot for “The Implementation” address.

If we look at Etherscan they show the code for both “The Proxy” and “The Implementation” on their explorer. This is only possible if we have a known storage slot for obtaining “The Implementation” address.

The ERC-1967 also provided defined slots for the “beacon address” (we’ll touch on this later) and the “admin address” as well as ensuring events were emitted when any were changed.

Code Deep Dive

Let’s now take a look through the OpenZepplin implementation of the transparent proxy and the 2 execution paths (admin & non-admin) to get a better understanding of what’s going on.

We’ll start with the user (non-admin) execution path.

User Access (Non-Admin)

1. Let’s start with the inheritance structure of the transparent proxy, we have 3 contracts one of which is abstract. An abstract contract is akin to an abstract class in that it cannot be instantiated on its own because it contains at least one function without a concrete implementation (this must be defined by the developer). Our core proxy contract “TransparentUpgradeableProxy” inherits from “ERC1967Proxy” which inherits from the “Abstract Proxy”. These represent the 3 contracts you see above.

2. Next, let’s briefly touch on the constructor. Constructors are executed in the order of inheritance, starting from the base class to the derived class. This means first the “ERC1967Proxy” constructor will be called then “TransparentUpgradeableProxy”. The “Abstract Proxy” contract has no constructor. Inherited contract constructors are automatically called however we must explicitly call them if they take in parameters such as “ERC1967Proxy” does. This is why we have ERC1967Proxy(_logic, _data) in the “TransparentUpgradeableProxy” constructor. This is the syntax for explicitly calling the constructor with specific inputs.

3. Now let’s start with the actual function call. A non-admin user will make a call to “TransparentUpgradeableProxy”. Note that every function in all 3 contracts above is private (denoted by _ prefix), as a result, any call is going to be passed to the fallback( ) function. Note the difference between _fallback( ) which is private and fallback( ) which is the actual fallback function. There is no fallback( ) in “TransparentUpgradeableProxy” but there is in the inherited “Abstract Proxy” contract. That will be our entry point.

4. The fallback( ) function just passes us along to the internal _fallback( ) function. A _fallback( ) function exists in both the “Abstract Proxy” contract and the “TransparentUpgradeableProxy” contract. Since “TransparentUpgradeableProxy” is the derived contract its _fallback( ) overrides “Abstract Proxy” and is therefore where the call goes.

5. At the _fallback( ) there are some checks to see if the user is the admin user, since we are not the admin we will be passed to super._fallback( ). Super is a keyword to call a function in the parent class, in our case “ERC1967Proxy”.

6. Since “ERC1967Proxy” doesn’t contain a _fallback( ) function we need to go up one level to the _fallback( ) in “Abstract Proxy”. This _fallback( ) in turn calls _delegate(_implementation( )) where _implementation( ) returns the address of the implementation contract.

7. The _delegate( ) implementation utilises some inline assembly to make the delegate call. (See evm.codes for a breakdown of each OPCODE)

   1. Line 27: calldatacopy(destOffset = 0, srcOffset = 0, length = calldatasize())

      1. This copies the calldata, at offset 0 of length calldatasize() into memory at offset 0 to be used in the delegate call.

   2. Line 31: delegatecall(g = gas(), a = implementation, in = 0, insize = calldatasize(), out = 0, outsize = 0)

      1. g = gas - The amount of gas to be sent along with the call. This must be enough for execution.

      2. a = address - The address of the contract for the delegate call, in our case the implementation contract.

      3. in = start memory location input - This marks the start position of the input data in memory that will be sent to the target contract, remember that calldatacopy copied to memory position 0.

      4. insize = input size - The size (in bytes) of the input data, in our case the calldatasize( ) since we are passing everything along.

      5. out = start memory location output - Marks the start position in memory where the output data of the delegate call will be stored, position 0 is selected.

      6. outsize = output size - The size (in bytes) of the output area in memory, in our case this is 0 which means nothing will be stored in memory.

      7. Note the output value (not the result) of the delegate call will be stored in the return data buffer. This can be accessed using returnDataCopy. This means the return value is still available even though we didn’t save it to memory.

   3. The variable “result” captures whether the delegate call was executed successfully or not. 0 indicates that the execution was unsuccessful.

   4. Line 34: returndatacopy(destOffset = 0, srcOffset = 0, length = returndatasize())

      1. This copies the contents of the return data buffer at offset 0 of length returndatasize() (which contains the output of our delegate call) into memory at offset 0.

      2. You may have noticed that returndatacopy() just copies the return data to memory and asked why didn’t we do that in the delegate call with “out” and “outsize”. The issue is that we didn’t know the size of the return data at that point. If we had we could have copied the return data to memory immediately via the delegate call removing the need for returndatacopy().

   5. Line 36: A switch statement, in both cases the output is returned to the user either via a return or a revert depending on whether the delegate call was successful or not.

      1. return(offset = 0, size = returndatasize()) - Returns from memory starting at the offset 0 the specified size returndatasize() which is the output of the delegate call.

      2. revert(offset = 0, size = returndatasize()) - Same as return but state changes are reverted and unused gas is returned to the caller.

With that we have covered the User (Non-Admin) flow, now let’s take a quick look at the Admin flow for the Transparent Proxy.

Admin Access

The Admin flow introduces a new contract “The Proxy Admin” and the library ERC1967Utils. Below you will see how they are utilised.

1. To understand the admin flow we first need to see who the _admin is in our core proxy contract “TransparentUpgradeableProxy”. We can see admin is set in the constructor. The constructor initialises a “ProxyAdmin” contract and sets the _admin as the ProxyAdmin contract address. This means it is the “ProxyAdmin” contract, not the ProxyAdmin owner EOA that is authorised.

2. Because of this, our call from our admin user must go through the “ProxyAdmin” contract not directly to “TransparentUpgradeableProxy”. We must be the owner of the “ProxyAdmin” contract.

3. We call upgradeAndCall passing in the proxy we want to target, the new implementation address and the data for an (optional) call on that new implementation. This in turn calls upgradeToAndCall on the proxy.

4. As explained before all calls will end at the fallback since all other methods are private. The fallback( ) then calls the private _fallback( ) method.

5. We have the admin check again using msg.sender but this time we are the _proxyAdmin( ). Note _proxyAdmin is just a getter on _admin. This a good time to remind you of the difference between tx.origin and msg.sender. tx.origin refers to the original external account (EOA) that initiated the transaction, in this case, the owner of the ProxyAdmin contract. msg.sender is the immediate caller of this contract which in this case is the ProxyAdmin contract. We pass the admin check, then verify only the specific method “upgradeToAndCall” is being called. if it isn’t revert the call, if it is, call the function _dispatchUpgradeToAndCall( ).

6. _dispatchUpgradeToAndCall( ) grabs the new implementation address from the calldata and then uses the ERC1967Utils.UpgradeToAndCall, passing in the new implementation address and any data for a subsequent call.

7. ERC1967Utils.UpgradeToAndCall verifies the code at the new implementation address is non-zero and then updates the storage space specified in ERC-1967 with the new implementation address.

8. If the data length is > 0 it means the user wanted to make some call after the update so make that delegate call at the new address. If data length is 0 verify the call has no value, this is just to prevent funds getting stuck in the contract.

And that’s the Admin flow.

Concepts have become code, you have now seen how the theory is implemented within solidity. This will help us deepen our understanding of how proxies work and potential security vulnerabilities to watch out for.

However the transparent proxy was not the last iteration of the proxy pattern, there is one more that we need to review. The reasons for why this proxy was created are primarily focused on the gas usage of the transparent proxy.

The introduction of the admin check within “The Proxy” meant that the admin needed to be loaded from storage on every call. Solidity devs will know loading from storage is one of the most expensive OPCODES in the EVM.

This gas overhead for users (and therefore increased costs) led to the development of the UUPS Proxy (Universally Upgradable Proxy Standard).

UUPS Proxy

The key differentiator with the UUPS proxy was moving the “upgradeToAndCall” logic from “The Proxy” contract to “The Implementation” contract.

This change meant “The Proxy” became a simple forwarder of all calls to “The Implementation” contract via delegate call.

With the auth now in “The Implementation”, we no longer needed the ProxyAdmin contract and we reduced the gas overhead of checking msg.sender against the “admin” for every call to “The Proxy”.

Instead, the authorisation logic and subsequently the gas-expensive SLOAD of the admin address is only executed when upgradeToAndCall is called. As a result, all non-admin user calls avoid this SLOAD.

OpenZepplin provides an abstract UUPS contract that can be used as a base for your “Implementation”. It leaves one function _authorizeUpgrade(address newImplementation) undefined so that you, the developer, can implement your own custom authorisation. Here features such as time lock upgrades, multi-sig upgrades, etc. can be implemented.

When coding your “Implementation” contract one important item to be aware of is initialiser functions. You should know why they exist and their differences from constructors.

Constructors vs Initialisers

Constructors are used for initialising state in contracts. They are executed once at contract deployment and their code isn’t included in the contract bytecode.

In the proxy pattern, “The Proxy” (holding the state) and “The Implementation” (holding the logic) are separate. Because of this any state initialisation done in the constructor of “The Implementation” affects only “The Implementation” contract's storage, not “The Proxy's”.

To address the limitation of constructors in proxy setups, initialiser functions are used. These are designed to set up the initial state in “The Proxy's” storage.

Initializers are designed to be executed via a delegatecall from “The Proxy”. This ensures that the state initialised is within “The Proxy's” storage, aligning with the intended logic of “The Implementation” contract.

Similar to constructors, initialisers are meant to be executed only once. This is typically enforced through a mechanism, like a boolean flag, to prevent re-initialization, which could lead to security vulnerabilities.

One thing to be aware of is that, unlike constructors, initializers do not automatically handle inheritance. Under the hood, an initialiser is just a normal function meaning if any of “The Implementation’s” parent contracts have constructors, they need to be explicitly called in the initializer. This differs from a constructor where parent constructors are automatically called.

When implementing upgradable contracts, extra care must be taken with initialiser functions. Ensuring they are secure and only callable as intended is crucial to maintaining the integrity of the contract.

Now back from that detour to the advantages and disadvantages of the UUPS Proxy.

Advantages & Disadvantages

There are both pros and cons to the UUPS.

The major advantages are as follows:

• Reduction in gas overhead for your users.

• Removes the need for the ProxyAdmin contract.

• The upgradeAndCall logic itself becomes upgradable since it’s in the implementation and the implementation can be upgraded. This includes the ability to eventually remove it and enshrine a contract in its current state.

The disadvantages include:

• Reduced separation of concerns, your implementation contract now handles both your auth logic and your business logic.

• Increase risk when updating the implementation contract. Since your implementation now contains your auth logic every upgrade potentially changes the attack surface of your auth logic.

• Risk of “bricking” the proxy. If there is inadvertently an upgrade to the implementation contract that doesn’t contain the upgradeAndCall function, the upgrade functionality for the proxy is lost forever.

If you want to dive into the UUPS abstract implementation contract you can here.

Our final topics for today are to briefly touch on the minimal proxy (also known as clones) and the beacon proxy. Two proxy concepts you may see out in the wild.

The Minimal Proxy

The concept of a minimal proxy is to offer a streamlined approach to deploying multiple instances of a contract that share common logic but require individual storage.

An example of this could be Gnosis Safe contracts, where each Safe is distinct but the underlying multisig logic remains consistent.

Rather than redeploying the entire logic for each new instance, which is gas-intensive and costly, the minimal proxy pattern involves deploying a single implementation contract and then creating lightweight proxy contracts for each new instance.

Minimal proxies do not include upgradeability or authorization functionality, simplifying their structure and reducing both deployment and runtime gas costs. They are static and immutable once deployed.

The Beacon Proxy

The Beacon Proxy pattern introduces an efficient upgrade mechanism for systems where multiple proxy contracts require synchronized updates.

The design utilises a separate contract known as “The Beacon”, which holds the implementation address used by all associated proxies. Each “Proxy” then simply queries “The Beacon” to retrieve the current implementation address rather than holding it themselves.

The Beacon Proxy is very useful when an update across numerous proxy instances is required. Going back to our Gnosis Safe example, where each user's Safe is a proxy contract, imagine a critical update was needed.

Updating the implementation address of each Safe (Proxy) individually would be prohibitively expensive in terms of gas and require huge coordination efforts with users (the deployers and owners of their Proxies) to update.

With a Beacon Proxy, the maintainers of the platform, such as the Gnosis team, need only to update the implementation address in “The Beacon” contract.

All proxy instances pointed at “The Beacon” will be updated as well.

This not only saves gas (as the implementation address only needs to be updated in one location) but also significantly reduces the operational burden since users don’t need to perform individual upgrades.

The one drawback is of course that the pattern does centralise control over the implementation address. The owner of the beacon represents a significant point of trust.

To mitigate this trust and enhance security, mechanisms such as multi-signature wallets and time locks can be implemented.

We’ve covered a lot in this article, traversing the intricate landscape of Proxy contracts. Hopefully, you’ve learned new concepts and added one more pattern to your toolkit.

Till next time.

noxx

Twitter @noxx3xxon

Block builders, a new entity in the post-merge world are about to enter a brutal game of battle royal.

And their weapon of choice - Order Flows.

In this article we’ll be discussing how builders will weaponise their order flows, the risks it poses to the Ethereum chain and take a peek at the potential futures that lay before us.

Subscribe now

State of Play: Pre-Merge

Before we take a look at how things could play out post-merge it’s good for us to have an understanding of how things work at the moment.

The image below maps out a Uniswap trade from a user. It highlights the actors involved as the transaction makes its way from the user to the miner and shows some of the paths the transaction can take to get on-chain.

1. A User has some “intent” in this case the intent is to trade some tokens on Uniswap.

2. The User navigates to the app he wants to use and connects using his wallet provider, for this example let’s say he uses Metamask.

3. The user specifies the trade he wants to make 10 ETH → 20,000 DAI. The app constructs some call data for him to sign (0x5ae4…000) which creates a transaction that represents his trade. This signed data is what will be sent to the RPC endpoints in the next section.

4. Let’s Assume the user hasn’t changed any of the default settings on Metamask, specifically the RPC Endpoint for the Ethereum network. If this is the case RPC endpoint will be set to https://mainnet.infura.io/v3/. This means the transaction will be sent to Infura.

5. Infura will then propagate this transaction out to the rest of the nodes in the Ethereum network. When the transactions land at each node they are placed in the public mempool, a staging area for transactions before they are committed to the chain. The transaction will sit here until it is sequenced into a block.

6. Miners create blocks by selecting and sequencing transactions in their mempool. Typically they prioritise high gas transactions first.

7. Potentially unbeknown to this user another group of actors called searchers are monitoring the mempool. They are looking for valuable transactions. When they see the user’s ETH → DAI transaction their bot sandwichs it to give him the worst possible execution price and themselves the greatest profit.

8. They do this by submitting bundles of transactions to the Flashbots relay where they are guaranteed to be top of block and that either all the transactions in the bundle execute or none do.

9. These bundles are merged together by Flashbots into a megabundle and sent on to whitelisted miners to be included at the top of the block.

10. If we look back at the start of our journey the user could have changed his RPC endpoint in the Metamask settings. He could have switched to a private RPC endpoint, one that bypasses the mempool. An example of a private RPC endpoint is Flashbots Protect, they guarantee no front running or sandwiching enabling you to avoid the monsters in the dark forest.

11. The private RPC is set up to route to specific miners where agreements are made about what can be done with the transactions. These miners typically will have a custom client (ie mev-geth) which enables them to have a private mempool that doesn’t broadcast the transactions sent there. The miners extract as much “ethical” value (ie via back running) as they can and order them in the block.

The purpose of this is to show you the order flows that already exist. I have highlighted the “user public order flow” which comes from the public mempool, the “user private order flow” which comes via private RPC endpoints and the “searcher order flow” which comes via searcher auctions/relays.

The public user order flow is available to everyone.

The searcher & private user order flows on the other hand are “exclusive” to the entities that set up those private relays / RPC endpoints.

It’s this exclusive order flow that has the power to change the game.

Post-Merge World

Ok, that’s what happens in the pre-merge world but what happens in the post-merge one?

For us to understand that there are two important changes happening at the merge we need to review.

PBS, proposer builder separation and the concept of blinded blocks.

Let’s start with PBS.

Proposer Builder Separation (PBS)

PBS is the ability to separate block building from block proposal. Let’s take a look at each one.

Block Building

Block building involves ordering/sequencing transactions within a block. It is a game where hardware, algorithms and information determine your success.

It’s a competitive game, this means you will need to upgrade your hardware, improve your algorithms and get access to the best order flows (information) to stay in the game.

These requirements mean block building has a high barrier to entry.

Block Proposing

Block proposals require you to have put up some stake 32 ETH and run some client software.

The hardware requirements of this software are currently low enough that an individual staker can afford to maintain their own validator.

The only way you compete is by staking more ETH the computation requirements do not increase by much as you increase you’re validator count.

While the initial stake 32 ETH may be prohibitive for many, the computation requirements have been kept low enough for individual stakers to compete in block proposals.

MEV Blocks

Let’s think about what happens in a world where the validator both builds & proposes the block.

The individual validator, doesn’t have access to the hardware, algorithms & information required to build a MEV Block so instead builds a vanilla block.

This vanilla block uses the execution clients default sequencing logic for transactions ordering by gas price.

The MEV validators, who will be larger incumbent entities with access to the hardware, algorithms & information will be able to produce these more valuable MEV based blocks.

MEV Yield

There are some estimates that MEV could make up to 60% of a validator’s yield for the year.

This means that if our individual validator is making 4% per year with their vanilla blocks the MEV validators with their MEV blocks will be making 10%.

The diagram below shows what this yield delta can do to the individual validator over time.

Let’s run through what’s going on here.

1. This equation represents the compounding interest of the individual validator.

   1. The 1.04 represents a 4% annual yield.

   2. x represents the number of years the node has been running for.

   3. Note in reality staking doesn't auto compound your rewards you need to take out what you have earnt and create a new validator / buy more liquid staking tokens.

2. This equation represents the compounding interest for the MEV validator.

   1. The 1.10 represents the 10% annual yield.

3. The graph shows the returns of the 2 validators over the course of 30 years. We can clearly see that as the yield difference compounds the MEV validator begins to vastly outperform the individual validator. This gets worst at an accelerated rate as time progresses.

4. At the 30-year stage, the individual validator has earned 2.25x its original investment while the MEV validator has earned 16.5x.

   1. The MEV validator has been able to take these profits and spin up new validators at a much faster rate than the individual validator reducing their market share.

   2. It’s clear to see that if the entire validator set was split 50/50 with one half being individual validators and the other half being MEV validators the MEV validators quickly gain dominance in the validator set.

This graph shows us how much of a centralising force MEV could be if block building & block proposals are kept together.

Now you may be thinking if you split the roles you just move this centralising force to the builders rather than the validators and you would be right.

Implicit in the design of PBS is saying MEV is a centralising force but we would rather the centralisation happen at the builder level than at the validator level.

It’s through PBS a new entity officially enters the Ethereum ecosystem.

An entity focused solely on building blocks.

Block Builders

Block builders already exist today.

The mining pools that have private relays with dedicated searcher teams. Flashbots with the Flashbots auction that receives searchers bundles. Both of these entities are given a set of transactions/bundles and order them in a way that captures the most value.

The mining pools do this for the entire block and Flashbots do this for their megabundles.

Pre-Merge: Trust-Based System

Pre-merge these “builders” would only entrust their “builds” to themselves or miners they had agreements with. It was a trust-based system.

If we look at a “builder” like Flashbots, they had to send their megabundles to the miners and trust them not to steal the MEV contained within.

Miners have the ultimate power as validators will post-merge.

If a searcher sent a transaction for a $10 million liquidation in theory the miner could just call that liquidation with their own address at the top of the block stealing the opportunity.

To prevent this partnerships were formed with large mining pools where incentives meant stealing an individual transaction wasn’t worth damaging the relationship with Flashbots and losing their access to the MEV bundles.

These incentives didn’t exist for individual miners where stealing the MEV and damaging the relationship may yield the highest expected value given how infrequently they won a block.

The result of this was a permissioned system with only some miners gaining access to the Flashbots MEV orderflow and profits.

Post-Merge: Trustless System

In Ethereum post-merge the builder/validator relationship which is analogous to the builder/miner relationship pre-merge moves closer to a trustless model.

This is enabled via a new feature in Ethereum called “Blinded Blocks”.

Blinded blocks are blocks that only include the block headers present in an Ethereum block. No transactions are sent along with the block.

The transactions are sent after the validator signs the blinded block and sends it to the builder.

Since the builder will emit this signed block to the network it means the validator cannot steal the MEV contained within until the block has already begun propagating to other nodes.

At this point, if the validator were to propose a new block where it “stole” a MEV opportunity it would have “proposed two different blocks at the same height” which is a slashable offense.

Additionally, there is no guarantee that the block that claims the MEV opportunity ends up as the canonical one. There's a 50/50 chance the original does and the validator gets slashed and doesn’t manage to claim the MEV.

This provides a deterrent to validators since the cost of slashing is likely higher than the potential gain from stolen MEV. (People are looking into cases where the highest expected value is to attempt to steal the MEV however these instances will not be common)

Note that when we said that the relationship moves closer to a trustless model, this applies in the direction of the builder to the validator.

Since the block is blinded the validator can’t determine if it is a valid block. It has to trust that the builder has sent one.

The builder is obviously incentivised to send valid blocks, if it doesn’t it loses out on value it could have captured & may be blacklisted for the future.

Fortunately, the downside for the validator is limited to missing their block proposal as an invalid block is not a slashable offense.

In the post-merge world, any validator will be able to connect with any builder and access these MEV transactions via blinded blocks.

This puts an individual validator on an even playing field with the larger entities as both now have access to the enhanced rewards via MEV.

MEV Supply Chain

Next, let’s take a look at the MEV Supply chain in the post-merge world focusing specifically on Builders.

We’ll use the “Flashbots Builder” as an example and show some of the different fronts they can compete on.

• Exclusive Transaction Order Flows

  • Searcher Order Flow - Flashbots Relay

  • User Private Order Flow - Flashbots Protect

• Internal MEV

  • Identifying MEV that isn’t in your “Searcher Order Flow”

  • Capturing Ethical MEV from the “User Private Order Flow”

• Latency

  • MEV boost will introduce some latency from the additional network hops.

  • Vertical integration / co-location could limit the time taken for these hops.

  • This could give the builder more time to see transactions / calculate the best block before the deadline to submit.

• Block Building Algorithms

  • More efficiently packing a block to include the most value.

Of all of these “Exclusive Transaction Order Flows” will almost certainly be the most important factor.

Let’s revist the Uniswap trade that was mapped out earlier but now with the builder/validator model.

The white box shows where the majority of the change is occurring. I’ve omitted the relays which act as aggregators of the block builders and deliver the most profitable block to the validator.

1. Here this private RPC endpoint represents Flashbots Protect. Before these order flows were sent onto the whitelisted Miners. Now they will be exclusive order flows for the Flashbots Builder. Exclusive meaning other competing builders won’t have access to them.

2. The searcher order flow here is the bundles the Flashbots Relay receives. Again this will be an exclusive order flow, only the Flashbots Builder will have access to it.

3. The public order flow found in the mempool, the Flashbots Builder will also have access to these transactions however so will every other builder meaning it provides no competitive advantage.

4. Validators running mev-boost will be able to hook into this builder network. They will receive blinded blocks from the builders and will propose the block that delivers the most value to them.

This example looks specifically at Flashbots but we can expect the same themes to play out with every builder. They will have their own searcher and private transaction endpoints which they will be trying to incentivise people to use. This is their exclusive order flow and the key competitive advantage.

Below is an excellent diagram from Flashbots which shows the dotted white line box above in a bit more detail.

Let’s now zoom in on the “Private RPC Endpoints” and the benefits they offer to users.

Benefits of Private RPC Endpoints

Private RPC endpoints can provide a number of benefits to users some of which we’ve already touched on. Let’s run through them.

• Pre Trade Privacy

  • Frontrunning / Sandwhich protection

• Transaction Simulation

  • Revert Protection - Never include if it fails/reverts

• Generalised Protection (In the Future)

  • Warn you if you are sending tokens to a known honey pot address

  • If Gas paid is extremely high double-check with the user this is their intention

So with all these great features why aren’t all users using them?

Primarily it’s down to knowledge & the friction in getting it set up.

If we look at knowledge a lot of users don’t know this exists or that there are solutions to some of their problems. They don’t know they’re being front-run or sandwiched. They don’t know that they could have prevented that expensive revert during an NFT mint.

To look at friction let’s see how we would set this up on Metamask as an example.

The user has to go into the Settings → Networks → Add Network and from there has to give the new “network” a name ie Ethereum(Custom RPC), add the RPC endpoint you want to use, with a chainID of 1 and currency of ETH.

An advanced DeFi user will understand how to do this and what they are doing. For casual users, this is a complicated process and they likely don’t want to play around with default settings.

One could argue this isn’t something the user should have to deal with, there’s too much knowledge required to make an informed decision.

So how do we resolve this?

One way would be for the wallet provider ie Metamask to change their global default setting to a private relay.

Metamask - A Sleeping Kingmaker

Let’s think about how powerful this ability to change the global default endpoint is for a wallet provider like Metamask?

Think about how much of the public mempool comes from a Metamask wallet. Some studies have said up to ~70% of the transactions being made on Ethereum are via Metamask.

How much would a builder be willing to pay for exclusive access to that order flow. Or how easily Metamask could dominate if they decided to create their own builder entity.

In other words, Metamask appears to be a “Sleeping Kingmaker” and one that could crown itself if it wanted to.

For Metamask it’s a difficult path to navigate.

They have access to this huge amount of value via their order flow but they want to make sure they don’t damage their users’ experience and that the community is on board with any changes that are being made.

If Metamask used a default private RPC and the builder on the other end wasn’t winning builds consistently users may be waiting many blocks for their transactions to confirm.

Since their transactions aren’t in the mempool they can’t get on-chain until Metamask’s builder wins a build.

To limit this wait time Metamask could easily embed some default logic. An example would be stating that transactions are sent to the public mempool if they haven’t been included within 3 blocks.

Monetising Order Flow

Wallet providers are thinking about monetising their order flows.

Monetising their order flows enables them to capture MEV value and give it back to their users.

They can do this via gas discounts, token emissions that represent a share of the value captured etc.

If the dominant wallets decide not to monetise order flows do we could see a great migration from those that ignore order flows to wallets that acknowledge and exploit it.

A payment for order flow solution to me exists at the application and wallet level, the best applications and wallets will be the ones that are able to return the maximum amount of value to their users

Stephane Gosselin - Flashbots - Unchained Podcast

Does it force the hand of the dominant wallet providers to enter the order flow game?

Is this too much value to ignore?

Maybe let’s take a look at how these order flows could be sold.

Exclusivity Agreements

The simplest way for a wallet provider (Metamask) to sell order flow would be via an agreement to provide exclusive order flow for one or more builders.

The agreement would have terms of service.

• No Malicious MEV ie front-running, sandwiching

• Tx will be emitted to the mempool after 3 blocks

• 6 month contract

• etc.

I would argue that this approach would be very centralising for the builder market. If only one builder got access to Metamasks order flows that might be game over for everyone else.

Order Flow Auctions

Another possibility is the concept of individual tx auctions.

The wallet provide could provide an auction service to all builders where they exposed a stream of unsigned transactions to be bid on.

The auctions would be time bound to ensure inclusion and only builders who were registered with the validator that was up next to propose the block would be able to bid.

If no bids were received for a tx it could be emitted to the public mempool. Transactions known to have no “MEV value such as simple ETH value transfers could also be set up to default to them mempool.

When a builder successfully won a bid they would pay the fee and be sent the signed transaction.

Similar to the “Exclusivity Agreements” there would be terms of service with the auction ie No front-running sandwiching, Tx will be emitted to the mempool after 3 blocks etc.

The Builders would need to write algorithms/models to automatically price different transactions and determine what to bid.

The wallet provider could take a small percentage from these auctions and return the remainder to the user for that specific transaction.

The more valuable a user’s transaction, the more the builder will bid and the higher the payment back to them.

This auction method fixes the issue of attributing MEV to different addresses when a batch of transactions is sold.

In “Exclusivity Agreements” how can you determine which transactions generated the MEV and therefore which users should be compensated. Here we have a clear 1-to-1 mapping of Tx (user) to the price paid.

Whoever the auctioneer is in this model has a significant amount of power since they hold all the signed transactions.

While it would likely start as a centralised entity efforts would need to be made to decentralise/trust minimise that component.

Psyops

One other thing we could see with order flow auctions is builders making predictions based on the available unsigned transactions in the same way bots look at exchange order books.

Could entities spoof transactions in the auction to gain some advantage? It would be up to the wallet providers / auctioneer to prevent this from happening.

A Centralising Force

Let’s look at what happens when 1 builder has exclusive access to the majority of transactions on Ethereum.

Let’s say 20 builders have access to 300 Txs in the mempool. There is a single builder who has exclusive access to Metamask’s 700 Txs in addition to the 300 mempool Txs giving them 1000 Txs to build with.

The 1000 Tx block builder gets to build the majority of blocks. They have a larger search space from which to build a block and exclusive access to some of the value.

Slowly the block builders with mempool only access go out of business.

They’re not winning enough blocks. Any exclusive order flow agreements they may have had aren’t getting renewed or are being terminated.

How often a builder wins a block has a direct impact on their user’s experience, eventually, they are unable to compete, unable to operate at a profit.

Exclusive order flow is a very big risk and very big danger in the MEV space over the next couple years.

Hasu - Flashbots - Wintermute MEV Hackathon

A world where block builders compete on exclusive order flow is a world that gravitates strongly to a winner takes all effect occurring in block building.

MEV Dystopia

The image below is from Stephane’s MEV Utopia and Dystopia talk and highlights a decentralised MEV supply chain. The red block I have added represents the vertical integration that could occur via exclusive order flow.

Let's run a simulation where Metamask creates their own builder and see what could happen.

Metamask own 70% of the public order flow, they make this exclusive order flow to themselves and are able to quickly dominate the block building space.

Since they are dominating the block builds searchers have no choice but to send their bundles to the Metamask builder. If they don’t they’re only able to access MEV on the blocks their current builder wins which due to Metamasks dominance is a low percentage.

Metamask begins to build an internal searcher team who learns from the searcher order flow they have access to.

The internal searcher team gets to extract value from 70% of the Ethereum transactions with no competition while the external searchers are left to fight for the value in the remaining 30% in the mempool.

By dominating the builder space Metamask also gets to keep more of the MEV for itself rather than passing it on to the validator.

In a competitive market, margins are cut and the majority of value ends up in the validators hands.

In a monopoly, Metamask just needs to ensure their block build pays slightly more than the next best builder.

Very quickly Metamask has come to dominate the wallet, searcher & builder market.

How the community reacts would be interesting.

Likely Metamask would have to self-regulate in the same way mining pools and validator pools have had to.

The diagram below from Jon Charbonneau shows the feedback loop discussed above that can quickly lead to centralisation.

App Level Optimisations, Cross-Chain & CEX

There are lots of factors I haven’t touched on that will impact how this future plays out. Let’s briefly touch on each one and provide a high-level overview.

Application Optimisations

Decentralised applications such as Uniswap, Sushiswap, etc. have a huge incentive to reduce the MEV exposed by their protocol.

Ideally, they can capture the value for themselves and their users at the Tx origin.

A great example of this is the collaboration between Sushiswap & Manifold Finance (Manifold would like to be one of the main block builders post-merge).

Sushi is going to replace their “transaction router” with Manifolds “MEV router” at the protocol level.

The “MEV router” looks to capture arbitrage opportunities as the user makes the trade and return the value back to the protocol. You can read more about it here.

These application/builder relationships will be another area in which builders will compete.

Cross-Chain MEV

Cross-chain MEV is already occurring however we can expect it to get more competitive in the future.

Cross-chain MEV is non-atomic, has higher execution risk, involves inventory management and requires deep knowledge across multiple chains.

It, therefore, has a much higher barrier to entry.

Everything we have talked about is roughly mirrored on other chains. Image gaining access to Solana orderflow, Avalanche orderflow, etc.

The order flows on other chains will influence what can be done on Ethereum.

Increasing the search space of valuable transactions is always better for finding the highest value combination.

How big an impact this “other chain” order flow has on the builder network is yet to be seen but in an ultra-competitive environment it would provide an edge.

Centralised Exchanges

Like cross-chain MEV we are already seeing the on-chain/off-chain MEV opportunities be exploited.

With centralised exchanges, builders will have to minimise their latency through co-location and negotiate deals to get the lowest trading fee.

If one builder has negotiated a trading fee of 0.02% and another has a trading fee of 0.08% how does this impact the on-chain/off-chain opportunities available to them?

This will be another area in which builders can compete and try to find their edge.

An Unknown Future

Who knows how this future will play out, this is an active area of research that has lots of moving parts.

Stephane’s quote below captures the reality of the builder market but also the mission of the community to keep it as decentralised / flat as possible.

Ultimately it’s likely the builder marketplace is going to have some power law distribution where the top builders aggregate the majority of the proposal power but we want to keep this distribution as flat as possible.

Stephane Gosselin - Flashbots - Bankless

And who knows maybe there is light at the end of the tunnel.

Til next time

noxx

Follow me on Twitter @noxx3xxon

Lucky for you that’s what we’ll be diving into today.

By far the largest form of MEV on-chain is arbitrage. The concept is simple, find price differences between exchanges on given tokens, execute a trade, pocket some profit and in the process bring the token prices on the exchanges back in line with each other.

While the concept is simple, finding the highest yielding arbitrage across a large set of exchanges and tokens can be difficult.

When finding an optimal arbitrage you’re racing against the block time of the chain and there are lots of moving parts. New transactions in the mempool, changing reference prices on centralised exchanges etc.

Lucky for us finding this optimal arbitrage has been found to be a “convex optimsation” problem for Constant Function Market Makers (CFMMs) like Uniswap, Sushiswap, Balancer etc.

What this means will be the subject of this article but to give you a taster it means that we can efficiently solve the arbitrage problem to global optimality.

Or in plain English, we have a formula that can efficiently find the set of trades that maximises arbitrage profit across a set of CFMMs.

Subscribe now

Mathematical Optimisations

Convex optimisations are a subfield of mathematical optimisations.

If we want to learn about convex optimisations a good place to start is gaining a high-level understanding of what a mathematical optimisation is.

Mathematical optimisation is the selection of a best element, with regard to some criterion, from some set of available alternatives

So what does this actually mean, let’s focus on the most common use case which is using mathematical optimisations when handling min/max problems.

Min/Max problems are problems that minimise or maximise an “objective function” given some “constraints” on the input values of that function.

Note that constraints can come in the form of inequality constraints (x^2 + y^2 >= 1) or equality constraints (x^2 + y^2 = 1).

For example, given a budget buy as many pieces of fruit from the supermarket as possible where each fruit has a different price. Our constraints could be we can buy no more than 5 bananas (b <= 5 inequality constraint) and that we must buy exactly one orange (o = 1 equality constraint).

Now let’s look at a more complex example and the notation that would be used to represent the problem. I will also provide an alternative way to view it which may be more intuitive for someone from a programming background.

Constrained Optimisation Example

You are asked to maximise the objective function f( x, y ) where,

f( x, y ) = x^2 * y 

with the constraint

x^2 + y^2 = 1

Let’s start with the constraint, the constraint provides us with a set of viable x & y values.

For example, when x = 1 & y = 1, x^2 + y^2 = 2 which is not 1. Therefore it does not meet the constraint and is not a valid x, y position.

When x = 0.70710678118 & y = 0.70710678118, x^2 + y^2 = 1 which is equal to 1. Therefore these x, y co-ordinates do meet the constraint and are valid.

This same objective function and constraints can be represented in the form of a function in python. Our objective is to maximise what the function returns.

The function objective_function( x, y ) and is equivalent to f( x, y ). For the constraint, I have raised an exception if it isn’t met rather than using an indicator/penalty function.

This problem can be viewed graphically with 3 axes, one for x, one for y and one for the returned result f( x, y ).

Above is a 3-dimensional graph that represents this problem. The red circle represents all the x, y coordinates that satisfy the constraint

x^2 + y^2 = 1

Another way to visualise this graph is to imagine drawing the x & y axes on the floor in a large playground using some chalk.

Given x, y coordinates, we can walk to that position in the playground and at that location a value, f( x, y ), will be returned to us.

The returned value is the objective function we’re trying to maximise. Its value will represent some height above or below the floor. Therefore the height above/below the ground represents our third axis f( x, y ).

If we had the ability to place a floating tennis ball above/below the ground based on the returned f( x, y ) we could plot out the 3-dimensional graph.

We would simply walk around the playground note the x & y position and place our tennis ball some point above or below the ground.

If done at every coordinate this network of floating tennis balls would match the 3-dimensional graph we see in the images above.

The maximisation question can then be thought of as given a set of tennis balls placed above / below the ground at all playground coordinates (x, y) where x^2 + y^2 = 1 find the tennis ball that is the highest above the ground.

Framing an Optimisation Problem

The purpose of this example is it shows us how an optimisation problem is framed.

We have some objective function which is the thing we want to minimise/maximise and a set of constraints. The importance of this will become apparent when we look at a real-world arbitrage.

This is all the context we need for the rest of this article however if you are interested in learning more about this specific problem there are a set of videos that describe the solution. Feel free to come back at the end and run through them to help aid your understanding.

• Constrained Optimization Part 1

• Constrained Optimization Part 2

• Constrained Optimization Part 3

Now let’s move on to the optimisation specific to CFMM arbitrage, convex optimisation.

Convex Optimisation

First, let’s start by looking at what makes our CFMM arbitrage optimisation problem convex. We’ll be dealing with a lot of what we have already encountered namely the objective function and constraints.

1. The objective function must be convex.

2. The equality function can be linear, you may wonder why the equality function can be linear we’ll see why in [3].

3. The linear equality function can be converted into 2 inequality functions and given the equality function is linear we know that the associated inequality functions will be convex (see here if you’d like to learn why).

4. The inequality functions must be convex.

So we’ve determined we need the objective function and the inequality constraints to be convex but what determines if a function is convex.

Convex Functions

Let’s have look at the definition.

In mathematics, a real-valued function is called convex if the line segment between any two points on the graph of the function lies above the graph between the two points

The image below will help clarify what this means.

We can see in the second and third graphs we are able to define a line segment between 2 points on the graph that goes below the graph indicating that they are non-convex.

If we take a look at Uniswaps (x * y = k) function on a graph we can see it is a convex function.

Again this is all the context we need, we have determined that our objective function and inequality constraints must be convex for a convex optimization problem.

There is lots more to learn about convex optimisation, the property of duality, the lagrangian, interior point method etc. however they’re not required to understand the rest of the article.

I would encourage you to dig into these topics after finishing. You can start with these 3 videos which give a great overview of some of these concepts.

• Convex Optimisation Part 1

• Convex Optimisation Part 2

• Convex Optimisation Part 3

Now that we have determined that our CFMM arbitrage problem is a convex problem we can move on to the implementation.

CFMM Arbitrage Routing

This section will focus on enhancing your understanding of how an arbitrage problem is framed as a convex optimisation problem and solving that problem via python.

We will draw heavily from 2 resources, the first a talk from Theo Diamandis on convex optimisation and the second a convex optimisation github repo from Guillermo Angeris. Both should be reviewed at the end of the article to solidify your understanding.

All the code in the rest of the article can be found in this gist which is a fork of Guillermo’s arbitrage.py with some additions.

One caveat to note we will be ignoring gas during these calculations to keep things simple. Note Theo does touch on how to include gas in his talk if you are interested. Now let’s begin.

Framing The Problem

The problem statement is given a set of CFMM (Constant Function Market Maker) pools is there an arbitrage opportunity and if so which is optimal?

This problem is actually a subset of the CFMM routing problem.

We will see later that the addition of one extra constraint enables us to use this routing problem to solve our arbitrage optimisation.

So how do we formulate this routing problem into a convex optimisation problem?

Let’s run through it step by step taking you through the mathematical approach and its translation into code.

Search Space

We start by defining the search space. We can either define a set of tokens and find all the pools that contain these tokens or we can define a set of pools in which case the tokens are defined by the pools in our data set.

Our tokens will be labeled 1 to “n” and CFMM pools will be labeled 1 to “m”.

The connection between the tokens and the pools represents the CFMM network and can be viewed using a bipartite graph.

Let’s have a look at the bipartite graph along with how the tokens and CFMMs are defined in arbitrage.py (Note in the code we are using labeling 0 to n-1 & 0 to m-1)

This looks complicated but I can assure you it isn’t.

1. The CFMM pools are declared in code as an array called “local_indices”. Each CFMM pool is itself an array where the items in the array determine which tokens are available within that pool. “m” is equal to 5 since we have 5 CFMM pools.

2. The tokens are declared in code as a list [ 0, 1, 2, 3 ] called “global indices”. “n” is equal to 4 since we have 4 items in the list. The numbers within this list represent tokens ie

   1. 0 = TOKEN-0

   2. 1 = TOKEN-1

   3. While I have labeled these TOKEN-X for simplicity you can imagine these mapping to real tokens such as ETH, DAI, SOL etc.

3. The bipartite graph shows the CFMM pools on the left-hand side and the tokens on the right-hand side. A pool node is connected to a token node if that pool contains that token. This gives us a full representation of the network of CFMM pools we are working with.

Let’s quickly run through each CFMM.

• CFMM 0 is a Balancer Pool (Balancer pools can hold more than 2 tokens)

  • [ 0, 1, 2, 3 ]

  • Contains TOKENS 0, 1, 2 & 3

• CFMM 1 is a UniswapV2 Pool

  • [ 0, 1 ]

  • Contains TOKENS 0 & 1

• CFMM 2 is a UniswapV2 Pool

  • [ 1, 2 ]

  • Contains TOKENS 1 & 2

• CFMM 3 is a UniswapV2 Pool

  • [ 2, 3 ]

  • Contains TOKENS 2 & 3

• CFMM 4 is a Constant-Sum Pool

  • [ 2, 3 ]

  • Contains TOKENS 2 & 3

At this point, you may be asking why the tokens were defined as “global_indices” and the CFMM pools as “local_indices”? Let’s find out.

Global vs Local Indices

The naming above refers to the global index labeling of tokens which applies to all CFMM pools and the local index labeling of tokens which applies to a specific CFMM pool.

To give you an example above we have declared the following global indexes.

• 0 → TOKEN-0

• 1 → TOKEN-1

• 2 → TOKEN-2

• 3 → TOKEN-3

If we look at the local index for CFMM-2 we have.

• 0 → TOKEN-1

• 1 → TOKEN-2

This means the index mapping of a token can be viewed globally or locally. If we look at the global index 0 we can see it maps to TOKEN-0. If we look at the local index 0 of CFMM-2 we can see it maps to TOKEN-1, a different token to the global index mapping.

The local indices can be defined by the notation below,

Below is a table showing both the global index and local index of each CFMM.

Since our global index differs from our local ones we need to have a way of translating local indices to global indices.

Ultimately we want to see the net gain/loss of each token across the entire network of CFMM Pools after all trades have been completed. This will be viewed in the global index.

To do this translation from local index to global index a set of matrices is used.

Below is the set of Matrices for our example.

Note that A0 maps to CFMM-0, A1 to CFMM-1 etc. These matrices are generated using the following code.

We’ll see these matrices in action later in the article, for now, you just need to know they exist and that their purpose is mapping local indexes to global ones.

Next, we need to look at how we define our trades across the CFMMs.

Trades - Lambdas & Deltas

When making a trade/swap with a pool we have the amount we put into the pool, referred to as “Delta” and the amount we take out of the pool, known as “Lambda”.

Each token within the pool has its own “Delta” & “Lambda” values.

For example, if we traded against the UniswapV2 pool of ETH/DAI and put in 1 ETH and received 2000 DAI we would have the following values for “Delta” & “Lambda”.

• ETH

  • Delta = 1

  • Lambda = 0

• DAI

  • Delta = 0

  • Lambda = 2000

Trading Function

We can define the trade using “Delta” & “Lambda” and use those values to ensure the trade adheres to the trading function that governs the pool.

We define the trading function with the greek symbol phi φ.

1. Making a trade of “Delta i” & “Lambda i” against “CFMM i”

2. The trade results in converting the tendered tokens “Delta” into the received tokens “Lambda”

3. Trade is accepted if it meets the trading function constraint. The trading function phi takes in pool reserves, “Delta”, “Lambda” and “Gamma”.

   1. “Gamma” represents the 1 minus the trading fee of the CFMM. This ensures we take into consideration the trading fee (0.3% for UniswapV2) that will be sent to the protocol from our “Delta” when we add tokens to the reserves.

   2. The trading function ensures that the trade results in a new reserve that is greater than or equal to the trading function result of the old reserves.

Let’s see how we handle this in the code.

1. The reserves are declared for each CFMM pool. In this example these have been hardcoded, in reality, you would be constantly updating these reserves as trades happen on-chain. The first item in the array [ 4, 4, 4, 4 ] represents the Balancer pool and means we have the following within the pool

   1. 4 of TOKEN-0

   2. 4 of TOKEN-1

   3. 4 of TOKEN-2

   4. 4 of TOKEN-3

2. The trading fees are declared for each CFMM pool. The trading fees are defined as 1 - the actual fee. For example, UniswapV2 is a 0.3% fee so our fee is 0.997.

3. “Deltas” & “Lambdas” are declared and defined using cp which is the cvxpy library. This library is a convex optimisation solver. At this point in the code “Delta” & “Lambda” are abstract, they have no real value until we ask cvxpy to solve the optimisation.

4. The new reserves are declared. We can see they are calculated using the equation we saw earlier.

   1. R = Reserves

   2. gamma = “Gamma”

   3. D = “Delta”

   4. L = “Lambda”

Now we understand how each individual swap will be defined we can define the “Net Network Trade”.

Net Network Trade

The “Net Network Trade” is the +/- of each token in the network, at the end of all the trades, relative to our starting position.

This is where the “Ai” matrices we defined earlier will be used.

They allow us to take a trade against a CFMM pool which is made up of the tokens on that CFMM at their local indexes and combine it with our “Ai” matrix to update a global index array which will represent our “Net Network Trade”.

The “Net Network Trade” is represented by the greek letter psi Ψ. Its mathematical notation is seen below.

The image above states that psi Ψ is the sum of all trades across all CFMMs 1 → m where a trade is defined by “Lambda i” - “Delta i” and “Ai” is used to convert that trade into its global mapping.

Again let’s dive into the code, focusing on CFMM-2 as an example.

1. Psi is declared. Once again we’re using the cvxpy library. The @ symbol when used with matrices means the dot product of the 2 values. We have the A2 matrix which converts the local token indexes to global token indexes and (L-D) which is “Lambda” - “Delta” ie how much goes in during the swap and how much comes out. We sum the results for the CFMMs to give us our “Net Network Trade”.

2. Is a demonstration of the dot product method for those who aren’t familiar with matrix multiplication.

3. The result of the dot production calculation for CFMM-2 can be seen here. Each row represents the +/- of a token in the trade. Note the numbers above come from the cvxpy solution to our convex optimsation problem.

   1. (0 * -0.224) + (0 * 0.931) = 0 = TOKEN-0

   2. (1 * -0.224) + (0 * 0.931) = -0.224 = TOKEN-1

   3. (0 * -0.224) + (1 * 0.931) = 0.931 = TOKEN-2

   4. (0 * -0.224) + (0 * 0.931) = 0 = TOKEN-3

Above we have looked at CFMM-2 in isolation, now let’s look at the sum of all the CFMMs to get our “Net Network Trade” matrix.

Note, for this diagram we have rounded to 3 decimal places so the result will differ slightly from the python output in arbitrage.py.

Each matrix represents the trade that occurred on that specific CFMM with positive values being received tokens and negative values being tendered tokens. By combining all these trades together we get our “Net Network Trade”.

• CFMM-0 Executes a trade

  • Tenders 4.234 of TOKEN-0 & 0.131 of TOKEN-2

  • Receives 2.135 of TOKEN-1 & 1.928 of TOKEN-3

• CFMM-1 Executes a trade

  • Tenders 0.736 of TOKEN-1

  • Receives 4.234 of TOKEN-0

• CFMM-2 Executes a trade

  • Tenders 0.224 of TOKEN-1

  • Receives 0.931 of TOKEN-2

• CFMM-3 Executes a trade

  • Tenders 4.646 of TOKEN-2

  • Receives 5.189 of TOKEN-3

• CFMM-4 Executes a trade

  • Tenders 3.867 of TOKEN-3

  • Receives 3.864 of TOKEN-2

• Net Network Trade

  • Receives 1.175 TOKEN-1, 0.018 TOKEN-2 & 3.25 TOKEN-3

Next, we need to think about what exactly it is we what to maximise. What is our objective function?

Objective (Utility) Function

The Objective Function sometimes known as the utility function is what we want to maximise.

So what do we want to maximise?

We want to maximise the total value we receive at the end of all the trades. To do this we can’t use the number of each individual token as token prices vary. We need to convert the tokens to a common unit of value, we need to normalise the data.

We can do this by getting the USD values of the tokens from external markets with deep liquidity.

This means our objective function is maximising the “Net Network Trade” in USD value. Let’s check out the code.

1. We define the market_value of each token. Here we use a hardcoded array but in reality, we would be constantly querying an exchange endpoint to get the latest prices.

   1. $1.50 is the price for TOKEN-0

   2. $10 is the price for TOKEN-1

   3. etc.

2. The objective function is declared as obj. It states we want to maximise “market_value @ psi”, as I mentioned previously @ in this context means matrix multiplication.

3. These 2 matrices represent the market value and psi in the real solution. The resulting matrix is the “Net Network Trade” in USD value, exactly what we are trying to maximise.

As mentioned the values I’ve used here are from the actual solution, in reality prior to the convex optimisation being solved these are all abstract values.

I’ve included them as I feel seeing the real values rather than symbols can sometimes help with our understanding.

Note sometimes we may want to maximise the value for specific tokens. If we were only interested in acquiring TOKEN-0 & TOKEN-2 we could set the market value of TOKEN-1 & TOKEN-3 to zero. This will make the optimisation maximise the return value only in tokens 0 & 2 rather than across all 4 tokens.

We now have our objective function and can finally move on to the last piece of the puzzle, the constraints of the system.

Trading Constraints

The convex optimisation problem we have been setting up throughout the article exists within a network of CFMM pools.

These pools have their own laws that govern them.

These laws come in the form of trading functions, which we touched on earlier. The most famous being Uniswaps “x * y = k”.

To dig into each CFMM’s trading function is outside the scope of this article but if you are interested have a read of this article.

Above are the trading functions for the 3 DEXs we are trading in. Within these 3 DEXs we are trading in 5 CFMM pools. Each pool has an arrow pointing to the trading function it uses.

Let’s see these constraints defined in the code.

1. The Balancer trading function is a geometric mean function. It includes the weights of the tokens in the pool and is declared with the cp.geo_mean. The sum of the weights ( [ 4, 3, 2, 1 ] ) adds up to 1 representing all of the assets in the pool.

   1. TOKEN-0 = 40%

   2. TOKEN-1 = 30%

   3. TOKEN-2 = 20%

   4. TOKEN-3 = 10%

2. UniswapV2 is also a geometric mean market maker and so a cp.geo_mean can again be used to define the constraints for CFMM 1, 2 & 3.

3. Constant sum uses a different trading function and as such we use cp.sum.

4. This is not a trading function constraint but instead the constraint that turns our routing problem into an arbitrage problem that we discussed earlier.

   1. By stating that at the end of all trades there should be no tokens that need to be tendered we turn the routing problem into an arbitrage problem.

   2. This constraint checks that each token in psi (net network trade) is greater or equal to 0. This means at the end of all trades for every token we have either received that token or at least not had to tender any of that token.

Solving Convex Optimisation Problem

Now that we have our objective function and our constraints we can solve the convex optimisation problem.

The objective function and constraints, which effectively frame the problem, are displayed mathematically in Theo’s talk using the following notation.

1. Our Objective Function, which represents the “Net Network Trade” in USD

2. Our trading constraints for each CFMM from 1 → m

3. Valid values for trade amounts across all CFMMs (Note not explicitly defined in the code)

4. Arbitrage constraint, (cT)Ψ is our objective function where (cT) is the market values of the tokens. The arbitrage constraint is an indicator/penalty function. When Ψ >= 0 it will resolve to infinity otherwise it resolves to 0. Since anything where Ψ >= 0 will result in negative infinity, it ensures if this condition isn’t met that permutation won’t be selected (see Theo’s talk for more details).

The solution to the optimisation gives us the total value of the net network trade. By looking through the “Lambdas” & “Deltas” of each CFMM pool we can also see what trades were made to get to this result.

What cvxpy (cp) is doing under the hood to solve this problem would be another entire article so we’re not going to dive into it here. If you are interested I recommend starting here which is the documentation for CFMMRouter.jl, an optimiser written for this problem in julia.

For the context of this article what’s important is that we have a tool that solves convex optimistation problems and we now know how to programmatically frame questions we may want to ask.

After calling solve we will be given a list of trades that are known to be the trades that result in the optimal arbitrage. One issue we still have is that we don’t know in what order to execute them.

Execution Ordering

To kick-start an arbitrage some capital is required for the first trade (even if it is from a flashloan). As such our goal when ordering the trades should be to minimise the kick-start capital required.

Here we are going to minimise USD value across all the tokens to kick-start the trade. There may be situations where you have some of token x and so want to weight it towards that token.

The number of permutations for trade ordering is n! (n factorial) where n is the number of trades.

In our case we have 5 so we have 5 x 4 x 3 x 2 x 1 = 120 permutations.

To keep things simple we will brute force the trade orders to determine the best ordering.

The code is relatively simple and ultimately just loops through each permutation and keeps a tally of how much of each token was required taking into account any tokens that have been received in prior trades.

You can find the full arbitrage.py code below and play around with it yourself. I’ve added a few print statements and comments around the code to aid in your understanding.

Here is the output from the code defining the trades, their execution order, the minimum number of tokens required to kick start the trade and the total tokens received from the arbitrage.

There we have it I hope you’ve learned something new and added a new tool to your arbitrage tool kit.

Til next time

noxx

Follow me on Twitter @noxx3xxon

Do you understand their inner mechanics?

This article looks to provide a deep dive into the Mempool through the lens of the Flashbots auction.

The reader will be taken on a journey through the development of MEV Geth, a custom Ethereum client that enabled Flashbots to alter the shape & structure of the Mempool.

MEV Geth along with the Flashbots relay provided the gateway between searchers & miners changing the MEV game forever.

Subscribe now

The Mempool

Let’s start with the protagonist of this story “The Mempool” before the first official MEV Geth even existed.

The mempool (memory pool) is a smaller database of unconfirmed or pending transactions which every node keeps. When a transaction is confirmed by being included in a block, it is removed from the mempool.

The definition is a great place to get us started. Let’s cover a few more basics.

• A node ie Geth (or MEV Geth) keeps a list of unconfirmed or pending transactions.

• These transactions are communicated to the nodes through their peers or are received directly through their RPC endpoint.

• Each node has its own Mempool, there is no such thing as a global Mempool.

• This means nodes can/do have different Mempools depending on where they are geographically and the peers they are connected to.

• The nodes limit on the number of transactions they keep in their Mempool this is how they ensure they don’t get overwhelmed.

The Mempool is represented in a Geth node via a TxPool struct which can be seen below.

Two items have been highlighted. The first item, “locals”, represents a set of addresses. If a transaction in the TxPool (Mempool) is from one of these addresses it will be considered a local transaction (You’ll see why this is important in the next section).

The second highlighted item is “pending” which represents all currently processable transactions in the TxPool.

You might also notice the “queue” field on line 242, this represents transactions that are in the TxPool but aren’t processable. An example would be a Tx with a nonce that is not in sequence, indicating there is another transaction from the same address which should be processed first.

When thinking about MEV the next question you need to ask is how do these transactions find their way from the TxPool into a block.

Below is the Geth code that executes this functionality. You’ll see that the transactions are actually split into localTxs and remoteTxs, ordered by their gas price / nonce and that localTxs get priority over remoteTxs.

1. The “commitNewWork” function does many things including populating the block with transactions from the TxPool

2. This section gets the transactions from the TxPool and splits them into local and remote transactions

   1. On line 954 you can see the comment “Fill the block with all available pending transactions” after this line, we set the “pending” variable via w.eth.TxPool().Pending(true). This returns a key-value mapping of address to a transaction.

   2. Lines 967 - 974 show us using the “locals” variable we highlighted earlier to split the transactions into local & remote. We are looping through the locals addresses and checking to see if any of the pending Txs are from a locals address. If it matches, those transactions are removed from remoteTxs and added to localsTxs. (Locals is a set of addresses a node can define in its config, they get priority over remote transactions and won’t be dropped by the node)

   3. The end result is the pending transactions are split into localTxs which have come from “locals” addresses and remoteTxs which have come from everyone else.

3. This block represents the localTxs being sorted and committed into the block. Since the localTxs are processed first in the code they get priority over the remoteTxs.

4. The transactions are ordered by gas price and nonce via “NewTransactionsByPriceAndNonce” and then committed to the block via “commitTransactions”

5. “NewTransactionsByPriceAndNonce” takes a set of Txs orders them by gas price and ensures account nonces are not out of order. To do this it uses a heap data structure which we can see initialised on line 443.

   1. The heads variable is an array of TxByPriceAndTime which under the hood is just an array of transactions. It implements the heap interface which enables us to use heap calls to sort our data. It represents the “Next transaction for each unique account (price heap)”. To understand more about heaps see here.

   2. Transactions are ordered per account by gas price but nonce order is maintained. This means a high gas-priced transaction with a nonce that isn’t next may won’t be at the top of the block. The below printout of a Geth test case demonstrates this.

      

   3. If multiple transactions have the same price, the one that is seen earlier

      is prioritized to avoid network spam attacks aiming for a specific ordering (timestamp is captured here in the code).

6. We return the transaction set to be used in the “commitTransactions” function to commit the transactions to the block.

7. The exact same process happens with the remote transactions, they are sorted by gas price and nonce and committed to the block. The number of committed transactions is limited by the block gas limit. Remote transactions can be dropped by on the nodes when the number of Txs in the TxPool exceeds the nodes limit.

This takes us back to the times of “Priority Gas Auctions” (PGA’s) where searchers & bots would increase the gas price of their transactions to get to the top of the block.

Bots would continually bid against each other in the ~13.5 second block time to be first in the block and as a result first to an on-chain opportunity (ie execute a liquidation).

When you lost an auction you still had to pay the gas price for your highest bid since your transaction would still be executed but it would revert. Bots could lose a lot of money from this.

When bidding in PGA’s the bots & searchers had to follow these rules to increase the gas price for a given transaction.

Now we’ve covered vanilla Geth let’s take a look at what changed with the first official release of MEV Geth.

MEV-Geth v0.1 - 31 Mar 2021

For those who don’t know MEV Geth was a new custom client that enabled miners to receive MEV bundles.

“MEV Bundles” represented bundles of transactions that extracted value and needed to be executed atomically. All transactions within the bundle should be executed or none of them.

Flashbots provided a relay connecting Searchers with Miners. Searchers would submit the bundles to the Flashbots Relay and the relay would forward them to Miners. The system relied on a level of trust between the parties to function.

MEV Geth and the Flashbots Relay looked to take PGA’s off the chain where they were impacting everyday users and move it to the relay.

The new auction rules were determined and made available to the Searchers. Losing bids wouldn’t be executed, saving bots their money and Ethereum its block space.

Bundles also introduced the ability to pay a miner via a coinbase.transfer( ) a direct payment to the miner rather than via gas fees.

For v0.1 only one bundle could be selected for inclusion per block.

Let’s take a look at the client alterations that were made to enable these MEV Bundles.

Transaction Ordering

1. TxPool Geth’s implementation of the Mempool which we saw earlier.

2. A new field is added to the TxPool called “mevBundles” which is an array of type mevBundle. MevBundle is composed of 4 elements

   1. “txs” - A list of transactions in the bundle. Each transaction is signed and RLP-encoded.

   2. “blockNumber” - The exact block number at which the bundle can be executed

   3. “minTimestamp” - Minimum block timestamp (inclusive) at which the bundle can be executed

   4. “maxTimestamp” - Maximum block timestamp (inclusive) at which the bundle can be executed

3. “CommitNewWork” is the same function we looked at above which handles filling a block with all pending transactions.

4. The “Local Transactions” & “Remote Transactions” sections for ordering each group of Txs and committing them to the block. You’ll notice both are beneath the “Flashbots Bundles” section meaning the bundle’s transactions will have priority and be placed at the top of the block.

5. This section handles the “mevBundles” received from Flashbots. Line 1148 grabs all the bundles from the TxPool. The “findMostProfitableBundle” function (which we will look at in the next section) is used to determine the most profitable bundle. Bundle info is logged on the node and then the bundle is committed to the block via “commitBundle” on Line 1155.

So how did Flashbots determine the most profitable bundle?

Most Profitable Bundle

Earlier we said, “The new auction rules were determined and made available to the Searchers”.

Below are the new auction rules, it looks complicated but I can assure you it isn’t.

Let’s run through the diagram.

• “s” is the “Adjusted Gas Price” which is what we what to maximise to win the auction.

  

• Delta coinbase is the total ETH paid to the miner from the transactions in the bundle via direct payments ie coinbase.transfer( ).

  

• The sum of all the bundle’s transaction gas payments, (gas price * gas used) per transaction, represents the total gas payment for the bundle.

  

• The sum of all gas used in the bundle.

  

• Dividing these 2 values gives you a ETH price per unit of gas for the bundle (Adjusted Gas Price)

• To maximise this value we need to either

  • Increase the numerator by paying the miner more money through coinbase.transfer( ) or Gas. We do this by reducing our profit margin or finding more lucrative oppourtunities

  • Decrease the denominator by reducing the gas used in the bundle, we do this by gas optimising our contracts

Ok, let’s have a look at how this calculation is implemented in MEV Geth. We start where we left off in the previous example with the “findMostProfitableBundle” function.

1. The “findMostProfitableBundle” function loops over bundles to determine the “maxBundle” (most profitable) and returns this bundle along with some other data that is logged on the Geth node.

2. Each bundle is run through the “computeBundleGas” function. This function returns “totalEth” which represents the “coinbaseDiff” (How much has the miner’s balance increased by) and “totalGasUsed” which is the gas consumed by the transactions within the bundle.

3. We calculate the gas used by looping over the transactions in the bundle and running “ApplyTransaction” this allows us to simulate the transaction and get the transaction receipt which contains “GasUsed”. By summing the “GasUsed” for each transaction we can get the “totalGasUsed” of the whole bundle. The updated state is used for the next transaction in the loop so that it is representative of what happens in a real block.

   1. Remember “totalGasUsed” represents the denominator (bottom) of our “Adjusted Gas Price” calculation which determines the winner of the Flashbots auction.

4. On line 1245 we declared a variable “coinbaseBalanceBefore” which grabs the balance of the coinbase (miner) address before any transactions are simulated. Line 1254 declares “coinbaseBalanceAfter” which grabs the coinbase balance after all the transactions have been applied to the state. Line 1255 sets “coinbaseDiff” which subtracts “coinbaseBalanceBefore” from “coinbaseBalanceAfter” to yield the miner profit. The value is used to set totalEth which is returned.

   1. This value takes into account both coinbase.transfer( ) payments and payments in the form of gas which occurred during the “ApplyTransaction” function. This means “coinbaseDiff” represents the entire numerator (top) of our “Adjusted Gas Price” calculation.

5. The “Adjusted GasPrice” given we now have the numerator and denominator we just need to run the calculation. On line 1221 a variable “mevGasPrice” is declared, we divide “totalEth” by “totalGasUsed” which yields our “Adjusted GasPrice”.

6. Once the “Adjusted GasPrice” is calculated each bundle is compared to the current max value (Lines 1222 - 1227) this ensures the bundle with the highest “Adjusted GasPrice” (“mevGasPrice”) is returned.

This was the first version of MEV Geth but there was much more to come, over the next few months v0.2 was released. Let’s see what improvements were made.

MEV-Geth v0.2 - 12 Apr 2021 →16 Jun 2021

A number of improvements were made in v0.2 but we’ll focus on the main 3 changes. A change to the “Adjusted Gas Price” calculation, bundle merging and a tweak to the structure of a MevBundle within the client.

Adjusted Gas Price

The change to the calculation was a small one. It involved removing the gas payments from Txs that were in a bundle but were already in the TxPool. These were represented by

The purpose of this was to prevent “bundle stuffing” where searchers were stuffing their bundles with high gwei Txs from TxPool to inflate their “Adjusted Gas Price” score.

1. We revisit “computeBundleGas” to see what has changed with the calculation.

2. As before we loop through the Txs in the bundle running “ApplyTransaction” to simulate the Tx and see the change in the state

3. First we set “txInPendingPool” to false

   1. Then we get all transactions pending in the TxPool from the address of the bundle Tx

   2. Get the nonce of the bundle Tx

   3. For each transaction in the TxPool associated with that address check if the nonces match

   4. If they do set txInPendingPool to true and break out of the loop

4. If the transaction is not in the pending pool add the associated gasFees from that Tx to the gas fees for the entire bundle. (This in effect acts as the minus gas fees from Txs that were present in the TxPool)

5. Comparing the adjusted gas price calculation to the code we can now that

   1. “ethSentToCoinbase” maps to “delta coinbase” - payments made to the coinbase address

      

   2. “gasFees” maps the “total gas fees for the bundle” - this represents the gas fees for all Txs in the bundle minus the gas fees from Txs that were already in the mempool

      

Bundle Merging

In v0.1 we could only include 1 bundle per block, with bundle merging in v0.2 we could merge 3 bundles to maximise profit. Let’s see how.

1. “commitNewWork” which handles filling a block with transactions

2. As before we have our Flashbots bundle section, localTxs section and remoteTxs section. The “Flashbots Bundle” section has changed from v0.1, we have a new function called generateFlashbotsBundle.

3. “generateFlashbotsBundle” is taking in an array of bundles, simulating them, sorting them and then merging them. Let’s take a closer look.

4. We have a new struct called “simulatedBundle”, which contains the original bundle plus the key data required for our “Adjusted Gas Price” calculation, totalGasUsed, totalEth etc. The simulateBundles function on line 1217 takes a bundle and simulates it against the head of the chain to verify it doesn’t revert and computes the bundle gas.

5. The simulated bundles are sorted based on “mevGasPrice” (Adjusted Gas Price)

6. These sorted bundles are passed to the “mergeBundles” function. At the start of this function, a variable “finalBundle” is declared which represents a set of transactions. The “mergeBundles” function is designed to enable more than one bundle to be included in a block.

7. This section occurs inside of a bundle loop, each bundle is again simulated via “computeBundleGas” but instead of all being simulated against the chain head state they are instead simulated against the chain state that the previous bundle has left it in. If “computeBundleGas” returns an error or the “mevGasPrice” is below the floorGasPrice (this is a new hardcoded lower limit they introduced in v0.2 ) then the state/gasPool will be reset to what it was in the previous loop. The “continue” will put the program back to the start of the loop with the next item meaning the bundle won’t be included.

8. If the bundle passes the “computeBundleGas” check its Txs are added to the “finalBundle” and some key/values are updated ie totalGasUsed, totalEth etc. Finally, a counter is incremented, a default maximum of 3 bundles can be merged together. This “maxMergeBundles” value balances profit with node performance and can be updated in config.

9. This section checks the counter and breaks out of the for loop if the counter has reached the “maxMergeBundles”

10. A number of variables are returned including “finalBundle”, which is returned to generateFlashbotsBundle, inside the “commitNewWork” function on line 1146 the “bundleTxs” is set which corresponds to “finalBundle”. This value is then committed to the block on line 1155.

Reverting Tx Hashes

One other minor change was to the structure of the MevBundle as defined in the client code. An additional field, RevertingTxHashes, was added which represents a list of Tx hashes that are allowed to return status 0 (revert) on transaction receipts.

The idea of allowing reverting transactions seems strange. As a searcher you should have simulated the bundle and ensured it can execute at the top of the block so why do we need it.

This was a valid assumption when we had a single bundle being submitted in v0.1 but we now have bundle merging enabled on the node.

Suddenly you can’t be sure of the chain state when your bundle is included. You may want to flag some transactions ie liquidations as allowed to revert in case another bundle was included before you.

If your bundle can be profitable with a reverting transaction it makes sense to include it in the list. The alternative is the bundle is discarded by the node so the searcher has nothing to lose.

Strategies that required more than one transaction to execute such as sandwiching likely wouldn’t be allowed to revert since you may end up in a situation where one leg of the trade reverts but the other doesn’t which could leave you exposed.

Next, we’re going to jump straight to version v0.4 where Megabundles were introduced. For those interested, v0.3 involved making MEV Geth compatible with EIP-1559 you can read more about it here.

MEV-Geth v0.4 - 27 Sep 2021 →10 Jan 2022

If you look at the “mergeBundles” implementation in v0.2 you can see that it is quite naive and limiting in how it goes about merging the bundles.

The reason for this is that you don’t want to implement a change in the software (MEV Geth) that completely changes the characteristics of the required hardware (CPU MEM).

Ideally, you want bundle merging to be conducted over the maximum amount of bundles with optimised hardware and algorithms. It doesn’t make sense to implement this on every node.

Megabundles enabled this, they are the precursor to the “full block” bundles we’ll see in MEV Boost.

One interesting change that Megabundles introduces was the ability to rank bundles via profitability rather than gas price.

Imagine 2 bundles one that nets you a profit of 1 ETH with an “Adjusted Gas Price” of 100 and another that nets you 10 ETH with an “Adjusted Gas Price” of 80. These numbers are exaggerated but as a miner you want the 10 ETH bundle. You don’t know when you’ll next get a block so you want to maximise profit when it is your turn.

See this Bert Miller Tweet for some more context.

The value proposition was simple we’ll do the computation and find you a bundle that maximises profit.

Let’s see how it worked.

Megabundles

1. Back at the TxPool struct (Mempool) we can see we have a new field called Megabundles which is a mapping of addresses to “MevBundles”. The address represents the relay the MevBundle is coming from.

2. The sendMegabundleArgs struct is very similar to the MevBundle struct with one additional field RelaySignature. This is the signature from the relay for that specific Megabundle.

3. RecoverRelayAddress takes the RelaySignature and determines the address that made it.

4. The authorised relay addresses are maintained through the MinerTrustedRelaysFlag. The recovered address from the Megabundle signature will be cross-referenced with the trusted relay addresses to ensure only Megabundles from trusted relays are accepted.

Why do Megabundles have this additional security where the node checks that it is from a trusted relayer. Let’s look into the implementation of how a Megabundle is committed to the block to help us understand why.

Committing a Megabundle

The Megabundles are the result of a Relay merging multiple bundles together to maximise profit.

They are designed to take computation load off the MEV Geth node. They do this by removing the need for the node to merge and order bundles, for the client to not perform these calculations there needs to be a level of trust.

Let’s see which steps are skipped when a Megabundle is committed to a block.

1. “commitNewWork” which handles filling a block with transactions

2. There is an if statement checking whether the received bundle is a Megabundle, if it is, the Megabundle is grabbed from the TxPool and committed to the block. Above line 1220 in the codebase is the alternate path for when != Megabundle the node takes the vanilla bundles and merges them as we saw previously.

3. The Megabundle is committed to the block, note there is no “simulateBundles”, “mergeBundles” or “computeBundleGas”. This reduces the computation the node needs to complete.

4. “commitBundle” in turn calls “commitTransaction”

5. “commitTransaction” applies the transaction to the state, verifying it does not revert, updating the profit and returning the receipt logs.

We can see that the Megabundles implementation focuses on speed & performance.

In v0.5 the speed & performance was increased even further by processing a Megabundle immediately if it was better than the best-known block so far. You can dig into the code changes here.

In MEV Geth v0.6, the latest release of the client, private transactions were introduced. This enabled users to send transactions that would be bundled in with the remote transactions but wouldn’t be emitted to node peers for a period of time.

These private transactions aren’t sent to “the Mempool” where “the Mempool” means the TxPool on other Geth nodes.

Generalised frontrunners will snipe transactions they see in the Mempool that are profitable. While a Flashbot bundle protects against this since they aren’t sent to the Mempool they are recorded on the Flashbots API.

Searchers often look through these recorded transactions for alpha. The searcher may want to disguise their Tx by putting it in with other remote transactions.

MEV Boost

As I mentioned earlier Megabundles were the precursor to full block builds and MEV Boost.

In ETH 2 the concept of a block builder has arisen. An entity dedicated to building optimised blocks.

In this new world Validators (Not Miners) will have the block ordering power and will be able to opt-in to receiving full blocks from builders to submit for their allocated slots.

These blocks will be blinded - the validator will not be able to see the transactions until the block has been emitted to the network. This prevents validators from stealing MEV for themselves reducing the required trust between parties.

MEV Boost will be a sidecar container connecting the Validator to Relays which in turn will connect to a network of “Block Builders”.

If you’d like to learn more here is a good place to start.

That’s all for today, hope you enjoyed it.

noxx

Follow me on Twitter @noxx3xxon

Today we’re going to be deep-diving into a key data structure within the EVM, transaction receipts and their associated event logs. If you’ve coded in Solidity before you’ve likely emitted event logs yourself, they make up a huge portion of the data available to us on-chain data.

In this article, we’ll journey from the block header all the way down to the internals of an event log giving you a comprehensive understanding of what data is available to you and how it was created.

Subscribe now

Why use Logs

Before we begin I want to briefly touch on why we use Event logs as solidity developers.

• As a cheaper alternative to data storage, as long as the contract does not need access to it.

• As a method to trigger web3 applications that are listening out for specific event logs.

EVM nodes are not required to keep logs forever and can remove old logs to save space. Contracts cannot access log storage so they are not required for nodes to execute a contract. Contract storage on the other hand is required for execution so cannot be removed.

Ethereum Block Merkle Roots

In Part 4 of the EVM Deep Dives, we dived into the Ethereum architecture specifically the state Merkle root. The state Merkle root was 1 of 3 Merkle roots contained in the block header. The other 2 were the transaction Merkle root and the transaction receipts Merkle root.

To frame this deep dive we’re going to reference block 15001871 on the Ethereum chain which contains 5 transactions, their associated receipts and the event logs that were emitted. This will help us link any concepts we learn back to a real-world example.

Block Header

We’ll start with the block header. There are 3 components we’re interested in, the “Transaction Root”, the “Receipt Root” and the “Logs Bloom”.

Within the Ethereum client underneath the “Transaction” and “Receipt” roots are Merkle Patricia Tries containing the transaction data & receipt data for all transactions and receipts within that block.

We won’t dive into how a Merkle Patricia Trie works. For the purpose of this article understanding that the node has access to all the transactions and receipts is all we need to know.

Let’s take a look at the real block header for block 15001871 by querying an Ethereum node.

Take note of the block header logsBloom, it is a key data structure that we will refer back to later in the article.

For now let’s start with the data that lies underneath the Transaction Root, the Transaction Trie.

Transaction Trie

The “Transaction Trie” is the data set that generates the transactionsRoot and records the transaction request vectors.

Transaction request vectors are the pieces of information required to execute a transaction.

The fields included in a transaction can be seen below.

• Type = The transaction type (LegacyTxType, AccessListTxType, DynamicFeeTxType).

• ChainId = The EIP155 chain ID of the transaction.

• Data = The input data of the transaction

• AccessList = The access list of the transaction

• Gas = The gas limit of the transaction

• GasPrice = The gas price of the transaction

• GasTipCap = The gasTipCap per gas of the transaction

• GasFeeCap = The fee cap per gas of the transaction

• Value = The ether amount of the transaction

• Nonce = The sender account nonce of the transaction

• To = The recipient address of the transaction. For contract-creation transactions, To returns nil

• RawSignatureValues = The V, R, S signature values of the transaction

Let’s take a look at some real data from a transaction within block 15001871. We’ll use the first transaction 0x311ba3a0affb00510ae3f0a36c5bcd0a48cdb23d803bbc16f128639ffb9e3e58.

Let’s use Geth’s ethclient to query a node. Note ChainId and AccessList both have “omitempty”, which means if the field is empty it will be omitted from the response.

This transaction represents a transfer of USDT to this address 0xec23e787ea25230f74a3da0f515825c1d820f47a.

The to address is the ERC20 USDT contract 0xdac17f958d2ee523a2206206994597c13d831ec7.

If we look at the input data we can see the function signature 0xa9059cbb which corresponds to transfer(address,uint256) , the address to send the USDT to 0xec23e787ea25230f74a3da0f515825c1d820f47a and the amount 0x2b279b8 = 45251000 in decimal or $45.251.

What you might notice about this transaction data structure is that it doesn’t tell us anything about the outcome of the transaction. Was the transaction successful? How much gas did it use? What event logs were emitted?

This is where transaction receipts & the “Receipt Trie” come in.

Receipts Trie

A shopping receipt records the outcome of a transaction. An object in the Receipt Trie does the same thing for an Ethereum transaction along with some additional details.

The questions posed above are what a transaction receipt looks to answer. We’re going to focus on the third question. What event logs were emitted?

Again I’ve queried the chain to get some us some real data. We’re going to look at the transaction receipt for the transaction we looked at above 0x311ba3a0affb00510ae3f0a36c5bcd0a48cdb23d803bbc16f128639ffb9e3e58.

Let’s run through the fields.

• Type = The transaction type (LegacyTxType, AccessListTxType, DynamicFeeTxType).

• PostState (root) = The StateRoot post-execution of the transaction. You may note it’s 0x in the query above this is likely due to EIP-98.

• CumulativeGasUsed = Sum of gasUsed by this transaction and all preceding transactions in the same block.

• Bloom (logsBloom) = Bloom filter for event logs (We’ll dig into this in the next section, remember we saw a logsBloom field in the block header as well)

• Logs = Array of log objects

• TxHash = The transaction hash that the receipt is associated with

• ContractAddress = Address of the deployed contract if the transaction was a contract creation. 0x000…0 if the transaction isn’t a contract creation.

• GasUsed = Gas used by this transaction

• BlockHash = Hash of the block this transaction occurred in

• BlockNumber = Block number for the block this transaction occurred in

• TransactionIndex = Transactions index within the block. The index determines which transaction is executed first. This transaction is at the top of the block and therefore has an index 0.

Now we know what a transaction receipt is composed of we can zoom in on the logsBloom and the log array within the transaction receipt.

Event Logs

We noted in the transaction section that this transaction is a USDT transfer. I’ve grabbed a snippet of code from the USDT contract on Etherscan for us to review.

We can see the Transfer event is declared on line 86 and that 2 of the input parameters have the keyword “indexed”.

You may be wondering what the indexed keyword means. When an event input is “indexed” it enables us to do quick look-ups for a log with that input.

For example with an indexed “from” as seen above I can ask the question get me all event logs of type Transfer with a “from” address of 0x5041ed759dd4afc3a72b8192c143f72f4724081a between blocks X & Y. How this indexing works under the hood will be covered in the next section.

We can also see that this event log is emitted when the transfer function is called on line 138. Note this contract was created with an earlier solidity version hence why the emit keyword is missing.

Again let’s take a look at the real on-chain data for this transaction.

If you refer to the comments in the Log struct you’ll see descriptions for each field. The fields we want to take a closer look at are address, topics and data.

Topics

Let’s start with topics. Topics are indexed values. You’ll notice we have 3 topics in our on-chain query while the Transfer event only has 2 indexed parameters (from & to). This is because the first topic is always the hash of the event signature.

In this case the event signature is Transfer(address,address,uint256). We keccak256 hash this value to give us ddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef. Try it for yourself here (Note input type is text).

This makes sense, if we look at the question we wanted to ask above we wanted to limit it to event logs of type Transfer only. There may be multiple Events that have a from field so by indexing the event signature as well we are able to filter by event type.

We can have a maximum of 4 topics and each topic is 32 bytes in size. We can declare 3 indexed parameters given the first is taken by the event signature.

There is one case when the first topic isn’t the hashed event signature. This is when we declare an anonymous Event. This opens up the possibility of having 4 indexed parameters rather than 3 but we lose the ability to index on the Event name. One other advantage of anonymous events is that they can be cheaper to deploy since they don’t force you to use 1 additional topic.

The other topics are the indexed “from” and “to” values from the Transfer Event.

If the type of an indexed parameter is larger than 32 bytes (i.e. string and bytes), the actual data isn’t stored, but rather the keccak256 digest of the data is stored.

Data

The data section contains the remaining (non-indexed) parameters in the event log. In our case this is just “value” 0x0000000000000000000000000000000000000000000000000000000002b279b8 which is equal to 45251000 in decimal or $45.251.

If we had more they would be appended to the data item. Let’s look at an example where there is more than 1 non-indexed parameter.

In this example, we add an additional “tax” field to the Transfer event. Let’s assume tax is 20% so our tax value should be 20% of 45251000. This is 9050200 in decimal which is 0x8a1858 in hex, the type is uint = uint256 so we’ll need to pad the hex value to 32 bytes.

The resulting data item would be 0x0000000000000000000000000000000000000000000000000000000002b279b800000000000000000000000000000000000000000000000000000000008a1858.

Address

The address field is the address of the contract that emitted the event. One important note on this field is that it will also be indexed despite it not being included in the topics section.

Again this makes sense, the Transfer event is part of the ERC20 standard meaning when we filter logs on the ERC20 Transfer event we’re going to get the transfer events from all ERC20 contracts.

By indexing the contract address we can narrow down the search to a specific contract/token that we are interested in (USDT).

Opcodes

Finally, let’s touch on the LOG opcodes of which there are 5. They go from LOG0 for when no topics are included to LOG4 when 4 topics are included.

LOG3 is what would have been used in our example. It takes in

• offset = memory offset, which represents the start location of the data field input

• length = length of the data to read in from memory

• topic1 = value for topic1

• topic2 = value for topic2

• topic3 = value for topic3

Offset and length define where in memory the data is located for the data section.

Now we understand how the log is structured we can finally answer the question of what happens under the hood when a topic is indexed.

Bloom Filters

The secret to how indexed items enable faster lookup is Bloom filters.

Llimllib has a great definition of what these data structures are.

A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.

The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set.

The base data structure of a Bloom filter is a Bit Vector.

Below is an example of a small bit vector. The white cells represent bits with value 0 while the green cells represent bits with value 1.

These bits were set to 1 by taking some input and hashing it. The value of the resulting hash is used as the bit index for which bit should be updated.

The bit vector above is the result of using 2 different hash functions on the value “ethereum” to get 2 bit indexes.

The hashes represent hexadecimal numbers. To get the index we can take this number and convert it into a value between 0 and 14. There are various ways to do this such as using modulo 14.

See this great site for this example and try it out yourself.

Lookup

Ok, so we have a bloom filter for a transaction which we now understand to be a bit vector. For Ethereum, the inputs that are hashed to determine which bits to update in the bit vector are the address field and the topics of the event log.

Let’s refer back to the logBloom in our transaction receipt. This is the bloom filter for a specific transaction. Remember a transaction can have multiple logs so this represents the addresses/topics of all those logs.

0x00000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010800000000000000000000000000000000000000000000000000000000000000000100000000000000000000008000080000000000000000000000000000000000000000000002002000000000000000000000000004000000000000000000000000000000000000000000000000000800000000000000000000000000000000000000000

If we refer back to our block header we have another logsBloom. This is the bloom filter for all transactions within the block. This is all the addresses/topics in every log of every transaction.

0x0100000000000004000000000000100000000000000000000000000000200000000000000000000000000000000001000000000000000000080008000000000040000000002000000000040800000000000000000000200000000000004800000040000002000000000000000000081000000000000040000000001080020000200001000000000000000000040000004000000000000000000000000010000000008000000000000800008000000800000000008000000200000800000000000000200a000000200000000000100002004000000000000000000000000020000000000080000020000000800000000000004000000000000000080000004000

These bloom filters are represented in hex rather than binary. They are 256 bytes in length which represents a 2048-bit vector.

If we refer to the Llimllib example above our bit vector was 15 in length with bit index 2 and 13 flipped. If we convert that to hex let’s see what we get.

001000000000010 = 0x1002

So while the hex may not look like a bit vector remember that it is under the hood.

Queries

If we remember our earlier query where we asked “get me all event logs of type Transfer with a “from” address of 0x5041ed759dd4afc3a72b8192c143f72f4724081a between blocks X & Y”.

We can take the Event signature topic, which represents the type Transfer along with the from value topic (0x5041ed759dd4afc3a72b8192c143f72f4724081a) and determine which bit indexes in the bloom filter should be set to 1.

If we use the logsBloom in the block header we can check if any of these bits aren’t set to 1. If they aren’t we can know with certainty that there are no logs that match that criteria in the block.

If we find the bits are set we know that a matching log may be in the block. We don’t know with certainty because the block header logsBloom is made up of multiple addresses and topics. It’s possible other event logs have set the matching bits. This is why a bloom filter is a probabilistic data structure.

The bigger the bit vector the less chance of a bit index collision from other logs.

Once we have a matching bloom filter we can query the individual receipt logsBloom using the same methodology. When we get a match we can view the actual log entries to retrieve the object.

By doing this from block X to Y we can quickly find & retrieve all logs that match our criteria.

That’s conceptually how the bloom filter works. Let’s now see the actual implementation used in Ethereum.

Geth Implementation - Bloom Filters

We understand how a bloom filter works but we want to know the exact steps of how we go from the address/topics to the logsBloom and see it done with a real block.

Ok no problem, we can start with the definition in the yellow paper. Don’t worry if it makes no sense right now we’re about to break it down.

The easiest way to show you what this means is to provide an example and reference back to the Geth client implementation.

Here’s the transaction log we looked at above on Etherscan.

We’re going to look at the first topic which is the Event signature 0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef and show how this value is converted into which bit indexes should be updated.

Below is the bloomValues function from the Geth codebase. This is the function takes in data such as the Event signature topic 0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef and give us back the bit indexes that need to be updated in the bloom filter. Let’s run through it.

1. The function takes in the data ie a topic (In our case the event signature topic) and a hashbuf which is just an empty byte array of length 6.

   1. Refer back to the yellow paper snippet, “the first three pairs of bytes in a Keccak-256 hash of the byte sequence”. Three pairs of bytes are equal to 6 bytes which is why our hashbuf is of length 6.

   2. The data for our example is 0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef

2. The sha commands between lines 140 - 144 hashes the data input and load the output into the hashbuf.

   1. The sha output, which uses keccak256, is ada389e1fc24a8587c776340efb91b36e675792ab631816100d55df0b5cf3cbc.

   2. You can verify this using the online keccak 256. (Note make sure you change the input type from text to hex. When using keccak 256 for function signatures the input is of type text whereas here it is of type hex.)

   3. The hasbuf now has contents [ad, a3, 89, e1, fc, 24] (in hex). Remember each hexadecimal character represents 4 bits so 2 characters represent an 8-bit byte.

3. v1 is calculated.

   1. hashbuf [1] = 0xa3 = 10100011 is used with a bitwise AND against 0x7. 0x7 = 00000111 in binary.

   2. A byte is composed of 8 bits, if we want to obtain a bit index we need to ensure the value we get is between 0 and 7 for a zero index array. Using a bitwise AND constrains hashbuf [1] to be a value between 0 and 7. In our case, it is a 3 = 00000011.

   3. This bit index value is used with a bit shift operator to create an 8-bit byte with the flipped bit at the correct index, 00001000.

   4. v1 is the whole byte rather than the actual bit index because this value will later be used with a bitwise OR on the bloom filter. The OR will ensure all corresponding bits in the bloom filter will also be flipped.

4. We now have the byte value but we still need the byte index. Our bloom filter is 256 bytes (2048 bits) in length so we need to know which byte to run the bitwise OR on. The value i1 represents this byte index.

   1. Note we use a big-endian uint16 with our hashbuf, this will constrain it to the first 2 bytes of the array. In our case this represents 0xada3 = 1010110110100011.

   2. We use this value with a bitwise AND against 0x7ff = 0000011111111111. If you count the number of bits set to 1 in 0x7ff you’ll notice there are eleven. From the yellow paper, “It does this through taking the low-order 11 bits of each of the first three pairs”. This yields us the value 0000010110100011.

   3. This value is then bit shifted down by 3. This turns an 11-bit number into an 8-bit number. We want a byte index and our bloom filter has a byte length of 256 so we need our byte index value to be in that range. An 8-bit number can be any value from 0 to 255. In our case, this value is 180.

   4. We calculate our byte index bus using the BloomByteLength which we know is 256 minus our calculated value 180, minus 1. The minus 1 is to keep the result between 0 to 255. This gives us our byte index to update, in this case it’s byte 75.

5. This is telling us to update the bit index 3 (0 index so 4th bit) in the 75th byte of the bloom filter. This can be done by running a bitwise OR of v1 against the 75th byte in the bloom filter.

   1. Note we’ve only covered the first “byte pair” 0xada3, This is done again for “byte pair” 2 and 3. Each address/topic will update 3 bits in the 2048-bit vector. From the yellow paper, “specialised Bloom filter that sets three bits out of 2048”.

   2. “Byte pair” 2 states update bit index 1 in byte 195

   3. “Byte pair” 3 states update bit index 4 in byte 123

   4. If the bit to be changed has already been flipped by another topic it will stay as is otherwise it will be flipped to a 1.

So in conclusion we have determined that the Event signature topic will flip the following bits in the bloom filter.

• bit index 3 in byte 75

• bit index 1 in byte 195

• bit index 4 in byte 123

Take a look at the logBlooms in the transaction receipt convert it to binary and you can verify those bit indexes are set.

I’ve compiled this example into a Github repo evm-by-example for you to play around with. Check out the bloom folder it will definitely help consolidate what you’ve learned in the article.

For those interested in going a little deeper down the rabbit hole have a look at the BloomBits Trie.

Till next time.

noxx

Twitter @noxx3xxon

MEV bots are scampering around the forest floor and we want to decipher what those bots are doing under the hood.

To find these secrets we’re going to have the learn the tools & techniques related to decompiling contract bytecode. This article is going to run you through them and in the process decompile an unverified MEV bot contract.

This is Part 2 of a series detailing MevAlphaLeak’s first foray into the MEV arena. This article follows directly from Part 1 so if you haven’t read that yet I recomment you do so before continuing.

We left off in Part 1 having discovered the encoding of the callInfo variable within the ApeBot Contract and determined that 3 calls are made via the assembly code. These 3 calls were made to 2 unverified contracts.

Our only way to progress is to decompile these contracts to see whats going on.

ApeBot Contract Calldata

The image below shows the calldata for the original wfjizxua( ) call and how it is split up to be used as inputs for subsequent calls. This represents the majority of our findings from Part 1.

The 3 calls target the addresses 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 & 0xf4863028b093fdac9cf7fd67c0df6866ac3c7a60, both of which are unverified contracts.

Before we begin let’s quickly clarify what an unverified contract is. On Etherscan when you create a contract you have the ability to verify it by submitting the code that created the contract.

This enables users to see the solidity code that created the contract. An official project will always do this to be as transparent as possible. When a contract isn’t verified you will instead see this.

You will only have access to the bytecode of the contract which is stored on-chain. You will have no solidity code to reference. As such it can be very hard to understand what is going on within the contract.

Our task is to decompile the bytecode for the unverified contracts to understand what happened in the ApeBot transaction.

Tools & Techniques

Our investigation will use the following tools.

• Online decompiler

  • https://library.dedaub.com

  • There are a variety of other online decompilers

    • https://ethervm.io/decompile

    • https://github.com/eveem-org/panoramix

• Cast cli using --debug mode on the transaction hash

  • https://book.getfoundry.sh/cast/index.html

  • Useful for identitfying decompiled variable values, calldata input etc.

  • cast run --debug --rpc-url $ETH_RPC_URL 0x1126aa5e5b648eebad1c88141e5142cf0a4082e6ccf9fed77d69a190c21724a3

• Transaction visualisation

  • https://versatile.blocksecteam.com/tx/eth/0x0efe3832b85e610fc4ba815f2be3943036a1a1be33cbd8f378a20d20667c1b39

  • The best transaction visualisation tool I’ve come across

• Etherscan

  • Easy access to parity traces, contract byte code, sub calls etc.

The first step in decompiling the bytecode is to use an online decompiler to get a rough outline of the code. Note whatever the decompiler gives us will likely not be 100% accurate. There are occasions where the decompiler will give you incorrect information. This is why you must cross reference with the opcode dubugger.

The first task is to run through the decompiled code line by line and attempt to associate values and meaning to any variables declared. Here’s a list of the things to watch out / do when running through the code,

• If we see a variable that represents bytes 32 - 64 of the calldata, find those exact bytes and note it down in a comment next to that line so you know the actual value

• If we see an address pop up in one of the variables, look it up on Etherscan to see if it’s a known address, does it have a verified contract etc.

• If variables are being passed into verified contract functions we should be able to work out what those variables represent. Lookup it’s inputs in the docs / code.

• Can we identify what each piece of calldata represents.

• If a contract is called multiple times we should check a few transactions - sometimes the calldata won’t make sense till you look at multiple transcations.

• What other contracts does the contract interact with, are they verified If they’re not we have repeat all these step on those contracts also.

Now let’s run through these tools & techniques one by one with the ApeBot example.

Decompiler - Dedaub

We’ll start with the decompiler, I’m using the Dedaub decompiler for this example. Below is a snippet of the decompiled contract 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 that is involved in Call [1] & Call [2].

The Dedaub decompiler uses a function signature lookup table to find any known functions that are called. We can see the address 0x8d12a197cb00d4747a1fe03395095ce2a5cc6819 has the “orderFills” & “balanceOf” function. Let’s have a closer look at it.

Turns out 0x8d12a197cb00d4747a1fe03395095ce2a5cc6819 is the EtherDelta contract. It’s a verified contract which means we can look at the code for each of these functions.

A huge part of understanding unverified contracts is understanding the entities that they interact with. As such we need to take a quick detour to get an overview of what EtherDelta is and how it works.

EtherDelta 2

Etherdelta 2 is an on-chain orderbook exchange, this differs from an “Automated Market Maker” exchange (AMM).

An on-chain orderbook exchange acts much like a off-chain orderbook exchange ie Binance. There are Makers & Takers rather than liquidity pools. A Maker order defines a asset to sell/buy for another asset at a certain price.

In EtherDelta’s case these “Maker” orders can be made on-chain via a transaction or by signing an order transaction on the EtherDelta site.

Note EtherDelta is no longer functional but I assume these signatures would have been stored in an off-chain DB somewhere and “Taker” orders could request the signature of the “Maker” order they want to take.

If a “Maker” order is made on-chain an event is emitted. I did a look-up of the event for the associated address with this ApeBot transaction on-chain and found nothing. As a result, we can infer that the “Maker” order involve in the ApeBot transaction was made via a signature.

Now we have a basic understanding of how EtherDelta works lets jump back to the code. Here’s the full decompiled contract for 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75.

Let’s start with the first call (Call [1]) to to function signature 0x78789120..

Function 0x78789120 - Contract 0xd3…75 - Call [1]

Below is the decompiled code for function 0x78789120. Snippets of the the EtherDelta 2 contract have also been included along with the parity traces for the internal calls (orderFills & balanceOf). Let’s run through it piece by piece.

1. We start with a call to the orderFills function for address 0x8d12a197cb00d4747a1fe03395095ce2a5cc6819 which we know is the EtherDelta 2. OrderFills takes in varg4, varg5 and returns v0 & v1. v0 represents whether the call was successful and v1 the actual returned result. The require of v0 after this call verifies the call was successful. We’ll use the parity traces to determinie varg4 & varg5 but we can see they come from the calldata.

2. The Parity trace for this internal call, here we can see the input data (calldata) for this call

   1. 0x19774d43

      1. Function Signature

   2. 000000000000000000000000aac971235706aa7b49dd3cc2e42a9695d2060da0

      1. This is varg4 from above, it looks like an Ethereum Address, If we look it up on Etherscan we can see it is an EOA address

   3. 6ce7751bd5b9723aa3fa7e4fc4d97865cf912fce880a7797dc0a0da9508f31d9

      1. This is varg5 from above, at the moment we don’t know what the value represents but since this is an input to a function we can look it up in the verified EtherDelta contract.

3. If we check the orderFills code in the EtherDelta contract we can see orderFills is a mapping of a mapping. A “User Account” is mapped to an “Order Hash” which maps to a uint. This uint represents how much of an order has been filled. Using this new information we can determine that 0xaac971235706aa7b49dd3cc2e42a9695d2060da0 is in fact the “Maker User Account Address” and that 0x6ce7751bd5b9723aa3fa7e4fc4d97865cf912fce880a7797dc0a0da9508f31d9 is actually the hash of an order on EtherDelta.

4. varg1 - v1, we know from the previous function that v1 represents the amount of an order that has been filled (Note this is in ETH terms). We can’t be sure yet but it’s likely that varg1 is the total order amount in ETH. The total order amount minus the filled amount would yield the remaining order amount. varg1 is equal to 0x00000000000000000000000000000000000000000000000000f0142dd1c52700 from our calldata and v1 can be found from the output of parity trace [ 2, 1, 0, 3, 0, 2, 1 ] (orderFills) which equals 0x0000000000000000000000000000000000000000000000000000000000000000

5. Call to EtherDelta 2 address on the balanceOf function, takes in varg2 & varg4. Again we’ll use the parity traces.

6. Parity trace for this internal call, calldata

   1. 0xf7888aec

      1. Function signature

   2. 000000000000000000000000bb49a51ee5a66ca3a8cbe529379ba44ba67e6771

      1. This is varg2, again it appears to be an Ethereum address, looking it up on Etherscan shows it’s the CST token address.

   3. 000000000000000000000000aac971235706aa7b49dd3cc2e42a9695d2060da0

      1. This is varg4 which we have already determined is the Maker User Account Address.

7. The balanceOf function in the EtherDelta contract interacts with the tokens mapping. The function returns to us the balance of a specific token for a specific address. So we are checking the CST balance of the “Maker User Account”. Looking at the output from the Parity trace we can see that v5 is equal to 0x00000000000000000000000000000000000000000000005b95329a965952e83d

8. We can see some calculation, v5 * varg1 / varg3 = CST Balance * (Trade Amount in ETH / varg3 ). At this stage we are unsure of what varg3 represents. As a result it’s hard for us to determine what this is trying to calculate.

   1. This is a good example of where the next call (Call [2]) will aid us in detremining this calculation. For now I’m going fill you in on what varg3 is but watch out for when we discover this piece of info in the next call. In reality we would of had to loop back to this item once we had the new info.

   2. varg3 tells us the CST amount on the Maker order. The Maker is willing to swap X CST for Y ETH. varg3 is the X. The calculation above uses X & Y to get the trade ratio 1/2500 ETH/CST. This value is multipled by the Makers CST balance. Therefore the result of this calculation, v5, is the Makers CST balance in ETH terms using the trade ratio as the converstion rate.

9. v3 < v6 = 0xf0142dd1c52700 < 0xf0142dd1dcb4be checks whether the trade amount in ETH is less than the Makers balance in ETH. This ensures the Maker is good to fulfill the trade. In our case this returns True. We can see this If statement has no code inside of it, when looking through the opcodes you can see there is a JUMPI based on this result. It is likely if this condition is not meet the execution will revert. You can confirm this using foundry with --debug & --fork-block-number to create transactions that would explore this section of the code and look at the opcodes that are called in different scenarios.

10. v2 < varg6 = 0xf0142dd1c52700 < 0x05 checks whether the Maker trade amount in ETH is less than the amount we want to trade in ETH. Note that v2 refers to its definition on line 15 rather than line 21 another thing to watch out for with decompiled code. This check makes sense, it’s verifying the open trade amount it big enough to fill our order. In our case, this returns false so we jump to the else statement.

11. Line 27 is not called in the flow of the ApeBot transaction however it is interesting to note that byte 2 of calldata item [0] in our case 0x4b appears to be some custom encoding. It is used when the balance of the maker trade amount is less than the amount we would like to trade.

12. v2 is set to 4200, unsure of what this value represents. The returned value isn’t used in any subsequent calls of the ApeBot transaction.

13. Returns 2 values. The 2 v2’s again represent different values, we can always verify returned values via the parity traces.

    1. v2, v2 = 0x05, 0x1068

This shows us this first call (Call [1]) is ultimately about checking the validity of the trade ie is it possible.

A number of the calldata items weren’t used in this function call or were used without context ie varg3. As such we weren’t able to determine their meaning.

Let’s now look at Call [2] which calls the same contract 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 and see if it can shed any light on these unknown pieces of calldata.

Function 0x401687f4 - Contract 0xd3…75 - Call [2]

Let’s quickly refer back to the calldata from Call [1] and Call [2] at the top of the article. You’ll notice they are the same. Below is the decompiled code for function 0x401687f4, let’s dive in.

1. The 0x401687f4 Function call another internal function 0x74 and passes in the value 4

2. v0 - v11 are declared using the calldata in 32 byte chunks all with a 4 byte offset. The offset comes from, varg0 = 4, which represents the 4 byte function signature in the calldata.

3. A check is done to see if there is a non-zero address in the v0 = calldata item [0]. Note the zero address 0x000…00 represents ETH in EtherDelta so this is effectively asking is the trade in ETH or an ERC20. In our case we have a zero address so we wouldn’t enter this chunk of code. Let’s have a look at what it does anyway. After we enter theres a check on the first byte of v0. If it is zero it indicates the token hasn’t been approved for this contract.

4. This section calls the ERC20 contract for the given token and checks if EtherDelta (0x8d1…19) has any allowance using the allowance( ) function. If it doesn’t it calls the approve( ) function on the ERC20 contract with the EtherDelta address. This allows EtherDelta to move your ERC20 token without any further approval.

5. Next it checks the balance of the ApeBot contract (Since its a delegate call address(this) is the parent caller) for the given ERC20 token by calling balanceOf on the token contract address. It then deposits the full amount (which came from balanceOf) into EtherDelta minus 1 uint of the token. This minus 1 is a gas saving optimisation for future calls. It’s cheaper to change a slot from a non-zero value to another non-zero value than it is to change from a zero value to a non-zero value.

6. Now we’re back to the flow the ApeBot transaction took, this also does an EtherDelta deposit however uses v11 (calldata [11]) = 0x05 as the amount to deposit (5 Wei).

7. The EtherDelta trade function, I’ve included a snippet from the verified contract to show you the function inputs. A lot of the inputs we use are from our calldata, this gives us a chance to work out what each piece of calldata represents. Below is the list of inputs.

   1. TokenGet (calldata [0]) = This is from the makers perspective so the token they would like to get is ETH.

   2. AmountGet (calldata [1]) = The amount the maker would like to recieve in ETH for the full trade.

   3. TokenGive (calldata [2]) = Again this is from the makers perspective so the token they would like to give is CST.

   4. AmountGive (calldata [3]) = The amount the maker would like to give in CST for the full trade.

      1. At this stage we can work out what the trade value was by looking at the ratio of CST/ETH = 0x5b95329a8d5d289800/0xf0142dd1c52700 = 1689404535900000000000/67576181436000000 = 2500 CST → 1 ETH

      2. This is when we could refer back to varg3 in Call [1] to determine what the calculation was doing

   5. Expires (calldata [4]) = The block number the order expires in. After this block number, the order can no longer trade.

   6. Nonce (calldata [5]) = Used by EtherDelta, the nonce is a number you can include with your order to make it relatively unique. This way, if you want to place two otherwise identical orders, they won't have the same hash.

   7. User (calldata [6]) = Maker’s Ethereum address

   8. V (calldata [7]) = ECDSA signature component - used to verify the proposed trade is legitimate ie has been signed by the Maker

   9. R (calldata [8]) = ECDSA signature component - used to verify the proposed trade is legitimate ie has been signed by the Maker

   10. S (calldata [9]) = ECDSA signature component - used to verify the proposed trade is legitimate ie has been signed by the Maker

   11. Amount = Amount the taker would like to trade, note the amount is in amountGet terms which in our case is ETH. The value here is 0x03 which is different from our 0x05 calldata. You’ll notice 0xde0b6b3a7640000/0xdeb5f2f95b78000 = 1000000000000000000/1003000000000000000 = ~0.997 the taker fee for a trade is 0.3%. The calculation above takes your trade input and multiples it by 0.997 so you have enough left over to pay the 0.3% taker fee. 5 Wei * 0.997 = 4.985 but Ethereum doesn’t have floating point numbers so we round down to 4. We then minus one to give us 3 Wei (The minus one is again is related to gas savings).

8. Finally after the trade is made we withdraw our funds. WithdrawToken( ) is used for ERC20 withdraws while withdraw( ) is used for ETH. Since v2 is the CST address we’ll use WithdrawToken( ) again there is a minus one for gas savings.

Now we have gone through both Call [1] and Call [2] we are able to determine what the calldata to the original call represents. Below is that calldata for Call [1] & [2] along with what each value represents.

This concludes the EtherDelta leg of the trade let’s recap what happened.

EtherDelta Leg

• 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 - Call [1]

  • Check to make sure the trade hasn’t been filled

    • 0 ETH of the 0.067576181436 ETH trade had been filled

    • Therefore 0.067576181436 ETH of the trade still available

  • Check to make sure that the Maker address has sufficent tokens in their EtherDelta balance to make the trade (in ETH terms)

    • Maker (0xaac971235706aa7b49dd3cc2e42a9695d2060da0) had a balance of 1689.404535938590369853 CST

    • Convert to ETH terms base on trade ratio (1:2500) yields 0.067576181437543614 ETH

    • Open trade in ETH < Maker Balance in ETH

    • 0.067576181436 ETH < 0.067576181437543614 ETH = True

    • Therefore Maker is has enough funds to cover the trade

  • Check to make sure the proposed trade amount by the taker is less than the open Maker trade amount in ETH

    • Open trade in ETH < Proposed Taker trade in ETH

    • 0.067576181436 ETH < 0.000000000000000005 ETH = False

    • Therefore we will be able to execute the trade for our Taker amount

• 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 - Call [2]

  • Check if the Taker trade is in an ERC20 token or ETH, for us it’s ETH

  • Desposit ETH into EtherDelta from the MevAlphaLeak contract for the trade

    • 5 Wei deposited

  • Excute trade of ETH for CST

    • Proposed trade amount 5 Wei is used in a calculation to determine the amount put into the trade function

      • ((5 * 1000000000000000000) / 1003000000000000000) - 1

      • Yields 3.9850448654, no floating point numbers so rounds down to 3

    • 3 Wei is swapped for 0.000000000000075 CST

    • Taker fee is (0.000000000000000003 * 3000000000000000) / 1000000000000000000 this yields 9e-21

      • 1 Wei = 1e-18 ETH, you cannot go lower than 1 Wei & there are no floating point numbers in the EVM so this rounds down to 0

      • Therefore no taker fee is paid

  • Check CST balance of ApeBot contract on EtherDelta post trade

    • Balance returns 0.000000000000075 CST

  • Withdraw that CST balance from EtherDelta to MevAlphaLeak contract for next leg of the arb

    • Withdraws 0.00000000000007499 CST

There we have it, I’ve taken you through the first 2 calls and shown you the tools & techniques. For those interested in a challenge see if you can decompile the final piece of the puzzle, Call [2] to 0xf4863028b093fdac9cf7fd67c0df6866ac3c7a60 which interacts with Uniswap V2. Here’s the decompiled contract.

Hope you enjoyed, now go unearth some alpha anon!

noxx

Twitter @noxx3xxon

A new entrant is about to enter the fray.

On block 12342861 a Searcher appeared from the shadows. He came with nothing and took his first shot.

This is the story of how MevAlphaLeak entered the MEV arena.

Through The Eyes of a Searcher

The exploration of this story and subsequent deep dive gives us a chance to see the world through the Searcher’s eyes at that point in time.

Our task is the same as a mechanic who is taking apart a car to see how it works. Through the exercise of reverse-engineering the parts, the mechanic can begin to understand the thought process of the engineer/designer.

This is far more valuable than simply copying a strategy. As you collect these searcher perspectives you can then build & innovate on the ideas that have come before you.

What Happened?

We’ll start with a high-level overview of what happened in block 12342861 and then zoom in on a specific part of the deployed contract for the deep dive.

MevAlphaLeak’s first transactions are located at the top of block 12342861, let’s start there for the investigation.

1. This section shows the first 2 transactions from block 12342861 on Etherscan. The first creates an ApeBot Contract and the second interacts with that contract. We can see that mevalphaleak.eth is the EOA that initiated the transactions. Note mevalphaleak.eth was a brand new address with 0 ETH in the account.

2. Shows the created ApeBot Contract on Etherscan. The contract address is 0x666f80a198412bCb987c430831B57AD61facB666. Note that the contract source code has been verified so we can see the solidity code. Typically searchers don’t verify their contracts to obfuscate what is going on.

3. The second transaction in the block interacts with the ApeBot contract. Note that the “Interacted with (To)” section has the ApeBot contract address 0x666f80a198412bCb987c430831B57AD61facB666 as its entry point.

4. By looking at tokens transferred we get a rough idea of what happened. A flashloan was taken from dYdX and then used in an arbitrage opportunity between EtherDelta 2 & Uniswap V2 for the CST token. We can see the flashloan is paid back at the end.

5. There are two transfers at the end of the transaction that are interesting. The first to “Spark Pool” (0x5A0b54D5dc17e0AadC383d2db43B0a0D3E029c4c), a big Ethereum Mining Entity for a value of ~ 0.4497 ETH. The second to 0x90102a92e8E40561f88be66611E5437FEb339e79, which corresponds to the ENS mevalphaleak.eth for ~0.0004 ETH. You’ll soon find out the relevance of these transactions.

6. The Gas Price of the transaction which is set to zero (The contract creation transaction also had a gas price of zero). At this point you should be asking why any miner would accept a zero gas transaction.

Why a miner would accept those transactions relates to the transfer of ~ 0.4497 ETH in [ 5 ] to Spark Pool. Let’s take a look at who was the miner for block 12342861.

We can see that block 12342862 was mined by “Spark Pool”. The same “Spark Pool” that was paid out in the second mevalphaleak.eth transaction. What is going on that allows a 0 ETH account to make multiple transactions at 0 zero gas?

The secret is that these 2 transactions didn’t go the traditional route of into mempool to be picked up by a miner. Instead, they went via the flashbots relay.

Flashbots Relay

I won’t go too much into the details of the Flashbots Relay however will provide a brief synopsis for the purpose of this article.

When searchers are executing MEV strategies they often need to execute multiple transactions one after the other and they usually want to be at the top of the block.

Their search is based on the state of the world at block n-1 where n is the block they want to be included in. An Ethereum block can have hundreds of transactions each of which changes the world state.

Imagine “Searcher X” & “Searcher Y” seeing the same arbitrage opportunity and both submitting arbitrage transactions. When the transactions of a block are executed they are executed procedurally (in order).

If Searcher X’s transaction is above Searcher Y’s then when the node gets to computing Searcher Y’s transaction the Ethereum state will have changed. The arbitrage opportunity will no longer be there and their transaction with either revert or be unprofitable.

This is why it’s so important to have control over the order of transactions in a block.

As I’m sure you know transaction ordering in a block is an essential component of MEV. Before the Flashbots relay, this was typically done via PGA’s (Priority Gas Auctions) or by being a miner.

Flashbots saw this problem and looked to create a solution. They altered the Geth codebase to create mev-geth an Ethereum client that enabled searchers to submit bundles of transactions to the miners via the Flashbots Relay.

The Miner would look at which proposal gave them the biggest reward and place this bundle at the top of the block. This reward could be paid out in gas or with a “coinbase.transfer” which sends the specified amount of ETH to the miner of the block.

Unlike the mempool the relay is private to everyone except Flashbots. You are able to sign mutliple transactions/bundles and you won’t pay any gas unless they are executed.

A cool feature of the Flashbots Relay is their API which shows us for each block whether any bundles were included via the relay.

Let’s take a look at block 12342861.

We can see that MevAlphaLeaks transactions went via the Flashbots Relay which explains why he was able to use a 0 ETH address and the coinbase.transfer to Spark Pool.

Ok, let’s do a quick review of what we’ve learned so far before the deep dive.

• MevAlphaLeak submitted a bundle of transactions via the flashbots relay

• The first transaction created the ApeBot contract

• The second transaction interacted with the ApeBot contract to execute an arbitrage

• The arbitrage did the following (Note I have ommitted the WETH / ETH conversions that take place throughout the arbitrage)

  • Flashloan From dYdX of WETH

  • Exchange WETH for CST on EtherDelta 2

  • Exchange CST for ETH on Uniswap V2

  • Pay back WETH from dYdX Flashloan

• At the end of the second transaction, MevAlphaLeak pays the miner via the conbase.transfer method 0.449293093766000097 ETH

• MevAlphaLeak leaves with a contract deployed for free and  0.000449742836602602 ETH

Now let’s take a deep dive into the ApeBot contract.

A warning, the next section is heavy on the code side and assumes a fair amount of EVM knowledge from the reader.

ApeBot Contract

Now we will investigate the ApeBot Contract. We’ll briefly touch on the entry point of the contract and then zoom in on the block of assembly code that executes the arbitrage.

We can start with a high-level overview of the contract flow and identify where the assembly code we’d like to inspect is located. Note all the code snippets come from the verified contract on Etherscan so the line numbers should match up with that.

1. We start by calling wfjizxua(uint256,uint256[]). If you’re wondering what is with the strange name try hashing this to get its function signature. It returns the signature 0x00000000 which is more gas efficient than having a function signature that is non zero (A zero byte in calldata costs 4 gas whereas a non-zero byte costs 16 gas). We pass in actionFlags & actionData to the function.

2. This data (actionFlags & actionData) is in turn passed to ape(uint256,uint256[]). This is a permissionless function that allows a user to execute any arbitrary logic. This means you can have a single contract and target various DEX’s based on your call data rather than writing custom contracts for each. You’ll see how this function is generalised later in the article.

3. The “data” variable in the ape function which corresponds to the “actionData” from the original wfjizxua call is looped over. Some assembly code is executed on each loop. Let’s see what happens.

First, we need to look at the calldata for the ApeBot contract call.

How are we to decipher what this data means? We can start with the function signature that tells us a uint256 & unit256[ ] is passed in.

A unit256[ ] is a dynamic type. The encoding for dynamic types is different from static types. For static types like “uint256 actionFlags” we pass the values directly into the calldata. We can see this value at calldata item [0] in the image above.

For dynamic types like “unit256[] actionData”, we instead pass in the offset in bytes to the start of their data area, measured from the start of the value encoding. In our case, this can be seen at calldata item [1] and has a value 0x40. This is equal to 64 in decimal and tells us the data area for the array starts 64 bytes into our calldata.

An offset of 64 bytes means calldata item [2] signals the start of the data area. The first item in this data area [2] declares the length of the array, 0x25 = 37 decimal.

After this, we have 37 items from [3] to [39]. These items are the actual values in the uint256[ ] array.

These groupings are useful but we still have no idea how this calldata is used. To determine this we need to look at the assembly code and work backward from there.

I’ve highlighted in green the first item in the actual array, calldata [3], it will be apparent why when we look into the assembly code.

Assembly Code

What better place to start than the first line of the assembly code. The image below highlights this (line 219) along with some excerpts from the foundry debugger.

At the beginning of the assembly, a variable callInfo is created by running an MLOAD on memory location 0xa0. The data at this memory location, 100000000c78789120020674d380f7e1dc7408aa007744ed3af390f8a47f9b75, is the same as the calldata [3] item highlighted in green in the previous section.

Let’s now look at where this callInfo variable is used in the rest of the code.

Above is the full “Assembly code”. The highlighted boxes in the assembly code show where callInfo is being used. We can see that there are a number of bitmasks being used on callInfo to extract values and execute logic based on what is returned. If you’re not aware of how bitmasks work check out Part 3 of the EVM Deep Dives which looks at how this technique is used in storage slot packing.

By looking at the assembly we can determine that this value, 100000000c78789120020674d380f7e1dc7408aa007744ed3af390f8a47f9b75, is actually a custom encoded set of 32 bytes.

Below is the decoding of it. Note the numbers ( [1] etc.) in the assembly code image above correspond to the numbers in the image below so you can cross-reference.

1. callLength - encoded in bytes 4 - 5, the number of items to ingest from the calldata for the subsequent delegatecall / call

   1. 0x000c = 12 decimal

2. Function signature - encoded in bytes 6 - 9, the function signature for the subsequent delegatecall / call

   1. 0x78789120, we can look this up in the Ethereum Signature Database. It returns nothing, this indicates the associated contract may be unverified

3. callContract - encoded in bytes 13 - 32, the contract address for the subsequent delegatecall / call

   1.  0xd380f7e1dc7408aa007744ed3af390f8a47f9b75, we can look at this address on Etherscan. The contract hasn’t been verified so we’ll have to work with the contract bytecode.

4. Delegate Call or Call - encoded in byte 1, whether the subsequent call should be a DELEGATECALL or a CALL

   1. 0x10, execute as a DELEGATECALL

5. Gas Amount for Call - encoded in bytes 10 - 12, how much gas is allocated for the subsequent delegatecall / call

   1. 0x020674 = 132724 decimal

6. Should the returned data be used in the next call - encoded in byte 3, whether the returned data is needed for the next loop

   1. 0x00, the return data is not needed

To reinforce our understanding of how these encoded values are used we’ll quickly run through the logic that uses them and determines the execution path.

1. This section of the code checks for a non-zero function signature. Note how lines 226 & 234 differ. Both update the callLength but when the function signature is non-zero an extra 4 is added to the callLength. This is for the 4-byte function signature. The same applies to lines 228 & 236, both are for loops that loop over the data but the for loop on line 236 starts at 4 while the loop on 228 starts at 0. Again this is to account for the 4-byte function signature.

2. This section deals with the callLength. When you make a DELEGATECALL or CALL you have to specify where in memory the calldata/input for that call is located. This for loop is storing the calldata items in memory in anticipation of that call. It loads in the number of items from the calldata specified in the encoded data. If you’re unsure of how the DELEGATECALL opcode works take a look at Part 5 of the EVM Deep Dives which does an in-depth review.

3. This section looks at the DELEGATECALL/CALL byte, if the byte is 0x10 it executes a delegatecall on the “callContract” and for anything else, a call is made.

4. This looks at byte 3 and determines whether the returned data should be used in the next loop. For it to be used in the next loop it needs to be stored somewhere. If byte 3 is non-zero an MSTORE is used to save it in memory so it can be accessed later.

Now that we understand callInfo’s encoding and where it’s located in the calldata we can revisit the full calldata for the arbitrage transaction.

We’re going to organise the calldata into sections based on any encoded callInfos we can find.

We’re also going to link these sections to the parity traces of the transaction to determine which calldata is used for which call.

Parity traces enable us to see all the internal contract calls for a given transaction. This is extremely useful when debugging & attempting to piece together what happened on-chain.

The traces have a traceAddress. TraceAddresses have the notation [ 2, 1, 0, 3, 0, 2 ] where the number of items in the array shows you the depth of the call and the value of each item shows you the index of that call at that depth (ie its order position relative to other calls at that depth).

Here’s a quick summary of the notation from the OpenEthereum (Parity) website.

Now let’s dig into the calldata and the associated parity traces. There’s a lot going on in the image below but I promise it’s not too complicated.

The 3 sections in the parity traces above represent the 3 calls that execute the arbitrage between EtherDelta 2 and Uniswap V2.

The calldata has been grouped to show you what calldata was passed to the top call in each of parity trace groupings ([ 2, 1, 0, 3, 0, 2 ], [ 2, 1, 0, 3, 0, 3 ] & [ 2, 1, 0, 3, 0, 4 ]).

At the top of each calldata section is the custom encoded “callInfo” value, see calldata items [3], [17] & [31]. The groupings were determined by looking at the callInfo data along with the assembly code.

The parity traces show us that multiple subsequent calls are being made in each section. Two in the first call, five in the second call and ten in the third call.

Let’s have a closer look at the 3 core calls.

1. The first call ([ 2, 1, 0, 3, 0, 2 ]) uses calldata item [3] as its encoded callInfo. We looked at this exact callInfo earlier. The encoding tells us to make a DELEGATECALL to address 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 and take the next 12 items from the calldata as input.

   1. Note the first item after the callInfo in the calldata ([4]) is 0x000…0. This represents the Wei amount for the call. You won’t see it being used in the delegatecall flow of the assembly since the DELEGATECALL opcode doesn’t take in a value. You can however see it being accessed in the call flow on line 260 of the assembly code. Note this “Wei value” is not included in the “next 12 items” from the calldata. Therefore the “next 12 items” runs from [5] to [16]. This applies to all 3 core calls.

2. If we inspect the parity traces of the transaction on Etherscan, specifically, Action [17] TraceAddress [ 2, 1, 0, 3, 0, 2 ] we can see that the values encoded in the callInfo match what is in the trace.

   1. The “To” address = 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75

   2. CallType = delegatecall

   3. Gas = 132724 (Allocated Gas in decimal)

   4. Input Data matches the 12 calldata items highlighted with a prefix of the encoded function signature

3. The second call ([ 2, 1, 0, 3, 0, 3 ]) uses calldata item [17] as its callInfo. It makes a DELEGATECALL to the same address 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 but with a different function signature 0x401687f4. Again the next 12 items from the calldata are used as input along with the function signature.

4. The third call ([ 2, 1, 0, 3, 0, 4 ]) uses calldata item [31] as its callInfo. It makes a DELEGATECALL to a different address 0xf4863028b093fdac9cf7fd67c0df6866ac3c7a60 with the function signature 0x0fd72adb. The encoded callLength is 7 so the next 7 items from the calldata are used as the input along with function signature.

These 3 calls represent 3 loops of our assembly code. The first 2 calls handle the EtherDelta leg of the arb while the third executes the Uniswap section.

The 2 contracts the calls interact with 0xd380f7e1dc7408aa007744ed3af390f8a47f9b75 & 0xf4863028b093fdac9cf7fd67c0df6866ac3c7a60 are both unverified contracts.

This means we’re going to need to decompile their bytecode and debug via foundry at the opcode level to understand what is going on.

But that one is for next time.

Hope you enjoyed!

noxx

Twitter @noxx3xxon

Today we’re going to take a close look at the opcodes CALL & DELEGATECALL. This episode builds on concepts covered in Part 2, Part 3 & Part 4, I recommend reading those if you haven’t yet.

We’re going to cover how these opcodes work at the solidity level, the EVM level and the Geth client level to give you a complete understanding.

Before we dig into each of these we need to first understand the concept of a contract execution context.

Execution Context

When the EVM executes a smart contract, a context is created for it. The context consists of the following.

• The Code

  • The contract bytecode which is immutable, it is stored on-chain and referenced using a contract address.

• The Stack

  • The call stack, an empty stack is initialised for each EVM contract execution.

• The Memory

  • The contract memory, a clean memory is initialised for each EVM contract execution.

• The Storage

  • The contract storage which is persisted across executions, it is stored on-chain and is referenced via a contract address and its storage slot.

• The Call Data

  • The input data for a transaction.

• The Return Data

  • The data returned from a contract function call.

Keep these items in your mind as we proceed through the article.

We will start with a DELEGATECALL Solidity example from the Smart Contract Programmer and reference it throughout.

Solidity Example

The diagram below shows the execution of two function calls on the same contract, one which uses DELEGATECALL and the other which uses CALL.

We’ll run through both and compare how they differ.

Let’s start by noting the constants in this interaction (Note if you recreate in remix your addresses will likely be different.)

We have two contracts, Contract A & B and an EOA.

• EOA Address = 0x5B38Da6a701c568545dCfcB03FcB875f56beddC4

• Contract A Address = 0x7b96aF9Bd211cBf6BA5b0dd53aa61Dc5806b6AcE

• Contract B Address = 0x3328358128832A260C76A4141e19E2A943CD4B6D

We’re going to call the 2 functions in Contract A, setVarsDelegateCall & setVarsCall.

We will pass in the parameters Contract B Address, a uint of 12 and a Wei value of 1000000000000000000 (1 ETH).

Delegate Call

1. An EOA address calls Contract A’s setVarsDelegateCall with Contract B’s address, uint 12 and value 1000000000000000000 Wei. This in turn makes a delegatecall to Contract B’s setVars(uint256) function with uint 12.

2. The delegatecall executes the setVars(uint256) code from Contract B but updates Contract A’s storage. The execution has the same storage, msg.sender & msg.value as its parent call setVarsDelegateCall.

3. The values are set in Contract A’s storage, 12 for num, 0x5b38…c4 for sender (EOA Address) & 1000000000000000000 for value. Despite setVars(uint256) being called by Contract A with no value when we check msg.sender & msg.value we get the values from the original setVarsDelegateCall.

After the execution of this function we can check the num, sender & value state items of Contract A & B. We will see that none of the values are initialised in Contract B while all are set in Contract A.

Call

1. An EOA address calls Contract A’s setVarsCall with Contract B’s address, uint 12 and value 1000000000000000000 Wei. This in turn makes a call to Contract B’s setVars(uint256) function with uint 12.

2. The standard call executes the setVars(uint256) code from Contract B with no alterations to storage, msg.sender, msg.value.

3. The values are set in Contract B’s storage, 12 for num, 0x7b96…ce for sender (Contract A Address) & 0 for value. These values correspond with what we expect since setVars(uint256) was called from Contract A and no Wei value was passed into the setVars(uint256) (the 1000000000000000000 Wei was passed into the parent call setVarsCall)

Again after the execution of this function we can check the num, sender & value state items of Contract A & B. We see that the reverse is true this time, none of the values are initialised in Contract A while all are set in Contract B.

Conceptually a “Delegate Call” effectively allows you to copy and paste a function from another contract into your contract. It will be run as if it were executed by your contract and will have access to the same storage, msg.sender & msg.value.

Delegate Call & Storage Layout

In the above example, you may have noticed the comment in the code for Contract B on line 5 stating “NOTE: storage layout must be the same as contract A”.

Remember a function in a contract maps to some static bytecode that is calculated at compile time.

When we look at solidity code we think in terms of variables. We see the state variables num, sender & value.

The compiled bytecode doesn’t see these variables it instead sees storage slots. Declared state variables are mapped to storage slots (If you’re unsure how this works check out Part 3).

If we look at Contract B setVars(uint256) specifically “num = _num” this is saying store value _num into storage slot 0.

When we look at contracts involved in a DELEGATECALL don’t think about the mapping of num → num, sender → sender. That’s not how it works at the bytecode level.

We need to think in terms of mapping slot 0 → slot 0, slot 1 → slot 1

The diagram below shows this mapping, along with the corresponding variable names.

Think what would happen if we were to change the order in which our state variables are defined.

It would change their storage slot positions and subsequently the bytecode associated with the setVars(uint256) function.

If we updated Contract B by switching lines 6 and 8 we would be declaring the “value” state variable first and the “num” state variable last.

This means line 11 “num = _num” in setVars(uint256) would now say store value _num into storage slot 2. Line 13 “value = msg.value” would now say store msg.value in storage slot 0.

This means our variable mappings between Contract A & B would no longer match relative to their storage slots.

When we run DELEGATECALL the “num” value is going to be stored in storage slot 2 for Contract A which maps to the “value” state variable. The same applies for when “value” is stored its going to update slot 0 which maps to the “num” state variable.

This is one of the reasons DELEGATECALL can be dangerous.

Above we’ve accidentally replaced the “num” state variable with the “value” state variable and vice versa.

A Hacker won’t be accidentally changing your state variables. They will be conducting a targeted attack.

Imagine we have a contract that makes an open delegatecall and we know the slot location where the owner of that contract is stored.

We would be able to construct a contract with a state variable layout and function that allows us to update the “owner” slot location with a different address. This would enable us to claim ownership of that contract.

If you’re interested in how these hacks work, take a look at these 2 Ethernaut problems, you have the required knowledge to solve them.

• Ethernaut Level 6 - Delegation

• Ethernaut Level 16 - Preservation

Now let’s jump into the opcodes.

Opcodes

We have a rough idea of how DELEGATECALL works so let’s have a look at the opcodes for DELEGATECALL & CALL.

For DELEGATECALL we have the following input variables;

• gas: amount of gas to send to the sub context to execute. The gas that is not used by the sub context is returned to this one.

• address: the account which context to execute.

• argsOffset: byte offset in the memory in bytes, the calldata of the sub context.

• argsSize: byte size to copy (size of the calldata).

• retOffset: byte offset in the memory in bytes, where to store the return data of the sub context.

• retSize: byte size to copy (size of the return data).

CALL has exactly the same input variables with one additional value.

• value: value in wei to send to the account. (CALL only)

Delegate call doesn’t require a value input as it is inherited from its parent call. Recall when we mentioned that the execution context has the same storage, msg.sender & msg.value as its parent call.

Both have one output variable “success” which is 0 if the sub context reverted otherwise it returns 1.

Delegatecall will return success ‘True’ if it is called on an address that is not a contract and so has no code. This can cause bugs if code expects delegatecall functions to return `False` when they can’t execute.

To understand the opcode let’s inspect how DELEGATECALL was executed for the earlier example with Contracts A & B.

DELEGATECALL Opcode Inspection With Remix

Below is a snapshot from the Remix IDE as the DELEGATECALL opcode was called. It corresponds to lines 24 - 26 in the earlier code snippet.

We will look at the items on the stack & memory and see how these values determine the call data that is passed into the DELEGATECALL.

We’ll work our way from the opcode → stack → memory → calldata.

Let’s run through this

1. On line 24 of the Solidity code, a “delegatecall” is made to Contract B setVars(unit256) with a value of 12. This results in the DELEGATECALL opcode being executed.

2. The DELEGATECALL opcode takes 6 inputs, gas, address, argsOffset, argsSize, retOffset & retSize which are taken off the stack.

   1. Gas = 0x45eb

   2. Address = 0x3328358128832A260C76A4141e19E2A943CD4B6D (Address for Contract B)

   3. ArgsOffset = 0xc4

   4. ArgsSize = 0x24

   5. RetOffset = 0xc4

   6. RetSize = 0x00

3. Let’s focus on the argsOffset & argsSize which are the calldata that will be passed to Contract B. These 2 values order us to go to memory location 0xc4 and copy the next 0x24 (36 in Decimal) bytes to get our calldata.

4. This yields 0x6466414b000000000000000000000000000000000000000000000000000000000000000c which can be split into 0x6466414b which is the function signature for setVars(uint256) and 0x000000000000000000000000000000000000000000000000000000000000000c which is 12 in decimal and represents our input value for num.

5. This value maps to what is produced by line 25 in the Solidity code abi.encodeWithSignature("setVars(uint256)", _num)

Note the retSize is equal to 0 since setVars(uint256) doesn’t return anything. If it did the retSize value would be updated and the returned value would be stored at the retOffset.

This should give you a good idea of what the opcode is doing under the hood and enable you to connect it back to a real Solidity example.

Now let’s look at the Geth Client Implementation.

A warning, the next section is heavy on the code side.

Geth Implementation

I’m going to focus on a specific part of DELEGATECALL within Geth.

The goal is to show you how the DELEGATECALL opcode differs from the CALL opcode at the storage scope level and how this relates to the SLOAD opcode.

The diagram below looks intimidating but we will run through it step by step. By the end, you’ll understand the subtle implementation differences between DELEGATECALL and CALL in Geth.

We have the DELEGATECALL & CALL opcodes labeled on the left-hand side and the SLOAD opcode labeled bottom right. Let’s see how they’re connected.

1. Note there are two [ 1 ] ‘s on the diagram. These are the Geth functions for the opcodes DELEGATECALL & CALL found in instructions.go. We can see the values we discussed earlier being popped off the stack into variables. Later in the function, we see that interpreter.evm.DeleagteCall and interpreter.evm.Call are called with the values off the stack, the “to address” and the current contract scope.

2. Note there are two [ 2 ] ‘s on the diagram. Both the evm.DelegateCall & evm.Call functions are executed (found in evm.go). I’ve omitted sections of the functions to focus on the NewContract function call which is creating a new contract context for us to execute in.

3. Note there are two [ 3 ] ‘s on the diagram. The NewContract function call for evm.DelegateCall & evm.Call are very similar except for 2 items.

   1. In DelegateCall the value parameter is set to nil, remember it inherits its value from its parent context so doesn’t take in this parameter.

   2. The second input into the NewContract functions are different. In evm.DelegateCall caller.Address( ) is passed in (Contract A address). In evm.Call addrCopy is passed in which is equal to the toAddr from the opCall function (Contract B address). This difference will be very important later. Note both are of type AccountRef.

4. DelegateCall’s NewContract will return a Contract struct. The AsDelegate( ) function is called (found in contract.go). It sets the msg.sender & msg.value to that of the original call (EOA address & 1000000000000000000 Wei). This is not done on the Call implementation.

5. Both evm.DelegateCall & evm.Call execute the NewContract function (found in contract.go). Note “object ContractRef” is the second input variable for NewContract which maps to the AccountRef’s we discussed in [ 3 ]

6. This “object ContractRef” is used along with a number of other values to initialise a Contract. The “object ContractRef” is mapped to “self” in the Contract struct.

7. The Contract struct (found in contract.go) has the field “self” which is what we are interested in. You can see some of the other fields that relate to items we discussed earlier when talking about contract execution context.

8. We are now jumping to the SLOAD opcode implementation in Geth (found in instructions.go). It runs GetState on scope.Contract.Address( ). The “Contract” within this statement refers to the Contract struct in [ 7 ].

9. The implementation of Address( ) for a Contract object (found in contract.go). It in turn calls self.Address( ).

10. Self is of type ContractRef so type ContractRef must have an Address( ) function.

11. ContractRef is an interface (found in contract.go) and defines that for something to be a ContractRef it must implement an Address( ) function that returns a common.Address (common.Address is defined as a byte array of length 20, the length of an Ethereum address).

12. If we refer back to section [ 3 ] we discussed the different AccountRef values in evm.DelegateCall and evm.Call which became “self” on the Contract objects. We can see that AccountRef is actually just a common.Address but it implements an Address( ) function. AccountRef, therefore, meets the ContractRef interface requirements.

13. The Address( ) function for a AccountRef just casts the AccountRef to an common.Address which in our case would be Contract A’s address for evm.DelegateCall & Contract B’s address for evm.Call. This means the SLOAD opcode we looked at in [ 8 ] is looking at Contract A’s storage for the DELEGATECALL opcode and Contract B’s storage for the CALL opcode.

Seeing the Geth implementation shows you how the storage, msg.sender & msg.value are altered for a DelegateCall. You should now have a comprehensive understanding of the DELEGATECALL opcode.

You made it congrats! Until next time.

noxx

Twitter @noxx3xxon

To do this we’re going to inspect the Ethereum chain architecture, its data structures and peer inside the internals of the “Go Ethereum” (Geth) client.

We’ll start with the data contained in an Ethereum block and work backward to a specific contract’s storage. We’ll finish by taking a look at the SSTORE & SLOAD opcodes implementations in Geth.

This will serve multiple purposes. It will introduce you to the Geth codebase, teach you about the Ethereum “World State” and further your overall understanding of the EVM.

Subscribe now

Ethereum Architecture

We’ll start with the image below. Do not be intimidated, by the end of this article you’ll understand exactly how this all fits together. This represents the Ethereum architecture and the data contained within the Ethereum chain.

Rather than look at the diagram as a whole we’ll analyse it piece by piece. For now, let’s focus on the “Block N Header” and the fields it contains.

Block Header

The Block Header contains the key information about an Ethereum block. Below is the “Block N Header” snippet along with its data fields. Take a look at this block 14698834 on etherscan and see if you can see some of the fields in the diagram.

The block header contains the following fields:

• Prev Hash - Keccak hash of the parent block

• Nonce - Used in proof of work computation

• Timestamp - Scale value of the output of UNIX time( )

• Uncles Hash - Keccak hash for uncled blocks

• Beneficiary - Beneficiary address, mining fee recipient

• LogsBloom - Bloom filter of two fields, log address & log topic in the receipts

• Difficulty - Scalar value of the difficulty of the previous block

• Extra Data - 32 byte data relevant to this block

• Block Num - Scalar value of the number of ancestor blocks

• Gas Limit - Scalar value of the current limit of gas usage per block

• Gas Used - Scalar value of the total gas spent on transactions in this block

• Mix Hash - 256-bit value used with a nonce to prove proof of work computation

• State Root - Keccak Hash of the root node of state trie (post-execution)

• Transaction Root - Keccak Hash of the root node of transaction trie

• Receipt Root - Keccak Hash of the root node of receipt trie

Let’s see how these fields map to what is in the Geth client codebase. We’ll look at the “Header” struct defined in block.go which represents a block header.

We can see the values stated within the codebase match our conceptual diagram. Our goal is to get from the block header down to the storage of an individual contract.

To do so we need to focus on the “State Root” field of the block header highlighted in red.

State Root

The “State Root” acts like a merkle root in that it is a hash that is dependent on all the pieces of data that lie underneath it. If any piece of data changes the root will also change.

The data structure underneath the “State Root” is a Merkle Patricia Trie which stores a key-value pair for every Ethereum account on the network, where the key is an Ethereum address and the value is the Ethereum account object.

In actuality, the key is the hash of the Ethereum address and the value is the RLP encoded Ethereum account however we can ignore this for now.

Below is the section of the “Ethereum Architecture” diagram that represents the Merkel Patricia Trie for the “State Root”.

The Merkle Patricia Trie is a non-trival data structure so we won’t deep dive into it in this article. Instead, we can instead keep the key-value mapping model of address to the Ethereum account.

If you are interested in the Merkle Patricia Trie I recommend checking out this excellent introductory article.

Next, let’s inspect the Ethereum account value that the Ethereum addresses are mapping to.

Ethereum Account

The Ethereum account is the consensus representation for an Ethereum address. It is made up of 4 items.

• Nonce - Number of transactions made by the account

• Balance - Balance of the account in Wei

• Code Hash - Hash of the bytecode stored in the contract/account

• Storage Root - Keccak Hash of the root node of storage trie (post-execution)

We see these in this snippet from the original Ethereum architecture image.

Again we can jump into the Geth codebase and find the corresponding file state_account.go and the struct that defines an “Ethereum account” referred to as a StateAccount.

Again we can see the values stated within the codebase match our conceptual diagram.

Next, we need to zoom in on the “Storage Root” field within the Ethereum account.

Storage Root

The storage root is much like the state root in that underneath it is another Merkle Patricia trie.

The difference is that this time the keys are the storage slots and the values are the data in each slot.

Again in actuality, there is RLP encoding of the values & hashing of the keys that goes on as part of this process.

Below is the section of the “Ethereum Architecture” diagram that represents the Merkel Patricia Trie for the “Storage Root”.

As before the “Storage Root” is a merkle root hash that will be impacted if any of the underlying data (contract storage) changes.

Any change in contract storage will impact the “Storage Root” which in turn will impact the “State Root” which in turn will impact the “Block Header”.

At this stage of the article, we’ve achieved our goal of taking you from an Ethereum block down to an individual contract’s storage.

The next part of the article is a deep dive into the Geth codebase. We will look briefly at how the contract storage is initialised and what happens when the SSTORE & SLOAD opcodes are called.

This will help you make the mental connections from what we’ve discussed so far back to your solidity code and the underlying storage opcodes.

A warning, the next section is heavy on the code side and assumes the ability to read code

StateDB → stateObject → StateAccount

To get us started we need a brand new contract. A brand new contract means a brand new StateAccount.

Before we start there are 3 structures we’re going to be interfacing with:

• StateAccount

  • StateAccount is the Ethereum consensus representation of “Ethereum accounts”.

• stateObject

  • stateObject represents an “Ethereum account” that is being modified.

• StateDB

  • StateDB structs within the Ethereum protocol are used to store anything within the merkle trie. It's the general query interface to retrieve: Contracts & Ethereum Accounts

Let’s look at how these 3 items are interconnected and how they relate back to what we have been discussing.

1. StateDB struct, we can see it has a stateObjects field which is a mapping of addresses to stateObjects (Remember the “State Root” Merkle Patricia Trie was a mapping of Ethereum addresses to Ethereum accounts and that a stateObject is an Ethereum account that is being modified)

2. stateObject struct, we can see it has a data field which is of type StateAccount (Remember that earlier in the article we mapped an Ethereum account to StateAccount in Geth)

3. StateAccount struct, we have seen this struct already, it represents an Ethereum account and the Root field represents the “Storage Root” we discussed earlier

At this stage some pieces of the puzzle are starting to fit together. Now we have the context to see how a new “Ethereum account” (StateAccount) is initialised.

Initalising A New Ethereum Account (StateAccount)

To create a new StateAccount we’ll need to interact with the statedb.go file and the StateDB struct.

StateDB has a createObject function which creates a new stateObject and passes a blank StateAccount into it. This is effectively creating a blank “Ethereum account”.

The below diagram details the code flow.

1. StateDB has a createObject function which takes in a Ethereum address and returns a stateObject (Remember a stateObject represents an Ethereum account that is being modified.)

2. The createObject function calls the newObject function passing in the stateDB, the address and an empty StateAccount (Remember a StateAccount = Ethereum account) it returns a stateObject

3. The return statement of the newObject function, we can see there are a number of fields associated with the stateObject, address, data, dirtyStorage etc.

4. The stateObject data field maps to the empty StateAccount input in the function - Note nil values are replaced in the StateAccount in lines 103 - 111

5. The stateObject created that contains the initialised StateAccount as a data field is returned

Ok, so we have an empty stateAccount, what do we want to do next?

We want to store some data and to do that we need to use the SSTORE opcode.

SSTORE

Before we dive into the SSTORE implementation in Geth let’s quickly remind ourselves of what SSTORE does.

It pops 2 values off the stack, first the 32-byte key second the 32-byte value and stores that value at the specified storage slot defined by the key.

Below is the Geth code flow for the SSTORE opcode let’s take a look at what it does.

1. We start with the instructions.go file which defines all the EVM opcodes. Within this file, we find the “opSstore” function.

2. The scope variable which is passed into the function contains the contract context such as the stack, memory etc. We pop 2 values off the stack and label them loc (short for location) and val (short for value).

3. The 2 values popped off the stack are then used as inputs along with the contract address for the SetState function associated with the StateDB. The SetState function uses the contract address to check if a stateObject exists for that contract, if it doesn’t it will create one. It then calls SetState on that stateObject passing in the StateDB db, the key and the value.

4. The stateObject SetState function does some checks on fake storage and whether the value has changed and then runs a journal append.

5. If you look at the code comment about the journal struct you’ll see that the journal is used to track state modifications so that they can be reverted in the case of an execution exception or request for reversal.

6. After the journal is updated the storageObject setState function is called with the key and value. This updates the storageObjects dirtyStorage.

Ok, so we have updated the stateObject’s dirtyStorage with the key and value. What does that actually mean and how does it relate to everything we’ve learned so far.

Let’s start with the dirtyStorage definition within the code.

1. dirtyStorage is defined within the stateObject struct, it is of type Storage and is described as “Storage entries that have been modified in the current transaction execution”

2. The Storage type which corresponds to dirtyStorage is a simple mapping of common.Hash to common.Hash

3. The Hash type is simply a byte array of length HashLength

4. HashLength is a constant defined as 32

This should sound familiar to you a 32-byte key mapping to a 32-byte value. It is exactly how we conceptually viewed contract storage in Part 3 of the EVM Deep Dives.

You may have noticed pendingStorage & originStorage in the stateObject just above the dirtyStorage field. They are all related, during finalisation dirtyStorage is copied across to pendingStorage which in turn is copied across to originStorage when the trie is updated.

After the trie is updated the “Storage Root” of the StateAccount will also be updated during a StateDB “Commit”. This writes the new state to the underlying in-memory trie database.

Now onto the last piece of the puzzle, SLOAD.

SLOAD

Again let’s quickly remind ourselves of what SLOAD does.

It pops 1 value off the stack, the 32-byte key, which represents the storage slot and returns the 32-byte value stored there.

Below is the Geth code flow for the SLOAD opcode let’s take a look at what it does

1. Again we start with the instructions.go file where we can find the “opSload” function. We grab the location (storage slot) for the SLOAD from the top of the stack using peek.

2. We call the GetState function on the StateDB passing in the contract address and the storage location. GetState gets the stateObject associated with that contract address. If the stateObject is not nil it calls GetState on that stateObject.

3. The GetState function on the stateObject does a check on fakeStorage and then does a check on dirtyStorage

4. If dirtyStorage exists return the value at the key location in the dirtyStorage mapping. (dirtyStorage represents the most up-to-date state of the contract which is why we try to return that first)

5. Otherwise call the GetCommitedState function to look up the value in the storage trie. Again fakeStorage is checked for.

6. If pendingStorage exists return the value at the key location in the pendingStorage mapping.

7. If none of the above have returned go to the originStorage and retrieve & return the value from there.

You’ll have noticed that the function attempted to return dirtyStorage first, then pendingStorage, then originStorage. This makes sense, during execution dirtyStorage is the most up-to-date storage mapping followed by pending and then the originStorage.

One transaction can manipulate a single storage slot multiple times so we must ensure we have the most recent value.

Let’s imagine an SSTORE that happens before an SLOAD on the same slot and in the same transaction. In this situation the dirtyStorage would be updated in the SSTORE and in the SLOAD it would be returned.

There you have it you now have an understanding of how SSTORE & SLOAD are implemented at the Geth client level. How they interact with state & storage objects and how updating a storage slot relates to the wider Ethereum “World State”.

That was intense but you made it. My guess is this article has left you with more questions than you had before you started but that’s part of the fun of crypto.

Keep grinding anon.

noxx

Twitter @noxx3xxon

In this episode, we’ll dig into how contract storage works, provide some mental models to aid your understanding and deep dive into storage slot packing. If the term “slot packing” is foreign to you don’t worry, knowledge of slot packing is vital for EVM hackers and you’ll have a deep understanding of it by the end of the article.

If you’ve ever attempted the Ethernaut Solidity Wargame Series or other Solidity “Capture The Flag” type games you’ll know slot packing knowledge is often the key to cracking the puzzles/hacks.

Storage Fundamentals

A high-level overview of storage fundamentals has been done brilliantly in this “Program the Blockchain” post. I’ll provide a refresher of the key points required for this article however I highly recommend reading their full article.

Data Structure

We’ll start with the data structure of contract storage, this provides us a solid foundation upon which the rest of our knowledge will sit.

Contract storage is simply a key to value mapping. It maps a 32-byte key to a 32-byte value. Given our key is 32 bytes in size we can have a maximum of (2^256)-1 keys.

32 bytes is equal to 256 bits which gives us (2^256)-1 binary numbers to choose from for the key.

All values are initialised as 0 and zeros are not explicitly stored. This makes sense since 2^256 is approximately the number of atoms in the known, observable universe.

No computer can hold that much data. This is also the reason setting a storage value to zero refunds you some gas as that key value no longer needs to be stored by the nodes on the network.

Conceptually storage can be viewed as an astronomically large array. Our first key with binary value 0 represents item 0 in the array, the key with binary value 1 represents item 1 in the array etc.

Fixed Size Variables

Contract variables that are declared as storage variables can be split into 2 camps fixed-size and dynamic-size. We’re going to focus on fixed-size variables and how the EVM can pack multiple variables into a single 32-byte storage slot.

To learn more about dynamic size variables refer to the “Program the Blockchain” post.

Now that we know storage is a key-value mapping, the next question is how are the keys assigned to the variables. Say we have the following solidity code.

Given all these variables are fixed size the EVM can use reserved storage locations (keys) starting from slot 0 (key of binary value 0) and moving linearly forward to slot 1, 2 etc.

It will do this based on the order the variables are declared in the contract. The first declared storage variable will be stored at slot 0.

In this example slot 0 will hold variable “value1”, variable “value2” is a fixed-sized array of 2 so will take up slots 1 & 2 and finally, slot 3 will hold variable “value3”. The diagram below shows this.

Now let’s take a look at a similar contract and inspect how the variables are stored in this scenario.

You might expect this to take up slots 0 to 3 as in the previous example. We had 4 values to store in our previous example (taking into consideration the array of size 2) and we have 4 values to store in this example.

You may be surprised to hear that in this example only storage slot 0 is used. The key difference is the unit types that are used for the variables.

Before all variables were of type uint256 which represents 32 bytes of data. Here we use uint32, uint64 & uint128 which represent 4, 8 and 16 bytes of data respectively.

Slot Packing

This is where the term slot packing arises. The solidity compiler knows it can store 32 bytes of data at a storage slot. As a result, when “uint32 value1”, which only takes up 4 bytes, is stored at slot 0 when the next variable is read in the compiler will see if it can be packed into the current storage slot.

Given slot 0 had 32 bytes of space and value1 only took up 4 of them as long as the next variable is less than 28 bytes in size it will also be packed into slot 0.

For the above example we start with 32 bytes at slot 0;

• value1 is stored at slot 0 which takes up 4 bytes

• slot 0 has 28 bytes remaining

• value2 is 4 bytes which is <= 28 therefore it can be stored at slot 0

• slot 0 has 24 bytes remaining

• value3 is 8 bytes which is <= 24 therefore it can be stored at slot 0

• slot 0 has 16 bytes remaining

• value4 is 16 bytes which is <= 16 therefore it can be stored at slot 0

• slot 0 has 0 bytes remaining

Note that uint8 is the smallest solidity type, therefore packing cannot be smaller than 1 byte (8 bits)

The image below shows how the 32 bytes of data in slot 0 hold all 4 variables.

EVM Storage Opcodes

Now we understand the data structure of storage and the concept of slot packing let’s take a quick look at the 2 storage opcodes SSTORE & SLOAD.

SSTORE

We’ll start with SSTORE it takes in a 32-byte key and a 32-byte value from the call stack and stores that 32-byte value at that 32-byte key location. Check out this EVM playground to see how it works.

SLOAD

Next, we have SLOAD which takes in a 32-byte key from the call stack and pushes the 32-byte value stored at that 32-byte key location onto the call stack. Check out this EVM playground to see how it works.

The question you should be asking yourself at this stage is if SSTORE and SLOAD only deal in 32-byte values how can you extract a variable that has been packed into a 32-byte slot.

If you take our example above when we run SLOAD on slot 0 we’re going to get the full 32-byte value stored at that location.

This value will include the data for value1, value2, value3 & value4. How does the EVM extract the specific bytes in that 32-byte slot to return the value that we need?

The same goes for when we run SSTORE if we’re storing 32 bytes every time how does the EVM ensure when we store value2 it doesn’t overwrite value1. When we store value3 it doesn’t overwrite value2 etc.

These are the questions we’ll look to answer next.

Storing & Retrieving Packed Variables

Below is a simple contract that imitates the example we looked at above. The only addition is a store function that sets the variable values and has to read one variable to perform some arithmetic.

The store() function in the above solidity will perform the exact operations we had questions about.

Storing multiple variables in a single slot without overwriting existing data and retrieving a variable’s specific bytes from a 32-byte slot.

Let’s start by looking at the end state of slot 0 and work backward from there. Below is both the binary and hexadecimal representation of slot 0.

Remember that hexadecimal numbers are ultimately seen as binary numbers by the machine. This is important as a number of bitwise operations are used in slot packing.

Note the values you can see in the hexadecimal, 0x115c which is equal to 4444 in decimal, 0x14d = 333, 0x16 = 22 & 0x01 = 1. These correspond to what we see in our solidity code. One slot holds 32 bytes of data which is 64 hexadecimal characters or 256 bits.

Bitwise Operations

Slot packing makes use of 3 bitwise operations, AND, OR & NOT. These correspond to 3 EVM opcodes with the same naming. Let’s take a quick look at each one.

AND

Below we have two 8 bit binary numbers. In an AND operation the 1st bit in the first number is compared with the 1st bit in the second number.

If both values are a 1 then the AND statement returns true and the first bit of our result will equal 1 otherwise the statement returns false and the bit will equal 0.

This continues ie the 2nd bit of our first number is compared with the 2nd bit of our second number etc.

OR

In the OR operation, only one of the values needs to have a value of 1 for the statement to return true. Using the same inputs as above we get a completely different output.

NOT

NOT is slightly different in that it only takes in one value rather than performing a comparison on 2 . NOT performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0.

Let’s now jump into how these are used in the above solidity example

Slot Manipulation - Slot Packing SSTORE

We’re going to focus on solidity line 18.

value2 = 22;

At this stage some data, value1, has been stored in slot 0, we now need to pack some additional data into the same slot.

All the logic we see for this example is the same as when value3 & value4 are stored. We’ll look at how this is done conceptually and an EVM playground will be provided for you to explore further.

We start with the following values.

Note “0xffffffff” is equal to “11111111111111111111111111111111” in binary.

The first thing the EVM does is use the EXP opcode which takes in a base integer and an exponent and returns the value.

Here we use 0x0100 as the base integer which represents a 1-byte offset and raise it to exponent 0x04 which is the start position for “value2”. The image below shows why the returned value is useful.

We can see that the result of the EXP function enables us to insert our data 0x16 at the correct position (4-byte offset).

We can’t use this value however as it would overwrite value1 which has already been stored. This is where bitmasks are utilised.

The above image shows how a bitmask can be utilised to get all data from a slot except for the bytes you are looking to overwrite. In this case, value2’s bytes were already set to 0 however if they had not been we would have seen this data wiped.

Here’s another example to crystalise what is happening. This is the same process but looking at what would happen if all 4 values had already been stored and we wanted to update value2 from 22 to 99. Look out for the existing 0x016 value being zeroed out.

You may already be thinking about how a bitwise OR could help us combine the values we have. The image below shows the next steps.

We can now use SSTORE on this 32-byte value at slot 0 which contains the data for both value1 & value2 at the correct byte positions.

Slot Manipulation - Retrieving a Packed Variable SLOAD

For retrieval, we will focus on solidity line 22.

uint96 value5 = value3 + uint32(666)

We’re not interested in the arithmetic, we’re interested in value3 being retrieved to perform the calculation.

We have a slightly different set of starting values.

Much of what we have seen already will be reused for retrieval with some modifications.

We have retrieved value3 from our packed slot 0. Hexadecimal 0x14d is equal to 333 which is what we set in the solidity code above.

Again bitmasks and bitwise operations are used to help extract specific bytes from the 32-byte slot. This value is now on the stack and can then be used by the EVM to calculate “value3 + uint32(666)”.

EVM Playground

I’ve taken all the opcodes executed in the store() function we just explored and put them into an EVM playground. Here you’ll be able to interactively play with the opcodes that are used and see how the call stack and contract storage change as you jump through them.

I’ve left comments next to the opcodes on the 2 sections we explored (solidity lines 18 & 22). I highly encourage you to check it out and jump through the opcodes it will greatly enhance your understanding.

Check it out here.

You should now have an in-depth understanding of how storage slot packing works and how the EVM is able to retrieve and store bytes in specific locations in a 32-byte slot.

Although the EVM opcodes SLOAD & SSTORE only deal in 32-byte chunks we can use bitwise operations and bitmasks to store and load the data we want.

In Part 4 of the series, we take a look under the hood of the Go Ethereum (Geth) client to see how it implements the SSTORE & SLOAD opcodes.

Hope you enjoyed the article.

noxx

Twitter @noxx3xxon

In Part 1 we explored how the EVM knows which bytecode to run depending on which contract function is called. This helped us build an understanding of the call stack, calldata, function signatures & the EVM opcodes instructions.

In Part 2 we’ll take a trip down “memory” lane and provide a comprehensive review of what contract memory is and how it works under the EVM hood.

A Trip Down Memory Lane

As you will recall in Part 1 we took a look at the default 1_Storage.sol contract from remix.

We then generated the byte code and zoomed in on the part relating to function selection. In this article, we going to focus on the first 5 bytes of the contract runtime bytecode.

6080604052

60 80                       =   PUSH1 0x80
60 40                       =   PUSH1 0x40
52                          =   MSTORE 

These 5 bytes represent the initialisation of the “free memory pointer”. To fully understand what that means and what these bytes do we must first build your understanding of the data structures that govern contract memory.

Memory Data Structure

Contract memory is a simple byte array, where data can be stored in 32 bytes (256 bit) or 1 byte (8 bit) chunks and read in 32 bytes (256 bit) chunks. The image below illustrates this structure along with the read/write functionality of contract memory.

This functionality is determined by the 3 opcodes that operate on memory.

• MSTORE (x, y) - Store a 32 byte (256-bit) value “y” starting at memory location “x”

• MLOAD (x) - Load 32 bytes (256-bit) starting at memory location “x” onto the call stack

• MSTORE8 (x, y) - Store a 1 byte (8-bit) value “y” at memory location “x” (the least significant byte of the 32-byte stack value).

You can think of the memory location as simply the array index of where to start writing/reading the data. If you want to write/read more than 1 byte of data you simply continue writing or reading from the next array index.

EVM Playground

This EVM playground will help solidify your understanding of what these 3 opcodes do and how memory locations work. Click Run and the curled arrow at the top right to jump through the opcodes and see how the stack and memory are altered. (There are comments above the opcodes to describe what each section does)

While walking through the EVM playground above you may have noticed a few strange occurrences. First, when we wrote a single byte 0x22 using MSTORE8 to memory location 32 (0x20) the memory changed from

to

You may ask the question, what’s with all the additional zeros we only added 1 byte?

Memory Expansion

When your contract writes to memory, you have to pay for the number of bytes written. If you are writing to an area of memory that hasn't been written to before, there is an additional memory expansion cost for using it for the first time.

Memory is expanded in 32 bytes (256-bit) increments when writing to previously untouched memory space.

Memory expansion costs scale linearly for the first 724 bytes and quadratically after that.

Above our memory was 32 bytes before we wrote 1 byte at location 32. At this point we began writing into untouched memory, as a result, the memory was expanded by another 32-byte increment to 64 bytes.

Note that all locations in memory are well-defined initially as zero which is why we see 2200000000000000000000000000000000000000000000000000000000000000 added to our memory.

Remember Memory is a Byte Array

The second thing you may have noticed occurred when we ran an MLOAD from memory location 33 (0x21). We returned the following value to the call stack.

3300000000000000000000000000000000000000000000000000000000000000

We were able to start our read from a non 32 factor.

Remember memory is a byte array meaning we can start our reads (and our writes) from any memory location. We are not constrained to multiples of 32. Memory is linear and can be addressed at the byte level.

Memory can only be newly created in a function. It can either be newly instantiated complex types like array/struct (e.g. via new int[...]) or copied from a storage referenced variable.

Now we have an understanding of the data structures let’s return to the free memory pointer.

Free Memory Pointer

The free memory pointer is simply a pointer to the location where free memory starts. It ensures smart contracts keep track of which memory locations have been written to and which haven’t.

This protects against a contract overwriting some memory that has been allocated to another variable.

When a variable is written to memory the contract will first reference the free memory pointer to determine where the data should be stored.

It then updates the free memory pointer by noting how much data is to be written to the new location. A simple addition of these 2 values will yield where the new free memory will start.

freeMemoryPointer + dataSizeBytes = newFreeMemoryPointer 

Bytecode

As mentioned before the free memory pointer is defined at the start of the runtime bytecode through these 5 opcodes.

60 80                       =   PUSH1 0x80
60 40                       =   PUSH1 0x40
52                          =   MSTORE  

These effectively state that the free memory pointer is located in memory at byte 0x40 (64 in decimal) and has a value of 0x80 (128 in decimal).

The immediate questions you may have are why the values 0x40 & 0x80 are used above. The answer to this can be found in the following statement.

Solidity’s memory layout reserves four 32-byte slots:

• 0x00 - 0x3f (64 bytes): scratch space

• 0x40 - 0x5f (32 bytes): free memory pointer

• 0x60 - 0x7f (32 bytes): zero slot

We can see that 0x40 is the predefined location by solidity for the free memory pointer. The value 0x80 is merely the first memory byte that is available to write to after the 4 reserved 32-byte slots.

We’ll quickly run through what each reserved section does.

• Scratch space, can be used between statements i.e. within inline assembly and for hashing methods.

• Free memory pointer, currently allocated memory size, start location of free memory, 0x80 initially.

• The zero slot, is used as an initial value for dynamic memory arrays and should never be written to.

Memory in a Real Contract

To consolidate what we’ve learned so far we’re going to look at how memory and the free memory pointer update within real solidity code.

I’ve created a MemoryLane Contract and intentionally kept it extremely simple. It has a single function that merely defines two arrays of lengths 5 & 2 and then assigns b[0] a value of 1. Despite the simplicity, there is a lot that goes on when these 3 lines of code are executed.

To view the details of how this solidity code executes within the EVM it can be copied into a remix IDE. After it’s copied you can compile the code, deploy it, run the memoryLane() function and then enter debugging mode to step through the opcodes (See here for instructions on how to do this). I have extracted a simplified version into an EVM Playground and will run through it below.

The simplified version organises the opcodes sequentially removing any JUMP’s and any code that isn’t relevant to memory manipulation. Comments have been added to the code to provide context to what is being done. The code is split into 6 distinct sections which we will delve into.

I cannot stress enough how important it is to use the playground and step through the opcodes yourself. This will greatly enhance your learning. Now let’s dig into the 6 sections.

Free Memory Pointer Initialisation (EVM Playground Lines 1-15)

First, we have “free memory pointer initialisation” which we have discussed above. A value of 0x80 (128 in decimal) is pushed onto the stack. This is the value of the free memory pointer and is determined by Solidity’s memory layout. At this stage, we have nothing in memory.

Next, we push the free memory pointer location 0x40 (64 in decimal) again determined by Solidity’s memory layout.

Finally, we call MSTORE which pops the first item off the stack 0x40 to determine where to write to in memory and the second value 0x80 as what to write.

This leaves us with an empty stack but we have now populated some memory. This memory representation is in hexadecimal where each character represents 4 bits.

We have 192 hexadecimal characters in memory which means we have 96 bytes (1 byte = 8 bits = 2 hexadecimal characters).

If we refer back to Solidity’s memory layout we were told the first 64 bytes would be allocated as scratch space and the next 32 would be for the free memory pointer.

Thats exactly what we have below.

Memory Allocation Variable “a” & Free Memory Pointer Update (EVM Playground Lines 16-34)

For the remaining sections, we’re going to skip to the end state of each section and give a high-level overview of what happened for brevity. The individual opcode steps can be seen via the EVM playground.

Next memory is allocated for variable “a” (bytes32[5]) and the free memory pointer is updated.

The compiler will have determined how much space is required through the array size and the default array element size.

Remember elements in memory arrays in Solidity always occupy multiples of 32 bytes (this is even true for bytes1[], but not for bytes and string)

The size of the array multiplied by 32 bytes tells us how much memory we need to allocate.

In this case that calculation 5 * 32 yields 160 or 0xa0 in hex. We can see this being pushed onto the stack and added to the current free memory pointer 0x80 (128 in decimal) to get the new free memory pointer value.

This returns 0x120 (288 in decimal) which we can see has been written to the free memory pointer location.

The call stack keeps the memory location of the variable “a” on the stack 0x80 so it can reference it later if needed. 0xffff represents a JUMP location and can be ignored since it isn’t relevant to memory manipulation.

Memory Initialisation Variable “a” (EVM Playground Lines 35-95)

Now that the memory has been allocated and the free memory pointer updated we need to initialise the memory space for variable “a”. Since the variable is just declared and not assigned it will be initialised with the zero value.

To do this write the EVM uses CALLDATACOPY which takes in 3 variables.

• memoryOffset (which memory location to copy the data to)

• calldataOffset (byte offset in the calldata to copy)

• size (byte size to copy)

In our case, the memoryOffset is the memory location for variable “a” (0x80). The calldataOffset is the actual size of our calldata since we don’t want to copy any of the calldata, we want to initialise the memory with the zero value. Finally, the size is 0xa0 or 160 bytes since that is the size of the variable.

We can see our memory has expanded to 288 bytes (this includes the zero slot) and the stack again holds the memory location of the variable and a JUMP location on the call stack.

Memory Allocation Variable “b” & Free Memory Pointer Update (EVM Playground Lines 96-112)

This is the same as the memory allocation and free memory pointer update for variable “a” except this time it is for “bytes32[2] memory b”.

The memory pointer is updated to 0x160 (352 in decimal) which is equal to the previous free memory pointer 288 plus the size of the new variable in bytes 64.

Note that the free memory pointer has updated in memory to 0x160 and we now have the memory location for variable “b” (0x120) on the stack.

Memory Initialisation Variable “b” (EVM Playground Lines 113-162)

Same as memory initialisation of variable “a”.

Note that memory has increased to 352 bytes. The stack still holds memory locations for the 2 variables.

Assign Value to b[0] (EVM Playground Lines 163-207)

Finally, we get to assigning a value to array “b” index 0. The code states that b[0] should have a value of 1.

This value is pushed onto the stack 0x01. A bit shift left occurs next however the input for the bit shift is 0 meaning our value doesn’t change.

Next, the array index position to be written to 0x00 is pushed to the stack and a check is done to verify this value is less than the length of the array 0x02. If it isn’t the execution jumps to a different part of the bytecode which handles this error state.

The MUL (multiply) & ADD opcodes are used to determine where in memory the value needs to be written for it to correspond to the correct array index.

0x20 (32 in decimal) * 0x00 (0 in decimal) = 0x00

Remember memory arrays are 32-byte elements so this value represents the start location of an array index. Given we are writing to index 0 we have no offset.

0x00 + 0x120 = 0x120 (288 in decimal)

ADD is used to add this offset value to the memory location for variable “b”. Given our offset was 0 we will write our data straight to the assigned memory location.

Finally, an MSTORE stores the value 0x01 to this memory location 0x120.

The image below shows the system state at the end of the function execution. All the stack items have been popped off.

Note in actuality in remix there are a few items left on the stack, a JUMP location and the function signature however they are not relevant to memory manipulation and therefore have been omitted in the EVM playground.

Our memory has been updated to include the b[0] = 1 assignment, on the third last line of our memory a 0 value has turned into a 1.

You can verify the value is at the correct memory location, b[0] should occupy locations 0x120 - 0x13f (bytes 289 - 320).

There we have it 🎉 , that was a lot of information to take in but we now have a solid understanding of how contract memory works. This will serve us well the next time we need to write some solidity code.

When you’re jumping through some contract opcodes and see certain memory locations that keep popping up (0x40) you’ll now know exactly what they mean.

Next, in the series, we “Demystify Storage Slot Packing” in EVM Deep Dives - Part 3.

Until next time.

noxx

Twitter @noxx3xxon

In the smart contract world, the “Ethereum Virtual Machine” along with its algorithms and data structures are the first principles. Solidity and the smart contracts we create are the components built on top of this foundation. To be a great Solidity dev one must have a deep understanding of the EVM.

This is the first in a series of articles that will deep dive into the EVM and build that foundational knowledge needed to become a “shadowy super coder”.

Subscribe now

The Basics: Solidity → Bytecode → Opcode

Before we begin, this article assumes some basic knowledge of Solidity and how it’s deployed to the Ethereum chain. We’ll briefly touch on these subjects however if you’d like a refresher see this article here.

As you know your Solidity code needs to be compiled into bytecode prior to being deployed to the Ethereum network. This bytecode corresponds to a series of opcode instructions that the EVM interprets.

This series will focus on specific parts of the compiled bytecode and illuminate how they work. By the end of each article, you should have a much clearer understanding of how each component functions. Along the way, you will learn lots of the foundational concepts relating to the EVM.

Today we’re going to look at a basic Solidity contract along with an excerpt of its bytecode/opcodes to demonstrate how the EVM selects functions.

The runtime bytecode created from Solidity contracts is a representation of the entire contract. Within the contract, you may have multiple functions that can be called once it is deployed.

A common question is how does the EVM know what bytecode to execute depending on which function of the contract is called. This is the first question we’ll use to help understand the underlying mechanics of the EVM and how this particular case is handled.

1_Storage.sol Breakdown

For our demo, we will use the 1_Storage.sol contract, which is one of the default contracts in the online Solidity IDE Remix.

The contract has 2 functions store(uint256) and retrieve() that the EVM will have to decide between when a function call comes in. Below is the compiled runtime bytecode of the entire contract.

608060405234801561001057600080fd5b50600436106100365760003560e01c80632e64cec11461003b5780636057361d14610059575b600080fd5b610043610075565b60405161005091906100d9565b60405180910390f35b610073600480360381019061006e919061009d565b61007e565b005b60008054905090565b8060008190555050565b60008135905061009781610103565b92915050565b6000602082840312156100b3576100b26100fe565b5b60006100c184828501610088565b91505092915050565b6100d3816100f4565b82525050565b60006020820190506100ee60008301846100ca565b92915050565b6000819050919050565b600080fd5b61010c816100f4565b811461011757600080fd5b5056fea2646970667358221220404e37f487a89a932dca5e77faaf6ca2de3b991f93d230604b1b8daaef64766264736f6c63430008070033 

We are going to focus on the snippet of bytecode below. This snippet represents the function selector logic. Run “ctrl f” on the snippet to verify it is in the above bytecode.

60003560e01c80632e64cec11461003b5780636057361d1461005957

This bytecode corresponds to a set of EVM opcodes and their input values. You can check out the list of EVM opcodes here.

Opcodes are 1 byte in length leading to 256 different possible opcodes. The EVM only uses 140 unique opcodes.

The below shows the bytecode snippet broken into its corresponding opcode commands. These are run sequentially on the call stack by the EVM. You can navigate to the link above to verify the opcode number 60 = PUSH1 etc. By the end of the article, you’ll have a full understanding of what these do.

60 00                       =   PUSH1 0x00 
35                          =   CALLDATALOAD
60 e0                       =   PUSH1 0xe0
1c                          =   SHR
80                          =   DUP1  
63 2e64cec1                 =   PUSH4 0x2e64cec1
14                          =   EQ
61 003b                     =   PUSH2 0x003b
57                          =   JUMPI
80                          =   DUP1 
63 6057361d                 =   PUSH4 0x6057361d     
14                          =   EQ
61 0059                     =   PUSH2 0x0059
57                          =   JUMPI  

Smart Contract Function Calls & Calldata

Before diving deep into opcodes we need to quickly run through how we call a contract function.

When we call a contract function we include some calldata that specifies the function signature we are calling and any arguments that need to be passed in.

This can be done in Solidity with the following code.

Here we are making a contract call to the store function with argument 10. We use abi.encodeWithSignature() to get the calldata in the desired format. The emit logs our calldata for testing.

0x6057361d000000000000000000000000000000000000000000000000000000000000000a

The above is what abi.encodeWithSignature("store(uint256)", 10) returns.

Earlier I mentioned function signatures, now let’s take a closer look at what they are.

Function signatures are defined as the first four bytes of the Keccak hash of the canonical representation of the function signature.

The canonical representation of the function signatures is the function name along with the function argument types ie. “store(uint256)” & “retrieve()”. Below are the function signatures of the 1_Storage.sol contract, try hashing store(uint256) yourself to verify the results here.

keccak256(“store(uint256)”) →  first 4 bytes = 6057361d

keccak256(“retrieve()”) → first 4 bytes = 2e64cec1

Looking at our calldata above we can see that we have 36 bytes of calldata, the first 4 bytes of our calldata correspond to the function selector we just computed for the store(uint256) function.

The remaining 32 bytes correspond to our uint256 input argument. We have a hex value of “a” which is equal to 10 in decimal.

6057361d = function signature (4 bytes)

000000000000000000000000000000000000000000000000000000000000000a = uint256 input (32 bytes)

If we take the function signature 6057361d and refer back to the opcode section, run “ctrl f” on this value and see if you can find it.

Opcodes & The Call Stack

We now have everything we need to commence our deep dive into what goes on at the EVM level during function selection.

We are going to run through each of the opcode commands what they do and how they affect the call stack.

If you’re unfamiliar with how a stack data structure works watch this quick video as a primer.

We start with PUSH1 which tells the EVM to push the next 1 byte of data, 0x00 (0 in decimal), to the call stack. Why we do this will become apparent with the next opcode.

Next, we have CALLDATALOAD which pops off the first value on the stack (0) as input.

This opcode loads in the calldata to the stack using the “input” as an offset. Stack items are 32 bytes in size but our calldata is 36 bytes. The pushed value is msg.data[i:i+32] where “i” is this input. This ensures only 32 bytes are pushed to the stack but enables us to access any part of the calldata.

In this case, we have no offset (the value popped off of the stack was 0 from the previous PUSH1) so we push the first 32 bytes of the calldata to the call stack.

Remember earlier we logged our call data via an emit which equalled “0x6057361d000000000000000000000000000000000000000000000000000000000000000a”.

This means the trailing 4 bytes (“0000000a”) are lost. If we had wanted to access the uint256 variable we would have used an offset of 4 to omit the function signature but include the full variable.

Another PUSH1 this time with the hex value 0xe0 which has a decimal value of 224. Remember function signatures are 4 bytes long or 32 bits. Our loaded calldata is 32 bytes long or 256 bits. 256 - 32 = 224 you may see where this is going.

Next, we have SHR which is a bit shift right. It takes the first item off the stack (224) as an input of how much to shift by and the second item off the stack (0x6057361d0…00) represents what needs to be shifted. We can see after this operation we have our 4-byte function selector on the call stack.

If you are unfamiliar with how bit shifts work see this short video.

Next is DUP1, a simple opcode that takes the value on the top of the stack and duplicates it.

PUSH4 pushes the 4 byte function signature of retrieve() (0x2e64cec1) onto the call stack.

In case you’re wondering how it knows this value, remember this is in the bytecode that was compiled from the solidity code. The compiler, therefore, had information on all function names and argument types.

EQ pops 2 values off of the stack, in this case, 0x2e64cec1 & 0x6057361d and checks if they’re equal. If they are it pushes a 1 back to the stack, if not a 0.

PUSH2 pushes 2 bytes of data onto the call stack 0x003b in hex which is equal to 59 in decimal.

The call stack has something called a program counter which specifies where in the bytecode the next execution command is. Here we set 59 because that is the location for the start of the retrieve() bytecode. (Note the EVM Playground section below will help crystallize how this works)

You can view the program counter location in a similar way to a line number location in your Solidity code. If the function is defined on line 59 you can use the line number as a way to tell the machine where to find the code for that function.

JUMPI stands for “jump if”. It pops 2 values off of the stack as input, the first (59) is the jump location and the second (0) is the bool value for whether this jump should be executed. Where 1 = true and 0 = false.

If it is true the program counter will be updated and the execution will jump to that location. In our case it is false, the program counter is not altered and the execution continues as normal.

DUP1 again.

PUSH4 pushes the 4 byte function signature of store(uint256) (0x6057361d) onto the call stack.

EQ again however this time the result is true as the function signatures match.

PUSH2, push the program counter location for the store(uint256) bytecode, 0x0059 in hex which is equal to 89 in decimal.

JUMPI, this time the bool check is true meaning the jump executes. This updates the program counter to 89 which will move the execution to a different part of the bytecode.

At this location, there will be a JUMPDEST opcode, without this opcode at the destination the JUMPI will fail.

There we have it, after this opcode executes you’ll be taken to the location of the store(uint156) bytecode and the execution of the function will continue as normal.

While this contract only had 2 functions the same principles apply to a contract with 20+ functions.

You now know how the EVM determines the location of the function bytecode that it needs to execute based on a contract function call. It’s actually just a simple set of “if statements” for each function in your contract along with their jump locations.

EVM Playground

I highly recommend visiting this link, it’s an EVM playground where I have set up the exact bytecode we have just run through. You’ll be able to interactively see the stack changing and I’ve included the JUMPDEST so you can see what happens after the final JUMPI.

The EVM playground will also help with your understanding of the program counter, in the code, you’ll see comments next to each command with its offset which represents its program counter location.

You’ll also see the calldata input to the left of the Run button, try changing this to the retrieve() call data 0x2e64cec1 to see how the execution changes. Just click Run and then the “step into” (curled arrow) button at the top right to jump through each opcode one by one.

Next, in the series, we take a trip down “Memory” lane in EVM Deep Dives - Part 2.

See you soon.

noxx

Twitter @noxx3xxon