DEV Community: Akira

Creating a Toy Solidity compiler and running it in a Toy EVM

Akira — Wed, 20 Nov 2024 11:08:40 +0000

I wanted to try making my own compiler and runtime environment, so I gave it a shot. It doesn’t cover all the syntax or opcodes yet, but I’m satisfied as long as it can run basic functionality. I’ll make some improvements if I feel like it.

https://github.com/akira-19/toythereum

Demo

contract TestContract {
    uint256 a = 1 + 2 * 3 + 4;

    function increment() returns (uint256) {
        a = a + 1;
        return a;
    }

    function compare(uint256 b) returns (bool) {
        return a < b;
    }
}

When you compile the code, you can get the following bytecode.

7f00000000000000000000000000000000000000000000000000000000000000807f0000000000000000000000000000000000000000000000000000000000000040527f00000000000000000000000000000000000000000000000000000000000000047f00000000000000000000000000000000000000000000000000000000000000037f00000000000000000000000000000000000000000000000000000000000000027f00000000000000000000000000000000000000000000000000000000000000017f000000000000000000000000000000000000000000000000000000000000000b7f0000000000000000000000000000000000000000000000000000000000000000557f000000000000000000000000000000000000000000000000000000000000032f807f00000000000000000000000000000000000000000000000000000000000001515f395ff37f00000000000000000000000000000000000000000000000000000000000000807f0000000000000000000000000000000000000000000000000000000000000040527f00000000000000000000000000000000000000000000000000000000000000e07f0000000000000000000000000000000000000000000000000000000000000000351c7f00000000000000000000000000000000000000000000000000000000d09de08a147f0000000000000000000000000000000000000000000000000000000000000196577f00000000000000000000000000000000000000000000000000000000000000e07f0000000000000000000000000000000000000000000000000000000000000000351c7f00000000000000000000000000000000000000000000000000000000c4b8c257147f0000000000000000000000000000000000000000000000000000000000000283577f00000000000000000000000000000000000000000000000000000000000000007f0000000000000000000000000000000000000000000000000000000000000000fd5b7f00000000000000000000000000000000000000000000000000000000000000017f000000000000000000000000000000000000000000000000000000000000000054017f0000000000000000000000000000000000000000000000000000000000000000557f0000000000000000000000000000000000000000000000000000000000000000547f0000000000000000000000000000000000000000000000000000000000000080527f00000000000000000000000000000000000000000000000000000000000000207f0000000000000000000000000000000000000000000000000000000000000080f35b7f0000000000000000000000000000000000000000000000000000000000000004357f000000000000000000000000000000000000000000000000000000000000000054107f0000000000000000000000000000000000000000000000000000000000000080527f00000000000000000000000000000000000000000000000000000000000000207f0000000000000000000000000000000000000000000000000000000000000080f3

