درخت مرکل پاتریشیا

حالت اتریوم (مجموع همه حساب‌ها، موجودی‌ها و قراردادهای هوشمند)، در نسخه خاصی از ساختار داده‌ها که عموماً در علوم کامپیوتر به عنوان درخت مرکل شناخته می‌شود، کدگذاری می‌شود. این ساختار برای بسیاری از برنامه‌های کاربردی در رمزنگاری مفید است، زیرا یک رابطه قابل تأیید بین تمام تکه‌های داده‌های درهم‌تنیده در درخت ایجاد می‌کند، که منجر به یک مقدار ریشه می‌شود که می‌تواند برای اثبات چیزهایی در مورد داده‌ها استفاده شود.

ساختار داده‌های اتریوم یک «درخت مرکل-پاتریشیا اصلاح‌شده» است که به این دلیل نام‌گذاری شده است که برخی از ویژگی‌های PATRICIA (الگوریتم عملی برای بازیابی اطلاعات کدگذاری‌شده به صورت الفبایی) را به عاریت گرفته و به این دلیل که برای بازآزمایشداده های کارآمد مواردی که حالت اتریوم را تشکیل می دهند طراحی شده است.

درخت مرکل-پاتریشیا متغیر قطعی و از نظر رمزنگاری قابل تأیید است: تنها راه برای تولید ریشه حالت، محاسبه آن از تک تک تکه های حالت است، و دو حالت یکسان را می توان به راحتی با مقایسه هش ریشه و هش هایی که منجر به آن شده‌اند ثابت کرد (اثبات مرکل). برعکس، هیچ راهی برای ایجاد دو حالت مختلف با هش ریشه یکسان وجود ندارد، و هر تلاشی برای تغییر حالت با مقادیر مختلف منجر به یک هش ریشه متفاوت خواهد شد. از نظر تئوری، این ساختار «جام مقدس» کارایی O(log(n)) را برای درج‌ها، جستجوها و حذف‌ها فراهم می‌کند.

در آینده نزدیک، اتریوم قصد دارد به ساختار Verkle Tree(opens in a new tab) مهاجرت کند، که بسیاری از فرصت‌های جدید را برای بهبود پروتکل‌های آینده باز خواهد کرد.

موارد مورد نیاز

برای درک بهتر این صفحه، داشتن دانش اولیه در مورد هش(opens in a new tab)، درخت مرکل(opens in a new tab)، درخت ها(opens in a new tab) و سریال سازی(opens in a new tab) مفید خواهد بود. این مقاله با توضیح یک درخت ریشه(opens in a new tab) اصلی آغاز می‌شود، سپس به تدریج تغییرات لازم برای ساختار داده بهینه‌تر اتریوم را معرفی می‌کند.

درخت‌های پایه رادیکس

در یک درخت پایه رادیکس، هر گره به صورت زیر به نظر می رسد:

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

در حالی که i_0 ... i_n نمادهای الفبا (اغلب باینری یا هگزا) را نشان می دهد، مقدار مقدار پایانی در گره است و مقادیر در i_0، i_1 ... i_n اسلات‌ها یا NULL یا اشاره‌گر به (در مورد ما، هش‌های) گره‌های دیگر هستند. این یک ذخیره پایه (کلید، مقدار) را تشکیل می دهد.

فرض کنید می‌خواهید از یک ساختار داده درخت رادیکس برای تداوم سفارش روی مجموعه‌ای از جفت‌های مقدار کلیدی استفاده کنید. برای یافتن مقداری که در حال حاضر به کلید dog در درخت نگاشت شده است، ابتدا dog را به حروف الفبا تبدیل کنید (به 64 6f 67 بدهید) و سپس سعی کنید در درخت پایین بیایید تا مقدار را پیدا کنید. یعنی با جستجوی هش ریشه در یک DB کلید/مقدار مسطح برای یافتن گره ریشه درخت شروع می‌کنید. این امر، به صورت آرایه ای از کلیدها نشان داده می شود که به گره های دیگر اشاره می کنند. می‌توانید از مقدار شاخص 6 به عنوان کلید استفاده کنید و آن را در کلید/مقدار مسطح DB جستجو کنید تا گره را یک سطح پایین بیاورید. سپس index 4 را برای جستجوی مقدار بعدی انتخاب کنید، سپس شاخص 6 را انتخاب کنید و به همین ترتیب، تا زمانی که مسیر را دنبال کردید: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7، شما مقدار گره را جستجو می کنید و نتیجه را نشان می‌دهید.

