1. บทนำ

ในวันสุดท้ายของปี 2023 วิทาลิคได้แบ่งปันแผนการดำเนินงานของ Ethereum สำหรับปี 2023 ในทวิตเตอร์ สรุปความคืบหน้าของ Ethereum ในรอบปี ส่วนแผนการแผนที่ชื่อว่า "The Verge" อธิบายถึงวิธีที่เทคโนโลยีของ Ethereum สามารถยืนยันสถานะบล็อกเชนได้อย่างง่ายและมีประสิทธิภาพมากขึ้น หนึ่งคอนเซ็ปต์หลักที่ถูกกล่าวถึงที่นั่นคือ Verkle Trees ดังนั้น คืออะไรที่ Verkle Trees, ทำไม Ethereum ต้องการมัน และ Verkle Trees แก้ปัญหาอย่างไร? จุดประสงค์ของบทความนี้คือเพื่อตอบคำถามเหล่านี้สำหรับผู้อ่านโดยไม่ลงลึกไปในกระบวนการเขัยนและคณิตศาสตร์เพื่อช่วยให้ผู้ที่มีความเข้าใจ Ethereum บางส่วนเข้าใจแนวคิดของ Verkle Trees ได้อย่างรวดเร็ว

2. คำถามที่สามารถพิสูจน์ได้

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

ADS เป็นเทคนิคการค้นหาที่สามารถยืนยันได้ที่ใช้อย่างแพร่หลายในฐานข้อมูลแบบดั้งเดิม โดยส่วนใหญ่จะพัฒนาขึ้นบนโครงสร้างเช่น Merkle Trees หรือโครงสร้างสะสมที่คล้ายกัน กับการวิวัฒนาการของเครื่องมือทางคริปโทกราฟซึ่งมีผู้วิจัยหลายคนได้เริ่มต้นสำรวจการใช้เทคนิคการคำนวณที่สามารถยืนยันได้เพื่อแก้ไขปัญหาที่เกิดขึ้นกับคำถามที่ไม่น่าเชื่อถือ บางแผนการคำนวณที่สามารถยืนยันได้ที่ขึ้นอยู่กับโปรโตคอล Zero-Knowledge Proof เช่น SNARKs สามารถสนับสนุนการค้นหาที่สามารถยืนยันได้สำหรับฐานข้อมูลภายนอกอย่างอ้อมอวาจ แผนการเหล่านี้สนับสนุนประเภทของคำถามที่หลากหลายและสร้างข้อมูลการยืนยันที่น้อยลง แต่มีภาระการคำนวณที่สูงขึ้น

ในปัจจุบัน Ethereum ใช้ Merkle Trees เพื่อใช้ในการดำเนินการค้นหาที่สามารถยืนยันได้ และเทคโนโลยี Verkle Tree ยังอิงจากเทคโนโลยี Merkle Tree ด้วย ดังนั้นเราจะแนะนำ Merkle Trees ก่อนเพื่อช่วยให้อ่านเข้าใจบทบาทของคำค้นหาที่สามารถยืนยันได้โดยใช้ตัวอย่างเหล่านี้

3. ต้นไม้เมอร์เคิล

3.1. นิยามและลักษณะของต้นไม้เมอร์เคิล

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

Merkle Trees มีลักษณะสำคัญสองอย่าง

1. การต้านทานการแก้ไข: ต้นไม้เมอร์เคิลโดยทั่วไปถูกสร้างขึ้นโดยใช้ฟังก์ชันแฮชที่ต้านการชนกัน ซึ่งทำให้การคำนวณหาข้อความสองข้อที่แตกต่างกันที่สร้างค่าแฮชเดียวกันเป็นเรื่องที่ความเป็นไปไม่ได้ จากโครงสร้างของต้นไม้เมอร์เคิล จะเห็นได้ว่าการปรับเปลี่ยนข้อมูลธุรกรรมภายในโหนดใบจะทำให้มีการเปลี่ยนแปลงในค่าแฮชรากของต้นไม้
2. การยืนยันความสมบูรณ์แบบของชุดข้อมูลขนาดใหญ่อย่างมีประสิทธิภาพ: ผู้ตรวจสอบจำเป็นต้องเก็บรากของ Merkle Tree เพียงอย่างเดียวเพื่อยืนยันความสมบูรณ์ของข้อมูลใดก็ได้ สิ่งนี้ถูกบรรลุโดยไม่ต้องส่งข้อมูลเต็มรูปแบบ แต่โดยการใช้โหนดที่เป็นพี่น้องตามเส้นทางจากใบในไปยังรากที่รู้จักกันว่าเส้นทาง Merkle โหนดพี่น้องเหล่านี้สามารถใช้ในการสร้างรากของ Merkle เพื่อวัตถุประสงค์ในการยืนยัน

3.2. วิธีสร้างพิสูจน์ Merkle

