💻 computer science

Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries

यह शोध पत्र ऑन-चेन रजिस्ट्रियों के लिए इंक्रीमेंटल मर्केल ट्रीज़ (incremental Merkle trees) के एक कॉन्स्टेंट-टाइम, गैस-कुशल विकल्प के रूप में पैरेंट-हैश डीएजी (Parent-Hash DAG - PHDAG) को प्रस्तुत और औपचारिक रूप से विश्लेषित करता है, जो सैद्धांतिक मॉडलिंग और अनुभवजन्य बेंचमार्क के माध्यम से यह प्रदर्शित करता है कि PHDAG डेप्थ-इनवेरिएंट लागत (depth-invariant costs) बनाए रखता है जबकि मर्केल ट्री की लागत रैखिक रूप से बढ़ती है, जिससे PHDAG सभी व्यावहारिक उत्पादन गहराइयों (practical production depths) के लिए श्रेष्ठ सिद्ध होता है।

मूल लेखक: Ian C. Moore, Fernando Paredes Garcia

प्रकाशित 2026-06-09

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ian C. Moore, Fernando Paredes Garcia

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक डिजिटल लाइब्रेरी चला रहे हैं जहाँ लोग नई किताबें रजिस्टर करने आते हैं। हर बार जब कोई किताब जोड़ता है, तो लाइब्रेरी को अपनी मास्टर लिस्ट अपडेट करनी पड़ती है। यह शोध पत्र यह सवाल पूछता है: जैसे-जैसे लाइब्रेरी कुछ किताबों से बढ़कर लाखों तक पहुँचती है, इस लिस्ट को अपडेट करने का सबसे कुशल तरीका क्या है?

लेखक इस लाइब्रेरी को व्यवस्थित करने के दो अलग-अलग तरीकों की तुलना करते हैं: इन्क्रीमेंटल मर्केल ट्री (IMT) और पैरेंट-हैश DAG (PHDAG)।

यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है।

1. दो दृष्टिकोण

इन्क्रीमेंटल मर्केल ट्री (IMT): "ब्लॉक्स का टॉवर"

IMT को ब्लॉक्स के एक विशाल, पूरी तरह से सममित (symmetrical) टॉवर के रूप में सोचें।

यह कैसे काम करता है: हर बार जब आप एक नई किताब (एक लीफ/leaf) जोड़ते हैं, तो आपको टॉवर पर चढ़ना पड़ता है, उसके ठीक ऊपर वाले ब्लॉक को अपडेट करना होता है, फिर उसके ऊपर वाले को, और यह प्रक्रिया बिल्कुल ऊपर (रूट/root) तक चलती है।
लागत: टॉवर जितना ऊँचा होगा, चढ़ाई उतनी ही लंबी होगी। यदि लाइब्रेरी में 1,000 किताबें हैं, तो आप थोड़ा ऊपर चढ़ेंगे। यदि इसमें 10 लाख किताबें हैं, तो आपको बहुत ऊपर तक चढ़ना होगा।
समस्या: जैसे-जैसे लाइब्रेरी बढ़ती है, लागत (जिसे "गैस" कहा जाता है, जो अपडेट करने के लिए लगने वाली ऊर्जा फीस की तरह है) बढ़ती जाती है। यह एक टैक्सी यात्रा के लिए भुगतान करने जैसा है—आप जितनी दूर जाएंगे, उतना अधिक किराया देंगे। साथ ही, लागत बदलती रहती है: कभी आपको बहुत सीढ़ियाँ चढ़नी पड़ती हैं, तो कभी कम, यह इस पर निर्भर करता है कि आप अपनी नई किताब को ठीक कहाँ रखते हैं।

पैरेंट-हैश DAG (PHDAG): "पत्रों की श्रृंखला"

PHDAG को दोस्तों के बीच भेजी जाने वाली पत्रों की एक श्रृंखला के रूप में सोचें।

