LNPBP-81: Tagged Merkle trees

LNPBP: 0081
Vertical: Cryptographic primitives
Title: Tagged merkle trees for client-side-validation
Author: Dr Maxim Orlovsky  <[e-mail]>,
        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

Abstract

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