मर्कल पेट्रीशिया ट्री

एथेरियम की स्थिति (सभी खातों, शेष राशियों और स्मार्ट अनुबंधों की समग्रता) को डेटा संरचना के एक विशेष संस्करण में एन्कोड किया गया है जिसे आम तौर पर कंप्यूटर विज्ञान में मर्कल ट्री के रूप में जाना जाता है। यह संरचना क्रिप्टोग्राफी में कई अनुप्रयोगों के लिए उपयोगी है क्योंकि यह ट्री में उलझे डेटा के सभी अलग-अलग टुकड़ों के बीच एक सत्यापन योग्य संबंध बनाती है, जिसके परिणामस्वरूप एक एकल रूट मान होता है जिसका उपयोग डेटा के बारे में चीजों को साबित करने के लिए किया जा सकता है।

एथेरियम की डेटा संरचना एक 'संशोधित मर्कल-पेट्रीशिया ट्री' है, जिसका नाम इसलिए रखा गया है क्योंकि यह PATRICIA (प्रैक्टिकल एल्गोरिदम टू रिट्रीव इंफॉर्मेशन कोडेड इन अल्फ़ान्यूमेरिक) की कुछ विशेषताओं को उधार लेती है, और क्योंकि इसे एथेरियम स्थिति वाले आइटम्स की कुशल डेटा पुनर्प्राप्ति के लिए डिज़ाइन किया गया है।

एक मर्कल-पेट्रीशिया ट्री नियतात्मक और क्रिप्टोग्राफ़िक रूप से सत्यापन योग्य है: एक स्थिति रूट उत्पन्न करने का एकमात्र तरीका इसे स्थिति के प्रत्येक व्यक्तिगत टुकड़े से गणना करके है, और दो स्थितियाँ जो समान हैं, उन्हें रूट हैश और उन हैश की तुलना करके आसानी से साबित किया जा सकता है जो इसके कारण बने (एक मर्कल प्रूफ़)। इसके विपरीत, एक ही रूट हैश के साथ दो अलग-अलग स्थितियाँ बनाने का कोई तरीका नहीं है, और अलग-अलग मानों के साथ स्थिति को संशोधित करने के किसी भी प्रयास के परिणामस्वरूप एक अलग स्थिति रूट हैश होगा। सैद्धांतिक रूप से, यह संरचना इन्सर्ट, लुकअप और डिलीट के लिए O(log(n)) दक्षता का 'होली ग्रेल' प्रदान करती है।

निकट भविष्य में, एथेरियम वर्क्ल ट्री संरचना में माइग्रेट करने की योजना बना रहा है, जो भविष्य में प्रोटोकॉल सुधार के लिए कई नई संभावनाएं खोलेगा।

पूर्वापेक्षाएं

इस पेज को बेहतर ढंग से समझने के लिए, हैश (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) के विवरण के साथ शुरू होता है, फिर धीरे-धीरे एथेरियम की अधिक अनुकूलित डेटा संरचना के लिए आवश्यक संशोधनों का परिचय देता है।

बुनियादी रेडिक्स ट्री

एक बुनियादी रेडिक्स ट्री में, प्रत्येक नोड निम्नानुसार दिखता है:

    [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 देते हुए), और फिर उस पथ का अनुसरण करते हुए ट्री में तब तक उतरें जब तक आपको मान न मिल जाए। आप ट्री के रूट नोड को खोजने के लिए एक फ्लैट कुंजी/मान DB में रूट हैश को देखकर शुरू करते हैं। इसे अन्य नोड्स को इंगित करने वाली कुंजियों की एक सरणी के रूप में दर्शाया गया है। आप एक स्तर नीचे नोड प्राप्त करने के लिए इंडेक्स 6 पर मान को एक कुंजी के रूप में उपयोग करेंगे और इसे फ्लैट कुंजी/मान DB में देखेंगे। फिर अगला मान देखने के लिए इंडेक्स 4 चुनें, फिर इंडेक्स 6, और इसी तरह, जब तक, एक बार जब आप पथ का अनुसरण करते हैं: रूट -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, आप नोड के मान को देखेंगे और परिणाम वापस कर देंगे।