بین جستجوی چیزی در "درخت" و کلید/مقدار مسطح زیرین "DB" تفاوت وجود دارد. هر دو ترتیبات کلید/مقدار را تعریف می کنند، اما DB زیربنایی می تواند یک جستجوی سنتی یک مرحله ای از یک کلید را انجام دهد. جستجوی یک کلید در درخت نیاز به جستجوهای متعدد DB زیربنایی برای رسیدن به مقدار نهایی شرح داده شده در بالا دارد. اجازه دهید به دومی به عنوان مسیر برای رفع ابهام اشاره کنیم.

عملیات به روز رسانی و حذف برای درخت‌های radix را می توان به صورت زیر تعریف کرد:

1    def update(node,path,value):
2        curnode = db.get(node) if node 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,path):
13        if node is NULL:
14            return NULL
15        else:
16            curnode = db.get(node)
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)
نمایش همه

درخت ریشه «مرکل» با پیوند دادن گره‌ها با استفاده از هش رمزنگاری ایجاد شده قطعی ساخته می‌شود. این آدرس دهی محتوا (در کلید/مقدار DB key == keccak256(rlp(مقدار))) تضمین یکپارچگی رمزنگاری داده های ذخیره شده را فراهم می کند. اگر هش ریشه یک درخت داده شده به طور عمومی شناخته شده باشد، هرکسی که به داده‌های برگ زیرین دسترسی داشته باشد، می‌تواند با ارائه هش‌های هر گره که مقدار خاصی را به ریشه درخت می‌پیوندد، اثبات کند که سعی می‌کند یک مقدار معین را در یک مسیر خاص اضافه می‌کند.

برای یک مهاجم غیرممکن است که اثباتی برای یک جفت (مسیر، مقدار) ارائه دهد که وجود ندارد، زیرا هش ریشه در نهایت بر اساس همه هش های زیر آن است. هر گونه تغییر اساسی، هش ریشه را تغییر می دهد. می‌توانید هش را به‌عنوان نمایش فشرده‌ای از اطلاعات ساختاری در مورد داده‌ها در نظر بگیرید، که با محافظت پیش‌تصویر تابع درهم‌سازی ایمن شده است.

ما به یک واحد اتمی یک درخت ریشه (مثلاً یک کاراکتر هگز یا عدد باینری 4 بیتی) به عنوان "نیبل" اشاره خواهیم کرد. همانطور که در بالا توضیح داده شد، در حین پیمودن یک مسیر یک نوبت، گره‌ها می‌توانند حداکثر به 16 فرزند اشاره داشته باشند اما یک عنصر مقدار را شامل می‌شوند. بنابراین ما آنها را به صورت آرایه ای به طول 17 نشان می دهیم. ما این آرایه های 17 عنصری را "گره های شاخه ای" می نامیم.

درخت مرکل پاتریشیا

درختهای رادیکس یک محدودیت عمده دارند: ناکارآمد هستند. اگر می خواهید یک پیوند (مسیر، مقدار) را در جایی که مسیر، مانند اتریوم، 64 کاراکتر طول دارد (تعداد nibble ها در bytes32) ذخیره کنید، به بیش از یک کیلوبایت فضای اضافی برای ذخیره یک سطح در هر کاراکتر نیاز خواهیم داشت، و هر جستجو یا حذف 64 مرحله کامل طول خواهد کشید. درخت پاتریشیا معرفی شده در ادامه این مشکل را حل می کند.

بهينه سازی

یک گره در درخت مرکل پاتریشیا یکی از موارد زیر است:

NULL (به عنوان رشته خالی نمایش داده می شود)
شاخه یک گره 17 موردی [ v0 ... v15, vt ]
برگ یک گره 2 موردی [ encodedPath، مقدار ]
افزونه یک گره 2 موردی [ encodedPath, key ]