demo is here. (I don't know why, but I can embed gif file on the article)
https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8l5vmjmwwkp2iq85s7gd.gif

In the demo above, the following actions are performed:

Run the EVM.
Deploy the compiled bytecode (returns the contract code).
Execute compare with argument b as 12 (the initial value of a is 11, so it returns true, which is 1).
Execute increment (returns 12 in hexadecimal).
Execute compare again with argument b as 12 (since 12 == 12, it returns false, which is 0).

BTW, if you make a mistake in the return type as follows:

contract TestContract {
    uint256 a = 1 + 2 * 3 + 4;

    function compare(uint256 b) returns (uint256) {
        return a < b; // Compilation error occurs here because the return type is mismatched
    }
}

The error message looks like:

EVM

The EVM is a stack-based virtual machine.

Memory

Pre-allocated Memory

While inspecting compiled bytecode, I noticed that mstore often takes 0x40, so I looked into it.

Depending on the version, this might differ, but here is the reference I checked:

https://docs.soliditylang.org/en/v0.8.27/internals/layout_in_memory.html

The first 128 bytes of memory have specific purposes:

0x00 - 0x3f (64 bytes): Scratch space for hashing methods.
0x40 - 0x5f (32 bytes): Current memory size (referred to as the free memory pointer).
0x60 - 0x7f (32 bytes): Zero slot.
The scratch space is reserved for temporary use in hashing methods. If the allocated space is insufficient, it will use free memory.
The free memory pointer specifies the next available memory address. This means that the first mstore operation must store data at 0x80 since the first 128 bytes (up to 0x7f) are already reserved. The typical first instruction in a contract is to mstore 0x80 at address 0x40.
The zero slot is used as the default value for dynamic arrays. It remains filled with 0x00 and can be directly copied for initialization purposes.

Memory Allocation

Memory is allocated in 32-byte chunks.

Since the first 128 bytes are pre-allocated, the first writable memory address is 0x80.

Memory expands dynamically when needed. For example, if a 30-byte string is replaced with a 40-byte string, memory will automatically expand from 0x80-0x9f to 0x80-0xbf.

However, memory expansion incurs additional gas costs, so it should be managed carefully. Also, memory does not get freed automatically, even when it is no longer in use.

https://learnevm.com/chapters/evm/memory#memory-expansion

If the next memory space is already occupied, new memory is allocated at the end of the current memory.

https://medium.com/@PaulElisha1/layout-of-storage-and-memory-management-in-low-level-solidity-feb41c3de140

Storage

Slots

Unlike memory, storage is pre-allocated with 2^256-1 slots, each 32 bytes in size.

For fixed-size data types of 32 bytes or less, data is stored sequentially. For dynamically sized types, the following rules apply:

The slot stores the length of the data.
The actual data is stored in the slot calculated by keccak256(slot).

For example, if slot 3 is used:

Slot (3) stores the data length.
The actual data is stored at keccak256(3), e.g., 55b2c6.... If the data exceeds 32 bytes, subsequent slots after 55b2c6... are used. Arrays follow a similar pattern.

My implementation works only for strings of 32 bytes or less at the moment.

https://docs.alchemy.com/docs/smart-contract-storage-layout

For multidimensional arrays or mappings, slot numbers and key values are factored into the calculations.

https://docs.soliditylang.org/en/latest/internals/layout_in_storage.html

Currently, the implementation maps slots and values using Rust's HashMap, but in practice, a Merkle Patricia Trie is used.

Function Definitions

Functions are identified using a function selector, derived by taking the first 4 bytes of the keccak256 hash of the function signature.

https://docs.soliditylang.org/en/latest/abi-spec.html

For example, for a function like function mint(uint256),

keccak256(mint(uint256)) = 0xa0712d680358d64f694230b7cc0b277c73686bdf768385d55cd7c547d0ffd30e.

The function selector is 0xa0712d68.

When a transaction is sent, the first 4 bytes of the calldata contain the function selector. The contract compares this selector to the stored selector and jumps to the corresponding function if they match.

If you compile a simple contract in Remix and extract the opcodes for the function call, you will see something like this:

- CALLDATALOAD
- PUSH1 0xe0
- SHR
- DUP1
- PUSH4 0x6057361d
- EQ
- PUSH1 0x2a
- JUMPI

Explanation:

CALLDATALOAD, PUSH1 0xe0, and SHR: Extract the first 4 bytes of the calldata (the function selector).
PUSH4 0x6057361d, EQ: Compare the extracted function selector with the stored selector.
If they match, PUSH1 0x2a and JUMPI jump to the function (0x2a is the program counter in the bytecode).

Calldata

The first 4 bytes of the calldata represent the function selector. The arguments are stored in 32-byte chunks following the selector.

For simplicity, this assumes all arguments fit within 32 bytes, so the number of arguments multiplied by 32 bytes follows the function selector.

Solidity Compiler

Syntax

Unfortunately, there are no public or private keywords in my implementation at the moment.

In fact, there are no if statements or for loops either. Additionally, functions cannot call other functions within them.

Types

Not all types are supported at the moment. Currently, only string, uint256, and bool are available.

While string is defined, it only works if it is 256 bits or smaller.

Constant Folding

Constant folding is a process where constant expressions are precomputed at compile time instead of being evaluated at runtime on the EVM.

For example, in the statement uint256 a = 1 + 2;, instead of executing 1 + 2 on the EVM, the compiler calculates it during compilation and outputs uint256 a = 3;.

This is straightforward for simple cases, but it gets tricky when the expression includes unknown values, such as function arguments.

For instance, in uint256 a = 1 + arg + 2; (where arg is a function argument), the ideal approach would be to compute uint256 a = 3 + arg; at compile time and execute only 3 + arg on the EVM. However, due to complexity, if an unknown value is encountered, the entire expression is left for the EVM to calculate.

Deployment Code

In the EVM, there are two types of bytecode: deployment bytecode and deployed contract bytecode.

The deployed contract bytecode is included within the deployment bytecode and is eventually deployed using the codecopy opcode (technically, it is deployed at the point of RETURN).

When compiled with solc, the bytecode contains additional code before and after the contract code. In toythereum, the deployment process follows these steps:

Temporarily store all contract code without compiling functions until the entire contract code is scanned.
Compile non-function code (e.g., initializing storage variables).
Add deployment-specific instructions such as codecopy (use placeholders for contract code length as it is unknown at this stage).
Compile the functions (this becomes the contract code).
Calculate the length of the compiled functions and insert the length into the placeholders in the deployment instructions.

As a result, the final bytecode consists of two parts:

The first part handles initialization (e.g., storage setup) and deployment.
The second part contains the actual contract bytecode.

References

Why is a Hash Function Irreversible?

Akira — Sat, 16 Nov 2024 04:22:24 +0000

Introduction

Hash functions are commonly used for verifying data integrity and cryptographic purposes. In this article, I will implement the widely-used SHA-256 hash function and examine why it is irreversible (i.e., why the original value cannot be restored).

The conclusion is that the irreversibility of hash functions is achieved through information loss.

The Rust implementation of SHA-256 for this article is available here:

https://github.com/akira-19/algorithms_rust/tree/main/sha-256

The Flow of SHA-256

The irreversibility of SHA-256 can be understood by analyzing its flow. Let’s hash the string "msg" as an example.

First, convert the string msg into its character codes (hexadecimal representation).
Next, format the message into a 64-byte block. Add 0x80 just after the original message, and append the binary length of the original message to the last 8 bytes of the block. Since msg is 3 bytes, its binary length is 24 bits, represented as 0x18 in hexadecimal. Pad the gap between 0x80 and the message length with zeros.
Split the 64-byte block into 4-byte segments. For example, the first segment 6d 73 67 80 becomes 6d736780 (in decimal: 1836279680).

Calculate the value W, which includes irreversible processing. A part of sample Rust code snippet is as follows.

 fn calc_w(msg: [u32; 16]) -> [u32; 64] {
   let mut w = vec![0; 64];

   for i in 0..16 {
       w[i] = msg[i];
   }

   for i in 16..64 {
       w[i] = lower_sigma_1(w[i - 2])
           .wrapping_add(w[i - 7])
           .wrapping_add(lower_sigma_0(w[i - 15]))
           .wrapping_add(w[i - 16]);
   }

   w
 }

 fn lower_sigma_1(x: u32) -> u32 {
   rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)
 }

 fn rotr(x: u32, n: u32) -> u32 {
   (x >> n) | (x << (32 - n))
 }

 fn shr(x: u32, n: u32) -> u32 {
   x >> n
 }

