Statelessness series — Part2: ASE(Address Space Extension)

Chaisomsri

11 min readFeb 12, 2024

1. Introduction

2. Background of ASE 1: Adding address space ID for the introduction of state expiry

3. Background of ASE 2: Insufficient 20 bytes from a security perspective

4. Concept of ASE

5. Challenges Introduced by ASE

6. Solution: ASE with Translation Map

7. Conclusion

1. Introduction

ASE stands for Address Space Extension, a concept first introduced by Vitalik Buterin in March 2021 through a forum. As will be discussed later, the essence of ASE is to increase the address size from 20 bytes to 32 bytes. Vitalik cited three reasons for the need to expand the address space:

1. Adding an address space ID for the introduction of state expiry
2. Adding a shard ID for EVM-supported execution shards
3. The insufficiency of 20 bytes from a security perspective

Among these three reasons, the addition of a shard ID for EVM-supported execution shards was abandoned due to changes in plans, and currently, only the addition of an address space ID for the introduction of state expiry and the insufficiency of 20 bytes from a security perspective remain valid. Understanding the background behind the emergence of ASE can facilitate a better grasp of the concept of ASE, so before delving into the concept of ASE, we would like to first examine the two valid backgrounds for its emergence.

2. Background of ASE 1: Adding address space ID for the introduction of state expiry

State expiry is one of several measures aimed at reducing the burden of node operation by decreasing the size of the state. It involves deleting states that have not been accessed recently. To define what “recently” means, the concept of a period was introduced in state expiry. A new period begins every year (based on the current standard) with a new tree, and in state expiry, all periods except for the last and the current one are deleted, leaving only their roots.

There may be users who have not changed their wallet state since two periods ago. These users might want to transfer ETH that they own to another wallet. However, due to state expiry, the user’s state has been deleted. In this case, can the user not recover their ETH?

No, that’s not the case. Users can resurrect their state by paying a small fee and submitting a proof called a witness. A witness is a proof that a specific value did or did not exist at a certain location. If you want to know more about state expiry and witnesses, please check part 1 of this series (link).

However, depending on the opportunity cost between the amount of ETH owned and the cost of resurrection, users are faced with two choices. First, if the resurrection cost is higher than the amount of ETH owned, the user gives up their ETH and creates a new address. This way, they can minimize their losses. Second, if the amount of ETH owned is more than the resurrection cost, they pay the cost and resurrect their state.

Thus, with the introduction of state expiry and witnesses, it became possible to retrieve one’s state even after the states of past periods (except the last one) have been deleted. However, from the perspective of addresses, the creation and disappearance of numerous addresses can cause confusion. Therefore, Vitalik argues for adding information related to the period to the address space to prevent this confusion.

3. Background of ASE 2: Insufficient 20 bytes from a security perspective

To understand why the current address size of 20 bytes is not sufficient from a security perspective, it’s necessary first to grasp the concepts of collision and collision resistance in hash functions.

A collision means that two different messages have the same hash value. You can think of it as putting two different inputs into a hash function and getting the same output.

Collision resistance, on the other hand, refers to the property of it being difficult to find a collision. For example, if collision resistance is 128 bits, it means that finding a collision would require 2 ¹²⁸ operations (hash calculations).

Ethereum primarily uses the Keccak-256 hash function. Ideally, the output of the Keccak-256 hash function is 256 bits, but Ethereum currently uses only the last 20 bytes (=160 bits) of the Keccak-256 hash of a public key, arbitrarily truncated and represented in hexadecimal as the address. According to Vitalik’s “Increasing address size from 20 to 32 bytes”, the current Ethereum address has a collision resistance of 80 bits.

The text does not describe how the collision resistance value was calculated, but it is presumed to have been determined through the birthday attack. This article will not delve into the details of the birthday attack but will briefly explain it as a cryptographic attack used to find hash collisions. The probability of finding a collision using such a birthday attack in a hash function with H possible values (collision resistance) can be represented by the following formula:

For the current Ethereum address where H =2¹⁶⁰, calculating Q(2¹⁶⁰) yields a value of approximately 1.51516382 * 10²⁴. Since 2⁸⁰ = 1.20892581 * 10²⁴, Q(2¹⁶⁰) can be approximated to 2⁸⁰.

Let’s assume there is an attacker who generates one input through 1 unit of computing work. This attacker would have to perform computing work exceeding 2⁸⁰ to find a collision in an Ethereum address. Initially, when the Ethereum network was created, reaching the number 2⁸⁰ was not possible, so it did not pose a significant security issue. However, by March 2021, Bitcoin had already generated more than 2⁹⁰ hashes, leading Vitalik to conclude that the current collision resistance of 80 bits was within the range that could be attacked. Therefore, Vitalik proposes increasing the address size from 20 bytes to 32 bytes, incorporating the hash of the public key into 26 bytes of the address space to increase collision resistance.

Some may find it curious that only 26 bytes out of the total 32-byte address space are used to incorporate the hash value of the public key. This is because the larger the space occupied by the hash value, the stronger the security. However, as explained in Chapter 2, some of the remaining 6 bytes must contain period information for the introduction of state expiry. Moreover, configuring the address as ‘hash value + period information’ can also be beneficial from a security perspective. It becomes less vulnerable to simple repetitive attacks by attackers than when the address is composed solely of a hash value.

4. Concept of ASE

So far, we have examined the two backgrounds leading to the emergence of ASE, and now we intend to delve into the concept of ASE. As mentioned earlier, ASE signifies increasing the address space from 20 bytes to 32 bytes. However, it’s not just a simple increase in address size; the hash value of the public key, along with version information and period information, have been incorporated into the address space. Comparing the schema of the original address with the new address schema looks like this:

Original address schema

#legacy address
Byte 0-19 : 20-byte Keccak-256 hash

New address schema

#new address
Byte 0    : Version byte (must be 1 for now)
Byte 1-2  : Reserved (must be zero)
Byte 3-5  : Period number (0 <= e <= 16777215)
Byte 6-31 : 26 byte Keccak-256 hash

The meanings of each byte are as follows:

Byte 0: Represents the version information. (Currently, it must be 1)
Byte 1–2: Space left for the future. (Currently, it must be 0)
Byte 3–5: Represents period information.
Byte 6–31: The Keccak-256 hash value of the 26-byte public key.

To aid in understanding ASE, let’s assume a situation where Alice’s A address has been deleted due to state expiry, and Bob wants to transfer 9,101 ETH located at C address to Alice. The current period is 2.

Bob has the option to 1) pay the resurrection cost and transfer 9,101 ETH to the A address, or 2) not pay the resurrection cost and create a new address to which he can transfer the 9,101 ETH. Bob chose the former, and as a result, the A address was resurrected in period 2. The illustration contains the situation just before the transfer of 9,101 ETH.

5. Challenges Introduced by ASE

ASE represents a complete overhaul of the existing address system, and as such, it inevitably faces several challenges. To implement ASE, four major challenges must be addressed:

1. Existing contracts rely on 20-byte addresses.
2. External protocols also largely depend on 20-byte addresses.
3. How can we support both 20-byte and 32-byte addresses in current contracts?
4. How can we support both 20-byte and 32-byte addresses in new contracts?

6. Solution: ASE with Translation Map

Ipsilon proposed an idea called a Translation map in a forum to solve the four challenges mentioned above. Let’s take a closer look at how Ipsilon suggests solving these issues.

Notation:

hex”0100": Represents a hexadecimal string that becomes 01, 00 bytes.
|| : Represents byte-wise concatenation.
[i:]: Represents byte-wise slicing where the first i bytes are cut off.
keccak256(in) -> out: Represents the Keccak-256 hash function.
rlp([…]) -> out: Represents the RLP (Recursive Length Prefix) encoding of the array […].

Address Format

shortaddress: Refers to the current address of 20 bytes length that includes both contracts and EOAs (Externally Owned Accounts).
longaddress: Refers to the new address of 32 bytes, having the following structure.