यह कैसे काम करता है: जब आप एक नई किताब जोड़ते हैं, तो आप बस उसका विवरण लिखते हैं और एक नोट लिखते हैं कि, "यह किताब उस विशिष्ट पिछली किताब के बाद आती है।" आप उस नोट को एक सार्वजनिक मेलबॉक्स (ब्लॉकचेन इवेंट लॉग) में डाल देते हैं। आपको टॉवर पर चढ़ने या किसी केंद्रीय रूट को अपडेट करने की आवश्यकता नहीं है। आप बस अपना नोट लिखते हैं और उसे अतीत से जोड़ देते हैं।
लागत: इससे कोई फर्क नहीं पड़ता कि लाइब्रेरी में 10 किताबें हैं या 1 करोड़। आप हमेशा समान मात्रा में टेक्स्ट लिखते हैं और उसे उसी मेलबॉक्स में डालते हैं।
लाभ: इसकी लागत स्थिर (constant) है। लाइब्रेरी कितनी भी बड़ी हो जाए, यह कभी नहीं बदलती। यह एक पोस्टकार्ड भेजने के लिए एक निश्चित शुल्क देने जैसा है, चाहे पहले कितने भी पोस्टकार्ड भेजे गए हों।

2. बड़ी खोज: बदलाव कब होता है?

लेखकों ने गणित लगाया और वास्तविक दुनिया के परीक्षण के लिए एक टेस्ट नेटवर्क (Base Sepolia) पर परीक्षण किया ताकि यह देखा जा सके कि "पत्रों की श्रृंखला" (PHDGA) कब "ब्लॉक्स के टॉवर" (IMT) से सस्ती हो जाती है।

टिपिंग पॉइंट (निर्णायक बिंदु): उन्होंने पाया कि "टॉवर" केवल तब सस्ता होता है जब लाइब्रेरी बहुत छोटी होती है (लगभग 7 स्तर गहरी)।
वास्तविकता: लगभग हर वास्तविक दुनिया का सिस्टम जो इन रजिस्ट्रीज़ (जैसे गोपनीयता उपकरण या पहचान प्रणाली) का उपयोग करता है, वह बहुत, बहुत अधिक गहरा होता है। वे आमतौर पर 20 से 40 स्तर गहरे होते हैं।
परिणाम: वास्तविक दुनिया में, "पत्रों की श्रृंखला" (PHDAG) हमेशा सस्ती और हमेशा अनुमानित (predictable) होती है।

3. यह क्यों मायने रखता है? (द "वैरिएंस" समस्या)

कल्पना कीजिए कि आप लाइब्रेरी को अपडेट करने के लिए एक निश्चित शुल्क लेने वाली एक डिलीवरी सेवा हैं।

टॉवर के साथ (IMT): कभी अपडेट सस्ता होता है, तो कभी महंगा। आपको कीमत का अनुमान लगाना पड़ता है। यदि आपका अनुमान गलत निकला, तो आप महंगे अपडेट के कारण नुकसान उठा सकते हैं। लागत ऊपर-नीचे "झिलमिलाती" (jitters) रहती है।
श्रृंखला के साथ (PHDAG): कीमत हमेशा बिल्कुल एक जैसी होती है। कोई अनुमान लगाने की जरूरत नहीं है। लेखकों ने पाया कि लागत केवल 6 यूनिट गैस के आसपास घटती-बढ़ती है (एक बहुत ही मामूली मात्रा), जो कि व्यावहारिक रूप से शून्य है। यह इसे व्यवसायों के लिए अविश्वसनीय रूप से विश्वसनीय बनाता है।

4. "रिकंस्ट्रक्शन" (पुनर्निर्माण) की महाशक्ति

एक अन्य प्रमुख अंतर भी है।

टॉवर (IMT): यह साबित करने के लिए कि एक किताब मौजूद है, आपको एक विशिष्ट "प्रूफ" (एक रसीद जो टॉवर में ऊपर जाने वाले पथ को दर्शाती है) की आवश्यकता होती है। यदि केंद्रीय इंडेक्स टूट जाता है, तो शायद आप पूरे टॉवर को आसानी से सत्यापित करने की क्षमता खो सकते हैं।
श्रृंखला (PHDAG): पूरा इतिहास सार्वजनिक मेलबॉक्स (इवेंट लॉग्स) में लिखा गया है। भले ही लाइब्रेरी चलाने वाला कंप्यूटर क्रैश हो जाए, कोई भी मेलबॉक्स में जा सकता है, क्रम में पत्रों को पढ़ सकता है, और शून्य से पूरी लाइब्रेरी को फिर से बना सकता है। यह "अविनाशी" है क्योंकि इसका इतिहास एक एकल स्टोरेज स्लॉट में लॉक होने के बजाय सार्वजनिक रिकॉर्ड में बिखरा हुआ है।

