सामान्य इंटरव्यू: एक Merkle समावेशन प्रमाण (inclusion proof) को सत्यापित करना

प्रॉम्प्ट और दायरा

यह एक क्रिप्टोग्राफ़िक डेटा-संरचना और प्रोटोकॉल कार्यान्वयन समस्या है। एक Merkle समावेशन प्रमाण पूरे ट्री के बजाय लक्ष्य लीफ को रूट से जोड़ने के लिए केवल आवश्यक सिबलिंग नोड्स भेजता है। RFC 9162 लीफ और आंतरिक-नोड हैश को डोमेन-पृथक करता है और सत्यापनकर्ता को प्रत्येक स्तर पर बाएँ और दाएँ का निर्णय लेते समय leaf_index और tree_size का उपयोग करने की आवश्यकता होती है। मान लें कि क्लाइंट ने एक विश्वसनीय चैनल के माध्यम से root_hash प्राप्त किया है; सत्यापनकर्ता उस विश्वास को स्थापित नहीं करता है।

इंटरव्यूअर क्या जांच रहा है

लीफ हैश, आंतरिक हैश और पाथ दिशा जानकारी में अंतर करना।
सीमाओं और पाथ सत्यापन के लिए leaf_index और tree_size का उपयोग करना।
डोमेन पृथक्करण को समझना ताकि लीफ बाइट्स को आंतरिक-नोड इनपुट के साथ भ्रमित न किया जा सके।
O(log n) प्रमाण आकार और सत्यापन समय के साथ-साथ विश्वसनीय-रूट सीमा को समझाना।

पहले पूछे जाने वाले स्पष्टीकरण

ट्री विनिर्देश की पुष्टि करें: RFC 9162 का परिवर्तनीय-आकार (variable-size) वाला ट्री या एक निश्चित पूर्ण बाइनरी ट्री; लीफ कैनोनिकलाइज़ेशन; हैश एल्गोरिथ्म और प्रीफ़िक्स स्थिरांक; और क्या पाथ लीफ से रूट की ओर क्रमबद्ध है। यह भी स्पष्ट करें कि क्या अपेंड-ओनली स्थिरता प्रमाण या हस्ताक्षर आवश्यक हैं, या केवल एक समावेशन प्रमाण। इन सम्मेलनों (conventions) के बिना, हैश की एक सूची विशिष्ट रूप से रूट को परिभाषित नहीं करती है।

30-सेकंड का उत्तर

0 <= leaf_index < tree_size की जाँच करें और पाथ की लंबाई को सीमित करें। लीफ को HASH(0x00 || leaf_bytes) के रूप में कैनोनिकलाइज़ करें, फिर fn = leaf_index, sn = tree_size - 1 और वर्तमान हैश r बनाए रखें। प्रत्येक स्तर पर, सिबलिंग बाएँ है या दाएँ, यह तय करने के लिए fn के निम्न बिट या स्थिति fn == sn का उपयोग करें, आंतरिक प्रीफ़िक्स 0x01 के साथ हैश करें, और दोनों इंडेक्स को शिफ्ट करें। केवल तभी सफल हों जब sn == 0 और r == root_hash हो।

चरण-दर-चरण समाधान

1. इनपुट अनुबंध और डोमेन पृथक्करण तय करें

सत्यापनकर्ता को एक संस्करणयुक्त (versioned) हैश एल्गोरिथ्म, लीफ एन्कोडिंग, पाथ क्रम और ट्री-साइज सिमेंटिक्स की आवश्यकता होती है। RFC 9162 का Merkle Tree Hash पत्तियों (leaves) के लिए 0x00 और आंतरिक नोड्स के लिए 0x01 का उपयोग करता है, जिससे एक ही बाइट स्ट्रिंग को दो भूमिकाओं में व्याख्यायित होने से रोका जा सके। बिना डोमेन पृथक्करण के leaf || sibling को हैश न करें या किसी कॉलर को मनमाने ढंग से प्रीफ़िक्स बदलने की अनुमति न दें।

2. पहले सीमा और संसाधन जाँच करें

