[ZIP 227] Attack against Spendability due to ρ potentially not being unique in an issuance action

[daira]

There are several related issues concerning ρ values for issued notes in ZIP 227 @ 2e8876c.

ZIP 227 T.5a.i.4 rho says:

Nullifier encoded as 32-byte representation of a point on the Pallas curve.

However ρ is not the nullifier of the note being issued, and it's not sufficiently clear that there is an extra nullifier here that is not associated with a note.

If this were an output note of an Orchard[ZSA] Action, its ρ value would be taken from $\mathsf{nf^{old}}$ of the Orchard note spent by the Action. So, it necessarily has the same type as an Orchard nullifier: i.e. $\mathbb{F}_ {q_ {\mathbb{P}}}$ which is the output type of $\mathsf{DeriveNullifier}$ in § 4.1.6 Computing ρ values and Nullifiers. Below we will suggest that it should be treated as an Orchard nullifier, which may explain why T.5a.i.4 calls it that. But as written, I think an implementor might just see this as a mistake, as I did initially.

The rest of the protocol depends on ρ values being unique in order to prevent Faerie Gold attacks. That is, since ρ is the only field of an Orchard[ZSA] note that isn't of necessity chosen by the note creator, the security argument for uniqueness of Orchard nullifiers depends on ρ values being unique across Orchard[ZSA] notes (and also on $\mathsf{DeriveNullifier}$ being collision-resistant on its ρ input). Uniqueness of ρ values would have to include those of Orchard[ZSA] notes being issued, as well as of notes created in Actions.

Note that duplicating a ρ value does not help to duplicate the corresponding nullifier unless the other fields of the note are the same. In particular, assuming collision-resistance of both the AssetId → AssetDigest hash (based on BLAKE2b-512) and the AssetDigest → AssetBase mapping $\mathsf{ZSAValueBase}$ (based on $\mathsf{GroupHash}^\mathbb{P}$), the issuance bundles containing notes with colliding nullifiers would need to be signed under the same issuance key $\mathsf{ik}$. Therefore the scope for Faerie Gold attacks by this method is limited to insider attacks within the same issuer (as defined by issuance key). Thanks to @str4d for pointing out this nuance. However, they do break the Spendability security property as defined on slide 24 of my Understanding the Security of Zcash presentation, and so if we decided to permit the attack, the definition of Spendability would have to be relaxed if we wanted to still assert it. Since the Spendability definition is very complicated as it is, that seems undesirable.

The most obvious way to prevent these attacks is to require that verifiers treat ρ values of issued notes as Orchard nullifiers, checking that they are not duplicated (either between or within transactions) and adding them to the Orchard nullifier set when an IssueAction occurs in a mined transaction. There does not appear to be any consensus rule requiring this in the current draft (it would need to be in ZIP 227 - Specification: Consensus Rule Changes). Since the nullifier in an IssueAction is not the nullifier of a note, we would need to modify wording that assumes nullifiers always belong to notes [*].

In making this change we must be careful not to introduce roadblock attacks, which the current protocol is intended to prevent. A roadblock attack is an attack on availability in which an adversary sees a transaction and then can create another transaction that would block it if mined first. In order to prevent a roadblock attack against (or using) issuance transactions, the ρ value should be derived pseudorandomly in a way that can't be chosen to match one in a transaction created by another party. The way I would suggest to do this is to not encode ρ in an IssueAction, and instead derive it as a hash of the txid and the IssueAction's index in the transaction. For example:

$$\mathsf{DeriveIssuedRho}(txid ⦂ \mathbb{B}^{\mathbb{Y}[32]}, index ⦂ \mathbb{N}) := \mathsf{ToBase^{Orchard}}(\mathsf{PRF^{expand}}(txid, [\textsf{domain-sep-byte}] \textsf{ || } \mathsf{LEI2OSP}_{32}(index)))$$

where $\mathsf{ToBase^{Orchard}}$ is defined in § 4.2.3 Orchard Key Components. (The use of $\mathsf{ToBase^{Orchard}} \circ \mathsf{PRF^{expand}}$ is an existing idiom to produce a value pseudorandomly distributed on the full range of $\mathbb{F}_ {q_ {\mathbb{P}}}$. It would also be sufficient in this case to use BLAKE2s truncated to 254 bits, which is more circuit-efficient in case we had any reason to include this hash in a future circuit.)

Note that in this approach, even though the ρ values of issued notes are no longer committed to directly by issue_notes_digest (so ZIP 227 T.5a.i.4 rho is removed), they are still committed to by the txid — because they're derived from it and the index, and because the number of issuance actions is committed to as effecting data. A road-blocking adversary cannot reuse an existing txid because then it would commit to all of the same effecting data.

On reflection, we could have used this approach for all Orchard ρ values, and it would have been simpler in some respects. [Edit: see later comments for discussion of this.]

---

[*] As far as I can see, the protocol spec only makes the assumption that nullifiers belong to notes in § 1.2 High-level Overview which is explicitly not normative, in § 3.2.3 Nullifiers, and in § 3.9 Nullifier Sets.

The first paragraph of § 3.2.3 should be changed to:

The nullifier for a note \nuseven{or IssueAction}, denoted $\mathsf{nf}$, is a value unique to the note \nuseven{or IssueAction} that is used to prevent double-spends. When a transaction that contains one or more JoinSplit descriptions \sapling{or Spend descriptions} \nufive{or Action descriptions} \nuseven{or IssueActions} is entered into the block chain, all of the nullifiers for notes spent by that transaction, \nuseven{and the IssueAction nullifiers derived as ρ values for issued notes,} are added to the nullifier set of the associated treestate. A transaction is not valid if it would have added a nullifier to the nullifier set that already exists in the set.