ในสถานการณ์การสอบสวนที่สามารถตรวจสอบได้ทั่วไป มีผู้พิสูจน์และผู้ตรวจ ผู้พิสูจน์จำเป็นต้องสร้างหลักฐานและส่งให้ผู้ตรวจ สำหรับเครือข่าย Ethereum สถานการณ์การใช้งานที่ทั่วไปคือเมื่อโหนดเบา (ลูกค้าที่เก็บเฉพาะหัวเรื่องบล็อก) สอบถามข้อมูลธุรกรรมจากโหนดเต็มหรือโหนดเก็บข้อมูล (ลูกค้าที่มีข้อมูลทั้งหมด) และได้รับหลักฐาน Merkle เพื่อตรวจสอบในท้องถิ่นว่าผลลัพธ์การสอบถามถูกต้องหรือไม่

Merkle proof ประกอบด้วยสามส่วนต่อไปนี้:

1. รากแฮชของต้นไม้เมอร์เคิลสำหรับชุดข้อมูลทั้งหมด
2. บล็อกข้อมูลที่ความความถูกต้องของมันต้องการจะถูกพิสูจน์
3. เส้นทางเมอร์เคิล ซึ่งรวมถึงค่าของโหนดที่เป็นพี่น้องทั้งหมดในเส้นทางตั้งแต่โหนดใบถึงโหนดราก

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

ด้านล่างเป็นตัวอย่างเฉพาะ: เมื่อผู้พิสูจน์ต้องพิสูจน์ให้ผู้ตรวจสอบเห็นว่า “4” เป็นบล็อกข้อมูลที่มีอยู่ในชุดข้อมูล และผู้ตรวจสอบถือราก trusted hash “1d25” ของ Merkle tree ของชุดข้อมูลทั้งหมด จะต้องให้ผู้พิสูจน์เพียงแค่ให้ข้อมูลทัั้งหมดที่ถูกทำเครื่องหมายสีน้ำเงิน โดยสมมติว่ามีข้อมูล n ชิ้นในชุด จะต้องใช้การคำนวณแฮชไม่เกิน log₂(n) เพื่อยืนยันความถูกต้องของบล็อกข้อมูลใด ๆ

โหนดแสงของ Ethereum ซิงโครไนซ์เฉพาะหัวของบล็อกซึ่งประกอบด้วยรากของ Merkle Trees สำหรับชุดข้อมูลต่าง ๆ (state tree, transaction tree, receipt tree) เมื่อโหนดแสงสอบถามโหนดเต็มเพื่อข้อมูลในต้นไม้ของใบเฉพาะ ๆ โหนดเต็มจะส่งข้อมูลเดิมพร้อมกับเส้นทางพิสูจน์ Merkle ที่สอดคล้องกัน ซึ่งทำให้โหนดแสงสามารถเชื่อถือในความถูกต้องของผลลัพธ์การสอบถาม

3.3. รูปแบบของต้นไม้เมอร์เคิล

โดยสร้างขึ้นบนพื้นฐานของ Merkle Trees สามารถรวมกันและแก้ไขได้ด้วยโครงสร้างข้อมูลอื่นเพื่อให้ได้ลักษณะใหม่ตามวัตถุประสงค์ที่แตกต่างกัน เพื่อให้เหมาะสำหรับสถานการณ์คำถามที่สามารถยืนยันได้ต่างๆ Merkle Trees สามารถขยายเป็นโครงสร้างข้อมูลที่มีดัชนีต่างๆ เช่น Merkle-B Trees (MBT) สำหรับการดำเนินการเชิงประสิทธิภาพ เช่น การแทรก การลบ และการสอบถาม ทีม Ethereum ได้เสนอ Merkle Patricia Tree (MPT)

3.3.1. ต้นไม้ Merkle-B

Merkle-B Tree (MBT) ใช้สำหรับการจัดการคิวรี่ช่วงที่สามารถตรวจสอบได้เป็นหลัก ให้ 𝑓 เป็นการกระจายของ MBT (จำนวนของโหนดลูกสำหรับแต่ละโหนด) ขึ้นอยู่กับโครงสร้างเรียง B+ tree โหนดภายในของ MBT นอกจากการจัดเก็บดัชนีกุญแจ 𝑓 — 1 และตัวชี้สำหรับโหนดลูก 𝑓 ยังรักษาค่าแฮชของโหนดลูกทั้งหมดของมันในรูปแบบสรุป ด้านล่างคือการแสดงโครงสร้างของโหนดใบและโหนดภายในใน MBT

เมื่อจำเป็นต้องพิสูจน์ว่าข้อมูลที่ส่งกลับจากคิวรี่ช่วงที่ระบุเป็นไปตามช่วงที่ระบุ แม่บริการที่คำนวณ Verification Object (VO) ต้องทำการค้นหาด้านบนลงมาสองครั้งเพื่อหาขอบซ้ายและขอบขวา มันยังต้องส่งข้อมูลทั้งหมดภายในขอบเหล่านี้รวมถึง hashes ของทุก branch ที่ต้องการสร้างเส้นทางไปยัง root hash ด้วย