leaf_index >= tree_size विफल होना चाहिए; एक खाली ट्री में कोई वैध लीफ नहीं होती है। पाथ को सीमित करें, उदाहरण के लिए ceil(log2(tree_size)) + 1 पर, और प्रत्येक हैश के लिए एक निश्चित बाइट लंबाई की आवश्यकता रखें। पूर्णांक ओवरफ़्लो, नकारात्मक एन्कोडिंग, डुप्लिकेट पार्सिंग और अत्यधिक बड़े पाथ को अस्वीकार करें ताकि शत्रुतापूर्ण प्रमाण असीमित संसाधनों की खपत न कर सकें। एक छोटा पाथ स्वचालित रूप से मान्य नहीं होता है; अंतिम स्थिति को एक ही रूट पर अभिसरित (converge) होना चाहिए।

3. स्तर-दर-स्तर रूट का पुनर्निर्माण करें

RFC 9162 के परिवर्तनीय-आकार वाले ट्री के लिए, केवल समता (parity) पर्याप्त नहीं है: सीमा शर्त fn == sn संयोजन की दिशा को बदल देती है। वर्तमान नोड को उसके पैरेंट से मैप करने के लिए प्रत्येक स्तर के बाद fn और sn दोनों को शिफ्ट करें। स्यूडोकोड:

text

verify(leaf, leafIndex, treeSize, path, expectedRoot):
  if treeSize <= 0 or leafIndex < 0 or leafIndex >= treeSize: return false
  r = HASH(0x00 || leaf)
  fn = leafIndex
  sn = treeSize - 1
  for sibling in path:
    if sn == 0: return false
    if (fn & 1) == 1 or fn == sn:
      r = HASH(0x01 || sibling || r)
    else:
      r = HASH(0x01 || r || sibling)
    fn = fn >> 1
    sn = sn >> 1
  return sn == 0 and r == expectedRoot

4. पाथ और ट्री-साइज की सहमति की जाँच करें

प्रमाण का tree_size दिशा गणना में भाग लेता है; यह केवल सजावटी लॉग मेटाडेटा नहीं है। जब पाथ समाप्त हो जाता है, तो sn शून्य होना चाहिए। यदि यह धनात्मक बना रहता है, तो प्रमाण रूट तक नहीं पहुँचा; यदि sn पहले से ही शून्य है और अधिक सिबलिंग्स शेष हैं, तो प्रमाण को अस्वीकार करें। एक निश्चित-ट्री कार्यान्वयन विभिन्न नियमों का उपयोग कर सकता है, लेकिन इसके जनरेटर और सत्यापनकर्ता को RFC 9162 पाथ के साथ मिलाने के बजाय उसी ट्री सम्मेलन को साझा करना चाहिए।

5. जटिलता, संचार और विश्वास

एक संतुलित ट्री में आमतौर पर O(log n) सिबलिंग हैश होते हैं। सत्यापन में O(log n) हैश संचालन और पाथ से परे O(1) स्थिति लगती है; संचार O(log n * hashSize) है। प्रमाण केवल एक लीफ को आपूर्ति किए गए रूट से बांधता है। यदि रूट किसी अविश्वसनीय प्रतिक्रिया से आया है, तो एक हमलावर रूट और प्रमाण दोनों को बदल सकता है। प्रोडक्शन प्रोटोकॉल हस्ताक्षर, एक विश्वसनीय लॉग हेड, या प्रमाणित ट्रांसपोर्ट के साथ रूट और ट्री साइज की रक्षा करते हैं।

मॉडल उत्तर

मैं सत्यापनकर्ता को एक संस्करणयुक्त ट्री विनिर्देश से बाँधूँगा। पहले tree_size > 0, 0 <= leaf_index < tree_size, हैश लंबाई और पाथ बजट की जाँच करें, फिर r = HASH(0x00 || leaf) की गणना करें। fn = leaf_index और sn = tree_size - 1 बनाए रखें; प्रत्येक स्तर पर सिबलिंग को बाईं ओर रखें जब fn विषम हो या fn == sn हो, अन्यथा दाईं ओर, और HASH(0x01 || left || right) के साथ अपडेट करें। दोनों इंडेक्स को शिफ्ट करें। अंत में, केवल sn == 0 और विश्वसनीय रूट के साथ समानता ही सफल होती है। प्रमाण का आकार और सत्यापन लागत O(log n) है, जबकि प्रोटोकॉल को रूट, ट्री साइज और पाथ क्रम को प्रमाणित करना चाहिए।