5. निष्कर्ष (Bottom Line)

यह शोध पत्र निष्कर्ष निकालता है कि किसी भी बड़े पैमाने के, वास्तविक दुनिया के सिस्टम के लिए जिसे घटनाओं का इतिहास रिकॉर्ड करने की आवश्यकता है (जैसे यह साबित करना कि कौन सा डिजिटल आर्ट किसका है या सप्लाई चेन को ट्रैक करना):

इस विशिष्ट कार्य के लिए "टॉवर" (IMT) का उपयोग करना बंद करें। जैसे-जैसे यह बढ़ता है, यह बहुत महंगा और अप्रत्याशित हो जाता है।
"श्रृंखला" (PHDAG) का उपयोग करना शुरू करें। यह सस्ता है, इसकी कीमत कभी नहीं बदलती, और डेटा अधिक सुरक्षित है क्योंकि इसे किसी भी समय सार्वजनिक रिकॉर्ड से फिर से बनाया जा सकता है।

लेखक सुझाव देते हैं कि ब्लॉकचेन समुदाय को भविष्य के सभी प्रोवेनेंस रजिस्ट्रीज़ (provenance registries) के लिए एक मानक नियम के रूप में इस "पत्रों की श्रृंखला" पद्धति को अपनाना चाहिए, क्योंकि यह बड़ी मात्रा में डेटा को संभालने का सबसे कुशल और मजबूत तरीका है।

तकनीकी सारांश: ऑन-चेन रजिस्ट्रियों के लिए कॉन्स्टेंट-टाइम अपेंड का लागत विश्लेषण

समस्या विवरण (Problem Statement)

प्रूवेनेंस ट्रीज़ (PTs) अपेंड-ओनली डायरेक्टेड एसाइक्लिक ग्राफ्स (DAGs) हैं जिनका उपयोग ऑपरेटर-गेटेड प्रूवेनेंस इंफ्रास्ट्रक्चर के लिए डेटा सबस्ट्रेट के रूप में किया जाता है। जबकि पिछले कार्यों ने यह दावा किया था कि PTs के लिए अंतर्निहित अपेंड ऑपरेशन की गैस लागत $O(1)$ है—जो रजिस्ट्री के आकार और ट्री डेप्थ से स्वतंत्र है—इस दावे में एक स्टैंडअलोन प्रिमिटिव के रूप में औपचारिक अलगाव, स्पष्ट कॉन्स्टेंट बाउंड्स, या उद्योग मानक: इंक्रीमेंटल मर्केल ट्री (IMT) के विरुद्ध अनुभवजन्य बेंचमार्किंग का अभाव था।

IMT, जो ज़ीरो-नॉलेज प्रोटोकॉल (जैसे, टोनाडो कैश, सेमाफोर) और रोलअप स्टेट कमिटमेंट्स में प्रमुख है, संक्षिप्त $O(\log N)$ समावेश प्रमाण (inclusion proofs) प्रदान करता है, लेकिन इसमें एक अपेंड लागत होती है जो ट्री डेप्थ के साथ लॉगरिदमिक रूप से ( $\Theta(\log N)$ ) बढ़ती है। उन अनुप्रयोगों के लिए जहाँ संक्षिप्त सदस्यता प्रमाण (membership proofs) प्राथमिक क्वेरी नहीं हैं (जैसे कि प्रूवेनेंस रजिस्ट्रियां), IMT का लागत ट्रेड-ऑफ कम अनुकूल है, फिर भी वह क्रॉसओवर पॉइंट जहाँ एक विकल्प सस्ता हो जाता है, अभी तक कठोरता से स्थापित नहीं किया गया है।

कार्यप्रणाली (Methodology)