'ट्री' में कुछ देखने और अंतर्निहित फ्लैट कुंजी/मान 'DB' के बीच एक अंतर है। वे दोनों कुंजी/मान व्यवस्था को परिभाषित करते हैं, लेकिन अंतर्निहित DB एक कुंजी का पारंपरिक 1 चरण लुकअप कर सकता है। ट्री में एक कुंजी को देखने के लिए ऊपर वर्णित अंतिम मान तक पहुंचने के लिए कई अंतर्निहित DB लुकअप की आवश्यकता होती है। आइए अस्पष्टता को खत्म करने के लिए बाद वाले को 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)

एक "मर्कल" रेडिक्स ट्री नियतात्मक रूप से उत्पन्न क्रिप्टोग्राफ़िक हैश डाइजेस्ट का उपयोग करके नोड्स को लिंक करके बनाया गया है। यह सामग्री-एड्रेसिंग (कुंजी/मान DB में key == keccak256(rlp(value))) संग्रहीत डेटा की क्रिप्टोग्राफ़िक अखंडता की गारंटी प्रदान करता है। यदि किसी दिए गए ट्री का रूट हैश सार्वजनिक रूप से ज्ञात है, तो अंतर्निहित लीफ डेटा तक पहुंच वाला कोई भी व्यक्ति एक प्रमाण का निर्माण कर सकता है कि ट्री में एक विशिष्ट मान को ट्री रूट से जोड़ने वाले प्रत्येक नोड के हैश प्रदान करके एक विशिष्ट पथ पर एक दिया गया मान शामिल है।

एक हमलावर के लिए एक ऐसे (path, value) जोड़े का प्रमाण प्रदान करना असंभव है जो मौजूद नहीं है क्योंकि रूट हैश अंततः इसके नीचे के सभी हैश पर आधारित होता है। कोई भी अंतर्निहित संशोधन रूट हैश को बदल देगा। आप हैश को डेटा के बारे में संरचनात्मक जानकारी के एक संपीड़ित प्रतिनिधित्व के रूप में सोच सकते हैं, जो हैशिंग फ़ंक्शन के प्री-इमेज संरक्षण द्वारा सुरक्षित है।

हम एक रेडिक्स ट्री की एक परमाणु इकाई (जैसे, एक एकल हेक्स वर्ण, या 4 बिट बाइनरी संख्या) को "निबल" के रूप में संदर्भित करेंगे। जैसा कि ऊपर वर्णित है, एक समय में एक निबल पथ को पार करते समय, नोड अधिकतम 16 बच्चों को संदर्भित कर सकते हैं लेकिन एक value तत्व शामिल करते हैं। इसलिए, हम उन्हें लंबाई 17 की एक सरणी के रूप में दर्शाते हैं। हम इन 17-तत्व सरणियों को "ब्रांच नोड्स" कहते हैं।

मर्कल पेट्रीशिया ट्री

रेडिक्स ट्री की एक बड़ी सीमा है: वे अक्षम हैं। यदि आप एक (path, value) बाइंडिंग को स्टोर करना चाहते हैं, जहाँ पथ, जैसा कि एथेरियम में है, 64 वर्ण लंबा है (bytes32 में निबल्स की संख्या), हमें प्रति वर्ण एक स्तर स्टोर करने के लिए एक किलोबाइट से अधिक अतिरिक्त स्थान की आवश्यकता होगी, और प्रत्येक लुकअप या डिलीट में पूरे 64 चरण लगेंगे। निम्नलिखित में पेश किया गया पेट्रीशिया ट्री इस मुद्दे को हल करता है।

अनुकूलन

मर्कल पेट्रीशिया ट्री में एक नोड निम्नलिखित में से एक है:

1. NULL (खाली स्ट्रिंग के रूप में दर्शाया गया)
2. branch एक 17-आइटम नोड [ v0 ... v15, vt ]`
3. leaf एक 2-आइटम नोड [ encodedPath, value ]
4. extension एक 2-आइटम नोड [ encodedPath, key ]

64 कैरेक्टर पाथ के साथ यह अनिवार्य है कि ट्री की पहली कुछ परतों को पार करने के बाद, आप एक ऐसे नोड पर पहुंचेंगे जहां नीचे के रास्ते के कम से कम हिस्से के लिए कोई अलग रास्ता मौजूद नहीं है। पथ के साथ 15 तक विरल NULL नोड्स बनाने से बचने के लिए, हम [ encodedPath, key ] के रूप का एक extension नोड स्थापित करके अवरोहण को छोटा करते हैं, जहाँ encodedPath में आगे बढ़ने के लिए "आंशिक पथ" होता है (नीचे वर्णित एक कॉम्पैक्ट एन्कोडिंग का उपयोग करके), और key अगले DB लुकअप के लिए है।

leaf नोड के लिए, जिसे encodedPath के पहले निबल में एक फ़्लैग द्वारा चिह्नित किया जा सकता है, पथ सभी पूर्व नोड के पथ अंशों को एन्कोड करता है और हम सीधे value को देख सकते हैं।

हालाँकि, यह उपरोक्त अनुकूलन, अस्पष्टता का परिचय देता है।

निबल्स में पथों को पार करते समय, हम पार करने के लिए निबल्स की एक विषम संख्या के साथ समाप्त हो सकते हैं, लेकिन क्योंकि सभी डेटा bytes प्रारूप में संग्रहीत है। उदाहरण के लिए, निबल 1, और निबल्स 01 के बीच अंतर करना संभव नहीं है (दोनों को <01> के रूप में संग्रहीत किया जाना चाहिए)। विषम लंबाई निर्दिष्ट करने के लिए, आंशिक पथ को एक फ़्लैग के साथ उपसर्ग किया जाता है।

विनिर्देशन: वैकल्पिक टर्मिनेटर के साथ हेक्स अनुक्रम की कॉम्पैक्ट एन्कोडिंग

जैसा कि ऊपर वर्णित है, विषम बनाम सम शेष आंशिक पथ लंबाई और लीफ बनाम एक्सटेंशन नोड दोनों का फ़्लैगिंग किसी भी 2-आइटम नोड के आंशिक पथ के पहले निबल में रहता है। वे निम्नलिखित में परिणत होते हैं:

सम शेष पथ लंबाई (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 now has an even length whose first nibble is the flags.
        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)

उदाहरण ट्री

मान लीजिए कि हम चार पथ/मान जोड़े ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion') वाला एक ट्री चाहते हैं।

सबसे पहले, हम पथ और मान दोनों को बाइट्स में बदलते हैं। नीचे, पथों के लिए वास्तविक बाइट अभ्यावेदन को <> द्वारा दर्शाया गया है, हालांकि मानों को अभी भी स्ट्रिंग्स के रूप में दिखाया गया है, जिसे '' द्वारा दर्शाया गया है, ताकि आसानी से समझा जा सके (वे भी, वास्तव में बाइट्स होंगे):

    <64 6f> : 'क्रिया'
    <64 6f 67> : 'पिल्ला'
    <64 6f 67 65> : 'सिक्के'
    <68 6f 72 73 65> : 'घोड़ा'

अब, हम अंतर्निहित DB में निम्नलिखित कुंजी/मान जोड़े के साथ ऐसा ट्री बनाते हैं:

    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 प्रतिवर्ती है।

एथेरियम में ट्री

एथेरियम की निष्पादन परत में सभी मर्कल ट्री मर्कल पेट्रीशिया ट्री का उपयोग करते हैं।

एक ब्लॉक हैडर से इन 3 ट्री से 3 रूट होते हैं।

1. स्थिति रूट
2. लेनदेन रूट
3. रसीद रूट

स्टेट ट्री

एक वैश्विक स्टेट ट्री है, और जब भी कोई क्लाइंट ब्लॉक को प्रोसेस करता है तो इसे अपडेट किया जाता है। इसमें, एक पथ हमेशा होता है: keccak256(ethereumAddress) और एक मान हमेशा होता है: rlp(ethereumAccount)। अधिक विशेष रूप से एक एथेरियम खाता [nonce,balance,storageRoot,codeHash] की 4 आइटम सरणी है। इस बिंदु पर, यह ध्यान देने योग्य है कि यह storageRoot एक और पेट्रीशिया ट्री का रूट है:

स्टोरेज ट्री

स्टोरेज ट्री वह जगह है जहाँ सभी अनुबंध डेटा रहता है। प्रत्येक खाते के लिए एक अलग स्टोरेज ट्री होता है। किसी दिए गए पते पर विशिष्ट स्टोरेज पदों पर मान प्राप्त करने के लिए स्टोरेज पता, स्टोरेज में संग्रहीत डेटा की पूर्णांक स्थिति और ब्लॉक आईडी की आवश्यकता होती है। फिर इन्हें JSON-RPC API में परिभाषित eth_getStorageAt के लिए तर्कों के रूप में पारित किया जा सकता है, उदाहरण के लिए, पते 0x295a70b2de5e3953354a6a8344e616ed314d7251 के लिए स्टोरेज स्लॉट 0 में डेटा पुनर्प्राप्त करने के लिए:

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 बाइट्स की लंबाई तक शून्य से बाएं-पैड किया जाता है। उदाहरण के लिए, पते 0x391694e7e0b0cce554cb130d723a9d27458f9298 के लिए स्टोरेज स्लॉट 1 में डेटा की स्थिति है:

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

गेथ कंसोल में, इसकी गणना इस प्रकार की जा सकती है:

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

इसलिए पथ 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 डिफ़ॉल्ट रूप से खाली है।

लेनदेन ट्री

प्रत्येक ब्लॉक के लिए एक अलग लेनदेन ट्री होता है, जो फिर से (कुंजी, मान) जोड़े को संग्रहीत करता है। यहाँ एक पथ है: rlp(transactionIndex) जो उस कुंजी का प्रतिनिधित्व करता है जो एक मान से मेल खाती है जो निम्न द्वारा निर्धारित होती है:

यदि legacyTx:
  मान = rlp(tx)
अन्यथा:
  मान = TxType | encode(tx)

इस पर अधिक जानकारी EIP 2718 (opens in a new tab) प्रलेखन में पाई जा सकती है।

रसीद ट्री

हर ब्लॉक का अपना रसीद ट्री होता है। यहाँ एक पथ है: rlp(transactionIndex)। transactionIndex उस ब्लॉक के भीतर इसका सूचकांक है जिसमें इसे शामिल किया गया था। रसीद ट्री को कभी अपडेट नहीं किया जाता है। लेनदेन ट्री के समान, वर्तमान और विरासत रसीदें हैं। रसीद ट्री में एक विशिष्ट रसीद को क्वेरी करने के लिए, उसके ब्लॉक में लेनदेन का सूचकांक, रसीद पेलोड और लेनदेन प्रकार की आवश्यकता होती है। लौटाई गई रसीद रसीद प्रकार की हो सकती है जिसे TransactionType और ReceiptPayload के संयोजन के रूप में परिभाषित किया गया है या यह LegacyReceipt प्रकार की हो सकती है जिसे rlp([status, cumulativeGasUsed, logsBloom, logs]) के रूप में परिभाषित किया गया है।

इस पर अधिक जानकारी EIP 2718 (opens in a new tab) प्रलेखन में पाई जा सकती है।

अतिरिक्त पठन

• संशोधित मर्कल पेट्रीशिया ट्री — एथेरियम एक स्थिति कैसे बचाता है (opens in a new tab)
• एथेरियम में मर्कलिंग (opens in a new tab)
• एथेरियम ट्री को समझना (opens in a new tab)