Forem: zemse

Understanding EIP-7864's Unified Binary Tree

zemse — Mon, 17 Feb 2025 10:18:15 +0000

Thanks to Ignacio Hagopian (EIP-7864 author) for a quick review of this article and the cover image features a tree from the Goerli Park.

Intro

Unlike Bitcoin, Ethereum includes something called "state root" in its current block's header. For being functional, it's not necessary to have a state root, since any new full node joining the network can sync and execute all blocks to arrive at the current state. However, running full-node is time and resource-consuming. As of Feb 2025, the Ethereum's current blockchain size is ~1500 GiB. Forget about mobile phones, even most laptops don't have that much space capacity. To make things worse, we also have many L2s. It's not practical for users to run full nodes for every network they use. Hence, almost every Ethereum or L2 user knowingly or unknowingly trusts a full-node RPC provider. If these providers give malicious responses, the user won't realize until money is lost.

That's why Ethereum, since its inception in mid-2015, came with a state root, a 32-byte value that is calculated by encoding the entire state using the Merkle Patricia Trie structure. This enables devices with limited storage/computation to still use Ethereum in a safe and trustless way.

However, MPT has many complexities like RLP and Extension Nodes which make writing zk constraints extremely challenging (was in development for about 2 years). Being a hex-ary trie, its proof size is quite huge, especially when required to supply multiple state proofs. Light clients also face an edge case while operating on a partial MPT.

Verkle tree solution was studied for the last few years and attempted to solve the above problems, however, it's not post-quantum safe. The security of hash functions is not proven to be affected by quantum computers. Hence, the hash-based Binary tree can be a promising solution.

Unified Binary Tree (UBT)

There are many technical details specified in the EIP-7864. This post is an informal attempt to specify the details one by one, such that it can be easy for an engineer to digest quickly.

Step 1 - Sparse Tree

Let's imagine a sparse merkle tree structure with 256 depth, meaning the number of leaves is $2^{256}$ . Each leaf stores a 256-bit value. This makes it like a mapping of uint256 to uint256, where we traverse down the tree by consuming a bit from the key.

In the following steps, we will make some modifications to the tree to arrive at the Binary Tree specified in EIP-7864.

Spoiler alert: the UBT is not sparse, it will be discussed later in Step 8.

Step 2 - Group every 256 leaves

In the MPT's Account trie, the leaf was an RLP byte string of tuple of the nonce, balance, code hash, and storage root. It's convenient to have these details together.

In our binary tree, how can we keep these related values together?

We can hash their RLP string and store it as the leaf value.
We can store related values in adjacent leaves in the merkle tree.

The first option adds an extra layer of hashing and increases complexity. The second option is simpler. Let's go!

To be able to store related items in adjacent leaves in a neat way, we can allocate adjacent groups of 256 leaves and call it "sub-tree". This means our original 256-bit key of the huge tree is split into two parts: 248-bit stem-key + 8-bit sub-key.

Note that from a structural perspective, there's no difference from our original 256-depth sparse merkle tree. We have simply grouped all the leaves of our massive tree into groups of 256 leaves. So it looks like we have a tree of 248-depth, and each of its leaves is an 8-depth sub-tree.

There are three types of sub-trees:

Account sub-tree
Storage sub-tree
Code chunks sub-tree

All of these sub-trees are 8-depth, so they look the same. The only difference is the kind of data that is stored in the leaves.

Step 3 - Account sub-tree

Details of an account will be stored in a subtree. To reach that sub-tree for an account we need to convert a 20-byte address into a 31-byte key using the following logic:

fn address_to_key(address: [u8; 20]) -> [u8; 31] {
  let address: [u8; 32] = to_bytes_32(address);
  let tree_idx: [u8; 32] = [0u8; 32];

  // use first 31 bytes result of the hash
  let result: [u8; 32] = hash(concat(address, tree_idx));
  result[..31]
}

In a sub-tree there are 256 leaves. Every account has the following details:

Nonce (8 bytes)
Balance (16 bytes)
Bytecode (dynamic, max length 24kb)
Storage (dynamic, max count is very high)

Our goal is to somehow store it. Now nonce and balance could each take a leaf but each leaf size is 32 bytes. So to save proof cost, we can combine these details in a single leaf.

First leaf data layout

1 byte: Version byte
4 bytes: Reserved for future usage
3 bytes: code size
8 bytes: nonce
16 bytes: balance

Second leaf

32 bytes: Codehash

Rest of the leaves

Third leaf to 64th leaf: Reserved for future usage.
65th leaf to 128th leaf: Reserved for Storage.
129th leaf to 256th leaf: Reserved for Bytecode chunks.

Step 4 - Storage sub-tree

