रिकर्सिव्ह-लेंग्थ प्रीफिक्स (RLP) क्रमिकरण

इथेरियमच्या अंमलबजावणी क्लायंट्समध्ये रिकर्सिव्ह लेंग्थ प्रीफिक्स (RLP) क्रमिकरणाचा मोठ्या प्रमाणावर वापर केला जातो. RLP नोड्समधील डेटाचे हस्तांतरण एका स्पेस-इफिशिएंट (जागेची बचत करणाऱ्या) फॉरमॅटमध्ये प्रमाणित करते. बायनरी डेटाच्या अनियंत्रितपणे नेस्टेड अ‍ॅरेला एन्कोड करणे हा RLP चा उद्देश आहे आणि इथेरियमच्या अंमलबजावणी स्तरामध्ये ऑब्जेक्ट्सचे क्रमिकरण करण्यासाठी वापरली जाणारी RLP ही प्राथमिक एन्कोडिंग पद्धत आहे. RLP चा मुख्य उद्देश स्ट्रक्चर एन्कोड करणे हा आहे; धन पूर्णांक (positive integers) वगळता, RLP विशिष्ट डेटा प्रकार (उदा. स्ट्रिंग्स, फ्लोट्स) एन्कोड करण्याचे काम उच्च-स्तरीय प्रोटोकॉल्सकडे सोपवते. धन पूर्णांक हे बिग-एन्डियन बायनरी स्वरूपात दर्शविले जाणे आवश्यक आहे ज्यामध्ये कोणतेही लीडिंग झिरो (सुरुवातीचे शून्य) नसतात (अशा प्रकारे शून्य हे पूर्णांक मूल्य रिकाम्या बाइट अ‍ॅरेच्या समतुल्य बनते). RLP वापरणाऱ्या कोणत्याही उच्च-स्तरीय प्रोटोकॉलद्वारे लीडिंग झिरो असलेल्या डीसीरियलाइज्ड धन पूर्णांकांना अवैध मानले जाणे आवश्यक आहे.

अधिक माहिती इथेरियम येलो पेपर (परिशिष्ट B) (opens in a new tab) मध्ये आहे.

डिक्शनरी एन्कोड करण्यासाठी RLP वापरताना, सुचविलेले दोन कॅनोनिकल फॉर्म्स खालीलप्रमाणे आहेत:

• लेक्सिकोग्राफिक क्रमाने कीज (keys) सोबत [[k1,v1],[k2,v2]...] वापरा
• इथेरियम प्रमाणे उच्च-स्तरीय पॅट्रिशिया ट्री (Patricia Tree) एन्कोडिंग वापरा

व्याख्या

RLP एन्कोडिंग फंक्शन एक आयटम घेते. आयटमची व्याख्या खालीलप्रमाणे केली जाते:

• स्ट्रिंग (म्हणजेच, बाइट अ‍ॅरे) हा एक आयटम आहे
• आयटम्सची यादी हा एक आयटम आहे
• धन पूर्णांक हा एक आयटम आहे

उदाहरणार्थ, खालील सर्व आयटम्स आहेत:

• एक रिकामी स्ट्रिंग;
• "cat" शब्द असलेली स्ट्रिंग;
• कोणत्याही संख्येने स्ट्रिंग्स असलेली यादी;
• आणि ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"] सारखे अधिक गुंतागुंतीचे डेटा स्ट्रक्चर्स.
• 100 हा क्रमांक

लक्षात घ्या की या उर्वरित पृष्ठाच्या संदर्भात, 'स्ट्रिंग' म्हणजे "बायनरी डेटाच्या बाइट्सची ठराविक संख्या"; कोणतेही विशेष एन्कोडिंग्स वापरले जात नाहीत, आणि स्ट्रिंग्सच्या सामग्रीबद्दल कोणतेही ज्ञान सूचित केले जात नाही (नॉन-मिनिमल धन पूर्णांकांविरूद्धच्या नियमानुसार आवश्यक असल्याशिवाय).

RLP एन्कोडिंगची व्याख्या खालीलप्रमाणे केली जाते:

• धन पूर्णांकासाठी, तो सर्वात लहान बाइट अ‍ॅरेमध्ये रूपांतरित केला जातो ज्याचे बिग-एन्डियन इंटरप्रिटेशन तो पूर्णांक असतो, आणि नंतर खालील नियमांनुसार स्ट्रिंग म्हणून एन्कोड केला जातो.
• ज्या सिंगल बाइटचे मूल्य [0x00, 0x7f] (दशांश [0, 127]) श्रेणीत आहे, तो बाइट स्वतःच त्याचे RLP एन्कोडिंग असतो.
• अन्यथा, जर स्ट्रिंग 0-55 बाइट्स लांब असेल, तर RLP एन्कोडिंगमध्ये 0x80 (दशांश 128) मूल्य असलेला एक सिंगल बाइट अधिक स्ट्रिंगची लांबी आणि त्यानंतर ती स्ट्रिंग असते. अशा प्रकारे पहिल्या बाइटची श्रेणी [0x80, 0xb7] (दशांश [128, 183]) असते.
• जर स्ट्रिंग 55 बाइट्सपेक्षा जास्त लांब असेल, तर RLP एन्कोडिंगमध्ये 0xb7 (दशांश 183) मूल्य असलेला एक सिंगल बाइट अधिक बायनरी स्वरूपातील स्ट्रिंगच्या लांबीची बाइट्समधील लांबी, त्यानंतर स्ट्रिंगची लांबी, आणि त्यानंतर ती स्ट्रिंग असते. उदाहरणार्थ, 1024 बाइट लांब स्ट्रिंग \xb9\x04\x00 (दशांश 185, 4, 0) आणि त्यानंतर ती स्ट्रिंग म्हणून एन्कोड केली जाईल. येथे, 0xb9 (183 + 2 = 185) हा पहिला बाइट म्हणून, त्यानंतर 2 बाइट्स 0x0400 (दशांश 1024) जे प्रत्यक्ष स्ट्रिंगची लांबी दर्शवतात. अशा प्रकारे पहिल्या बाइटची श्रेणी [0xb8, 0xbf] (दशांश [184, 191]) असते.
• जर स्ट्रिंग 2^64 बाइट्स लांब किंवा त्याहून अधिक लांब असेल, तर ती एन्कोड केली जाऊ शकत नाही.
• जर यादीचा एकूण पेलोड (म्हणजेच, RLP एन्कोड केल्या जाणाऱ्या त्याच्या सर्व आयटम्सची एकत्रित लांबी) 0-55 बाइट्स लांब असेल, तर RLP एन्कोडिंगमध्ये 0xc0 मूल्य असलेला एक सिंगल बाइट अधिक पेलोडची लांबी आणि त्यानंतर आयटम्सच्या RLP एन्कोडिंग्सचे कॉनकेटिनेशन (एकत्रीकरण) असते. अशा प्रकारे पहिल्या बाइटची श्रेणी [0xc0, 0xf7] (दशांश [192, 247]) असते.
• जर यादीचा एकूण पेलोड 55 बाइट्सपेक्षा जास्त लांब असेल, तर RLP एन्कोडिंगमध्ये 0xf7 मूल्य असलेला एक सिंगल बाइट अधिक बायनरी स्वरूपातील पेलोडच्या लांबीची बाइट्समधील लांबी, त्यानंतर पेलोडची लांबी, आणि त्यानंतर आयटम्सच्या RLP एन्कोडिंग्सचे कॉनकेटिनेशन असते. अशा प्रकारे पहिल्या बाइटची श्रेणी [0xf8, 0xff] (दशांश [248, 255]) असते.

थोडक्यात सांगायचे तर:

• p = पेलोड
• n = लांबी (पेलोड बाइट्सची संख्या)
• N = लांबीच्या-लांबीचा ऑफसेट (N+1 n बाइट्स पुढे येतात)

कोडमध्ये, हे असे आहे:

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        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
    raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    return to_binary(int(x / 256)) + chr(x % 256)

उदाहरणे

