मर्कल पॅट्रिशिया ट्राय
इथेरियमची स्थिती (सर्व खाती, शिल्लक आणि स्मार्ट कॉन्ट्रॅक्ट्सची एकूण बेरीज), संगणक विज्ञानामध्ये सामान्यतः मर्कल ट्री म्हणून ओळखल्या जाणाऱ्या डेटा स्ट्रक्चरच्या एका विशेष आवृत्तीमध्ये एन्कोड केलेली असते. ही रचना गूढलेखनातील अनेक अनुप्रयोगांसाठी उपयुक्त आहे कारण ती ट्रीमध्ये गुंतलेल्या डेटाच्या सर्व वैयक्तिक तुकड्यांमध्ये एक पडताळणी करण्यायोग्य संबंध निर्माण करते, ज्याचा परिणाम एकाच रूट (root) मूल्यामध्ये होतो ज्याचा वापर डेटाबद्दल गोष्टी सिद्ध करण्यासाठी केला जाऊ शकतो.
इथेरियमची डेटा रचना ही एक 'सुधारित मर्कल पॅट्रिशिया ट्राय' आहे, तिला असे नाव दिले आहे कारण ती PATRICIA (the Practical Algorithm To Retrieve Information Coded in Alphanumeric) ची काही वैशिष्ट्ये घेते, आणि कारण ती इथेरियम स्थिती समाविष्ट असलेल्या आयटमच्या कार्यक्षम डेटा पुनर्प्राप्तीसाठी (retrieval) डिझाइन केलेली आहे.
मर्कल पॅट्रिशिया ट्राय हे निश्चित आणि क्रिप्टोग्राफिकदृष्ट्या पडताळणी करण्यायोग्य आहे: स्टेट रूट तयार करण्याचा एकमेव मार्ग म्हणजे स्थितीच्या प्रत्येक वैयक्तिक तुकड्यावरून त्याची गणना करणे, आणि दोन समान स्थिती सहजपणे रूट हॅश आणि त्याकडे नेणाऱ्या हॅशेसची तुलना करून सिद्ध केल्या जाऊ शकतात (एक मर्कल प्रूफ). याउलट, समान रूट हॅशसह दोन भिन्न स्थिती तयार करण्याचा कोणताही मार्ग नाही, आणि भिन्न मूल्यांसह स्थिती सुधारण्याच्या कोणत्याही प्रयत्नाचा परिणाम भिन्न स्टेट रूट हॅशमध्ये होईल. सैद्धांतिकदृष्ट्या, ही रचना इन्सर्ट, लुकअप आणि डिलीट करण्यासाठी 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) च्या वर्णनासह सुरू होतो, त्यानंतर हळूहळू इथेरियमच्या अधिक ऑप्टिमाइझ केलेल्या डेटा रचनेसाठी आवश्यक असलेल्या सुधारणांची ओळख करून देतो.
मूलभूत रॅडिक्स ट्राय
मूलभूत रॅडिक्स ट्रायमध्ये, प्रत्येक नोड खालीलप्रमाणे दिसतो:
[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 निवडा, आणि असेच पुढे, जोपर्यंत, एकदा तुम्ही मार्गाचा अवलंब केला: 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-घटकांच्या अॅरेला "ब्रांच नोड्स" म्हणतो.
मर्कल पॅट्रिशिया ट्राय
रॅडिक्स ट्रायची एक मोठी मर्यादा आहे: ते अकार्यक्षम आहेत. जर तुम्हाला एक (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 नोड सेट करून खाली उतरण्याचा शॉर्टकट करतो, जिथे encodedPath मध्ये पुढे जाण्यासाठी "आंशिक मार्ग" (partial path) असतो (खाली वर्णन केलेल्या कॉम्पॅक्ट एन्कोडिंगचा वापर करून), आणि key पुढील DB लुकअपसाठी असतो.
leaf नोडसाठी, जो encodedPath च्या पहिल्या निबलमधील फ्लॅगद्वारे चिन्हांकित केला जाऊ शकतो, मार्ग सर्व मागील नोडच्या मार्ग खंडांना एन्कोड करतो आणि आपण थेट value शोधू शकतो.
तथापि, वरील ऑप्टिमायझेशनमुळे संदिग्धता निर्माण होते.
निबल्समध्ये मार्गांवरून जाताना, आपल्याला पार करण्यासाठी विषम संख्येचे निबल्स मिळू शकतात, परंतु कारण सर्व डेटा bytes फॉरमॅटमध्ये संग्रहित केला जातो. उदाहरणार्थ, निबल 1 आणि निबल्स 01 यांच्यात फरक करणे शक्य नाही (दोन्ही <01> म्हणून संग्रहित केले जाणे आवश्यक आहे). विषम लांबी निर्दिष्ट करण्यासाठी, आंशिक मार्गाच्या आधी एक फ्लॅग लावला जातो.
तपशील: पर्यायी टर्मिनेटरसह हेक्स अनुक्रमाचे कॉम्पॅक्ट एन्कोडिंग
वर वर्णन केल्याप्रमाणे विषम वि. सम उर्वरित आंशिक मार्गाची लांबी आणि लीफ वि. एक्स्टेंशन नोड या दोन्हींचे फ्लॅगिंग कोणत्याही 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 एन्कोडिंग फंक्शन आहे.
लक्षात घ्या की ट्राय अपडेट करताना, नव्याने तयार केलेल्या नोडची लांबी >= 32 असल्यास की/व्हॅल्यू जोडी (keccak256(x), x) पर्सिस्टंट लुकअप टेबलमध्ये संग्रहित करणे आवश्यक आहे. तथापि, जर नोड त्यापेक्षा लहान असेल, तर काहीही संग्रहित करण्याची आवश्यकता नाही, कारण फंक्शन f(x) = x हे रिव्हर्सिबल आहे.
इथेरियममधील ट्राय
इथेरियमच्या अंमलबजावणी स्तरावरील सर्व मर्कल ट्राय मर्कल पॅट्रिशिया ट्राय वापरतात.
ब्लॉक हेडरमधून या 3 ट्रायचे 3 रूट्स असतात.
- स्टेटरूट (stateRoot)
- ट्रान्झॅक्शन्सरूट (transactionsRoot)
- रिसिप्ट्सरूट (receiptsRoot)
स्टेट ट्राय
एक ग्लोबल स्टेट ट्राय आहे, आणि प्रत्येक वेळी क्लायंट ब्लॉकवर प्रक्रिया करतो तेव्हा ते अपडेट केले जाते. त्यामध्ये, path नेहमी: keccak256(ethereumAddress) असते आणि value नेहमी: rlp(ethereumAccount) असते. अधिक स्पष्टपणे सांगायचे तर इथेरियम account हा [nonce,balance,storageRoot,codeHash] चा 4 आयटम अॅरे आहे. या टप्प्यावर, हे लक्षात घेण्यासारखे आहे की हे storageRoot दुसऱ्या पॅट्रिशिया ट्रायचे रूट आहे:
स्टोरेज ट्राय
स्टोरेज ट्रायमध्ये सर्व कॉन्ट्रॅक्ट डेटा असतो. प्रत्येक खात्यासाठी एक स्वतंत्र स्टोरेज ट्राय असते. दिलेल्या पत्त्यावर विशिष्ट स्टोरेज पोझिशन्सवरील मूल्ये पुनर्प्राप्त करण्यासाठी स्टोरेज पत्ता, स्टोरेजमधील संग्रहित डेटाची इंटिजर पोझिशन आणि ब्लॉक आयडी आवश्यक आहेत. हे नंतर जेसॉन-आरपीसी 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"
म्हणून 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) दस्तऐवजीकरणामध्ये आढळू शकते.