RLP(Recursive Length Prefix) & HP(Hex Prefix) 엔코딩

다양한 복잡한 형식의 데이타를 하나의 정형화된 형식으로 직렬화하여 저장하거나 전송하는것은 현재 여러 컴퓨터 시스템에서 반드시 필요합니다. 이와같은 목적을 위해 RLP(Recursive Length Prefix) 엔코딩은 이더리움 내부에서 임의의 길이의 배열이나 문자를 엔코딩하기위해 개발된 엔코딩 패키지입니다. RLP 엔코딩은 이더리움 헤더의 state root, transaction root, receipt root와 통신 프로토콜상의 메시지등 이더리움에서 전체적으로 사용되고 있습니다. 기존의 Base64, 유니코드, UTF-8등 다양한 엔코딩 방식에 비해 엔코딩 과정이 단순하고 바이트단위의 일관성을 확보하기 쉬운 장점을 가지고 있습니다.

RLP 엔코딩은 아이템(item)을 단위로 사용하고 있으며, 아이템은 다음과 같이 정의됩니다.

1. 바이트배열로 변환이 될 스트링

2. 스트링의 배열

위 2개 아이템의 예를 들면 다음과 같습니다.

- ["cat",  ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]

- ["cat", "horse"] : "cat", "horst", ["cat", "horst"] 총 3개의 아이템으로 구성됨

즉, RLP 엔코딩의 단위는 하나의 단어가 될수도 있고, 그 단어로 구성된 배열도 또한 RLP 엔코딩의 단위가 될수 있습니다.

1. RLP 엔코딩

RLP 엔코딩은 다음과 같이 5개의 규칙으로 정의되어 있습니다.

1. 1바이트의 데이타가 [0x00, 0x7f] 사이의 값이면 해당 바이트를 그대로 사용한다. 이는 아스키코드(0x00 ~ 0x7f) 는 그대로 사용한다는 의미로 볼수 있습니다.

   - RLP(0x01) = 0x01, RLP(0x7f) = 0x7f

2. 스트링의 길이가 0~55 바이트인 경우, 0x80에 스트링의 길이를 더한값을 앞에 붙이고 이어서 스트링을 붙입니다. 따라서 첫번째 바이트는 [0x80, 0xb7] 사이의 값을 가집니다.

   - RLP("hello world") = [0x8b, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x77, 0x6f, 0x72, 0x6c, 0x64]

      : "hello world" 길이는 11(0x0b), 0x8b = 0x80 + 0x0b

