Audit of Renegade's Circuits and Smart Contracts
February 26, 2024

Description. A wallet update is an operation that encompasses a number of flows: deposit, withdraw, create or update orders, etc. A user performs a wallet update by:

1. consuming an existing wallet
2. updating their wallet
3. signing the new wallet

The first two steps are done in a private way via the use of zero-knowledge proofs. The last step is done out of circuit in the smart contract's logic. If the wallet update triggers a transfer of tokens (a withdrawal or deposit) then the smart contract handles some separate logic to process the transfer.

More specifically, the permit2 contract and its permitTransferFrom function are used to perform the transfer of on-chain funds in a user-friendly way.

The transfer logic of the Renegade smart contract is described here in pseudo-code:

def execute_external_transfer(old_pk_root, transfer, transfer_aux_data):
    if transfer.is_withdrawal:
        # either the 
        assert(valid_sig(
            pub=old_pk_root, 
            msg=transfer, 
            sig=transfer_aux_data.transfer_signature)
            )
        transfer.mint.transfer_call(transfer.account_addr, transfer.amount)
    else: # deposit flow
       permit = {
          "permitted": [transfer.amount, transfer.mint],
          "nonce": transfer_aux_data.permit_nonce,
          "deadline": transfer_aux_data.permit_deadline,
       }
       signature_transfer_details = {
          "to": THIS_CONTRACT_ADDRESS,
          "requested_amount": transfer.amount
       }
       CONTRACT_PERMIT2_ADDRESS.permit_transfer_from_call(
            permit, 
            signature_transfer_details,
            transfer.account_addr, 
            transfer_aux_data.signature
        )

Note that transfer_aux_data is not authenticated by the proof. This means that two things can happen:

1. the auxiliary data can be reused in a different context by a frontrunning transaction or
2. someone can reuse the rest of a transaction with a different transfer_aux_data

The second attack does not work because the transfer_aux_data is basically a signature, and changing the data being signed (or the signer) will render the signature invalid. This signature passed as auxiliary data covers the token being transferred and its amount, the address spending it (the Renegade contract), as well as a nonce and a deadline.

As such, the auxiliary data is strongly tied to the transfer authenticated (passed as public input) by the proof, but not to any other user intent or the proof itself.

This makes the first attack possible. To perform such an attack, a malicious actor Bob could follow these steps:

1. Bob observes Alice trying to deposit some amount of token via an update_wallet transaction (via their mempool).
2. Bob creates a similar update_wallet transaction to deposit the same amount of tokens but for their own wallet, using Alice's transfer_aux_data (so that Alice funds Bob's wallet)
3. Now Bob is attempting to frontrun Alice's transaction and get theirs processed first (for example, by using a higher gas price).

Recommendation. The Renegade contract should use the permit2's permitWitnessTransferFrom function in place of permitTransferFrom, as it allows authenticating additional data as part of approving a transfer.

We recommend adding the proof's bytes to the witness field of the permitWitnessTransferFrom function, to strongly tie the transfer authorization to the user proof (which encapsulates the whole intent).

Alternatively, the pk_root of the recipient could be used instead, as it would strongly tie both ends of the transfer.

Description. Renegade implements a number of circuit gadgets to perform fixed-point arithmetic operations. One of these internal gadgets (used in FixedPointGadget::floor) implements the euclidian division in the field arithmetic of the circuit field. That is, it calculates the values $r$ and $q$ such that:

As of now, the implementation is not sound as it does not properly constrain the quotient variable (q_var) which could wrap around when multiplied with the divisor.

For example, an attacker might want to find $q'$ and $r'$ such that $a = b \cdot q' + r'$ and $q' \neq q$ and/or $r' \neq r$. This can be done by solving the following equation (obtained by subtracting the two equations):

If we fix $r'$, for example, we can solve for $q'$. That is, as long as $r'$ is smaller than the divisor $b$, as it is constrained in the circuit:

// Constraint r < b
LessThanGadget::<D>::constrain_less_than(r_var, b, cs)?;

Note that we could not find a way to exploit this in practice, but the code can still become an issue in the future as it is easy to misuse.

Reproduction steps. The following sagemath code solves for a small example $a=563$ and $b=25$:

# define BN254 scalar field
F = GF(21888242871839275222246405745257275088548364400416034343698204186575808495617)

# setup a small problem
a = 563
b = 25
q = a // b # 22
r = a % b # 13
assert(a == q * b + r) # 563 = 25 * 22 + 13

# let's set r' = 10
r2 = 10
q2 = F((b * q + r - r2)/b) # 7879767433862139080008706068292619031877411184149772363731353507167291058400
assert(q2 != q)
assert(r2 != r)
assert(r2 < b)
assert(a == b * q2 + r2)

