[이더리움 Stateless] 2. ASE(Address Space Extension)

Published in

Decipher Media ｜디사이퍼 미디어

17 min readFeb 14, 2023

서울대학교 블록체인 학회 디사이퍼(Decipher) After the merge 팀에서 이더리움의 로드맵 중 하나인 Stateless에 대한 글을 시리즈로 연재합니다. 본 글은 이더리움 Stateless 시리즈의 두 번째 편으로 ASE(Address Space Extension)에 관해 설명합니다.

Authors

정수현(Sam Jung)

Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)

Reviewd by 박성완, 신우진, 임요한

[이더리움 Stateless]

[목차]

들어가며
ASE 등장 배경 1: State expiry 도입을 위한 address space ID 추가
ASE 등장 배경 2: 보안 측면에서 충분하지 않은 20 bytes
ASE 개념
ASE 도입으로 인한 챌린지
솔루션: ASE with Translation Map
나가며

1. 들어가며

ASE는 Address Space Extension의 약자로 2021년 3월 비탈릭 부테린(Vitalik Buterin)이 포럼을 통해 처음 제시한 개념입니다. 후술하겠지만 ASE의 핵심은 address size를 20 bytes에서 32 bytes로 늘리자는 것인데, 비탈릭은 address space를 확장해야 하는 이유로 세 가지를 꼽았습니다.

1. State expiry 도입을 위한 address space ID 추가
2. EVM 지원 실행(execution) 샤드를 위한 샤드 ID 추가
3. 보안 측면에서 충분하지 않은 20 bytes

세 가지 이유 중에서 2. EVM 지원 실행 샤드를 위한 샤드 ID 추가는 계획 변경으로 인해 무산되었으며, 현재 1. State expiry 도입을 위한 address space ID 추가와 3. 보안 측면에서 충분하지 않은 20 bytes만 유효한 상황입니다. ASE가 등장하게 된 배경을 이해하면 ASE의 개념을 더 쉽게 이해할 수 있으므로, ASE 개념을 살펴보기에 앞서 ASE의 두 가지 등장 배경을 먼저 살펴보고자 합니다.

2. ASE 등장 배경 1: State expiry 도입을 위한 address space ID 추가

State expiry는 노드 운영 부담을 덜기 위해 state 크기를 줄이는 여러 방안 중 하나로, 최근에 접근하지 않은 state를 삭제하는 방안입니다. ‘최근’이라는 모호한 단어의 기준을 세우기 위해 state expiry에서는 period라는 개념을 도입했습니다. 1년을 주기(현재 기준)로 새로운 period가 새로운 tree와 함께 시작되는데, state expiry에서는 직전 period와 현재 period, 총 2개의 periods를 제외한 모든 periods를 roots만을 남겨둔 채 삭제합니다.

이때 2 periods 전을 마지막으로 지갑 상태를 변경하지 않은 사용자가 존재할 수 있습니다. 또한, 이 사용자가 자신이 보유하고 있던 ETH를 다른 지갑에 전송하기를 희망할 수 있습니다. 그러나 state expiry로 인해 사용자의 state는 삭제된 상황입니다. 이 경우 사용자는 자신의 ETH를 되찾을 수 없을까요?

아닙니다. 사용자는 약간의 비용을 지불하고 witness라는 proof를 제출하여 자신의 상태를 부활(resurrect)시킬 수 있습니다. Witness는 해당 위치에 특정 값이 존재했음 혹은 존재하지 않았음을 증명하기 위한 proof입니다. State expiry와 witness에 대해 더 자세하게 알고 싶으신 경우, 본 시리즈의 1편(링크)을 확인해주십시요.

다만, 보유 중인 ETH 수량과 부활 비용 사이의 기회비용에 따라 사용자에게는 두 가지의 선택지가 주어집니다. 첫째, 보유 중인 ETH 수량보다 부활 비용이 큰 경우, 사용자는 자신이 보유하고 있던 ETH를 포기하고 새로운 address를 생성합니다. 그렇게 해야 사용자 입장에서 손해를 덜 볼 수 있습니다. 둘째, 부활 비용보다 보유 중인 ETH 수량이 많은 경우, 비용을 지불하고 자신의 상태를 부활시킵니다.