ข้อเสียของโครงสร้างข้อมูลนี้คือ VO ที่ส่งกลับมาสามารถพิสูจน์ได้เพียงว่าผลลัพธ์ของคิวรีอยู่ในช่วงคิวรีที่ขอ แต่มันไม่สามารถพิสูจน์ได้ว่าผลลัพธ์ที่ส่งกลับมาครบถ้วน

3.3.2. ต้นไม้ Merkle Patricia

หากใช้ Naive Merkle Tree เพื่อให้บริการการค้นหาที่สามารถยืนยันได้ กระบวนการใช้เวลาในการสร้างรากของ Merkle tree ใหม่หลังจากแต่ละการแทรกข้อมูลหรือการลบข้อมูลสามารถกลายเป็นสำคัญ นอกจากนี้ยังต้องการการบำรุงรักษาเพิ่มเติมของต้นไม้ค้นหาข้อมูลสำหรับการเก็บรักษา Merkle Patricia Tree (MPT) รวมคุณสมบัติของ Radix Tree (ต้นไม้คำย่อเข้ม) และ Merkle Tree ทำให้สามารถดำเนินการแทรกข้อมูล ลบข้อมูล และค้นหาในเวลา O(log(N)) เพื่อเข้าใจอย่างละเอียดเกี่ยวกับ MPT ผู้อ่านสามารถอ้างอิงไปยังบทความเชิงเทคนิคที่ละเอียดเกี่ยวกับเรื่องนี้ บทความนี้จะเสนอบางคำจำกัดและให้ตัวอย่างเพื่อช่วยให้ผู้อ่านเข้าใจ MPT อย่างรวดเร็ว

โครงสร้างพื้นฐานของ Ethereum ใช้ฐานข้อมูลแบบ key-value สำหรับการเก็บข้อมูลซึ่งหมายความว่าข้อมูลถูกเก็บในรูปแบบของคู่ค่า key-value โดย MPT ยังถูกแยกออกเป็น key-value pairs สำหรับการเก็บข้อมูล เรากำหนดโครงสร้างตรรกะของโหนด MPT ตามนี้:

• ดัชนี
• เส้นทาง
• ข้อมูล

ในบริบทของต้นไม้ Merkle Patricia (MPT) “index” หมายถึง คีย์ของคู่ค่าคีย์-ค่า ในขณะที่ “path” ที่รวมกับ “data” มีค่าเป็นค่าของคู่ค่าคีย์-ค่า ดังนั้น index จริง ๆ เก็บแฮชของตู้ Merkle tree node และเส้นทางเข้ากับเส้นทางของต้นไม้คำนำหาหาโหนดเป้าหมาย Ethereum ใช้สตริงฮีกซาเดซเป็นเส้นทาง และดังนั้นความกว้างของ MPT คือ 16 ข้อมูลคือข้อมูลเป้าหมายที่สอดคล้องกับเส้นทาง

ด้านล่างนี้คือตัวอย่างของ MPT ที่ได้รับการปรับแต่งด้วยคำนำหน้าที่ถูกบีบอัด เก็บข้อมูลคู่คีย์-ค่าต่อไปนี้:

{

‘cab8’: ‘หมา’,

‘cabe’: ‘แมว’,

‘39’: ‘ไก่’,

'395': 'เป็ด',

‘56f0’: ‘horse’

}

เพื่อค้นหาข้อมูล "duck" โดยใช้เส้นทาง "395" คุณจะเริ่มต้นที่รากของข้อมูลและดำเนินการผ่าน hashA, hashC, และ hashD เพื่อเดินทางไปยังข้อมูลเป้าหมาย นี่คือคำแนะนำขั้นตอนตามลำดับ:

1. Root Hash: นี่คือจุดเริ่มต้นของต้นไม้ Merkle Patricia (MPT) และคุณจะใช้มันเพื่อค้นหาโหนดแรก
2. hashA: โดยอ้างอิงถึง root hash, คุณจะสามารถเรียกคืน node หรือเนื้อหาที่ระบุโดย hashA โดยเส้นทางคือ “395,” คุณกำลังมองหาส่วนของต้นไม้ที่จะนำคุณไปยัง “3”
3. hashC: หลังจากเข้าถึงเนื้อหาของ hashA คุณจะดำเนินตามเส้นทางต่อไป ช่วงถัดไป “9” จะนำคุณไปยัง hashC
4. hashD: ในที่สุดการดำเนินการต่อไปบนเส้นทาง ชิ้นสุดท้าย "5" ชี้คุณไปยัง hashD ซึ่งมีค่า "duck"

