tip: 4
title: Milestone Merkle Validation
description: Add Merkle tree hash to milestone for local ledger state verification
author: Wolfgang Welz (@Wollac) 
discussions-to: https://github.com/iotaledger/tips/pull/12, https://github.com/iotaledger/tips/pull/31
status: Active
type: Standards
layer: Core
created: 2020-05-04

Summary

In the IOTA protocol, nodes use the milestones issued by the Coordinator to reach a consensus on which transactions are confirmed. This RFC adds extra information to each milestone in the form of a Merkle tree hash, which allows nodes to explicitly validate their local view of the ledger state against the Coordinator's. This mechanism further enables a simple cryptographic proof of inclusion for transactions confirmed by the particular milestone.

Motivation

With the changes proposed in the IOTA protocol TIP-2, milestones are allowed to reference conflicting transactions. These conflicts are then resolved by traversing the newly confirmed transactions in a global, deterministic order and applying the corresponding ledger state changes in that order. Conflicts or invalid transactions are ignored, but stay in the Tangle. This approach has considerable advantages in terms of network security (e.g. protection against conflict spamming attacks) and network performance. However, a milestone no longer represents the inclusion state of all its referenced transactions, but only marks the order in which transactions are checked against the ledger state and then, if not violating, applied. This has two significant drawbacks:

• Milestone validation: In the IOTA protocol, each node always compares the milestones issued by the Coordinator against its current ledger state. Discrepancies are reported and force an immediate halt of the node software. However, in the white flag proposal this detection is no longer possible as any milestone can lead to a valid ledger state by ignoring the corresponding violating ledger changes.
• Proof of inclusion: In the pre-white-flag protocol, the inclusion of transaction t in the Tangle, and thus, the ledger, can be shown by providing an audit path of referencing transactions from t to its confirming milestone. In the white flag proposal this is no longer possible, as such an audit path does not provide any information on whether the transaction has been included or ignored.

Note that the white flag proposal only changes the behavior of conflicting transactions. Messages without a transaction payload can never conflict and are thus always included in Tangle when they are first referenced by a milestone. As such, these messages do not need to be considered by the RFC and their processing and inclusion proof remain unchanged.

Where previously the structure of the Tangle alone was sufficient to address those issues, this RFC proposes to add the Merkle tree hash of all the valid (i.e. not ignored) newly confirmed transactions to the signed part of a milestone. This way, each IOTA node can check that the hash matches its local ledger state changes or provide a Merkle audit path for that milestone to prove the inclusion of a particular transaction.

Detailed design

Creating a Milestone

• Perform tip selection to choose the parents referenced by the milestone.
• Determine the topological order according to TIP-2 of the referenced messages that are not yet confirmed by a previous milestone.
• Construct the list D consisting of the message IDs of all the not-ignored state-mutating transaction payloads in that particular order. A UTXO transaction is considered state-mutating, if it creates a new output.
• Compute the 32-byte Merkle tree hash H = MTH(D).
• Prepare the milestone payload as described in TIP-8, where the field Inclusion Merkle Root is set to H.

Milestone validation

• Verify the signature of the milestone m.
• Construct the ordered list D of the message IDs of all the not-ignored state-mutating transaction payloads m confirms.
• Compute H = MTH(D).
• Verify that the field Inclusion Merkle Root in m matches H.

Proof of inclusion

• Identify the confirming milestone m of the input transaction t.
• Determine the ordered list of the not-ignored messages m confirms.
• Compute the Merkle audit path of t with respect to the Merkle tree for this ordered list.
• Provide the audit path as well as m as proof of inclusion for t.

Cryptographic components

Merkle hash trees

This RFC uses a binary Merkle hash tree for efficient auditing. In general, any cryptographic hashing algorithm can be used for this. However, we propose to use BLAKE2b-256, as it provides a faster and more secure alternative to the widely used SHA-256. In the following we define the Merkle tree hash (MTH) function that returns the hash of the root node of a Merkle tree:

• The input is a list of binary data entries; these entries will be hashed to form the leaves of the tree.
• The output is a single 32-byte hash.

Given an ordered list of n input strings D_n = {d₁, d₂, ..., d_n}, the Merkle tree hash of D is defined as follows:

• If D is an empty list, MTH(D) is the hash of an empty string:
  MTH({}) = BLAKE2().
• If D has the length 1, the hash (also known as a leaf hash) is:
  MTH({d₁}) = BLAKE2( 0x00 || d₁ ).
• Otherwise, for D_n with n > 1:
  • Let k be the largest power of two less than n, i.e. k < n ≤ 2k.
  • The Merkle tree hash can be defined recursively:
    MTH(D_n) = BLAKE2( 0x01 || MTH({d₁, ..., d_k}) || MTH({d_k+1, ..., d_n}) ).

Note that the hash calculations for leaves and nodes differ. This is required to provide second preimage resistance: Without such a prefix, for a given input D an attacker could replace two (or more) leaves with their corresponding aggregated node hash without changing the final value of MTH(D). This violates the fundamental assumption that, given MTH(D), it should be practically impossible to find a different input D' leading to the same value. Adding a simple prefix mitigates this issue, since now leaf and node hashes are computed differently and can no longer be interchanged.

Note that we do not require the length of the input to be a power of two. However, its shape is still uniquely determined by the number of leaves.

