💻 computer science

Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

यह शोध पत्र "स्प्लिट टैलीज़" (Split Tallies) को प्रस्तुत करता है, जो एक निरंतर-मेमोरी ऑडिटिंग योजना है जो एक डिस्क्रीट सर्टिफिकेट कैलकुलस के माध्यम से अधिकतम अंतराल (maximal gaps) को ट्रैक करके एक अविश्वसनीय पक्ष द्वारा बनाए गए गतिशील क्रमबद्ध सेटों को सत्यापित करती है, जो कम्प्यूटेशनल रूप से असीमित विरोधियों के विरुद्ध उच्च-संभाव्यता सुरक्षा प्राप्त करती है और यह सिद्ध करती है कि छिपे हुए यादृच्छिकता (randomness) या टाइमस्टैम्प के बिना ऐसी दक्षता असंभव है।

मूल लेखक: Faruk Alpay, Levent Sarioglu

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

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

CC BY 4.0

मूल लेखक: Faruk Alpay, Levent Sarioglu

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

कल्पना कीजिए कि आपके पास एक बहुत ही बुद्धिमान, लेकिन संभावित रूप से बेईमान लाइब्रेरियन (जिसे मेंटेनर कहा जाता है) है जो किताबों को एक आदर्श क्रम में व्यवस्थित करने वाली एक लाइब्रेरी का प्रबंधन करता है। आप (यूजर) सवाल पूछते हैं जैसे "क्या किताब X यहाँ है?" या "Y से ठीक पहले कौन सी किताब है?" लाइब्रेरियन तुरंत जवाब देता है। हालाँकि, आपको लाइब्रेरियन की आंतरिक स्मृति (मेमोरी) पर भरोसा नहीं है, और आप हर बार सवाल पूछने पर उनकी अलमारियों की जाँच नहीं कर सकते क्योंकि वह बहुत धीमा होगा।

आपको बाद में यह सत्यापित करने का एक तरीका चाहिए कि लाइब्रेरियन द्वारा दिया गया प्रत्येक उत्तर वास्तव में सही था, बिना खुद पूरी लाइब्रेरी को याद रखे।

यह पेपर स्प्लिट टैलीज़ (Split Tallies) नामक एक सिस्टम पेश करता है जो इस समस्या को हल करता है। यह प्राचीन लेखांकन इतिहास और आधुनिक गणित के एक चतुर मिश्रण का उपयोग करता है ताकि एक "प्रमाणपत्र" बनाया जा सके जो यह साबित करे कि लाइब्रेरियन सच बोल रहा है, जिसमें आपकी ओर से लगभग शून्य मेमोरी का उपयोग होता है।

यह कैसे काम करता है, इसे सरल अवधारणाओं में यहाँ समझाया गया है:

1. प्राचीन रूपक: स्प्लिट स्टिक (विभाजित छड़ी)

यह विचार 600 साल पुराने अंग्रेजी "टैली स्टिक्स" (तुलनात्मक छड़ियों) से प्रेरित है।

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

2. मुख्य युक्ति: किताबों के बजाय "अंतरालों" (Gaps) को ट्रैक करना

अधिकांश लोग लाइब्रेरी को किताबों की एक सूची के रूप में देखते हैं। यह पेपर कहता है: "नहीं, खाली स्थानों (गैप्स) के बारे में सोचें।"

कल्पना करें कि लाइब्रेरी की शेल्फ का एक प्रारंभ (0) और एक अंत (U) है।
यदि शेल्फ खाली है, तो शुरुआत से अंत तक एक विशाल अंतराल (गैप) है।
यदि आप एक किताब जोड़ते हैं, तो आप उस बड़े अंतराल को दो छोटे अंतरालों में विभाजित (split) करते हैं।
यदि आप एक किताब हटाते हैं, तो आप दो अंतरालों को वापस एक में विलय (merge) करते हैं।

पेपर यह सिद्ध करता है कि यदि आप जानते हैं कि अंतराल वास्तव में कैसे जुड़े हुए हैं, तो आप जानते हैं कि हर किताब कहाँ है। लाइब्रेरियन केवल यह नहीं कहता कि "किताब X यहाँ है"; उन्हें उस विशिष्ट अंतराल (gap) की ओर संकेत करना चाहिए जो उसे सिद्ध करता है।