यह शोध पत्र पैरेंट-हैश डायरेक्टेड एसाइक्लिक ग्राफ (PHDAG) को एक विशिष्ट प्रिमिटिव के रूप में अलग करता है और इंक्रीमेंटल मर्केल ट्री (IMT) के विरुद्ध तीन दृष्टिकोणों से तुलना करता है:

औपचारिक जटिलता विश्लेषण (Formal Complexity Analysis): लेखक PHDAG अपेंड ऑपरेशन को औपचारिक रूप करते हैं, यह सिद्ध करते हुए कि यह रजिस्ट्री के आकार ( $n$ ) या डेप्थ से स्वतंत्र होकर सीमित संख्या में EVM ऑपरेशन्स को निष्पादित करता है। वे IMT के फ्रंटियर-अपडेट लूप के विपरीत, जो डेप्थ ( $d$ ) के साथ रैखिक रूप से स्केल करता है, इसका विश्लेषण करते हैं।
स्टोकेस्टिक लागत मॉडलिंग (Stochastic Cost Modeling): यह पहचानते हुए कि IMT अपेंड लागत लीफ इंडेक्स के बाइनरी रिप्रेजेंटेशन (हैमिंग वेट) के आधार पर भिन्न होती है, लेखक प्रति-इंसर्ट गैस लागत को एक रैंडम वेरिएबल के रूप में मॉडल करते हैं। वे यूनिफॉर्म डिस्ट्रीब्यूशन के तहत IMT लागत के मीन (mean) और वेरिएंस (variance) के लिए क्लोज्ड-फॉर्म एक्सप्रेशंस निकालते हैं, जो "राइट लेवल्स" (फ्रंटियर को अपडेट करना) और "रीड लेवल्स" (बिना लिखे ट्रैवर्स करना) के बीच अंतर करते हैं।
अनुभवजन्य सत्यापन (Empirical Validation): दोनों प्रिमिटिव के लिए स्वतंत्र कॉन्ट्रैक्ट्स को बेस सेपोलिया (Base Sepolia) टेस्टनेट पर तैनात किया गया था। प्रयोगों में 1 से 25 तक की ट्री डेप्थ को कवर करने के लिए डेप्थ स्वैप किया गया।
- IMT: वेरिएंस को कैप्चर करने के लिए प्रत्येक डेप्थ के लिए $\max(d, 2)$ अपेंड्स के साथ टेस्ट किया गया।
- PHDAG: लागत वितरण और वेरिएंस को समझने के लिए 200-अपेंड रन के माध्यम से टेस्ट किया गया।
- मेट्रिक्स: स्थिर-अवस्था प्रदर्शन (steady-state performance) पर ध्यान केंद्रित करने के लिए प्रारंभिक कोल्ड-स्टोरेज इनिशियलाइजेशन लागत को छोड़कर, ट्रांजैक्शन रिसीट्स से गैस खपत मापी गई।

मुख्य योगदान (Key Contributions)

1. PHDAG की औपचारिक जटिलता (Formal Complexity of PHDAG)

यह शोध पत्र स्थापित करता है कि PHDAG अपेंड गैस लागत में सख्ती से $O(1)$ है।

तंत्र (Mechanism): प्रत्येक अपेंड एक अद्वितीय पहचानकर्ता (unique identifier) द्वारा की-युक्त तीन अनटच्ड स्टोरेज स्लॉट्स (कोल्ड SSTOREs) में लिखता है, साथ ही एक काउंटर में वार्म राइट (warm write) करता है।
अपरिवर्तनीयता (Invariance): लागत ग्लोबल रजिस्ट्री आकार $n$ और किसी भी ट्री डेप्थ के प्रति अपरिवर्तनीय है। एक ट्रांजैक्शन के लिए एक्सेस लिस्ट ट्रांजैक्शन के प्रारंभ में रीसेट हो जाती है; चूंकि PHDAG हर बार नए स्लॉट्स में लिखता है, इसलिए लागत केवल निश्चित संख्या में ऑपरेशन्स पर निर्भर करती है, न कि कॉन्ट्रैक्ट की स्थिति पर।
पुनर्निर्माण (Reconstruction): यह शोध पत्र सिद्ध करता है कि संपूर्ण रजिस्ट्री को सार्वजनिक इवेंट लॉग्स से $O(|V|)$ समय में पुनर्गठित किया जा सकता है, क्योंकि इवेंट स्ट्रीम कैनोनिकल हिस्ट्री को वहन करती है।