Merkle audit paths

A Merkle audit path for a leaf in a Merkle hash tree is the shortest list of additional nodes in a Merkle tree required to compute the Merkle tree hash for that tree. At each step towards the root, a node from the audit path is combined with a node computed so far. If the root computed from the audit path matches the Merkle tree hash, then the audit path is proof that the leaf exists in the tree.

Example

Merkle tree with 7 leaves:

• input D:
  1. 52fdfc072182654f163f5f0f9a621d729566c74d10037c4d7bbb0407d1e2c649
  2. 81855ad8681d0d86d1e91e00167939cb6694d2c422acd208a0072939487f6999
  3. eb9d18a44784045d87f3c67cf22746e995af5a25367951baa2ff6cd471c483f1
  4. 5fb90badb37c5821b6d95526a41a9504680b4e7c8b763a1b1d49d4955c848621
  5. 6325253fec738dd7a9e28bf921119c160f0702448615bbda08313f6a8eb668d2
  6. 0bf5059875921e668a5bdf2c7fc4844592d2572bcd0668d2d6c52f5054e2d083
  7. 6bf84c7174cb7476364cc3dbd968b0f7172ed85794bb358b0c3b525da1786f9f
• Merkle tree hash H = MTH(D) (32-byte): bf67ce7ba23e8c0951b5abaec4f5524360d2c26d971ff226d3359fa70cdb0beb

root: bf67ce7ba23e8c0951b5abaec4f5524360d2c26d971ff226d3359fa70cdb0beb
 ├─ node: 03bcbb3cf4314eab2f5ae68c767ff0a5fec4573c865728231f71d596fd867b56
 │  ├─ node: ae4505f4cfae93586e23958ca88d35d2f34d43def49786b6d0d4224b819f4cda
 │  │  │  ┌ msg id: 52fdfc072182654f163f5f0f9a621d729566c74d10037c4d7bbb0407d1e2c649
 │  │  ├──┴ leaf: 3d1399c64ff0ae6a074afa4cd2ce4eab8d5c499c1da6afdd1d84b7447cc00544
 │  │  │  ┌ msg id: 81855ad8681d0d86d1e91e00167939cb6694d2c422acd208a0072939487f6999
 │  │  └──┴ leaf: 83b0b255014e9a3656f0004a3f17943a20b715ef9c3e7cb85a6b2abac15e00d0
 │  └─ node: 54d51291aca22ce5b04cd3e6584fa3026ebe86ef86f0a6dfb47ab843801d4b38
 │     │  ┌ msg id: eb9d18a44784045d87f3c67cf22746e995af5a25367951baa2ff6cd471c483f1
 │     ├──┴ leaf: ad4bc0a34b27f37810f2ff3a8177ecc98402f8f59a06270f9d285fdf764e45fe
 │     │  ┌ msg id: 5fb90badb37c5821b6d95526a41a9504680b4e7c8b763a1b1d49d4955c848621
 │     └──┴ leaf: ffb3a7c6bea8f9fdcfb26f4701ad6e912a6076e1a40663607dbe110ebfc9a571
 └─ node: ce22d5bc728023e7ab6a9eb8f58baf62b9565fc8baeef4b377daa6709dbe598c
    ├─ node: e14c8af1258005cd0dbed88f0c5885c6988f319bb8f24272a7495592b873c169
    │  │  ┌ msg id: 6325253fec738dd7a9e28bf921119c160f0702448615bbda08313f6a8eb668d2
    │  ├──┴ leaf: 1c062628a7a147cc6a4defa655ce6c4ae5b838b4b4cd81b12e8924b5b4b5cca6
    │  │  ┌ msg id: 0bf5059875921e668a5bdf2c7fc4844592d2572bcd0668d2d6c52f5054e2d083
    │  └──┴ leaf: 2ef4e2ad06b8c8ae1fd4b28b5ed166829533fbfff1f6c14218358537da277fa3
    │  ┌ msg id: 6bf84c7174cb7476364cc3dbd968b0f7172ed85794bb358b0c3b525da1786f9f
    └──┴ leaf: 7ec774ebc33ed4ca298e8a1cf1f569e36c6784467d63b055efd7612abe2858a4

Drawbacks

• The computation of the Merkle tree hash of D_n requires 2n-1 evaluations of the underlying hashing algorithm. This makes the milestone creation and validation computationally slightly more expensive.

Rationale and alternatives

It is a crucial security feature of the IOTA network that nodes are able to validate the issued milestones. As a result, if the Coordinator were to ever send an invalid milestone, such as one that references counterfeit transactions, the rest of the nodes would not accept it. In a pure implementation of TIP-2 this feature is lost and must be provided by external mechanisms. A Merkle tree hash provides an efficient, secure and well-established method to compress the information about the confirmed transactions in such a way, that they fit in the milestone transaction.

In this context, it could also be possible to use an unsecured checksum (such as CRCs) of the message IDs instead of a Merkle tree hash. However, the small benefit of faster computation times does no justify the potential security risks and attack vectors.

Reference implementation

Example Go implementation in wollac/iota-crypto-demo:

• Merkle tree computation of message IDs: pkg/merkle/merkle.go
• Example: examples/merkle/pt2

Copyright

Copyright and related rights waived via CC0.