ZIP: 244 Title: Transaction Identifier Non-Malleability Owners: Kris Nuttycombe <[email protected]> Daira Hopwood <[email protected]> Status: Proposed Category: Consensus Created: 2021-01-06 License: MIT Discussions-To: <https://github.com/zcash/zips/issues/411>
The key words "MUST" and "MUST NOT" in this document are to be interpreted as described in RFC 2119. [1]
The terms "consensus branch", "epoch", and "network upgrade" in this document are to be interpreted as described in ZIP 200. [2]
The term "field encoding" refers to the binary serialized form of a Zcash transaction field, as specified in section 7.1 of the Zcash protocol specification [7].
This proposal defines a new transaction digest algorithm for the NU5 network upgrade onward, in order to introduce non-malleable transaction identifiers that commit to all transaction data except for attestations to transaction validity.
This proposal also defines a new transaction digest algorithm for signature validation, which shares all available structure produced during the construction of transaction identifiers, in order to minimize redundant data hashing in validation.
This proposal also defines a new name and semantics for the hashLightClientRoot field of the
block header, to enable additional commitments to be represented in this hash and to
provide a mechanism for future extensibility of the set of commitments represented.
In all cases, but particularly in order to support the use of transactions in higher-level protocols, any modification of the transaction that has not been explicitly permitted (such as via anyone-can-spend inputs) should invalidate attestations to spend authority or to the included outputs. Following the activation of this proposed change, transaction identifiers will be stable irrespective of any possible malleation of "witness data" such as proofs and transaction signatures.
In addition, by specifying a transaction identifier and signature algorithm that is decoupled from the serialized format of the transaction as a whole, this change makes it so that the wire format of transactions is no longer consensus-critical.
- Continue to support existing functionality of the protocol (multisig, signing modes for transparent inputs).
- Allow the use of transaction ids, and pairs of the form (transaction id, output index) as stable identifiers.
- A sender must be able to recognize their own transaction, even given allowed forms of malleability such as recomputation of transaction signatures.
- In the case of transparent inputs, it should be possible to create a transaction (B) that spends the outputs from a previous transaction (A) even before (A) has been mined. This should also be possible in the case that the creator of (B) does not wait for confirmations of (A). That is, (B) should remain valid so long as any variant of (A) is eventually mined.
- It should not be possible for an attacker to malleate a transaction in a fashion that would result in the transaction being interpreted as a double-spend.
- It should be possible in the future to upgrade the protocol in such a fashion that only non-malleable transactions are accepted.
- It should be possible to use the transaction id unmodified as the value that is used to produce a signature hash in the case that the transaction contains no transparent inputs.
In order to support backwards-compatibility with parts of the ecosystem that have not yet upgraded to the non-malleable transaction format, it is not an initial requirement that all transactions be non-malleable.
It is not required that legacy (Sapling V4 and earlier) transaction formats support construction of non-malleable transaction identifiers, even though they may continue to be accepted by the network after the NU5 upgrade.
All digests are personalized BLAKE2b-256 hashes. In cases where no elements are available for hashing (for example, if there are no transparent inputs) the resulting hash will be over just the personalization string, providing domain separation even for empty data fields.
A new transaction digest algorithm is defined that constructs the identifier for a transaction from a tree of hashes. Each branch of the tree of hashes will correspond to a specific subset of transaction data. The overall structure of the hash is as follows; each name referenced here will be described in detail below:
txid_digest
├── header_digest
├── transparent_digest
│ ├── prevouts_digest
│ ├── sequence_digest
│ └── outputs_digest
└── sapling_digest
├── sapling_spends_digest
│ ├── sapling_spends_compact_digest
│ └── sapling_spends_noncompact_digest
├── sapling_outputs_digest
│ ├── sapling_outputs_compact_digest
│ ├── sapling_outputs_memos_digest
│ └── sapling_outputs_noncompact_digest
└── valueBalance
Each node written as snake_case in this tree is a BLAKE2b-256 hash of its
children, initialized with a personalization string specific to that branch
of the tree. Nodes that are not themselves digests are written in camelCase.
In the specification below, nodes of the tree are presented in depth-first order.
A BLAKE2b-256 hash of the following values
T.1: header_digest (32-byte hash output) T.2: transparent_digest (32-byte hash output) T.3: sapling_digest (32-byte hash output)
The personalization field of this hash is set to:
"ZcashTxHash_" || CONSENSUS_BRANCH_ID
ZcashTxHash_ has 1 underscore character.
As in ZIP 143 [5], CONSENSUS_BRANCH_ID is the 4-byte little-endian encoding of the consensus branch ID for the epoch of the block containing the transaction. Domain separation of the transaction id hash across parallel consensus branches provides replay protection: transactions targeted for one consensus branch will not have the same transaction identifier on other consensus branches.
This signature hash personalization prefix has been changed to reflect the new role of
this hash (relative to ZcashSigHash as specified in ZIP 143) as a transaction
identifier rather than a commitment that is exclusively used for signature purposes.
The previous computation of the transaction identifier was a SHA256d hash of the
serialized transaction contents, and was not personalized.
A BLAKE2b-256 hash of the following values
T.1a: version (4-byte little-endian version identifier including overwinter flag) T.1b: version_group_id (4-byte little-endian version group identifier) T.1c: consensus_branch_id (4-byte little-endian consensus branch id) T.1d: lock_time (4-byte little-endian nLockTime value) T.1e: expiry_height (4-byte little-endian block height)
The personalization field of this hash is set to:
"ZTxIdHeadersHash"
A BLAKE2b-256 hash of the following values
T.2a: prevouts_digest (32-byte hash) T.2b: sequence_digest (32-byte hash) T.2c: outputs_digest (32-byte hash)
The personalization field of this hash is set to:
"ZTxIdTranspaHash"T.2a: prevouts_digest
A BLAKE2b-256 hash of the field encoding of all outpoint
field values of transparent inputs to the transaction.
The personalization field of this hash is set to:
"ZTxIdPrevoutHash"T.2b: sequence_digest
A BLAKE2b-256 hash of the 32-bit little-endian representation of all nSequence
field values of transparent inputs to the transaction.
The personalization field of this hash is set to:
"ZTxIdSequencHash"T.2c: outputs_digest
A BLAKE2b-256 hash of the concatenated field encodings of all transparent
output values of the transaction. The field encoding of such an output consists
of the encoded output amount (8-byte little endian) followed by
the scriptPubKey byte array (serialized as Bitcoin script).
The personalization field of this hash is set to:
"ZTxIdOutputsHash"
The digest of Sapling components is composed of two subtrees which are organized to
permit easy interoperability with the CompactBlock representation of Sapling data
specified by the ZIP 307 Light Client Protocol [6].
This digest is a BLAKE2b-256 hash of the following values
T.3a: sapling_spends_digest (32-byte hash) T.3b: sapling_outputs_digest (32-byte hash) T.3c: valueBalance (64-bit signed little-endian)
The personalization field of this hash is set to:
"ZTxIdSaplingHash"T.3a: sapling_spends_digest
This digest is a BLAKE2b-256 hash of the following values
T.3a.i: sapling_spends_compact_digest (32-byte hash) T.3a.ii: sapling_spends_noncompact_digest (32-byte hash)
The personalization field of this hash is set to:
"ZTxIdSSpendsHash"T.3a.i: sapling_spends_compact_digest
A BLAKE2b-256 hash of the field encoding of all nullifier field
values of Sapling shielded spends belonging to the transaction.
The personalization field of this hash is set to:
"ZTxIdSSpendCHash"T.3a.ii: sapling_spends_noncompact_digest
A BLAKE2b-256 hash of the non-nullifier information for all Sapling shielded spends belonging to the transaction, excluding both zkproof data and spend authorization signature(s). For each spend, the following elements are included in the hash:
T.3a.ii.1: cv (field encoding bytes) T.3a.ii.2: anchor (field encoding bytes) T.3a.ii.3: rk (field encoding bytes)
In Transaction version 5, Sapling Spends have a shared anchor, which is hashed into the sapling_spends_noncompact_digest for each Spend.
The personalization field of this hash is set to:
"ZTxIdSSpendNHash"T.3b: sapling_outputs_digest
This digest is a BLAKE2b-256 hash of the following values
T.3b.i: sapling_outputs_compact_digest (32-byte hash) T.3b.ii: sapling_outputs_memos_digest (32-byte hash) T.3b.iii: sapling_outputs_noncompact_digest (32-byte hash)
The personalization field of this hash is set to:
"ZTxIdSOutputHash"T.3b.i: sapling_outputs_compact_digest
A BLAKE2b-256 hash of the subset of Sapling output information included in the
ZIP-307 [6] CompactBlock format for all Sapling shielded outputs
belonging to the transaction. For each output, the following elements are included
in the hash:
T.3b.i.1: cmu (field encoding bytes) T.3b.i.2: ephemeral_key (field encoding bytes) T.3b.i.3: enc_ciphertext[..52] (First 52 bytes of field encoding)
The personalization field of this hash is set to:
"ZTxIdSOutC__Hash" (2 underscore characters)T.3b.ii: sapling_outputs_memos_digest
A BLAKE2b-256 hash of the subset of Sapling shielded memo field data for all Sapling shielded outputs belonging to the transaction. For each output, the following elements are included in the hash:
T.3b.ii.1: enc_ciphertext[52..564] (contents of the encrypted memo field)
The personalization field of this hash is set to:
"ZTxIdSOutM__Hash" (2 underscore characters)T.3b.iii: sapling_outputs_noncompact_digest
A BLAKE2b-256 hash of the remaining subset of Sapling output information not included
in the ZIP 307 [6] CompactBlock format, excluding zkproof data, for all
Sapling shielded outputs belonging to the transaction. For each output, the following
elements are included in the hash:
T.3b.iii.1: cv (field encoding bytes) T.3b.iii.2: enc_ciphertext[564..] (post-memo Poly1305 AEAD tag of field encoding) T.3b.iii.3: out_ciphertext (field encoding bytes)
The personalization field of this hash is set to:
"ZTxIdSOutN__Hash" (2 underscore characters)
A new per-input transaction digest algorithm is defined that constructs a hash that may be
signed by a transaction creator to commit to the effects of the transaction. In the case
that the transaction consumes no transparent inputs, it should be possible to just sign
the transaction identifier produced by the TxId Digest algorithm. In the case that
transparent inputs are present, this algorithm follows closely the ZIP 143 [5]
algorithm.
The overall structure of the hash is as follows; each name referenced here will be described in detail below:
signature_digest ├── header_digest ├── transparent_sig_digest └── sapling_digest
A BLAKE2b-256 hash of the following values
S.1: header_digest (32-byte hash output) S.2: transparent_sig_digest (32-byte hash output) S.3: sapling_digest (32-byte hash output)
The personalization field of this hash is set to:
"ZcashTxHash_" || CONSENSUS_BRANCH_ID
ZcashTxHash_ has 1 underscore character.
This value has the same personalization as the top hash of the transaction identifier digest tree, so that what is being signed in the case that there are no transparent inputs is just the transaction id.
Identical to that specified for the transaction identifier.
If we are producing a hash for the signature over a transparent input,
the value of the digest produced here depends upon the value of a hash_type
flag as in ZIP 143 [5].
The construction of each component below depends upon the values of the
hash_type flag bits. Each component will be described separately
This digest is a BLAKE2b-256 hash of the following values
S.2a: prevouts_sig_digest (32-byte hash) S.2b: sequence_sig_digest (32-byte hash) S.2c: outputs_sig_digest (32-byte hash) S.2d: txin_sig_digest (32-byte hash)
The personalization field of this hash is set to:
"ZTxIdTranspaHash"S.2a: prevouts_sig_digest
This is a BLAKE2b-256 hash initialized with the personalization field value
ZTxIdPrevoutHash.
If the SIGHASH_ANYONECANPAY flag is not set:
identical to the value of ``prevouts_digest`` as specified for the transaction identifier in section T.2a.
otherwise:
the hash is immediately finalized, without being updated with any additional dataS.2b: sequence_sig_digest
This is a BLAKE2b-256 hash initialized with the personalization field value
ZTxIdSequencHash.
If the SIGHASH_ANYONECANPAY flag is not set, and the sighash type is neither
SIGHASH_SINGLE nor SIGHASH_NONE:
identical to the value of ``sequence_digest`` as specified for the transaction identifier in section T.2b.
otherwise:
the hash is immediately finalized, without being updated with any additional dataS.2c: outputs_sig_digest
This is a BLAKE2b-256 hash initialized with the personalization field value
ZTxIdOutputsHash.
If the sighash type is neither SIGHASH_SINGLE nor SIGHASH_NONE:
identical to the value of ``outputs_digest`` as specified for the transaction identifier in section T.2c.
If the sighash type is SIGHASH_SINGLE and the signature hash is being computed for
the transparent input at a particular index, and a transparent output appears in
the transaction at that index:
the hash is updated with the transaction serialized form of the transparent output at that index, and finalized.
If the sighash type is SIGHASH_SINGLE and the signature is being computed for
a shielded input, or if the sighash type is SIGHASH_NONE:
the hash is immediately finalized, without being updated with any additional dataS.2d: txin_sig_digest
This is a BLAKE2b-256 hash initialized with the personalization field value
Zcash___TxInHash (3 underscores).
If the signature hash is being computed for a transparent input, the hash is updated with the following properties of that input:
S.2d.i: prevout (field encoding) S.2d.ii: script_code (field encoding) S.2d.iii: value (8-byte signed little-endian) S.2d.iv: nSequence (4-byte unsigned little-endian)
otherwise:
the hash is immediately finalized, without being updated with any additional data
Identical to that specified for the transaction identifier.
A new transaction digest algorithm is defined that constructs a digest which commits to the authorizing data of a transaction from a tree of BLAKE2b-256 hashes. The overall structure of the hash is as follows:
auth_digest ├── transparent_scripts_digest └── sapling_auth_digest
Each node written as snake_case in this tree is a BLAKE2b-256 hash of authorizing
data of the transaction.
The pair (Transaction Identifier, Auth Commitment) constitutes a commitment to all the data of a serialized transaction that may be included in a block.
A BLAKE2b-256 hash of the following values
A1: transparent_scripts_digest (32-byte hash output) A2: sapling_auth_digest (32-byte hash output)
The personalization field of this hash is set to:
"ZTxAuthHash_" || CONSENSUS_BRANCH_ID
ZTxAuthHash_ has 1 underscore character.
A BLAKE2b-256 hash of the field encoding of the Bitcoin script associated with each transparent input belonging to the transaction.
The personalization field of this hash is set to:
"ZTxAuthTransHash"
A BLAKE2b-256 hash of the field encoding of the Sapling zkproof value of each Sapling
Spend Description, followed by the field encoding of the spend_auth_sig value of each
Sapling Spend Description belonging to the transaction, followed by the field encoding of
the zkproof field of each Sapling Output Description belonging to the transaction,
followed by the field encoding of the binding signature:
A.2a: spend_zkproofs (field encoding bytes) A.2b: spend_auth_sigs (field encoding bytes) A.2c: output_zkproofs (field encoding bytes) A.2d: binding_sig (field encoding bytes)
The personalization field of this hash is set to:
"ZTxAuthSapliHash"
The nonmalleable transaction identifier specified by this ZIP will be used
in the place of the current malleable transaction identifier within the
Merkle tree committed to by the hashMerkleRoot value. However, this
change now means that hashMerkleRoot is not sufficient to fully commit
to the transaction data, including witnesses, that appear within the block.
As a consequence, we now need to add a new commitment to the block header.
This commitment will be the root of a Merkle tree that has parallel structure
to the tree committed to by hashMerkleRoot (a path through this Merkle
tree to a transaction identifies the same transaction as that path reaches
in the tree rooted at hashMerkleRoot), but where the leaves are hashes
produced according to the Authorizing Data Commitment part of this
specification.
This new commitment is named hashAuthDataRoot and is the root of a left-dense
binary Merkle tree of transaction authorizing data commitments. Empty internal nodes
and leaves in the Merkle tree (nodes without children) have the "null" hash value
[0u8; 32]. Hashes in this tree are BLAKE2b-256 hashes personalized by the string
"ZcashAuthDatHash".
Changing the block header format to allow space for an additional
commitment is somewhat invasive. Instead, the name and meaning of the
hashLightClientRoot field, described in ZIP 221 [3], is changed.
hashLightClientRoot is renamed to hashBlockCommitments. The value
of this hash is the BLAKE2b-256 hash personalized by the string "ZcashBlockCommit"
of the following elements:
hashLightClientRoot (as described in ZIP 221) hashAuthDataRoot (as described below) terminator [0u8;32]
This representation treats the hashBlockCommitments value as a linked
list of hashes terminated by arbitrary data. In the case of protocol upgrades
where additional commitments need to be included in the block header, it is
possible to replace this terminator with the hash of a newly defined structure
which ends in a similar terminator. Fully validating nodes MUST always use the
entire structure defined by the latest activated protocol version that they
support.
The linked structure of this hash is intended to provide extensibility for use by light clients which may be connected to a third-party server that supports a later protocol version. Such a third party SHOULD provide a value that can be used instead of the all-zeros terminator to permit the light client to perform validation of the parts of the structure it needs.
Unlike the hashLightClientRoot change, the change to hashBlockCommitments
happens in the block that activates this ZIP.
The block header byte format and version are not altered by this ZIP.
| [1] | RFC 2119: Key words for use in RFCs to Indicate Requirement Levels |
| [2] | ZIP 200: Network Upgrade Activation Mechanism |
| [3] | ZIP 221: FlyClient - Consensus Layer Changes |
| [4] | ZIP 76: Transaction Signature Validation before Overwinter |
| [5] | (1, 2, 3) ZIP 143: Transaction Signature Validation for Overwinter |
| [6] | (1, 2, 3) ZIP 307: Light Client Protocol for Payment Detection |
| [7] | Zcash Protocol Specification, Version 2020.1.24 [NU5 proposal]. Section 7.1: Transaction Encoding and Consensus |