Merkle Timber เป็นส่วนพื้นฐานของสิ่งที่ทำให้ blockchains เห็บ แม้ว่ามันจะเป็นไปได้ในทางทฤษฎีที่จะสร้าง blockchain โดยไม่มีต้นไม้ merkle เพียงแค่สร้างส่วนหัวบล็อกยักษ์ที่มีการทำธุรกรรมโดยตรงทุกครั้งการทำเช่นนั้นทำให้เกิดความท้าทายในการปรับขนาดได้อย่างมาก ขอบคุณ Merkle Timber เป็นไปได้ที่จะสร้างโหนด Ethereum ที่ทำงานบนคอมพิวเตอร์และแล็ปท็อปทุกเครื่องสมาร์ทโฟนขนาดใหญ่และขนาดเล็กและแม้แต่อุปกรณ์อินเทอร์เน็ตของสิ่งต่าง ๆ เช่นที่จะผลิตโดย slock.it– ดังนั้นต้นไม้ merkle เหล่านี้ทำงานอย่างไรและพวกเขาให้คุณค่าอะไรทั้งในปัจจุบันและในอนาคต
ขั้นแรกพื้นฐาน ต้นไม้ Merkle โดยทั่วไปเป็นวิธีการแฮชข้อมูลจำนวนมากของข้อมูลเข้าด้วยกันซึ่งอาศัยการแยกชิ้นส่วนออกเป็นถังซึ่งแต่ละถังมีเพียงไม่กี่ชิ้นเท่านั้น
ต้นไม้ Merkle ที่พบได้ง่ายและเรียบง่ายที่สุดคือต้นไม้ Mekle แบบไบนารีที่ซึ่งถังมักประกอบด้วยชิ้นส่วนหรือแฮชที่อยู่ติดกันสองชิ้นเสมอ มันสามารถอธิบายได้ดังนี้:
ดังนั้นประโยชน์ของอัลกอริทึมการแฮชแบบแปลก ๆ นี้คืออะไร? ทำไมไม่เพียงแค่เชื่อมต่อชิ้นส่วนทั้งหมดเข้าด้วยกันเป็นก้อนใหญ่ตัวเดียวและใช้อัลกอริทึมการแฮชแบบปกติในนั้น? คำตอบคือมันช่วยให้กลไกเรียบร้อยที่รู้จักกันในชื่อ Merkle Proofs:
การพิสูจน์ merkle ประกอบด้วยก้อน, แฮชรากของต้นไม้และ “สาขา” ซึ่งประกอบด้วยแฮชทั้งหมดที่ขึ้นไปตามเส้นทางจากก้อนไปจนถึงราก คนที่อ่านหลักฐานสามารถตรวจสอบได้ว่าการแฮชอย่างน้อยก็สำหรับสาขานั้นมีความสอดคล้องกันไปตลอดทางขึ้นไปบนต้นไม้และดังนั้นจึงเป็นก้อนที่กำหนดอยู่ในตำแหน่งนั้นในต้นไม้ แอปพลิเคชันนั้นง่าย: สมมติว่ามีฐานข้อมูลขนาดใหญ่และเนื้อหาทั้งหมดของฐานข้อมูลจะถูกเก็บไว้ในต้นไม้ Merkle ที่รากของต้นไม้ Merkle เป็นที่รู้จักและเชื่อถือได้ (เช่นมันลงนามแบบดิจิทัลโดยฝ่ายที่เชื่อถือได้เพียงพอหรือมีหลักฐานการทำงานมากมาย) จากนั้นผู้ใช้ที่ต้องการทำการค้นหาคีย์-ค่าบนฐานข้อมูล (เช่น “บอกฉันว่าวัตถุในตำแหน่ง 85273”) สามารถขอหลักฐานการพิสูจน์ได้และเมื่อได้รับหลักฐานยืนยันว่าถูกต้อง เป็นจริง ที่ตำแหน่ง 85273 ในฐานข้อมูลที่มีรูทเฉพาะนั้น จะช่วยให้กลไกสำหรับการตรวจสอบความถูกต้อง เล็ก จำนวนข้อมูลเช่นแฮชที่จะขยายเพื่อตรวจสอบความถูกต้อง ใหญ่ ฐานข้อมูลขนาดที่อาจไม่มีขอบเขต
Merkle Proofs ใน Bitcoin
แอปพลิเคชั่นดั้งเดิมของ Merkle Proofs อยู่ใน Bitcoin ตามที่อธิบายและสร้างโดย Satoshi Nakamoto ในปี 2009 bitcoin blockchain ใช้การพิสูจน์ Merkle เพื่อจัดเก็บธุรกรรมในทุกบล็อก:
ประโยชน์ที่ให้ไว้คือแนวคิดที่ Satoshi อธิบายว่า “การตรวจสอบการชำระเงินแบบง่าย”: แทนที่จะดาวน์โหลด ทั้งหมด ธุรกรรมและทุกบล็อก “ไคลเอนต์แสง” สามารถดาวน์โหลดห่วงโซ่ของ บล็อกส่วนหัวข้อมูล 80 ไบต์สำหรับแต่ละบล็อกที่มีเพียงห้าสิ่งเท่านั้น:
- แฮชของส่วนหัวก่อนหน้านี้
- การประทับเวลา
- ค่าความยากในการขุด
- หลักฐานการทำงานที่ไม่ได้รับ
- แฮชรูทสำหรับต้นไม้ Merkle ที่มีธุรกรรมสำหรับบล็อกนั้น
หากไคลเอนต์แสงต้องการกำหนดสถานะของการทำธุรกรรมก็สามารถขอหลักฐานการพิสูจน์ได้ว่าการทำธุรกรรมโดยเฉพาะนั้นอยู่ในต้น Merkle ที่มีรากอยู่ในส่วนหัวบล็อกสำหรับห่วงโซ่หลัก
สิ่งนี้ทำให้เราค่อนข้างไกล แต่ลูกค้าที่มีแสงสไตล์ Bitcoin มีข้อ จำกัด ข้อ จำกัด อย่างหนึ่งคือในขณะที่พวกเขาสามารถพิสูจน์การรวมการทำธุรกรรมพวกเขาไม่สามารถพิสูจน์อะไรเกี่ยวกับสถานะปัจจุบัน (เช่นการถือครองสินทรัพย์ดิจิตอลการลงทะเบียนชื่อสถานะของสัญญาทางการเงิน ฯลฯ ) ตอนนี้คุณมี bitcoins กี่ตัว? ไคลเอนต์ Bitcoin Gentle สามารถใช้โปรโตคอลที่เกี่ยวข้องกับการสืบค้นหลายโหนดและเชื่อมั่นว่าอย่างน้อยหนึ่งในนั้นจะแจ้งให้คุณทราบถึงการใช้จ่ายธุรกรรมใด ๆ จากที่อยู่ของคุณและสิ่งนี้จะช่วยให้คุณได้ไกลสำหรับกรณีการใช้งานนั้น แต่สำหรับแอปพลิเคชันที่ซับซ้อนกว่านี้ ลักษณะที่แม่นยำของผลกระทบของการทำธุรกรรมสามารถขึ้นอยู่กับผลกระทบของการทำธุรกรรมก่อนหน้าหลายครั้งซึ่งขึ้นอยู่กับการทำธุรกรรมก่อนหน้านี้และท้ายที่สุดคุณจะต้องตรวจสอบสิทธิ์การทำธุรกรรมทุกครั้งในห่วงโซ่ทั้งหมด เพื่อให้ได้สิ่งนี้ Ethereum ใช้แนวคิด Merkle Tree อีกหนึ่งก้าว
การพิสูจน์ Merkle ใน Ethereum
ส่วนหัวบล็อกทุกตัวใน Ethereum ไม่ได้มีเพียงต้น Merkle หนึ่งต้นเท่านั้น แต่ สาม ต้นไม้สำหรับวัตถุสามชนิด:
- การทำธุรกรรม
- ใบเสร็จรับเงิน (โดยพื้นฐานแล้วชิ้นส่วนของข้อมูลที่แสดง ผล ของแต่ละธุรกรรม)
- สถานะ
สิ่งนี้ช่วยให้โปรโตคอลไคลเอนต์แสงที่ทันสมัยสูงซึ่งช่วยให้ลูกค้าเบาสามารถสร้างและรับคำตอบที่ตรวจสอบได้อย่างง่ายดายสำหรับการสืบค้นหลายประเภท:
- ธุรกรรมนี้รวมอยู่ในบล็อกเฉพาะหรือไม่?
- บอกฉันทุกกรณีของเหตุการณ์ Sort X (เช่นสัญญาระดมทุนไปถึงเป้าหมาย) ที่ปล่อยออกมาจากที่อยู่นี้ในช่วง 30 วันที่ผ่านมา
- ยอดเงินปัจจุบันของบัญชีของฉันคืออะไร?
- บัญชีนี้มีอยู่หรือไม่?
- แกล้งทำธุรกรรมนี้ในสัญญานี้ ผลลัพธ์จะเป็นอย่างไร?
ครั้งแรกได้รับการจัดการโดยต้นไม้ธุรกรรม ที่สามและสี่ได้รับการจัดการโดยต้นไม้ของรัฐและที่สองโดยต้นไม้ใบเสร็จรับเงิน สี่คนแรกค่อนข้างตรงไปตรงมาในการคำนวณ; เซิร์ฟเวอร์เพียงแค่ค้นหาวัตถุดึงสาขา merkle (รายการแฮชขึ้นมาจากวัตถุไปยังรูทต้นไม้) และตอบกลับไปยังไคลเอนต์แสงด้วยสาขา
ที่ห้าได้รับการจัดการโดยต้นไม้ของรัฐ แต่วิธีที่คำนวณนั้นซับซ้อนกว่า ที่นี่เราต้องสร้างสิ่งที่เรียกได้ว่า หลักฐานการเปลี่ยนแปลงของ Merkle State– โดยพื้นฐานแล้วมันเป็นข้อพิสูจน์ที่ทำให้การเรียกร้อง “ถ้าคุณเรียกใช้ธุรกรรม T ในสถานะที่มีราก Sผลลัพธ์จะเป็นสถานะที่มีราก S ‘ด้วยบันทึก l และเอาท์พุท โอ“(” เอาท์พุท “มีอยู่เป็นแนวคิดใน Ethereum เพราะการทำธุรกรรมทุกครั้งเป็นการเรียกใช้ฟังก์ชั่น; มันไม่จำเป็นในทางทฤษฎี)
ในการคำนวณการพิสูจน์เซิร์ฟเวอร์จะสร้างบล็อกปลอมตั้งค่าสถานะเป็น S และแกล้งทำเป็นไคลเอ็นต์เบาในขณะที่ใช้การทำธุรกรรม นั่นคือหากกระบวนการใช้การทำธุรกรรมกำหนดให้ลูกค้ากำหนดยอดคงเหลือของบัญชีไคลเอนต์แสงจะทำแบบสอบถามยอดคงเหลือ หากไคลเอนต์แสงต้องการตรวจสอบรายการใดรายการหนึ่งในการจัดเก็บสัญญาเฉพาะไคลเอนต์แสงจะทำแบบสอบถามสำหรับสิ่งนั้นและอื่น ๆ เซิร์ฟเวอร์ “ตอบกลับ” ไปยังการสืบค้นทั้งหมดของตัวเองอย่างถูกต้อง แต่ติดตามข้อมูลทั้งหมดที่ส่งกลับมา จากนั้นเซิร์ฟเวอร์จะส่งข้อมูลรวมจากคำขอทั้งหมดเหล่านี้เป็นหลักฐาน จากนั้นลูกค้าจะดำเนินการตามขั้นตอนเดียวกัน แต่ การใช้หลักฐานที่ให้ไว้เป็นฐานข้อมูล– หากผลลัพธ์นั้นเหมือนกับที่เซิร์ฟเวอร์อ้างสิทธิ์ลูกค้าจะยอมรับการพิสูจน์
ต้นแพทริเซีย
มันถูกกล่าวถึงข้างต้นว่าต้น Merkle ที่ง่ายที่สุดคือต้นไม้ Merkle แบบไบนารี อย่างไรก็ตามต้นไม้ที่ใช้ใน Ethereum นั้นซับซ้อนกว่า – นี่คือ “Merkle Patricia Tree” ที่คุณได้ยินในเอกสารของเรา บทความนี้จะไม่เข้าไปในข้อมูลจำเพาะโดยละเอียด ที่ทำได้ดีที่สุดโดย บทความนี้ และ อันนี้แม้ว่าฉันจะหารือเกี่ยวกับการใช้เหตุผลพื้นฐาน
ต้นไม้ Binary Merkle เป็นโครงสร้างข้อมูลที่ดีมากสำหรับการตรวจสอบข้อมูลที่อยู่ในรูปแบบ “รายการ” โดยพื้นฐานแล้วชุดของชิ้นหนึ่งหลังจากอื่น ๆ สำหรับต้นไม้ธุรกรรมพวกเขาก็ดีเพราะไม่สำคัญว่าจะต้องใช้เวลาเท่าไหร่ แก้ไข ต้นไม้เมื่อมันถูกสร้างขึ้นเมื่อต้นไม้ถูกสร้างขึ้นหนึ่งครั้งและจากนั้นก็แช่แข็งเป็นของแข็งตลอดไป
อย่างไรก็ตามสำหรับต้นไม้ของรัฐสถานการณ์มีความซับซ้อนมากขึ้น รัฐใน Ethereum นั้นประกอบด้วยแผนที่คีย์-ค่าซึ่งคีย์เป็นที่อยู่และค่าคือการประกาศบัญชีแสดงรายการยอดคงเหลือ, nonce, รหัสและที่เก็บข้อมูลสำหรับแต่ละบัญชี (ที่ที่เก็บข้อมูลเป็นต้นไม้) ตัวอย่างเช่นรัฐ Morden Testnet Genesis มีลักษณะดังนี้:
{
"0000000000000000000000000000000000000001": {
"stability": "1"
},
"0000000000000000000000000000000000000002": {
"stability": "1"
},
"0000000000000000000000000000000000000003": {
"stability": "1"
},
"0000000000000000000000000000000000000004": {
"stability": "1"
},
"102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
"stability": "1606938044258990275541962092341162602522202993782792835301376"
}
}
ซึ่งแตกต่างจากประวัติการทำธุรกรรมรัฐจำเป็นต้องได้รับการปรับปรุงบ่อยครั้ง: ยอดคงเหลือและการไม่ใช้บัญชีมักจะเปลี่ยนไปและสิ่งที่มากกว่านั้นบัญชีใหม่จะถูกแทรกบ่อยครั้งและคีย์ในการจัดเก็บจะถูกแทรกและลบบ่อยครั้ง สิ่งที่ต้องการคือโครงสร้างข้อมูลที่เราสามารถคำนวณรูทต้นไม้ใหม่ได้อย่างรวดเร็วหลังจากการแทรกอัปเดตแก้ไขหรือลบการดำเนินการโดยไม่ต้องคำนวณต้นไม้ทั้งหมดอีกครั้ง นอกจากนี้ยังมีคุณสมบัติทุติยภูมิที่ต้องการอย่างมากสองประการ:
- ความลึกของต้นไม้ถูกล้อมรอบแม้กระทั่งผู้โจมตีที่จงใจสร้างธุรกรรมเพื่อทำให้ต้นไม้ลึกที่สุดเท่าที่จะทำได้ มิฉะนั้นผู้โจมตีสามารถทำการปฏิเสธการโจมตีการบริการโดยการจัดการต้นไม้ให้ลึกมากจนการอัปเดตแต่ละครั้งช้ามาก
- รูทของต้นไม้ขึ้นอยู่กับข้อมูลเท่านั้นไม่ใช่ตามลำดับการอัปเดต การอัปเดตในลำดับที่แตกต่างกันและแม้แต่การคำนวณซ้ำต้นไม้จากศูนย์ไม่ควรเปลี่ยนรูท
ที่ ต้นแพทริเซียในแง่ง่ายอาจเป็นสิ่งที่ใกล้เคียงที่สุดที่เราสามารถมาเพื่อบรรลุคุณสมบัติทั้งหมดเหล่านี้พร้อมกัน คำอธิบายที่ง่ายที่สุดสำหรับวิธีการทำงานคือคีย์ภายใต้การจัดเก็บค่าจะถูกเข้ารหัสลงใน “เส้นทาง” ที่คุณต้องถอดต้นไม้ แต่ละโหนดมีลูก 16 คนดังนั้นเส้นทางจึงถูกกำหนดโดยการเข้ารหัส Hex: ตัวอย่างเช่นคีย์ สุนัข hex encoded คือ 6 4 6 15 6 7ดังนั้นคุณจะเริ่มต้นด้วยรากลงไปที่ลูกคนที่ 6 จากนั้นสี่และอื่น ๆ จนกว่าคุณจะถึงจุดสิ้นสุด ในทางปฏิบัติมีการเพิ่มประสิทธิภาพพิเศษสองสามอย่างที่เราสามารถทำให้กระบวนการมีประสิทธิภาพมากขึ้นเมื่อต้นไม้กระจัดกระจาย แต่นั่นคือหลักการพื้นฐาน ทั้งสอง บทความ กล่าวถึง ข้างบน อธิบายคุณสมบัติทั้งหมดในรายละเอียดมากขึ้น
