LNPBP-81: Tagged Merkle trees
LNPBP: 0081
Vertical: Cryptographic primitives
Title: Tagged merkle trees for client-side-validation
Author: Dr Maxim Orlovsky <[email protected]>,
Peter Todd
Comments-URI: https://github.com/LNP-BP/lnpbps/issues/<____>
Status: Draft
Type: Standards Track
Created: 2021-05-11
License: CC0-1.0Abstract
Background
Motivation
Problems with modern merkle trees:
Depth extension attack: no commitment to the tree depth
Design
Based on bitcoin merklization with following modifications:
Tagged hashing for source data
Tagged hashing of each tree object
Commitments to depth, width and height of the tree
Custom placeholders for empty objects
Restricting tree source to 2^16 elements (height is always <=16)
Specification
Merkle node is represented by a single SHA256 hash over the following data, serialized as a byte stream without any separators:
branch type (byte)
tag (128-bit number)
depth (byte)
width (4 bytes, little-endian)
child node 1 (32 bytes)
child node 2 (32 bytes)
If one or both of the child nodes are absent, a constant consisting of 16 0xFF
bytes is used.
The root is produced via CommitmentId procedure
Compatibility
Rationale
Reference implementation
Acknowledgements
References
Copyright
This document is licensed under the Creative Commons CC0 1.0 Universal license.
Test vectors
Last updated