डेवलपर टूल · UUID जनरेटर
एक v4 UUID में कितने यादृच्छिक बिट्स होते हैं? 122, नहीं 128
· यह काम किस प्रकार करता है
uuid क्रिप्टोग्राफी ब्राउज़र-एपिस
यादृच्छिक UUID में से छह 128 bits को मानक द्वारा तय किया जाता है, यादृच्छिकता के लिए 122 को छोड़ दिया जाता है। यह पोस्ट दिखाती है कि टकराव की संभावनाओं का ईमानदारी से अनुमान कैसे लगाया जाए और वास्तविक टकराव टूटे हुए जनरेटर से क्यों होते हैं, गणित से नहीं।
वास्तुकार का प्रश्न: क्या हमें कभी डुप्लिकेट मिलेगा? - चिंता कहां से आती है और क्यों इसका उत्तर जनरेटर पर निर्भर करता है
वास्तुकार पूछता है: यदि हम दस वर्षों तक प्रति दिन 10 मिलियन UUID उत्पन्न करते हैं, तो क्या हमें कभी डुप्लिकेट मिलेगा? ईमानदार उत्तर है: लगभग निश्चित रूप से नहीं, यदि जनरेटर क्रिप्टोग्राफ़िक रूप से सुरक्षित है; लगभग निश्चित रूप से हाँ, यदि जनरेटर टूट गया है। RFC 9562 गणित सही है: 122 यादृच्छिक बिट्स के साथ एक v4 UUID में लगभग n² / 2 से 123वीं शक्ति तक टकराव की संभावना होती है, जहां n उत्पन्न पहचानकर्ताओं की संख्या है। अधिकांश वास्तविक प्रणालियों के लिए, यह संभावना नगण्य है। समस्या यह है कि यह सूत्र मानता है कि प्रत्येक बिट वास्तव में यादृच्छिक है। यदि जनरेटर लीक हो जाता है या दोहराया जाता है या पूर्वानुमानित रूप से बीजित किया गया था, तो सूत्र गलत है, और डुप्लिकेट अपरिहार्य हो जाता है। 128-बिट लेआउट में चार संस्करण बिट्स (v4 के लिए 0100) और दो वैरिएंट बिट्स (RFC 9562 के लिए 10) शामिल हैं, जो मानक द्वारा तय और सेट किए गए हैं।
कौन से छह बिट्स के लिए बात की जाती है - चार संस्करण बिट्स और दो वैरिएंट बिट्स, और उन्हें यादृच्छिक के बजाय क्यों सेट किया जाता है
वह यादृच्छिकता के लिए 122 bits छोड़ देता है। फॉर्मूलेशन को कभी-कभी 2 से 122 यादृच्छिक बिट्स कहा जाता है, जो अद्वितीय मान उत्पन्न करता है। जन्मदिन विरोधाभास सन्निकटन का उपयोग करते हुए, n यादृच्छिक रूप से उत्पन्न मानों के बीच कम से कम एक टकराव की संभावना लगभग n² / 2 से 123वें तक है। n = 1 मिलियन के लिए, यह (10^6)² / 2^123 = 10^12 / 9 है। 3 × 10^36, जो लगभग 10^-25 है। n = 10 बिलियन के लिए, यह अभी भी लगभग 10^-16 है। ये "प्रभावी रूप से शून्य" नहीं हैं; वे हैं "आप इसका कभी भी पालन नहीं करेंगे।" जन्मदिन सन्निकटन जोखिम की गणना करने का एक ठोस तरीका देता है: आप जिस UUID को उत्पन्न करने की योजना बना रहे हैं उसे गिनें, उस संख्या का वर्ग करें, 2 से 123वीं घात तक विभाजित करें। यदि जनरेटर ब्राउज़र का crypto.getRandomValues है, तो प्रत्येक बिट ऑपरेटिंग-सिस्टम एन्ट्रॉपी द्वारा समर्थित है। यदि यह एक गणित है.
स्पष्ट शब्दों में जन्मदिन सन्निकटन - n पहचानकर्ताओं के बीच कम से कम एक टकराव की संभावना मोटे तौर पर n वर्ग को 2 से 123 से विभाजित किया जाता है।
किसी अनुपयुक्त या बार-बार स्थिति उत्पन्न करने वाले जनरेटर द्वारा निर्मित UUID के लिए, गणितीय मॉडल टूट जाता है क्योंकि इसकी स्वतंत्रता की धारणा गलत है। एक निश्चित परीक्षण बीज, कॉपी किया गया फिक्स्चर या प्रक्रिया स्नैपशॉट मानों को फिर से चला सकता है, भले ही पाठ में अभी भी संस्करण-4 निबल हो। वे कार्यान्वयन दोष हैं, इस बात का प्रमाण नहीं कि 122-फ़ील्ड गणना ग़लत थी। एक अन्य सांसारिक स्रोत एक ही शाब्दिक पहचानकर्ता को कई फिक्स्चर में कॉपी कर रहा है और बाद में उनके डेटा को मर्ज कर रहा है। डुप्लिकेट की जांच करते समय, जनरेटर, बीज नीति, प्रक्रिया जीवनचक्र और आयात इतिहास को सुरक्षित रखें। एक बार दोहराए गए मान से यह दावा न करें कि स्वतंत्र CSPRNG आउटपुट ने UUID स्थान को समाप्त कर दिया है।
कार्यान्वित उदाहरण - बताई गई उत्पादन दर और समय अवधि को सन्निकटन में प्लग करना, जिसमें प्रत्येक चरण दिखाया गया है ताकि आप अपने स्वयं के आंकड़ों को प्रतिस्थापित कर सकें
रैंडम-स्टेट रीसिंक्रनाइज़ेशन के बिना प्रक्रिया फोर्किंग। एक बग कहाँ Math.random के स्थान पर प्रयोग किया गया crypto.getRandomValues. एक परीक्षण फिक्स्चर जो उसी के साथ हाथ से तैयार किया गया था UUID कई पंक्तियों में और गलती से उत्पादन में उपयोग किया गया था। का एक पुराना संस्करण UUID लाइब्रेरी जिसमें सीमा सीमा या स्थिति बग थी। इनमें से किसी भी परिदृश्य में जन्मदिन सन्निकटन गणित शामिल नहीं है; उनमें टूटा हुआ कार्यान्वयन या परिचालन संबंधी गलतियाँ शामिल हैं। अपने सिस्टम के लिए टकराव के जोखिम की ईमानदारी से गणना करें: की दर की गणना करें UUID पीढ़ी (प्रति सेकंड, प्रति दिन, प्रति वर्ष), इसे उस समय प्रोजेक्ट करें जब सिस्टम चलेगा, और कुल को जन्मदिन सूत्र में प्लग करें। यदि आपका सिस्टम उत्पन्न करता है 100,000 पाँच वर्षों तक प्रति दिन UUID (182 कुल मिलियन), टक्कर की संभावना है (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, जो नगण्य है.
डुप्लिकेट वास्तव में कहां से आते हैं - Math.random बीज, क्लोन वर्चुअल मशीन, कॉपी की गई स्थिति के साथ फोर्कड प्रक्रियाएं, और फिक्स्चर में कॉपी-पेस्ट
यदि आप एक वर्ष के लिए 10 मिलियन प्रति सेकंड (कुल 315 ट्रिलियन) उत्पन्न करते हैं, तो संभावना है (3। 15 × 10^14)² / 2^123 ≈ 10^-10, जो अभी भी लुप्त हो रहा है। ये अनुमान मानते हैं कि प्रत्येक बिट स्वतंत्र और यादृच्छिक है। ToolAcre जनरेटर crypto.getRandomValues का उपयोग करता है, जो आपको CSPRNG-समर्थित यादृच्छिकता देता है; ऑपरेशन ही एकमात्र हिस्सा है जिस पर आपको भरोसा करने की आवश्यकता है। उचित प्राधिकरण जांच को छोड़ने के बहाने के रूप में कभी भी टकराव की संभावना पर भरोसा न करें। UUID कोई पासवर्ड नहीं है, कोई एक्सेस टोकन नहीं है, और कोई रहस्य नहीं है, भले ही वह 122 यादृच्छिक बिट्स हो। विशिष्टता ही लाभ है; अप्रत्याशितता एक अलग (और अधिक महत्वपूर्ण) संपत्ति है जो अनुमान लगाने से रोकती है। जन्मदिन का गणित विशिष्टता को संभालता है; यह जीवनकाल को संबोधित नहीं करता है (क्या यह UUID समाप्त हो जाना चाहिए?), गोपनीयता (क्या इसे भंडारण से पहले हैश करने की आवश्यकता है?), या प्राधिकरण (क्या इस UUID को रखने से कॉल करने वाले के बारे में कुछ भी साबित होता है?)। ToolAcre जनरेटर आपको 122 यादृच्छिक बिट्स के साथ CSPRNG-समर्थित UUID देता है, जिसका अर्थ है कि गणित में अद्वितीयता है और अप्रत्याशितता ध्वनि है। बाकी सब कुछ-टोकन सत्यापन, समाप्ति, पहुंच नियंत्रण-आपके एप्लिकेशन की जिम्मेदारी है। संभाव्यता सूत्र पिछली पीढ़ियों से प्रत्येक उत्पन्न UUID की स्वतंत्रता मानता है। यदि आपका सिस्टम एकल CSPRNG उदाहरण से पहचानकर्ता उत्पन्न करता है, और प्रत्येक कॉल OS से नई यादृच्छिकता खींचता है, तो स्वतंत्रता की धारणा कायम रहती है। यदि आपका सिस्टम कैश्ड CSPRNG स्थिति या OS रीसीडिंग के बिना सीडेड जनरेटर का उपयोग करता है, तो धारणा टूट जाती है। यदि एन्ट्रापी स्रोत समाप्त हो जाता है (लोड के तहत कुछ एम्बेडेड सिस्टम या वर्चुअल मशीनों पर होता है) या यदि प्रक्रियाओं के बीच यादृच्छिक स्थिति को कभी भी रीसेट नहीं किया जाता है (CSPRNG को फिर से सीडिंग किए बिना प्रक्रिया फोर्किंग) तो टकराव का जोखिम नाटकीय रूप से बढ़ जाता है।
इसमें क्या शामिल नहीं है - v1 और v7 विशिष्टता, जो अकेले यादृच्छिकता के बजाय टाइमस्टैम्प और घड़ी अनुक्रम पर निर्भर करती है
ToolAcre फ़ॉलबैक प्रत्येक बाइट सरणी के लिए crypto.getRandomValues को कॉल करता है और कोई एप्लिकेशन-स्तर PRNG स्थिति नहीं रखता है। प्लेटफ़ॉर्म आंतरिक ब्राउज़र और ऑपरेटिंग सिस्टम की ज़िम्मेदारी बनी हुई है। वास्तविक जनरेटर के साथ टकराव का अनुकरण सिद्धांत और टूटे हुए अभ्यास के बीच अंतर दिखाता है। एक ही बीज से शुरू करके Math.random से निर्मित जनरेटर समान अनुक्रम उत्पन्न करेगा; आप पहली UUID टक्कर कुछ सौ से कुछ हज़ार उत्पन्न मानों के भीतर देखेंगे, 2^60 मान (2^122 का वर्गमूल) के बाद नहीं, जैसा कि जन्मदिन सन्निकटन भविष्यवाणी करता है। ध्वनि OS एन्ट्रॉपी से crypto.getRandomValues का उपयोग करने वाला जनरेटर केवल तभी टकराव उत्पन्न करेगा जब सैद्धांतिक संभावना अपरिहार्य हो जाती है (लगभग 2^60 UUIDs), एक संख्या इतनी बड़ी कि आप कभी भी उस तक नहीं पहुंच पाएंगे। एक कमजोर या पुन: उपयोग किए गए एन्ट्रापी स्रोत (खराब ढंग से कार्यान्वित UUID पुस्तकालयों या परीक्षण ढांचे में आम) का उपयोग करने वाला जनरेटर बीच में कहीं टकराव उत्पन्न करेगा।
टेकअवे: गणित पर भरोसा करें, जनरेटर का ऑडिट करें - ToolAcre जनरेटर ब्राउज़र के CSPRNG का उपयोग करता है, जो वह हिस्सा है जिसे नकली नहीं बनाया जाना चाहिए
एक बैच परीक्षण एक कार्यान्वयन को पकड़ सकता है जो एक स्थिरांक लौटाता है या एक स्पष्ट अनुक्रम को दोहराता है, लेकिन एक उत्तीर्ण नमूना भविष्य की विशिष्टता साबित नहीं कर सकता है। जहां भी डुप्लिकेट पहचानकर्ता डेटा को दूषित करेंगे, उत्पादन प्रणालियों को अभी भी एक अद्वितीय बाधा लागू करनी चाहिए। आयात पर विशेष ध्यान देने की आवश्यकता है क्योंकि दो वैध स्रोत प्रणालियों में पहले से ही समान शाब्दिक पहचानकर्ता हो सकते हैं, और फिक्स्चर को पूरे वातावरण में कॉपी किया जा सकता है। ToolAcre के परीक्षण जांचते हैं कि 500 के बैच में 500 विशिष्ट मान हैं; यह इस कार्यान्वयन के लिए एक प्रतिगमन जाँच है, कोई सांख्यिकीय गारंटी नहीं। यदि कोई डुप्लिकेट दिखाई देता है, तो सबूत सुरक्षित रखें और कारण बताने से पहले उत्पादन, आयात, स्थिरता और भंडारण पथ का निरीक्षण करें।