सामान्य गलतियाँ

केवल इंडेक्स समता से दिशा चुनना और परिवर्तनीय-ट्री सीमा fn == sn को अनदेखा करना।
पत्तियों और आंतरिक नोड्स के लिए एक ही हैश प्रीफ़िक्स का उपयोग करना, जिससे डोमेन पृथक्करण खो जाता है।
लीफ सीमाओं, पाथ की लंबाई या sn अभिसरण की जाँच किए बिना केवल पुनर्निर्मित रूट की तुलना करना।
किसी अविश्वसनीय प्रतिक्रिया के रूट को प्रमाणीकरण एंकर मानना।
एक ट्री सम्मेलन के साथ निर्माण करना और एक भिन्न पूर्ण-बाइनरी-ट्री नियम के साथ सत्यापित करना।
संस्करणयुक्त अनुबंध से पाथ क्रम, हैश बाइट क्रम, या लीफ कैनोनिकलाइज़ेशन को छोड़ना।

फॉलो-अप प्रश्न

आप एक अपेंड-ओनली स्थिरता प्रमाण को कैसे सत्यापित करेंगे?

एक समावेशन प्रमाण यह उत्तर देता है कि क्या एक लीफ किसी रूट से संबंधित है। एक स्थिरता प्रमाण पुराने और नए दोनों रूट का पुनर्निर्माण करता है और साबित करता है कि पुराना ट्री नए ट्री का प्रीफ़िक्स है। इनपुट में पुराने और नए आकार, एक पाथ और दोनों विश्वसनीय रूट शामिल हैं। इसके स्टेट ट्रांज़िशन भिन्न होते हैं, इसलिए इसे केवल-बूलियन समावेशन फ़ंक्शन के अंदर नहीं छिपाया जाना चाहिए।

केवल पाथ के बजाय tree_size क्यों संचारित करें?

एक परिवर्तनीय-आकार वाले ट्री में, अंतिम नोड का उसके स्तर पर कोई दायां सिबलिंग नहीं हो सकता है। दिशा वर्तमान सबट्री सीमा पर निर्भर करती है। tree_size सत्यापनकर्ता को बताता है कि कौन से नोड्स मौजूद हैं और अतिरिक्त हैश को एक नकली रूट पाथ में तस्करी (smuggle) होने से रोकता है।

आप हैश-एल्गोरिथ्म डाउनग्रेड को कैसे रोकते हैं?

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

डुप्लिकेट लीव्स प्रमाण को कैसे प्रभावित करती हैं?

एक समावेशन प्रमाण बाइट्स को एक स्थिति से बाँधता है; यह यह साबित नहीं करता कि मान केवल एक बार दिखाई देता है। विशिष्टता (uniqueness) के लिए एक अलग कुंजी इंडेक्स या सेट प्रमाण की आवश्यकता होती है। एक एकल Merkle रूट किसी अन्य समान मान के गैर-अस्तित्व को साबित नहीं कर सकता है।

पूरे ट्री को संग्रहीत किए बिना एक जनरेटर वृद्धिशील (incremental) कैसे हो सकता है?

प्रत्येक स्तर पर नवीनतम दाएं हाथ के सबट्री डाइजेस्ट को एक प्रीफ़िक्स संचयक (accumulator) के रूप में रखें और बाइनरी कैरी प्रसार की तरह एक नई लीफ को मर्ज करें। एक पुरानी लीफ को साबित करने के लिए अभी भी आवश्यक सिबलिंग्स या बाहरी स्टोर को बनाए रखने की आवश्यकता होती है; केवल रूट एक पाथ को फिर से नहीं बना सकता है।

सत्यापनकर्ता को अत्यधिक बड़े पाथ को कैसे संभालना चाहिए?

पार्स करने से पहले ट्री साइज और हैश लंबाई से एक सीमा की गणना करें, लंबे पाथ को अस्वीकार करें, और गुणन ओवरफ़्लो से बचने के लिए प्रत्येक तत्व की निश्चित लंबाई की जाँच करें। हैशिंग से पहले संसाधन बजट समाप्त करें ताकि एक विकृत प्रमाण अनंत लूप या बड़े आवंटन को ट्रिगर न कर सके।