3, 스트링의 길이가 55바이트를 넘어가는 경우, 0xb7에 스트링의 길이값의 바이트값을 더하고, 스트링의 길이를 이어서 붙인후, 스트링의 바이트를 붙입니다. 첫번째 바이트는 [0xb8, 0xbf] 사이의 값을 가집니다.

   - RLP("aaa...") [1024개의 a로 이루어진 스트링] = [0xb9, 0x04, 0x00, 0x61, 0x61, …]

      : 0xb9 = 0xb7 + 0x02 (스트링 사이즈가 1024이며, 이는 0x0400(0x04, 0x00, 즉 길이의 바이트수는 2)

4. 배열의 아이템들이 RLP 엔코딩된 아이템의 총길이가 0~55 바이트 사이인 배열인 경우, 0xc0에 각각 아이템들을 RLP엔코딩한 값들의 길이를 더하고 각각의 아이템을  RLP엔코딩한 데이타를 이어 붙입니다. 첫번째 바이트는 [0xc1, 0xf7] 사이의 값을 가집니다.

   - RLP([“hello”, “world”]) = [0xcc, 0x85, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x85, 0x77, 0x6f, 0x72, 0x6c, 0x64]

      : RLP("hello") = 0x85, 0x68, 0x65, 0x6c, 0x6c, 0x6f,, 즉 길이는 6

        RLP("world") = 0x85, 0x77, 0x6f, 0x72, 0x6c, 0x64, 즉 길이는 6

        따라서 0xcc = 0xc0 + 0x06 + 0x06 

5. 배열의 아이템들이 RLP 엔코딩된 아이템의 총길이가 55보다 큰경우, 0xf7에 각각 아이템들의 RLP 엔코딩한 결과의 길이를 더한 길이값의 바이트값을 더하고, 각각 RLP엔코딩한 아이템들의 길이값의 합을 붙이고, 이어서 각각 아이템들의 RLP 엔코딩된 값을 이어붙입니다. 이와같이 3개 파트로 구성되며, 첫번째 바이트는 [0xf8, 0xff] 사이의 값을 가집니다.

   - RLP("a...", "a...") [a 50개로 이루어진 배열] = [0xf8, 0x66, 0xb2, 0x61..., 0xb2,, 0x61...]

      : 0xf8 = 0xf7 + 0x01 (a 50개로 이루어진 배열의 RLP 엔코딩결과의 길이는 51, 2개이기 떄문에 총 102(0x66), 즉 전체길이는 0x66 1바이트로 표현됨 

        0x66 = 각각 아이템 배열의 RLP 엔코딩된 전체길이

RLP 엔코딩의 파이썬 코드는 다음과 같습니다. : [Ethereum Wiki : RLP]

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80: return input
        else: return encode_length(len(input), 0x80) + input
    elif isinstance(input,list):
        output = ''
        for item in input: output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output
def encode_length(L,offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    else:
         raise Exception("input too long")
def to_binary(x):
    if x == 0:
        return ''
    else: 
        return to_binary(int(x / 256)) + chr(x % 256)

2. RLP 디코딩

RLP 디코딩은 다음과정으로 동작됩니다.

1. 입력 데이타의 첫번째 바이트에 따라, 데이타의 타입과 아이템의 갯수를 파악합니다.

2. 데이타의 유형 및 오프셋에 따라 데이타를 디코딩합니다. 

3. 나머지 입력데이타를 계속해서 디코딩합니다.

이중에서 데이타의 유형 및 오프셋을 디코딩하는 규칙은 다음과 같습니다.

1. 첫번째 바이트가 [0x00, 0x7f] 사이의 값이면 그값 자체가 문자 데이타입니다. [엔코딩 규칙 1번]

2. 첫번째 바이트가 [0x80, 0xb7] 사이의 값이면 문자열이고, 첫번째 바이트에서 0x80을 뺀 값이 문자열의 길이입니다. [엔코딩 규칙 2번]

3. 첫번째 바이트가 [0xb8, 0xbf] 사이의 값이면, 첫번째 바이트에서 0xb7을 뺀값이 바이트로 표현된 RLP 아이템의 갯수가 되고, 이어서 그 갯수만큼 문자가 이어집니다. [엔코딩 규칙 3번]

4. 첫번째 바이트가 [0xc0, 0xf7] 사이의 값이면, 배열을 의미하고, 첫번째 바이트에서 0xc0를 뺀값이 배열의 갯수를 의미합니다. [엔코딩 규칙 4번]

5. 첫번째 바이트가 [0xf8, 0xff] 사이의 값이면, 배열을 의미하고, 첫번째 바이트에서 0xf7을 뺀값이 아이템의 갯수이고, 이어서 RLP 엔코딩되어 연결된 데이타가 첫번빼 바이트 이후에 이어집니다. [엔코딩 규칙 5번]

RLP 디코딩의 파이썬 코드는 다음과 같습니다. : [Ethereum Wiki : RLP]

def rlp_decode(input):
    if len(input) == 0:
        return
    output = ''
    (offset, dataLen, type) = decode_length(input)
    if type is str:
        output = instantiate_str(substr(input, offset, dataLen))
    elif type is list:
        output = instantiate_list(substr(, offset, dataLen))
    output + rlp_decode(substr(input, offset + dataLen))
    return output
def decode_length(input):
    length = len(input)
    if length == 0:
        raise Exception("input is null")
    prefix = ord(input[0])
    if prefix <= 0x:
        return (0, 1, str)
    elif prefix <= 0xb7 and length > prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix   input, 1, prefix - 0xb7)):
        lenOfStrLen = prefix - 0xb7
        strLen = to_integer(substr(input, 1, lenOfStrLen))
        return (1 + lenOfStrLen, strLen, str)
    elif prefix <= 0xf7 and length > prefix - 0x
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
        lenOfListLen = prefix - 0x
        listLen = to_integer(substr(input, 1, lenOfListLen))
        return (1 + lenOfListLen, listLen, list)
    else:
        raise Exception("input don't conform RLP encoding form")
def to_integer(b):
    length = len(b)
    if length == 0:
        raise Exception("input is null"elif length == 1:
        return ord(b[0])
    else:
        return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

3. HP (Hex Prefix) 엔코딩

이더리움의 머클 패트리시아 트리의 경로를 만들기 위해 HP(Hex Prefix) 엔코딩이 사용이 되며, HP 엔코딩의 동작원리와 RLP 엔코딩과의 차이점에 대해서 알아보겠습니다. 

먼저 다음의 경로를 통해서 최종결과가 무엇인지 찾는 문제를 보겠습니다.

Path : 3-2-3

Root: {1: 'Dog', 2: B, 3: A}

A: {1: C, 2: D, 3: 'Cat'}

B: {1: 'Goat', 2: 'Bear', 3: 'Rat'}

C: {1: 'Eagle', 2: 'Parrot', 3: E}

D: {1: 'Shark', 2: 'Dolphin', 3: 'Whale'}

E: {1: 'Duck', 2: 'Chinken', 3: 'Pig'}

직관적으로 봐서 Root부터  시작해서 3(A) -> 2(D) -> 3(Whale), 즉 3-2-3 경로를 통해서 Whale을 찾을수 있습니다.

동일한 경로로 3-1-3-2의 경로는 Chicken에 해당됩니다.

위의 자료구조를 통해서 다음의 용어를 정의합니다.

키(Key) : 왼쪽의 Root, A, B, C, D, E

노드(Node) : 키와 연관된 오른쪽 요소 (예를 들어 {1: 'Dog', 2: B, 3: A})

값(Value) : 노드의 모든 요소는 키-값 구조로 구성되어 있으며, 값은 요소의 오른쪽 값이며, 위의 예에서는 값은 키가 될수도 있고, 동물이름(Dog, Goat, Gear 등)이 될수도 있습니다.

니블(Nibble) : 4비트의 hex form. 예를 들어 0x1, 0x4, 0xf 등

RLP 엔코딩과 HP 엔코딩의 차이는 다음과 같습니다.

1. RLP : 값(Value)를 엔코딩/디코딩하는 용도로 사용

2. HP : 패스(Path)를 엔코딩/디코딩하는 용도로 사용

HP 엔코딩을 하기 위한 목적은 위의 예에서 설명한것처럼 리프(Leaf)노드와 확장(Extension)노드를 구분하기 위해서 선행구분자를 붙이기 위한것 입니다. 리프노드는 더이상 확장이 되지않는 값을 가지는 최종노드이고, 확장노드는 다음 노드를 가리키는 확장되는 노드를 말합니다. 리프노드와 확장노드의 다음포스팅인 머클 패트리시아 트리에서 다시 다루어집니다. 리프노드는 "terminator"로 끝나며 이것은 0x10에 해당됩니다.

정리를 해보면 HP 엔코딩의 목적은 다음과 같습니다.

1. "terminator"가 없이 리프노드와 확장노드를 구분

2. 경로를 짝수길이로 변환

이것은 다음과 같이 이루어집니다.

1. 입력에 "terminator"가 있다면 "terminator"를 제거

2. 리프노드와 확장노드에 따라 하기의 prefix를 앞에 추가

node type    path length    |    prefix    hexchar
--------------------------------------------------
extension    even           |    0000      0x0
extension    odd            |    0001      0x1
leaf         even           |    0010      0x2
leaf         odd            |    0011      0x3

3. 만약 prefix가 0x0이거나 0x2가 된다면 경로를 짝수로 만들기 위해 패딩 0을 붙여서 0x00, 0x20으로 만들어줍니다.

4. prefix를 경로에 추가

위의 과정을 확인하기 위한 예제는 다음과 같습니다.

> [ 1, 2, 3, 4, 5]

'11 23 45'

> [ 0, 1, 2, 3, 4, 5]

'00 01 23 45'

> [ 0, f, 1, c, b, 8, 16]

'20 0f 1c b8'

> [ f, 1, c, b, 8, 16]

'3f 1c b8'

하나만 예를 들어본다면 다음과 같습니다.

- [1,2,3,4,5] 는 마지막에 16(0x10)이 없이 때문에 리프노드가 아닌 확장노드 (0x0, 0x1중 선택가능)

- 경로가 홀수개이기 때문에 0x1 선택

- 경로는 짝수로 만들어야 하기 때문에 앞에 prefix 1을 붙여 11

- 나머지는 각 경로를 2개씩 묶어서 짝수로 해서 23, 45.

- 최종 경로는 11 23 45

나머지는 각자 생각해보시면 좋을것 같습니다.