मर्कल पैट्रिशिया ट्राई

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

इथेरियम की डेटा संरचना एक 'संशोधित मर्कल-पैट्रिशिया ट्राई' है, जिसका नाम ऐसा इसलिए रखा गया है क्योंकि यह PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric) की कुछ विशेषताओं को उधार लेती है, और क्योंकि इसे इथेरियम स्थिति को बनाने वाले आइटमों की कुशल डेटा पुनर्प्राप्ति (retrieval) के लिए डिज़ाइन किया गया है।

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

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

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

इस पृष्ठ को बेहतर ढंग से समझने के लिए, हैश (एक नए टैब में खुलता है), मर्कल ट्री (एक नए टैब में खुलता है), ट्राई (tries) (एक नए टैब में खुलता है) और क्रमांकन (एक नए टैब में खुलता है) का बुनियादी ज्ञान होना मददगार होगा। यह लेख एक बुनियादी रेडिक्स ट्री (radix tree) (एक नए टैब में खुलता है) के विवरण के साथ शुरू होता है, फिर धीरे-धीरे इथेरियम की अधिक अनुकूलित डेटा संरचना के लिए आवश्यक संशोधनों का परिचय देता है।

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

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

[i_0, i_1 ... i_n, value]

जहाँ i_0 ... i_n वर्णमाला के प्रतीकों (अक्सर बाइनरी या हेक्स) का प्रतिनिधित्व करते हैं, value नोड पर टर्मिनल मान है, और i_0, i_1 ... i_n स्लॉटों में मान या तो NULL हैं या अन्य नोड्स के पॉइंटर्स (हमारे मामले में, हैश) हैं। यह एक बुनियादी (key, value) स्टोर बनाता है।

मान लीजिए कि आप कुंजी मान (key value) जोड़े के एक सेट पर एक क्रम को बनाए रखने के लिए एक रेडिक्स ट्री डेटा संरचना का उपयोग करना चाहते हैं। ट्राई में कुंजी dog पर वर्तमान में मैप किए गए मान को खोजने के लिए, आप पहले dog को वर्णमाला के अक्षरों में बदलेंगे (जिससे 64 6f 67 मिलेगा), और फिर उस पथ का अनुसरण करते हुए ट्राई में तब तक नीचे जाएंगे जब तक कि आपको मान न मिल जाए। यानी, आप ट्राई के रूट नोड को खोजने के लिए एक फ्लैट कुंजी/मान DB में रूट हैश को देखकर शुरू करते हैं। इसे अन्य नोड्स को इंगित करने वाली कुंजियों की एक सरणी (array) के रूप में दर्शाया गया है। आप सूचकांक 6 पर मान का उपयोग एक कुंजी के रूप में करेंगे और एक स्तर नीचे नोड प्राप्त करने के लिए इसे फ्लैट कुंजी/मान DB में देखेंगे। फिर अगला मान देखने के लिए सूचकांक 4 चुनें, फिर सूचकांक 6 चुनें, और इसी तरह, जब तक कि, एक बार जब आप पथ: root -> 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 बिट बाइनरी संख्या) को "निबल (nibble)" के रूप में संदर्भित करेंगे। एक समय में एक निबल पथ को पार करते समय, जैसा कि ऊपर वर्णित है, नोड्स अधिकतम 16 बच्चों को संदर्भित कर सकते हैं लेकिन इसमें एक value तत्व शामिल होता है। इसलिए, हम उन्हें 17 की लंबाई वाली सरणी के रूप में दर्शाते हैं। हम इन 17-तत्व सरणियों को "ब्रांच नोड्स (branch nodes)" कहते हैं।

मर्कल पैट्रिशिया ट्राई

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

अनुकूलन

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

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

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

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

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

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

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

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

हेक्स वर्ण	बिट्स	नोड प्रकार आंशिक	पथ की लंबाई
0	0000	एक्सटेंशन	सम
1	0001	एक्सटेंशन	विषम
2	0010	टर्मिनेटिंग (लीफ)	सम
3	0011	टर्मिनेटिंग (लीफ)	विषम

सम शेष पथ लंबाई (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
        # हेक्सएरे की लंबाई अब सम है, जिसका पहला निबल फ्लैग्स है।
        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') हों।

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

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

अब, हम अंतर्निहित 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 प्रतिवर्ती (reversible) है।

इथेरियम में ट्राई

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

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

stateRoot
transactionsRoot
receiptsRoot

स्टेट ट्राई

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

स्टोरेज ट्राई

स्टोरेज ट्राई वह जगह है जहाँ सभी अनुबंध डेटा रहता है। प्रत्येक खाते के लिए एक अलग स्टोरेज ट्राई है। किसी दिए गए पते पर विशिष्ट स्टोरेज स्थितियों पर मान प्राप्त करने के लिए स्टोरेज पता, स्टोरेज में संग्रहीत डेटा की पूर्णांक स्थिति और ब्लॉक ID की आवश्यकता होती है। फिर इन्हें जेसन-आरपीसी 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"))

गो इथेरियम (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 (एक नए टैब में खुलता है) दस्तावेज़ में पाई जा सकती है।

रसीद ट्राई

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

इस पर अधिक जानकारी EIP-2718 (एक नए टैब में खुलता है) दस्तावेज़ में पाई जा सकती है।

मर्कल पैट्रिशिया ट्राई

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

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

मर्कल पैट्रिशिया ट्राई

अनुकूलन

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

उदाहरण ट्राई

इथेरियम में ट्राई

स्टेट ट्राई

स्टोरेज ट्राई

लेन-देन ट्राई

रसीद ट्राई

आगे की पढ़ाई