با 64 مسیر کاراکتر، اجتناب ناپذیر است که پس از عبور از چند لایه اول سعی کنید، به گره ای برسید که در آن مسیر واگرا حداقل برای بخشی از مسیر پایین وجود نداشته باشد. برای جلوگیری از ایجاد حداکثر 15 گره NULL پراکنده در طول مسیر، با راه‌اندازی یک گره افزونه به شکل [ encodedPath, key ] مسیر فرود را میانبر می‌کنیم، جایی که encodedPath حاوی "مسیر جزئی" برای رد شدن از پیش است (با استفاده از یک رمزگذاری فشرده که در زیر توضیح داده شده است)، و کلید برای جستجوی DB بعدی است.

برای یک گره برگ، که می‌توان آن را با یک پرچم در اولین نیبل encodedPath علامت‌گذاری کرد، مسیر تمام قطعات مسیر گره قبلی را رمزگذاری می کند و ما می توانیم مقدار را مستقیماً جستجو کنیم.

با این حال، این بهینه‌سازی بالا باعث ایجاد ابهام می‌شود.

هنگام پیمایش مسیرها در نیبل، ممکن است در نهایت با تعداد فرد نیبل برای پیمایش مواجه شویم، اما به این دلیل که همه داده ها در قالب بایت ذخیره می شوند. نمی توان بین، به عنوان مثال، nibble 1 و nibbles 01 تفاوت قائل شد (هر دو باید به عنوان <01> ذخیره شوند). برای تعیین طول فرد، مسیر جزئی با یک پرچم پیشوند داده می شود.

مشخصات: رمزگذاری فشرده دنباله هگزا با پایان دهنده اختیاری

علامت گذاری طول مسیر جزئی باقیمانده فرد در مقابل زوج و گره برگ در مقابل پسوند همانطور که در بالا توضیح داده شد در اولین نوک مسیر جزئی هر گره 2 موردی قرار دارد. آنها به موارد زیر منجر می شوند:

1hex char    bits    |    node type partial     path length
2----------------------------------------------------------
3   0        0000    |       extension              even
4   1        0001    |       extension              odd
5   2        0010    |   terminating (leaf)         even
6   3        0011    |   terminating (leaf)         odd

حتی برای طول مسیر باقی‌مانده (0 یا 2)، یک نوک 0 "padding" دیگر همیشه در پی می‌آید.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray now has an even length whose first nibble is the flags.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        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'

در اینجا کد توسعه یافته برای گرفتن یک گره در درخت مرکل پاتریشیا آمده است:

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

درخت نمونه

فرض کنید ما درختی می خواهیم حاوی چهار جفت مسیر/مقدار ('do', 'verb'), ('dog', 'puppy'), (' doge، «coins»)، («horse»، «stallion»).

ابتدا، هم مسیرها و هم مقادیر را به بایت تبدیل می کنیم. در زیر، نمایش‌های واقعی بایت برای مسیرها با > نشان داده می‌شوند، اگرچه مقادیر که برای درک آسان تر همچنان به صورت رشته‌ها`نشان داده می‌شوند (آنها نیز در واقعبایت` خواهند بود):

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

اکنون، ما چنین درختی را با جفت‌های کلید/مقدار زیر در DB زیرین می‌سازیم:

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' ] ]

هنگامی که یک گره در داخل گره دیگری ارجاع داده می شود، آنچه شامل می شود H(rlp.encode(node)) است، که در آن H(x) = keccak256(x) اگر len(x) > = 32 else x و rlp.encode تابع رمزگذاری RLP است.

توجه داشته باشید که هنگام به‌روزرسانی یک درخت، باید جفت کلید/مقدار (keccak256(x)، x) را در یک جدول جستجوی دائمی ذخیره کنید اگر گره تازه ایجاد شده دارای طول >= 32 باشد. با این حال، اگر گره کوتاه‌تر از آن باشد، نیازی به ذخیره چیزی نیست، زیرا تابع f(x) = x قابل برگشت است.

درخت ها در اتریوم

تمام درخت های مرکل در لایه اجرایی اتریوم از درخت مرکل پاتریشیا استفاده می‌کنند.

از یک سر بلوک 3 ریشه از 3 مورد از این درخت ها وجود دارد.

