> For the complete documentation index, see [llms.txt](https://standards.lnp-bp.org/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://standards.lnp-bp.org/commitment-schemes/lnpbp-0081.md).

# LNPBP-81: Tagged Merkle trees

```
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](#abstract)
* [Background](#background)
* [Motivation](#motivation)
* [Design](#design)
* [Specification](#specification)
* [Compatibility](#compatibility)
* [Rationale](#rationale)
* [Reference implementation](#reference-implementation)
* [Acknowledgements](#acknowledgements)
* [References](#references)
* [Copyright](#copyright)
* [Test vectors](#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