ต้นไม้ Verkle คือรูปแบบการผูกมัดที่ทำงานคล้ายกับต้นไม้ Merkle แต่มีพยานที่เล็กกว่ามาก โดยทำงานโดยการแทนที่แฮชในต้นไม้ Merkle ด้วยเวกเตอร์ผูกมัด ซึ่งทำให้ปัจจัยการแยกสาขาที่กว้างขึ้นมีประสิทธิภาพมากขึ้น
ขอขอบคุณ Kevaundray Wedderburn สำหรับคำติชมเกี่ยวกับโพสต์นี้
ภาพรวม
สำหรับรายละเอียดเกี่ยวกับการทำงานของต้นไม้ Verkle โปรดดูที่:
จุดประสงค์ของโพสต์นี้คือการอธิบายเค้าโครงคอนกรีตของ ร่างต้นไม้เวอร์เคิล EIPมุ่งเป้าไปที่นักพัฒนาไคลเอนต์ที่ต้องการนำ Verkle Bushes มาใช้และกำลังมองหาคำแนะนำก่อนที่จะเจาะลึก EIP
ต้นไม้ Verkle ทำให้เกิดการเปลี่ยนแปลงหลายประการต่อโครงสร้างของต้นไม้ การเปลี่ยนแปลงที่สำคัญที่สุด ได้แก่:
- การสลับจากคีย์ 20 ไบต์เป็นคีย์ 32 ไบต์ (อย่าสับสนกับที่อยู่ 32 ไบต์ซึ่งเป็นการเปลี่ยนแปลงที่แยกต่างหาก)
- การผสานบัญชีและการพยายามจัดเก็บข้อมูล และสุดท้าย
- การแนะนำของ verkle trie เองซึ่งใช้การมุ่งมั่นเวกเตอร์แทนแฮช
เนื่องจากเป็นโครงร่างความมุ่งมั่นของเวกเตอร์สำหรับต้นไม้ Verkle เราใช้ ความมุ่งมั่นของพีเดอร์เซนข้อผูกมัดของ Pedersen นั้นมีพื้นฐานมาจากเส้นโค้งวงรี สำหรับคำแนะนำเกี่ยวกับข้อผูกมัดของ Pedersen และวิธีใช้เป็นข้อผูกมัดพหุนามหรือเวกเตอร์โดยใช้อาร์กิวเมนต์ผลคูณภายใน โปรดดู ที่นี่–
เส้นโค้งที่เรากำลังใช้อยู่คือ แบนเดอร์สแนทช์เราเลือกเส้นโค้งนี้เพราะมีประสิทธิภาพและยังช่วยให้ SNARK ที่มีประสิทธิภาพใน BLS12_381 สามารถหาเหตุผลเกี่ยวกับต้นไม้ Verkle ได้ในอนาคต ซึ่งอาจมีประโยชน์สำหรับการสรุปข้อมูล รวมถึงช่วยให้สามารถอัปเกรดโดยสามารถบีบอัดพยานทั้งหมดให้เหลือ SNARK เดียวได้เมื่อทำได้จริง โดยไม่ต้องอัปเดตการยืนยันเพิ่มเติม
ลำดับเส้นโค้ง/ขนาดสนามสเกลาร์ของแบนเดอร์สแนตช์คือ พี = 13108968793781547619861935127046491459309155893440570251786403306729687672801ซึ่งเป็นไพรม์ขนาด 253 บิต ด้วยเหตุนี้ เราจึงสามารถคอมมิตสตริงบิตที่มีขนาดไม่เกิน 252 บิตได้อย่างปลอดภัย มิฉะนั้น ฟิลด์จะล้น เราเลือกแฟกเตอร์การแยกสาขา (ความกว้าง) เป็น 256 สำหรับเวอร์เคิลทรี ซึ่งหมายความว่าการคอมมิตแต่ละครั้งสามารถคอมมิตค่าได้สูงสุด 256 ค่า โดยแต่ละค่าจะมีขนาด 252 บิต (หรือเพื่อให้แม่นยำยิ่งขึ้น คือ จำนวนเต็มสูงสุดถึง พี – 1). เราเขียนสิ่งนี้เป็น คอมมิต (v₀, v₁, …, v₂₅₅) ที่จะมุ่งมั่นในรายการ วี มีความยาว 256.
เค้าโครงของต้นเวอร์เคิล
เป้าหมายการออกแบบอย่างหนึ่งของ EIP แบบเวอร์เคิลทรีคือการทำให้การเข้าถึงตำแหน่งใกล้เคียง (เช่น พื้นที่เก็บข้อมูลที่มีที่อยู่เกือบจะเหมือนกันหรือชิ้นส่วนโค้ดใกล้เคียง) เข้าถึงได้ในราคาที่ถูก เพื่อทำเช่นนี้ คีย์จะประกอบด้วย ก้าน ของ 31 ไบต์และ คำต่อท้าย ของหนึ่งไบต์สำหรับทั้งหมด 32 ไบต์ โครงร่างคีย์ได้รับการออกแบบเพื่อให้ตำแหน่งจัดเก็บ “แบบใกล้เคียง” ถูกแมปกับสเต็มเดียวกันและต่อท้ายที่แตกต่างกัน สำหรับรายละเอียด โปรดดูที่ ร่าง พ.ร.บ.ส.ป.–
ต้นไม้ Verkle ประกอบด้วยโหนดสองประเภท:
- โหนดส่วนขยายที่แสดงค่า 256 ค่าที่มีลำต้นเหมือนกันแต่มีคำต่อท้ายต่างกัน
- โหนดภายในซึ่งมีโหนดย่อยสูงสุด 256 โหนด ซึ่งอาจเป็นโหนดภายในหรือโหนดส่วนขยายอื่นๆ ก็ได้
การมุ่งมั่นต่อโหนดส่วนขยายคือการมุ่งมั่นต่อเวกเตอร์ 4 องค์ประกอบ ตำแหน่งที่เหลือจะเป็น 0 นั่นคือ:
C₁ และ C₂ เป็นข้อผูกมัดเพิ่มเติมอีกสองข้อที่มุ่งมั่นต่อค่าทั้งหมดที่มีค่าเท่ากับ ก้านเหตุผลที่เราต้องมีการคอมมิทต์สองครั้งก็คือค่าต่างๆ มี 32 ไบต์ แต่เราสามารถจัดเก็บได้เพียง 252 บิตต่อองค์ประกอบฟิลด์ ดังนั้นการคอมมิทต์เพียงครั้งเดียวจึงไม่เพียงพอที่จะจัดเก็บค่าได้ 256 ค่า ดังนั้น C₁ จึงจัดเก็บค่าสำหรับค่าต่อท้าย 0 ถึง 127 และ C₂ จัดเก็บค่า 128 ถึง 255 โดยค่าจะถูกแบ่งออกเป็นสองส่วนเพื่อให้พอดีกับขนาดฟิลด์ (เราจะพูดถึงเรื่องนี้ในภายหลัง)
ส่วนขยายพร้อมกับพันธกรณี C₁ และ C₂ เรียกกันว่า “ต้นไม้ส่วนขยายและคำต่อท้าย” (ย่อว่า EaS)
รูปที่ 1 การแสดงการเดินผ่านต้นไม้ Verkle สำหรับกุญแจ 0xfe0002abcd..ff04: เส้นทางจะผ่านโหนดภายใน 3 โหนด โดยแต่ละโหนดมีโหนดย่อย 256 โหนด (254, 0, 2) โดยมีโหนดส่วนขยาย 1 โหนดที่แสดง กขก..ff และคำมั่นสัญญาต่อท้ายสองรายการรวมถึงค่าสำหรับ 04v₄. โปรดทราบว่า ก้าน คือ 31 ไบต์แรกของคีย์ รวมถึงเส้นทางผ่านโหนดภายในด้วย
มุ่งมั่นต่อคุณค่าของโหนดใบ
แต่ละโหนดของต้นไม้ส่วนขยายและส่วนต่อท้ายจะมีค่า 256 ค่า เนื่องจากค่ามีความกว้าง 256 บิต และเราสามารถจัดเก็บได้อย่างปลอดภัยเพียง 252 บิตในองค์ประกอบฟิลด์หนึ่งองค์ประกอบ ดังนั้นจะสูญเสียบิตสี่บิตหากเราพยายามจัดเก็บค่าหนึ่งค่าในองค์ประกอบฟิลด์หนึ่งองค์ประกอบ
เพื่อหลีกเลี่ยงปัญหานี้ เราจึงเลือกที่จะแบ่งกลุ่มค่า 256 ค่าออกเป็น 2 กลุ่ม กลุ่มละ 128 ค่า โดยค่า 32 ไบต์ในแต่ละกลุ่มจะถูกแบ่งออกเป็น 2 ค่า กลุ่มละ 16 ไบต์ ดังนั้น ค่า vᵢ∈ 𝔹₃₂ จึงเปลี่ยนเป็น v⁽ˡᵒʷᵉʳ⁾ᵢ ∈ 𝔹₁₆ และ v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ 𝔹₁₆ โดยที่ v⁽ˡᵒʷᵉʳ⁾ᵢ ++ v⁽ᵘᵖᵖᵉʳ⁾ᵢ= vᵢ.
เพิ่ม “เครื่องหมายใบ” ลงใน v⁽ˡᵒʷᵉʳ⁾ᵢ เพื่อแยกความแตกต่างระหว่างใบที่ไม่เคยถูกเข้าถึงและใบที่ถูกเขียนทับด้วย 0 ไม่มีค่าใดถูกลบออกจากต้นไม้ Verkleสิ่งนี้จำเป็นสำหรับแผนการหมดอายุสถานะที่กำลังจะมาถึง เครื่องหมายดังกล่าวจะถูกตั้งไว้ที่บิตที่ 129 นั่นคือ v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = v⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ ถ้า vᵢ เคยเข้าถึงมาก่อน และ v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = 0 ถ้า vᵢ ไม่เคยเข้าถึงเลย
ความมุ่งมั่นสองประการ C₁ และ C₂ ได้รับการกำหนดเป็น
การมุ่งมั่นของโหนดส่วนขยาย
การมุ่งมั่นต่อโหนดส่วนขยายประกอบด้วย “เครื่องหมายส่วนขยาย” ซึ่งเป็นเพียงหมายเลข 1 การมุ่งมั่นของซับทรีสองอันคือ C₁ และ C₂ และ ก้าน ของคีย์ที่นำไปสู่โหนดส่วนขยายนี้
ไม่เหมือนกับโหนดส่วนขยายในต้นไม้ Merkle-Patricia ซึ่งมีเพียงส่วนของคีย์ที่เชื่อมระหว่างโหนดภายในของผู้ปกครองกับโหนดภายในของลูก สเต็มจะครอบคลุมคีย์ทั้งหมดจนถึงจุดนั้น เนื่องจากต้นไม้ Verkle ได้รับการออกแบบมาโดยคำนึงถึงการพิสูจน์แบบไร้สถานะ: หากมีการแทรกคีย์ใหม่ที่ “แบ่ง” ส่วนขยายออกเป็นสองส่วน ก็ไม่จำเป็นต้องอัปเดตโหนดที่เก่ากว่า ซึ่งทำให้สามารถพิสูจน์ได้เล็กลง
ความมุ่งมั่นของโหนดภายใน
โหนดภายในมีวิธีการคำนวณที่ง่ายกว่าสำหรับการคอมมิตของโหนด: โหนดนั้นถูกมองว่าเป็นเวกเตอร์ของค่า 256 ค่า ซึ่งเป็นการคอมมิตรูท (การแสดงฟิลด์ของ) ของแต่ละซับทรี 256 ซับทรี การคอมมิตสำหรับซับทรีว่างคือ 0 หากซับทรีไม่ว่าง การคอมมิตสำหรับโหนดภายในคือ
โดยที่ Cᵢ คือลูกของโหนดภายใน และเป็น 0 ถ้าลูกนั้นว่างเปล่า
การแทรกเข้าไปในต้นไม้
รูปที่ 2 เป็นภาพประกอบกระบวนการในการแทรกค่าใหม่ลงในต้นไม้ ซึ่งจะน่าสนใจเมื่อสเต็มเกิดการชนกันในไบต์เริ่มต้นหลาย ๆ ตัว
รูปที่ 2 ค่า v₁₉₂ ถูกแทรกในตำแหน่ง 0000010000…0000 ในต้นไม้เวอร์เคิลที่มีค่า v₁₂₇ เฉพาะที่ตำแหน่ง 0000000000…0000เนื่องจากสเต็มต่างกันที่ไบต์ที่สาม โหนดภายในสองโหนดจึงถูกเพิ่มเข้าไปจนกระทั่งถึงไบต์ที่แตกต่างกัน จากนั้นจึงแทรกทรี “ส่วนขยายและคำต่อท้าย” อีกอันหนึ่งด้วยสเต็มขนาด 31 ไบต์ โหนดเริ่มต้นจะไม่ถูกแตะต้อง และ C²₀ มีค่าเท่ากับ C²⁰₀ ก่อนการแทรก
ต้นไม้ตื้นกว่า หลักฐานเล็กกว่า
โครงสร้างแบบเวอร์เคิลทรีทำให้ต้นไม้มีความลึกน้อยลง ซึ่งจะลดปริมาณข้อมูลที่จัดเก็บ อย่างไรก็ตาม พลังที่แท้จริงของโครงสร้างนี้มาจากความสามารถในการสร้างหลักฐานขนาดเล็ก เช่น พยาน ซึ่งจะอธิบายเรื่องนี้ในบทความถัดไป