Previously, there were MPTs inside MPTs (account trie contained storage trie). To open a storage slot, we had to open the account's storage root first, which adds proof size as well as extra work. In the Binary tree, we could avoid this by combining all key-value pairs in the single tree.

The first 64 storage slots are stored in the Account's sub-tree. The 65th leaf to 128th leaf is reserved for this purpose. The rest of the storage slots in groups of 256 are stored together in a deterministically random sub-tree calculated using the following logic.

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
        pos = HEADER_STORAGE_OFFSET + storage_key
    else:
        pos = MAIN_STORAGE_OFFSET + storage_key
    return get_tree_key(
        address,
        pos // STEM_SUBTREE_WIDTH,
        pos % STEM_SUBTREE_WIDTH
    )

This helps with giving state proof for Solidity arrays which start at a deterministically random slot and then all array elements are sequential. In the case of solidity mappings, it will store things in random leaves in our UBT, but if the solidity mapping points to a structure (e.g. mapping(address => Person)) then solidity lays out the structure contents sequentially, so we can make easy state proofs for that too.

Step 5 - Bytecode chunk sub-tree

Previously in MPT only codehash was present in the state. Opening a small part of bytecode through state proof meant providing an entire preimage of codehash which is lengthy. This is troublesome especially when we want to create block execution proof, a worse-case block would touch as many Ethereum accounts and we have to witness all bytecode when only a small portion of it is used, this causes a lot of hashing, creating a DoS vector for zk light clients.

In the new UBT, we want to improve this situation by placing the bytecode in the merkle tree, chunk by chunk in the leaves. So that zk light clients can expose sufficiently required code slices. The costs of CALL opcodes can also be updated to incentivize usage of less bytecode.

Bytecode in the worst case (24kb) will require 750+ leaves. So we need to allocate other sub-trees to be able to fill all the bytecode.

A naive approach can be to simply break bytecode into 32-byte chunks and place them in the merkle tree. However, note that bytecode can also contain push opcodes. So when you are given a 32-byte chunk from a huge bytecode, you are not sure if the first byte is an executable opcode or part of a push opcode.

To resolve this issue, we can simply allocate 1 byte in every chunk to store the number of bytes that are non-executable (part of the push opcode in the previous chunk).

Layout of chunk

1 byte: number of non-executable/push bytes at the begining of this chunk
31 bytes: raw bytecode

Example 1 - short bytecode

# raw bytecode len 3 bytes
345f55

# 1-byte num of non-exec bytes + 31-byte chunks
- 00345f5500000000000000000000000000000000000000000000000000000000

Example 2 - long bytecode

# raw bytecode len 64 bytes
5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b

# 1-byte num of non-exec bytes + 31-byte chunks
- 005b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
- 005b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
- 005b5b0000000000000000000000000000000000000000000000000000000000

Example 3 - long bytecode with push opcode

# raw bytecode len 64 bytes
5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b6911223344
5566778899aa5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b

# 1-byte num of non-exec bytes + 31-byte chunks
- 005b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b69112233
- 07445566778899aa5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5b
- 005b5b0000000000000000000000000000000000000000000000000000000000

In the above example, we have a PUSH10 (0x69) in the first chunk whose push data is also going into the second chunk. The complete instruction looks like 69112233445566778899aa, however when we break it into 31-byte chunks we have 445566778899aa push bytes, hence we store 7 in the num of non-exec bytes.

The first 128 bytecode chunks are stored in the account sub-tree. The rest of the chunks in groups of 256 chunks are stored somewhere in the UBT.

def get_tree_key_for_code_chunk(address: Address32, chunk_id: int):
    return get_tree_key(
        address,
        (CODE_OFFSET + chunk_id) // STEM_SUBTREE_WIDTH,
        (CODE_OFFSET + chunk_id)  % STEM_SUBTREE_WIDTH
    )

Step 6 - Simplify the tree by hash function special case

Usually in a Merkle tree, the hash value of a node is the hash of the concatenation of its children.

top = hash(concat(A, B))

If you see the scale of our tree, most of it is going to be empty even after 100 years of production usage.

There will be a lot of hashing involved, we can add a special case - if both A and B are 0, then hash(concat(0, 0)) is 0.

This means if our tree is empty, its root is 0.

Similarly, if a leaf is non-zero, we can compute the hash of that section easily.

Also, note that the hash function is not yet finalized. People are waiting for the security analysis of poseidon2.

Step 7 - Empty node to further simplify tree

A naive approach for creating such a tree in memory will require about $10^{68}$ GB of memory.

To ghost the unused portions of the tree, we can introduce "Empty Node".

Interestingly, the usage of empty nodes to hide the section or actual full sections does not affect the state root.

Step 8 - Convert into a non-sparse tree to further simplify the tree

