เปลี่ยนรูปแบบของแผนผังสถานะ Ethereum โดยใช้การซ้อนทับ

หมายเหตุบรรณาธิการ: บทความนี้มาจากผู้ที่ชื่นชอบ Ethereum (ID: ethfans)หมายเหตุบรรณาธิการ: บทความนี้มาจาก

ผู้ที่ชื่นชอบ Ethereum (ID: ethfans)

วิธีที่บัญชีและสัญญาจัดเก็บข้อมูลเป็นหนึ่งในหลาย ๆ ประเด็นที่ส่งผลกระทบต่อ Ethereum โปรโตคอล Ethereum ใช้ Merkle Patricia Tree (MPT, Merkle Patricia Tree) เพื่อจัดระเบียบบัญชีและข้อมูลสัญญา แม้ว่าโครงสร้างข้อมูลนี้จะทำงานได้ดีในทางทฤษฎี แต่ในทางปฏิบัตินั้นสร้างปัญหามากกว่าที่จะแก้ไข นักพัฒนาหลักได้พูดคุยกันเป็นเวลาหลายปีว่าพวกเขาต้องการแทนที่โครงสร้างข้อมูลนี้ด้วยต้นไม้ไบนารี ในบทความนี้ ฉันจะอธิบายมุมมองของฉันเกี่ยวกับปัญหานี้และวิธีทำให้การแปลงนี้บรรลุผลสำเร็จ

พื้นหลัง

วิธีการที่เสนอของฉันเกี่ยวข้องกับช่วงการเปลี่ยนแปลงซึ่งเครือข่ายจะรักษาโครงสร้างต้นไม้ทั้งสองไว้ ข้อดีของสิ่งนี้คือกระบวนการแปลงโครงสร้างแบบต้นไม้จะไม่ส่งผลกระทบต่อการทำงานของห่วงโซ่ และสามารถมั่นใจได้ว่าบัญชีทั้งหมดจะถูกแปลงเป็นรูปแบบไบนารี

พื้นหลัง

ปัจจุบัน ต้นไม้สถานะของ Ethereum เป็นเลขฐานสิบหก Hex หมายความว่าแต่ละโหนดมีโหนดลูก 16 โหนด ในทางทฤษฎี เป็นเรื่องปกติ เพราะการมีลูกมากขึ้นหมายถึง "ระดับ" (เช่น ความสูงของต้นไม้) น้อยลงในการจัดเก็บข้อมูลทั้งหมด

คำอธิบายภาพ

- รูปที่ 1. ตัวอย่างของ hex tree แสดงวิธีเก็บค่า v ที่คีย์ที่เกี่ยวข้อง 0xaa ความยาวคีย์ของทรีนี้มีเพียง 2 ไบต์ และแสดงเฉพาะทรีย่อยตาม 0xaa เท่านั้น เพื่อความกระชับ ต้นไม้ย่อยที่ไม่เกี่ยวข้องจะถูกแทนที่ด้วย "..." -

จะเห็นได้ว่าต้นไม้ในภาพด้านบนนั้นสั้นและกว้างมาก ด้วยคู่คีย์-ค่าเดียวกัน รูปภาพต่อไปนี้แสดงสถานการณ์ของหน่วยเก็บไบนารีทรี 170 แสดงเป็น 10101010 ในไบนารีทรี

คำอธิบายภาพ

ดังที่เห็นได้จากรูป ต้นไม้ไบนารีนั้นลึกและแคบกว่ามาก

ใน Ethereum แต่ละบล็อกมีฟิลด์ stateRoot ซึ่งเป็นค่าแฮชรูทของ MPT ที่แสดงถึงสถานะโดยรวมของ Ethereum หลังจากที่บล็อกได้รับการประมวลผล โดยทั่วไป ค่าแฮชนี้ได้มาจากการแฮชรายการค่าแฮชของโหนดลูก 16 โหนดของโหนดรูท ค่าแฮชของโหนดย่อยเหล่านี้ได้จากการแฮชรายการค่าแฮชของโหนดย่อย 16 รายการและอื่น ๆ

ทุกครั้งที่ธุรกรรมแพ็คเกจสร้างบล็อกใหม่ นักขุดจะอัปเดตโครงสร้างบัญชีและคำนวณแฮชรูทใหม่ แฮชรูทถูกเก็บไว้ในฟิลด์ stateRoot ของบล็อกใหม่ จากนั้นบล็อกใหม่จะถูกใช้

คำอธิบายภาพ

นี่คือปัญหา: การคำนวณรูทแฮชใหม่อาจใช้เวลานานเกินไปหากโหนดทั้งหมดถูกแฮช ดังนั้นในการคำนวณแฮชของโหนดรูท คนขุดแร่จะดึงข้อมูลแฮชพี่น้องจากฐานข้อมูล (แฮชพี่น้อง) แม้ว่าวิธีหลัง (นักขุดจะดึงโหนดย่อยจากฐานข้อมูล) จะไม่ใช้เวลามากเท่ากับวิธีแรก (นักขุดจะได้รับโหนดลีฟทั้งหมดจากฐานข้อมูลและแฮช) การดำเนินการนี้ยังคงใช้เวลานาน เนื่องจากต้องดึงแฮชแต่ละรายการจากฐานข้อมูล

