note: The Right Way to Hash a Merkle Tree by Potuz | Devcon Bogotá
video note
video นี้จะแบ่งเป็น
- อธิบายการทำงานของ sha 256 ส่วนนี้เราจะ skip กัน
- Merkle tree implementation ใน Ethereum
- Merkle tree implementation ใน lightnode
- การทำให้การ hash Merkle tree ใน Ethereum เร็วขึ้น
2. Merkle tree implementation ใน Ethereum
ตอนนี้การ hash Merkle tree ใน Ethereum consensus layer
จะเป็นการ hash ทีละ 2 node เพื่อหา parent node ไปเรื่อยๆ
3.Merkle tree implementation ใน lightnode
lightnode จะทำการสร้าง sub tree แล้วค่อยมาประกอบกัน
โดยแต่ละ subtree จะสร้างแบบ parallel แยกกันไปบนแต่ละ thread
4. การทำให้การ hash Merkle tree ใน Ethereum เร็วขึ้น
เราสามารถใช้ 2 เทคนิคนี้ได้
- การ hardcode word ที่ต้อง hash ไปเลย ไม่ต้อง pad
ก่อนอื่นต้องเกริ่นก่อนว่า ในการทำงานของ sha256 จะมีขั้นตอนนึง ที่เป็นการ pad ตัว word ให้ครบ 64 byte เนื่องจาก sha256 ออกแบบมาให้ hash input ขนาดยาวเท่าไหร่ก็ได้
แต่ประเด็นคือ leaf node ของ Merkle tree ทุกอันจะยาว 64 byte เสมออยู่แล้ว เพราะเป็นค่าจากการ hash
นี่ทำให้เราสามารถข้าม step การ pad ไป hardcode ได้เลย
2. การใช้ vectorization มาช่วยให้สามารถ hash หลายๆครั้งได้ในทีเดียว
cpu หลายๆเจ้าจะมี feature ในการนำค่าบน register มาทำการ hash พร้อมๆกันได้
ดังนั้น ถ้าเราสามารถป้อนค่าเข้าไปใน register ในทีเดียว แล้ว hash ค่าเหล่านั้นพร้อมกัน
จะเร็วกว่าการที่เราวนใช้ register ในการ hash แต่ละค่าแยกกัน
โดยทางทีม speaker ได้มีการ implement code เอาไว้แล้ว
