อะไรคือหลักฐานหลายค่าของต้นไม้ Merkle ที่เบาบาง

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

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

, ผู้แต่ง: Jim McDonald, แปลและพิสูจน์อักษร: Pei Qi & A Jian, พิมพ์ซ้ำโดยได้รับอนุญาตจาก Odaily

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

วิทยาศาสตร์ยอดนิยม | การตัด Merkel คืออะไร

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

คำอธิบายภาพ

บทพิสูจน์หลายค่าแบบเบาบางถูกเสนอครั้งแรกโดย Vitalik Buterin

หลักฐานหลายค่า

คำอธิบายภาพ

-รูปที่ 2, 3 และ 4: การพิสูจน์ของ Merkel ที่สอดคล้องกับ Banana, Peach และ Kumquat ตามลำดับ-

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

คำอธิบายภาพ

-รูปที่ 5: หลักฐานหลายค่าของ Merkle ที่สอดคล้องกับ Banana, Peach และ Kumquat-

หลักฐานหลายค่ากระจัดกระจาย

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

คำอธิบายภาพ

-รูปที่ 6: ค่าแฮชที่สามารถลบออกได้ในการพิสูจน์แบบหลายค่าของ Merkle tree (ดูเครื่องหมายสีเหลือง)-

หลังจากลบค่าแฮชเหล่านี้แล้ว สามารถรับการพิสูจน์แบบหลายค่าแบบกระจายใน Merkle tree ดังแสดงในรูปต่อไปนี้:

คำอธิบายภาพ

-รูปที่ 7: การพิสูจน์หลายค่าของต้นไม้ Merkle แบบเบาบาง-

• การพิสูจน์หลายค่าของ Merkle แบบเบาบางช่วยลดจำนวนแฮชที่ต้องรวมจาก 9 เป็น 3 การพิสูจน์แบบหลายค่าแบบกระจัดกระจายยังมีประสิทธิภาพมากกว่าการพิสูจน์แบบตัดทอนของ Merkle ซึ่งต้องใช้ 6 แฮชสำหรับการพิสูจน์แบบเดียวกัน

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

• (หมายเหตุผู้แปล: "แฮชค่า" หมายถึง: ใช้ค่าเป็นอินพุตของฟังก์ชันแฮช และรับเอาต์พุตสตริงแบบสุ่ม)

• แฮชบานาน่าเพื่อรับ bc4f...8d3f

• แฮชพีชเพื่อรับ 59a0…421d

• แฮช Kumquat เพื่อรับ 2aab…6f791

• แฮช bc4f...8d3f และ 59a0...421d เพื่อรับ 9c15...5dec

• แฮช 2aab…6f79 และ 45cf…14d9 เพื่อรับ a6e4…87df

แฮช d596…66ef และ 9c15…5dec เพื่อรับ c0b7…da30

แฮช e336…ed14 และ a6e4…87df เพื่อรับ 6ff9…8e3d

แฮช c0b7...da30 และ 6ff9...8e3d เพื่อรับ d576...ffd9

ณ จุดนี้ ค่าแฮชสุดท้ายสามารถเปรียบเทียบได้กับค่าแฮชรูทของ Merkle tree หากทั้งสองสอดคล้องกันค่าทั้งหมดจะถูกกำหนดให้อยู่ใน Merkle tree

รูปต่อไปนี้เปรียบเทียบจำนวนพื้นที่เก็บข้อมูลที่ Merkle tree ตัดทอนและกระจัดกระจายการพิสูจน์หลายค่าใน Merkle tree สามารถประหยัดได้เมื่อจัดเก็บ Merkle proof เมื่อจำนวนค่าและการพิสูจน์ใน Merkle tree เปลี่ยนไป:

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

• การเปรียบเทียบการพิสูจน์ที่มีหลายค่าแบบกระจัดกระจายกับ Merkle ที่ถูกตัดทอน

• ดังที่เห็นได้จากตารางด้านบน การพิสูจน์แบบหลายค่าแบบกระจัดกระจายช่วยประหยัดพื้นที่จัดเก็บได้มากกว่าการตัดทอนต้นไม้ของ Merkle เหตุใดจึงต้องใช้การตัดทอนต้นไม้ของ Merkle เนื่องจากการพิสูจน์ที่มีหลายค่าแบบกระจัดกระจายมีลักษณะที่แตกต่างกันบางประการเมื่อเทียบกับ Merkle tree ที่ถูกตัดทอน ประเด็นหลักมีดังนี้:

• ในวิธีการพิสูจน์แบบหลายค่า การพิสูจน์สำหรับค่าทั้งหมดจะถูกสร้างและตรวจสอบร่วมกัน ในวิธีการตัดทอน การพิสูจน์สำหรับแต่ละค่าจะถูกสร้างขึ้นและตรวจสอบแยกกัน ในแง่ของการตัดทอน ค่าใดเจาะจงเฉพาะค่านี้ และจำเป็นต้องมีการพิสูจน์ที่เกี่ยวข้องสำหรับการพิสูจน์แบบหลายค่าจะต้องนำค่าหลายค่าที่ต้องตรวจสอบและพิสูจน์ที่สอดคล้องกันของค่าหลายค่าออก)

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

การพิสูจน์หลายค่าแบบกระจัดกระจายนั้นสร้างและตรวจสอบควบคู่กันไปได้ยาก

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

https://github.com/ในบางกรณี เนื่องจากระบบการเข้ารหัสที่แตกต่างกันที่ใช้ในการส่งข้อมูล อาจทำให้การพิสูจน์หลายค่ากระจัดกระจายต้องใช้พื้นที่มากกว่าการตัดต้นไม้ Merkle ดังนั้นจึงแนะนำให้ทดสอบก่อนใช้งาน