रिकर्सिव-लेंथ प्रीफिक्स (⁨RLP⁩) क्रमांकन

रिकर्सिव लेंथ प्रीफिक्स (RLP) क्रमांकन का उपयोग इथेरियम के निष्पादन क्लाइंट्स में बड़े पैमाने पर किया जाता है। RLP एक स्पेस-एफिशिएंट (स्थान-कुशल) प्रारूप में नोड्स के बीच डेटा के ट्रांसफर को मानकीकृत करता है। RLP का उद्देश्य बाइनरी डेटा के मनमाने ढंग से नेस्टेड एरेज़ को एन्कोड करना है, और RLP इथेरियम की निष्पादन परत में ऑब्जेक्ट्स को क्रमबद्ध (serialize) करने के लिए उपयोग की जाने वाली प्राथमिक एन्कोडिंग विधि है। RLP का मुख्य उद्देश्य संरचना को एन्कोड करना है; धनात्मक पूर्णांकों (positive integers) के अपवाद के साथ, RLP विशिष्ट डेटा प्रकारों (जैसे, स्ट्रिंग्स, फ्लोट्स) को एन्कोड करने का काम उच्च-क्रम (higher-order) प्रोटोकॉल को सौंपता है। धनात्मक पूर्णांकों को बिना किसी लीडिंग शून्य (leading zeroes) के बिग-एंडियन बाइनरी रूप में दर्शाया जाना चाहिए (इस प्रकार पूर्णांक मान शून्य को खाली बाइट एरे के बराबर बना दिया जाता है)। RLP का उपयोग करने वाले किसी भी उच्च-क्रम प्रोटोकॉल द्वारा लीडिंग शून्य वाले डिसीरियलाइज़्ड (deserialized) धनात्मक पूर्णांकों को अमान्य माना जाना चाहिए।

इथेरियम येलो पेपर (परिशिष्ट B) (एक नए टैब में खुलता है) में अधिक जानकारी।

डिक्शनरी को एन्कोड करने के लिए RLP का उपयोग करने हेतु, दो सुझाए गए विहित (canonical) रूप हैं:

• लेक्सिकोग्राफिक (शब्दकोशीय) क्रम में कुंजियों (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 एन्कोडिंग्स का संयोजन (concatenation) आता है। इस प्रकार पहले बाइट की रेंज [0xc0, 0xf7] (दशमलव [192, 247]) होती है।
• यदि किसी सूची का कुल पेलोड 55 बाइट्स से अधिक लंबा है, तो RLP एन्कोडिंग में 0xf7 मान वाला एक सिंगल बाइट और बाइनरी रूप में पेलोड की लंबाई की बाइट्स में लंबाई शामिल होती है, जिसके बाद पेलोड की लंबाई और फिर आइटम्स की RLP एन्कोडिंग्स का संयोजन आता है। इस प्रकार पहले बाइट की रेंज [0xf8, 0xff] (दशमलव [248, 255]) होती है।

संक्षिप्त रूप में:

• p = पेलोड
• n = लंबाई (पेलोड बाइट्स की संख्या)
• N = लंबाई-की-लंबाई (len-of-len) ऑफ़सेट (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 ]
• तीन का सेट सैद्धांतिक प्रतिनिधित्व (set theoretical representation) (एक नए टैब में खुलता है), [ [], [[]], [ [], [[]] ] ] = [ 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] है, और सूची के सभी आइटम्स की RLP एन्कोडिंग्स का संयोजन जिसका कुल पेलोड पहले बाइट माइनस 0xc0 के बराबर है, पहले बाइट के बाद आता है;

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 (एक नए टैब में खुलता है)
• इथेरियम तकनीकी रूप से कैसे काम करता है (under the hood): RLP (एक नए टैब में खुलता है)
• कोग्लियो, ए. (2020). ACL2 में इथेरियम का रिकर्सिव लेंथ प्रीफिक्स। arXiv प्रीप्रिंट arXiv:2009.13769. (एक नए टैब में खुलता है)

संबंधित विषय

• पेट्रीसिया मर्कल ट्राई (Patricia merkle trie)