3. खेल के नियम (द इंडेंचर)

लाइब्रेरियन को झूठ बोलने से रोकने के लिए, सिस्टम उन्हें सख्त नियमों का पालन करने के लिए मजबूर करता है, जैसे कि सख्त समय के साथ म्यूजिकल चेयर्स का खेल:

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

4. यह इतना कुशल क्यों है?

पेपर का दावा है कि यह सिस्टम अविश्वसनीय रूप से हल्का है:

आपके लिए (ऑडिटर): आपको केवल 5 नंबर और एक "फ्लैग" (हाँ/ना स्विच) याद रखने की आवश्यकता है। आपको लाइब्रेरी, किताबें या इतिहास को स्टोर करने की आवश्यकता नहीं है। आप बस खांचों (notches) के प्रवाह को देखते हैं।
लाइब्रेरियन के लिए: उन्हें किताबों के प्रति एक अतिरिक्त नंबर के बराबर थोड़ी अतिरिक्त जगह (extra space) की आवश्यकता होती है ताकि अंतराल की आईडी को स्टोर किया जा सके।
लागत: यदि लाइब्रेरियन धोखाधड़ी करने की कोशिश करता है, तो उनके सफल होने की संभावना अत्यंत कम है (दस लाख ऑपरेशनों के लिए एक ट्रिलियन में से एक से भी कम)।

5. "असंभव" भाग

लेखकों ने यह भी सिद्ध किया कि आप इस सिस्टम को सरल बनाए बिना इसे तोड़ देंगे:

कोई रैंडमनेस (यादृच्छिकता) नहीं? यदि आप गुप्त रैंडम नंबर का उपयोग नहीं करते हैं, तो एक चतुर झूठा हमेशा आपको धोखा दे सकता है।
कोई गोपनीयता नहीं? यदि लाइब्रेरियन को आपका गुप्त नंबर पता चल जाए, तो वे गणित को फर्जी बना सकते हैं।
कोई समय सीमा नहीं? यदि लाइब्रेरियन को "भविष्य" की आईडी उद्धृत करने की अनुमति दी जाती है (टाइम ट्रैवल), तो वे एक पूर्ण फर्जी लाइब्रेरी बना सकते हैं जो वास्तविक दिखती है। "क्लॉक" नियम इसे रोकने के लिए आवश्यक है।

6. "रीबैलेंसिंग" बोनस

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

सारांश

यह पेपर गतिशील सूचियों (dynamic lists) के लिए एक गणितीय झूठ पकड़ने वाला यंत्र (lie detector) बनाता है।

लाइब्रेरियन काम करता है।
ऑडिटर लगभग कुछ नहीं करता (केवल 5 नंबर)।
टैली "खांचों" का एक सार्वजनिक रिकॉर्ड है।
परिणाम: आप लगभग 100% निश्चितता के साथ सत्यापित कर सकते हैं कि दिया गया प्रत्येक उत्तर सही था, भले ही लाइब्रेरियन आपको ठगने की कोशिश करने वाला एक सुपर-कंप्यूटर हो, और भले ही आपके पास डेटा स्टोर करने के लिए लगभग कोई मेमोरी न हो।

यह एक बैंक खाते के बैलेंस की जांच करने जैसा है, जिसमें आप हर एक सिक्के को गिनने के बजाय केवल एक रसीद देखते हैं जो यह सिद्ध करती है कि गणित सही है।

तकनीकी सारांश: स्प्लिट टैलीज़ (Split Tallies): निरंतर मेमोरी में डायनेमिक ऑर्डर्ड सेट्स के ऑडिटिंग के लिए एक डिस्क्रीट सर्टिफिकेट कैलकुलस

समस्या विवरण