ในทุกขั้นตอนของเส้นทาง MPT ใช้ประโยชน์จากคุณสมบัติของ Radix Tree ในการค้นหาเส้นทางที่ถูกต้องโดยขึ้นอยู่กับคีย์ และ Merkle Tree เพื่อให้มั่นใจในความสมบูรณ์ของข้อมูลผ่านลิงก์แฮช "เส้นทาง" ในต้นไม้มักถูกแทนด้วยการเข้ารหัสฮีกซาเดึม ซึ่งสอดคล้องกับปัจจัยการแยกสาขาของต้นไม้ 16 ทุกโหนดในเส้นทางรวมถึงลิงก์แฮชพอยนเตอร์เพียงพอสมบูรณ์ในการยืนยันความสมบูรณ์ของข้อมูลและในการนำทางผ่านต้นไม้

โปรดทราบว่าใน MPT จริง ๆ เส้นทางและข้อมูลจะถูกเข้ารหัสและเก็บไว้อย่างไร้ระบบ และชนิดของโหนดเพิ่มเติม (เช่น โหนดส่วนขยายและโหนดใบ) ช่วยในการปรับโครงสร้างเพื่อเพิ่มประสิทธิภาพในสถานการณ์ต่าง ๆ

4. การสัญญาณเวกเตอร์

ระบบการสร้างความมั่นใจ[1] เป็นหลักการทางคริปโตที่รักษาความเป็นส่วนตัวและความสมบูรณ์ของข้อมูล พวกเขาถูกใช้กันอย่างแพร่หลายในสถานการณ์เช่นการพิสูจน์ทฤษฎีศาสตร์ที่ไม่ระบุข้อมูลและการคำนวณร่วมกันอย่างปลอดภัย ระบบการสร้างความมั่นใจพื้นฐานถูกแบ่งเป็นสองขั้นตอน: เวลาสร้างความมั่นใจและเวลาเปิดเผย (หรือเปิดเผย)

1. ขั้นตอนการยืนยัน: ในขั้นตอนนี้ ผู้ยืนยันใช้อัลกอริทึมทางคริปโตเกราะเพื่อผูกข้อความกับค่าการยืนยันและส่งค่าการยืนยันนี้ไปยังผู้รับ ในขั้นนี้ การยืนยันมีสองคุณสมบัติ: การซ่อนและการผูก การซ่อนทำให้เนื้อหาของข้อความที่ถูกยืนยันไม่ทราบโดยใคร ยกเว้นผู้ยืนยัน เชื่อมั่นทำให้เมื่อมีการยืนยันแล้ว จะไม่สามารถเปลี่ยนแปลงได้โดยผู้ใด รวมถึงผู้ยืนยันเอง
2. เปิดเผย (เปิด) เฟส: ในช่วงเวลานี้ ผู้บันทึกสามารถพิสูจน์กับผู้รับว่าค่าการกระทำที่พวกเขาได้รับเป็นการกระทำที่ถูกต้องต่อข้อความเดิม การกระทำมีคุณสมบัติของความถูกต้องซึ่งหมายความว่าหากทั้งผู้บันทึกและผู้รับปฏิบัติตามโปรโตคอลอย่างถูกต้องผู้รับจะถูกโน้มน้าวว่าค่าการกระทำที่พวกเขาได้รับในช่วงการกระทำเป็นการกระทำที่ถูกต้องต่อข้อความเดิม

การสัญญาเวกเตอร์เป็นชนิดพิเศษของวิธีการสัญญาที่ถูกเสนอโดย Catalano et al. [2] ซึ่งช่วยให้ผู้สัญญาสามารถทำการสัญญากับเซ็ตของข้อความที่เรียงลำดับ 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ และเปิดเผย (open) ที่ตำแหน่งใดตำแหน่งหนึ่งเพื่อพิสูจน์ว่าข้อความ 𝑚𝑖 เป็นข้อความที่ถูกสัญญาไว้ที่ตำแหน่งที่ i ในการสัญญาเวกเตอร์ การผูกมั่นหมายถึงไม่มีใครสามารถเปิดตำแหน่งเดียวกันเพื่อเปิดเผยข้อความที่แตกต่างกัน

โดยทั่วไประบบการสร้างความมั่นใจเวกเตอร์ประกอบด้วยอัลกอริทึมต่อไปนี้:

5. ต้นไม้ Verkle

5.1. นิยามและลักษณะของ Verkle Trees

Definition：Verkle Trees = Vector Commitments + Merkle Trees。

โปรดทราบ: Vitalik Buterin, ผู้ร่วมก่อตั้งของ Ethereum, มีบล็อกโพสต์ที่มีการกำหนดเฉพาะกับการแนะนำต้นไม้ Verkle บทนี้เพิ่มบางพื้นหลังและความรู้ทางคณิตศาสตร์โดยอ้างอิงจากเว็บบล็อกของเขา บางส่วนของข้อมูลและภาพประกอบในข้อความต่อไปนี้มาจากเว็บบล็อกของเขา

