อ่านอัลกอริทึมการสับเปลี่ยนของ Ethereum 2.0 ในบทความเดียว
ผู้แต่ง |Ben Edgington
การแนะนำ
ผู้แต่ง |การแนะนำหากคุณต้องการเรียนรู้
ผีสเต็ปแดนซ์
(ชัฟเฟิลแดนซ์) ถ้าอย่างนั้นคุณมาผิดที่แล้ว แต่เชื่อฉันเถอะ การสลับเพลงใน Eth2 ก็น่าตื่นเต้นไม่แพ้กันรายการสุ่มเป็นการดำเนินการพื้นฐานใน Ethereum 2.0 ส่วนใหญ่จะใช้เพื่อหลอกสุ่มเลือกผู้ตรวจสอบเพื่อจัดตั้งคณะกรรมการในทุก ๆ 12 วินาที และเพื่อเลือกผู้เสนอสำหรับบล็อกเชนสัญญาณในแต่ละช่องสุ่มดูเหมือนค่อนข้างตรงไปตรงมา แม้ว่าจะมีบ้างFisher-Yeats shuffleอันตรายที่ซ่อนอยู่
ขึ้น. แล้วทำไมเราไม่ใช้ใน Eth2? ฉันจะอธิบายรายละเอียดในตอนท้ายของบทความ แต่สั้น ๆ - ไคลเอนต์เบากระดาษกระดาษTekuกลาง. ฉันเพิ่งใช้ไคลเอนต์ Eth2กลาง
เขียนใหม่
การนำไปปฏิบัติของเราจึงอยากเขียนออกมาในขณะที่ยังร้อนอยู่
อัลกอริทึมการสลับหรือไม่สับ
รอบการทำงาน
การสับไพ่จะดำเนินการเป็นรอบ ขั้นตอนจะเหมือนกันในแต่ละรอบ ดังนั้นฉันจะสาธิตขั้นตอนสำหรับรอบเดียวด้านล่าง ซึ่งง่ายกว่าที่เห็นมาก
อันดับแรก เราเลือก pivot index p ซึ่งเลือกแบบสุ่มหลอกตามรอบและข้อมูลเมล็ดอื่น ๆ หลังจากเลือกแกนแล้ว แกนจะได้รับการแก้ไขในรอบ
จากจุดหมุนนี้ เราเลือกดัชนีมิเรอร์ m1 ที่จุดกึ่งกลางระหว่าง p และ 0 นั่นคือ m1=p/2 (เพื่อประโยชน์ในการอธิบาย เราจะเพิกเฉยต่อปัญหาการปัดเศษข้อผิดพลาดทีละรายการ)
คำอธิบายภาพ
จุดหมุนและดัชนีมิเรอร์ตัวแรก
2. จากดัชนีมิเรอร์ตัวแรกถึงจุดหมุน เปลี่ยนหรือไม่เปลี่ยน
สำหรับแต่ละดัชนีระหว่างดัชนีมิเรอร์ m1 และดัชนี pivot เราสุ่มตัดสินใจว่าจะแทนที่องค์ประกอบเหล่านั้นหรือไม่
หากเราตัดสินใจแทนที่ เราจะแทนที่องค์ประกอบรายการบน i1 ด้วยองค์ประกอบบน i1' ซึ่งเป็นภาพบนดัชนีมิเรอร์ นั่นคือ i1 ถูกแทนที่ด้วย i1'=m1-(i1-m1) เพื่อให้ระยะทางจาก i1 และ i1' ถึง m1 เท่ากัน
เราทำการตัดสินใจแลกเปลี่ยนหรือไม่เหมือนกันสำหรับแต่ละดัชนีระหว่าง m1 และ p
คำอธิบายภาพ
3. คำนวณดัชนีมิเรอร์ตัวที่สอง
หลังจากตัดสินใจดัชนีทั้งหมดจาก m1 ถึง p ตอนนี้เราพบดัชนีมิเรอร์ตัวที่สองที่มี m2 เป็นจุดกึ่งกลาง กล่าวคือ จุดที่ห่างจาก p และจุดสิ้นสุดของรายการเท่ากัน นั่นคือ m2=m1+n/2
คำอธิบายภาพ
4. จากจุดหมุนไปยังกระจกบานที่สอง เปลี่ยนหรือไม่เปลี่ยน
สุดท้าย เราทำกระบวนการสลับหรือไม่เปลี่ยนซ้ำ โดยพิจารณาการตัดสินใจเปลี่ยน p จากจุดหนึ่งไปยังจุดหมุนทั้งหมด นั่นคือ การตัดสินใจจาก p ไปยังมิเรอร์ที่สอง m2 หากเราเลือกที่จะไม่เปลี่ยน เราจะไปยังอันถัดไป หากเราเลือกที่จะแทนที่ เราจะแทนที่องค์ประกอบบน j1 ด้วยภาพสะท้อนในกระจกเงาบน j1' ที่ดัชนีมิเรอร์ m2
คำอธิบายภาพ
สลับหรือไม่ตัดสินใจจากเดือยเป็นดัชนีมิเรอร์ที่สอง
ในตอนท้ายของรอบ เราได้พิจารณาดัชนีทั้งหมดระหว่าง m1 และ m2 นั่นคือครึ่งหนึ่งของดัชนีทั้งหมด และแต่ละดัชนีมีดัชนีเฉพาะในอีกครึ่งหนึ่ง ไม่ว่าจะถูกแทนที่หรือไม่ก็ตาม ดังนั้นสำหรับการเปลี่ยนหรือไม่ดัชนีทั้งหมดได้รับการพิจารณาเพียงครั้งเดียว
รอบถัดไปเริ่มต้นด้วยการเพิ่ม (หรือลด) รอบ เพื่อให้เรามีดัชนีเดือยใหม่ จากนั้นจึงเริ่มวนไปตามกระบวนการที่อธิบายไว้ข้างต้น
คำอธิบายภาพ
กระบวนการย้ายจากกระจกบานหนึ่งไปยังอีกบานหนึ่งในรอบเดียวกัน
สถานที่ที่แยบยลทำให้สำเร็จเมื่อตัดสินใจว่าจะแทนที่หรือไม่ อัลกอริทึมจะเลือกดัชนีตัวเลือกที่สูงกว่าหรือภาพสะท้อนกลับอย่างชาญฉลาด หมายความว่าเมื่ออยู่ด้านล่างแกน i_1 จะถูกเลือกแทน i_1' เมื่ออยู่เหนือแกน i_k' จะถูกเลือกแทน i_k ซึ่งหมายความว่าเราสามารถวนซ้ำดัชนีในรายการได้อย่างยืดหยุ่น: เราสามารถแยก 0 ถึง m1 และ p ถึง m2 ออกเป็นสองลูปแยกกัน หรือรวมทั้งสองอย่างในลูปเดียวกันจาก m1 ถึง m2 ตามที่ฉันได้อธิบายไว้ข้างต้นในข้อความ (และ
ทำให้สำเร็จ
)ของ. ผลลัพธ์จะเหมือนกันทั้งสองวิธี: ไม่สำคัญว่าฉันจะพิจารณา i_1 หรือมิเรอร์ i_1' หรือไม่ การแทนที่หรือไม่ให้ผลลัพธ์เหมือนกันรอบใน Eth2 กระบวนการข้างต้นจะดำเนินการ 90 ครั้งกระดาษต้นฉบับมีการกล่าวถึงว่าต้องใช้รอบ 6lgN เพื่อ "เริ่มแสดงขอบความปลอดภัยที่ดีในการโจมตีด้วยรหัสผ่านแบบเลือก (CCA)" โดยที่ N คือความยาวของรายการ ที่ไวทาลิค
ข้อกำหนดคำอธิบายประกอบ
ใน เขากล่าวว่า "ผู้เชี่ยวชาญด้านการเข้ารหัสแนะนำว่าเรามีรอบ 4log2N เพื่อให้มีความปลอดภัยเพียงพอ" จำนวนสูงสุดของตัวตรวจสอบความถูกต้องใน Eth2 ซึ่งเป็นจำนวนครั้งสูงสุดที่เราต้องสุ่มรายการคือประมาณ 222 (4.2 ล้าน) ค่าประมาณที่กำหนดโดย Vitalik คือ 88 รอบ และค่าประมาณในกระดาษคือ 92 รอบ (สมมติว่า lg เป็นลอการิทึมธรรมชาติ) ตอนนี้เราอยู่ในช่วงที่ถูกต้องโดยประมาณ โดยเฉพาะอย่างยิ่งเนื่องจากเราน่าจะไม่ได้ลงเอยด้วยตัวตรวจสอบความถูกต้องที่ใช้งานอยู่จำนวนมากนี้Issue Fการปรับรอบตามความยาวของรายการอาจให้ผลลัพธ์ที่น่าสนใจ แต่เราจะไม่ทำเช่นนั้น อาจเป็นการปรับให้เหมาะสมที่ไม่จำเป็น
ที่น่าสนใจคือ เมื่อ Least Authority ตรวจสอบข้อมูลจำเพาะของ Beacon Chain พวกเขาพบว่ามีอคติในการสับเปลี่ยนที่เลือกผู้เสนอบล็อก (ดู
). แต่กลับกลายเป็นว่าพวกเขาใช้การกำหนดค่าการสับเปลี่ยนที่มีเพียง 10 รอบอย่างผิดพลาด เมื่อพวกเขาเพิ่มการกำหนดค่าการสุ่มเป็น 90 รอบ (จำนวนที่เราใช้ใน mainnet) ความเอนเอียงก็หายไป
(หลอก)สุ่ม
อัลกอริทึมการสับเปลี่ยนกำหนดให้เราต้องสุ่มเลือกจุดหมุนในแต่ละรอบ และสุ่มเลือกว่าจะแทนที่องค์ประกอบใดในแต่ละรอบ
ใน Eth2 เราสร้างการสุ่มจากค่าเมล็ดโดยที่เมล็ดเดียวกันจะให้ผลการสับเหมือนกันเสมอ
ตัวบ่งชี้ Pivot ถูกสร้างขึ้นโดยการแฮช SHA2 ขนาด 8 ไบต์ของเมล็ดที่เชื่อมกับรอบ
ดัชนี Pivot ถูกสร้างขึ้นจากแปดไบต์ของแฮช SHA2 ของค่า Seed ที่เชื่อมกับรอบ ดังนั้นโดยปกติแล้วจะเปลี่ยนทุกรอบ
บิตชี้ขาดที่ใช้ในการตัดสินใจว่าจะแทนที่องค์ประกอบหรือไม่จะถูกดึงมาจากองค์ประกอบต่อไปนี้: แฮช SHA256 ของเมล็ด รอบ ดัชนีขององค์ประกอบในรายการ
ประสิทธิภาพ
อัลกอริธึมการสับเปลี่ยนนี้ช้ากว่าอัลกอริทึมของ Fisher-Yates มาก หากอัลกอริทึมของ Fisher-Yates ต้องการการสับ N ครั้ง อัลกอริทึมของเราต้องการการสับโดยเฉลี่ย 90N/4 ครั้ง เราต้องพิจารณาการสร้างการสุ่มหลอกซึ่งเป็นส่วนที่แพงที่สุดของอัลกอริทึม Fisher-Yates ต้องการการสุ่มที่ใกล้เคียงกับตัวเลข Nlog2N และเราต้องการตัวเลข 90(log2N+N/2) ตามช่วงของค่า N ที่เราต้องการใน Eth2 ตัวเลขที่เกินมานั้นค่อนข้างมาก (เมื่อ N คือหนึ่งล้าน , Eth2 ต้องการ N ประมาณสองเท่า)
เหตุใดจึงเลือกอัลกอริทึม swap-or-not
หากไม่มีประสิทธิภาพ ทำไมคุณถึงเลือกใช้วิธีนี้
สับองค์ประกอบเดียว
ดังนั้น หากเราต้องการทราบว่าองค์ประกอบที่ดัชนี 217 ถูกสับที่ใด เราสามารถเรียกใช้อัลกอริทึมสำหรับดัชนีนั้นเท่านั้น โดยไม่ต้องสับเปลี่ยนทั้งรายการ นอกจากนี้ ในทางกลับกัน หากเราต้องการทราบว่าองค์ประกอบใดถูกสับเปลี่ยนไปยังดัชนี 217 เราสามารถเรียกใช้อัลกอริทึมแบบย้อนกลับเพื่อค้นหาองค์ประกอบ 217 (ย้อนกลับหมายถึงการรันรอบจากสูงไปต่ำ ไม่ใช่ต่ำไปสูง )
ข้อกำหนด Eth2
สิ่งที่เขียนเป็นเรื่องเกี่ยวกับวิธีการใช้อัลกอริทึมเพื่อสับดัชนีเดียว อันที่จริงแล้ว การสับเปลี่ยนรายการทั้งหมดพร้อมกันเป็นเพียงการปรับให้เหมาะสมเท่านั้น! ถ้าเราต้องการ เราสามารถสุ่มได้เพียงองค์ประกอบเดียวของรายการตามลำดับ: (ย้อนกลับ) เรียกใช้การสับเปลี่ยนเพื่อค้นหาองค์ประกอบที่สิ้นสุดที่ดัชนี 0 เรียกใช้การสับเปลี่ยนอีกครั้งเพื่อค้นหาองค์ประกอบที่สิ้นสุดที่ดัชนี 1 และอื่น ๆ เหตุผลที่เราไม่ทำเช่นนั้นก็เนื่องมาจากการตัดสินใจว่าการสลับหรือไม่ต้องสร้างแฮช 256 บิตพร้อมกัน และการทิ้ง 255 บิตแบบนั้นจะเป็นการสิ้นเปลือง หากเราใช้แฮชหรือออราเคิล 1 บิต การสับองค์ประกอบหนึ่งของรายการจะมีประสิทธิภาพเทียบเท่ากับการสับเปลี่ยนทั้งรายการ
เป็นลูกค้า "แสง" ที่แท้จริง
ประวัติศาสตร์ที่นี่ที่นี่ที่นี่ตรวจสอบการอภิปรายเกี่ยวกับภารกิจดั้งเดิมสำหรับอัลกอริทึมการสับเปลี่ยนสำหรับ Eth2
ที่นี่หากคุณต้องการดูอัลกอริทึมการสลับหรือไม่สับจากมุมอื่น คุณสามารถดูที่เผยแพร่โดย Protolambda。
ในที่สุด
ในที่สุด
ข้อจำกัดความรับผิดชอบ: งานแปลของ ECN มีเป้าหมายเพื่อส่งมอบข้อมูลคุณภาพสูงและทรัพยากรการเรียนรู้สำหรับชุมชน Ethereum ของจีน ลิขสิทธิ์ของบทความเป็นของผู้เขียนต้นฉบับ การพิมพ์ซ้ำต้องระบุแหล่งที่มาของข้อความต้นฉบับและ ethereum.cn สำหรับระยะยาว พิมพ์ซ้ำ โปรดติดต่อ Authorize etheremcn@gmail.com
