RLP encoding

RLP(Recursive Length Prefix)는 임의의 깊이와 개수로 중첩된 배열을 binary data로 표현하는 인코딩 방식이다. 인코딩할 데이터 앞에 binary data의 길이를 추가하는 방식으로 동작하기 때문에 Length Prefix라는 이름이 붙었다. 현재 RLP는 이더리움이 patricia tree를 만드는 데만 이용되고 있지만, 스펙 자체는 일반적으로 사용할 수 있도록 정의돼 있다.

RLP의 input은 binary data이다. 그 값의 이름이 무엇이고, 어떤 타입이고, 어떤 representation을 가지는지는 RLP에서 정의하지 않는다. 이는 별도의 규약을 정하여 RLP 인코딩을 하기 전에 binary data로 변경해야 한다.

RLP가 인코딩하는 방법은 인코딩할 입력이 무엇인지에 따라 달라진다.

ASCII

우선 입력이 한 바이트의 일반 ASCII 캐릭터. 즉, 0x00에서 0x7F에 해당하는 값이라면 별도의 length prefix 없이 바로 사용한다.

문자열

입력이 한 바이트 ASCII 캐릭터가 아닌 바이트의 배열. 즉, 문자열이라면, 앞에 배열의 길이를 prefix로 붙이고, 그 뒤에 바이트의 배열을 그대로 사용한다. 다만 여기서 말하는 문자열은 일반적인 프로그래밍에서 말하는 문자열이 아닌, 바이트의 배열로 봐야 한다. RLP는 배열이 아닌 다른 타입은 구분 없이 문자열로 받는다. 예를 들어 문자에는 ASCII를 쓰고, 정수는 zero padding 없는 big endian을 사용한다고 했을 때, 문자열 'ab'도 [0x61, 0x62]로 표현되고, 정수 24,930도 [0x61, 0x62]로 표현된다.실제 이 값을 정수로 해석해야 하는지, 문자로 해석해야 하는지는 RLP보다 상위 레이어에서 결정하여야 한다.

여러 바이트의 문자열은 몇 바이트가 인코딩됐는지 length prefix를 붙여 인코딩하는데, length prefix를 어떻게 붙일지는 문자열의 길이에 따라 달라진다. 만약 문자열의 길이가 55 이하라면, 길이에 0x80을 더한 값 1바이트가 prefix로 붙는다. 예를 들어 인코딩할 문자열이 'ab'라면, 길이는 2이므로, 'ab' 앞에 0x82가 prefix로 붙어 인코딩한 값은 [0x82, 0x61(=a), 0x62(=b)]가 된다. 길이가 55 이하인 문자열에서만 이 방법을 사용하기 때문에, prefix의 범위는 0x80에서 0xB7이 된다. 문자열의 길이가 55보다 크면 길이의 길이를 한 번 더 prefix로 붙이고, 그 뒤에 길이를 prefix로 붙인다. 이때 길이는 big endian으로 표현하고, 길이의 길이는 앞에 0을 붙이지 않고 길이를 표현할 수 있는 최소한의 바이트 수가 된다. 예를 들어 길이가 56(0x38)이면 1이 되고, 1024(0x0400)라면 2가 되는 식이다. 이 길이의 길이는 바로 사용하면 한 바이트인 일반 ASCII 캐릭터와 구분되지 않기 때문에 0xB7을 더해서 prefix로 붙인다. 따라서 56바이트를 인코딩한 경우 prefix로 [ 0xB8, 0x01 ]이 붙고, 길이가 1024인 문자열을 인코딩하면 prefix로 [ 0xB9, 0x04, 0x00 ]이 붙는다. 길이의 길이는 1바이트만을 사용하고, 0xB8에서 0xBF만을 사용한다. 따라서 길이의 길이는 최대 8이고, 인코딩할 수 있는 문자열의 최대 길이는 0xFFFFFFFFFFFFFFFF다.

배열

지금까지 일반적인 바이트 배열을 어떻게 인코딩하는지 설명하였다. 이를 이용하여 string이나 integer 등 간단한 값을 인코딩할 수 있다. 하지만 RLP의 목적은 임의의 깊이로 중첩된 배열을 binary data로 변환하는 것이므로 배열의 배열 또한 표현할 수 있어야 한다.

배열의 배열을 인코딩할 때는 배열의 각 원소를 재귀적으로 인코딩한다. 배열의 원소를 전부 인코딩하여 연결하면 binary data가 된다. 배열의 배열은 이 binary data에 binary data의 길이를 prefix로 붙이는 것으로 인코딩한다. prefix를 붙이는 방법은 문자열의 prefix를 붙이는 방식과 비슷하다. 길이가 55 이하인 binary data의 길이는 한 바이트로 prefix가 붙고, 56 이상인 경우 길이의 길이와 길이를 prefix로 사용한다. 다만, 이때 인코딩된 문자열과 구분하기 위해서 55보다 작은 길이에는 0x80 대신 0xC0을 더하고, 56보다 긴 길이의 길이에는 0xB8 대신 0xF7을 더한다.

앞에서 설명했듯이 RLP는 데이터의 길이를 prefix로 붙이는 것만으로 다양한 형태의 데이터를 인코딩할 수 있게 해준다. 이로 인해 단순하지만 빠르고 효율적인 인코딩이 된다. 하지만 앞에서 말했듯이 타입과 이름을 인코딩하지 않기 때문에 RLP를 사용하는 레이어에서 인코딩된 정보가 어떤 타입이고 어떤 의미를 가지는지 알고 있어야 한다. 또한, 길이를 prefix로 붙이는 것뿐이고 데이터 자체에는 아무런 가공을 하지 않기 때문에 변조나 오염에 매우 취약하다. 따라서 데이터를 전송하거나 저장할 때, RLP로 인코딩된 값을 그대로 사용하지 않고, 데이터가 변조된 것을 알 수 있게 하는 코드나 signature를 더 붙이는 가공을 해야 한다.