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

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

هيكل بيانات إيثريوم هو 'Merkle-Patricia Trie المعدلة'، وقد سُميت بذلك لأنها تستعير بعض ميزات PATRICIA (الخوارزمية العملية لاسترداد المعلومات المشفرة في صيغة أبجدية رقمية)، ولأنها مصممة لاسترداد البيانات بكفاءة للعناصر التي تشكل حالة إيثريوم.

إن شجرة Merkle-Patricia trie حتمية وقابلة للتحقق تشفيريًا: الطريقة الوحيدة لإنشاء جذر حالة هي عن طريق حسابه من كل جزء فردي من الحالة، ويمكن إثبات تطابق حالتين بسهولة من خلال مقارنة التجزئة (هاش) الجذرية والتجزئات (هاشات) التي أدت إليها (إثبات ميركل). وعلى العكس من ذلك، لا توجد طريقة لإنشاء حالتين مختلفتين بنفس تجزئة الجذر، وأي محاولة لتعديل الحالة بقيم مختلفة ستؤدي إلى تجزئة جذر حالة مختلفة. من الناحية النظرية، يوفر هذا الهيكل 'الكأس المقدسة' لكفاءة 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) الأساسية، ثم تقدم تدريجيًا التعديلات اللازمة لهيكل بيانات إيثريوم الأكثر تحسينًا.

أشجار الأساس التفرعية الأساسية

في مخطط الأساس الأساسي، تبدو كل عقدة على النحو التالي:

1    [i_0, i_1 ... i_n, value]

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

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

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

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

1    def update(node_hash, path, value):
2        curnode = db.get(node_hash) if node_hash else [NULL] * 17
3        newnode = curnode.copy()
4        if path == "":
5            newnode[-1] = value
6        else:
7            newindex = update(curnode[path[0]], path[1:], value)
8            newnode[path[0]] = newindex
9        db.put(hash(newnode), newnode)
10        return hash(newnode)
11
12    def delete(node_hash, path):
13        if node_hash is NULL:
14            return NULL
15        else:
16            curnode = db.get(node_hash)
17            newnode = curnode.copy()
18            if path == "":
19                newnode[-1] = NULL
20            else:
21                newindex = delete(curnode[path[0]], path[1:])
22                newnode[path[0]] = newindex
23
24            if all(x is NULL for x in newnode):
25                return NULL
26            else:
27                db.put(hash(newnode), newnode)
28                return hash(newnode)
إظهار الكل

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

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

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

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

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

التحسين

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

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

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

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

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

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

المواصفات: ترميز مضغوط لتسلسل سداسي عشري مع محرف إنهاء اختياري

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

حرف سداسي عشري	أجزاء	نوع العقدة جزئي	طول المسار
0	0000	امتداد	حتى
١	واحد	امتداد	غريب
2	عشرة	إنهاء (ورقة)	حتى
3	إحدى عشر	إنهاء (ورقة)	غريب

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

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # أصبح للمصفوفة السداسية الآن طول زوجي وأول نصف بايت (nibble) لها هو الأعلام.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        return o
إظهار الكل

أمثلة:

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

هذا هو الكود الموسع للحصول على عقدة في Merkle Patricia trie:

1    def get_helper(node_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
إظهار الكل

مثال على الشجرة التفرعية

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

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

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

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

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

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

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

الأشجار التفرعية في إيثريوم

تستخدم جميع محاولات merkle في طبقة تنفيذ إيثريوم Merkle Patricia Trie.

من رأس الكتلة يوجد 3 جذور من 3 من هذه المحاولات.

StateRoot
TransactionRoot
إيصالاتRoot

شجرة الحالة التفرعية

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

شجرة التخزين التفرعية

شجرة التخزين التفرعية هي المكان الذي توجد فيه جميع بيانات العقود. هناك مساحة تخزين منفصلة لكل حساب. لاسترجاع القيم في مواضع تخزين محددة عند عنوان معين، يلزم وجود عنوان التخزين، وموضع عدد صحيح للبيانات المخزنة في التخزين، ومعرف الكتلة. يمكن بعد ذلك تمرير هذه كوسائط إلى eth_getStorageAt المحددة في واجهة برمجة تطبيقات JSON-RPC، على سبيل المثال، لاسترداد البيانات في خانة التخزين 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 هو:

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

في وحدة التحكم غيث، يمكن حساب ذلك على النحو التالي:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"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) الذي يمثل المفتاح الذي يتوافق مع القيمة المحددة بواسطة:

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

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

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

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