The calc_w function calls the lower_sigma_1 function, which in turn calls rotr. Let’s visualize how this works.

As an example, let x = 31 and n = 3. In binary, 31 is 11111. Since x and n are unsigned 32-bit integers, x is represented as 000...000011111 (27 leading zeros).
The operation x >> n shifts x to the right by n bits, adding 000 to the left and removing the last 111.
Similarly, x << (32 - n) shifts x to the left by 32 - 3 = 29 bits. The first three bits become 111, followed by zeros.
Finally, the bitwise OR of steps 6 and 7 results in a value like 111000...0011.

The information loss occurs in the shr operation. In step 6, the bits shifted out to the right cannot be recovered.

Additionally, in lower_sigma_1, the operation rotr(x, 17) ^ rotr(x, 19) results in information loss. To simplify, this process involves XORing 10000 shifted right by 1 bit with 10000 shifted right by 2 bits, yielding 01000 ^ 00100 = 00000. This result could also originate from an original value of 00000, making the original value unrecoverable.

By repeating such operations, it becomes impossible to restore the original value.

Referrence

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

Creating Regular Expression

Akira — Wed, 13 Nov 2024 13:00:47 +0000

I created a toy regular expression engine to understand how regular expression works.

Process Flow

A regular expression represents a pattern for strings, such as /ab*(a|c)+/. However, this expression can be difficult to handle directly in a program. Therefore, the first step is to convert it into a format that is easier to work with programmatically.

This format is typically represented as an AST (Abstract Syntax Tree). An AST is a data structure that represents the structure of the regular expression in a tree format. By creating an AST, it becomes easier to analyze the regular expression and process it for pattern matching.

Next, we perform code generation based on the AST. Code generation is the process of creating instructions that a computer can execute. By analyzing the AST, we can generate the necessary commands and processing steps to create code that can actually handle the regular expression.

Finally, we evaluate the given string to see if it matches the regular expression using the generated code. The goal is to execute the generated code to determine whether the given string matches the regular expression pattern.

This approach allows effective handling of regular expressions, enabling pattern matching and searching within strings.

Parsing to AST

First, we parse the regular expression into an AST.
Consider a regular expression such as ab*(c|d) as an example.