One can test the attack in Rust by modifying the behavior of the DivRemGadget::div_rem function as follows:

pub struct DivRemGadget<const D: usize> {}
impl<const D: usize> DivRemGadget<D> {
    /// Return (q, r) such that a = bq + r and r < b
    pub fn div_rem(
        a: Variable,
        b: Variable,
        cs: &mut PlonkCircuit,
    ) -> Result<(Variable, Variable), CircuitError> {
        let a_bigint = scalar_to_biguint(&a.eval(cs));
        let b_bigint = scalar_to_biguint(&b.eval(cs));

        // Compute the divrem outside of the circuit
-        let (q, r) = a_bigint.div_rem(&b_bigint);
+        let attack_a: BigUint = 563u64.into();
+        let attack_b: BigUint = 25u64.into();
+        let (q, r) = if a_bigint == attack_a && b_bigint == attack_b {
+            let q_str =
+                "14008475437977136142237699676964656056670953216266261979966850679408517437217";
+            let q = q_str.parse().unwrap();
+            let r = 10u64.into();
+            (q, r)
+        } else {
+            a_bigint.div_rem(&b_bigint)
+        };

        let q_var = biguint_to_scalar(&q).create_witness(cs);
        let r_var = biguint_to_scalar(&r).create_witness(cs);

        // Constrain a == bq + r
        let one_var = cs.one();
        let one = ScalarField::one();
        cs.mul_add_gate(&[b, q_var, r_var, one_var, a], &[one, one])?;

        // Constraint r < b
        LessThanGadget::<D>::constrain_less_than(r_var, b, cs)?;

        Ok((q_var, r_var))
    }
}

And then run the following test:

#[test]
fn test_div_rem_attack() {
    let aa = BigUint::from(563u32);
    let bb = BigUint::from(25u32);

    let (expected_q, expected_r) = aa.div_rem(&bb);
    let expected_q = biguint_to_scalar(&expected_q);
    let expected_r = biguint_to_scalar(&expected_r);

    // Build a constraint system
    let mut cs = PlonkCircuit::new_turbo_plonk();
    let expected_q_var = expected_q.create_public_var(&mut cs);
    let expected_r_var = expected_r.create_public_var(&mut cs);

    // Allocate the inputs in the constraint system
    let dividend_var = biguint_to_scalar(&aa).create_witness(&mut cs);
    let divisor_var = biguint_to_scalar(&bb).create_witness(&mut cs);

    let (q_res, r_res) =
        DivRemGadget::<32 /* bitlength */>::div_rem(dividend_var, divisor_var, &mut cs)
            .unwrap();

    let q_eq = cs.is_equal(expected_q_var, q_res).unwrap();
    use circuit_types::traits::CircuitVarType;
    assert!(!q_eq.eval(&cs));
    let r_eq = cs.is_equal(expected_r_var, r_res).unwrap();
    assert!(!r_eq.eval(&cs));

    assert!(cs.check_circuit_satisfiability(&[expected_q.inner(), expected_r.inner()]).is_ok())
}

Recommendation. We recommend constraining the size of $q$ such that the equation being constrained cannot wrap around. As $a$ and $b$ are both assumed to be 32-bit values, $q$ could easily be constrained to be 32-bit as well.

Description. Renegade uses the Poseidon hash function in multiple places in its circuit logic. The Poseidon hash function uses the "sponge" paradigm, which is to absorb data, and then squeeze as many times as you want to output different random values. This kind of construction has been called XOF for eXtended Output Functions in the past.

Unfortunately, the current implementation produces the same value when squeezed multiple times. While the current code never squeezes more than once, which does not lead to vulnerabilities in the protocol, we highly recommend fixing the issue as it is not clear how the code will be used in the future.

The problem is in this part of the code:

impl PoseidonHashGadget {
    /// Squeeze an element from the sponge and return its representation in the
    /// constraint system
    pub fn squeeze<C: Circuit<ScalarField>>(
        &mut self,
        cs: &mut C,
    ) -> Result<Variable, CircuitError> {
        // Once we exit the absorb state, ensure that the digest state is permuted
        // before squeezing
        if !self.in_squeeze_state || self.next_index == RATE {
            self.permute(cs)?;
            self.next_index = 0;
            self.in_squeeze_state = true;
        }

        Ok(self.state[CAPACITY + self.next_index])
    }

As one can see, the next_index is never incremented, and so it always points to the same value to squeeze in the state.

Recommendation. Make sure that the squeeze function properly increments the next_index variable:

+ let res = self.state[CAPACITY + self.next_index];
+ self.next_index += 1;
- Ok(self.state[CAPACITY + self.next_index])
+ Ok(res)

Description. Renegade uses different pseudo-random number generators (PRNGs) in its protocol to deterministically produce randomness.

PRNGs have different security properties, including backward security which dictates that one should not be able to predict future outputs based on the state of a PRNG. This property is useful in case the state of the PRNG state is leaked.

We found examples of non-backward secure PRNGs, which not only leak their state when producing random values, but also leak all future states. That being said, we could not find a way to exploit this particular issue in the protocol.

The problem resides in renegade/circuits/src/zk_gadgets/poseidon.rs:

pub struct PoseidonCSPRNGGadget;
impl PoseidonCSPRNGGadget {
    /// Samples values from a chained Poseidon hash CSPRNG, seeded with the
    /// given input
    pub fn sample<C: Circuit<ScalarField>>(
        mut seed: Variable,
        num_vals: usize,
        cs: &mut C,
    ) -> Result<Vec<Variable>, CircuitError> {
        let mut values = Vec::with_capacity(num_vals);

        // Chained hash of the seed value
        let mut hasher = PoseidonHashGadget::new(cs.zero() /* zero_var */);
        for _ in 0..num_vals {
            // Absorb the seed and then squeeze the next element
            hasher.absorb(seed, cs)?;
            seed = hasher.squeeze(cs)?;

            values.push(seed);

            // Reset the hasher state; we want the CSPRNG chain to be stateless, this
            // includes the internal state of the Poseidon sponge
            hasher.reset_state(cs);
        }

        Ok(values)
    }
}

As one can see, the squeezed value is used as both the random output and the seed for the next iteration of the PRNG. This means that learning one of the random values leaks the state, as well as future states.

This problem is mirrored in renegade/renegade-crypto/src/hash.rs:

/// Compute a chained Poseidon hash of the given length from the given seed
    pub fn evaluate_hash_chain(seed: Scalar, length: usize) -> Vec<Scalar> {
        let mut seed = seed.inner();
        let mut res = Vec::with_capacity(length);

        for _ in 0..length {
            // Create a new hasher to reset the internal state
            let mut hasher = Poseidon2Sponge::new();
            seed = hasher.hash(&[seed]);

            res.push(Scalar::new(seed));
        }

        res
    }

Description. At the lower layer of Renegade lies a Zcash-like shielded pool on which the protocol is built. This Zcash-like shielded pool is a Merkle tree that stores commitments to the different user wallets and allows private retrieval and use of these wallets.

The way the shielded pool works is that before any wallet operations, users must prove in zero-knowledge proofs that they know the path to a wallet in a historical snapshot of that Merkle tree, and that the wallet hasn't been consumed before by revealing a unique value verifiably derived from the wallet itself, but hiding which wallet it was derived from.

Each time a wallet is used, it is consumed in this way and a new wallet along with a new derived commitment is produced and inserted in the tree.

Currently, the Merkle tree contract does not check if a commitment has already been added before adding it to the Merkle tree.

There's a few annoying edge cases that might arise from that. First, a user might mistakenly produce two wallets that converge to the same active commitments. This would be problematic as consuming one of the wallets would then void the other, which would cause a loss of funds.

A relayer could also produce a wallet with the same content as one of their user's wallets (and thus the same commitment), but doing that seems to only be a problem for the relayer (as they would need to match the pk_root field to obtain the same commitment, which would effectively transfer their funds to the targeted user).

While these two scenarios seem unlikely or benign, they appear as strange enough edge cases to warrant preventing this behavior.

Recommendation. Keep track of all commitments added previously, for example, by mirroring the way the Renegade smart contracts already keep track of past Merkle roots. In addition, ensure that a new commitment was not previously added before adding it.

Description. Renegade uses proof linking to bind different (but related) Plonk proofs together into a single proof bundle. This means, there's a need to prove that some witness variables have exactly the same values between two linked proofs (as described in Proof Linking).

The verifier challenge $\eta$ is generated using Poseidon hash from the proof linking statement, which consists of commitments to wire polynomials $[a]_1$ and $[b]_1$ and commitment to the linking quotient polynomial $[q]_1$.

The issue is: to verify the linking proof, the verifier computes the value of $Z_S(\eta)$, and the input data for this computation (the LinkingVerificationKey) is not absorbed into the hash to compute $\eta$.

let LinkingVerificationKey {
    link_group_generator,
    link_group_offset,
    link_group_size,
} = linking_vkey;

// TRUNCATED

let mut transcript = Transcript::<H>::new();
let eta = transcript
    .compute_linking_proof_challenge(
        wire_poly_comms.0,
        wire_poly_comms.1,
        linking_quotient_poly_comm,
    )
    .map_err(|_| VerifierError::ScalarConversion) ?;

With fixed LinkingVerificationKey, this should not be a problem: the variable parts (the "statement") are all bound when computing $\eta$.

Generally speaking, verification key, as well as the full statement, should always be absorbed when computing Fiat-Shamir challenges. Not doing so is known to have lead to vulnerabilities in the past (see https://eprint.iacr.org/2023/691).

Was LinkingVerificationKey not fixed (and controlled by the attacker), an attack would be easy to construct: make link_group_size == 0. Proof and verification would succeed without any witness elements being necessarily equal.

Recommendation. Absorb the entire LinkingVerificationKey, as well as wire_poly_comms.0, wire_poly_comms.1, linking_quotient_poly_comm, to compute the challenge eta.

Description. In several places in the codebase, all fields contained in a struct must be used or checked. For example, when verifying a state transition between a wallet and its updated counterpart, all untouched fields must remain the same.

fn verify_sender_state_transition(
    send_index: Variable,
    is_protocol_fee: BoolVar,
    old_wallet: &WalletVar<MAX_BALANCES, MAX_ORDERS>,
    new_wallet: &WalletVar<MAX_BALANCES, MAX_ORDERS>,
    cs: &mut PlonkCircuit,
) -> Result<(), CircuitError> {
    // All orders should be the same
    EqGadget::constrain_eq(&old_wallet.orders, &new_wallet.orders, cs)?;

    // The keys, match fee, and managing cluster should be the same
    EqGadget::constrain_eq(&old_wallet.keys, &new_wallet.keys, cs)?;
    EqGadget::constrain_eq(&old_wallet.match_fee, &new_wallet.match_fee, cs)?;
    EqGadget::constrain_eq(&old_wallet.managing_cluster, &new_wallet.managing_cluster, cs)?;

    // TRUNCATED...

    for (old_bal, new_bal) in old_wallet.balances.iter().zip(new_wallet.balances.iter()) {
        // TRUNCATED...
        EqGadget::constrain_eq(&old_bal.mint, &new_bal.mint, cs)?;
        EqGadget::constrain_eq(&old_bal.amount, &new_bal.amount, cs)?;

During the audit, we had to manually check this to make sure that every field was properly constrained. This is a tedious process and could lead to mistakes.

Fortunately, Rust provides a simple way to help by using the destructuring syntax. Destructing an object allows all the fields to enter the scope, and if a field is unused the compiler will throw a warning visible to the developer.

For example, the above code could be rewritten as:

fn verify_sender_state_transition(
    send_index: Variable,
    is_protocol_fee: BoolVar,
    old_wallet: &WalletVar<MAX_BALANCES, MAX_ORDERS>,
    new_wallet: &WalletVar<MAX_BALANCES, MAX_ORDERS>,
    cs: &mut PlonkCircuit,
) -> Result<(), CircuitError> {
    let WalletVar {
        balances: old_balances,
        orders: old_orders,
        keys: old_keys,
        match_fee: old_match_fee,
        managing_cluster: old_managing_cluster,
        blinder: _,
    } = old_wallet;
    let WalletVar {
        balances: new_balances,
        orders: new_orders,
        keys: new_keys,
        match_fee: new_match_fee,
        managing_cluster: new_managing_cluster,
        blinder: _,
    } = new_wallet;
    // All orders should be the same
    EqGadget::constrain_eq(old_orders, new_orders, cs)?;

    // The keys, match fee, and managing cluster should be the same
    EqGadget::constrain_eq(old_keys, new_keys, cs)?;
    EqGadget::constrain_eq(old_match_fee, new_match_fee, cs)?;
    EqGadget::constrain_eq(old_managing_cluster, new_managing_cluster, cs)?;

    // TRUNCATED...

    for (old_bal, new_bal) in old_balances.iter().zip(new_balances) {
        let BalanceVar {
            mint: old_mint,
            amount: old_amount,
            relayer_fee_balance: old_relayer_fee_balance,
            protocol_fee_balance: old_protocol_fee_balance,
        } = old_bal;
        let BalanceVar {
            mint: new_mint,
            amount: new_amount,
            relayer_fee_balance: new_relayer_fee_balance,
            protocol_fee_balance: new_protocol_fee_balance,
        } = new_bal;
        // TRUNCATED...
        EqGadget::constrain_eq(old_mint, new_mint, cs)?;
        EqGadget::constrain_eq(old_amount, new_amount, cs)?;