이처럼 state expiry와 witness의 도입으로 과거 periods(직전 제외)의 states를 삭제한 상태에서도 자신의 state를 불러오는 것이 가능해졌지만, address의 관점에서 보면 수많은 addresses가 생성되고 사라져 혼란이 야기됩니다. 따라서 비탈릭은 이러한 혼란을 방지하기 위해 address space에 period에 관한 정보를 추가하자고 주장하는 것입니다.

3. ASE 등장 배경 2: 보안 측면에서 충분하지 않은 20 bytes

현재의 address size인 20 bytes가 보안 측면에서 충분하지 않은지를 이해하기 위해서는 해시 함수에서의 충돌(collision)과 충돌 저항성(collision resistance)이라는 개념을 먼저 이해해야 합니다.

충돌은 서로 다른 2개의 메시지가 같은 해시값을 갖는 것을 의미합니다. 하나의 해시 함수에 서로 다른 두 개의 인풋을 넣었는데 동일한 아웃풋이 나온다는 정도로 이해하면 수월할 것 같습니다.

또한, 충돌 저항성은 충돌을 발견하기 어려운 성질을 의미합니다. 예를 들어 충돌 저항성이 128 bits라면, 이는 충돌을 찾기 위해 2¹²⁸번의 작업(해시 계산)이 필요하다는 것을 의미합니다.

이더리움은 Keccak-256이라는 해시 함수를 주로 사용합니다. 원래대로라면 Keccak-256 해시 함수의 아웃풋은 256 bits지만, 이더리움은 현재 공개 키의 Keccak-256 해시값 중 마지막 20 bytes(=160 bits)만을 임의로 잘라 16진수로 나타내어 address로 사용하고 있습니다. 비탈릭이 작성한 Increasing address size from 20 to 32 bytes에 따르면 현재 이더리움 address의 충돌 저항성은 80 bits입니다.

윗글에 충돌 저항성 값을 구하는 과정이 서술되어 있지 않지만, 생일 공격(birthday attack)을 통해 값을 구했을 것으로 추측됩니다. 본고에서는 생일 공격에 대해 자세히 설명하지 않고, 해시 함수의 해시 충돌을 찾아내는 암호해독 공격이라고만 간단히 설명하겠습니다. 이러한 생일 공격을 활용하여 충돌을 찾을 확률을 수식으로 나타낼 수 있는데, H가지의 값을 가지는 해시 함수에서 충돌을 찾을 확률(=충돌 저항성)은 다음과 같습니다.

현재 이더리움 address에서 H = 2¹⁶⁰이므로, Q(2¹⁶⁰)를 계산하면 약 1.51516382 * 10²⁴라는 값이 도출됩니다. 2⁸⁰ = 1.20892581 * 10²⁴이므로 Q(2¹⁶⁰) ~= 2⁸⁰으로 어림잡을 수 있습니다.

1의 컴퓨팅 작업을 통해 1개의 인풋을 생성하는 공격자가 있다고 가정해보겠습니다. 이 공격자는 이더리움 address의 충돌을 발견하기 위해 최소 2⁸⁰을 초과하는 컴퓨팅 작업을 수행해야 합니다. 이더리움 네트워크가 생성된 초기에는 2⁸⁰이라는 숫자에 도달할 수 없었기 때문에 보안 측면에서 큰 문제가 발생하지 않았습니다. 그러나 비트코인은 2021년 3월을 기준으로 이미 2⁹⁰개가 넘는 해시를 만들었기에 비탈릭은 80 bits인 현재의 충돌 저항성이 공격당할 수 있는 범위에 들어왔다고 판단했습니다. 따라서 비탈릭은 20 bytes의 address를 32 bytes로 늘린 뒤, 이 중 26 bytes의 address space에 공개 키의 해시값을 포함하여 충돌 저항성을 늘리자고 주장하는 것입니다.