AST for ab*(c|d)

          Concat
            |
     ---------------------------------
     |              |                 |
Literal('a')  Repeat0(Literal('b'))   or
                                      |
                                 -----------
                                |          |
                           Literal('c')  Literal('d')

Representing this tree structure as structs makes it easier to handle in a program.

enum RegexAst {
    Literal(char),
    Concat(Vec<RegexAst>),
    Or(Box<RegexAst>, Box<RegexAst>),
    Repeat0(Box<RegexAst>), // Repeat 0 or more times
    ...other symbols like + and ?
}

With such a struct definition, the AST for ab*(c|d) can be represented as follows:

Concat([
  Literal('a'), 
  Repeat0(Literal('b')), 
  Or(
    Concat([Literal('c')]), 
    Concat([Literal('d')])
  )
])

Code Generation

In code generation, we analyze the AST and generate code to process the regular expression. Specifically, we define a set of instructions to handle the regular expression, and based on this, we generate the code.

First, we define a register machine as the data structure to handle regular expressions. A register machine consists of a finite set of registers and a program counter (which indicates the current instruction to execute). Using this register machine, we execute the regular expression processing.

We define the commands to use. This register machine has four commands:

char: Matches a specific character. If the current character matches the specified character, it moves to the next command.
match: Checks for a match with the regular expression. If the specified pattern matches the current string, it moves to the next command.
jump: Jumps to a specified location, changing the execution point of the command.
split: Branches to two different commands, each with its own target command. This can allow processing of two branches.

By combining these commands, we can represent the processing of regular expressions. By analyzing the AST and generating commands for each node, we also generate control structures like loops and conditional branches as needed.

With just these four commands, we can evaluate a regular expression.
The sample regular expression (ab*(c|d)) can be represented with only these four commands, as shown below.

0001: Char(a)
0002: Split 0003, 0005
0003: Char(b)
0004: Jump(0002)
0005: Split 0006, 0008
0006: Char(c)
0007: Jump(0009)
0008: Char(d)
0009: Match

The numbers on the left are the PC (Program Counter).

Evaluation

This may be a bit challenging to understand, so let’s walk through the generated code step by step.

First, the Char(a) command is executed, checking if the current character is 'a'. If it doesn’t match, the regular expression does not match. If it matches, we increment the PC by one and jump to 0002.
If it matches, the Split 0003, 0005 command is executed, branching the program counter into two locations, 0003 and 0005. This represents the b* part of the expression, which can repeat 0 or more times. If 0005 is chosen, 0003 is skipped, so the 'b' character is not evaluated. However, if it jumps to 0003, it evaluates 'b'. If it matches, the PC is incremented to 0004, which instructs to jump back to 0002. This branches again into 0003 and 0005, and if 0003 is selected, 'b' is re-evaluated, allowing 'b' to match consecutively. Jumping to 0005 exits this branch, resulting in the b* evaluation for zero or more repetitions of 'b'.
Next, it branches into 0006 and 0008. This allows for a match of either 'c' or 'd'. At location 0006, the Char(c) command is executed, checking if the current character is 'c'. If it matches, it moves the PC to 0007, which jumps to 0009, ending the process. At location 0008, the Char(d) command is executed, checking if the current character is 'd'. Here too, the PC advances, and ultimately, the Match command confirms a match with the regular expression and the program ends.

Thus, this sequence of commands efficiently processes the pattern /ab*(c|d)/. Each command reflects the structure of the regular expression, with appropriate branching and repetition achieved through program counter control.

Evaluation is conducted using a loop.

For instance, to evaluate a string like char = xabd:

char[0] == x, so process at 0001 ends, moving to the next check.
char[1] == a, so 0001 passes, and the PC increments.
At 0002, branches to 0003 and 0005 are evaluated.
At 0003, 'b' matches, so we change the evaluated character to 'd' and increment the PC to 0004.

This process continues, evaluating one character at a time.

How to disconnect WebSocket from Chrome Developer tool

Akira — Wed, 13 Nov 2024 12:21:52 +0000

Sometimes, you may need to test how your application behaves when a WebSocket connection is disconnected. Here’s a step-by-step guide to disconnecting a WebSocket via the Chrome Console.

First, enter queryObjects(WebSocket) in the Chrome Console to retrieve the WebSocket object.

Next, right-click on the WebSocket object, select Store as global variable from the modal that appears.

This action will store the WebSocket object in a temporary variable, typically named temp1.

Finally, to close the WebSocket connection, use the command temp1.close(). This will disconnect the WebSocket, allowing you to observe your application’s response to the disconnection.