Forem: teddav

From 0 to Bi(ge)nius: field extensions

teddav — Fri, 14 Feb 2025 14:15:06 +0000

We dive into “small field”, “field extension”, “binary field” and "field extension tower".

Because this article contains a lot of LaTeX, for better rendering you'll find it here: https://hackmd.io/@teddav/ry9wppnK1x

Tornado Cash with Halo2

teddav — Fri, 09 Feb 2024 06:12:12 +0000

tl; dr: You already heard of Tornado Cash? And Halo2? Great! Here we’re going to mix those 2 and re-write the Tornado Cash circuits from Circom to Halo2.

Here's the code: https://github.com/teddav/tornado-halo2/

Ok, let’s have a bit of a better intro…

“Zero Knowledge” is definitely a scary word (or 2 words)! When I started learning about it a few months ago I couldn’t understand anything 🤯

Recently I started to learn about Halo2, and after reading a bit of code and a few tutorials I tried to write my own circuit but was completely stuck: I had no idea how to do it...

That’s why I decided to write this article: to learn how to write a circuit, and teach some other people at the same time. Hopefully you’ll learn something from it.

This article may need to be corrected, or some things I’m saying might be completely wrong. If so: please message me so I can fix it (and improve myself at the same time 😄).

Let’s review where I am when starting this project:

read a few Halo2 tutorials
I think I understand what Chips and Circuits are, I have no idea what Layouter and Regions are for
I don’t know how to write my own circuit
I definitely don’t understand how things work “underneath”. Like how the proof is generated from the “halo2 board”

This is “part 1”. We’re going to start easy with an implementation as simple as possible, and the next parts will improve on it. I haven’t written part 2 (or 3, or…) yet, so if you’re here a few weeks/months from now and they are not published, it means I gave up 🥲 so you’re allowed to send me a twitter message and tell me you’re disappointed.

Here’s our plan for today:

i’ll give you a quick reminder on how tornado cash works
what is halo2?
how are we going to design our circuits
let’s code
- Hash
- Merkle
- Tornado circuit

Tornado Cash core

If you’re here, you probably already know what Tornado Cash is. If not → What is Tornado Cash?

We are going to rewrite the “original” Tornado. Not Tornado Nova. Nova is a newer version which is really interesting too but more complicated, so won’t look into it for now.

This is the repo we’re going to look at: Tornado core.

Tornado has 2 parts: circuits and smart contracts. We’ll only focus on the circuits here (though we might take a quick peek at the contracts for general understanding).

Circuits were written with Circom and that’s what we’re going to change. We’ll rewrite those circuits with Halo2, the PSE implementation (the KZG one, i’ll tell you more about it in the next section).

Ok thanks, but… how does it work? It’s actually really easy…

The “private” numbers

Everything is secured by only 2 numbers called a secret and a nullifier. That’s it.

Those 2 numbers alone are the only things keeping you from stealing the millions of ethers deposited in the tornado pools 😱

When you deposit money into Tornado, you need to generate a random secret and a random nullifier. Those numbers can go up to 21888242871839275222246405745257275088548364400416034343698204186575808495617 (see here or here) Yes it’s a big number, it’s more than $2^{253}$ .

Keep those numbers written in a secured location, you’re going to need them when you want to withdraw your money.

Tornado can be reduced to only 2 steps:

depositing
withdrawing

Let’s see them in more details.

Deposit

When you make a deposit, of course you have to send X ethers (depending on the pool) but you also have to send a commitment.

This commitment is just a hash of the previous 2 numbers: commitment = H(nullifier, secret).

Tornado uses a merkle tree to store those commitments. Again, I’m sorry 🙏 but I’m too lazy to explain to you what a merkle tree is. If you don’t know → Google.

A great way to see how it’s done is looking at the frontend/cli that was written by the Tornado devs. These are the tools most people used (still use?) to deposit money into Tornado.

Here we have the deposit() function of the cli, where the deposit is created

const deposit = createDeposit({
    nullifier: rbigint(31),
    secret: rbigint(31)
});

and the createDeposit() where you can clearly see how the commitment is a hash of nullifier + secret

function createDeposit({ nullifier, secret }) {
  const deposit = { nullifier, secret };
  deposit.preimage = Buffer.concat([deposit.nullifier.leInt2Buff(31), deposit.secret.leInt2Buff(31)]);
  deposit.commitment = pedersenHash(deposit.preimage);
  deposit.commitmentHex = toHex(deposit.commitment);
  deposit.nullifierHash = pedersenHash(deposit.nullifier.leInt2Buff(31));
  deposit.nullifierHex = toHex(deposit.nullifierHash);
  return deposit;
}

You can see how the random numbers are generated

const rbigint = (nbytes) => snarkjs.bigInt.leBuff2int(crypto.randomBytes(nbytes));

The numbers are 31 bytes long, which means up to $2^{248}$ , which is less than the max we saw earlier ( $2^{253}$ ). So we’re good!

Withdraw

This is where it becomes interesting. How do we withdraw our money?!

Obviously we’re going to use a zk proof:

to prove that we know the secret and the nullifier, but without revealing them
to prove that our commitment is in the merkle tree

Nullifier

But what is the nullifier used for exactly?

We need a way to ensure that a deposit is only withdrawn once. That’s what it’s for. When a withdrawal is made, the hash of the nullifier is stored in the contract, and therefore the commitment is “nullified”, it can’t be used again.

And why do we use the nullifierHash: because we want to make sure the nullifier is always kept private, so we just disclose its hash as a public value. It’s just as unique, and there’s no way to reverse it.

Let’s look at the withdraw() function. It takes as input the zk proof and the public inputs: root of the tree, nullifier hash, recipient, relayer, fee and refund.

If we look at the Withdraw circuit you’ll see that these are the same public inputs. The private inputs are:

the secret
the nullifier
the merkle tree inputs, which are kept private so that we don’t know which leaf of the tree is being withdrawn

More details

Wow… those explanations were longer than what I wanted to. At least now you should have a clear picture of how it works. I left out some features that are important but we’ll (maybe) come back to them when writing our own circuits.

For now, if you want more details check those links:

Understanding Zero-Knowledge Proofs Through the Source Code of Tornado Cash

Rareskills - How Tornado Cash Works

Why Halo2?

Tornado zk circuits were written using Circom and the Groth16 proving system. You can look at the circuit compile scripts in package.json and at the generateProof function.

One of the main issues with Groth16 is that it requires a circuit-based trusted setup. Which is annoying, and reduces trust. Then Plonk was created and allowed for a universal trusted setup. There are some limits, but basically: we do it once, and everybody can write circuits based on the same setup.

That’s it, let’s keep the explanations to the minimum 😊

Halo2 is a proving system created by Zcash based on top of Plonk and somehow makes it better/more efficient (I guess…). I’m not smart enough (yet 😉) to understand exactly why it’s so good, but some really smart people told me it’s good, so I’m just going to trust them.

So… today we’re going to use Halo2 to rebuild Tornado Cash.

As I said at the beginning, I’m actually writing this article as a way to learn Halo2. I have no idea how it works 😂 So I’m learning along the way.

Circuit design

As we just saw, the Tornado circuit is actually pretty simple. We only need 2 building blocks:

hashing
merkle tree

These are what we call “chips” in Halo2, they are like classes, or the equivalent of template in circom. You can reuse them when needed in other chips or circuits.

Ok… before going any further I have something to disclose. A lot of the code that I’m going to show you next, I haven’t written it myself. Most of the Hash chip and the Merkle chip are “heavily inspired” (ok… mostly copied) from https://github.com/summa-dev/halo2-experiments

