شجرة ميركل باتريشيا

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

بنية بيانات إيثيريوم هي "شجرة ميركل باتريشيا معدلة"، وسميت كذلك لأنها تستعير بعض ميزات PATRICIA (الخوارزمية العملية لاسترجاع المعلومات المشفرة أبجديًا ورقميًا)، ولأنها مصممة لاسترجاع البيانات بكفاءة للعناصر التي تتكون منها حالة إيثيريوم.

شجرة ميركل باتريشيا حتمية وقابلة للتحقق باستخدام علم التشفير: الطريقة الوحيدة لإنشاء جذر حالة هي حسابه من كل جزء فردي من الحالة، ويمكن إثبات تطابق حالتين بسهولة من خلال مقارنة تجزئة الجذر والتجزئات التي أدت إليه (إثبات ميركل). على العكس من ذلك، لا توجد طريقة لإنشاء حالتين مختلفتين بنفس تجزئة الجذر، وأي محاولة لتعديل الحالة بقيم مختلفة ستؤدي إلى تجزئة جذر حالة مختلفة. من الناحية النظرية، توفر هذه البنية "الهدف الأسمى" المتمثل في كفاءة O(log(n)) لعمليات الإدراج والبحث والحذف.

في المستقبل القريب، تخطط إيثيريوم للانتقال إلى بنية شجرة فيركل (Verkle Tree)، مما سيفتح العديد من الاحتمالات الجديدة لتحسينات البروتوكول المستقبلية.

المتطلبات الأساسية

لفهم هذه الصفحة بشكل أفضل، سيكون من المفيد أن يكون لديك معرفة أساسية عن التجزئات (opens in a new tab)، وأشجار ميركل (opens in a new tab)، وأشجار التراي (tries) (opens in a new tab)، والتسلسل (opens in a new tab). تبدأ هذه المقالة بوصف شجرة الجذر (radix tree) (opens in a new tab) الأساسية، ثم تقدم تدريجيًا التعديلات اللازمة لبنية بيانات إيثيريوم الأكثر تحسينًا.

أشجار الجذر الأساسية (Basic radix tries)

في شجرة الجذر الأساسية، تبدو كل عقدة كما يلي:

[i_0, i_1 ... i_n, value]

حيث تمثل i_0 ... i_n رموز الأبجدية (غالبًا ثنائية أو سداسية عشرية)، وvalue هي القيمة النهائية عند العقدة، والقيم في خانات i_0, i_1 ... i_n هي إما NULL أو مؤشرات إلى (في حالتنا، تجزئات) عقد أخرى. يشكل هذا مخزن (key, value) أساسي.

لنفترض أنك أردت استخدام بنية بيانات شجرة الجذر للحفاظ على ترتيب عبر مجموعة من أزواج القيمة والمفتاح. للعثور على القيمة المعينة حاليًا للمفتاح dog في الشجرة، ستقوم أولاً بتحويل dog إلى أحرف أبجدية (مما يعطي 64 6f 67)، ثم تنزل في الشجرة متبعًا هذا المسار حتى تجد القيمة. أي أنك تبدأ بالبحث عن تجزئة الجذر في قاعدة بيانات مسطحة للقيمة/المفتاح للعثور على العقدة الجذرية للشجرة. يتم تمثيلها كمصفوفة من المفاتيح التي تشير إلى عقد أخرى. ستستخدم القيمة عند المؤشر 6 كمفتاح وتبحث عنها في قاعدة بيانات القيمة/المفتاح المسطحة للحصول على العقدة في المستوى التالي لأسفل. ثم اختر المؤشر 4 للبحث عن القيمة التالية، ثم اختر المؤشر 6، وهكذا، حتى تتبع المسار: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7، ستبحث عن قيمة العقدة وترجع النتيجة.

هناك فرق بين البحث عن شيء ما في "الشجرة" وقاعدة بيانات القيمة/المفتاح المسطحة الأساسية. كلاهما يحدد ترتيبات القيمة/المفتاح، ولكن يمكن لقاعدة البيانات الأساسية إجراء بحث تقليدي بخطوة واحدة عن مفتاح. يتطلب البحث عن مفتاح في الشجرة عمليات بحث متعددة في قاعدة البيانات الأساسية للوصول إلى القيمة النهائية الموضحة أعلاه. دعنا نشير إلى الأخير باسم path لإزالة الغموض.

يمكن تعريف عمليات التحديث والحذف لأشجار الجذر على النحو التالي:

    def update(node_hash, path, value):
        curnode = db.get(node_hash) if node_hash else [NULL] * 17
        newnode = curnode.copy()
        if path == "":
            newnode[-1] = value
        else:
            newindex = update(curnode[path[0]], path[1:], value)
            newnode[path[0]] = newindex
        db.put(hash(newnode), newnode)
        return hash(newnode)

    def delete(node_hash, path):
        if node_hash is NULL:
            return NULL
        else:
            curnode = db.get(node_hash)
            newnode = curnode.copy()
            if path == "":
                newnode[-1] = NULL
            else:
                newindex = delete(curnode[path[0]], path[1:])
                newnode[path[0]] = newindex

            if all(x is NULL for x in newnode):
                return NULL
            else:
                db.put(hash(newnode), newnode)
                return hash(newnode)

يتم بناء شجرة جذر "ميركل" عن طريق ربط العقد باستخدام ملخصات تجزئة تشفيرية يتم إنشاؤها بشكل حتمي. توفر عنونة المحتوى هذه (في قاعدة بيانات القيمة/المفتاح key == keccak256(rlp(value))) ضمانًا لسلامة التشفير للبيانات المخزنة. إذا كانت تجزئة الجذر لشجرة معينة معروفة للجمهور، فيمكن لأي شخص لديه وصول إلى بيانات الورقة الأساسية إنشاء إثبات بأن الشجرة تتضمن قيمة معينة في مسار محدد من خلال توفير تجزئات كل عقدة تربط قيمة معينة بجذر الشجرة.

من المستحيل على المهاجم تقديم إثبات لزوج (path, value) غير موجود لأن تجزئة الجذر تعتمد في النهاية على جميع التجزئات الموجودة أسفلها. أي تعديل أساسي سيغير تجزئة الجذر. يمكنك التفكير في التجزئة كتمثيل مضغوط للمعلومات الهيكلية حول البيانات، ومؤمنة بواسطة حماية الصورة المسبقة لوظيفة عملية التجزئة.

سنشير إلى الوحدة الذرية لشجرة الجذر (على سبيل المثال، حرف سداسي عشري واحد، أو رقم ثنائي مكون من 4 بت) باسم "نصف بايت" (nibble). أثناء اجتياز مسار بمقدار نصف بايت في كل مرة، كما هو موضح أعلاه، يمكن للعقد أن تشير كحد أقصى إلى 16 عقدة فرعية ولكنها تتضمن عنصر value. وبالتالي، نمثلها كمصفوفة بطول 17. نطلق على هذه المصفوفات المكونة من 17 عنصرًا اسم "عقد الفروع" (branch nodes).

شجرة ميركل باتريشيا

أشجار الجذر لها قيد رئيسي واحد: إنها غير فعالة. إذا كنت ترغب في تخزين ارتباط (path, value) واحد حيث يكون المسار، كما هو الحال في إيثيريوم، بطول 64 حرفًا (عدد أنصاف البايت في bytes32)، فسنحتاج إلى أكثر من كيلوبايت من المساحة الإضافية لتخزين مستوى واحد لكل حرف، وستستغرق كل عملية بحث أو حذف 64 خطوة كاملة. تحل شجرة باتريشيا المقدمة فيما يلي هذه المشكلة.

التحسين

العقدة في شجرة ميركل باتريشيا هي واحدة مما يلي:

1. NULL (ممثلة كسلسلة فارغة)
2. branch عقدة مكونة من 17 عنصرًا [ v0 ... v15, vt ]
3. leaf عقدة مكونة من عنصرين [ encodedPath, value ]
4. extension عقدة مكونة من عنصرين [ encodedPath, key ]

مع مسارات مكونة من 64 حرفًا، من المحتم أنه بعد اجتياز الطبقات القليلة الأولى من الشجرة، ستصل إلى عقدة لا يوجد فيها مسار متباعد لجزء على الأقل من الطريق لأسفل. لتجنب الاضطرار إلى إنشاء ما يصل إلى 15 عقدة NULL متفرقة على طول المسار، نقوم باختصار النزول عن طريق إعداد عقدة extension بالشكل [ encodedPath, key ]، حيث يحتوي encodedPath على "المسار الجزئي" للتخطي للأمام (باستخدام تشفير مضغوط موضح أدناه)، وkey مخصص للبحث التالي في قاعدة البيانات.

بالنسبة لعقدة leaf، والتي يمكن تمييزها بعلامة في أول نصف بايت من encodedPath، يقوم المسار بتشفير جميع أجزاء مسار العقدة السابقة ويمكننا البحث عن value مباشرة.