ต้นไม้ Verkle (VTs) จะมีลักษณะที่ให้พิสูจน์ขนาดเล็กกว่าเมอร์เคิลทรี สำหรับข้อมูลขนาดพันล้านรายการ เมอร์เคิลทรีอาจสร้างพิสูจน์ขนาดประมาณ 1KB ในขณะที่พิสูจน์ของต้นไม้ Verkle สามารถมีขนาดน้อยกว่า 150 ไบต์ ขนาดพิสูจน์ที่กระชับนี้เป็นประโยชน์ในการนำไปปฏิบัติstateless clients”.

โครงสร้างของต้นไม้ Verkle คล้ายกับ Merkle Patricia Tree (MPT) ถึงบางประการ ต่อไปนี้คือตัวอย่างของโครงสร้าง โหนดของต้นไม้ Verkle สามารถเป็น: (i) ว่าง (ii) โหนดใบที่มีคีย์และค่าที่สอดคล้องกัน หรือ (iii) โหนดภายในที่มีจำนวนโหนดลูกคงที่ จำนวนโหนดลูกเหล่านี้เรียกว่า “ความกว้าง” ของต้นไม้

ความแตกต่างระหว่าง VT (Verkle Trees) และ MPT (Merkle Patricia Trees) อยู่โดยส่วนใหญ่ในวิธีที่ความกว้างของต้นไม้ (หรือความห่างระหว่างลำต้น ซึ่งอ้างถึงจำนวนของลูกโหลดที่ลำต้นในต้นไม้มี) มีผลต่อประสิทธิภาพของพวกเขา ในกรณีของ MPT หากความกว้างใหญ่ขึ้น มันจะมีความไมมากเพราะความกว้างที่มากกว่าหมายถึงลูกโหลดที่มากขึ้น ซึ่งอาจทำให้มีเวลาอัพเดทยาวขึ้นสำหรับ MPT และขนาดพิสูที่ใหญ่ขึ้น ในทางกลับกันสำหรับ VT ความกว้างของต้นไม้ที่กว้างขึ้นนั้นทำให้พิสูที่เล็กลง ข้อจำกัดเพียงอยู่ที่หากความกว้างสูงเกินไป เวลาที่ใช้ในการสร้างพิสูอาจกลายเป็นเวลานานขึ้น

ใน Ethereum’s @vbuterin/verkle_tree_eip">การออกแบบข้อเสนอสำหรับ VTs แนะนำความกว้างของ 256 ซึ่งมากกว่าปัจจุบัน 16 สำหรับ MPT อย่างมาก ความกว้างขนาดใหญ่นี้เป็นไปได้ใน VTs เนื่องจากการใช้เทคโนโลยีเข้ารหัสลับขั้นสูง เช่น vector commitments ซึ่งทำให้ proof เข้มงวดได้โดย compact โดยไม่ว่าถึงความกว้างของต้นไม้ ทางเทคนิคการบีบอัดนี้ทำให้ Verkle Trees สามารถมีประสิทธิภาพในเรื่องขนาด proof ได้อย่างมีประสิทธิภาพมากขึ้น ข้อความต่อไปจะอธิบายคุณสมบัติที่กล่าวถึงข้างต้นอย่างละเอียด

5.2. การยินยอมและพิสูจน์ของต้นไม้ Verkle

เรามาดูกันว่าหลักฐานถูกสร้างขึ้นใน MPT อย่างไร: การพิสูจน์ต้องรวมค่าแฮชของโหนดด้านข้างทั้งหมด (หรือโหนดน้องสาว) บนเส้นทางจากโหนดรากไปยังโหนดใบเป้าหมาย ยกตัวอย่าง "4ce" ชิ้นส่วนที่ทําเครื่องหมายเป็นสีแดงในแผนภาพด้านล่างเป็นโหนดที่ต้องรวมอยู่ในหลักฐานที่ส่งคืน

ในต้นไม้ Verkle คุณไม่จำเป็นต้องให้โหนด兄弟แทนที่คุณเพียงจำเป็นต้องให้เส้นทางพร้อมกับข้อมูลเพิ่มเติมเป็นหลักฐาน

ดังนั้นวิธีการสร้างความมั่นใจสำหรับ VT คืออะไร? ฟังก์ชันแฮชที่ใช้สำหรับการคำนวณไม่ใช่แฮชแบบดั้งเดิม แต่ใช้ความมั่นใจเวกเตอร์

หลังจากที่ทำการแทนที่ฟังก์ชันแฮชด้วยอัลกอริทึมการสร้างความมั่นใจจากการสัญญาณเวกเตอร์ เราเรียกค่าแฮชนี้ว่าค่าความมั่นใจเริ่มต้น หากข้อมูลของโหนดใดๆ ถูกแก้ไข มันจะมีผลต่อค่าความมั่นใจเริ่มต้น

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

