RLP (Recursive Length Prefix) 직렬화 이해하기

 RLP는 임의의  바이트열을 공간 효율적인 형식으로 인코딩하는 방식으로, 이더리움 클라이언트에서 사용됩니다.

 

 RLP 인코딩 함수는 아이템을 파라미터로 받는데, 아이템의 정의는 다음과 같습니다.

• 문자열
• 아이템의 리스트

 예를 들어, 이하의 항목은 모두 아이템으로 취급됩니다.

• 빈 문자열
• "cat"
• [ "cat", "dog" ] (리스트)
• [ "cat", [ "puppy", "cow", [ ] ] (중첩된 리스트)

이 글에서 문자열이라고 함은, 단순히 '바이너리 데이터의 바이트 표현의 모음; 바이트열'을 의미합니다. 별다른 인코딩이 사용되거나 하지 않습니다.

정수는 부호가 없는 정수만 사용이 가능하며, 문자열로 변환하여 인코딩합니다. 그렇지 않으면 다른 타입과의 충돌이 발생할 수 있습니다.

---

RLP 인코딩 규칙

1. 단일 바이트

 값이 [0x00. 0x7f] (10진수로 [0, 127]) 사이의 단일 바이트인 경우, 그 자체로 RLP 인코딩된 아이템으로 취급합니다. (0~127 사이의 아스키 코드 취급)

2. 문자열

문자열의 길이가 55 바이트 이하인 경우

 0x80 (10진수로 128)에 문자열의 길이(바이트 단위)를 더한 값을 접두사로 사용하고 그 뒤에 문자열을 연결합니다. 문자열의 길이가 [0, 55]이므로 접두사는 [0x80, 0xb7] (10진수로 [128, 183]) 사이의 값을 가집니다.

 

 예를 들어, "cat"을 RLP 인코딩하면

[]byte("cat") = 0x63/0x61/0x74
len("cat") = 3
prefix = 0x80 + 0x03 = 0x83
RLP("cat") = 0x83/0x63/0x61/0x74

문자열의 길이가 55 바이트를 초과하는 경우

 0xb7 (10진수로 183)에 문자열의 길이를 바이트열로 변환했을 때의 길이를 더한 값을 접두사로 사용하고 문자열의 길이와 문자열을 이어 붙입니다. 접두사는 [0xb8, 0xbf] (10진수로 [184, 191]) 사이의 값을 가집니다.

 

 예를 들어, 길이가 1024인 문자열 s를 인코딩하면

len(s) = 1024 = 0x0400
len(bigendian(len(s))) = 0x02
prefix = 0xb7 + 0x02 = 0xb9
RLP(s) = 0xb9/0x04/0x00/ []byte(s)...

3. 리스트

페이로드의 길이가 55 바이트 이하인 경우

 리스트의 페이로드의 길이(리스트의 모든 아이템을 RLP 인코딩한 결과의 길이의 합)가 55바이트 이하인 경우, 0xc0 (10진수로 192)에 페이로드의 길이(바이트 단위)를 더한 값을 접두사로 사용하고 그 뒤에 페이로드를 연결합니다. 페이로드의 길이가 [0, 55]이므로 접두사는 [0xc0, 0xf7] (10진수로 [192, 247]) 사이의 값을 가집니다. (문자열의 길이는 최대 2⁶⁴ - 1)

 

 예를 들어, 리스트 ["cat", "dog"]를 인코딩하면

[]byte("cat") = 0x63/0x61/0x74
len("cat") = 3
prefix1 = 0x80 + 0x03 = 0x83
RLP("cat") = 0x83/0x63/0x61/0x74

[]byte("dog") = 0x64/0x6f/0x67
len("dog") = 3
prefix2 = 0x83
RLP("dog") = 0x83/0x64/0x6f/0x67

payload = 0x83/0x63/0x61/0x74/0x83/0x64/0x6f/0x67
len(payload) = 0x08
prefix3 = 0xc0 + 0x08 = 0xc8
RLP(["cat", "dog"]) = 0xc8/0x83/0x63/0x61/0x74/0x83/0x64/0x6f/0x67

페이로드의 길이가 55 바이트를 초과하는 경우

 0xf7 (10진수로 247)에 페이로드의 길이를 바이트열로 변환했을 때의 길이를 더한 값을 접두사로 사용하고 그 뒤에 페이로드를 연결합니다. 접두사는 [0xf8, 0xff] (10진수로 [248, 255]) 사이의 값을 가집니다. (페이로드의 길이는 최대 2⁶⁴ - 1)

 

 예를 들어, 길이가 1024인 페이로드 s' 인코딩하면

len(s') = 1024 = 0x0400
len(bigendian(len(s'))) = 0x02
prefix = 0xf7 + 0x02 = 0xf9
RLP(s) = 0xf9/0x04/0x00/ []byte(s)...

---

RLP 코딩 규칙

1. 단일 바이트

 입력의 첫 번째 바이트가 [0x00, 0x7f]인 경우, 단일 바이트 값 그 자체로 읽어들입니다.

2. 문자열

입력의 첫 번째 바이트가 [0x80, 0xb7]

 길이가 55이하인 문자열입니다. 첫 번째 바이트에서 0x80을 뺀 값 만큼 문자열을 읽어들입니다.

입력의 첫 번째 바이트가 [0xb8, 0xbf]

 길이가 55를 초과하는 문자열입니다. 첫 번째 바이트에서 0xb7을 뺀 값 만큼 바이트를 읽어들인 뒤, 읽어 들인 바이트를 정수(빅 엔디언)로 변환하여 다시 해당 길이 만큼 문자열을 읽어들입니다.

3. 리스트

입력의 첫 번째 바이트가 [0xc0, 0xf7]

 길이가 55이하인 페이로드를 가진 리스트입니다. 첫 번째 바이트에서 0xc0을 뺀 값 만큼 페이로드를 읽어들입니다. 페이로드는 문자열 또는 리스트를 포함하므로 재귀적으로 디코딩합니다.

입력의 첫 번째 바이트가 [0xf8, 0xff]

 길이가 55를 초과하는 페이로드를 가진 리스트입니다. 첫 번째 바이트에서 0xf7을 뺀 값 만큼 바이트를 읽어들인 뒤, 읽어 들인 바이트를 정수로 변환하여 다시 해당 길이 만큼 페이로드를 읽어들입니다. 읽어 들인 페이로드는 문자열 또는 리스트를 포함하므로 재귀적으로 디코딩합니다.

---

정리

• RLP는 길이와 아이템의 타입을 나타내는 접두사를 사용해 재귀적으로 인코딩/디코딩을 수행합니다.
• 아이템에는 문자열과 리스트가 있습니다.
• RLP는 1바이트 크기의 접두사를 사용해 동적으로 아이템의 타입과 길이를 나타냅니다. 이는 고정 크기의 접두사를 사용하는 방식보다 공간 효율적입니다.
• [0x00, 0x7f]는 접두사가 아니며, 단일 바이트로 예약된 값입니다.
• [0x80, 0xbf]는 문자열의 길이를 나타내는 접두사로 예약된 값입니다.
• [0xc0, 0xff]는 리스트의 페이로드 길이를 나타내는 접두사로 예약된 값입니다.

---

참고

Recursive-length prefix (RLP) serialization | ethereum.org

Data structure in Ethereum | Episode 1: Recursive Length Prefix (RLP) Encoding/Decoding.