เครื่องมือสำหรับนักพัฒนา · ตัวสร้าง UUID
v4 UUID มีบิตสุ่มจำนวนเท่าใด 122 ไม่ใช่ 128
· มันทำงานอย่างไร
uuid การเข้ารหัส เบราว์เซอร์-apis
หกใน 128 bits ในการสุ่ม UUID ได้รับการแก้ไขโดยมาตรฐาน เหลือ 122 ไว้สำหรับการสุ่ม โพสต์นี้แสดงวิธีการประมาณโอกาสที่จะเกิดการชนกันอย่างตรงไปตรงมา และเหตุใดการชนที่แท้จริงจึงมาจากเครื่องกำเนิดไฟฟ้าที่เสียหาย ไม่ใช่จากคณิตศาสตร์
คำถามของสถาปนิก: เราจะได้สำเนาซ้ำหรือไม่? — ความกังวลมาจากไหน และเหตุใดคำตอบจึงขึ้นอยู่กับผู้สร้าง
สถาปนิกถามว่า: ถ้าเราสร้าง UUID 10 ล้าน UUID ต่อวันเป็นเวลาสิบปี เราจะมีวันซ้ำกันหรือไม่ คำตอบที่ตรงไปตรงมาคือ: แทบจะไม่แน่นอนเลย หากตัวสร้างมีความปลอดภัยแบบเข้ารหัส เกือบจะใช่แน่นอน ถ้าเครื่องกำเนิดไฟฟ้าเสีย คณิตศาสตร์ RFC 9562 นั้นฟังดูดี: v4 UUID ที่มีบิตสุ่ม 122 มีความน่าจะเป็นในการชนกันที่ประมาณ n² / 2 ยกกำลัง 123 โดยที่ n คือจำนวนตัวระบุที่สร้างขึ้น สำหรับระบบจริงส่วนใหญ่ ความน่าจะเป็นนี้มีน้อยมาก สิ่งที่จับได้ก็คือสูตรนี้ถือว่าทุกบิตเป็นการสุ่มอย่างแท้จริง หากเครื่องกำเนิดไฟฟ้ารั่วหรือเกิดซ้ำหรือคาดเดาได้ สูตรนั้นผิด และการทำซ้ำจะกลายเป็นสิ่งที่หลีกเลี่ยงไม่ได้ เค้าโครง 128 บิตประกอบด้วยบิตเวอร์ชันสี่บิต (0100 สำหรับ v4) และบิตรูปแบบสองบิต (10 สำหรับ RFC 9562) ซึ่งได้รับการแก้ไขและกำหนดโดยมาตรฐาน
หกบิตใดที่พูดถึง — บิตสี่เวอร์ชันและบิตตัวแปรสองบิต และเหตุใดจึงตั้งค่าไว้แทนที่จะสุ่ม
นั่นทำให้ 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 nibble ก็ตาม สิ่งเหล่านั้นเป็นข้อบกพร่องในการใช้งาน ไม่ใช่หลักฐานว่าการคำนวณฟิลด์ 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 data 10^-10 ซึ่งยังคงเล็กอยู่จนหมดสิ้น การประมาณการเหล่านี้ถือว่าทุกบิตมีความเป็นอิสระและเป็นแบบสุ่ม ตัวสร้าง ToolAcre ใช้ crypto.getRandomValues ซึ่งให้ CSPRNG- การสุ่มสำรองแก่คุณ การดำเนินการเป็นเพียงส่วนเดียวที่คุณต้องไว้วางใจ อย่าพึ่งพาความน่าจะเป็นของการชนกันเป็นข้ออ้างในการข้ามการตรวจสอบการอนุญาตที่เหมาะสม UUID ไม่ใช่รหัสผ่าน ไม่ใช่โทเค็นการเข้าถึง และไม่ใช่ความลับ แม้ว่าจะเป็น 122 บิตสุ่มก็ตาม เอกลักษณ์คือคุณประโยชน์ ความคาดเดาไม่ได้เป็นคุณสมบัติแยกต่างหาก (และสำคัญกว่า) ที่ป้องกันการคาดเดา คณิตศาสตร์วันเกิดจัดการกับเอกลักษณ์ มันไม่ได้กล่าวถึงอายุการใช้งาน (สิ่งนี้ UUID ควรหมดอายุหรือไม่ ), ความลับ (จำเป็นต้องแฮชก่อนการจัดเก็บหรือไม่) หรือการอนุญาต (การครอบครอง UUID นี้พิสูจน์อะไรเกี่ยวกับผู้โทรหรือไม่) ตัวสร้าง ToolAcre มอบ UUID ที่ได้รับการสนับสนุน CSPRNG ให้กับคุณ พร้อมด้วยบิตสุ่ม 122 ซึ่งหมายถึงความเป็นเอกลักษณ์ทางคณิตศาสตร์ที่คงอยู่ และความคาดเดาไม่ได้คือเสียง สิ่งอื่นๆ เช่น การตรวจสอบโทเค็น การหมดอายุ การควบคุมการเข้าถึง ถือเป็นความรับผิดชอบของแอปพลิเคชันของคุณ สูตรความน่าจะเป็นถือว่าเป็นอิสระจากแต่ละ UUID ที่สร้างขึ้นจากรุ่นก่อนๆ หากระบบของคุณสร้างตัวระบุจากอินสแตนซ์ CSPRNG เดี่ยว และการโทรแต่ละครั้งดึงการสุ่มใหม่จากระบบปฏิบัติการ สมมติฐานความเป็นอิสระจะยังคงอยู่ หากระบบของคุณใช้สถานะ CSPRNG ที่แคชไว้หรือตัวสร้างแบบ seeded โดยไม่มีการปรับปรุงระบบปฏิบัติการใหม่ สมมติฐานจะพังลง ความเสี่ยงในการชนกันจะเพิ่มขึ้นอย่างมากหากแหล่งเอนโทรปีหมดลง (เกิดขึ้นบนระบบฝังตัวหรือเครื่องเสมือนบางเครื่องภายใต้โหลด) หรือหากสถานะสุ่มไม่เคยถูกรีเซ็ตระหว่างกระบวนการ (การฟอร์กกระบวนการโดยไม่ต้องเริ่มต้นใหม่ CSPRNG)
สิ่งนี้ไม่ครอบคลุมถึง - เอกลักษณ์ของ v1 และ v7 ซึ่งขึ้นอยู่กับการประทับเวลาและลำดับนาฬิกามากกว่าการสุ่มเพียงอย่างเดียว
ทางเลือก ToolAcre จะเรียก crypto.getRandomValues สำหรับแต่ละไบต์อาร์เรย์ และไม่มีสถานะ PRNG ระดับแอปพลิเคชัน ภายในแพลตฟอร์มยังคงเป็นความรับผิดชอบของเบราว์เซอร์และระบบปฏิบัติการ การจำลองการชนกับเครื่องกำเนิดไฟฟ้าจริงแสดงให้เห็นถึงความแตกต่างระหว่างทฤษฎีและการปฏิบัติที่แตกหัก เครื่องกำเนิดไฟฟ้าที่สร้างด้วย Math.random เริ่มต้นจากเมล็ดเดียวกันจะสร้างลำดับที่เหมือนกัน คุณจะเห็นการชนกันของ UUID ครั้งแรกภายในสองสามร้อยถึงสองสามพันค่าที่สร้างขึ้น ไม่ใช่หลังจากค่า 2^60 ค่า (รากที่สองของ 2^122) ตามที่คาดการณ์วันเกิดโดยประมาณ ตัวสร้างที่ใช้ crypto.getRandomValues จากเอนโทรปีของระบบปฏิบัติการเสียงจะทำให้เกิดการชนกันก็ต่อเมื่อความน่าจะเป็นทางทฤษฎีนั้นหลีกเลี่ยงไม่ได้ (ประมาณ 2^60 UUID) ซึ่งเป็นตัวเลขที่มากจนคุณจะไม่มีวันไปถึงมัน เครื่องกำเนิดไฟฟ้าที่ใช้แหล่งเอนโทรปีที่อ่อนแอหรือใช้ซ้ำ (พบได้ทั่วไปในไลบรารีหรือเฟรมเวิร์กการทดสอบ UUID ที่ใช้งานไม่ดี) จะทำให้เกิดการชนกันที่ใดที่หนึ่งในระหว่างนั้น
ประเด็นสำคัญ: เชื่อถือคณิตศาสตร์ ตรวจสอบตัวสร้าง — ตัวสร้าง ToolAcre ใช้ CSPRNG ของเบราว์เซอร์ ซึ่งเป็นส่วนที่จะต้องไม่ปลอมแปลง
การทดสอบเป็นกลุ่มสามารถตรวจจับการใช้งานที่ส่งคืนค่าคงที่หรือเล่นซ้ำลำดับที่ชัดเจน แต่ตัวอย่างที่ผ่านไม่สามารถพิสูจน์เอกลักษณ์ในอนาคตได้ ระบบการผลิตควรยังคงบังคับใช้ข้อจำกัดเฉพาะในกรณีที่ตัวระบุที่ซ้ำกันอาจทำให้ข้อมูลเสียหายได้ การนำเข้าสมควรได้รับความสนใจเป็นพิเศษ เนื่องจากระบบต้นทางที่ถูกต้องสองระบบอาจมีตัวระบุตามตัวอักษรเดียวกันอยู่แล้ว และสามารถคัดลอกโปรแกรมติดตั้งข้ามสภาพแวดล้อมได้ การทดสอบของ ToolAcre ตรวจสอบว่าชุดของ 500 มีค่าที่แตกต่างกัน 500 นั่นคือการตรวจสอบการถดถอยสำหรับการใช้งานนี้ ไม่ใช่การรับประกันทางสถิติ หากรายการซ้ำปรากฏขึ้น ให้เก็บรักษาหลักฐานและตรวจสอบการสร้าง การนำเข้า อุปกรณ์ติดตั้ง และเส้นทางการจัดเก็บก่อนที่จะระบุสาเหตุ