भाग III: क्रिप्टोग्राफ़ी अनुसंधान से आधार¶
हम Sibuna के दो proof-of-work टियर के पीछे के लागत मॉडल निकालते हैं, Cohen-Pietrzak के अनुक्रमिक कार्य के प्रमाण (Proof of Sequential Work) को उसके सुरक्षा तर्क के साथ प्रस्तुत करते हैं, और चैलेंज तथा सत्र के लिए कुंजी-युक्त हैश प्रमाणीकरण का औचित्य बताते हैं। SID 0006 धारणाएँ और संदर्भ दर्ज करता है।
Hashcash: टियर एक का गणित¶
परिभाषा और लागत¶
चैलेंज स्ट्रिंग \(C\) और \(b\) बिट की कठिनाई के लिए Sibuna की टियर एक पहेली यह है: ऐसा \(N \in \mathbb{N}\) खोजें कि \(\text{SHA-256}(C \parallel \text{":"} \parallel \mathrm{dec}(N))\) में \(b\) शुरुआती शून्य बिट हों। नॉनस को दशमलव रूप में लिखना जानबूझकर है; इससे WebAssembly सॉल्वर, JavaScript फ़ॉलबैक और नेटिव सत्यापनकर्ता के बीच वायर प्रारूप बिना किसी बाइनरी एन्कोडिंग चरण के एक समान रहता है।
कठिनाई की इकाई एक अपेक्षित हैश प्रयास (hash trial) है, compression फ़ंक्शन की कॉल नहीं। एक इनपुट कई SHA-256 ब्लॉक घेर सकता है। प्रीफ़िक्स की पूर्व-गणना भी प्रति नॉनस कार्य बदल सकती है। वायर नियम डाइजेस्ट प्रेडिकेट ही रहता है; इम्प्लीमेंटेशन को स्टेटमेंट और नॉनस एन्कोडिंग पर सहमत होना चाहिए, अनुमानित CPU लागत पर नहीं।
स्वतंत्र आदर्श डाइजेस्ट के लिए प्रयास संख्या \(X\), \(p = 2^{-b}\) के साथ ज्यामितीय है। इसकी माध्यिका \(\left\lceil \ln(1/2) / \ln(1-p) \right\rceil\) है, जो छोटे \(p\) के लिए लगभग \(2^b \ln 2\) है, और इसका प्रसरण \((1-p)/p^2\) है। सत्यापनकर्ता खोज करने के बजाय एक उम्मीदवार डाइजेस्ट की जाँच करता है। पार्सिंग, चैलेंज प्रमाणीकरण, फ़िंगरप्रिंट जाँच, spent-state में प्रविष्टि और रिस्पॉन्स अतिरिक्त कार्य हैं। किसी प्रिमिटिव के समय-माप को उलटकर सर्वर की बाढ़ सहने की क्षमता नहीं निकाली जा सकती।
खोज की दो सीमाएँ¶
पहली सीमा प्रसरण है: लंबी खोज का अर्थ यह नहीं कि वर्कर खराब है। दूसरी सीमा समानांतरता है: स्वतंत्र नॉनस प्रयास एक साथ चल सकते हैं। अधिक कोर खोज में बीता समय घटाते हैं, भले ही अपेक्षित कुल प्रयास संख्या वही रहे। इसलिए प्रवेश नीति के लिए हार्डवेयर थ्रूपुट मायने रखता है। न कोई दावा की गई हैश दर और न कोई अकेला बेंचमार्क हर अनुरोधकर्ता के लाभ को सीमित कर सकता है।
अनुक्रमिक कार्य का प्रमाण: टियर दो¶
अनुक्रमिक कार्य क्यों¶
अनुक्रमिक कार्य वाला निर्माण गणनाओं के बीच निर्भरताएँ लाता है: बाद के लेबल को पहले बना मान चाहिए। यह कुल कार्य से अलग एक मात्रा को संबोधित करता है, यानी गणना की गहराई। स्वतंत्र पहेलियाँ फिर भी समानांतर चल सकती हैं, और हार्डवेयर की हैश लेटेंसी फिर भी मायने रखती है।
Sibuna, Cohen और Pietrzak द्वारा वर्णित हैश-आधारित निर्माण का अनुसरण करता है। इसके ग्राफ़ में गहराई \(n\) पर \(2^{n+1}-1\) लेबल होते हैं, लेकिन लेबल की निश्चित संख्या ब्राउज़र की निश्चित लेटेंसी नहीं है: लेबल कई compression ब्लॉक में फैल सकते हैं, ओपनिंग सबट्री की दोबारा गणना कर सकती हैं, और शेड्यूलिंग भिन्नता जोड़ती है। oracle-model विश्लेषणों से मिले सुरक्षा कथनों को हर ठोस इम्प्लीमेंटेशन या विरोधी के बारे में बिना शर्त दावे में नहीं बदलना चाहिए।
निर्माण¶
मान लें \(n\) गहराई है, और उस पूर्ण बाइनरी ट्री पर विचार करें जिसके नोड अधिकतम \(n\) लंबाई की बाइनरी स्ट्रिंग से नामित हैं (रूट \(\varepsilon\), चाइल्ड \(v0\) और \(v1\), लीफ़ की लंबाई \(n\))। हर नोड \(v\) एक 32-बाइट लेबल \(\ell_v = H(\chi, v, \mathrm{parents}(v))\) रखता है, जहाँ \(\chi\) चैलेंज स्टेटमेंट है और \(H\) वह SHA-256 है जिसमें \(\chi\) एक बार सोखा गया है (Hashcash सॉल्वर वाली ही प्रीफ़िक्स तरकीब):
- आंतरिक नोड अपने दो चाइल्ड का हैश करता है: \(\ell_v = H(\chi, v, \ell_{v0}, \ell_{v1})\);
- लीफ़ \(u = u_1 \dots u_n\) उन सभी स्थानों पर अपने पूर्वजों के बाएँ सहोदरों का हैश करती है जहाँ रूट से आने वाला पाथ दाईं ओर मुड़ा: \(\ell_u = H(\chi, u, \{\ell_{u_1 \dots u_{i-1} 0} : u_i = 1\})\)।
बाएँ-सहोदर वाले किनारे ही गणना को अनुक्रमिक बनाती हैं: लीफ़ \(u\) का लेबल तब तक नहीं बन सकता जब तक उसके बाईं ओर का हर सबट्री पूरा न हो जाए, इसलिए depth-first post-order traversal अनिवार्य हो जाता है और रूट लेबल \(\varphi = \ell_\varepsilon\) क्रम से सभी \(2^{n+1} - 1\) लेबल पर निर्भर करता है।
ओपनिंग। \(\varphi\) की गणना के बाद प्रूवर Fiat-Shamir से \(t\) लीफ़ निकालता है, \(\gamma_i = H(\chi \parallel \varphi \parallel i) \bmod 2^n\), और हर एक के लिए लीफ़ लेबल तथा रूट पाथ पर पड़ने वाले \(n\) सहोदर लेबल भेजता है। सत्यापनकर्ता उन सहोदरों से लीफ़ की दोबारा गणना करता है जो उसके पैरेंट हैं, पाथ से ऊपर की ओर हैश करता है, और जाँचता है कि वह \(\varphi\) तक पहुँचता है। सत्यापनकर्ता की लागत सीमित वर्कस्पेस के साथ \(O(tn)\) लेबल गणनाएँ है। एक लेबल गणना कई हैश ब्लॉक में फैल सकती है; लेबल गिनना compression कॉल गिनना नहीं है।
fn verify_opening(base: &Sha256, n: u8, phi: &Label, gamma: u32, opening: &[Label]) -> bool {
let Some((leaf, siblings)) = opening.split_first() else {
return false;
};
// `siblings` गहराई n से गहराई 1 तक चलता है; उलटने पर यह गहराइयों 1..=n से जोड़ा बनाता है।
let mut hasher = node_hasher(base, n, gamma);
for (d, sibling) in (1..=n).zip(siblings.iter().rev()) {
if turns_right(gamma, n, d) {
hasher.update(sibling);
}
}
if hasher.finalize() != *leaf {
return false;
}
let mut current = *leaf;
for (d, sibling) in (1..=n).rev().zip(siblings) {
let mut parent = node_hasher(base, d - 1, gamma >> (n - d + 1));
if turns_right(gamma, n, d) {
parent.update(sibling);
parent.update(¤t);
} else {
parent.update(¤t);
parent.update(sibling);
}
current = parent.finalize();
}
current == *phi
}
सैंपलिंग, सुदृढ़ता और उनकी सीमाएँ¶
एक निश्चित कमिटमेंट पर विचार करें जिसमें स्वतंत्र रूप से पहचाना जा सकने वाला खराब अंश \(\alpha\) है। यदि हर ओपनिंग समान रूप से और स्वतंत्र रूप से सैंपल करती है, तो \(t\) ओपनिंग में हर खराब स्थान के छूट जाने की संभावना \((1-\alpha)^t\) है। यह प्रारंभिक गणना समझाती है कि अधिक ओपनिंग क्यों मदद करती हैं। यह अपने आप में अनुक्रमिक कार्य वाले प्रोटोकॉल का सुरक्षा प्रमाण नहीं है।
संदर्भित अनुक्रमिक कार्य वाले निर्माण का oracle model में सुरक्षा विश्लेषण है। Sibuna के domain separation, पैरामीटर मैपिंग, truncation और इम्प्लीमेंटेशन को फिर भी निर्माण की धारणाओं के विरुद्ध जाँचना होगा। Fiat-Shamir सैंपलिंग ओपनिंग को कमिटमेंट से दोबारा बनाने योग्य बनाती है; केवल दोबारा बनाने योग्य होना grinding के प्रति प्रतिरोध सिद्ध नहीं करता। हम कोई बिना शर्त दावा नहीं करते कि धोखा देना कभी सस्ता नहीं होता।
प्रूवर की मेमोरी¶
एक सीधा-सादा प्रूवर हर लेबल (\(2^{n+1} - 1\) लेबल) संग्रहीत करता है। Sibuna का प्रूवर पहले पास के दौरान मौजूदा पाथ के बाएँ-सहोदर लेबल का एक स्टैक (\(n + 1\) लेबल) रखता है और केवल ऊपर के \(m = \min(n, 10)\) स्तर (\(2^{m+1} - 1\) लेबल, अधिकतम 64 KB) बनाए रखता है। किसी लीफ़ को खोलने के लिए वह लीफ़ के गहराई \(m\) वाले पूर्वज के सबट्री की दोबारा गणना करता है, यानी \(2^{n-m+1} - 1\) हैश, और रखे गए स्तरों से स्टैक को प्रारंभ करता है। प्रूवर की कुल लागत \(2^{n+1} - 1 + t\,(2^{n-m+1} - 1)\) हैश है, और आउटपुट प्रमाण सहित पूरा वर्कस्पेस 100 KB से कम है: ब्राउज़र टैब और नेटिव परीक्षण एक ही Workspace प्रकार (sibuna_pow::posw::Workspace) साझा करते हैं।
पैरामीटर समय-माप नहीं हैं¶
Sibuna वर्क बिट्स को \(n = b - 3\) से गहराई में बदलता है, जिसे समर्थित अंतराल \([4, 24]\) में सीमित किया जाता है। यह कार्य के पैमाने की एक परिपाटी है, एल्गोरिदम के बीच बराबर वास्तविक समय की गारंटी नहीं। एक लीफ़ कई पैरेंट लेबल का हैश कर सकती है, जबकि Hashcash बार-बार एक नॉनस परखता है। कंपाइलर, ब्राउज़र, प्रोसेसर और पैरामीटर के चुनाव, सभी उनकी सापेक्ष लागतों को प्रभावित करते हैं। कमिट किया गया प्रिमिटिव बेंचमार्क सत्यापन को मापता है; वह ब्राउज़र में हल की लेटेंसी स्थापित नहीं करता।
प्रमाण का आकार \(32(1 + t(n+1))\) बाइट है। सोलह ओपनिंग के साथ गहराई 13 पर यह \(32(1 + 16 \times 14) = 7200\) बाइट है। ओपनिंग की संख्या बढ़ाने से प्रमाण और सत्यापनकर्ता का कार्य, दोनों बढ़ते हैं, भले ही ट्री बनाने की प्रमुख लागत वही रहे।
निर्माण का चुनाव¶
प्रासंगिक तुलना संसाधन बजट की है, किसी एल्गोरिदम की प्रतिष्ठा की नहीं। प्रूवर की मेमोरी, सत्यापनकर्ता का सबसे खराब स्थिति वाला कार्य, प्रमाण के बाइट, और दावा किए गए गुण के लिए आवश्यक धारणाएँ दर्ज करें। memory-hard खोज उपयोगी हो सकती है, लेकिन जिस सत्यापनकर्ता को महँगा कार्य दोहराना पड़े, वह हमलावर को सर्वर के संसाधन खर्च कराने की एक और जगह देता है। सार्वजनिक रूप से सत्यापित की जा सकने वाली delay निर्माण साझा सीक्रेट वाले गेट से भिन्न विश्वास मॉडल की सेवा करते हैं।
Sibuna सस्ता हैश सत्यापन और हैश-आधारित अनुक्रमिक कार्य का विकल्प बनाए रखता है। अनुक्रमिक कार्य के लिए अधिक प्रमाण बाइट और अधिक सावधान पैरामीटर विश्लेषण चाहिए। कोई भी चुनाव महँगे सत्यापन में प्रवेश से पहले विकृत प्रमाणों को अस्वीकार करने की आवश्यकता को नहीं हटाता।
सममित प्रमाणीकरण: चैलेंज और सत्र¶
जारीकर्ता ही सत्यापनकर्ता है¶
डिजिटल हस्ताक्षर सार्वजनिक कुंजी रखने वाले किसी को भी सत्यापन करने देता है, जो तब सही उपकरण है जब सत्यापनकर्ताओं को टोकन बनाने (mint) में सक्षम नहीं होना चाहिए। Sibuna का सत्यापनकर्ता ही जारीकर्ता है (या एक सीड साझा करने वाला क्लस्टर)। pseudorandom फ़ंक्शन से बना message authentication code उस विश्वास क्षेत्र के भीतर प्रमाणीकरण देता है। यह सार्वजनिक सत्यापन नहीं देता: MAC कुंजी रखने वाला कोई भी टोकन बना भी सकता है। बेंचमार्क अध्याय लागू किए गए टोकन संचालनों की तुलना करता है।
दीर्घकाल के लिए एक दूसरा परिणाम मायने रखता है: Ed25519 elliptic-curve समूह में discrete logarithm पर टिका है, जिसे Shor का एल्गोरिदम तोड़ देता है; कुंजी-युक्त हैश केवल हैश फ़ंक्शन पर टिका है, जिसके विरुद्ध क्वांटम एल्गोरिदम अधिकतम द्विघाती गति-वृद्धि देते हैं। Sibuna उन डिप्लॉयमेंट के लिए Ed25519 को एक विकल्प (--token-scheme ed25519) के रूप में रखता है जिन्हें टोकन न बना सकने वाले सत्यापनकर्ता चाहिए।
कुंजी अनुसूची (key schedule)¶
एक 32-बाइट मास्टर सीड (--secret-file, SIBUNA_SECRET से, या एक नए यादृच्छिक मान से) कुंजी-युक्त BLAKE3 और एक domain स्ट्रिंग के साथ हर उद्देश्य की कुंजी निकालता है: टोकन, चैलेंज, Ed25519 और फ़िंगरप्रिंट कुंजियाँ, और वह आवश्यकता कुंजी जो आवश्यकता टिकट को सील करती है (भाग IV)।
pub fn derive(seed: &Seed) -> Keys {
Keys {
token: subkey(seed, "sibuna/token/v1"),
challenge: subkey(seed, "sibuna/challenge/v1"),
ed25519_seed: subkey(seed, "sibuna/ed25519/v1"),
fingerprint: subkey(seed, "sibuna/fingerprint/v1"),
requirement: subkey(seed, "sibuna/requirement/v1"),
}
}
fn subkey(seed: &Seed, purpose: &str) -> [u8; 32] {
blake3::keyed_hash(seed.as_bytes(), purpose.as_bytes())
}
क्लस्टर में Keys::bind_node चैलेंज कुंजी को sibuna/challenge-node/v1 और नोड id पर उसी कुंजी के तहत कुंजी-युक्त BLAKE3 से बदल देता है, इसलिए चैलेंज को उसी नोड पर लौटना होगा जिसने उसे जारी किया, जबकि सत्र टोकन और आवश्यकता टिकट हर सदस्य पर वैध रहते हैं।
domain separation उद्देश्यों के बीच आकस्मिक पुनः उपयोग रोकता है; मास्टर सीड के लीक होने से हर व्युत्पन्न कुंजी लीक हो जाती है। क्लस्टर को केवल एक सीड पर सहमत होना होता है।
स्टेटलेस चैलेंज¶
चैलेंज पहचानकर्ता एक स्वयं-प्रमाणित रिकॉर्ड है: संस्करण, एल्गोरिदम, कठिनाई, ओपनिंग की संख्या, जारी करने का समय, क्लाइंट का कुंजी-युक्त फ़िंगरप्रिंट, PRF से निकाला गया नॉनस, और उस नीति नियम का हैश जिसने चैलेंज माँगा, जिसके बाद चैलेंज कुंजी के तहत 16-बाइट टैग आता है। इसे जारी करने में कुछ भी नहीं लिखा जाता। सत्यापन रिकॉर्ड को डिकोड करता है, स्थिर समय में टैग जाँचता है, चैलेंज TTL के विरुद्ध आयु जाँचता है, सबमिट करने वाले क्लाइंट के विरुद्ध फ़िंगरप्रिंट जाँचता है, और उसके बाद ही प्रमाण की जाँच करता है।
spent set 16-बाइट टैग पर Robin Hood open addressing के 16 शार्ड है (भाग V)। फ़िंगरप्रिंट क्लाइंट पते और User-Agent का कुंजी-युक्त हैश है, लंबाई से अलग किया गया ताकि कोई दो इनपुट जोड़ने (concatenation) से टकराएँ नहीं, और कुंजी-युक्त ताकि दूसरे क्लाइंट के फ़िंगरप्रिंट ऑफ़लाइन न निकाले जा सकें।