혹자는 전체 address space인 32 bytes 중에서 26 bytes에만 공개 키의 해시값을 집어넣었다는 점에서 의아하게 생각하실 수도 있습니다. 해시값이 차지하는 space가 넓을수록 보안이 강해지기 때문입니다. 그러나 2장에서 설명했던 것처럼 state expiry 도입을 위해서는 남은 6 bytes의 일부분에 period 정보를 집어넣어야 합니다. 또한, address의 구성을 ‘해시값 + period 정보’로 가져가는 것이 보안 측면에서도 도움이 될 수 있습니다. 해시값만으로 address를 구성했을 때보다 공격자의 단순 반복 공격에 덜 취약해지기 때문입니다.

4. ASE 개념

지금까지 ASE가 등장하게 된 두 가지 배경을 살펴보았으며, 지금부터는 ASE의 개념을 파헤쳐보고자 합니다. 앞서 언급했던 것처럼 ASE는 address space를 20 bytes에서 32 bytes로 늘리는 것을 의미합니다. 다만 단순히 address size만 늘리지 않고, 공개 키의 해시값과 더불어 version 정보 및 period 정보를 address space에 함께 집어넣었습니다. 기존 address와 새 address의 스키마를 비교해보면 다음과 같습니다.

기존 address 스키마

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

새 address 스키마

#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

각 byte가 나타내는 의미는 다음과 같습니다.

Byte 0 : 버전 정보를 나타냅니다. (현재 기준으로 반드시 1)
Byte 1-2 : 미래를 위해 남겨 놓은 공간입니다. (현재 기준으로 반드시 0)
Byte 3-5 : Period 정보를 나타냅니다.
Byte 6-31 : 26 bytes 크기의 공개 키에 대한 Keccak-256 해시값입니다.

ASE에 대한 이해를 돕기 위해 Alice의 A address가 state expiry로 인해 삭제된 상황에서 Bob이 C address에 있는 9,101ETH를 Alice에게 전송하려는 상황을 가정해보겠습니다. 현재 period는 2입니다.

Bob은 1) 부활 비용을 지불하고 A address로 9,101ETH를 전송할 수 있으며, 혹은 2) 부활 비용을 지불하지 않고 새로운 address를 생성하여, 그 address로 9,101ETH를 전송할 수 있습니다. Bob은 전자를 택했고, 그 결과 A address가 period 2에서 부활하였습니다. 그림은 9,101ETH를 전송하기 직전까지의 상황을 담고 있습니다.

5. ASE 도입으로 인한 챌린지

ASE는 기존 address 체계를 모두 바꾸는 작업이기에 여러 가지 챌린지에 직면할 수밖에 없습니다. ASE를 도입하기 위해서는 크게 네 가지 챌린지를 해결해야 합니다.

1. 현존하는 컨트랙트는 20 bytes address에 의존한다.
2. 외부 프로토콜 또한 대부분 20 bytes address에 의존한다.
3. 어떻게 현재 컨트랙트에 20 bytes address와 32 bytes address를 함께 지원할 수 있을까?
4. 어떻게 새 컨트랙트에 20 bytes address와 32 bytes address를 함께 지원할 수 있을까?

6. 솔루션: ASE with Translation Map

Ipsilon은 앞에서 언급한 네 가지 챌린지를 해결하기 위해 Translation map이라는 아이디어를 포럼에 제안했습니다. Ipsilon이 어떤 식으로 문제를 해결하는지 차근차근 살펴보겠습니다.

표기법

hex"0100" : 01, 00 bytes가 되는 16진수 문자열을 뜻합니다.
|| : byte 단위 연결을 뜻합니다.
[i:] : 앞 i bytes가 잘리는 byte 단위 슬라이싱을 뜻합니다.
keccak256(in) -> out : Keccak-256 해시 함수를 뜻합니다.
rlp([...]) -> out 배열 [...] 의 RLP(Recursive-length prefix) 인코딩을 뜻합니다.