ในการปฏิบัติจริงการสัญญาก่อนหน้าถูกใช้งาน (ซึ่งสามารถนำมาใช้งานได้อย่างง่ายและมีประสิทธิภาพสำหรับการสัญญาก่อนหน้าเวกเตอร์) ทำให้สามารถทำสัญญาก่อนหน้ากับหลักการได้ โครงการสัญญาก่อนหน้าที่เป็นที่นิยมที่สุดสองระบบคือความมุ่งมั่นของ KZG” และ “ความมั่นคงเหมือนกระสุนของ polynomial commitments(ส่วนแรกมีขนาดความสำคัญของ 48 ไบต์ ในขณะที่ส่วนหลังมี 32 ไบต์)

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

ความซับซ้อนทฤษฎีเวลาสำหรับการดำเนินการบนต้นไม้ Merkle และต้นไม้ Verkle คือดังนี้:

โครงการพิสูจน์ Verkle ที่ถูกนำเสนอจนถึงตอนนี้เป็นพื้นฐานเพียงอย่างเดียว; ในความเป็นจริงยังมีกลยุทธ์การปรับปรุงระดับสูงเพิ่มเติมที่มีอยู่

5.3. การปรับปรุง: การผสานพิสูจน์

5.3.1. ไอเดีย

เมื่อเทียบกับการสร้างหลักฐานสําหรับแต่ละชั้นของภาระผูกพันบนเส้นทางลักษณะของพันธะพหุนามสามารถใช้เพื่อให้บรรลุ "การพิสูจน์ความสัมพันธ์ระหว่างพ่อแม่และลูกระหว่างภาระผูกพันทั้งหมดบนเส้นทางด้วยการพิสูจน์ขนาดคงที่ซึ่งอาจรวมถึงองค์ประกอบได้ไม่ จํากัด จํานวน" เพื่อให้เข้าใจโดยเฉพาะว่าสิ่งนี้สําเร็จได้อย่างไรจําเป็นต้องแนะนําความรู้ทางคณิตศาสตร์เพื่ออธิบาย บทความนี้จะเกี่ยวข้องกับสูตรทางคณิตศาสตร์บางอย่าง แต่จะไม่ครอบคลุมส่วนการเข้ารหัสของการพิสูจน์ในหลักการ สําหรับวิธีการเฉพาะโปรดดูที่ โครงการที่นำมาปรับใช้ multiproofs ผ่านการประเมินแบบสุ่ม.

5.3.2. การถอดรหัสทางคณิตศาสตร์

ก่อนอื่นเรามาแนะนำแนวคิดพื้นฐานเกี่ยวกับพหุคูณในคณิตศาสตร์: เราจะดำเนินการลดพหุคูณอย่างไร หรือที่รู้จักกันในนามการลดดีกรีของพหุคูณ?

สมมติว่าเราทราบ多項式 𝑃(𝑥) และค่าของมันที่ 𝑥₁ คือ 𝑦₁ นั่นคือ 𝑃(𝑥₁) = 𝑦₁

ตอนนี้ พิจารณา多項式 𝑃(𝑥) - 𝑦₁ ใหม่ ซึ่งมีค่าเป็นศูนย์ที่ (𝑥 = 𝑥₁) เพราะ 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0

ดังนั้น พหุนาม 𝑃(𝑥) - 𝑦₁ มีรากที่ 𝑥 = 𝑥₁ ซึ่งหมายความว่า (𝑥 - 𝑥₁ ) เป็นปัจจัยของ 𝑃(𝑥) - 𝑦₁

กล่าวอีกอย่างคือเราสามารถแสดงในรูปแบบต่อไปนี้: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) เป็นพหุนัยอีกตัวที่มีดีกรีน้อยกว่า 𝑃(𝑥) โดยเหตุนี้เกิดจาก (𝑥 -𝑥₁ ) เป็นปัจจัยดีกรีหนึ่ง ซึ่งลดดีกรีรวมของพหุนัย

วิธีใช้ KZG เพื่อพิสูจน์ค่าเดียวในเวกเตอร์

เรียกความมุ่งมั่น KZG10 เป็นตัวอย่าง สำหรับพหุนาม 𝑃(𝑥) , สมมติว่าความมุ่งมั่นของพหุนามนี้คือ [ 𝑃(𝑠) ]₁.

เหมือนกับที่ได้อธิบายไว้ก่อนหน้านี้ สำหรับพหุนาม 𝑃(𝑥) ถ้า 𝑃(𝑧) = 𝑦 แล้วเราจะได้ 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)

ตอนนี้พิสูจน์ได้สร้างพิสูจน์ที่ polynomial 𝑃(𝑥) ทำให้ 𝑃(𝑧) = 𝑦 : คำนวณ [ 𝑄(𝑠) ]₁ และส่งไปยังผู้ตรวจสอบ

ผู้ตรวจสอบจำเป็นต้องทำการตรวจสอบ 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂)

การใช้ KZG เพื่อพิสูจน์ค่า multiple ในเวกเตอร์

เราสามารถสร้างพิสูจน์เพื่อแสดงค่าหลายค่าในเวกเตอร์ได้ดังนี้:

โดยใช้วิธีนี้ ไม่ว่าจำนวนข้อมูลจุดใดในเวกเตอร์เดียวกันที่ต้องการที่จะตรวจสอบ จะต้องใช้พิสูจน์ขนาดคงที่เท่านั้น

ตอนนี้เราจะมองไปที่ระบบ Verkle Tree โดยไม่มีการปรับปรุงจากมุมมองของอัลกอริทึมการสังหาร KZG

โดยใช้วิธีก่อสร้างจากส่วน “วิธีใช้ KZG เพื่อพิสูจน์ค่าเดียวในเวกเตอร์” ผู้ทดสอบสามารถก่อสร้างการสนับสนุนสำหรับพหลมอิเฟเดียลและหารส่วนสำหรับทุกๆ พหลมอี(เอ็กซ์) ทำให้มีทั้งหมด 𝟐﹡𝑚 การสนับสนุน KZG ผู้ทดสอบส่งการสนับสนุนทั้งหมดเหล่านี้เป็นพิสูจน์สำหรับการตรวจสอบ

อย่างไรก็ตาม ตามที่กล่าวไว้ก่อนหน้านี้ วิธีการนี้ต้องการการสร้างพิสูจน์ที่เป็นจำนวนมาก และผู้ตรวจก็ต้องทำการคำนวณการตรวจสอบจำนวนมากเช่นกัน เราต้องหาวิธีในการบีบอัดพิสูจน์การสมัครมากๆ

การผสานพิสูจน์

ผู้พิสูจน์ส่งพิสูจน์ [ 𝑞( 𝑠 )]₁ ไปยังผู้ตรวจสอบเพื่อการตรวจสอบ

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

1. หลักฐานขนาดคงที่
2. ข้อมูลของใบไม้ที่จะพิสูจน์ (คู่ค่าคีย์)
3. ค่าการสร้างความมั่นใจของโหนดทั้งหมดในเส้นทางจากใบไปสู่ราก (ในกรณีที่มีความกว้างของต้นไม้ 256 โหนด 2³² โหนด แล้วความลึกเฉลี่ยคือ 4 ต้องการเพียง 3 ค่าการสร้างความมั่นใจ)

โปรดทราบว่า 𝑥ᵢ และ 𝑦ᵢ ไม่จำเป็นต้องระบุโดยชัดเจน; สามารถคำนวณทั้งหมดได้

5.3.3. ประสิทธิภาพ

เกี่ยวกับแผนงานการรวมพิสูจน์สำหรับต้นไม้เวอร์เคิล ขนาดเฉพาะของพิสูจน์ที่สร้างขึ้นคือดังนี้ (หน่วยของแถวคือพันล้าน)

ข้อมูลข้างต้นถือว่าใช้ต้นไม้ที่มีความกว้าง 256 โดยใช้ระบบการสัญญาณการยืนยัน KZG (พร้อมขนาดการยืนยันของ 48 ไบต์) และสูงสุดการใช้ประโยชน์จากต้นไม้ ในการปฏิบัติ สำหรับการกระจายของข้อมูลที่สุ่มแบบเต็ม ความลึกของต้นไม้จะเพิ่มขึ้นประมาณ 60% และขนาดของแต่ละองค์จะเพิ่มขึ้น 30 ไบต์ หากใช้ระบบกระแสแบบกันกระสุน จะมีขนาดการยืนยันคือ 32 ไบต์

5.4. โหลดการคำนวณของ Prover และ verifier

1. การสร้างพิสูจน์: ค่าใช้จ่ายในการสร้างพิสูจน์โดยผู้พิสูจน์เกี่ยวข้องกับความกว้างของต้นไม้ แต่การดำเนินการแอตอมิกแต่ละตัวต้องใช้ค่าที่สูงไม่มาก ดังนั้น ต้นไม้เวอร์เคิลที่มีความกว้างระหว่าง 256 และ 1024 ทำงานได้ดีตามอัลกอริทึม
2. การยืนยันความถูกต้อง: วิทาลิคได้ระบุว่าอัลกอริทึมการยืนยันเร็วมากและโดยทั่วไปสามารถเสร็จสิ้นภายใน 100 มิลลิวินาที แม้ว่าจะมีค่าหลายพันค่าที่ต้องยืนยัน
3. เมื่ออัปเดตต้นไม้เวอร์เคิล: การอัปเดตต้นไม้ต้องการคำนวณค่าความมั่นใจระหว่างทางที่กลายเป็นค่าทางกลับเมื่อมีการเปลี่ยนแปลงค่าหรือโครงสร้าง อย่างไรก็ตาม Vitalik กล่าวถึงว่า ด้วยคุณสมบัติบางประการของอัลกอริทึมการมั่นใจสมการหลายๆ อย่าง มีทางที่จะออกแบบวิธีที่ทำการคำนวณค่าความมั่นใจทางเลือกไว้ล่วงหน้าและเก็บไว้ ซึ่งทำให้ลดเวลาที่ใช้ในการคำนวณลง ซึ่งพื้นที่สำหรับเวลา ในระหว่างการอัปเดต ซึ่งในทางปฏิบัติคือการแลกเปลี่ยนพื้นที่เพื่อเวลา