byte 0    ; Version byte (must be 1)
byte 1-5  : Reserved (must be zero)
byte 6-31 ; 26-byte Keccak-256 hash

External owned addresses (EOAs)

In the case of EOAs, the longaddress is calculated through the code below, and the same EOA public-private key pair can control both the longaddress and the shortaddress.

hex"010000000000" || keccak256(pubkey)[6:]

Execution

This is an explanation of how execution semantics are affected. For clarity, Ipsilon has named the shortaddress as a legacy account and the longaddress as an extended account. Additionally, a new context variable, isLegacyAccount, has been introduced in the EVM execution frame. It is implemented to return true if the currently executed account belongs to a legacy account, otherwise false.

Address Translation

The Address Translation process is as follows: Since a legacy account can only handle a shortaddress, a conversion step to longaddress has been introduced. Also, several helper functions have been defined.

TRANSLATION_MAP_ADDR = hex"00000000000000000000000000000000000000ff"
EMPTY_CHUNK = bytes32([0] * 32)
DOMAIN = hex"efefefef"

If the first 12 bytes are not empty, it is considered a LongAddress.

# First 12 bytes are not empty, consider it as a LongAddress
def is_longaddress(address: LongAddress) -> bool:
    return address[:12] != hex"0000000000000000000000"

2. Compress the LongAddress through a helper.

# This helper compresses a LongAddress
def compress(address: LongAddress) -> ShortAddress:
    return keccak256(keccak256(DOMAIN + address))[12:]

3. If the address is a LongAddress, insert an entry in the translation map.

# Insert entry into the translation map if the address is a LongAddress
#
# This is only called within a non-legacy context.
def compress_and_touch(state: EthereumState, address: LongAddress) -> ShortAddress:
    if is_longaddress(address):
        short_address = compress(address)
        state[TRANSLATION_MAP_ADDR][short_address] = address
        return short_address
    else
        return address

4. The following function can be used when it is necessary to translate a ShortAddress to a LongAddress, such as when querying a target address. This function is called only within a legacy context.

# Look up a target address (if a ShortAddress translates to a LongAddress)
#
# This is only called within a legacy context.
def lookup_target(state: EthereumState, address: LongAddress) -> LongAddress:
    # Truncate input
    address = address[12:]
    if state[TRANSLATION_MAP_ADDR][address] != EMPTY_CHUNK:
        return state[TRANSLATION_MAP_ADDR][address]
    else
        # The account may or may not be legacy
        return address

While the translation map is a good solution, there is one drawback that must be overcome. As of February 12, 2024, according to ychart, there are approximately 258,080,000 unique addresses existing in Ethereum, and assuming the chain grows similarly, about 150 million new addresses will be added over the next two years, converting to short addresses. According to Ipsilon, in this case, the translation map would require a size of at least 150,000,000 * 64 / 1024 / 1024 ≈ 9,155Mb, so storage issues must be considered as well.

So far, we have explored the background and concept of ASE, the challenges of introducing ASE, and solutions to those challenges. ASE signifies the expansion of the address space from 20 bytes to 32 bytes. However, it’s not just an increase in size; the expansion also incorporates the hash value of the public key, along with version information and period information, into the address space.

This ASE was a necessary prerequisite for the introduction of state expiry. With the introduction of state expiry, addresses would be deleted and resurrected according to the period, necessitating the addition of period information to the address space to prevent confusion. Additionally, from a security perspective, the existing 20-byte addresses had reached a range that could be attacked, so it was necessary to increase the address size to 32 bytes to enhance collision resistance.

However, since both existing contracts and external protocols rely on 20-byte addresses, it was necessary to devise a way to support both 20-byte and 32-byte addresses. Therefore, Ipsilon proposed a solution utilizing a Translation map. This made it possible to compress a 32-byte address to a 20-byte address as needed and to look up the compressed 20-byte address as a 32-byte address. In Part 3, we will examine Merkle tree verification.