SIMD-0064

TL;DR

Here we propose a mechanism for proving transaction inclusion into a block in the Solana protocol. This is a pre-requisite for several use-cases that would like to build upon a [Simple Payment Verification](https://en.wikipedia.org/wiki/Bitcoin_network#Payment_verification) like construction. We employ the well-known [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree) data structure to compress a block's transactions and their results into a compact identifier, with which inclusion proofs can be generated

Summary

Here we propose a mechanism for proving transaction inclusion into a block in the Solana protocol. This is a pre-requisite for several use-cases that would like to build upon a [Simple Payment Verification](https://en.wikipedia.org/wiki/Bitcoin_network#Payment_verification) like construction. We employ the well-known [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree) data structure to compress a block's transactions and their results into a compact identifier, with which inclusion proofs can be generated

Motivation

One of the fundamental requirements of a Solana client is access to the status of a confirmed transaction. This is due to the fact that transactions are not guaranteed to be confirmed once submitted, and may fail once executed. Virtually all Solana clients therefore use a subscription-based or polling mechanism to inquire whether a transaction was successfully executed. The only standard mechanism to retrieve transaction statuses remotely is via the RPC protocol. However, the RPC protocol only serves replay information of the RPC service itself. It does not provide information whether the validator network at large has derived the same information. This may allow an RPC provider to send incorrect information to a client, such as marking a failed transaction as successful. Solana validator nodes replay all transactions and thus have access to transaction status information. To improve security, clients should verify that transaction status information received via RPC matches the validator network at large. This proposal introduces a new “transaction receipt” data structure, which contains a subset of the information available via RPC. The derivation and serialization functions for transaction receipts are defined to be deterministic to prevent malleability. To succinctly detect transaction receipt mismatches, this proposal further introduces a commitment scheme based on a binary hash tree that is constructed once per slot. ### Design Goals 1. Transaction Receipts must be deterministic. Given a transaction T and ledger history leading up to it, serializing the receipt generated for T should result in the same byte vector for all nodes in the network. *Rationale:* Determinism is required for cluster-wide consensus. 2. Transaction Receipts must not be required during block construction. *Rationale:* Future upgrades propose tolerating asynchronous replay during block construction. In other words, validators should be allowed to produce and distribute a block before replaying said block. It is impossible to introduce such a tolerance if transaction receipts are mandatory components of blocks.

Key Changes

• Transaction Receipt Version (currently v1, other values reserved for future upgrades)
• Message Hash identifying the transaction it refers to
• The Execution Status, a boolean identifying whether the transaction was successfully executed or failed without extrinsic state changes.
• When inserted as a leaf node into the tree defined below, this structure requires hashing two SHA-256 blocks.
• The version integer can safely be shortened to u8 in a future upgrade (Due to little-endian encoding). Using a u64 allows for this flexibilty. Futhermore, we could also fit a domain hash separator in the version bits to prevent re-interpreting the leaf nodes as a different structure in the future as a good practice.
• In future versions, hashes for a subset of fields exhibiting a small set of possible combinations could be aligned to the hash function block size and precomputed. (Such as version and status). For now, this micro-optimization would yield no performance improvements as mentioned above.
• The Merkle tree construction used is an extension of the tree construction used in PoH. (With different input data)
• The tree derivation function is surjective: Each vector of transaction receipts results in a unique tree, thereby making it deterministic and immalleable.
• The order of the leaf nodes matches the block's transaction order. (As it unambiguously appears in the PoH construction)
• Succinct inclusion proofs are constructed by providing a hash path from a leaf node to the root node. The inclusion proof format is defined separately from this SIMD.
• Input: Vector of TransactionReceiptData objects in PoH order
• Pre-condition: Each element's message_hash is unique
• Output: Transaction receipt tree root (32 byte hash)
• Definitions:
• The intermediate_root is the 32 byte root of the binary merkle tree as externally specified. Specification: Binary Merkle Tree
• The root_prefix is the byte 0x80
• The function u64_le_encode encodes a 64-bit integer in little-endian byte order.
• The leaf_count is the number of TransactionReceiptData objects to serve as leaf nodes in the tree.
• sentinel_root is a byte array of zeros with length 32
• If the leaf count is zero, the output is sha256(root_prefix || sentinel_root || u64_le_encode(0)).

Impact

The generation of a Transaction Receipt Tree is a prerequisite for providing proof that a transaction was included in a block. Itself a step toward providing proof that a transaction was executed and accepted under consensus by a Solana cluster. A major improvement in trust-minimization for the ecosystem, opening the door to new use-cases and reducing infrastructure requirements for some of today's.

Backwards Compatibility

This change does not impact the Solana ledger, and thus introduces no backwards compatibility concerns.

Security Considerations

The transaction receipt tree is expected to be used for transaction inclusion proofs. For example, an inclusion proof might attest that a token transfer has succeeded. Such proofs may then be relied on to provide financial services. It is thus important to ensure that proofs cannot be forged. Common forgery attacks against Merkle trees include: - Various forms of pre-image attacks against the underlying hash functions. As of 2023-Oct, no practical collision attacks against SHA-256 are known. - Malleability and type confusion in the hash tree construction. These are prevented via two mechanisms: 1. Hash domain separation via one byte prefixes (for leaf nodes, branch nodes, and the final hash respectively) 2. A node count suffix to prevent malleable leaf count attacks Further conerns include: - Implementation bugs: To reduce the risk of such, this proposal deliberately keeps the amount of newly introduced logic low. - Performance-related attacks (DoS): The computational complexity of transaction receipt tree construction is `O(n+log n)` where `n` is the number of transactions. There are no other user controllable components such as variable-length inputs.