6. สรุป

ข้อความต้นฉบับของบล็อกวิทาลิค ที่มีเนื้อหาดังต่อไปนี้ เราได้เพิ่มย่อหน้าท้ายสำหรับเป็นเสริม

Verkle trees are a powerful upgrade to Merkle proofs that allow for much smaller proof sizes. Instead of needing to provide all “sister nodes” at each level, the prover need only provide a single proof that proves all parent-child relationships between all commitments along the paths from each leaf node to the root. This allows proof sizes to decrease by a factor of ~6–8 compared to ideal Merkle trees, and by a factor of over 20–30 compared to the hexary Patricia trees that Ethereum uses today (!!).

พวกเขาต้องการการเข้ารหัสที่ซับซ้อนมากขึ้นเพื่อนําไปใช้ แต่พวกเขานําเสนอโอกาสในการทํากําไรจํานวนมากเพื่อปรับขนาดได้ ในระยะกลาง SNARKs สามารถปรับปรุงสิ่งต่าง ๆ เพิ่มเติมได้: เราสามารถ SNARK ตัวตรวจสอบหลักฐาน Verkle ที่มีประสิทธิภาพอยู่แล้วเพื่อลดขนาดพยานให้ใกล้ศูนย์หรือเปลี่ยนกลับไปใช้ SNARKed Merkle proofs หาก / เมื่อ SNARKs ดีขึ้นมาก (เช่นผ่าน GKR หรือฟังก์ชันแฮชที่เป็นมิตรกับ SNARK หรือ ASICs) การเพิ่มขึ้นของการคํานวณควอนตัมจะบังคับให้มีการเปลี่ยนแปลงการพิสูจน์ STARKed Merkle ด้วยแฮชเนื่องจากทําให้ homomorphisms เชิงเส้นที่ต้นไม้ Verkle ขึ้นอยู่กับความไม่ปลอดภัย แต่สําหรับตอนนี้พวกเขาให้ผลกําไรจากการปรับขนาดแบบเดียวกับที่เราจะได้รับจากเทคโนโลยีขั้นสูงดังกล่าวและเรามีเครื่องมือทั้งหมดที่เราต้องการเพื่อนําไปใช้อย่างมีประสิทธิภาพ

ในปัจจุบัน มีลูกค้า Ethereum มากมายที่ได้ให้การประมวลผลของต้นไม้ Verkle และเครือข่ายทดสอบที่เกี่ยวข้อง ชุมชนกำลังพูดถึงเวลาที่ต้นไม้ Verkle จะถูกเปิดใช้ในเครือข่ายหลัก น่าจะถูกนำมาใช้ในการอัพเกรดโฮร์ดฟอร์คในปี 2024 หรือ 2025 สำหรับข้อมูลเพิ่มเติมเกี่ยวกับต้นไม้ Verkle บน Ethereum ดูที่https://verkle.info/ .

7. การอ้างอิง

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. พิสูจน์การระบุขั้นต่ำของความรู้[J]. วารสารวิทยาการคอมพิวเตอร์และระบบ, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. การสัญญาเวกเตอร์และการประยุกต์ของพวกเขา [C] // การเขียนรหัสโดยใช้คีย์สาธารณะ - PKC 2013: ประชุมวิชาการระหว่างปฏิบัติและทฤษฎีในการเขียนรหัสโดยใช้คีย์สาธารณะครั้งที่ 16 ณ นาระ ญี่ปุ่น วันที่ 26 กุมภาพันธ์ - 1 มีนาคม 2013 พิจารณา 16. Springer, 2013: 55-72.

ข้อความปฏิเสธความรับผิดชอบ：

1. บทความนี้พิมพ์ซ้ําจาก [ZAN], ลิขสิทธิ์ทั้งหมดเป็นของผู้เขียนต้นฉบับ [AntChain Open Labs และ ZAN]. หากมีข้อคิดเห็นเกี่ยวกับการพิมพ์ฉบับนี้ กรุณาติดต่อGate Learnทีมและพวกเขาจะดำเนินการโดยเร็ว
2. คำปฏิเสธความรับผิด: มุมมองและความเห็นที่แสดงในบทความนี้เป็นเพียงของผู้เขียนเท่านั้น และไม่เป็นคำแนะนำในการลงทุนใด ๆ
3. การแปลบทความเป็นภาษาอื่นๆ จะทำโดยทีม Gate Learn หากไม่ได้กล่าวถึง การคัดลอก การกระจาย หรือการลอกเลียนบทความที่ถูกแปลนั้นถือเป็นการละเมิดลิขสิทธิ์