In a sparse merkle tree, the proof size is $O(logb(leaves_{max}))$ . In our tree where we have $2^{256}$ depth, we will have a very huge proof size i.e. 32 bytes x 256 = 8192 bytes.

Especially, when most of the leaves in our tree are going to be empty even after 1000 years of production usage. The ideal case would be to have the proof in $O(logb(leaves_{count}))$ .

We introduce a structure something called StemNode which is supposed to represent the 256 leaves of the sub-tree. It also stores the 31 bytes of the stem.

struct StemNode {
  stem: [u8; 31],
  leaves: [u256; 256],
}

The goal is to have a minimal amount of internal branching nodes. If there's just a single StemNode then we can place it directly.

Tree examples

Following is an empty tree:

Since there's nothing, the root node is EmptyNode and root hash is 0.

First insertion

Now we insert one element key=bytes32(1) and value=1.

Since we have one insertion, it creates a stem node with the stem as the first 31 bytes from the key, last 1 byte is used as the id in the stem node. In this case, our key=1 is broken down into stem=0 and id=1.

Second insertion

Now we insert one more element key = 1<<255 and value=1. This key is broken down into stem=1<<247 and id=0. We will now update the tree.

Third insertion

To show an insertion in existing stem node, let us insert key=0 value=4. Here key is broken down into stem=0 and id=0. As we walk down the tree, we arrive at a StemNode where stem is 0. So we update the value at id=0.

Fourth insertion

We can do additional insertion at key = 1<<253 and value=1 to see how internal nodes are created. This key is broken down into stem=1<<245 and id=0. We create minimum internal nodes as needed.

As we walk down the stem path, we arrive at a StemNode whose stem is 0 instead of 1<<245. So we refactor that section by adding some internal nodes and creating a new StemNode.

As you can see a node existed already on the left leg of the root. It was refactored down as needed using a minimal amount of internal branch nodes.

In the previous MPT specification, a field similar to stem existed called path in the branch, extension, and leaf nodes in MPT, however, it excluded the already consumed nibbles down in the path. So in the process when we have to refactor the tree, it changes the path, hereby changing the hash of the node, giving rise to some edge cases. It is great to see that in the UBT specification, the stem value is not affected by refactoring in placement as it's the full 31-byte key value.

Outro

As of Feb 2025, this proposal is in draft status. Unified Binary Tree is a step towards a quantum-safe and snarkified Ethereum. It also makes Ethereum's spec simpler and can work together with state-expiry EIP. It overall sounds beneficial to Ethereum, however making changes to Ethereum is not easy and we have to explore the challenges too.

To participate in the UBT discussion, you can use the thread at https://ethereum-magicians.org/t/eip-7864-ethereum-state-using-a-unified-binary-tree/22611/6.

Setup GPG on macOS

zemse — Sun, 12 Mar 2023 14:07:08 +0000

Install

brew install gpg

Create new key

# generate key
gpg --full-generate-key

# get the public key using key ID
gpg --armor --export XXXXXX

# set the key ID in git
git config --global user.signingkey XXXXXXX

# always sign commits
git config commit.gpgsign true

Setup keychain

gpg collects password from cli. This causes issues if using vscode to create a commit. So input can be taken from a popup or keychain.

brew install pinentry-mac

The brew installation will print these caveats:

==> Caveats
You can now set this as your pinentry program like

~/.gnupg/gpg-agent.conf
    pinentry-program /opt/homebrew/bin/pinentry-mac

So just create a ~/.gnupg/gpg-agent.conf file if it doesn't exist and put the line pinentry-program /opt/homebrew/bin/pinentry-mac in it.

Now, to check if it works.

1.gpg --list-keys to print the existing keys.

pkill -TERM gpg-agent.
Restart the terminal.
echo test | gpg -e -r <PUT THE KEY ID HERE> | gpg -d

This should open a pin entry popup and make sure "save in keychain" option is selected.

Unlocking the Lockbox2 | ParadigmCTF’22

zemse — Wed, 24 Aug 2022 05:50:00 +0000

This weekend was fun, thanks to Paradigm for organising a great CTF again, that has very original and really tough challenges. Got to learn a lot while attempting/solving some of them. This CTF sometimes reminds me of IITJEE exam (a not-for-noobs high school/10+2 level exam in India).

Lockbox (the first) was very interesting challenge. I attempted it last year during the CTF, found it very tough. This year’s challenge isn’t any less. From seeming like you can do it, then making you feel like it’s literally impossible, Lockbox kept the reputation with it's 2nd iteration.

The Lockbox2 challenge is available here. In this post, we'll understand the challenge and solve it (based on how I approached it during the CTF). I've posted links wherever necessary. As a heads up, this is a quite long post, it's intended for beginners/intermediates to be able to follow. For experts, feel free to skim through the post or directly skip to the final solution here.