• "dog" ही स्ट्रिंग = [ 0x83, 'd', 'o', 'g' ]
• [ "cat", "dog" ] ही यादी = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
• रिकामी स्ट्रिंग ('null') = [ 0x80 ]
• रिकामी यादी = [ 0xc0 ]
• 0 हा पूर्णांक = [ 0x80 ]
• '\x00' हा बाइट = [ 0x00 ]
• '\x0f' हा बाइट = [ 0x0f ]
• '\x04\x00' हे बाइट्स = [ 0x82, 0x04, 0x00 ]
• तीनचे सेट थिओरेटिकल रिप्रेझेंटेशन (opens in a new tab), [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
• "Lorem ipsum dolor sit amet, consectetur adipisicing elit" ही स्ट्रिंग = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

RLP डिकोडिंग

RLP एन्कोडिंगचे नियम आणि प्रक्रियेनुसार, RLP डिकोडचे इनपुट बायनरी डेटाचा अ‍ॅरे मानले जाते. RLP डिकोडिंग प्रक्रिया खालीलप्रमाणे आहे:

1. इनपुट डेटाच्या पहिल्या बाइटनुसार (म्हणजेच, प्रीफिक्स) आणि डेटा प्रकार डिकोड करून, प्रत्यक्ष डेटाची लांबी आणि ऑफसेट;

2. डेटाचा प्रकार आणि ऑफसेटनूसार, धन पूर्णांकांसाठी किमान एन्कोडिंग नियमाचा आदर करून, डेटा त्यानुसार डिकोड करा;

3. उर्वरित इनपुट डिकोड करणे सुरू ठेवा;

त्यापैकी, डेटा प्रकार आणि ऑफसेट डिकोड करण्याचे नियम खालीलप्रमाणे आहेत:

1. जर पहिल्या बाइटची (म्हणजेच, प्रीफिक्स) श्रेणी [0x00, 0x7f] असेल तर डेटा एक स्ट्रिंग असतो, आणि ती स्ट्रिंग तंतोतंत पहिला बाइटच असते;

2. जर पहिल्या बाइटची श्रेणी [0x80, 0xb7] असेल तर डेटा एक स्ट्रिंग असतो, आणि ज्या स्ट्रिंगची लांबी पहिल्या बाइटमधून 0x80 वजा केल्यावर येणाऱ्या संख्येइतकी असते ती पहिल्या बाइटनंतर येते;

3. जर पहिल्या बाइटची श्रेणी [0xb8, 0xbf] असेल तर डेटा एक स्ट्रिंग असतो, आणि ज्या स्ट्रिंगची बाइट्समधील लांबी पहिल्या बाइटमधून 0xb7 वजा केल्यावर येणाऱ्या संख्येइतकी असते ती लांबी पहिल्या बाइटनंतर येते, आणि स्ट्रिंग त्या स्ट्रिंगच्या लांबीनंतर येते;

4. जर पहिल्या बाइटची श्रेणी [0xc0, 0xf7] असेल तर डेटा एक यादी असतो, आणि ज्या यादीचा एकूण पेलोड पहिल्या बाइटमधून 0xc0 वजा केल्यावर येणाऱ्या संख्येइतका असतो त्या यादीतील सर्व आयटम्सच्या RLP एन्कोडिंग्सचे कॉनकेटिनेशन पहिल्या बाइटनंतर येते;

5. जर पहिल्या बाइटची श्रेणी [0xf8, 0xff] असेल तर डेटा एक यादी असतो, आणि ज्या यादीच्या एकूण पेलोडची लांबी पहिल्या बाइटमधून 0xf7 वजा केल्यावर येणाऱ्या संख्येइतकी असते तो पेलोड पहिल्या बाइटनंतर येतो, आणि यादीतील सर्व आयटम्सच्या 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 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)
    raise Exception("input does not conform to 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])
    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

पुढील वाचन

• इथेरियममध्ये RLP (opens in a new tab)
• इथेरियम अंडर द हूड: RLP (opens in a new tab)
• कोग्लिओ, ए. (2020). इथेरियम्स रिकर्सिव्ह लेंग्थ प्रीफिक्स इन ACL2. arXiv प्रीप्रिंट arXiv:2009.13769. (opens in a new tab)

संबंधित विषय

• पॅट्रिशिया मर्कल ट्री (Patricia merkle trie)