यह शोध पत्र एक प्रतिकूल पक्ष (रखने वाले/maintainer) द्वारा बनाए गए डायनेमिक ऑर्डर्ड सेट्स (dynamic ordered sets) के सत्यापन को संबोधित करता है, जिसे एक उपभोक्ता द्वारा क्वेरी किया जाता है। आधुनिक कंप्यूटिंग के कई परिदृश्यों में, डेटा संरचनाएं अविश्वसनीय वातावरण (जैसे, रिमोट सेवाएं, अपारदर्शी हार्डवेयर एक्सेलेरेटर, या प्रोक्योर की गई लाइब्रेरी) में रहती हैं। उपभोक्ता ऑपरेशन (इंसर्शन, डिलीशन, मेंबरशिप टेस्ट, प्रेडेसेसर/सक्सेसर क्वेरी और एक्सट्रीमम क्वेरी) जारी करता है और तुरंत प्राप्त उत्तरों पर कार्य करता है।

मुख्य चुनौती पूरे ऑपरेशन्स के इतिहास का एक सत्यता प्रमाण (certificate of correctness) प्रदान करना है, बिना उपभोक्ता (ऑडिटर) द्वारा स्वयं डेटा संरचना को स्टोर करने या ऑपरेशन्स को पुनः निष्पादित करने की आवश्यकता के। ऑडिटर को निष्क्रिय (passive) होना चाहिए, जो केवल एक निश्चित मात्रा में स्टेट (विशेष रूप से, पांच मशीन वर्ड्स और एक फ्लैग) स्टोर करता है, जबकि मेंटेनर प्रत्येक ऑपरेशन के लिए एक सार्वजनिक, अपेंड-ओनली सीक्वेंस जिसे टैली (tally) कहा जाता है, में एक छोटा "नॉच" (रिकॉर्ड) जोड़ता है। लक्ष्य यह पता लगाना है कि क्या मेंटेनर ने कभी भी कोई गलत उत्तर दिया है, भले ही मेंटेनर के पास असीमित कम्प्यूटेशनल शक्ति हो और वह दृश्य इतिहास के आधार पर अपनी रणनीति बदल सके।

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

प्रस्तावित समाधान, जिसे स्प्लिट टैलीज़ (Split Tallies) कहा जाता है, ऐतिहासिक लकड़ी के 'टैली स्टिक्स' (tally sticks) से प्रेरित है, जहाँ ऋण को एक स्टिक पर नॉच लगाकर दर्ज किया जाता था, जिसे फिर लंबाई में विभाजित किया जाता था। ऋणदाता (creditor) "स्टॉक" (stock) रखता था और देनदार (debtor) "फॉइल" (foil) रखता था; निपटान के समय, प्रामाणिकता सत्यापित करने के लिए दोनों हिस्सों को आपस में मिलाया जाता था। इस डिजिटल संदर्भ में:

द टैली (The Tally): मेंटेनर द्वारा जोड़ा गया नॉच का एक सार्वजनिक स्ट्रीम।
द स्टॉक (The Stock): ऑडिटर की निजी स्थिति (पांच वर्ड्स और एक फ्लैग)।
द फॉइल (The Foil): मेंटेनर की आंतरिक बुककीपिंग।
द ऑडिट (The Audit): सत्र के अंत में स्टॉक को फॉइल के विरुद्ध "मेश" (mesh) करने की प्रक्रिया।

गैप कैलकुलस (The Gap Calculus)

इस प्रणाली का तकनीकी केंद्र गैप्स का एक डिस्क्रीट कैलकुलस है। सेट $S$ का सीधे ऑडिट करने के बजाय, सिस्टम मैक्सिमल वेकेंट इंटरवल्स (maximal vacant intervals) यानी अंतराल (gaps) के परिवार का ऑडिट करता है जो ऑर्डर्ड यूनिवर्स को विभाजित करते हैं।