Address 포맷

shortaddress : 컨트랙트와 EOA를 모두 포함하는 20 bytes 길이의 현재 address를 뜻합니다.
longaddress : 32 bytes의 새 address를 뜻하며, 다음과 같은 구조를 띱니다.

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)

EOA의 경우 아래의 코드를 통해 longaddress를 계산하며, 같은 EOA public-private key 쌍으로 longaddress와 shortaddress를 모두 제어할 수 있습니다.

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

Execution

실행 시맨틱이 어떻게 영향받는지에 관한 설명입니다. Ipsilon은 명확한 표현을 위해 shortaddress를 legacy account라고, longaddress를 extended account라고 명명하였습니다. 또한, EVM execution frame에 새 컨텍스트 변수 isLegacyAccount를 도입하였습니다. 아울러 현재 실행된 accoount 가 legacy account에 속하면 true, 그렇지 않다면 false를 반환하도록 구현하였습니다.

Address Translation

Address Translation 과정은 다음과 같습니다. Legacy account는 오직 shortaddress만 다룰 수 있기 때문에, longaddress에 변환 단계를 도입했습니다. 또한, 몇 가지 helper 함수를 정의했습니다.

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

첫 12 bytes가 비어 있지 않으면, LongAddress로 간주합니다.

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

2. Helper를 통해 LongAddress를 압축합니다.

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

3. Address가 LongAddress인 경우 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. 대상 address를 조회할 때와 같이 ShortAddress를 LongAddress로 translate 해야 하는 경우 아래의 함수를 활용할 수 있습니다. 이 함수는 legacy 콘텍스트 내에서만 호출됩니다.

# 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

Translation map은 좋은 솔루션이지만, 다만 한 가지 단점을 극복해야 합니다. 이더리움에 존재하는 총 unique addresses 수는 2023년 1월 11일 ychart 기준 약 219,610,000개인데, 체인이 비슷하게 성장한다고 가정하면 향후 2년 동안 1억 5천만 개의 새로운 address가 추가로 생겨 short address로 변환될 것입니다. Ipsilon에 따르면 이 경우 translation map은 최소 150,000,000 * 64 / 1024 / 1024≒ 9,155Mb의 크기를 요구하기 때문에, 스토리지 문제를 함께 고려해야 할 것입니다.

7. 나가며

지금까지 ASE의 등장 배경과 ASE의 개념, ASE 도입을 위한 챌린지 및 해결 방안을 살펴보았습니다. ASE는 address space를 20 bytes에서 32 bytes로 늘리는 것을 의미합니다. 다만 단순히 크기만 늘린 것은 아니며, 크기를 늘리면서 공개 키의 해시값과 더불어 version 정보 및 period 정보를 address space에 집어넣었습니다.

이러한 ASE는 State expiry 도입을 위해 반드시 선행되어야 하는 작업이었습니다. State expiry가 도입되면 Period에 따라 address가 삭제되고 부활하기 때문에 address space에 period에 관한 정보를 추가하여 혼란을 방지할 필요가 있었습니다. 또한, 보안 측면에서도 20 bytes의 기존 address는 공격당할 수 있는 범위에 도달했기 때문에 address size를 32 bytes로 늘려 충돌 저항성을 높일 필요가 있었습니다.

다만 기존 컨트랙트와 외부 프로토콜이 모두 20 bytes address에 의존하기 때문에 20 bytes address와 32 bytes address를 함께 지원하는 방안을 마련해야만 했습니다. 그래서 ipsilon은 Translation map을 활용하는 솔루션을 제시했습니다. 이를 통해 필요에 따라 32 bytes address를 20 bytes로 압축하여 사용하고, 압축한 20 bytes address를 32 bytes address로 조회하는 것이 가능해졌습니다. 3편에서는 버클 트리 검증에 대해 살펴보겠습니다.