Also change § 3.9 to read:

Each full validator maintains a nullifier set logically associated with each treestate. As valid transactions contain-
ing JoinSplit transfers \sapling{or Spend transfers} \nufive{or Action transfers} \nuseven{or issuance actions} are processed, the nullifiers revealed in JoinSplit descriptions \sapling{and Spend descriptions} \nuseven{and Action descriptions}, \nuseven{and the IssueAction nullifiers derived as ρ values for issued notes,} are inserted into the nullifier set associated with the new treestate. Nullifiers are enforced to be unique within a valid block chain, in order to prevent double-spends.

Consensus rule: A nullifier MUST NOT repeat either within a transaction, or across transactions in a valid block
chain. Sprout and Sapling and Orchard nullifiers are considered disjoint, even if they have the same bit pattern.

Note: The nullifier of an OrchardZSA IssueAction is an Orchard nullifier.

(There is some redundancy between the first paragraphs of § 3.2.3 and § 3.9 that should probably be fixed.)

These changes do not include the ones to remove the rho field from IssueActions and the issue_notes_digest computation, or to describe how ρ is derived instead.

[str4d]

On reflection, we could have used this approach for all Orchard ρ values, and it would have been simpler in some respects.

I don't believe this is true. We can derive ρ from the txid here because it is public in the transaction it is used within, and can be constrained for uniqueness directly by the consensus rules. In a regular Orchard transaction, ρ is private, so we are relying on the fact that the circuit ensures it equals the spent note's nullifier to transitively bind it as unique by way of the consensus rules checking the spent note's nullifier to be unique.

[daira]

I added this paragraph about constraints on the attack after discussion with @str4d:

Note that duplicating a ρ value does not help to duplicate the corresponding nullifier unless the other fields of the note are the same. In particular, assuming collision-resistance of both the AssetId → AssetDigest hash (based on BLAKE2b-512) and the AssetDigest → AssetBase mapping $\mathsf{ZSAValueBase}$ (based on $\mathsf{GroupHash}^\mathbb{P}$), the issuance bundles containing notes with colliding nullifiers would need to be signed under the same issuance key $\mathsf{ik}$. Therefore the scope for Faerie Gold attacks by this method is limited to insider attacks within the same issuer (as defined by issuance key). Thanks to @str4d for pointing out this nuance. However, they do break the Spendability security property as defined on slide 24 of my Understanding the Security of Zcash presentation, and so if we decided to permit the attack, the definition of Spendability would have to be relaxed if we wanted to still assert it. Since the Spendability definition is very complicated as it is, that seems undesirable.

[daira]

@str4d:

@daira:

On reflection, we could have used this approach for all Orchard ρ values, and it would have been simpler in some respects.

I don't believe this is true. We can derive ρ from the txid here because it is public in the transaction it is used within, and can be constrained for uniqueness directly by the consensus rules. In a regular Orchard transaction, ρ is private, so we are relying on the fact that the circuit ensures it equals the spent note's nullifier to transitively bind it as unique by way of the consensus rules checking the spent note's nullifier to be unique.

Actually, ρ of the output note in an Action description is public. It's okay for it to be public because the recipient of a note (or parties that obtain it via a viewing key) already know what transaction it was an output of. It's only the connection between outputs and spends that needs to be hidden.

So, I think it would be possible to do this, because you would just add the derived ρ as another public input to the circuit, distinct from $\mathsf{nf^{old}}$.

In any case, it's not useful to make this change unless we want to decouple spends from outputs. And we can do that in any upgrade (even retaining the existing Orchard and OrchardZSA anonymity set and notes).

[daira]

It occurs to me that if we had $\mathsf{DeriveIssuedRho}$ pick a ρ that does not correspond to the $x$-coordinate of a Pallas point (i.e. $x^3 + 5$ is nonsquare in $\mathbb{F}_ {q_\mathbb{P}}$), then it would be disjoint by construction from the nullifiers of Orchard notes. That would have the advantage of precluding any collision between these nullifiers and the ones corresponding to notes, as defence in depth. It is possible to do so deterministically (hash to the field and then if the result is a Pallas $x$-coordinate, modify it to not be, using the same technique as in SSWU hash-to-curve). On the other hand this is more complicated and might not be necessary.

[daira]

In order to prevent a roadblock attack against (or using) issuance transactions, the ρ value should be derived pseudorandomly in a way that can't be chosen to match one in a transaction created by another party. The way I would suggest to do this is to not encode ρ in an IssueAction, and instead derive it as a hash of the txid and the IssueAction's index in the transaction.

This is a bit weird because the ρ values (or any value used to derive them) don't get directly committed to by the sighash. I also realized that it depends on txid uniqueness: if an adversary can produce transactions with two colliding txids, then they will derive the same (or overlapping, if nAssetBurn is not the same) set of ρ values.

To recap the argument for txid uniqueness: every mined transaction has at least one input that is not an input of any other mined transaction. This applies also to the dummy input of coinbase transactions because of the "height in coinbase" rule, which has been enabled since launch in Zcash (also, the effecting data of a coinbase transaction includes nExpiryHeight which from NU5 onward has been required to be set equal to the block height). The transaction inputs and the expiry height are effecting data, so that results in each transaction having a unique input to the txid hash which is collision-resistant.

This argument is, however, dependent on a combined security property of the protocols of all pools from which spends are enabled. For example, you might be able to double-spend in a broken protocol for some pool. The effect of that on other protocols should be constrained by ZIP 209, and in any case should not affect Spendability. I don't want any security properties of ZSAs to be dependent on the transparent or Sapling protocols (or Sprout if they activate before ZIP 2003); it's an ugly expansion of the attack surface.

[To be continued.]