ومع ذلك، فإن هذا التحسين المذكور أعلاه يقدم بعض الغموض.

عند اجتياز المسارات بأنصاف البايت، قد ينتهي بنا الأمر بعدد فردي من أنصاف البايت لاجتيازها، ولكن لأن جميع البيانات مخزنة بتنسيق bytes. لا يمكن التمييز بين، على سبيل المثال، نصف البايت 1، وأنصاف البايت 01 (يجب تخزين كليهما كـ <01>). لتحديد الطول الفردي، يتم إضافة علامة كبادئة للمسار الجزئي.

المواصفات: التشفير المضغوط للتسلسل السداسي العشري مع فاصل اختياري

توجد علامة كل من طول المسار الجزئي المتبقي الفردي مقابل الزوجي و_عقدة الورقة مقابل عقدة الامتداد_ كما هو موضح أعلاه في أول نصف بايت من المسار الجزئي لأي عقدة مكونة من عنصرين. وتؤدي إلى ما يلي:

بالنسبة لطول المسار المتبقي الزوجي (0 أو 2)، سيتبعه دائمًا نصف بايت "حشو" 0 آخر.

    def compact_encode(hexarray):
        term = 1 if hexarray[-1] == 16 else 0
        if term:
            hexarray = hexarray[:-1]
        oddlen = len(hexarray) % 2
        flags = 2 * term + oddlen
        if oddlen:
            hexarray = [flags] + hexarray
        else:
            hexarray = [flags] + [0] + hexarray
        # أصبح لـ hexarray الآن طول زوجي، حيث يمثل النيبل الأول فيه العلامات.
        o = ""
        for i in range(0, len(hexarray), 2):
            o += chr(16 * hexarray[i] + hexarray[i + 1])
        return o

أمثلة:

    > [1, 2, 3, 4, 5, ...]
    '11 23 45'
    > [0, 1, 2, 3, 4, 5, ...]
    '00 01 23 45'
    > [0, f, 1, c, b, 8, 10]
    '20 0f 1c b8'
    > [f, 1, c, b, 8, 10]
    '3f 1c b8'

إليك الكود الموسع للحصول على عقدة في شجرة ميركل باتريشيا:

    def get_helper(node_hash, path):
        if path == []:
            return node_hash
        if node_hash == "":
            return ""
        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
        if len(curnode) == 2:
            (k2, v2) = curnode
            k2 = compact_decode(k2)
            if k2 == path[: len(k2)]:
                return get(v2, path[len(k2) :])
            else:
                return ""
        elif len(curnode) == 17:
            return get_helper(curnode[path[0]], path[1:])

    def get(node_hash, path):
        path2 = []
        for i in range(len(path)):
            path2.push(int(ord(path[i]) / 16))
            path2.push(ord(path[i]) % 16)
        path2.push(16)
        return get_helper(node_hash, path2)

مثال على شجرة (Trie)

لنفترض أننا نريد شجرة تحتوي على أربعة أزواج مسار/قيمة ('do', 'verb')، ('dog', 'puppy')، ('doge', 'coins')، ('horse', 'stallion').

أولاً، نقوم بتحويل كل من المسارات والقيم إلى bytes. أدناه، يُشار إلى تمثيلات البايت الفعلية لـ المسارات بواسطة <>، على الرغم من أن القيم لا تزال تظهر كسلاسل، يُشار إليها بواسطة ''، لتسهيل الفهم (ستكون هي أيضًا في الواقع bytes):

<64 6f> : 'verb'
    <64 6f 67> : 'puppy'
    <64 6f 67 65> : 'coins'
    <68 6f 72 73 65> : 'stallion'

الآن، نقوم ببناء مثل هذه الشجرة باستخدام أزواج القيمة/المفتاح التالية في قاعدة البيانات الأساسية:

rootHash: [ <16>, hashA ]
    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
    hashB:    [ <00 6f>, hashC ]
    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

عندما تتم الإشارة إلى عقدة داخل عقدة أخرى، فإن ما يتم تضمينه هو keccak256(rlp.encode(node))، إذا كان len(rlp.encode(node)) >= 32 وإلا node حيث rlp.encode هي وظيفة تشفير RLP.

لاحظ أنه عند تحديث شجرة، يحتاج المرء إلى تخزين زوج القيمة/المفتاح (keccak256(x), x) في جدول بحث دائم إذا كان طول العقدة المنشأة حديثًا = 32. ومع ذلك، إذا كانت العقدة أقصر من ذلك، فلا يحتاج المرء إلى تخزين أي شيء، لأن الدالة f(x) = x قابلة للعكس.

