রিকার্সিভ-লেংথ প্রিফিক্স (⁨RLP⁩) সিরিয়ালাইজেশন

রিকার্সিভ লেংথ প্রিফিক্স (RLP) সিরিয়ালাইজেশন ইথেরিয়ামের এক্সিকিউশন ক্লায়েন্টগুলোতে ব্যাপকভাবে ব্যবহৃত হয়। RLP একটি স্পেস-এফিশিয়েন্ট ফর্ম্যাটে নোডগুলোর মধ্যে ডেটা হস্তান্তর প্রমিত করে। RLP-এর উদ্দেশ্য হলো বাইনারি ডেটার ইচ্ছামতো নেস্টেড অ্যারেকে এনকোড করা, এবং ইথেরিয়ামের এক্সিকিউশন লেয়ারে অবজেক্টগুলোকে সিরিয়ালাইজেশন করার জন্য ব্যবহৃত প্রাথমিক এনকোডিং পদ্ধতি হলো RLP। RLP-এর মূল উদ্দেশ্য হলো স্ট্রাকচার এনকোড করা; ধনাত্মক পূর্ণসংখ্যা (positive integers) ব্যতীত, RLP নির্দিষ্ট ডেটা টাইপ (যেমন, স্ট্রিং, ফ্লোট) এনকোড করার দায়িত্ব উচ্চ-স্তরের প্রোটোকলগুলোর ওপর ছেড়ে দেয়। ধনাত্মক পূর্ণসংখ্যাগুলোকে কোনো লিডিং জিরো (leading zeroes) ছাড়াই বিগ-এন্ডিয়ান বাইনারি ফর্মে উপস্থাপন করতে হবে (যার ফলে শূন্য পূর্ণসংখ্যার মান খালি বাইট অ্যারের সমতুল্য হয়)। 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 এনকোডিংয়ের কনক্যাটেনেশন (concatenation) বসে। প্রথম বাইটের রেঞ্জ তাই [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] হয়, তবে ডেটাটি একটি তালিকা, এবং তালিকার সমস্ত আইটেমের 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 (opens in a new tab)
• ইথেরিয়ামের ভেতরে: RLP (opens in a new tab)
• Coglio, A. (2020). Ethereum's Recursive Length Prefix in ACL2. arXiv preprint arXiv:2009.13769. (opens in a new tab)

সম্পর্কিত বিষয়

• প্যাট্রিসিয়া মার্কেল ট্রাই