2. IMT के लिए स्टोकेस्टिक मॉडल (Stochastic Model for IMT)

लेखक यह व्युत्पन्न करते हैं कि IMT प्रति-इंसर्ट लागत $i$ (लीफ इंडेक्स) पर निर्भर एक रैंडम वेरिएबल $g$ है:

मीन (Mean): $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$ , जहाँ $c_L$ और $c_R$ क्रमशः राइट और रीड लेवल्स की मार्जिनल लागत हैं।
वेरिएंस (Variance): $Var[g] = (c_L - c_R)^2 \frac{d}{4}$ ।
निहितार्थ (Implication): हालांकि डेप्थ बढ़ने के साथ रिलेटिव वेरिएंस (कोएफिशिएंट ऑफ वेरिएशन) कम होता जाता है, लेकिन एब्सोल्यूट स्टैंडर्ड डेविएशन $\Theta(\sqrt{d})$ के रूप में बढ़ता है, जो उच्च-डेप्थ रजिस्ट्रियों के लिए परिचालन अनिश्चितता पैदा करता है।

3. अनुभवजन्य क्रॉसओवर और सत्यापन (Empirical Crossover and Validation)

PHDAG प्रदर्शन: प्रति अपेंड 76,276 गैस पर मापा गया (स्टैंडर्ड डेविएशन $\approx 6$ गैस), जो डेप्थ इनवेरिएंस की पुष्टि करता है।
IMT प्रदर्शन: लागत डेप्थ के साथ रैखिक रूप से बढ़ी।
क्रॉसओवर पॉइंट: वह डेप्थ जिस पर PHDAG, IMT से सस्ता हो जाता है, $d \approx 6$ से $7.2$ पर पहचाना गया।
- $d=6$ पर, मापी गई IMT लागत ( $\approx 78,000$ गैस) PHDAG की लागत से अधिक थी।
- लाइफटाइम-एवरेज क्रॉसओवर (यूनिफॉर्म इंडेक्स डिस्ट्रीब्यूशन) को $d^* \approx 7.2$ पर कैलकुलेट किया गया है।

परिणाम (Results)

अनुभवजन्य डेटा सैद्धांतिक मॉडलों को मान्य करता है:

PHDAG नगण्य वेरिएंस और सभी परीक्षण की गई डेप्थ के लिए स्थिर लागत प्रदर्शित करता है।
IMT रैखिक लागत वृद्धि और बढ़ती एब्सोल्यूट वेरिएंस प्रदर्शित करता है।
प्रोडक्शन संदर्भ (Production Context): सर्वेक्षण किए गए प्रत्येक प्रोडक्शन रजिस्ट्री (टोनाडो कैश, सेमाफोर, zkSync, स्क्रॉल, लिनिया) $d \ge 20$ की डेप्थ पर काम करती है। फलस्वरूप, ऐसे सभी सिस्टम वर्तमान में उस क्षेत्र में संचालित हो रहे हैं जहाँ PHDAG स्पष्ट रूप से सस्ता है और अनुमानित लागत प्रदान करता है, बशर्ते कि एप्लिकेशन को संक्षिप्त समावेश प्रमाणों की आवश्यकता न हो।

महत्व और दावे (Significance and Claims)

शोध पत्र का दावा है कि PHDAG प्रिमिटिव उन अपेंड-ओनली प्रूवेनेंस रजिस्ट्रियों के लिए बेहतर विकल्प है जहाँ:

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

लेखक निष्कर्ष निकालते हैं कि PHDAG एथेरियम प्रूवेनेंस इंफ्रास्ट्रक्चर के लिए एक समान इंटरफेस के रूप में मानकीकरण के लिए एक मजबूत उम्मीदवार है, जो गैर-ZK अनुप्रयोगों के लिए डेप्थ-डिपेंडेंट IMT के मुकाबले एक कॉन्स्टेंट-कॉस्ट, डेप्थ-इनवेरिएंट विकल्प प्रदान करता है।