I'd like to thank @rileyholterhus, the Lockbox2 puzzle creator, to do a quick review of this post and provide valuable suggestions 🙏.

The Setup contract deploys a Lockbox2 contract, that contains a variable called locked, which is instantiated as true. The challenge requires this locked to be set as false. We can see that if get the solve() method to execute successfully, it’d set locked variable as false. But there are some preceding conditions which depend on input, which if not met, the solve() tx would fail. The challenge is all about crafting an input that passes the combination of conditions, similar to cracking combination locks!

Crafting inputs and improving it sounds fun. However, interestingly, the solidity solve() method does not take any input!

function solve() external {

If the solve method doesn't accept any input, how are we supposed to insert the crafted input?!

The thing here is, you can basically pass more calldata than needed, solidity does not really care about it (ik this is pretty obvious now, if I’d show this to myself of two years ago I'd have no clue).

So if we use the usual libs that rely on ABI, the generated calldata will be just the 4 bytes selector and we won’t be able to able to have them encode it for us. So we have to get our hands dirty and do it ourselves. Check out the Contract ABI Spec in the Solidity docs.

First, we will go through the challenge just to get it’s overview and understand it. Then we can get started into crafting the calldata all together.

Overview of solve method

The solve method makes 5 delegate calls to the self contract, to invoke the logic for those 5 stages.

It’s easily visible that calldata beyond the 4 bytes msg.data[4:] is passed to the particular stage method.

Here, delegatecall preserves the msg.sender. The intention could be to just add some friction for those who have not played enough with delegatecall. Or if not, we'll get to know shortly ;)

Stage 1

Quite straight forward, the calldata must be under 500 bytes.

Stage 2

Looks at first 4 words and expects them to either be a prime number or simply 1. Each of those 4 numbers should small enough (like up to 1000), so that the for-loop can iterate within tx gas limit.

Stage 3

Looks at first 3 words as a, b and c. Makes a staticcall to address(a + b). Note that from previous stage, the words are quite small numbers (~1000) and hence their sum would also be small. This means we can’t target this staticcall to a contract that we could practically deploy. This has to either be a precompile address or empty account.

If it is a precompile, then we have just a handful of choices.

A staticcall to empty account would be successful and return empty data (you can verify this by doing a simple eth_call to random address, it won’t give json rpc error response).

Btw, this one has an interesting mstore(a, b) over there. This logic basically stores value b at memory location a. By initial thought, memory location cannot be very huge and maybe it just want's to restrict a to be sufficiently small, but isn't that implied from stage2? Can't make sense of it so far, let's move on for now.

Stage 4

Things get nasty here since now it involves dynamic types. It is important to understand how solidity handles dynamic types, specifically bytes in calldata for this case. Check out dynamic types section in the Contract ABI spec here.

For simplicity, let’s ignore previous stages, just look at this in order to understand what this stage needs in order to pass through.

The gist of the conditions:

It takes two byte strings, a and b.
Deploys a contract using a as the creation code. The bytecode should be a ECDSA public key (length 64) of the tx.origin (the EOA wallet that we will use to interact). Note that ECDSA of ecdsa public key gives ethereum address (after chopping of the upper 12 bytes).
Makes a staticcall to the contract just deployed, using b as the calldata, this call should be successful.

We can easily deploy a contract containing any code we want. Here, we want to have the tx.origin’s public key as the bytecode. So one thing is we should fix a EOA wallet. And then the challenge is getting the static call to succeed. Easiest approach I could think of is having first byte as zero (STOP opcode), so that it halts execution and staticcall passes.

If you notice, this does not involve b at all. So basically b taking any value can work, which is one less headache.

Making this stage pass individually is straight forward. It will be challenging to make combination of all stages pass.

Stage 5

It internally makes a msg call to solve function which should fail somehow. Though there’s a difference of msg.sender in both solve() invocation, msg.sender is really not consumed anywhere to make a difference. At first it might seem strange, how it is possible for one thing to work first and then not work in the same env conditions?

The key to this stage, is the fact that in a CALL only 63/64 of the available gas is passed (source evm.codes). If we pass just enough gas limit, slightly less gas would be passed such that internal message call fails due to out of gas, passing the check in stage 5. Also it is important to note that 1/64 gas should be enough to perform later operations, else it will not work. It also makes sense why there's locked variable is set to false, instead of having a solved variable which is set to true like in other challenges, since it'd cost less gas.

Solving the challenge

Step 1 - Solve Stage 4

I started from this stage because it has the most complex calldata, and getting other stage passed could look like minor tweaking in the calldata (this is what I expected, I believe it was a right decision).

In stage4, we need to write a bytecode that returns public key which has first byte as zero.

Okay, but for that we need a public key, and for that we need a wallet/private key in order to be the tx.origin.

I’ll just use ethers.js in my terminal (using ethers-repl) to get a wallet real quick. You can use anything which gets the job done.

sohamzemse@MacBook-Pro % ethers
ethers-repl> while((w = ethers.Wallet.createRandom()).publicKey.slice(4,6) !== '00') {}
undefined
ethers-repl> w.privateKey
'0x9b067b56552d3369e7762f0f92051db20a2db034e8e9fc803a71e64ae5b163b4'
ethers-repl> w.publicKey
'0x0400a86410b6215c11e36c6a60d02277415f69393b692b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a68452a4311cc7238d7431fa'

Note that the public key here has a 0x04 prefix byte, which is to signify that this is an uncompressed ECDSA public key. The actual public key follows after the prefix byte.

Now we need a code that creates contract with the public key as the bytecode. It's pretty opinionated, you can use solidity/yul/vyper/huff/etk/whatever. I happen to be an evm nerd and I was in a hurry, so couldn't stop myself from writing down the following raw evm code.

$ vim lockbox_stage4.evm
=========lockbox_stage4.evm========================
push1 0x40 // 64 bytes
dup1
push1 0xb // offset in this code
push1 0 // offset in memory
codecopy
push1 0
return
// public key
00a86410b6215c11e36c6a60d02277415f69393b692b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a68452a4311cc7238d7431fa
===================================================

$ evm-run lockbox_stage4.evm
code 604080600B6000396000f300A86410B6215C11E36C6A60D02277415F69393B692B6799805EE75969DF78D25398733FC3E0438BBCBB9E37FA1FF5DA79660324A68452A4311CC7238D7431FA
Returned: 00a86410b6215c11e36c6a60d02277415f69393b692b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a68452a4311cc7238d7431fa
gasUsed: 30

I'm using evm-run for assembling + running evm code. (Sidenote: you can checkout ETK which helps with labels as well).

We can see that the bytecode on execution spits out the public key in the returndata (so that it becomes the contract bytecode). Okay, so we got the code that should be passed as to the first input a. And in case of b we can pass anything, we can just use empty bytes for now i.e. 0x.

Now it's time to encode the calldata that should work with stage4. Notice that ethers.js strictly requires "0x" prefix, so we have to add that at the start of the bytecode.

ethers-repl> encoded = defaultAbiCoder.encode(['bytes', 'bytes'], ['0x604080600B6000396000f300A86410B6215C11E36C6A60D02277415F69393B692B6799805EE75969DF78D25398733FC3E0438BBCBB9E37FA1FF5DA79660324A68452A4311CC7238D7431FA', '0x'])
'0x000000000000000000000000000000000000000000000000000000000000004000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000000000004b604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b692b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a68452a4311cc7238d7431fa0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
ethers-repl> 
ethers-repl> wordify(encoded)
[
  '0000000000000000000000000000000000000000000000000000000000000040',
  '00000000000000000000000000000000000000000000000000000000000000c0',
  '000000000000000000000000000000000000000000000000000000000000004b',
  '604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69',
  '2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6',
  '8452a4311cc7238d7431fa000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000'
]
ethers-repl> 
ethers-repl> selector('solve()')
'0x890d6908'

Putting all of this together, I'm locally using hardhat:

// use the private key we generated earlier (for public key to have first byte zero)
const wallet = new Wallet('0x9b067b56552d3369e7762f0f92051db20a2db034e8e9fc803a71e64ae5b163b4', hre.ethers.provider);
// fund this wallet with some eth to pay for tx fees
const hardhatAccount0 = (await hre.ethers.getSigners())[0];
await hardhatAccount0.sendTransaction({
  to: wallet.address,
  value: parseEther("1"),
});

// we are not using the usual abi encoding tools, because this challenge involves manipulating the calldata to make the all stages passed
await wallet.sendTransaction({
  to: contract.address,
  gasLimit: 29_000_000, // pass some huge gas limit, bcz estimate has some issues
  data: '0x890d6908' + // 4 byte selector for solve() method
  [
    '0000000000000000000000000000000000000000000000000000000000000040',
    '00000000000000000000000000000000000000000000000000000000000000c0',
    '000000000000000000000000000000000000000000000000000000000000004b',
    '604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69',
    '2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6',
    '8452a4311cc7238d7431fa000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000'
  ].join('')
});

Now execute the tx, and you should see stage4 pass. I’m using Hardhat framework to view the execution trace, using the hardhat-tracer plugin. (Sidenote: A great alternative is using Foundry and it also has tracing built-in).

The stage4 is highlighted in the screenshot above, you can see that rest of the stages fail with empty revert data as UnknownError, while there is no error in case of stage4.

Stage4 done, now lets get others!

Step 2 - Solve Stage 2

The actual condition in the code first checks if the value is greater than or equal to one and then goes into a for-loop that requires word % j != 0 for all 2 <= j < word. This step basically translates to the requirement of the first 4 words to be a prime number or 1 and the number cannot be huge, otherwise the for loop will go out of gas.

Okay, lets look at our calldata:

"0x890d6908" + // 4 byte selector for solve() method
[
  "0000000000000000000000000000000000000000000000000000000000000040", // arr[0]
  "00000000000000000000000000000000000000000000000000000000000000c0", // arr[1]
  "000000000000000000000000000000000000000000000000000000000000004b", // arr[2]
  "604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69", // arr[3]
  "2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6",
  "8452a4311cc7238d7431fa000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
].join(""),

We can clearly see that arr[3] is huge. Also note that the first three words are not prime numbers either. We need to fix this.

Let’s see how dynamic types are encoded in the case of (bytes a, bytes b). The first word contains the location where content of a starts. And second word contains the location where content of b starts. This means we can move the content of a anywhere we want.

One easy idea is to simply move the data bit forward, by two words, in order to have arr[3] to take a value that’s within iterative limits as well as making arr[2] and arr[3] independent of the byte strings. So basically we can put any kind of stuff we want over there, the contract be won’t bothered about it at all.

"0x890d6908" + // 4 byte selector for solve() method
[
  "0000000000000000000000000000000000000000000000000000000000000080", // arr[0], changed from 0x40 to 0x80 (+0x40)
  "0000000000000000000000000000000000000000000000000000000000000100", // arr[1], changed from 0xc0 to 0x100 (+0x40)
  "0000000000000000000000000000000000000000000000000000000000000001", // arr[2] (just inserted)
  "0000000000000000000000000000000000000000000000000000000000000001", // arr[3] (just inserted)
  "000000000000000000000000000000000000000000000000000000000000004b",
  "604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69",
  "2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6",
  "8452a4311cc7238d7431fa000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
].join(""),

We have inserted two words just after the first two words. We can put anything there, but having 1 in there, simply works for now.

Also we need the first two words to be a prime number. So the first two words are 0x80 (128) and 0x100 (256). Let's see some prime numbers just after them (so we can push them bit further). We know 131 and 257 are primes.

"0x890d6908" + // 4 byte selector for solve() method
[
  "0000000000000000000000000000000000000000000000000000000000000083", // arr[0], changed from 0x80 to 0x83 (+0x03)
  "0000000000000000000000000000000000000000000000000000000000000101", // arr[1], changed from 0x100 to 0x101 (+0x01)
  "0000000000000000000000000000000000000000000000000000000000000001", // arr[2]
  "0000000000000000000000000000000000000000000000000000000000000001", // arr[3]
  "000000", // a is moved further by 3 bytes
  "000000000000000000000000000000000000000000000000000000000000004b",
  "604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69",
  "2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6",
  "8452a4311cc7238d7431fa000000000000000000000000000000000000000000",
  "00", // b is moved further by 1 byte
  "0000000000000000000000000000000000000000000000000000000000000000",
].join(""),

Now with this, we can see Stage2 passes! Following is a screenshot of trace generated on hardhat using hardhat-tracer, and the delegate call to stage2 is highlighted for visibility, we can see it does not revert.

Ah, finally stage2 passed! Actually, we've done a lot so far. Pads on the back!

Step 3 - Solve Stage3

Here, a static call is made to a + b, which in our case currently it's 0x83 + 0x101 = 0x184. That's definitely not a precompile address atm, can be checked by making an eth_call.

If it's not a precompile, then the static call would still success, however result would be empty data. And this stage requires that the third word should equal to the length of the return data.

The third word can be anything only that stage2 restricts the third word to a non-zero value (1 or prime). It means there should be some return data. But how? We definitely cannot deploy a contract at an address with so many zeros! So it means the a + b needs to be a precompile for this to work.

I couldn't find an up-to-date list of precompiles, had to look into client implementations. Here is the list in EthereumJS/EVM. We can clearly see precompiles are only upto 0x12. Also the return data length should be a prime number, when called with empty data. We can just try this using eth_call. For that, I'm quickly jumping into ethers-repl on my terminal.

$ ethers
ethers-repl> await mainnet.call({to: '0x0000000000000000000000000000000000000012', data: '0x'})
// {"jsonrpc":"2.0","id":44,"error":{"code":-32602,"message":"invalid 1st argument: transaction 'data': value was too short"}}

Couldn't really find any precompile that works with empty calldata and gives a return data with prime length. It means we cannot use a precompile. After playing around a bit, it was fairly convincing that forget prime length return data, there is no way this static call could return a non-zero length return data.

But wait, didn't we just eliminated all the possibilities? Is this challenge even solvable?

*Looks at the scoreboard, single integer number of people have solved it*

Okay, means definitely there's some advanced stuff going on here and something is missing in my observations.

Oh! could it be related to that weird mstore(a, b) which I believed it was there for no reason. Hmm, after a careful observation, I could see that we do not need to have the static call return a data with prime length, the check is data.length == c, where data.length is taken from memory. So we have to use the mstore(a, b) to write at a location and manipulate the value of data.length. To know where in the memory data.length is, I'm just using hardhat-tracer to print MLOAD operations.

$ npx hardhat test --trace --opcodes MLOAD

Here, we can see after the static call to the 0x00..184 address, there is an MLOAD at location 0x60 for reading data.length. Memory location 0x60 is a special one because it always points to zero, it's used as the initial value for dynamic memory arrays when they are empty (source).

Note that mstore(a, b) is done before the declaration of bytes memory data. And since the return data is empty, solidity uses 0x60 as the location for the data variable. Solidity docs mention that this memory slot should not be written to, since it'd cause empty arrays to assume non-zero length. This helps us!

Now comes another tricky part, we have to figure out how to rearrange our calldata. I'm reverting our calldata changes back to step3 initial, and then moving it further by one word (instead of two words as we previously did). We have to do this because the mstore(a, b) writes at memory slot a, and we want it to be 0x60.

"0x890d6908" + // 4 byte selector for solve() method
[
  "0000000000000000000000000000000000000000000000000000000000000060", // 0x40 to 0x60
  "00000000000000000000000000000000000000000000000000000000000000e0", // 0xc0 to 0xe0
  "0000000000000000000000000000000000000000000000000000000000000000", // inserted here
  "000000000000000000000000000000000000000000000000000000000000004b",
  "604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69",
  "2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6",
  "8452a4311cc7238d7431fa000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
].join(""),

Okay, but what about previous stage where these first 4 words need to be primes? We might slightly change them. We know that 0x61 and 0xe3 is a prime. So let's change the first two words to ensure they are prime. That will require shifting the content of towards right by one byte.

"0x890d6908" + // 4 byte selector for solve() method
[
  "0000000000000000000000000000000000000000000000000000000000000061", // 0x60 to 0x61
  "00000000000000000000000000000000000000000000000000000000000000e3", // 0xe0 to 0xe3
  "0000000000000000000000000000000000000000000000000000000000000001", // keeping this 1
  "00000000000000000000000000000000000000000000000000000000000000004b", // one byte extra here
  "604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69",
  "2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6",
  "8452a4311cc7238d7431fa000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000000000", // three bytes extra here
].join(""),

However, you can see that 4th word is zero. Previously it was length of the byte string a in stage4. Since the length was under 1 byte, the 4th word became zero. Just to recall, byte string a is the creation code of a contract that gets deployed in stage4. Is there a way we can increase the length, by adding some redundant code without affecting behaviour?

Turns out that the answer is yes, we can! This is the evm code we previously used. The current code length is 0x4b, and we want it to exceed 0x100, so that the "1" gets in the 4th word.

ethers-repl> wordify('00'.repeat(0x100 - 0x4b))
[
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000'
]

We can just put the above zeros after our bytecode

push1 0x40 // 64 bytes
dup1
push1 0xb // offset in this code
push1 0 // offset in memory
codecopy
push1 0
return
// public key
00a86410b6215c11e36c6a60d02277415f69393b692b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a68452a4311cc7238d7431fa
// add any code after this, it is not used
// redundant code which makes bytecode length 0x100
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000

===================================================

$ evm-run lockbox_stage4.evm
code 604080600B6000396000f300A86410B6215C11E36C6A60D02277415F69393B692B6799805EE75969DF78D25398733FC3E0438BBCBB9E37FA1FF5DA79660324A68452A4311CC7238D7431FA00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Returned: 00a86410b6215c11e36c6a60d02277415f69393b692b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a68452a4311cc7238d7431fa

Now we have to repeat the steps.

ethers-repl> bytecode = '604080600B......00000000' // paste here
ethers-repl> hexDataLength(bytecode)
256 // this is 0x100
ethers-repl> encoded = defaultAbiCoder.encode(['bytes', 'bytes'], [bytecode, '0x'])
ethers-repl> wordify(encoded)
[
  '0000000000000000000000000000000000000000000000000000000000000040',
  '0000000000000000000000000000000000000000000000000000000000000160',
  '0000000000000000000000000000000000000000000000000000000000000100',
  '604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69',
  '2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6',
  '8452a4311cc7238d7431fa000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000',
  '0000000000000000000000000000000000000000000000000000000000000000'
]

We have to now repeat the steps similar to previous. I'll just paste the updated calldata.

"0x890d6908" + // 4 byte selector for solve() method
[
  "0000000000000000000000000000000000000000000000000000000000000061", // 0x60 to 0x61
  "0000000000000000000000000000000000000000000000000000000000000161", // 0x160 to 0x161
  "0000000000000000000000000000000000000000000000000000000000000001", // keeping this 1
  "000000000000000000000000000000000000000000000000000000000000000100", // one byte extra here
  "604080600b6000396000f300a86410b6215c11e36c6a60d02277415f69393b69",
  "2b6799805ee75969df78d25398733fc3e0438bbcbb9e37fa1ff5da79660324a6",
  "8452a4311cc7238d7431fa000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
  "0000000000000000000000000000000000000000000000000000000000000000",
].join(""),

Note that here, 0x161 is written to memory location 0x61, which basically writes 1 to the 0x60 word (data.length memory slot), the rest 61 is written to next slot and it does not matter.

Now we've got stage1, stage2, stage3, stage4 passing, only stage5 is failing.

Step 5 - Solve Stage 5

This stage makes a call to the solve() method again, and in the trace above, we can see everything passes but only the stage5 check, which wants the solve() invocation from stage5 to fail.

It's based on the fact that when an execution context makes a CALL, it can at max give 63/64 of the gas available. We have to carefully pass a value of gasLimit such that when 63/64 of the gas available is passed to the solve() internal message call, it's not enough for it and it goes out of gas. That only fails the internal msg call, and 1/64 gas is available for the stage5's execution context to proceed. After trying for some values, I found 560_000 to be just enough to work.

Yay! The challenge is solved!

Se* is cool but have you ever tried catching a flag :P

Stay tuned to @paradigm_ctf for the future editions. Hopefully, we’ll see Lockbox3!

Also, if you made this far, thanks! Btw I’m Soham, and I mostly do open-source contributions to some ethereum dev tools. As a disclosure: hardhat-tracer, evm-run, ethers-repl mentioned above are some of my github projects. Oh yeah, also I'm attending my first Devcon this year as a Devcon Scholar, would love to meet if you are coming too! Looking forward to buidl more stuff. My social links: github, twitter.

EthersJS - Signing EIP712 Typed Structs

zemse — Fri, 18 Jun 2021 05:13:23 +0000

Heya! In this post we're going to go a quick look into using EthersJS API for the EIP712 standard.

Also, before we dive in, I would like to point out that if your use case is simple as a single message, you likely do not need to complicate it with EIP712. You can simply use signer.signMessage("hello") API (EIP191). While if you have multiple values (like complex structs) to sign, then EIP712 can be useful.

Setting up signer

Consider a use case where a user want to sign a complex struct. They also need to include a signature to prove that they own the private keys of an account containing some funds.

You can use Metamask. But if you're just trying for demo, you can just generate a random wallet.

const metamaskProvider = new ethers.providers.Web3Provider(window.ethereum);
const signer = metamaskProvider.getSigner();

// or

const signer = ethers.Wallet.createRandom()

Defining Domain Separator

Now we define our domain separator. This is useful for the case when there is a fork/clone of your app on your chain or even a different one, and some user using both the apps. The domain separator ensures different signatures for same messages by same user.

const domain = {
  name: 'My App',
  version: '1',
  chainId: 1,
  verifyingContract: '0x1111111111111111111111111111111111111111'
};

Defining Struct Types

const types = {
  Mail: [
    { name: 'from', type: 'Person' },
    { name: 'to', type: 'Person' },
    { name: 'content', type: 'string' }
  ],
  Person: [
    { name: 'name', type: 'string' },
    { name: 'wallet', type: 'address' }
  ]
};

Signing struct objects

const mail = {
  from: {
     name: 'Alice',
     wallet: '0x2111111111111111111111111111111111111111'
  },
  to: {
     name: 'Bob',
     wallet: '0x3111111111111111111111111111111111111111'
  },
  content: 'Hello!'
};

To sign the above struct, we use _signTypedData method on the signer.

const signature = await signer._signTypedData(domain, types, mail);
// 0x74ff2b1850dfa49f825a29760cf7f8194465190481afb49dd81f0ef7783d7b9638180110bdbf5d85ab8d9f39d2d4f4bc63f017c5b53e90bf915cf22c2b7125901b

This contains an underscore prepend because of the fact that it's recently introduced and is is in public beta. Once enough confidence in it, it will be moved out of beta by renaming to signTypedData (don't worry the underscore alias will also exist for backwards compatibility).

Verifying signatures

You can use the verifyTypedData util to verify if a given signature is valid.

const expectedSignerAddress = signer.address;
const recoveredAddress = ethers.utils.verifyTypedData(domain, types, mail, signature);
console.log(recoveredAddress === expectedSignerAddress);
// true

Summary

That's pretty much it for this post. To summarise, we saw

how to define a domain separator
struct types
signing our struct object
verifying a given signature