प्रतिनिधित्व (Representation): एक यूनिवर्स $\{1, \dots, U\}$ पर सेट $S$ को सेन्टिनल्स $0 $और$ U+1 $को जोड़ने वाले **इंटरलॉकिंग चेन** ऑफ गैप्स$ \langle a, b \rangle$ द्वारा विशिष्ट रूप से दर्शाया जाता है।
नॉर्मल फॉर्म (Normal Form): शोध पत्र सिद्ध करता है कि यह गैप परिवार एक इंटरवल एसाइक्लिक ग्राफ में $0 $से$ U+1$ तक के अद्वितीय यूनिट पाथ (unit path) के अनुरूप है।
रीराइट्स (Rewrites): ऑपरेशन्स को इस पाथ के स्थानीय रीराइट्स के रूप में मॉडल किया गया है:
- इंसर्शन (Insertion): एक गैप $\langle a, b \rangle$ को दो $\langle a, x \rangle, \langle x, b \rangle$ में विभाजित करता है।
- डिलीशन (Deletion): दो आसन्न गैप्स $\langle a, x \rangle, \langle x, b \rangle$ को एक $\langle a, b \rangle$ में मर्ज करता है।
- क्वेरीज़ (Queries): विशिष्ट गैप को प्रदर्शित करके उत्तर दिए जाते हैं (जैसे, मेंबरशिप के लिए $x$ वाला गैप, या प्रेडेसेसर के लिए $x$ से शुरू होने वाला गैप)।

इंडेंचर डिसिप्लिन (The Indenture Discipline)

इन रीराइट्स को बिना स्टेट स्टोर किए ऑडिट करने के लिए, ऑडिटर एक फिंगरप्रिंटिंग तंत्र का उपयोग करता है जो एक परिमित क्षेत्र (finite field) $\mathbb{F}_p$ पर पॉलिनॉमियल आइडेंटिटी टेस्टिंग पर आधारित है:

कोड और टाइमस्टैम्प: प्रत्येक गैप के जन्म को एक सार्वजनिक काउंटर $\kappa$ के माध्यम से एक अद्वितीय कोड (टाइमस्टैम्प) सौंपा जाता है।
साइटेशन (Citations): प्रत्येक ऑपरेशन को उन गैप्स के कोड को उद्धृत (cite) करना चाहिए जिन्हें वह उपभोग (consume) कर रहा है।
एक्युमुलेटर्स (Accumulators): ऑडिटर दो एक्युमुलेटर्स बनाए रखता है, $A$ $A$ (जन्मों के लिए) और $R$ $R$ (उपभोग के लिए)। एक गैप जिसके कोड $c$ $c$ और एंडपॉइंट्स $a, b$ $a, b$ हैं, उसके लिए मान $\nu(a, b, c)$ $ν (a, b, c)$ को फील्ड में मैप किया जाता है।
- जन्म पर: $A \leftarrow A \cdot (z - \nu(a, b, c))$
- उपभोग पर: $R \leftarrow R \cdot (z - \nu(a, b, c))$
- यहाँ, $z$ एक गुप्त फील्ड एलिमेंट है जिसे ऑडिटर द्वारा सत्र से पहले चुना जाता है।
सत्यापन (Verification): ऑडिट के समय, मेंटेनर वर्तमान सेट के गैप्स को उनके कोड के साथ प्रकट करता है। ऑडिटर जाँचता है कि क्या घोषित गैप्स एक वैध चेन बनाते हैं और क्या $A = R$ है।

मुख्य तंत्र (Key Mechanisms)

टेम्पोरल रूल (Temporal Rule): एक उद्धृत कोड इवेंट के प्रारंभ में काउंटर मान से कम होना चाहिए। यह मेंटेनर को भविष्य के कोडों का उपयोग करके बैलेंस को चुनी हुई तरह से बनाने से रोकता है।
फोर्सिंग (Forcing): गैप पाथ की विशिष्टता के कारण, किसी भी क्वेरी का सही उत्तर उद्धृत गैप का एक मजबूर फलन (forced function) होता है। यदि मेंटेनर एक ऐसा गैप उद्धृत करता है जो मौजूद नहीं है या लाइव नहीं है, तो उत्तर गैप के गुणों के साथ असंगत होगा, या लेजर असंतुलित हो जाएगा।

मुख्य योगदान और परिणाम

1. ऑडिट थ्योरम (सत्यता और पूर्णता)