أشجار التراي (Tries) في إيثيريوم

تستخدم جميع أشجار ميركل في طبقة التنفيذ الخاصة بإيثيريوم شجرة ميركل باتريشيا.

من رأس الكتلة، هناك 3 جذور من 3 من هذه الأشجار.

1. جذر الحالة (stateRoot)
2. جذر المعاملات (transactionsRoot)
3. جذر الإيصالات (receiptsRoot)

شجرة الحالة

توجد شجرة حالة عالمية واحدة، ويتم تحديثها في كل مرة يعالج فيها العميل كتلة. فيها، يكون path دائمًا: keccak256(ethereumAddress) ويكون value دائمًا: rlp(ethereumAccount). وبشكل أكثر تحديدًا، فإن account في إيثيريوم عبارة عن مصفوفة مكونة من 4 عناصر من [nonce,balance,storageRoot,codeHash]. في هذه المرحلة، تجدر الإشارة إلى أن storageRoot هذا هو جذر شجرة باتريشيا أخرى:

تراي التخزين

تراي التخزين هو المكان الذي توجد فيه جميع بيانات العقد. يوجد تراي تخزين منفصل لكل حساب. لاسترداد القيم في مواضع تخزين محددة في عنوان معين، يلزم عنوان التخزين، والموضع الصحيح للبيانات المخزنة في التخزين، ومعرف الكتلة. يمكن بعد ذلك تمرير هذه كوسطاء إلى eth_getStorageAt المحددة في JSON-RPC API، على سبيل المثال، لاسترداد البيانات في خانة التخزين 0 للعنوان 0x295a70b2de5e3953354a6a8344e616ed314d7251:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545

{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}

يعد استرداد العناصر الأخرى في التخزين أكثر تعقيدًا بعض الشيء لأنه يجب أولاً حساب الموضع في تراي التخزين. يتم حساب الموضع على أنه تجزئة keccak256 للعنوان وموضع التخزين، وكلاهما مبطن بالأصفار من اليسار إلى طول 32 بايت. على سبيل المثال، الموضع للبيانات في خانة التخزين 1 للعنوان 0x391694e7e0b0cce554cb130d723a9d27458f9298 هو:

keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

في وحدة تحكم جو إيثريوم (geth)، يمكن حساب ذلك على النحو التالي:

> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
undefined
> web3.sha3(key, {"encoding": "hex"})
"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

وبالتالي فإن path هو keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). يمكن الآن استخدام هذا لاسترداد البيانات من تراي التخزين كما كان من قبل:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545

{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

ملاحظة: يكون storageRoot لحساب إيثيريوم فارغًا افتراضيًا إذا لم يكن حساب عقد.

شجرة المعاملات

توجد شجرة معاملات منفصلة لكل كتلة، وتقوم مرة أخرى بتخزين أزواج (key, value). المسار هنا هو: rlp(transactionIndex) والذي يمثل المفتاح الذي يتوافق مع قيمة تحددها:

if legacyTx:
  value = rlp(tx)
else:
  value = TxType | encode(tx)

يمكن العثور على مزيد من المعلومات حول هذا في وثائق EIP-2718 (opens in a new tab).

شجرة الإيصالات

كل كتلة لها شجرة إيصالات خاصة بها. path هنا هو: rlp(transactionIndex). transactionIndex هو مؤشره داخل الكتلة التي تم تضمينه فيها. لا يتم تحديث شجرة الإيصالات أبدًا. على غرار شجرة المعاملات، هناك إيصالات حالية وقديمة. للاستعلام عن إيصال معين في شجرة الإيصالات، يلزم مؤشر المعاملة في كتلتها، وحمولة الإيصال، ونوع المعاملة. يمكن أن يكون الإيصال المرتجع من النوع Receipt والذي يُعرّف بأنه تسلسل TransactionType وReceiptPayload أو يمكن أن يكون من النوع LegacyReceipt والذي يُعرّف بأنه rlp([status, cumulativeGasUsed, logsBloom, logs]).

يمكن العثور على مزيد من المعلومات حول هذا في وثائق EIP-2718 (opens in a new tab).

قراءة إضافية

• شجرة ميركل باتريشيا المعدلة — كيف تحفظ إيثيريوم الحالة (opens in a new tab)
• عملية ميركل (Merkling) في إيثيريوم (opens in a new tab)
• فهم شجرة (trie) إيثيريوم (opens in a new tab)