RLP(Recursive Length Prefix)
씹어먹기
<외부자료로 활용 시 출처만 밝혀주세요>
Created by Onther Inc.
RLP란?
인코딩(Encoding)
RLP Definition - 이더리움 위키 정의
1.만약 단일 바이트가 [0x00, 0x7f] 사이값이라면, 그 바이트는 자체로 RLP인코딩이 된다.
파이썬 예제
>>import rlp
>>rlp.encode(0x1) # 리턴값 b'\x01'
>>rlp.encode(0x7f) # 리턴값 b'\x7f'
RLP Definition - 이더리움 위키 정의
2.만약 문자열이 0-55 bytes 사이의 길이라면 RLP는 싱글 바이트인 0x80에 문자열의 길이를 더한 값에 문자열바이트를 붙인다. 따라서 첫번째 바이트는 [0x80, 0xb7]사이의 값을 가진다.
파이썬 예제
>>rlp.encode(“ab”)
# 리턴값 b'\x82ab', 0x80 + 문자열길이 2 = 0x82에다가 a와 b 각각을 붙임
>>rlp.encode(“ab”).hex()
#리턴값 '826162', 8+2+a의 아스키값(61), b의 아스키값(62)
>>rlp.encode(“hello”) # 리턴값 b'\x85hello' 0x80+문자열길이(5), 거기에 h+e+l+l+o 붙임
RLP Definition - 이더리움 위키 정의
3. 만약 문자열의 길이가 55 bytes를넘어간다면, 0xb7에 길이값의 바이트값을 더하고, 길이의 바이트값을 붙인 뒤에, 문자열의 바이트를 붙인다.
“..뭐지?” 싶지만, 파이썬 예제를 보면 쉽다.
>>rlp.encode(“a”*1024) #1024자리의 문자열을 인코딩하면
# 리턴값 <b'\xb9\x04\x00aaaa….a가 2014개 >
#설명하자면, 1024를 바이트로 표현하면, <0x04> <0x00> 2바이트로 표현된다.
#따라서 <0xb7 + 0x02> 뒤에 0x04 0x00을 붙이면 → 0xb9 0x04 0x00 → 위의 <> 앞자리와 같음
#빨간색은 0xb7에 2를 더한것이고(길이가 2바이트로 표현되었기 때문)
#파란색은 1024를 바이트로 표현한 것이다.(1024 → 0x04 0x00)
#그 뒤에 a를 1024개 붙이면 끝
문제
>>rlp.encode(“a”*91)은? #파이썬 바이너리 표현식으로 나옴, 조심
RLP Definition - 이더리움 위키 정의
4.만약 배열의 모든 아이템들이 RLP인코딩된 값들의 길이가 55보다 작다면, 0xc0에 아이템들을 각각 RLP인코딩한 값들의 길이를 더하고, 각각의 아이템의 인코딩한 값들을 붙인다. 따라서 첫 바이트의 값은 [0xc0, 0xf7] 사이의 값을 가진다.
음..ㅎ 파이썬 예제를 보자
>>rlp.encode([“ab”]) #리턴값은 b'\xc3\x82ab', “ab”를 RLP인코딩하면, 0x82 a b 가 되고(rlp definition 1 참조), 이는 3자리 이므로, 0xc0+3 = 0xc3, 따라서 최종 값은 <0xc3 0x82 a b> → b'\xc3\x82ab'
>>rlp.encode([“ab”,”dc”]) #리턴값은 b'\xc6\x82ab\x82ab'
#ab를 인코딩하면 0x82 a b, “dc”를 인코딩하면 0x82 d c, 둘의 길이를 합치면 6 따라서
#0xc0+6 뒤에 0x82 a b, 0x82 d c → b'\xc6\x82ab\x82ab'
문제) rlp.encode([“adb”, 0x11])은 무슨 값으로 시작할까?
보기 : (1) 0xc3 (2)0xc4 (3)0xc5 (4)0x84 (5)0x85
RLP Definition - 이더리움 위키 정의
5.만약 배열의 모든 아이템들이 RLP인코딩된 값들의 길이가 55보다 크다면, 0xf7에 아이템들을 각각 RLP인코딩한 값들의 길이를 표현한 값의 길
붙인다. 따라서 첫 바이트의 값의 범위는 [0xc7, 0xff]가 된다.
파이썬 예제
>>rlp.encode([“a”*50, “a”*50])
# 리턴값 b'\xf8f\xb8da...a50개0xb2a...a50개'
# “a”*50를 인코딩하면 0x80 + 0x32(50개이므로)에다가 a50개를 붙이면 된다. 0xb2a...a50개, 총 51자리가 나옴.
# 똑같은게 2개가 있으니 아이템들의 rlp 인코딩 길이는 51*2 = 102, 핵스로 바꾸면 0x66, 1자리로 표현됨
# 따라서 0xf7+1 = 0xf8, 여기에 아이템들의 길이값인 102 → 0x66 → f(0x66은 아스키 문자 f로 바뀐다), 뒤에 아이템2개 붙임
# 결론적으로 <0xf8> <f> <0xb2a..a50개> <0xb2a..a50개> → b'\xf8f\xb8da...a50개0xb2a...a50개' 가 된다.
문제 : rlp.encode([["a"*54],["bcd"]])를 인코딩하면 첫번째 바이트는 무엇일까?
RLP Definition - 이더리움 위키 정의
6.배열에 관한 여러지가 예제 모음
파이썬 예제를 보자
>>rlp.encode([]) #리턴값 b'\xc0'
>>rlp.encode([‘’]) #리턴값 b'\xc1\x80'
>>rlp.encode([ [""],["abc"],[["bcd"], "ab", ""] ]) #b'\xd1\xc1\x80\xc4\x83abc\xc9\xc4\x83bcd\x82ab\x80'
>>rlp.encode([ [], [[]], [ [], [[]] ] ]) #b'\xc7\xc0\xc1\xc0\xc3\xc0\xc1\xc0', 자연수 3을 폰 노이만 서수 집합으로 표기한 것과 같다.
인코딩 코드(파이썬 구현)
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)
디코딩(decoding)
디코딩(Decoding)이란?
인코딩(encoding)의 역순(분해는 조립의 역순, 조립은 분해의 역순이다ㅋ)
RLP 디코딩 과정
RLP 디코딩 세부 로직
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(input, offset, dataLen))� output + rlp_decode(substr(input, offset + dataLen))� return output��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
def decode_length(input):� length = len(input)� if length == 0:� raise Exception("input is null")� prefix = ord(input[0])� if prefix <= 0x7f:� 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 - 0xb7 + to_integer(substr(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 - 0xc0:� 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 - 0xf7� listLen = to_integer(substr(input, 1, lenOfListLen))� return (1 + lenOfListLen, listLen, list)� else:� raise Exception("input don't conform RLP encoding form")
pyrlp 라이브러리
pyrlp 설치
$git clone https://github.com/ethereum/pyrlp.git
$cd pyrlp
$python3 setup.py install
quickstart1
>>import rlp
>>rlp.encode(12345)#12345를 인코딩한다
b'\x8209'
>>rlp.decode(b'\x8209', rlp.sedes.big_endian_int) #big endian을 안바꾸면 b'09'가 리턴됨.
12345
>>rlp.encode([1, [2, []]])
b'\xc4\x01\xc2\x02\xc0'
>>rlp.decode(b'\xc4\x01\xc2\x02\xc0')
[b'\x01', [b'\x02', []]] #각각의 값이 binary로 나온다.
quickstart2
소스코드 : https://gist.github.com/ggs134/a736d5364f84d291b60800cb7b13dd2f
다양한 구현체
참고자료 및 출처