LNPBP: 0081
Vertical: Cryptographic primitives
Title: Tagged merkle trees for client-side-validation
Author: Dr Maxim Orlovsky <orlovsky@protonmail.ch>,
Peter Todd
Comments-URI: https://github.com/LNP-BP/lnpbps/issues/<____>
Status: Draft
Type: Standards Track
Created: 2021-05-11
License: CC0-1.0
- Abstract
- Background
- Motivation
- Design
- Specification
- Compatibility
- Rationale
- Reference implementation
- Acknowledgements
- References
- Copyright
- Test vectors
Problems with modern merkle trees:
- Depth extension attack: no commitment to the tree depth
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)
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
This document is licensed under the Creative Commons CC0 1.0 Universal license.