ในแผนผังฐานสิบหก คุณมักจะต้องใช้ค่าแฮชพี่น้อง 15 ค่าในแต่ละระดับ ในตัวอย่างที่ฉันสร้างไว้ด้านบน (รูปที่ 1) (การคำนวณรูทแฮชใหม่) จะต้องใช้ 30 แฮช

แม้ว่าต้นไม้ไบนารีจะลึกกว่าเล็กน้อย แต่ต้องการแฮชพี่น้องเพียงอันเดียวในแต่ละระดับ จากตัวอย่างด้านบน (รูปที่ 2) ต้องใช้แฮชเพียง 8 อันเท่านั้น! นั่นเป็นเหตุผลที่ไบนารีทรีดีกว่าในทางปฏิบัติ

ชื่อระดับแรก

น่าเสียดายที่การแปลงเป็นไบนารีทรีนั้นไม่ใช่เรื่องเล็กน้อย มีข้อมูลมากมายที่จะแปลงซึ่งจะใช้เวลามากกว่า 15 วินาทีในการสร้างบล็อกเพื่อทำการแปลง

นอกจากนี้ ลองนึกภาพว่าคุณกำลังแปลหนังสือหนา 5,000 หน้า และผู้เขียนคอยบอกคุณว่าพวกเขาได้ทำการเปลี่ยนแปลงบางอย่างกับเนื้อเรื่อง และการเปลี่ยนแปลงเหล่านี้ส่งผลต่อหน้าที่คุณแปลไปแล้ว...จากนั้นกระบวนการก็จะสิ้นสุด การแปลงรูปแบบของ state tree เป็นปัญหาเดียวกัน: บางทีคุณอาจเพิ่งแปลงรูปแบบของ address เสร็จ และผู้ใช้ใช้ address (ซึ่งก็คือการอัพเดต state ของ address) จากนั้นคุณต้องแปลงอีกครั้งตั้งแต่ต้น (เนื่องจากสถานะของการอัปเดตที่อยู่มีผลกับแผนผังสถานะทั้งหมดด้วย)

ชื่อเรื่องรอง

ขั้นตอนที่ 1 - การแปลง

ภายใต้วิธีนี้ เมื่อความสูงของบล็อกคือ H1 จะต้องมีสถานะรูทสองสถานะ: หนึ่งคือรูทสถานะเลขฐานสิบหก "เลเยอร์พื้นฐาน" และอีกอันคือรูทสถานะไบนารีทรี "เลเยอร์ซ้อนทับ"

คำอธิบายภาพ

แผนผังฐานสิบหกถูกสร้างเป็นแบบอ่านอย่างเดียว ดังนั้นการอัปเดตใดๆ ต่อสถานะจะทำบนแผนผังซ้อนทับ

เมื่อธุรกรรมอ่านหรืออัปเดตบัญชี ระบบจะค้นหาแผนผังการซ้อนทับก่อน หากไม่พบบัญชีในแผนผังซ้อนทับ ต้นไม้ฐานสิบหกเก่าจะถูกค้นหาค่า

ชื่อเรื่องรอง

ขั้นตอนที่ 2 - การสลับทรีฐาน

คำอธิบายภาพ

- รูปที่ 5 ในขั้นตอนที่สองของการแปลง นักขุดจะแทนที่รูทเลขฐานสิบหกด้วยรูทของไบนารีทรีที่แปลงแล้วในส่วนหัวของบล็อก ส่งสัญญาณไปยังเครือข่ายว่าพร้อมแล้ว -

เมื่อชุดของบล็อกเพียงพอให้ค่าเดียวกันกับรากของแผนผังฐานไบนารีที่แปลงแล้ว หมายความว่านักขุดส่วนใหญ่ได้ทำการแปลงเสร็จสิ้นและอนุมัติแผนผังที่แปลงแล้ว กระบวนการรวมจะเริ่มขึ้น (หมายเหตุผู้แปล: การผสานในเวลานี้มีไว้สำหรับแผนผังฐานไบนารีแบบอ่านอย่างเดียวและแผนผังหลักไบนารีแบบอ่าน-เขียน)

กระบวนการรวมดำเนินการอย่างต่อเนื่อง: ทุกครั้งที่มีการสร้างบล็อกใหม่ คีย์ n ตัวจะถูกลบออกจากแผนผังการซ้อนทับและใส่กลับเข้าไปในแผนผังฐานสอง กระบวนการนี้ดำเนินต่อไปจนกว่าคีย์ทั้งหมดจะถูกลบออกจากแผนผังการซ้อนทับ เมื่อถึงขั้นตอนนี้ ส่วนหัวของบล็อกจะไม่เก็บรากของแผนผังสถานะซ้อนทับอีกต่อไป

ขั้นตอนต่อไป

ชื่อเรื่องรอง

ขั้นตอนต่อไป