stateRoot
transactionsRoot
receiptsRoot

درخت حالت

یک درخت حالت جهانی وجود دارد و هر بار که کلاینت یک بلوک را پردازش می کند، به روز می شود. در آن، یک مسیر همیشه: keccak256(ethereumAddress) و یک مقدار همیشه: rlp(ethereumAccount) است. به طور خاص، حساب اتریوم یک آرایه 4 موردی از [nonce,balance,storageRoot,codeHash] است. در این مرحله، شایان ذکر است که این storageRoot ریشه یکی دیگر از درخت های پاتریشیا است:

درخت حافظه

درخت Storage جایی است که همه داده‌های قرارداد زندگی می‌کنند. برای هر حساب یک فضای ذخیره سازی جداگانه وجود دارد. برای بازیابی مقادیر در موقعیت‌های ذخیره‌سازی خاص در یک آدرس معین، آدرس ذخیره، موقعیت عدد صحیح داده‌های ذخیره‌شده در حافظه و شناسه بلوک مورد نیاز است. سپس می‌توان آن‌ها را به‌عنوان آرگومان به eth_getStorageAt تعریف‌شده در JSON-RPC API ارسال کرد، به‌عنوان مثال: برای بازیابی داده ها در اسلات ذخیره سازی 0 برای آدرس 0x295a70b2de5e3953354a6a8344e616ed314d7251:

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

بازیابی عناصر دیگر در ذخیره سازی کمی بیشتر دخیل است زیرا ابتدا باید موقعیت در درخت حافظه محاسبه شود. موقعیت به عنوان هش keccak256 آدرس و موقعیت ذخیره سازی محاسبه می شود که هر دو در سمت چپ با صفر تا طول 32 بایت اضافه شده اند. به عنوان مثال، موقعیت داده در شکاف ذخیره سازی 1 برای آدرس 0x391694e7e0b0cce554cb130d723a9d27458f9298 است:

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

در یک کنسول Geth، این می تواند به صورت زیر محاسبه شود:

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

بنابراین مسیر keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>) است. اکنون می توان از آن برای بازیابی داده ها از درخت حافظه مانند قبل استفاده کرد:

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

توجه: storageRoot برای یک حساب اتریوم اگر یک حساب قراردادی نباشد به طور پیش‌فرض خالی است.

درخت تراکنش‌ها

برای هر بلوک یک تراکنش جداگانه وجود دارد که دوباره جفت‌های (کلید، مقدار) را ذخیره می‌کند. یک مسیر در اینجا عبارت است از: rlp(transactionIndex) که نشان دهنده کلیدی است که با مقدار تعیین شده از سوی این مطابقت دارد:

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

اطلاعات بیشتر در این مورد را می توان در اسناد EIP 2718(opens in a new tab) یافت.

درخت رسیدها

هر بلوک درخت رسیدهای خود را دارد. یک مسیر در اینجا این است: rlp(transactionIndex). transactionIndex شاخص آن در بلوکی است که در آن گنجانده شده است. درخت رسیدها هرگز به روز نمی شود. مشابه درخت تراکنش‌ها، رسیدهای جاری و قدیمی وجود دارد. برای استعلام یک رسید خاص در درخت رسیدها، شاخص تراکنش در بلوک آن، بار رسید و نوع تراکنش مورد نیاز است. رسید برگشتی می تواند از نوع رسیدی باشد که به عنوان الحاق TransactionType و ReceiptPayload تعریف می شود یا می تواند از نوع LegacyReceipt< باشد /0> که به صورت <code>rlp([status, cumulativeGasUsed, logsBloom, logs]). تعریف می‌شود.

اطلاعات بیشتر در این مورد را می توان در اسناد EIP 2718(opens in a new tab) یافت.

درخت مرکل پاتریشیا

موارد مورد نیاز

درخت‌های پایه رادیکس

درخت مرکل پاتریشیا

بهينه سازی

مشخصات: رمزگذاری فشرده دنباله هگزا با پایان دهنده اختیاری

درخت نمونه

درخت ها در اتریوم

درخت حالت

درخت حافظه

درخت تراکنش‌ها

درخت رسیدها

اطلاعات بیشتر

آیا این مقاله مفید بود؟