التسلسل ببادئة الطول العودية (⁦RLP⁩)

يُستخدم التسلسل ببادئة الطول العودية (RLP) على نطاق واسع في عملاء التنفيذ الخاصة بإيثيريوم. يوحد RLP تحويل البيانات بين العقد بتنسيق موفر للمساحة. الغرض من RLP هو تشفير مصفوفات متداخلة بشكل عشوائي من البيانات الثنائية، ويُعد RLP طريقة التشفير الأساسية المستخدمة لتسلسل الكائنات في طبقة التنفيذ الخاصة بإيثيريوم. الغرض الرئيسي من RLP هو تشفير البنية؛ وباستثناء الأعداد الصحيحة الموجبة، يفوض RLP تشفير أنواع بيانات محددة (مثل السلاسل النصية والأرقام العشرية) إلى بروتوكولات ذات ترتيب أعلى. يجب تمثيل الأعداد الصحيحة الموجبة بصيغة ثنائية بنظام النهاية الكبرى بدون أصفار بادئة (مما يجعل قيمة العدد الصحيح صفرًا مكافئة لمصفوفة البايتات الفارغة). يجب أن تُعامل الأعداد الصحيحة الموجبة التي تم إلغاء تسلسلها وتحتوي على أصفار بادئة على أنها غير صالحة بواسطة أي بروتوكول ذي ترتيب أعلى يستخدم RLP.

مزيد من المعلومات في الورقة الصفراء لإيثيريوم (الملحق ب) (opens in a new tab).

لاستخدام RLP لتشفير قاموس، فإن الصيغتين الأساسيتين المقترحتين هما:

• استخدام [[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) كبايت أول، متبوعًا بالبايتين 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]، وتسلسل تشفيرات 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)

مواضيع ذات صلة

• شجرة باتريشيا ميركل (Patricia merkle trie)