शोध पत्र स्थापित करता है कि यह योजना परफेक्टली कम्प्लीट (ईमानदार मेंटेनर हमेशा स्वीकार किए जाते हैं) और $\epsilon$ -साउंड है।

साउंडनेस एरर (Soundness Error): यदि मेंटेनर $T$ ऑपरेशन्स में से एक भी गलत उत्तर देता है, तो स्वीकृति की संभावना अधिकतम $(4T + 1)/p$ है।
पैरामीटर्स: 61-बिट प्राइम $p$ (जैसे, $2^{61}-1$ ) के साथ, एक मिलियन ऑपरेशन्स तक के सत्रों के लिए त्रुटि की संभावना $2^{-38}$ से कम है।
मान्यताएं (Assumptions): इसके लिए किसी कम्प्यूटेशनल हार्डनेस धारणा की आवश्यकता नहीं है; यह एक अनबाउंडेड एडवरसरी के विरुद्ध सूचना-सैद्धांतिक (information-theoretic) सुरक्षा प्रदान करता है।

2. असंभवता और आवश्यकता के परिणाम

शोध पत्र सिद्ध करता है कि विशिष्ट डिज़ाइन विकल्प अनिवार्य हैं:

डिटरमिनिस्टिक फ्लोर (Deterministic Floor): कोई भी डिटरमिनिस्टिक ऑडिटर, जिसका एंड-ऑफ-सेशन साउंडनेस हो, $n$ आकार के सेट के लिए कम से कम $2n - \log_2(2n+1)$ बिट्स का स्टेट स्टोर करेगा। यह सिद्ध करता है कि रैंडमनेस (यादृच्छिकता) एक आवश्यकता है, न कि केवल एक सुविधा।
सीक्रेट रैंडमनेस (Secret Randomness): यदि ऑडिटर के रैंडम कॉइन्स मेंटेनर को दिखाई देते हैं, तो साउंडनेस एरर 1 हो जाता है (मेंटेनर हमेशा ट्रांसक्रिप्ट को जालसाजी कर सकता है)। मूल्यांकन बिंदु $z$ की गोपनीयता आवश्यक है।
टेम्पोरल रूल की आवश्यकता: भविष्य के कोडों को उद्धृत करने से रोकने वाले नियम के बिना, एक स्पष्ट तीन-ऑपरेशन वाली जालसाजी संभव है जो सटीक संतुलन प्राप्त करती है और 1 की संभावना के साथ स्वीकार की जाती है।

3. मेंटेनर कार्यान्वयन

शोध पत्र एक लीफ-ओरिएंटेड (2, 4)-ट्री का उपयोग करके एक ठोस कार्यान्वयन प्रदान करता है:

जटिलता (Complexity): ऑपरेशन्स $O(\log n)$ वर्स्ट-केस टाइम में चलते हैं।
ओवरहेड (Overhead): इस संरचना को प्रत्येक तत्व के लिए केवल एक अतिरिक्त शब्द (गैप कोड स्टोर करने के लिए) की आवश्यकता होती है।
ऑडिटेड रीबैलेंसिंग: शोध पत्र एक अटेस्टेशन एनवेलप (attestation envelope) पेश करता है जो $m$ अपडेट्स के दौरान स्ट्रक्चरल इवेंट्स (स्प्लिट्स, फ्यूजन्स, शेयर्स) की संख्या को अधिकतम $2m$ के रूप में प्रमाणित करता है। यह सीमा एक-शब्द अटेस्टेशन द्वारा प्रमाणित की जाती है जिसे मेंटेनर द्वारा जोड़ा जाता है, जिससे अमोर्टाइज्ड एनालिसिस को एक सार्वजनिक रूप से सत्यापन योग्य दावे में बदल दिया जाता है।

4. चेकपॉइंट्स और एपॉक्स (Checkpoints and Epochs)

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

महत्व और दायरा

शोध पत्र डायनेमिक ऑर्डर्ड सेट्स के लिए कॉन्स्टेंट-मेमोरी ऑडिटिंग का एक क्लोज्ड अकाउंट प्रदान करने का दावा करता है। इसका महत्व यहाँ है:

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

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