# Penumbra circuit audit

Our understanding of the scope of this audit is as follows:

* Review the design of Penumbra’s multi-asset shielded protocol, including the asset swap and on-chain governance features, in order to understand how it is intended to work.
* Review the specification of the six statements and R1CS circuits used on-chain, both individually and in the ways they are intended to be used together:
* [x] [Spend](https://protocol.penumbra.zone/main/shielded_pool/action/spend.html)
* [x] [Output](https://protocol.penumbra.zone/main/shielded_pool/action/output.html)
* [x] [Swap](https://protocol.penumbra.zone/main/dex/action/swap.html)
* [ ] [SwapClaim](https://protocol.penumbra.zone/main/dex/action/swap_claim.html) [cannot finish because spec is incomplete]
* [x] [UndelegateClaim](https://protocol.penumbra.zone/main/stake/action/undelegate_claim.html)
* [x] [DelegatorVote](https://protocol.penumbra.zone/main/governance/action/delegator_vote.html)
* This includes assessing suitability of the selected cryptographic primitives and parameters where relevant.
* On a best-effort basis within the time available, review the implementation of these circuits using the Arkworks APIs (under `core/component/{shielded-pool,dex,governance}` and in the r1cs modules of the `decaf377` and `poseidon377` repositories), concentrating on areas that seem most likely to have flaws or divergence from the specification.
* The implementation review may drill down into selected parts of Arkworks if we believe there may be a problem in a specific Arkworks gadget used by the circuits — but the implementation of the Groth16 proof system; “out-of-circuit” cryptographic primitives; pairings, curves, fields, and algebraic primitives (other than the `r1cs` modules of `decaf377` and `poseidon377` as noted above); or circuit-building infrastructure are not in scope.
* Encoding and decoding of action descriptions or their elements is not in scope (unless investigation of the circuit code suggests a specific problem there).
* Proving security of the protocol, writing security arguments, cryptanalysis of cryptographic primitives, or quality of randomness generation are not in scope.
* Supply-chain issues with the use of libraries are not in scope.
* Analysis of the consequences of economic or governance policies, or of regulatory impacts, is not in scope.

## Code to be audited

> btw we just merged the only other circuit changes that are planned so here are some commit hashes that should be used for audit -

Penumbra monorepo commit hash:
Commit hash: `0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8`
Repo: https://github.com/penumbra-zone/penumbra

Decaf377 0.5.0
Commit hash: `979cc8846318897bbeb26348999e5f1d0fa5cd7f`
Repo: https://github.com/penumbra-zone/decaf377

Poseidon377 0.5.0
Commit hash: `4900900c1276b0040337d2d5a3732f70a6149487`
Repo: https://github.com/penumbra-zone/poseidon377

Poseidon-permutation 0.4.0
Commit hash: `4900900c1276b0040337d2d5a3732f70a6149487`
Repo: https://github.com/penumbra-zone/poseidon377 (this repo is a workspace which also has the `poseidon-permutation` crate)

### Severity scale

* Critical: A vulnerability that allows feasibly breaking an important security or privacy property affecting the whole Penumbra ecosystem.
* High: A vulnerability that allows feasibly breaking an important security or privacy property that affects some subset of users or wallets, or that will apply after some planned change to the system.
* Medium: A difficult-to-exploit threat to the ecosystem security properties.
* Low: A relatively minor threat to the Penumbra ecosystem.
* Informational: No immediate threat to the Penumbra ecosystem. May provide suggestions for specification improvement, or conditions that could later lead to an exploitable finding.

## Findings

### A. Insufficient randomization of $cv$ commitment for swaps

**Severity:** High; privacy violation if left unfixed once Sealed-Bid Batch swaps are implemented.

**Impact:** After Sealed-Bid Batch swaps are implemented, the asset values $v_1$ and $v_2$ are supposed to be private. However, these values can be obtained by a very feasible search, due to insufficient randomization of the commitment $cv$.

**Finding:** $\tilde{v}$ is shared for randomization between $cv$ and $cv_f$, which are both public. For Penumbra V1 this doesn't leak any additional information because the asset types and values are public (so $cv$ is deterministically derived from $cv_f$). However, when Sealed-Bid Batch Swaps are implemented (where asset types remain public but values are private), $cv$ can be trivially derandomized by subtracting $cv_f$, and then the space of $(v_1, v_2)$ can be searched to reveal the values.

Given that [a rational trader will set one of $v_1$ and $v_2$ to zero](https://protocol.penumbra.zone/main/dex/swap.html#swap-actions), this reduces to finding either $v_1$ such that $[-v_1]\, G_1 = cv - cv_f$, or $v_2$ such that $[-v_2]\, G_2 = cv - cv_f$.

In fact there are meet-in-the-middle attacks on the search space, so that the expected work is $\Theta(\sqrt{2^N})$ elliptic curve operations where $N$ is the number of unknown bits in $v_1$ or $v_2.$ This could be implemented using either a [Pollard kangaroo](https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm) attack, or a simpler meet-in-the-middle attack using more memory but less constant overhead. For the latter, the constant in the $\Theta$ notation is essentially $1$, i.e. we need only up to $\sqrt{2^N}$ decaf377 curve additions or doublings if we initially guess correctly which of $v_1$ and $v_2$ is zero, or up to twice that if we guess incorrectly. Since it is unlikely in practice that $N$ is more than $64$ (or even $50$), this is extremely feasible in a short time on a single machine.

The significance of this finding depends on whether a new phase 2 Groth16 setup will be required in any case when Sealed-Bid Batch swaps are implemented:
* If a new setup will be required, then this issue can be fixed then.
* If a new setup would not be required, then it is likely to be significantly easier to change the definition of $cv$ now.

The needed design change would impact the [Balance commitment integrity](https://protocol.penumbra.zone/main/dex/action/swap.html#balance-commitment-integrity) check of the Swap circuit. There is some additional cost in the Swap circuit, since another full-width fixed-base scalar multiplication is required to compute the new randomized point $[\widetilde{v}]\, G_{\widetilde{v}}$ (following the notation in the recommendation below).

**Recommendations:**

A1. Use separate randomization $[\widetilde{v}]\, G_{\widetilde{v}}$ for $cv$ in asset swaps, where $G_{\widetilde{v}}$ is the same generator as for the $cv_f$ commitment, but $\widetilde{v}$ is a scalar private witness to the Swap circuit that is uniformly random and independent of $\widetilde{v_f}$.
A2. Double-check all other commitments for adequate randomization.

### B. `SwapClaim` circuit specification is incomplete

**Severity:** Undetermined.

**Impact:** The `SwapClaim` circuit implementation cannot be audited against its specification, because its specification is incomplete.

**Finding:** Several statements within the `SwapClaim` circuit are not specified; they are only described approximately in prose.

In particular:
* Fee Consistency Check: the statement inputs use $v_f$ for both the witnessed and public fee values.
* Output Amounts Integrity Check: the fixed-point arithmetic and divisions in particular need to be precisely specified.
* Value commitment checks: there is currently no statement at all for them, but presumably they are implemented as part of the Output Amounts Integrity Check.

**Recommendations:**

B1. Specify the Output Amounts Integrity Check statement.
B2. Specify the statements that check the balance commitments.
B3. Clarify the Fee Consistency Check.

### C. Parts of the non-circuit non-consensus protocol are unspecified or underspecified

**Severity:** Undetermined.

**Impact:** TBD

**Finding:** Several parts of the protocol are not specified, while being referred to in other parts of the documentation.

Examples include:
* [2.4 Key Agreement](https://protocol.penumbra.zone/main/crypto/decaf377-ka.html)
* [8.3 Note Ciphertexts](https://protocol.penumbra.zone/main/shielded_pool/note_ciphertexts.html)
* The derivation process for note encryption keys is specified in [4.3 Payload Keys](https://protocol.penumbra.zone/main/addresses_keys/transaction_crypto.html), but that does not cover the decryption process, or the checks therein that clients must perform to be safe from e.g. Faerie Gold attacks.
* [9.3 LPNFTs](https://protocol.penumbra.zone/main/dex/lpnft.html)
* [9.5.3 Position Actions](https://protocol.penumbra.zone/main/dex/action/position.html)
* [10.8.1 Delegate](https://protocol.penumbra.zone/main/stake/action/delegate.html)
* [10.8.2 Undelegate](https://protocol.penumbra.zone/main/stake/action/undelegate.html)
* [11.1.2 ValidatorVote](https://protocol.penumbra.zone/main/governance/action/validator_vote.html)
* [11.1.3 Proposal Actions](https://protocol.penumbra.zone/main/governance/action/proposal.html)

**Recommendations:**

C1. Specify the remaining unspecified parts of the protocol.
C2. Remove blank pages for, and references to, documentation that is no longer relevant.

### D. Detection keys can potentially be used to link diversified addresses

**Severity:** Informational.

**Impact:** Users of detection keys may not understand the security impact of giving out these keys on unlinkability of their diversified addresses.

**Finding:** A detection entity given a set of `k` detection keys can link the corresponding diversified addresses via the clue keys contained within them.

* The detection entity is (by construction) reporting detected transactions from each detection key `dtk_d` in the set to the same user, so empirically knows that the detection keys are linked.
* If the detection entity observes two addresses belonging to the user, the entity can link them because `ck_d` appears in each address and is derived solely from `dtk_d`.

The protocol documentation [currently states in 1.3 Addresses and Keys](https://protocol.penumbra.zone/main/concepts/addresses_keys.html) only that diversified addresses are "publicly unlinkable", which provides insufficient detail. [4.3 Addresses and Detection Keys](https://protocol.penumbra.zone/main/addresses_keys/addresses.html#detection-keys) only describes delegation of a probabilistic detection capability, not an address linkability capability. In particular, users that are familiar with the privacy implications of giving out a Viewing Key may not recognise that giving out a set of Detection Keys also carries a subset of those privacy implications.

**Recommendations:**

D1. Document the impact of giving out detection keys on unlinkability of diversified addresses.

### E. Documentation is not fully updated to distinguish what functionality will not be deployed in Penumbra V1

**Severity:** Low.

**Impact:** Anyone wishing to understand the security of Penumbra (including its users and potential users), could obtain a misleading impression of the security properties provided in Penumbra V1 from the protocol documentation, especially if they read only a subset of it.

**Finding:** The Penumbra documentation was written assuming that all of the features it described would be included in the initial production release. Subsequent decisions have narrowed the scope of Penumbra V1, in particular to not include certain privacy features. A few parts of the documentation have been updated to reflect this narrowing of scope and reduction in privacy, but there are still significant parts of the documentation that have not been updated.

Examples include:
* The [main ZSwap page](https://protocol.penumbra.zone/main/dex.html) (and various other places therein) describe several features as part of ZSwap, but that are not implemented for V1:
* Amount hiding and front-running protection (via Flow Encryption).
* Sealed-Bid Batch Swaps.
* Nit: section 9.1 sidebar is named after this feature; rename to "Batch Swaps"
* [10.4 Delegation](https://protocol.penumbra.zone/main/stake/delegation.html) describes how delegation works in terms of Flow Encryption, which is not part of Penumbra V1.

**Recomendations:**

E1. Update all documentation to clarify what will be deployed in V1, and what will not be deployed until later.
E2. Clarify in documentation the privacy implications of Penumbra V1.

### F. Groth16 requires circuit-specific setup

**Severity:** Low, unless a separate circuit flaw is found after launch.

**Impact:** Mitigating any flaw in the circuits would require re-running the phase 2 trusted setup.

**Finding:** Groth16 is a solid choice of proof system. However, we note that its requirement for a circuit-specific "phase 2" trusted setup would introduce significant delay to mitigation of any circuit flaw. That would be particularly undesirable if the flaw were being actively exploited. Running a setup is also necessarily a public activity, which might tip off potential adversaries if it needed to be done at an unscheduled time.

There exist other choices of proof system that require only universal setup (i.e. they have no phase 2 setup). Some of them support R1CS, would not require any change of curves or other protocol changes beside the proof system itself, and have good performance (but slightly larger proof sizes) compared to Groth16.

In addition, Groth16 does not have post-quantum (knowledge) soundness. Therefore Penumbra, like the Sapling protocol it is partially based on, does not ensure balance preservation or spend authorization against quantum attacks. This is not likely to be a short-term problem, but should be considered for longer-term evolution of the protocol.

**Recommendations:**

F1. Consider the possibility of switching to a proof system with universal setup as part of a future routine upgrade.
F2. Keep up-to-date on research into plausibly post-quantum proof systems that could be practically deployable in Penumbra.

### G. Miscellaneous specification issues

These are collected from the auditing notes below.

* In [2.3 Randomizable Signatures](https://protocol.penumbra.zone/main/crypto/decaf377-rdsa.html), the description of the [spend auth signature scheme](https://protocol.penumbra.zone/main/crypto/decaf377-rdsa.html#spendauth-signatures) specifies multiplicative blinding, which is inconsistent with other documentation and with the implementation:
* [The Spend circuit constraint](https://protocol.penumbra.zone/main/shielded_pool/action/spend.html#randomized-verification-key-integrity) specifies additive.
* [The implementation is additive](https://rustdoc.penumbra.zone/main/src/decaf377_rdsa/verification_key.rs.html#181-188).
* In [6 Assets and Values](https://protocol.penumbra.zone/main/assets.html):
* The link to Cosmos specification document ADR001 is broken. This document appears to be available [here](https://github.com/cosmos/ibc-go/blob/main/docs/architecture/adr-001-coin-source-tracing.md).
* In the [Value Generators](https://protocol.penumbra.zone/main/assets.html#value-generators) section, `from_le_bytes(b"penumbra.value.generator")` should be `from_le_bytes(blake2b(b"penumbra.value.generator"))` to match [`AssetIdVar::value_generator`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/asset/src/asset/r1cs.rs#L47-L55).
* In [8.4.1 Spend](https://protocol.penumbra.zone/main/shielded_pool/action/spend.html):
* [Merkle auth path validation](https://protocol.penumbra.zone/main/shielded_pool/action/spend.html#merkle-auth-path-verification): "Only for notes with non-zero values $v \neq 0$, the note is unrooted" should be "Only for notes with zero value ($v = 0$), the note is unrooted".
* In [8.4.2 Output](https://protocol.penumbra.zone/main/shielded_pool/action/output.html):
* The [circuit specification](https://protocol.penumbra.zone/main/shielded_pool/action/output.html#note-commitment-integrity) uses `hash_6` to derive the note commitment including $ck_d$, while the [note commitment specification](https://protocol.penumbra.zone/main/shielded_pool/note_commitments.html) uses `hash_5` and doesn't commit to $ck_d$.
* In [9.1 Batch Swaps](https://protocol.penumbra.zone/main/dex/swap.html):
* The sidebar has a different name for this section ("Sealed-Bid Batch Swaps").
* In the [Swap actions](https://protocol.penumbra.zone/main/dex/swap.html#swap-actions) section, `note_commitment` should be named `swap_commitment`.
* In [9.5.1 Swap](https://protocol.penumbra.zone/main/dex/action/swap.html):
* It's confusing that `rseed` in the input to a swap commitment is used to derive identically named `rseed` for the corresponding notes.
* The signs of $cv$ and $cv_f$ are confusing because the convention is different to the Spend and Output circuits. Those circuits used positive-signed values for the commitments, and then had their transaction-relative sign applied to the commitments per the [Action reference](https://protocol.penumbra.zone/main/transactions/actions.html#all-actions). This should be explained more thoroughly.
* $B_d$ is not checked to be non-identity in the spec. (It is checked in the implementation, as it needs to be.)
* In [9.5.2 SwapClaim](https://protocol.penumbra.zone/main/dex/action/swap_claim.html):
* "The body of a SwapClaim has four parts" should be "five parts".
* "A balance commitment, which commits to the value balance of the spent note;" this isn't actually a spent note.
* The spec switches between $v$ and $\Delta$ for denoting swap values.
* The details about how the output note `rseed`s are derived is given in the specification for the `Swap` circuit, where it goes unused (as `BatchSwapOutputData` is unknown at that point). Consider moving everything from "The output notes for the `Swap`" down to just before "Invariants" to the `SwapClaim` spec (or to a separate page that specifies the whole swap protocol).
* In [9.2 Concentrated Liquidity](https://protocol.penumbra.zone/main/dex/concentrated_liquidity.html), there appears to be some out-of-date documentation (e.g. referring to NFTs for liquidity positions which is not the current design).
* In [10.8.3 UndelegateClaim](https://protocol.penumbra.zone/main/stake/action/undelegate_claim.html):
* $v_e$ is documented as the expected balance output from `ConvertCircuit`, but it is specified as a partial commitment to the value balance of the circuit. Fix this by instead specifying $v_e = p \cdot v_i$, and then either use a new intermediate variable name for the partial commitment, or simply defined $cv = [-v_i] G_{v_i} + [v_e] G_{v_t} + [\tilde{v}] G_\tilde{v}$.
* We note that the base for the target asset is denoted $G_{v_t}$, so it might instead be intended that $v_t$ is the expected balance computed from the public conversion rate and the input amount. In that case, specify that, and rename $v_e$ to something else.

Please also see the findings in the [Implementation](#Implementation) section below (to avoid duplication we will not repeat them here).

----

## Detailed auditing notes

### Choices of cryptographic primitives

#### Elliptic curves

Penumbra uses Groth16 over BLS12-377 for the proof system. The embedded application curve is decaf377, i.e. Decaf over $E_{Ed/BLS}$ from the [Zexe paper](https://eprint.iacr.org/2018/962).

These are sound choices of curves. BLS12-377 is well-studied and deployed; short of a major cryptanalytic breakthrough that would likely affect many other curves, any serious problems with it would have been found by now. The choice of a Decaf-based prime-order group eliminates issues with cofactors.

TODO: It will be necessary to check that the circuits implementing decaf377 are defined in a way that preserves Decaf's intended prime-order group without abstraction leaks. This will likely be okay provided that encoding and decoding are done inside the circuits.

##### Cost of discrete log attacks

BLS12-377 has an [estimated security level of $2^{126}$](https://gitlab.inria.fr/tnfs-alpha/alpha/-/blob/cbdf9617f7006d9cadd40660a33444458bfd7638/sage/tnfs/param/TestVectorSparseSeed.py#L62) against STNFS attacks, according to accompanying data for the ["tnfs" library](https://gitlab.inria.fr/tnfs-alpha/alpha) developed by the authors of [[GS2021]](https://eprint.iacr.org/2019/885).

> I verified that this is referring to the correct curve by recalculating the subgroup size as $q = u^4 - u^2 + 1$ where $u = 2^{63} + 2^{58} + 2^{56} + 2^{51} + 2^{47} + 2^{46} + 1$. This matches $q$ given at [The decaf377 group](https://protocol.penumbra.zone/main/crypto/decaf377.html#curve-parameters) and also the [Standard Curve Database entry for BLS12-377](https://neuromancer.sk/std/bls/BLS12-377).

BLS12-377 has a prime-order subgroup size of $252.2$ bits and a security level against Pollard rho of $\sqrt{\frac{\pi q}{12}} \approx 2^{125.1}$.

The group order of decaf377 is $r$ given at [The decaf377 group](https://protocol.penumbra.zone/main/crypto/decaf377.html#curve-parameters) which is $250.2$ bits, resulting in a security level against Pollard rho of $\sqrt{\frac{\pi r}{4}} \approx 2^{124.9}$.

> The difference between the denominators in the $\sqrt{\frac{\pi q}{12}}$ formula for Pollard rho security of BLS12-377 and the $\sqrt{\frac{\pi r}{4}}$ formula for decaf377, is that BLS12-377 is a CM curve with an automorphism group of size 6, allowing a slightly faster Pollard rho attack [[DGM1999]](https://inria.hal.science/inria-00511639).

A security level of at least $2^{124.9}$ makes discrete log attacks conservatively infeasible using classical (non-quantum) computing resources.

#### Hashes and PRFs

##### Poseidon

There was insufficient time in the audit period to check the parameters and compatibility of the Poseidon implemented by Penumbra with any version of the Poseidon specification.

There are known theoretical attacks against Poseidon, and similarly we did not have time to check that these are inapplicable.

##### Hash-to-group

Check everything is properly domain-separated (looks to be).

#### Commitments

Poseidon-based

* Finding: In [9.1 Swap actions](https://protocol.penumbra.zone/main/dex/swap.html#swap-actions), `note_commitment` should be named `swap_commitment`. ✅

### Addresses

For clarity, we use "account" to mean the key tree separation of spend authority.

Diversifiers being 16 bytes is the right way to do this; doesn't require the weird FF1 PRP used in Zcash Sapling and Orchard. It's definitely simpler to use AES here.

The derivation of $g_d$ uses the CDH encode_to_curve, which produces output that is not uniform on the group. We believe that this does not result in any vulnerability, taking into account the hashing of $d$ and reduction modulo $q$ to get the input to encode_to_curve, as described in [Addresses and Detection Keys -- Diversifiers](https://protocol.penumbra.zone/main/addresses_keys/addresses.html#diversifiers). That is, unlinkability of diversified addresses does not require the output to be uniform on the group.

We did not consider privacy properties of detection keys in detail (but see [Finding D](#D-Detection-keys-can-potentially-be-used-to-link-diversified-addresses)). Detection keys are per diversified address.

Address replacement attacks were considered out of scope.

### Note plaintexts

* Not clear from the specification whether the note plaintext includes either $pk_d$ or $ck_d$. Seems implied from the reference (request clarification).
* The note commitment has the clue key $ck_d$ as an input, and in order for the recipient to check the note commitment, it must know $ck_d$. Therefore I assume it is in the note plaintext. --Daira-Emma
* However this is only in the circuit description, not the note commitment specification (per finding below), so while we presume the circuit description is more likely correct, we need to confirm this against the implementation. --str4d
* Finding: Note encryption is unspecified. ✅
* What happens if the adversary mixes $d$ and $pk_d$ from one address with a clue key $ck_d$ from another? (Did not have time to investigate.)
* The [ovk-wrapped key encryption](https://protocol.penumbra.zone/main/addresses_keys/transaction_crypto.html#ovk-wrapped-key) stores the shared secret (`[esk] pk_d`), not the KDF output used to encrypt the note plaintext.
* It should be possible to verify the shared secret, by deriving $esk$ from $rseed$ and then re-deriving the expected shared secret from $esk$ and $pk_d$.
* In Zcash Sapling and Orchard, we do a similar re-derivation to verify esk.
* TODO: Determine whether verifying the shared secret is necessary. (Did not have time to investigate.)

### Swap ciphertexts

* Daira-Emma thinks there could potentially be an issue with lack of key commitment / (key, input) collisions in the note encryption.
* Is it possible to find a swap commitment that collides with one of the other [fixed nonces](https://protocol.penumbra.zone/main/addresses_keys/transaction_crypto.html#nonces)?
* Why do you both derive a key from the swap commitment, then use the first 12 bytes as the nonce?
* Consider the nonce collision probability, both with the fixed nonces (96-bit multi-target preimage) and between swap nonces (96-bit collision). Does the swap commitment have to be considered adversarially generated?
* This appears not to be an issue because the KDF for swap encryption mixes in the entire swap commitment, so it could just as well have used a constant (distinct) nonce such as $[2, 0\ldots]$.
* https://protocol.penumbra.zone/main/addresses_keys/transaction_crypto.html#per-action-payload-note-memo-key "should not" -> "must not"
* Do they document to check the note commitment on decryption?

### Circuits

TODO: check that hash-to-curve is correct. (Did not have time to investigate.)

The cofactor-4 Edwards curve defined over the BLS12-377 scalar field $\mathbb{F}_q$ has order $4r$, where $q > 4r$. Thus it is safe to encode application-layer (decaf377) scalars as curve-layer field elements.

#### Nullifier Uniqueness

[Nullifiers -- State Fragments](https://protocol.penumbra.zone/main/sct/nullifiers.html#state-fragments) does not document the security arguments for choice of nullifier keys.

The high-level argument for resistance to Faerie Gold and roadblock attacks is the same as in Sapling; see [section 8.4 Faerie Gold attack and fix](https://zips.z.cash/protocol/protocol.pdf#faeriegold) of the Zcash protocol spec.

#### Output

- Finding: The [circuit specification](https://protocol.penumbra.zone/main/shielded_pool/action/output.html#note-commitment-integrity) uses `hash_6` to derive the note commitment including $ck_d$, while the [note commitment specification](https://protocol.penumbra.zone/main/shielded_pool/note_commitments.html) uses `hash_5` and doesn't commit to $ck_d$. ✅

#### Spend

> We verify the auth_sig using the randomized verification key, which must not be 0, provided on the spend body, even if the amount of the note is 0.

The randomized verification key not being zero is unnecessary because [key rerandomization is defined using additive blinding in the implementation](https://rustdoc.penumbra.zone/main/src/decaf377_rdsa/verification_key.rs.html#181-188) (like [RedDSA](https://zips.z.cash/protocol/protocol.pdf#concretereddsa)).

Finding: [The signature scheme](https://protocol.penumbra.zone/main/crypto/decaf377-rdsa.html#spendauth-signatures) specifies multiplicative blinding for spend auth signatures, which is inconsistent with other documentation and with the implementation.
* [The Spend circuit constraint](https://protocol.penumbra.zone/main/shielded_pool/action/spend.html#randomized-verification-key-integrity) specifies additive.
* [The implementation is additive](https://rustdoc.penumbra.zone/main/src/decaf377_rdsa/verification_key.rs.html#181-188). ✅

Things to check about the implementation:
* Check that $\tilde{v}$ is in $\mathbb{F}_r$ as specified (even though it is fine to be in $\mathbb{F}_q$ as the commitment does not need to be binding on the randomness).
* `ivk` is generated via Poseidon to get $F_q$ and then reduced `mod r` inside the circuit. The circuit should be doing range checks here.
* c/f the Orchard circuit, where the base field of Pallas fits into the scalar field of Pallas, so no reduction is necessary and `ivk` can be used directly as a scalar.

``ivk = hash_2(from_le_bytes(b"penumbra.derive.ivk"), nk, decaf377_s(ak)) mod r``

This requires that the composition of the hash and the modular reduction is collision-resistant.

* Finding: [Merkle auth path validation](https://protocol.penumbra.zone/main/shielded_pool/action/spend.html#merkle-auth-path-verification): "Only for notes with non-zero values $v \neq 0$, the note is unrooted" should be "Only for notes with zero value ($v = 0$), the note is unrooted". ✅

#### Swap

The [main ZSwap page](https://protocol.penumbra.zone/main/dex.html) (and various other places) should explicitly call out the features that are described there as part of ZSwap, but that are not implemented for V1:
* Amount hiding and front-running protection (via flow encryption).
* Sealed-Bid Batch Swaps.
* Nit: section 9.1 sidebar is named after this feature; rename to "Batch Swaps". ✅

It's confusing that `rseed` in the input to a swap commitment is used to derive identically named `rseed` for the corresponding notes. ✅

Swap commitment:
* Everything except `rseed` is predictable in advance, so `rseed` randomness is important.
* Important because using the first 96 bits of the swap commitment as a nonce. Will get collisions after 2^48 swaps.

Swap encryption:
* The symmetric key for swap encryption is derived from `ovk` and the swap commitment.
* Rationale is that "third parties cannot create swaps for a given recipient, i.e. the user only sends swaps to themselves".
* TODO: Does this present the intended set of capabilities for an `ovk` holder?

* How is the fee balance commitment computed? Where is the blinding factor derived from or conveyed to future-user?
* TODO: Figure this out, probably by looking at the implementation.

* Finding: $B_d$ is not checked to be non-identity in the spec. ✅
* This was already found for SwapClaim by Daira-Emma before the audit and the documentation was fixed; the same applies here.
* TODO: check implementation.

The signs of $cv$ and $cv_f$ are confusing because the convention is different to the Spend and Output circuits. Those circuits used positive-signed values for the commitments, and then had their transaction-relative sign applied to the commitments per the [Action reference](https://protocol.penumbra.zone/main/transactions/actions.html#all-actions). This should be explained more thoroughly.
* For example, it appears from the specification that a transaction containing a Spend (of the fee asset, not the trade assets) and a Swap (locking the fee amount up for future emission in a SwapClaim) will not balance: the Spend contributes $+v_f$, and the Swap contributes $-(-v_f)$, resulting in an imbalance of $2v_f$ instead of a balance of $0$. ✅

Finding about inadequate randomization of $cv$ moved to the Findings section.

On the description of the Swap circuit as "burning" its inputs: you could alternatively describe this as putting the funds that are being "burnt" into a separate pool for outstanding swaps. I.e. a Swap is just an output to a weirdly implemented pool.

* Are there separate commitment trees for the note commitments and swap commitments, or is it a single state commitment tree for all commitment types?
* If the latter, are the commitment types domain-separated in some way when inserted into the tree, or is uniqueness of position the only separator?
* The "State Fragments" section at the bottom of [5.2 Nullifiers](https://protocol.penumbra.zone/main/sct/nullifiers.html#state-fragments) seems to suggest that Penumbra uses a single state tree for all state fragment types.
* Confirmed that Penumbra uses a single state commitment tree and single nullifier set.
* Nullifier uniqueness is preserved because nullifiers for different state fragment types occupy disjoint sets of positions within the state commitment tree.

#### SwapClaim

You need joint collision-resistance of Poseidon with rates 6 (for note commitments) and 7 (for swap commitments). This likely holds but is a tricky property.
* If both used rate 7 then analysis would be simpler, as you would then be relying specifically on the domain separation within a single Poseidon instantiation.

Spec notes:
* "The body of a SwapClaim has four parts" should be "five parts". ✅
* "A balance commitment, which commits to the value balance of the spent note;" this isn't actually a spent note? ✅
* The spec switches between $v$ and $\Delta$ for denoting swap values. ✅
* The details about how the output note `rseed`s are derived is given in the specification for the `Swap` circuit, where it goes unused (as `BatchSwapOutputData` is unknown at that point). Consider moving everything from "The output notes for the `Swap`" down to just before "Invariants" to the `SwapClaim` spec (or to a separate page that specifies the whole swap protocol). ✅

Finding: The value-balancing statements within the `SwapClaim` circuit are not specified. Moved to findings.

The swap's `rseed` is both used directly as the randomness for the swap commitment, and to derive `rseed1` and `rseed2`. This appears to be fine but is ugly.

The $ak \neq 0$ check is not technically necessary (as with Spend) given that additive blinding is used, but it is harmless.

TODO: is it fine to not check `rcm_1` and `rcm_2` in the circuit, given that both of those and the Swap `rseed` are witnessed?
* The argument for why this is fine is likely that violating this only compromises the privacy of the swap claimer. Any adversary that could perform this attack can also just leak the commitment openings directly.

There appears to be out-of-date documentation at https://protocol.penumbra.zone/main/dex/concentrated_liquidity.html (e.g. referring to NFTs for liquidity positions which is not the current design). ✅

#### Delegate and Undelegate

[7.3 Action Reference](https://protocol.penumbra.zone/main/transactions/actions.html#all-actions) describes the existence of this, as does [10.8 Transaction Actions (for Staking and Delegation)](https://protocol.penumbra.zone/main/stake/action.html), but there is no specification for [Delegate](https://protocol.penumbra.zone/main/stake/action/delegate.html) ([implementation](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/component/stake/src/delegate.rs#L9-L27)) or [Undelegate](https://protocol.penumbra.zone/main/stake/action/undelegate.html) ([implementation](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/component/stake/src/undelegate.rs#L10-L27)). We presume that these are fully-public actions, and therefore don't have circuits to review, but the lack of specifications about what they contain and how they interoperate with `UndelegateClaim` makes review of the latter more tricky.

Finding: [10.4 Delegation](https://protocol.penumbra.zone/main/stake/delegation.html) describes how delegation works in terms of Flow Encryption, which is not part of Penumbra V1.

#### UndelegateClaim

Spec findings:
* $v_e$ is documented as the expected balance output from `ConvertCircuit`, but it is specified as a partial commitment to the value balance of the circuit. Fix this by instead specifying $v_e = p \cdot v_i$, and then either use a new intermediate variable name for the partial commitment, or simply defined $cv = [-v_i] G_{v_i} + [v_e] G_{v_t} + [\tilde{v}] G_\tilde{v}$.
* We note that the base for the target asset is denoted $G_{v_t}$, so it might instead be intended that $v_t$ is the expected balance computed from the public conversion rate and the input amount. In that case, specify that, and rename $v_e$ to something else. ✅

#### DelegatorVote

This circuit could be replaced by the Spend circuit:
* The Start Position Verification check can be emulated by having clients provide a Merkle path to the root of the SCT at `start_pos`.
* The opening $(v, 0)$ of $cv$ would be revealed.
* This already appears to be the case for DelegatorVote: the body of a DelegatorVote includes the value of the staked note, but the DelegatorVote circuit takes the value as a private input and a balance commitment as a public input.
* Alternatively, the DelegatorVote circuit could just take the note value as a public input, and directly use it in Note Commitment Integrity, removing Balance Commitment Integrity check entirely.
* This allows voting using a dummy note, but that can be excluded by requiring $v \neq 0$ as a consensus rule (and in any case, dummy notes contribute zero voting power by definition).

### Misc spec notes

**Nit:** https://protocol.penumbra.zone/main/assets.html has a broken link to Cosmos specification document ADR001. ✅

### Implementation

#### Component types

- `AmountVar`
- [`amount::is_bit_constrained`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/num/src/amount.rs#L106-L129) almost exactly duplicates [`fixpoint::bit_constrain`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/num/src/fixpoint.rs#L716-L737) (used in `AmountVar::new_variable`), except that the latter uses a sentinel of 0 and the former uses a sentinel of 1 (as well as their differing return types, but that could be factored out).
- [`impl From<U128x128Var> for AmountVar`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/num/src/amount.rs#L528-L537) implements truncation (discarding the lower limbs containing the fixed-point decimal component). Noted for later when reviewing `SwapClaim`.

- Finding: [Value Generators](https://protocol.penumbra.zone/main/assets.html#value-generators) spec bug: `from_le_bytes(b"penumbra.value.generator")` should be `from_le_bytes(blake2b(b"penumbra.value.generator"))` to match [`AssetIdVar::value_generator`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/asset/src/asset/r1cs.rs#L47-L55). ✅
- [`pk_d` and `ck_d` are both specified as decaf377 elements in the general protocol](https://protocol.penumbra.zone/main/addresses_keys/addresses.html#addresses), but `ck_d` is only witnessed as an `Fq` element in the circuit (see e.g. [`Output` circuit statement](https://protocol.penumbra.zone/main/shielded_pool/action/output.html#output-zk-snark-statements)). This isn't itself necessarily a problem (if the clue key only needs to be committed to), but it leads to several findings:
- Finding: [`Address::to_field_elements`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/keys/src/address/r1cs.rs#L83) will return a different number of elements depending on whether `Address::clue_key` is a valid `Fq` element, due to [`impl IntoIterator for Result` returning one element for `Ok(_)` and no elements for `Err(_)`](https://doc.rust-lang.org/stable/std/result/enum.Result.html#method.into_iter-2).
- This is reachable via `Address::from_components`, due to `fmd::ClueKey` being a newtype wrapper with public internals (which cannot enforce the type constraint that it is a valid `Fq` element).
- Finding: [`AddressVar::new_variable` reads the clue key via `Fq::from_le_bytes_mod_order`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/keys/src/address/r1cs.rs#L58-L62), accepting any clue key byte encoding and reducing it into the field (which either means it is breaking the decaf377 encoding, or accepting non-canonical encodings of decaf377 elements), while [`Address::to_field_elements`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/keys/src/address/r1cs.rs#L83) uses `Fq::from_bytes` and expects a canonical `Fq` element encoding. The circuit should either allow non-canonical encodings of `ck_d` or reject them, not both.

- Possible inefficiencies in `BalanceVar::commit`:
- It is [deriving the value generator for each contribution separately](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/asset/src/balance.rs#L355). Could instead derive once per asset ID and then constrain the equivalent `asset_id` variables to be equal.
- It appears to be [doing scalar mul with all bits of `Fq`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/asset/src/balance.rs#L359-L360) (and assigning new bit variables for it), not just the 128 bits the value is constrained to (which are [discarded in `AmountVar::new_variable`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/num/src/amount.rs#L203-L204))
- Compare to `tct::r1cs::PositionVar` which stores its bit decomposition.
- Also noticed a comment in this method "It seems like the AddAssign impl here doesn't match the Add impl"; has this been upstreamed to Arkworks?

#### `OutputCircuit::generate_constraints`

Finding: Inconsistencies between the circuit specification and implementation:
- Impl negates the value of the note; spec does not.
- The spec instead indicates that [the negation occurs outside the circuit](https://protocol.penumbra.zone/main/transactions/actions.html#all-actions).
- Spec defines $\tilde{v}$ as an element of $F_r$; Impl witnesses it as a 256-bit vector and does not range constrain it.
- Should be fine, but circuit could be slightly more efficient if only used the 251 bit space of $F_r$.

Nits:
- `OutputCircuit` docstring says `v` is 64 bits, should be 128.

#### `SpendCircuit::generate_constraints`

Finding: Inconsistencies between the circuit specification and implementation:
- Spec defines $\tilde{v}$ and spend auth randomizer $\alpha$ as elements of $F_r$; Impl witnesses each of them as a 256-bit vector and does not range constrain them.
- Same notes as for $F_r$s in Output.
- Cannot find specification for SCT hashing as used in Merkle auth path validation. None of the circuit specs describe it, and neither do [5 State Commitment Tree](https://protocol.penumbra.zone/main/sct.html) or [5.1 Tiered Commitment Tree](https://protocol.penumbra.zone/main/sct/tct.html). The domain separator `penumbra.tct` appears nowhere in the spec.
- No circuit specification for `WhichWayVar` muxer (impl looks correct).

Weirdness:
- `IncomingViewingKeyVar::derive` has the following implicit constraints: `ivk_mod_q = mod_r * a + ivk_mod_r`, `a <= 4`, `ivk_mod_r < r`. However, $4 \cdot r < q < 4 \cdot r + (r - 1)$, so there exists a range of `ivk_mod_q` values and corresponding `a` where `ivk_mod_q < r`, `a <= 4`, `ivk_mod_r < r`, `ivk_mod_q != ivk_mod_r` and thus the prover can choose $a = 0$ or $a \neq 0$ to get two different `ivk`s for the same FVK.
- We can't think of an immediate consequence of there being two valid `ivk`s for a given full viewing key; the note being spent is still bound to only one of them. But it's weird.
- In the Orchard circuit, we by design have multiple ivks per fvk (using a witnessed `rivk` to generate them). But this is done by effectively producing a different FVK; inside the circuit it is still a 1:1 mapping from FVK to IVK.
- Example canonicity checks in the Orchard circuit: https://zcash.github.io/orchard/design/circuit/commit-ivk.html#canonicity-checks (variant of an approach originally from ia.cr/2012/598 Appendix C.1).
- In the Halo 2 var-base scalar mul circuit we have an overflow check that might be useful: https://zcash.github.io/halo2/design/gadgets/ecc/var-base-scalar-mul.html#overflow-check
- Alternatively you could constraint key tree derivation to require the output of `hash_2(ds, (ak, nk))` to be in range for $F_r$, and then only need the constraint `ivk_mod_q < r` in circuit.

Nits:
- `MerkleAuthPathVar::new_variable` impl is confusing; could simplify with modern Rust array methods.
- `ValueVar::commit` is mostly duplicative (modulo being for a single value and not accounting for sign) of `BalanceVar::commit` (and has the same inefficiencies).
- `WhichWayVar::at` takes `height: u8` as a 1-indexed height; can panic during array access if zero-indexed anywhere.

Perf notes:
- Circuit constrains `ivk` to be $F_r$ in `IncomingViewingKeyVar::derive`, but then `IncomingViewingKeyVar::diversified_public` does scalar mul with $F_q$-width bits.

#### `SwapCircuit::generate_constraints`

Finding: Inconsistencies between the circuit specification and implementation:
- Spec defines $\widetilde{v_f}$ as element of $F_r$; Impl witnesses it as a 256-bit vector and does not range constrain it.
- Same notes as for $F_r$s in Output.

Perf notes:
- Circuit uses `BalanceVar::commit` with a constant zero blinding factor to constrain `balance_1_commit` and `balance_2_commit`. This adds an unnecessary full-width fixed-base scalar mul into the circuit (although with both base and scalar constant, so perhaps the arkworks backend is optimising this out?). In any case, it would be more straightforward to use `let transparent_balance_commitment = (balance_1 + balance_2).commit(transparent_blinding_var)?;` (and this would be closer to what the circuit should be doing after addressing the earlier spec finding).

#### `SwapClaimCircuit::generate_constraints`

Finding: Inconsistencies between the circuit specification and implementation:
- Spec says that `rseed` is "interpreted as $F_q$", which is AFAIR unique language compared to the rest of the spec. Impl specifically does `rseed mod q`, which is _probably_ fine (reducing uniform 256-bit value into a 253-bit space should still be sufficiently hiding for the purposes of a Poseidon commit).
- Spec says that $ak$ and $pk_d$ are constrained to be non-zero / non-identity. Impl doesn't appear to include these constraints.
- TODO: Search further for them.
- This _might_ still be fine without these; the absolutely required constraint is that $B_d \neq 0$ (or else the output note created in the `SwapClaim` could be spent by any `ivk`), and that is enforced by `AddressVar::new_variable`.

Sort-of-Finding: Due to the weirdness observed in `IncomingViewingKeyVar::derive` above, any holder of the wallet FVK ~~that observes a `Swap` being fulfilled,~~ can produce a **`Swap` and subsequent** `SwapClaim` that sends the outputs of the swap to an address for the "shadow `ivk`" that the user's wallet is not actively scanning.
- This is only a temporary loss-of-funds, as the user's wallet could scan the shadow `ivk` to recover the funds, but it is less than ideal.
- Fix for this is to either constrain that only one `ivk` can be derived from a given `(ak, nk)` pair, or commit to `ivk` in `SwapPlaintext` and check it in the circuit.
- EDIT: Downgraded the finding, because the `SwapPlaintext` commits to the output address, which means only the `Swap` creator can do this, not the `SwapClaim` creator.

Other notes:
- `TradingPairVar::new_variable_unchecked` notes that canonical ordering is not constrained (and thus a non-canonically-ordered `SwapPlaintext` could be produced). However, as far as we can tell, it is implicitly constrained via the Trading Pair Consistency Check in `SwapClaim`, as the BSOD's publicly-witnessed trading pair is presumably canonically ordered, and any trader that produced a non-canonical `Swap` would become unable to claim the trade outputs in `SwapClaim`.
- This observation is separate from the comment in `SwapPlaintextVar::new_variable` about a malicious prover changing the trading pair order between `Swap` and `SwapClaim`; we agree that the swap commitment prevents this.

`BatchSwapOutputDataVar` review:
- `BatchSwapOutputDataVar::pro_rata_outputs` explicitly calls `U128x128Var::round_down` (explicitly truncating) before calling `AmountVar::from(U128x128Var)` (which implicitly truncates). For reviewability, it would be nice if `From<U128x128Var> for AmountVar` either asserted that it is already rounded down, or instead was `TryFrom<U128x128Var> for AmountVar` (which could then unwrap inside `_::pro_rata_outputs` due to the now-obvious prior truncation
- Then we noticed that `U128x128Var::round_down_to_amount` exists; use that instead of `.round_down().into()`.
- `U128x128Var::checked_mul`:
- `t1_bits` is constrained to 130 bits; should be 129 bits (and the impl treats it as 129 bits for constraining `t2`).
- `U128x128Var::enforce_cmp`:
- Comment: [in the constraint building for `gt` and `lt`](https://github.com/penumbra-zone/penumbra/blob/0c98304eaafac523d2ffefeb0ef0e2d05dcc77b8/crates/core/num/src/fixpoint.rs#L445-L452), `gt` accumulates the current bit pair before `lt`. Due to variable shadowing, `gt`'s constraint references the previous `lt` constraint (excluding the current bit pair), but `lt`'s constraint references the current `gt` constraint (including the current bit pair).
- We have analysed this and determined that the shadowing has no effect on the correctness.

Perf notes:
- `U128x128Var::new_variable` defines `hi_128_var` and `lo_128_var`, and constrains them to equal the boolean recomposition of the 128 bits of each half that were obtained from witnessing the four limbs. This seems unnecessary, given that `hi_128_var` and `lo_128_var` are then discarded.
- Maybe arkworks `Boolean::<Fq>::le_bits_to_fp_var` does not actually enforce a boolean decomposition constraint unless its output is used? If that's the case, document it here.

#### Misc notes

- The use of newtypes with public internals (e.g. [`pub struct StateCommitment(pub Fq)`](https://github.com/penumbra-zone/penumbra/blob/7611ac3b4a30fd60f99483881c24ed3787083ad1/crates/crypto/tct/src/commitment.rs#L8)) hinders type safety review, as we cannot assume that these types maintain their invariants.
- The `ivk` and `account_id` domain separators use `Fq::from_le_bytes_mod_order(string)` (i.e. directly interpreting the domain separator string as a field element encoding), while many other instances of domain separators use `Fq::from_le_bytes_mod_order(BLAKE2b(string))`.
- `AmountVar::quo_rem` appears to be completely unused. The only reference to it is in `U128x128Var::checked_div`, which is documented as "similar to `AmountVar::quo_rem`".

---

## Time log

### 2024-05-13

* Daira-Emma 1 hour: write up and comment on curve and primitive choices. Comment on the necessity of re-running the phase 2 setup if a circuit flaw is found. Recommend considering a universal-setup proof system in a future routine upgrade. Also note that balance preservation and spend authorization are subject to quantum attacks.

### 2024-05-17

* Daira-Emma 3 hours + str4d 3 hours + Sean 2 hours: review Spend and Output statements, along with everything necessary to understand them.
* Daira-Emma 2.5 hours + str4d 2.5 hours + Sean 1 hour: review Swap and (most of the) SwapClaim statements, along with everything necessary to understand them. This included the finding about insufficient randomization of $cv$.

### 2024-05-20

* Daira-Emma 1.5 hours + str4d 1.5 hours + Sean 1 hour: review (more of) and (partially) UndelegateClaim. This included the finding about the incomplete SwapClaim specification, and sufficient review to decide on the finding about the documentation clarity issues for the V1 protocol.
* Daira-Emma 1 hour + str4d 1 hour + Sean 1 hour: review UndelegateClaim and DelegatorVote.
* Daira-Emma 1 hour: Confirm BLS12-377 and decaf377 estimated classical security against discrete log attacks, and tidy up some of the notes. Also move "Groth16 requires circuit-specific setup" to Findings.

Total so far: 23 hours.

### 2024-05-22

* str4d 1.25 hours: review most of `Output` circuit implementation, diving into `NoteVar::new_variable` and its sub-components.
* str4d 1.75 hours: review rest of `Output` circuit implementation; review `Spend` circuit implementation, diving into its sub-components.
* str4d 0.5 hours + Sean 0.5 hours: review ivk derivation as used in `Spend` circuit
* str4d 1.5 hours: review `Swap`, and `SwapClaim` except for Output Amounts Integrity and Output Note Commitment Integrity checks.
* str4d 2.5 hours: review `SwapClaim` Output Amounts Integrity and Output Note Commitment Integrity checks.

### 2024-05-31

* Daira-Emma 1 hour: Clean up document and copy to a new doc for publication.

Total: 32 hours.