(which is itself “inspired” by https://github.com/jtguibas/halo2-merkle-tree 😁). So we can say thanks to Enrico, Jin and John.

But since I’m writing this long article to explain everything, I guess that makes up for it!

HashChip

This chip takes 2 values and hashes them together.

In this part1 we’re going to use a “fake” hash function, in order to make things simple. I’ll give you more details in the next part when we start coding.

To be represented correctly in Halo2 we’re going to need 3 advice columns (our private values, the witness), 1 instance column (our public value, the resulting hash) and 1 selector. And we’ll use only 1 row.

Let’s say we want to hash together the word “hello” and “tornado” and that the hash ends up being “thoerlnlaodo”

What’s happening? The result of the hash is computed during proving (into “Advice 3”), but it was also passed by the prover as a public input in “Instance” (obviously the prover knows all the values, so he can compute the hash himself). Then, the circuit applies a constraint on the values and make sure that advice3 == instance. That’s how we prove that we know the 2 initial values (”hello” and “tornado”) which result in the hash “thoerlnlaodo”.

In reality, strings don’t exist in circuits. Everything is a number.

MerkleChip

Next we need a chip to compute/constrain our merkle tree. This chip is going to be a bit more complicated.

We still have 3 advice columns but we need 2 rows this time.

First row will take the hashes of the 2 nodes. Then the swap bit will tell us if the nodes are in the right order (left and right) or need to be swapped. On the next row, we have the nodes in the right order, so we only need to hash them. To get to the root of the tree, we just do that in a loop, and once we get to the root we compare it with the root passed as public input.

Circuits

In the code you’re going to see a HashCircuit and a MerkleCircuit. These are not used for our Tornado circuit. They are just here to test and understand better how circuits work.

The important part is our Tornado circuit. It’s going to take as private inputs:

nullifier
secret
path elements
path indices

The public inputs will be:

nullifier hash
merkle root

That’s it, I think we’re ready to dive into the code!

Just a quick summary of the relations in the circuit.

Code

Here’s the final code, so you can follow along and run it yourself.

Hash

As explained in the previous part, a Chip is like a class. There is a Chip trait in halo2_proofs::circuit but you don’t necessarily have to follow it, you can just write your chip the way you want it.

Circuits are different. In order to generate your proof correctly, you’ll have to follow the

halo2_proofs::plonk::Circuit trait.

Our chip takes a “config” which means a description of the columns you’re going to use (see the table above).

pub struct HashConfig {
    pub advice: [Column<Advice>; 3],
    pub instance: Column<Instance>,
    pub hash_selector: Selector,
}

Our first gate

Then we write our chip and the function configure() that’s where we define our polynomial constraint.

I’m still not sure what enable_equality is for, but I think it enables you to setup copy constraints later in your circuit. Every example I saw of halo2 had that, so I just copied it. You’re right, it’s not that smart… 🤔 Remind me to come back to it in part 2 and give a better explanation.

meta.create_gate("hash constraint", |meta| {
    let s = meta.query_selector(hash_selector);
    let a = meta.query_advice(advice[0], Rotation::cur());
    let b = meta.query_advice(advice[1], Rotation::cur());
    let hash_result = meta.query_advice(advice[2], Rotation::cur());
    vec![s * (a * b - hash_result)]
});

In order to understand this code, first I have to tell you how I cheated. Instead of writing an actual hash function, I wrote something really stupid. Our hash function takes 2 values and multiplies them to return a hash (remember that every value is a number). If I had to write it in python it would be:

def hash(a, b):
    return a * b

Again, I promise in part 2 I’ll improve this. We’ll use the Poseidon hash and everything is going to look really nice 😎

Let’s try to explain everything once, so it will be easier for the next gates.

Currently our gate looks like this: s * (a * b - hash_result) = 0 which can be translated to: multiply a and b and subtract hash_result , if that equals 0 we’re good. Otherwise the hash_result is wrong.

s is what we call a “selector”, it’s a boolean that’s going to activate or not the constraint. If it’s 0 then the result is 0 so the constraint passes, and we don’t need to make sure a*b = hash_result. If it’s 1 then a*b must equal hash_result.

In order to get values a and b we use

let a = meta.query_advice(advice[0], Rotation::cur());

Which means: get the first row (Rotation::cur()) or the first advice column (advice[0]). That’s how things always work in halo2: columns and rows. If you wanted to access previous or next rows you could have done Rotation::prev() or Rotation::next() for example.

Regions and Layouter

Again, I’m going to tell you how I think of it. It might not be the best representation (but hopefully it’s not wrong…), but that’s how I understand Halo2 for now. For part 2, I’ll try to ask some other people to help me visualise it better and I’ll give you another perspective.

Halo2 represents everything in a big table (like an Excel spreadsheet). You can use that table however you want, but it can quickly get messy (that’s why we have regions).

Of course there is also a cost when generating the proof: each new column that you’re using is more expensive, while rows are cheaper. But remember that any new cell you’re using means more computing power.

Going back to our Excel comparison, if you want to compute the sum of 5 numbers, you could write your 5 numbers in B5 to B9, and then write a “sum()” formula in C4. If you wanted to use the sum result somewhere else in the table, let’s say “F15”, so you’d just use a reference to cell C4.

Halo2 works the same, you just assign values to cells, and then you reference them. To make things more efficient, everything has to be divided into regions, which are blocks of cells. So you define a new region, and in this region you automatically have access to the advice/instance columns that you pre-defined. You fill your cells and know that your constraints (that you added in configure()) will be enforced.

You can also add new constraints, and even constrain cells between regions! Wow that’s awesome 😍

The layouter is just a helper to create regions. In the background it optimises how regions are created so that they don’t overlap, and so that the cost is as low as possible. When you want a new region, you ask the layouter for it layouter.assign_region and then you can just use it without worrying about messing things up on the board.

Hash it

Now we can look at the hash() function which is a bit more complicated.

The function signature is

fn hash(
    &self,
    mut layouter: impl Layouter<F>,
    left_cell: AssignedCell<F, F>,
    right_cell: AssignedCell<F, F>,
) -> Result<AssignedCell<F, F>, Error>

left and right could be values, and it would make the function a bit simpler. But being AssignedCell makes the function more generic, and we can now use a ref to any cell on the board.

First we assign a region

layouter.assign_region( || "hash row", |mut region| {

then we copy the value in the left cell to our first advice column (first row)

left_cell.copy_advice(
    || "copy left input",
    &mut region,
    self.config.advice[0],
    0,
)?;

same for the right cell to second advice column and compute the hash in third advice column

let hash_result_cell = region.assign_advice(
    || "output",
    self.config.advice[2],
    0,
    || left_cell.value().cloned() * right_cell.value().cloned(),
)?;

Finally we return a reference to the cell where the hash is computed.

Hash circuit

Imagine that someone publicly revealed a hash H and you want to prove that you know 2 values a and b that when hashed together will give H. But of course you want to keep a and b private.

For that, we look at the Hash circuit.

It takes our 2 private inputs a and b

pub struct HashCircuit<F> {
    pub a: Value<F>,
    pub b: Value<F>,
}

And our public input is our hash H = a * b

let public_inputs = vec![Fp::from(a * b)];

In a circuit, the most interesting part happens in the synthesize function. Since our hash function takes cells as input, we’re going to create a temporary region that’s going to hold our a and b values, and then pass the cells to be hashed.

let (left, right) = layouter.assign_region(
    || "private inputs",
    |mut region| {
        let left = region.assign_advice(
            || "private input left",
            config.advice[0],
            0,
            || self.a,
        )?;

        let right = region.assign_advice(
            || "private input right",
            config.advice[1],
            0,
            || self.b,
        )?;

        Ok((left, right))
    },
)?;

let chip = HashChip::construct(config);
let hash_result_cell = chip.hash(layouter.namespace(|| "hasher"), left, right)?;

And the most important part is the last line

layouter.constrain_instance(hash_result_cell.cell(), config.instance, 0)

That’s where we set our constraint. instance is the column where our public inputs are. Here we make sure that the resulting hash which is in hash_result_cell is equal to the hash H we publicly displayed.

Merkle

Now let’s go into the MerkleChip. This should be faster since we already understood all the foundations.

When we pass values to our hash function, the order in which we pass a and b is important H(a,b) != H(b,a). Right now our current hash function is really dumb, so the order of the values a and b does not matter (we are just multiplying them). But when we will “upgrade” it and start using Poseidon it will matter.

For our merkle tree we’ll pay attention to the order of the nodes (left/right). That’s why we need a swap_bit: are the nodes in the correct order, or do they need to be swapped before being hashed? We also need 2 selectors to go with it:

swap_selector: check the swap bit → swap or not
swap_bit_bool_selector: the swap bit should be a boolean, so this checks that the swap bit is 0 or 1

Gates

Our first gate checks that the swap bit is 0 or 1. This can be re-written as

def is_zero_or_one(value):
    return value * (1 - value) == 0

The second gate is more complex, but it’s not that complicated 😊 I’ll leave it to you to try to understand it. Just to make sure it’s clear:

left[0] means left column, row 0

left[1] means left column, row 1

And that’s what we’re checking

if swap_bit == 1:
    return left[0] == right[1] and right[0] == left[1]
else:
    return left[0] == left[1] and right[0] == right[1]

That’s the actual constraint

let constraint1 = (right[0] - left[0]) * swap_bit + left[0] - left[1];
let constraint2 = (left[0] - right[0]) * swap_bit + right[0] - right[1];

Compute the merkle tree

Now that our gates are in place, we need to compute the merkle tree root. In merkle_prove_layer :

we assign our left and right nodes on row 0
we check the swap bit
on row 1 we assign left and right (in the correct order this time)
we hash the nodes
we return the cell where the hash result is

In prove_tree_root we just loop over each layer until we reach the root.

Again, there is a MerkleCircuit where you can see it in action.

The most important part is

layouter.constrain_instance(root_cell.cell(), config.instance, 1)?;

That’s where we validate that the root we computed in the circuit is equal to the root we passed as a public input.

Tornado circuit

And… finally! We arrive to our Tornado circuit. Here are the private inputs

pub struct TornadoCircuit<F> {
    nullifier: Value<F>,
    secret: Value<F>,
    path_elements: Vec<Value<F>>,
    path_indices: Vec<Value<F>>,
}

And the public inputs

let public_input = vec![nullifier_hash, root];

We are not fully respecting the real Tornado circuit which also takes as public input:

recipient
relayer
fee
refund

These values are definitely important in the zk proof and should be checked when verifying the proof, but these are useless for our current understanding of Halo2. So won’t bother using them.

Here are the steps taken in the circuit:

compute the nullifier hash
check that it matches the public nullifier hash
compute the merkle tree root
check that it matches the public merkle root

That’s it. Really easy.

Range check (not)

I haven’t set up any gate in the TornadoChip, which is a mistake because our circuit will be “under-constrained”.

We should definitely range check our private inputs. Range check means checking that a value is within a certain range, so between a lower bound and an upper bound. But again, let’s keep that for “part 2”.

Here is the range check in the original Tornado circuit: checking that nullifier and secret are less that 248 bits, which means less than $2^{248}$ .

Nullifier hash and commitment

In the TornadoChip you’ll find a helper compute_hash function. This makes the nullifier hash and the commitment easier to compute.

This time everything should be easy to understand, so I’m not going to give too much explanations.

Just a comment on the most important constraints:

layouter.constrain_instance(nullifier_hash_cell.cell(), config.clone().instance, 0)?;
layouter.constrain_instance(merkle_root_cell.cell(), config.clone().instance, 1)?;

First we make sure the nullifier hash matches the first row of our instance column (our public inputs), and then we also validate the merkle root against the second row.

And just like that, we have our Halo2 Tornado Cash! 🥳🥳

What’s next

I mentioned a lot “part 2” because I wanted to keep this first part as simple as possible. Here’s what we need to do to improve our circuit:

use a real hash function → Poseidon
range check the values

And to get a deeper understanding of Halo2, we could try to actually generate the proof, and generate the verifier solidity contract, so that we have a fully functioning Tornado Cash.

I have no idea how to do that yet 😂

PLEASE! If you have some ideas or advice, or if some parts of this article need to be improved → send me a message.

Foundry: add a cheatcode

teddav — Tue, 04 Apr 2023 08:45:19 +0000

We scratched the surface of Foundry’s code in part 1. Let’s go a bit deeper and try to create a new cheatcode this time.

What are we going to do?

We’ll try to write a getMemory(uint256 start, uint256 end) cheatcode. Which sounds pretty straightforward: get the current memory from index start to end. We’ll also add “bonus” cheatcodes that automatically format that memory, to easily be logged.

You can find the PR (still in review at the time of publishing this article) here and the commit I’m going to follow (in case the code changes before it’s merged).

Why this cheatcode?

Memory is hard to get in Solidity. You can only get it in chunks of 32 bytes (with mload), and sometimes it’s useful to have a better overview of the memory. That’s why.

Linter

Before we continue, a little tip…

Since my rust-analyzer config wasn’t using the nightly flag, the code kept getting changed when I was saving files. I’m using VSCode and didn’t want to change my config for all my projects, so I added a .vscode folder and a settings.json with

{
  "rust-analyzer.rustfmt.extraArgs": ["+nightly"]
}

Add a cheatcode

First I modified the minimum to make sure I had the correct process. I followed the steps in Foundry’s doc:

add the function signature to the abigen! macro so a new HEVMCalls variant is generated
implement the cheat code handler
add a Solidity test for the cheatcode under testdata/cheats
add the function signature to forge-std Vm interface

So I started by adding the function signature to evm/src/executor/abi/mod.rs

// Bindings for cheatcodes
ethers::contract::abigen!(
    HEVM,
    r#"[
            ...
            getMemory(uint256,uint256)
        ]"#,
);
pub use hevm::{HEVMCalls, HEVM_ABI};

Then in evm/src/executor/inspector/cheatcodes/util.rs in apply function

pub fn apply<DB: Database>(
    state: &mut Cheatcodes,
    data: &mut EVMData<'_, DB>,
    call: &HEVMCalls,
) -> Option<Result<Bytes, Bytes>> {
    Some(match call {
            ...
            HEVMCalls::GetMemory(inner) => get_memory(inner.0, inner.1),
            _ => return None,
    })
}

and our get_memory function

pub fn get_memory(start: U256, end: U256) -> Result<Bytes, Bytes> {
    println!("get_memory: {start} {end}");
    Ok(Bytes::new())
}

Just like in part 1, I set up a project with a forge Test to test my changes in real time. In that project, as with any project using Foundry, you have a lib directory with forge-std. You’ll need to add your cheatcode there, so that it’s recognized by your test

In my-project/lib/forge-std/src/Vm.sol we add the function signature

function getMemory(uint256 start, uint256 end) external;

And write our first test

pragma solidity 0.8.18;
import "forge-std/Test.sol";

contract MemoryTest is Test {
    function testBasicLog() public {
        vm.getMemory(2, 5);
    }
}

The test passes, no errors, and we get our log printed to the console:

“get_memory: 2, 5”

We are good to continue! 💪

Let’s write our cheatcode

Access the memory

Cheatcodes are called in the apply_cheatcode function in evm/src/executor/inspector/cheatcodes/mod.rs which itself is called in the call function in the same file. Those 2 functions are implementations of the Cheatcodes struct.

Unfortunately we cannot access the memory directly from the cheatcode. The parameters of the call function are:

fn call(
  &mut self,
  data: &mut EVMData<'_, DB>,
  call: &mut CallInputs,
  is_static: bool,
) -> (Return, Gas, Bytes) {}

But the memory is only accessible from the Interpreter, which is a parameter of step:

fn step(
  &mut self,
  interpreter: &mut Interpreter,
  data: &mut EVMData<'_, DB>,
  _: bool,
) -> Return {}

So we’ll have to store the memory somewhere for it to be accessible in our cheatcode. I decided to add a memory field on the Cheatcodes struct

pub struct Cheatcodes {
    ...
    /// Current's call memory
    pub memory: Vec<u8>,
}

And copy the memory to it in fn step()

fn step(
  &mut self,
  interpreter: &mut Interpreter,
  data: &mut EVMData<'_, DB>,
  _: bool,
) -> Return {
  self.memory = interpreter.memory.data().clone();

    ...
}

We can now access the memory from our fn get_memory() function!

Return our memory slice

Now that we have access to the memory the rest is easy. We get the requested part from it and return it. The parameters of our getMemory(uint256,uint256) function are passed as U256. We just convert them to usize, get our memory slice and return it as Bytes

HEVMCalls::GetMemory(inner) => {
  let start = (inner.0 as U256).as_usize();
  let end = (inner.1 as U256).as_usize();
  let mem = state.memory[start..=end].to_vec();
  Ok(ethers::abi::encode(&[Token::Bytes(mem)]).into())
}

To help us with the Bytes encoding, ethers-rs has an encode() function where you pass a Vector of Token and it formats the data properly.

The actual code I wrote was a bit longer because I added some error handling and some extra cheatcodes, but if we just wanted to implement the getMemory cheatcode, we would be done.

I’ll give some more details at the end of the article. For now let’s finish our “simple” cheatcode with unit tests.

Unit tests

In testdata/cheats we first add the function signature for our cheatcode to Cheats.sol

Then we can create a new test file GetMemory.t.sol

How are tests run?

I was trying to understand how tests are run when executing cargo test.

From what I understood, what matters to us is in forge/tests/it/cheats.rs. You can see the test that is going to test all cheatcodes: test_cheats_local.

Something a bit annoying when running tests: it logs info for all the tests that should be run, not only the only running. So you have to search through the logs to find your test. If anyone knows how to avoid that, please message me 🙏

$ cargo test test_cheats_local -- --show-output
or
$ cargo watch -x "test test_cheats_local -- --show-output"

Our test

This is what GetMemory.t.sol looks like

// SPDX-License-Identifier: Unlicense
pragma solidity >=0.8.0;

import "ds-test/test.sol";
import "./Cheats.sol";

contract GetMemoryTest is DSTest {
    Cheats constant vm = Cheats(HEVM_ADDRESS);

    function testGetMemory() public {
        assertEq(vm.getMemory(0, 31), abi.encodePacked(bytes32(0)));

        assembly {
            mstore(0, 0x4141414141414141414141414141414141414141414141414141414141414141)
            mstore(0x20, 0xbabababababababababababababababababababababababababababababababa)
        }
        bytes memory mem1 = vm.getMemory(0, 12);
        bytes memory mem2 = vm.getMemory(0x20, 0x3f);

        assertEq(mem1.length, 13);
        assertEq(mem2.length, 32);

        assertEq(mem1, hex"41414141414141414141414141");
        assertEq(mem2, hex"babababababababababababababababababababababababababababababababa");

        bytes memory mem3 = vm.getMemory(0x60, 0x7f);
        assertEq(mem3.length, 32);
        assertEq(mem3, abi.encodePacked(bytes32(0)));
    }
}

Done! 🎉 If you wanted to implement your own cheatcode you would be done since everything is working as expected. But before I sent it to review I decided to add a little extra work:

error handling
“bonus” cheatcodes

Overtime

The goal of the cheatcode is to make it easy to inspect the memory. Receiving the entire memory as bytes is already helpful, but why not format it as a nice string with indexes? So I added a getMemoryFormattedAsString and getMemoryFormatted cheatcodes. The first one returns a long string ready to be printed with console.log, and the second one returns a FormattedMemory struct, so you have a bit more control.

struct FormattedMemory {
    string header;
    string[] words;
}

It might be useless, I don’t know… we’ll see if people end up using those or not.

Error handling

I had a hard time understanding how to return errors properly from the cheatcode. I struggled a bit with the Bytes formatting and the fact that apply() in utils is supposed to return Option<Result<Bytes, Bytes>>.

When running my tests I would get

Cheatcode was unhandled. This is a bug.

or The application panicked (crashed). This is a bug. Consider reporting it at https://github.com/foundry-rs/foundry

To make it easier, I created a check_format_memory_inputs. Annoyingly, I couldn’t figure out how to have a nice error handling using ? so I add to use a match statement to propagate the error correctly.

HEVMCalls::GetMemory(inner) => {
  match check_format_memory_inputs(inner.0, inner.1, state.memory.len() as u32) {
      Ok((start, end)) => {
          let mem = state.memory[start as usize..=end as usize].to_vec();
          Ok(ethers::abi::encode(&[Token::Bytes(mem)]).into())
      }
      Err(err) => Err(format!("Error getMemory: {}", err).encode().into()),
  }
}

fn check_format_memory_inputs(
    start: U256,
    end: U256,
    memory_length: u32,
) -> Result<(u32, u32), String> {
    let start = u32::try_from(start).map_err(|err| format!("start parameter: {}", err))?;
    let end = u32::try_from(end).map_err(|err| format!("end parameter: {}", err))?;
    if start > end {
        return Err(format!("invalid parameters: start ({}) must be <= end ({})", start, end))
    }
    if end > memory_length - 1 {
        return Err(format!(
            "invalid parameters: end ({}). Max memory offset: {}",
            end,
            memory_length - 1
        ))
    }
    Ok((start, end))
}

Future improvements

You can see the entire implementation after which this article was written in this commit.

This cheatcode was meant to be a first “dirty” version. It’s not ideal because it modifies the same memory you’re trying to inspect. The memory is modified 3 times:

when calling the cheatcode (to store the arguments of the call)
when returning: the string or bytes are added to memory
when using console.log again it needs to add the data to memory before logging it

Ideally we would want to log directly the memory without modifying it. I’ll try to prepare a 2nd version soon! Why not write another article about it to close this series. We’ll see…

Your turn!

Now that you finished this article, it’s your turn to think of a useful cheatcode and implement it. If it’s useful for you, it might be useful for others. You can go ask beforehand on the Telegram channel if anyone is interested.

Follow me on Twitter: 0xteddav

And you can message me there if you have any question, or if I made a mistake somewhere.

Solving the Ethernaut with Yul

teddav — Sat, 04 Mar 2023 11:23:46 +0000

After learning the basics of Solidity assembly in Part 1: Playing with Yul let’s now dive deeper! 💪

We’re going to solve the Ethernaut challenges, written by Openzeppelin, entirely in assembly. We’ll use some more advanced assembly and also learn about Ethereum security exploits. On top of that we’ll use Foundry, built by Paradigm, to run our scripts, tests, and deploy to Goerli testnet.

Hopefully you’ll learn a lot going through this article!

The idea is that you should try the challenges yourself, one by one, and after each challenge go checkout my repo to understand the Yul version. You’ll see that throughout the challenges, the same assembly techniques are used over and over so it might be a bit boring after a while.

This article is not meant to be read alone. I just wrote here some explanations of the code for some difficult parts. So your first step should be to go to my Ethernaut-yul repo

I will not give detailed explanations on how to solve each challenge. Most challenges are pretty basic, and you’ll find a lot of explanations if you search online. This tutorial is mostly focused on Assembly.

evm.codes is a great website if you don’t understand what some opcodes do.

Just like with Part 1, if you have any questions, or issues understanding what I wrote, or if you just wanna chat → message me on Twitter 0xteddav

First: setup the repo

This repo is a mix of Foundry and Hardhat, so it can also be a good boilerplate for your future projects (you’re welcome 😁).

Install Foundry: https://github.com/foundry-rs/foundry/#installation

Then run yarn to install the dependencies in package.json

And copy .env.tmpl to .env and enter the correct values for your private key and the RPC you’re going to use.

Levels

Each level is solved by a forge script. You’ll find all scripts in script/foundry.

You’ll find a template in Level.s.sol that you can copy/paste. You’ll just need to:

specify the address of the level
the network you’re playing on (either “local” or “goerli”)
change the interface of the level you’re playing

If you’re running the levels locally, you have to run anvil (or hardhat node) as fork of Goerli

$ anvil -f https://rpc.ankr.com/eth_goerli

Then you can run the script with:

$ forge script ./script/foundry/XX_LevelName.s.sol

When you’re ready to actually send the transactions on-chain, you “execute” the broadcast by adding —-broadcast

$ forge script ./script/foundry/XX_LevelName.s.sol --broadcast

Each script has a baseVersion() where the level is solved with Solidity, and the same code is re-written in Yul in the yulVersion() function.

When a contract needs to be deployed, I usually wrote the Solidity version, commented it out and re-wrote the Yul version underneath.

In the test directory you’ll find some forge tests I wrote while working on some levels, so sometimes you can see what my thinking process was. You can run those tests with

$ forge test -vvvvv --mt testNameOfTheTest

Let’s now detail how I solved some of the levels!

HelloEthernaut

Didn’t use Yul for this level as it was just used to setup everything. I might come back to it if anyone is interested. It could be fun to parse the string response in assembly.

Fallback

Let’s start with the basics. We need to call contribute() with a value of 1

let dest := sload(instance.slot)

We load the address of the instance which is in the instance variable. We could figure out the storage slot of instance ourselves (you’ll have to go down the chain of the parent contracts we are inheriting from, which is annoying…), but in Yul we can easily get that value with .slot

Let’s detail how we call an external function with Yul. We’ll use that same pattern a lot throughout the challenges

mstore(0, "contribute()")
mstore(0, keccak256(0, 12))

To call a function we need its “selector”. You can read more about it in the Solidity doc. In Solidity we would do: bytes4(keccak256(abi.encodePacked("contribute()")))

First we store in memory at 0 the signature of the function we want to call: contribute()(notice that the length is 12). Our memory looks like this

0x00	0x636f6e7472696275746528290000000000000000000000000000000000000000
0x20	0x0000000000000000000000000000000000000000000000000000000000000000
0x40	0x0000000000000000000000000000000000000000000000000000000000000080

(if you don’t understand what “636f6e747269627574652829” is, lookup “string to hexadecimal” on Google 😁)

Then we hash that signature with keccak256(0, 12) and store the result at 0 in memory. This will overwrite the previous value, but we don’t care because we won’t need it anymore. Our memory is now

0x00	0xd7bb99ba2c5adddd21e5297f8f4a22a22e4de232bc63ec1e2ec542e79805202e
0x20	0x0000000000000000000000000000000000000000000000000000000000000000
0x40	0x0000000000000000000000000000000000000000000000000000000000000080

The function selector for contribute() will be the first 4 bytes of that: 0xd7bb99ba

Then we execute our call. Go check evm.codes for details on the parameters of the CALL opcode.

let success := call(gas(), dest, 1, 0, 4, 0, 0)
if iszero(success) {
    revert(0, 0)
}

dest is the address of the contract we’re calling. We pass it a value of 1, then we tell it to get the data from memory starting at 0 up until 4 (our function selector), and then we don’t expect a return value so we pass 0 and 0. success will be either 0 or 1 depending on the result of the call. So we check with iszero and if the call failed, we revert.

We just made our first external call. That was easy! 🎉

Let’s do another example: a view call. Further down the code you’ll find

mstore(0, "owner()")
mstore(0, keccak256(0, 7))
success := staticcall(gas(), dest, 0, 4, 0, 0x20)
if iszero(success) {
    revert(0, 0)
}

Here we call owner() on the instance, but this time we expect a result. The result will be stored in memory at 0 and will be 32 bytes long (0x20). We use staticcall because this is a view function and will not modify the state. More details… in the doc.

Then we load the returned value and check if it matches our player. Otherwise we revert

let owner := mload(0)
if iszero(eq(owner, sload(player.slot))) {
    revert(0, 0)
}

CoinFlip

This level couldn’t be solved with a Foundry script because each call to exploit() needs to be sent in a separate transaction. So you’ll find the solver in a Hardhat script in script/hardhat/3_CoinFlip.ts

Telephone

This level introduces a new pattern: deploying a contract.

You need to understand the difference between “creation code” (or “init code”) and “runtime code”. You can find explanations in the doc or in this article, or on Stackoverflow.

We want to deploy our TelephoneExploit contract. The contructor takes 1 argument address _telephone. The steps are:

store the init code in memory
add the constructor parameter
call CREATE opcode

We can only access the creation code in Solidity. So we’ll have

bytes memory creationCode = type(TelephoneExploit).creationCode;

This makes everything easier for us because it automatically stores the code to memory. You should remember how bytes are stored in memory. Let’s assume that there is nothing else in memory (which should be the case since there is no other instruction), so our memory should start at 0x80. Here’s what it should look like

0x80	size of the code
0xa0	the code of TelephoneExploit…
0xc0	the code of TelephoneExploit…
0xe0	…

Since creationCode is the address in memory where the data starts. Since we assumed that the data was stored at 0x80 we would have creationCode == 0x80

if we do mload(creationCode) (which is equal to mload(0x80)) this will return the size of the TelephoneExploit contract. Then the actual code starts 32 bytes later so we do add(creationCode, 0x20)

let contractSize := mload(creationCode)
let contractOffset := add(creationCode, 0x20)

We just need to store the constructor argument. This is stored at the end of the contract code. Since we know the size of the contract, we just add it to the start of the contract’s code. The address for _telephone should be the address of instance so we use sload(instance.slot)

let offsetConstructorArg := add(contractOffset, contractSize)
mstore(offsetConstructorArg, sload(instance.slot))

And then we just have to use CREATE and our contract is deployed! 🎉

let telephoneExploit := create(0, contractOffset, mload(creationCode))

You also noticed the getOwner() function. Our first function in Yul. Pretty cool!

function getOwner(_contract) -> _owner {
    mstore(0, "owner()")
    mstore(0, keccak256(0, 7))
    let success := staticcall(gas(), _contract, 0, 4, 0, 0x20)
    if iszero(success) {
        revert(0, 0)
    }
    _owner := mload(0)
}

Unfortunately, Yul functions are only usable in the same assembly block they were defined in. So we’ll not be using them too much because we will have to re-write them anyway.

Token

Let’s see how we can call a function with a parameter, and get a result back.

mstore(0, "balanceOf(address)")
mstore(0, keccak256(0, 18))
mstore(0x4, sload(player.slot))
pop(staticcall(gas(), token, 0, 0x24, 0, 0x20))
let startBalance := mload(0)

As you’ve seen before: we get the selector for balanceOf(address) but this time we are going to add an argument. We do mstore(0x4, sload(player.slot)). We store the address of the player at offset 4. Therefore, the first 4 bytes will the function selector, and the next 32 bytes will represent the address. For example let’s say the address is 0x7c019b7834722f69771cd4e821afc8e717baaab5

The data will be: 0x70a082310000000000000000000000007c019b7834722f69771cd4e821afc8e717baaab5

And its length is 36 bytes (0x24).

Notice that we use pop because we don’t want to check if the call succeeded or not. If it didn’t succeed, the transaction will revert anyway at some point and we’ll fail the challenge. But in production you should always check if the call succeeded or not!

King

Let’s try something new: revert with a string. Check contracts/9_King.sol.

You’ll find here and here explanations on how errors work in Solidity. Just like functions, errors have selectors too. The selector for an error string is Error(string). So we’ll need to have it, store it in memory and then store our string. Easy!

Store the selector

mstore(ptr, "Error(string)")
mstore(ptr, keccak256(ptr, 13))

Store the string

mstore(add(ptr, 4), 0x20)
mstore(add(add(ptr, 4), 0x20), 9)
mstore(add(add(ptr, 4), 0x40), "not owner")

Remember how string are handled by the EVM (just like bytes): first the offset, then the length of the string and finally the string itself. And then we revert with the data we just stored: revert(ptr, 0x64)

Reentrancy

I’m not going to do too much explanation, as it’s the same process as before, but here just notice that we have to store more than 1 parameters for the exploit() function. If we tried to store them at memory 0 we would overwrite the free memory pointer at 0x40 which will lead to dangerous behaviour and probably fail our transaction. So instead we store our data in memory where we have space available → where the free memory pointer points us to.

Note that in the previous level (King), when we stored our error string, we did overwrite the free memory pointer. But we didn’t care since we stopped the execution and reverted right after.

Privacy

In this level we need a bytes16 but you know that values are stored on 32 bytes in the EVM so we need a bitmask to erase some of the bytes. bytes are stored in the higher-order bytes (left aligned). So if we want the first 16 bytes we need to create a mask that looks like this 0xffffffffffffffffffffffffffffffff00000000000000000000000000000000

let mask := shl(128, sub(exp(2, 128), 1))

Which is 2**128 - 1 << 128

Then we just need to apply our mask: let key := and(data2, mask)

Preservation

In contracts/16_Preservation.sol we have a bitmask for an address. An address in Ethereum is 20 bytes (160 bits) so our mask will be 2 ** 160 - 1 → sub(exp(2, 160), 1)

Recovery

We compute the address where the contract will be deployed

address(uint160(uint256(keccak256(abi.encodePacked(bytes1(0xd6), bytes1(0x94), address(instance), nonce)))))

You’ll find some explanations on this here and here

In Foundry there is a convenient cheatcode for that: computeCreateAddress

MagicNumber

Here you can clearly see the difference between creation code and runtime code that we talked about previously. The runtime code is the code that will be returned by the constructor of the contract.

constructor(bytes memory bytecode) {
    assembly {
        return(add(bytecode, 0x20), mload(bytecode))
    }
}

We pass in bytecode what we eventually want the runtime code to be, and we just need to return it from the constructor. Our runtime code will be 602a60005260206000f3 which is translated to

PUSH1 42
PUSH1 0
MSTORE
PUSH1 32
PUSH1 0
RETURN

Puzzle Wallet

Wow! This one is a bit more advanced. More external calls than usual, and a lot of bytes encoding 😱 So i’ll try to give you some explanations.

Let's think about what we want to encode:

→ call multicall(bytes[]) with:

a call to deposit()
another call to multicall(bytes[])
- a subcall to deposit()

So what is our call data going to look like?

In Solidity, bytes are encoded in three parts in calldata:

An offset where the length of the bytes can be found.
At the offset specified in step 1, the length of the bytes is stored.
Then, to the offset from step 1, we add 0x20 and that’s where the actual bytes are stored.

This encoding is used to allow the EVM to efficiently read the length of the bytes being passed as arguments in a function call, without needing to parse the entire data.

A quick example as a reminder?

function myFunction(uint256 myUint, bytes memory myBytes, uint256 myOtherUint) public {}

Let's say we want to call this function with the following values:

myUint: 123
myBytes: 0xabcdef
myOtherUint: 456

Here's how the calldata would be encoded:

The function selector: bytes4(keccak256(abi.encodePacked("myFunction(uint256,bytes,uint256)"))) → 0xe329087e
The first parameter (myUint): 000000000000000000000000000000000000000000000000000000000000007b
The second parameter (myBytes):
1. The offset where we'll find the length: 0000000000000000000000000000000000000000000000000000000000000060
2. At that offset, the length of the bytes: 0000000000000000000000000000000000000000000000000000000000000003
3. At offset + 0x20, the actual bytes: abcdef0000000000000000000000000000000000000000000000000000000000
The third parameter (myOtherUint): 00000000000000000000000000000000000000000000000000000000000001c8

Putting it all together, the resulting calldata would be:

0xe329087e
000000000000000000000000000000000000000000000000000000000000007b
0000000000000000000000000000000000000000000000000000000000000060
00000000000000000000000000000000000000000000000000000000000001c8
0000000000000000000000000000000000000000000000000000000000000003
abcdef0000000000000000000000000000000000000000000000000000000000

Now, to the more complex stuff: our multicall(bytes[])

Let’s start with the first deposit() call.

function multicall(bytes[] calldata data) external {}
function deposit() external {}

The function selector for multicall(bytes[]): bytes4(keccak256(abi.encodePacked("multicall(bytes[])"))) → 0xac9650d8

The function selector for deposit(): bytes4(keccak256(abi.encodePacked("deposit()"))) → 0xd0e30db0

For arrays, calldata encoding is similar to bytes except we first need to store the length of the array. So our calldata will look like:

function selector
offset where we'll find the length of the array
length of array
list of offsets where the data will be found for each element
data

Our multicall(bytes[]) with deposit()

0xac9650d8
0000000000000000000000000000000000000000000000000000000000000020 offset
0000000000000000000000000000000000000000000000000000000000000001 length of array
0000000000000000000000000000000000000000000000000000000000000020 offset of first element of array
0000000000000000000000000000000000000000000000000000000000000004 length of data -> 4 bytes, which is the length of the function selector
d0e30db000000000000000000000000000000000000000000000000000000000 data -> the function selector of `deposit()`

And now, our calldata with everything

0x00	0xac9650d8
0x00	0000000000000000000000000000000000000000000000000000000000000020
0x20	0000000000000000000000000000000000000000000000000000000000000002
0x40	0000000000000000000000000000000000000000000000000000000000000040
0x60	0000000000000000000000000000000000000000000000000000000000000080
0x80	0000000000000000000000000000000000000000000000000000000000000004
0xa0	d0e30db000000000000000000000000000000000000000000000000000000000
0xc0	00000000000000000000000000000000000000000000000000000000000000a4
0xe0	ac9650d800000000000000000000000000000000000000000000000000000000
0x100	0000002000000000000000000000000000000000000000000000000000000000
0x120	0000000100000000000000000000000000000000000000000000000000000000
0x140	0000002000000000000000000000000000000000000000000000000000000000

0xac9650d8
0000000000000000000000000000000000000000000000000000000000000020 offset of array length
0000000000000000000000000000000000000000000000000000000000000002 length of array -> 2
0000000000000000000000000000000000000000000000000000000000000040 offset of 1st element of array: `deposit()` call
0000000000000000000000000000000000000000000000000000000000000080 offset of 2nd element: `multicall(bytes[])` call

0000000000000000000000000000000000000000000000000000000000000004 first element. This is the call to deposit(). We already covered it.
d0e30db000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000000000a4 second element. This is the inner multicall(). The data size is 0xa4 -> 164 bytes
ac9650d800000000000000000000000000000000000000000000000000000000
0000002000000000000000000000000000000000000000000000000000000000
0000000100000000000000000000000000000000000000000000000000000000
0000002000000000000000000000000000000000000000000000000000000000
00000004d0e30db0000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

Let separate the data of the second call. This is just another call to multicall(bytes[]) so it’s easy to understand

ac9650d8
0000000000000000000000000000000000000000000000000000000000000020 offset
0000000000000000000000000000000000000000000000000000000000000001 length
0000000000000000000000000000000000000000000000000000000000000020 offset of element 1
0000000000000000000000000000000000000000000000000000000000000004 length of data
d0e30db000000000000000000000000000000000000000000000000000000000 data -> function selector for `deposit()`
00000000000000000000000000000000000000000000000000000000         -> this is just some padding to make sure we have a multiple of 32 bytes

Motorbike

Just a comment on this level: when we load the exploitSelector, we do not apply a mask to it. We dont really care because when we pass it, we specify that the length of is 4 bytes. The rest will be ignored. But remember that if you actually send that transaction, it will be more expensive, because you’re sending more bytes. And calldata bytes are expensive!

mstore(add(fmp, 0x24), 0x40)
mstore(add(fmp, 0x44), 4) // <--- here we specify: "only read the next 4 bytes" (the selector for `exploit()`)
mstore(add(fmp, 0x64), exploitSelector) // <-- but here we store the entire hash, not only the 4-bytes selector

DoubleEntryPoint

Another bitmask to get only the 4 bytes of the selector

let selectorMask := shl(224, sub(exp(2, 32), 1))

If you open contracts/26_DoubleEntryPoint.sol the signature of the function is function handleTransaction(address user, bytes calldata msgData) external

So msgData is in calldata. It was not copied to memory, so we cannot use mload. We need to use calldataload instead to load the data.

We can easily compute ourselves the offset where we’ll find the data, but there is an easier way: .offset

First we get the function selector by applying the selectorMask bitmask.

Then we need to get the 3rd parameter: remember, the function is delegateTransfer(address to, uint256 value, address origSender) and we only want origSender

let msgSelector := and(calldataload(msgData.offset), selectorMask)
let origSender := calldataload(add(msgData.offset, 0x44))

GoodSamaritan

Here we revert with a Solidity custom error. Nothing special, it works just like function selectors

mstore(0, "NotEnoughBalance()")
mstore(0, keccak256(0, 18))
revert(0, 4)

GateKeeper 3

With that last one, since we have a lot of external functions to call, let’s write some Yul functions. You might have already seen on Telephone level that I already experimented with functions in the tests (check in test/foundry/4_Telephone.t.sol).

We need to make a few calls to gatekeeper contract: construct0r(), createTrick(), getAllowance(uint256) and enter()

We can easily write a function that just hashes the function signature for us and stores the selector. But, as you know, you need the length of the function signature. So let’s first write a function to get a string’s length

function getStrLen(_str) -> _length {
    for {
        let i := 0
    } lt(i, 0x20) {
        i := add(i, 1)
    } {
        if iszero(byte(i, _str)) {
            break
        }
        _length := add(_length, 1)
    }
}

Easy! We just pass a string as input, it loops over it as long as there is a char. If it finds a 0 it means we’re at the end of the string, so we return the length. Be careful: it only works as long as the string is less that 32 bytes, but it’s all good for us here since all our function signatures are less that 32 characters.

Next we can hash that string and store the result in memory

function hashSelector(_sig) {
    mstore(0, _sig)
    mstore(0, keccak256(0, getStrLen(_sig)))
}

Again, pretty simple. Finally we can just make our call:

function callExternal(_address, _sig, _param) {
    hashSelector(_sig)
    let calldataLen := 4

    if iszero(iszero(_param)) {
        mstore(4, _param)
        calldataLen := 0x24
    }

    let _success := call(gas(), _address, 0, 0, calldataLen, 0, 0)
    if iszero(_success) {
        revert(0, 0)
    }
}

Since getAllowance takes a parameter, we added an if statement to store that parameter and increase the size of the calldata that will be sent.

🔥 By the way, funny thing about that level. While solving it I discovered a small bug in Foundry for which I opened an issue, and finally decided to solve it myself and submit a PR. You can read more about it in my tweet and the related article on dev.to

And… WE ARE DONE !!! 😍

Conclusion

That’s all! I hope you had a good time solving the Ethernaut challenges, and that you enjoyed this little walkthrough and learned a lot about assembly!

Again, if you have any issues understanding, or if I made a mistake, you can contact me on Twitter: 0xteddav ❤️

Foundry: open source contribution

teddav — Thu, 02 Mar 2023 21:54:22 +0000

Contributing to open source projects can be a bit scary sometimes 👻 But it’s usually not that hard!

I just made my first (really small) contribution to Foundry (a toolkit to help develop smart contracts for Ethereum) today, and I really enjoyed it! 😍

While tackling the issue I took some notes, so if you’re thinking about contributing, I’m going to walk you through what I did and hopefully you’ll see that it’s pretty easy. Obviously the bug I fixed was really simple but it helped me get into the code and I’m ready to take on some more challenging ones 💪

It all started with this issue: https://github.com/foundry-rs/foundry/issues/4434

There was a bug in my forge script… I didn’t have time to look into it that day, so I left the issue opened for a few days, and today I finally took the time to do it. It took me about 3 hours from the moment I cloned the repo to the moment I opened the PR.

Setup

Foundry repo

First thing I did after cloning the repo was heading to the dev doc for help.

Since my PR was specifically related to forge script I thought I would only install forge locally with cargo build -p ./forge --profile local.

And I ran the tests: cargo test -p ./forge --profile local

I didn’t dig into it, but it seems like adding the local profile flag makes the build take longer, so in the end I just went with cargo build and built the entire project.

I now have the forge binary in foundry/target/debug/forge

And then I ran this command so that it would rebuild automatically when i make a change

cargo watch -x "build"

On every change, the build takes about 15-20 seconds on my Macbook Pro M1

Reproduce the error

I then created another directory where I setup my project for testing with the problematic script and I linked the newly built forge inside this repo with

$ ln -s ../foundry/target/debug/forge ./myforge

The repo looks like this

|-- cache
|-- foundry.toml
|-- lib
|-- myforge -> ../foundry/target/debug/forge
|-- myscript.s.sol
`-- out

Here is myscript.s.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.18;

// import "forge-std/Script.sol";
import { console, Script } from "forge-std/Script.sol";

contract MyScript is Script {
    function run() public {
        uint256 pk = 0xac0974bec39a17e36ba4a6b4d238ff944bacb478cbed5efcae784d7bf4f2ff80;
        vm.startBroadcast(pk);
        console.log("broadcaster    ", vm.addr(pk));
        console.log("script         ", address(this));
        console.log("origin         ", tx.origin);

        ContractA contractA = new ContractA();
        ContractB contractB = new ContractB();
        ContractC contractC1 = new ContractC();

        console.log("contractA      ", address(contractA));
        console.log("contractB      ", address(contractB));
        console.log("contractC1     ", address(contractC1));
        console.log("");

        contractA.test(address(contractB));
        contractB.method();
        contractC1.method();

        console.log("\n origin (end)   ", tx.origin);
        vm.stopBroadcast();
    }
}

contract ContractA {
    function test(address _contractB) public {
        ContractB contractB = ContractB(_contractB);
        ContractC contractC2 = new ContractC();

        console.log("A (start)  ", tx.origin);
        console.log("A (start) sender       ", msg.sender);
        contractB.method();
        console.log("A (after1) ", tx.origin);
        console.log("A (after1) sender      ", msg.sender);
        contractC2.method();
        console.log("A (after2) ", tx.origin);
        console.log("A (after2) sender      ", msg.sender);
    }
}

contract ContractB {
    function method() public {
        console.log("B          ", tx.origin);
        console.log("B sender               ", msg.sender);
    }
}

contract ContractC {
    function method() public {
        console.log("C          ", tx.origin);
        console.log("C sender               ", msg.sender);
    }
}

I can then run this command to reproduce my issue

$ ./myforge script ./myscript.s.sol --tc MyScript

The Foundry code

After looking at the code, trying to understand the architecture of the repo, and reading the dev doc I understood that I need to look into evm/src/executor/inspector/cheatcodes. So I started by adding some logs to understand what was going on.

I added logs in call, call_end, create and create_end

These are some examples of what it looked like

In evm/src/executor/inspector/cheatcodes/mod.rs on line 450

fn call(
        &mut self,
        data: &mut EVMData<'_, DB>,
        call: &mut CallInputs,
        is_static: bool,
    ) -> (Return, Gas, Bytes) {
            ...

            if let Some(broadcast) = &self.broadcast {
              println!("call() \n{broadcast:#?}");
              println!("contract: {}\ncontext: {:#?}", call.contract, call.context);
              println!("env before: {:#?}", data.env.tx);
              println!("\n");

                ...

And on line 730

fn create_end(
        &mut self,
        data: &mut EVMData<'_, DB>,
        call: &CreateInputs,
        status: Return,
        address: Option<Address>,
        remaining_gas: Gas,
        retdata: Bytes,
    ) -> (Return, Option<Address>, Gas, Bytes) {
            ...

        // Clean up broadcasts
        if let Some(broadcast) = &self.broadcast {
            println!("create_end() \n{broadcast:#?}");
            println!("address: {address:?}");
            println!("caller {:#?}", call.caller);
            println!("env before: {:#?}", data.env.tx);
            println!("depth: {}", data.journaled_state.depth());

            data.env.tx.caller = broadcast.original_origin;

            println!("/create_end()\n");

I quickly noticed that there was an issue with call_end and create_end which are the functions being called after a contract call and after a contract creation: it would reset the data.env.tx.caller which is the tx.origin in the Solidity context.

So the fix was pretty easy. Change

data.env.tx.caller = broadcast.original_origin;

if data.journaled_state.depth() == broadcast.depth {
    data.env.tx.caller = broadcast.original_origin;
}

This makes sure that tx.origin will be reset only when the last call is popped from the call stack and the execution returns to the run() function of the Script.

And… that’s it! We’re done 🎉

Integration tests

Now let’s add some tests.

After testing on my local setup by running forge script manually, it was time to add a proper integration test.

Tests are located in cli/tests/it/script.rs

To add a test, we use the forgetest_async! macro. I cleaned the Script that I was using and added some require statements and copied it inside my integration test.

I just need 1 line to make sure my script ran correctly:

assert!(cmd.stdout_lossy().contains("Script ran successfully."));

stdout_lossy() uses output() which, as the comment above says: “If the command failed, then this panics.”
So the script will fail if the Script fails, or if the output doesn’t contain “Script ran successfully.”

Run the test with

$ cargo test assert_tx_origin_is_not_overritten -- --show-output

or, if I want it to rebuild automatically everytime I make a change

$ cargo watch -x "test assert_tx_origin_is_not_overritten -- --show-output"

assert_tx_origin_is_not_overritten is the name I chose for the test I wrote. You can see it on the PR.

Let’s merge

Before pushing, make sure your code is formatted correctly and doesn’t have warnings.

$ cargo +nightly fmt -- --check
$ cargo +nightly clippy --all --all-features -- -D warnings

You can see the commands in the Contributing guidelines

We now need to open a PR and wait for someone to review 😊
Here it is: https://github.com/foundry-rs/foundry/pull/4469

Next time you have an issue with an open source project, maybe try to contribute 😁
If you have any question, or if I made a mistake somewhere: message me on Twitter 0xteddav

Playing with Yul (Assembly)

teddav — Wed, 22 Feb 2023 10:16:49 +0000

Assembly has been really hyped lately and all the cool kids seem to have started learning it. So I decided to do the same and learn what Yul is and how I can write my contracts with it. I started learning a few weeks ago and today I’m going to show you the basics so you can start enjoying it.

This tutorial is a bit advanced and doesn’t start from the beginning. If you want a real intro, you can check out the amazing series by @noxx3xxon EVM Deep Dives: The Path to Shadowy Super Coder where everything is really well explained. Or this great tutorial by @JeanCavallera.

What is Assembly/Yul

I’m not going to go into too much details, but basically assembly (or assembler) is a low-level language, really close to what your computer can understand. It’s a sequence of instructions for your computer to execute (here: the EVM).

Yul is just the name of the (almost) assembly for the EVM. I say “almost” because it’s a bit easier to write than pure assembly and it has the concept of variables, functions, for-loops, if statements, … whereas pure assembly doesn’t. So Yul makes our lives a bit easier 😊

You can use Yul when you need to have more control over what your code is doing. You can do anything in Yul since you control exactly what the EVM is going to execute, while Solidity is more restrictive. And most of the time Yul is used for gas optimizations.

Writing an entire contract in assembly (Yul) wouldn’t make sense usually, but that’s what we are going to do here so that you can understand better how it works and how the EVM works.

The base contract

As I already said, I’ll try to explain as much as possible, but I will not go over the very basics. So if you want to understand this tutorial, you’ll need a good understanding of Solidity and the EVM.

Let’s begin! We’ll rewrite this (really unsafe and stupid 😄) “lottery” contract to assembly. No access control, and the functions are a bit dumb, but it will be easier to write/understand when written in assembly 😊

contract AngleExplainsBase {
    uint private secretNumber;
    mapping(address =>  uint) public guesses;

    bytes32 public secretWord;

    // obviously this doesn't make sense
    // but it will be fun to write it in assembly :D
    function getSecretNumber() external view returns(uint) {
        return secretNumber;
    }

    // this should only be set by an admin
    // no access control because we want to keep it simple in assembly
    function setSecretNumber(uint number) external {
        secretNumber = number;
    }

    // a user can add a guess
    function addGuess(uint _guess) external {
        guesses[msg.sender] = _guess;
    }

    // yes i know... it doesn't make sense because you can change guesses for any user
    // it's just to teach you how to parse arrays in assembly
    function addMultipleGuesses(address[] memory _users, uint[] memory _guesses) external {
        for (uint i = 0; i < _users.length; i++) {
            guesses[_users[i]] = _guesses[i];
        }
    }

    // this is useless since the `secretWord` is not used anywhere
    // but this will teach us how to hash a string in assembly. Really cool! :)
    function hashSecretWord(string memory _str) external {
        secretWord = keccak256(abi.encodePacked(_str));
    }
}

We have a secretNumber that is private and we have a getter for that secret number getSecretNumber. Yes, it doesn't make, but if you're reading this, you should know that nothing is private on the blockchain anyway, so it doesn't really matter if we add a getter. It will just be fun to write it to assembly. Then, obviously, we have a setter setSecretNumber.

The user can add 1 or multiple guess(es) addGuess / addMultipleGuesses.

Then we have an extra function hashSecretWord. Let's imagine, we could use it if we decide to switch from a secret number to a secret string. Here it will help us understand more about how strings are handled in memory and we'll learn how to hash something in assembly (so cool!).

Get/Set our secret number

Throughout the code you’ll see a lot 0x20 or multiples of it (0x40, 0x60, 0x80, 0xa0, ...). This is the hexadecimal representation of 32 because the EVM uses 32 bytes memory slots (words). So values are always encoded in 32 bytes. (yes, you should know how to count in hexadecimal).

Let’s start with getSecretNumber. We will need SLOAD, MLOAD, MSTORE and RETURN opcodes for this function. Use the great https://www.evm.codes to learn more about EVM opcodes.

SLOAD just retrieves a value from storage. So we use SLOAD to get the value of our secret number. Then, in an ideal world, we should be done and just be able to return that number. But the EVM is a bit more complex than that and only returns values that are stored in memory. Solidity makes it easier for us and allows us to just return a value, and we don’t care what happens under the hood, but remember that Yul is more lower level, so we need to do the hard work.

First we’ll store that value to memory with MSTORE, and then we can return it.

Free memory pointer

We’ll use the “free memory pointer”, which is stored at 0x40 in memory.

mload(0x40) gives us the address in memory where we are allowed to write (in order not to overwrite anything). The memory before that address is already used, so if we overwrite it we might mess up our entire transaction (or even contract 😮 if something in that memory was meant to be written to storage for example).

We store our number there (MSTORE). And then we return it by specifying the address in memory, and the size that should be returned

function getSecretNumber() external view returns(uint) {
        assembly {
            // We get the value for secretNumber which is at slot 0
            // in Yul, you also have access to the slot number of a variable through `.slot`
                        // https://docs.soliditylang.org/en/latest/assembly.html#access-to-external-variables-functions-and-libraries
            // so we could also just write `sload(secretNumber.slot)`
            // SLOAD https://www.evm.codes/#54
            let _secretNumber := sload(0)

            // then we get the "free memory pointer"
            // that means we get the address in the memory where we can write to
            // we use the MLOAD opcode for that: https://www.evm.codes/#51
            // We get the value stored at 0x40 (64)
            // 0x40 is just a constant decided in the EVM where the address of the free memory is stored
            // see here: https://docs.soliditylang.org/en/latest/assembly.html#memory-management
            let ptr := mload(0x40)

            // we write our number at that address
            // to do that, we use the MSTORE opcode: https://www.evm.codes/#52
            // It takes 2 parameters: the address in memory where to store our value, and the value to store
            mstore(ptr, _secretNumber)

            // then we RETURN the value: https://www.evm.codes/#f3
            // we specify the address where the value is stored: `ptr`
            // and the size of the parameter returned: 32 bytes (remember values are always stored on 32 bytes)
            return(ptr, 0x20)
        }
    }

I just wanted to complicate things a bit for you by using the free memory pointer. But we could write our function in a shorter way:

// instead of using the free memory pointer, we could also store the value at `0`
// because the first 2 slots in memory are used as "scratch space"
// https://docs.soliditylang.org/en/latest/internals/layout_in_memory.html#layout-in-memory
// this means they are used to store temporary values, such as return values
// we would have had:
assembly {
    let _secretNumber := sload(0)
    mstore(0, _secretNumber)
    return(0, 0x20)
}

Why? You have to know that the EVM reserves the first 4 slots in memory for special purposes. Here are the slots. I added a 5th one which represents the first writable slot.

offset	value
0x00 (0)	scratch space, can be used for storing anything
0x20 (32)	scratch space, can be used for storing anything
0x40 (64)	free memory pointer. Initial value is 0x80 (where starts the memory we can write to)
0x60 (96)	zero slot, should never be touched
0x80 (128)	that’s where the memory starts

As you can see, we can use the first 2 slots to write anything. But we have to keep in mind that they can be also be overwritten at anytime.

Next we’ll write setSecretNumber which is a bit easier. We just need to retrieve the slot number where the value is stored, and use SSTORE to store our new value.

Here we’ll just use the special .slot helper that Yul offers us. It makes it easier, so we don't have to manually calculate the slot number 😄

function setSecretNumber(uint _number) external {
        assembly {
            // We get the slot number for `secretNumber`
            let slot := secretNumber.slot

            // We use SSTORE to store the new value
            // https://www.evm.codes/#51
            sstore(slot, _number)
        }
    }

Add guesses

We now need to allow a user to add a guess. But guesses is a mapping, so it complicates things. We first need to compute the value of the storage slot where the guess is going to be stored, and then we can store it with SSTORE

How mappings work

To write a value to a mapping: we concatenate the key and the slot number of the mapping, and hash that (for more details: https://docs.soliditylang.org/en/latest/internals/layout_in_storage.html#mappings-and-dynamic-arrays). Here our mapping guesses is at storage slot 1.

So in Solidity we would get the storage slot by doing keccak256(abi.encode(msg.sender, 1))

To hash something in Yul, we have to store it to memory first. It’s not possible otherwise, keccak256() only looks in memory.

Here are the steps to get our slot number

get the msg.sender address
get the slot number of the mapping
store both of them in memory (in order and next to each other)
compute the hash

function addGuess(uint _guess) external {
        assembly {
            // first we compute the slot where we will store the value
            // https://docs.soliditylang.org/en/latest/internals/layout_in_storage.html#mappings-and-dynamic-arrays
            // we have: keccak256(abi.encode(_user, 1)) where 1 is the slot number for `guesses`
            let ptr := mload(0x40)

            // we store the address of msg.sender at `ptr` address
                        // CALLER opcode: https://www.evm.codes/#33
            mstore(ptr, caller())

            // then right after that, we store the slot number for `guesses`
            mstore(add(ptr, 0x20), guesses.slot)

            // the 2 previous MSTORE are equivalent to abi.encode(msg.sender, 1)

            // then we just compute the hash of the msg.Sender and guesses.slot
            // they are currently stored at `ptr` and use 2 slots (2x 32bytes -> 0x40)
            let slot := keccak256(ptr, 0x40)

            // we now only need to store the value at that slot
            sstore(slot, _guess)
        }
    }

To get the address of the msg.sender in assembly we use the CALLER opcode.

We use the free memory pointer to know where to write our values. Then we store the msg.sender (caller()).

add(ptr, 0x20) gives us the memory address 32 bytes after, which means "the next memory slot". That's where we'll store our second value.

Operations in Assembly

In Assembly we can't do simple operations (+ - * /), they just don’t exist ☹️

We need to use specific opcodes for that. Here we use ADD to add 32 bytes to the address of ptr

This is equivalent to: ptr = ptr + 32

Then we hash all of that. The second argument of keccak256 is the size of the data to be hashed. Here it's 2 memory slots, so 2*32=64 (0x40 in hexadecimal)

Hash some strings

We are going to take a quick break from our main functions and focus and the most useless function (but most fun) of our Solidity contract: hashSecretWord. We'll even go as far as writing it 2 times with 2 different techniques to get the _str parameter’s value. We’ll use the CALLDATA opcodes, to help you understand how calldata works and how to manipulate the calldata (you're welcome!).

Non-value types

First, a little lesson about non-value types: one of the complicated parts I noticed when first learning Yul was when dealing with non-value types (array, mapping, bytes or string). But they are actually not that hard to understand, you just have to understand how the EVM deals with them and stores them in memory.

It goes like this: those values are usually stored in 2 parts: first their length, and then the actual value. Imagine you pass the string “angle” as a parameter. It will be stored like “5angle” so the EVM knows it’s supposed to read the next 5 characters.

It will actually look a bit different, since the EVM works in 32 bytes memory slots, it will look more like: 0000000000000000000000000000000000000000000000000000000000000005616e676c65000000000000000000000000000000000000000000000000000000

notice the 5 and then the word angle written in hexadecimal (616e676c65)

Ok, back to our code.

// computes the keccak256 hash of a string and stores it in a state variable
function hashSecretWord1(string memory _str) external view returns(bytes32) {
    assembly {
        // in assembly `_str` is just a pointer to the string
        // it represents the address in memory where the data for our string starts
        // at `_str` we have the length of the string
        // at `_str` + 32 -> we have the string itself

        // here we get the size of the string
        let strSize := mload(_str)

        // here we add 32 to that address, so that we have the address of the string itself
        let strAddr := add(_str, 32)

        // we then pass the address of the string, and its size. This will hash our string
        let hash := keccak256(strAddr, strSize)

        // we store the hash value at slot 0 in memory
        // just like we explained before, this is used as temporary storage (scratch space)
        // no need to get the free memory pointer, it is faster (and cheaper) to use `0`
        mstore(0, hash)

        // we return what is stored at slot 0 (our hash) and the length of the hash (32)
        return (0, 32)
    }
}

Here _str is a pointer to the slot in memory where the length of the string is stored, and then (at the next slot) the string itself starts. So we just need to retrieve that size, then we can just hash the string directly since it's already in memory and we know its address. Easy!

To make it even easier, let me show you what the memory looks like at the start of our function. Let’s say we passed the string “stablecoin”

offset	value
0x00 (0)	…
0x20 (32)	…
0x40 (64)	0xc0
0x60 (96)	…
0x80 (128)	10
0xa0 (160)	stablecoin
0xc0 (192)

The length of our string is written at 0x80, and our word is written at 0xa0. The free memory pointer points to the next available memory space: 0xc0.

And _str is equal to 0x80 (where our string is stored).

But you may ask: How was it stored in memory in the first place? There was no MSTORE to write to memory, so why isn’t the memory empty?

The EVM (magically) placed it there because we asked it to do so. When? Here: string memory _str.

By specifying memory in the parameter, we asked the EVM to prepare our memory and place our parameter there. That's why using calldata is cheaper, there is no writing to memory 😉

Second string hashing technique

// this is the same as `hashSecretWord1` but using a different technique
// here we use specific opcodes to manipulate calldata instead of using the parameters of the function
// instead of returning the hash, we'll assign it to storage variable `secretWord`
function hashSecretWord2(string calldata) external {
    assembly {
        // the calldata represents the entire data passed to a contract when calling a function
        // the first 4 bytes always represent the signature of the function, and the rest are the parameters
        // here we can skip the signature because we are already in the function, so the signature obviously represent the current function
        // we can use CALLDATALOAD to load 32 bytes from the calldata.
        // we use calldataload(4) to skip the signature bytes. This will therefore load the 1st parameter
        // when using non-value types (array, mapping, bytes, string) the first parameter is going to be the offset where the parameter starts
        // at that offset, we'll find the length of the parameter, and then the value

        // this is the offset in `calldata` where our string starts
        // here we use calldataload(4) -> loads the offset where the string starts
        // -> we add 4 to that offset to take into account the signature bytes
        // https://www.evm.codes/#35
        let strOffset := add(4, calldataload(4))

        // we use calldataload() again with the offset we just computed, this gives us the length of the string (the value stored at the offset)
        let strSize := calldataload(strOffset)

        // we load the free memory pointer
        let ptr := mload(0x40)

        // we copy the value of our string into that free memory
        // CALLDATACOPY https://www.evm.codes/#37
        // the string starts at the next memory slot, so we add 0x20 to it
        calldatacopy(ptr, add(strOffset, 0x20), strSize)

        // then we compute the hash of that string
        // remember, the string is now stored at `ptr`
        let hash := keccak256(ptr, strSize)

        // and we store it to storage
        sstore(secretWord.slot, hash)
    }
}

We don’t even need a name for our parameter since we’re not going to use it explicitly. And notice that this time we don’t need it in “memory", so we specify “calldata” so that it won’t be copied.

The CALLDATALOAD opcode loads 32 bytes from the calldata starting at the offset specified. We use it here to load values 1 by 1.

More non-value types

I need to add something to the previous explanation about non-value types. The calldata is just a bit more complicated than what I previously told you. Focus! This is not easy.

Let’s give an example of what the memory would look like for a function with 3 parameters:

function myToken(string memory name, uint randomValue, address[] memory _addresses)

we pass the following (pseudo random) parameters 🙂

“angle”, 7, ["0x31429d1856aD1377A8A0079410B297e1a9e214c2", "0x1a7e4e63778B4f12a199C062f3eFdD288afCBce8"]

What the calldata looks like 050eed260000000000000000000000000000000000000000000000000000000000000060000000000000000000000000000000000000000000000000000000000000000700000000000000000000000000000000000000000000000000000000000000a00000000000000000000000000000000000000000000000000000000000000005616e676c65000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000000000000031429d1856ad1377a8a0079410b297e1a9e214c20000000000000000000000001a7e4e63778b4f12a199c062f3efdd288afcbce8

Let’s split that in 32 bytes words to have a better view.

First we have the function signature: 050eed26, and then the parameters:

offset (from 1st param)	offset (calldata)	value
0x00 (0)	0x04 (4)	0000000000000000000000000000000000000000000000000000000000000060
0x20 (32)	0x24 (36)	0000000000000000000000000000000000000000000000000000000000000007
0x40 (64)	0x44 (68)	00000000000000000000000000000000000000000000000000000000000000a0
0x60 (96)	0x64 (100)	0000000000000000000000000000000000000000000000000000000000000005
0x80 (128)	0x84 (132)	616e676c65000000000000000000000000000000000000000000000000000000
0xa0 (160)	0xa4 (164)	0000000000000000000000000000000000000000000000000000000000000002
0xc0 (192)	0xc4 (196)	00000000000000000000000031429d1856ad1377a8a0079410b297e1a9e214c2
0xe0 (224)	0xe4 (228)	0000000000000000000000001a7e4e63778b4f12a199c062f3efdd288afcbce8

I used https://abi.hashex.org/ to easily encode the calldata.

We have our 3 function parameters, in order, but encoded in a special way.

I started the numbering at 0, but we’ll have to remember to add 4 to the offset to account for function signature.

For value types, the value is the value of the parameter. See at 0x20, we have 7 which is the value we passed for randomValue. But for non-value types, we actually get the offset where the data starts. See at 0x00 we have 0x60. If we check at 0x60, we have 5: the length of the string, and right after, at 0x80 we have the string "angle".

The last parameter starts at 0x40, again this is the offset. So let’s check at 0xa0, we have 2 (the length of our array), and then the 2 values at 0xc0 and 0xe0.

Nice! We finally know how the EVM understands all the “weird” types we can pass to it! 🔥

Back to our calldata then.

Let’s just explain this line better let strOffset := add(4, calldataload(4))

We use CALLDATALOAD to get the first parameter (at offset 4, remember the function signature…).

This returns the offset where the length of the string is stored. For example, if we take the previous example, we would get 0x60 (the value stored at 0x04 in calldata). If we add 4 to it, we get 0x64, which is the address where we get our string in the calldata.

Then we use CALLDATACOPY to copy the string to memory. We hash it and store it. And we’re done 😎

Yes this was a quick explanation for a complicated code, but with everything I explained to you until now, you should be able to understand it. If not, hit me up on Twitter @0xteddav and i’ll help you.

addMultipleGuesses: use all our Yul knowledge

Lastly, let’s reuse everything we just learned to loop through 2 arrays in assembly and store values to a mapping in storage! wow 🤯

function addMultipleGuesses(address[] memory _users, uint[] memory _guesses) external {
        assembly {
            // remember: `_users` is the address in memory where the parameter starts
            // This is where the size of the array is stored. And then 32 bytes after, we have the values of the array
            // so here we load what's at address `_users` -> which is the size of the array `_users`
            let usersSize := mload(_users)

            // same for `_guesses`
            let guessesSize := mload(_guesses)

            // we check that both arrays are the same size
            // check EQ, ISZERO and REVERT opcodes on https://www.evm.codes/
            if iszero(eq(usersSize, guessesSize)) { revert(0, 0) }

            // we use a for-loop to loop through the items
            for { let i := 0 } lt(i, usersSize) { i := add(i, 1) } {
                // to get the ith value from the array we multiply i by 32 (0x20) and add it to `_users`
                // we always have to add 1 to i first, because remember that `_users` is the size of the array, the values start 32 bytes after
                // we could also do it this way (maybe it makes more sense):
                // let userAddress := mload(add(add(_users, 0x20), mul(0x20, i)))
                let userAddress := mload(add(_users, mul(0x20, add(i, 1))))
                let userBalance := mload(add(_guesses, mul(0x20, add(i, 1))))

                // we use the 0 memory slot as temporary storage to compute our hash
                // we store the address there
                mstore(0, userAddress)
                // then the slot number for `guesses`
                mstore(0x20, guesses.slot)
                // we compute the storage slot number
                let slot := keccak256(0, 0x40)
                // and store our value to it
                sstore(slot, userBalance)
            }
        }
    }

I hope the comments are clear enough. I’ll just add a few explanations.

To check that both arrays are the same size, we use ISZERO and EQ opcodes. eq() takes 2 numbers as parameters and returns 1 if they are equal, 0 if not equal. Then we simply use iszero() to check the returned value from eq(). If they are not equal, we revert.

iszero(eq(a, b)) is equivalent to a != b in Solidity

Finally the for-loop: the line to get the value from the parameter is a bit complicated. Let’s explain this one:

let userAddress := mload(add(_users, mul(0x20, add(i, 1))))

So remember that our users’ addresses (_users) are written to memory by the EVM.

The variable _users is the address in memory where the length of the array is stored. So to get to the first value of the array we have to add 32 to it.

Since we are in a for-loop, every iteration we need to add 32.

So to get the current value we have 32*i + 32 → 32 * (i + 1) → which in assembly is mul(0x20, add(i, 1))

To make it easier (and more gas efficient), we could have started the loop at i=1 to avoid all the add(i, 1).

You made it!

So that’s it, we are done! We wrote an entire contract in assembly, and even did a bit of extra work (just for fun!).

You can find the entire code used in that thread in this Github Gist. So that if you’re too lazy to re-write it, you can just copy it.

If you have any question, hit me up on Twitter @0xteddav.

Let me know what you want me to write about next. Should I go deeper? Or write on another subject?