Our understanding of the scope of this audit is as follows:
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.r1cs modules of decaf377 and poseidon377 as noted above); or circuit-building infrastructure are not in scope.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: 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, 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 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:
The needed design change would impact the 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.
SwapClaim circuit specification is incompleteSeverity: 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:
Recommendations:
B1. Specify the Output Amounts Integrity Check statement.
B2. Specify the statements that check the balance commitments.
B3. Clarify the Fee Consistency Check.
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:
Recommendations:
C1. Specify the remaining unspecified parts of the protocol.
C2. Remove blank pages for, and references to, documentation that is no longer relevant.
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.
dtk_d in the set to the same user, so empirically knows that the detection keys are linked.ck_d appears in each address and is derived solely from dtk_d.The protocol documentation currently states in 1.3 Addresses and Keys only that diversified addresses are "publicly unlinkable", which provides insufficient detail. 4.3 Addresses and 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.
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:
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.
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.
These are collected from the auditing notes below.
from_le_bytes(b"penumbra.value.generator") should be from_le_bytes(blake2b(b"penumbra.value.generator")) to match AssetIdVar::value_generator.hash_6 to derive the note commitment including \(ck_d\), while the note commitment specification uses hash_5 and doesn't commit to \(ck_d\).note_commitment should be named swap_commitment.rseed in the input to a swap commitment is used to derive identically named rseed for the corresponding notes.rseeds 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).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}\).Please also see the findings in the Implementation section below (to avoid duplication we will not repeat them here).
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.
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.
BLS12-377 has an estimated security level of \(2^{126}\) against STNFS attacks, according to accompanying data for the "tnfs" library developed by the authors of [GS2021].
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 and also the Standard Curve Database entry for 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 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].
A security level of at least \(2^{124.9}\) makes discrete log attacks conservatively infeasible using classical (non-quantum) computing resources.
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.
Check everything is properly domain-separated (looks to be).
Poseidon-based
note_commitment should be named swap_commitment. ✅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. 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). Detection keys are per diversified address.
Address replacement attacks were considered out of scope.
[esk] pk_d), not the KDF output used to encrypt the note plaintext.
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.
Nullifiers – 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 of the Zcash protocol spec.
hash_6 to derive the note commitment including \(ck_d\), while the note commitment specification uses hash_5 and doesn't commit to \(ck_d\). ✅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 (like RedDSA).
Finding: The signature scheme specifies multiplicative blinding for spend auth signatures, which is inconsistent with other documentation and with the implementation.
Things to check about the implementation:
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.
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.
The main ZSwap page (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:
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:
rseed is predictable in advance, so rseed randomness is important.
Swap encryption:
The symmetric key for swap encryption is derived from ovk and the swap commitment.
ovk holder?How is the fee balance commitment computed? Where is the blinding factor derived from or conveyed to future-user?
Finding: \(B_d\) is not checked to be non-identity in the spec. ✅
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. This should be explained more thoroughly.
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.
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.
Spec notes:
rseeds 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?
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). ✅
7.3 Action Reference describes the existence of this, as does 10.8 Transaction Actions (for Staking and Delegation), but there is no specification for Delegate (implementation) or Undelegate (implementation). 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 describes how delegation works in terms of Flow Encryption, which is not part of Penumbra V1.
Spec findings:
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}\).
This circuit could be replaced by the Spend circuit:
start_pos.Nit: https://protocol.penumbra.zone/main/assets.html has a broken link to Cosmos specification document ADR001. ✅
AmountVar
amount::is_bit_constrained almost exactly duplicates fixpoint::bit_constrain (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 implements truncation (discarding the lower limbs containing the fixed-point decimal component). Noted for later when reviewing SwapClaim.Finding: 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. ✅
pk_d and ck_d are both specified as decaf377 elements in the general protocol, but ck_d is only witnessed as an Fq element in the circuit (see e.g. Output circuit statement). This isn't itself necessarily a problem (if the clue key only needs to be committed to), but it leads to several findings:
Address::to_field_elements 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(_).
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).AddressVar::new_variable reads the clue key via Fq::from_le_bytes_mod_order, 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 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:
asset_id variables to be equal.Fq (and assigning new bit variables for it), not just the 128 bits the value is constrained to (which are discarded in AmountVar::new_variable)
tct::r1cs::PositionVar which stores its bit decomposition.OutputCircuit::generate_constraintsFinding: Inconsistencies between the circuit specification and implementation:
Nits:
OutputCircuit docstring says v is 64 bits, should be 128.SpendCircuit::generate_constraintsFinding: Inconsistencies between the circuit specification and implementation:
penumbra.tct appears nowhere in the spec.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 ivks for the same FVK.
ivks for a given full viewing key; the note being spent is still bound to only one of them. But it's weird.
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.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:
ivk to be \(F_r\) in IncomingViewingKeyVar::derive, but then IncomingViewingKeyVar::diversified_public does scalar mul with \(F_q\)-width bits.SwapCircuit::generate_constraintsFinding: Inconsistencies between the circuit specification and implementation:
Perf notes:
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_constraintsFinding: Inconsistencies between the circuit specification and implementation:
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).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 can produce a Swap being fulfilled,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.
ivk to recover the funds, but it is less than ideal.ivk can be derived from a given (ak, nk) pair, or commit to ivk in SwapPlaintext and check it in the circuit.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.
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
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:
gt and lt, 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).
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.
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.pub struct StateCommitment(pub Fq)) hinders type safety review, as we cannot assume that these types maintain their invariants.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".Total so far: 23 hours.
Output circuit implementation, diving into NoteVar::new_variable and its sub-components.Output circuit implementation; review Spend circuit implementation, diving into its sub-components.Spend circuitSwap, and SwapClaim except for Output Amounts Integrity and Output Note Commitment Integrity checks.SwapClaim Output Amounts Integrity and Output Note Commitment Integrity checks.Total: 32 hours.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe