# 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://standards.lnp-bp.org/commitment-schemes/lnpbp-0081.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.