Report by nullity

[nullity00]

yAcademy - Spartan ECDSA

Review Resources:

• Spartan ECDSA

Auditors:

• nullity

Table of Contents

• Review Summary
• Scope
• Findings Explanation
• Critical Findings
• High Findings
• Medium Findings
• Low Findings
• Informational Findings

Review Summary

Spartan ECDSA

Spartan-ecdsa (which to our knowledge) is the fastest open-source method to verify ECDSA (secp256k1) signatures in zero-knowledge. Spartan is a high-speed zero-knowledge proof system which does not require trusted setup. Spartan uses curve25519-dalek for arithmetic over ristretto255 whereas spartan-ecdsa uses the secp256k1 curve with the following params. Ref [1] [2]

p (base field) = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
q (generator order) = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

The code was reviewed over 17 days. The code review was performed between 19th June and 5th July, 2023. The repository was under active development during the review, but the review was limited to the latest commit at the start of the review. This was commit 3386b30d9b for the circom-rln repo.

Scope

The following circom files are in scope!

eff_ecdsa.circom
tree.circom
add.circom
double.circom
mul.circom
poseidon.circom
pubkey_membership.circom

The findings were presented to Personae Labs team.

This review is a code review to identify potential vulnerabilities in the code. The reviewers did not investigate security practices or operational security and assumed that privileged accounts could be trusted. The reviewers did not evaluate the security of the code relative to a standard or specification. The review may not have identified all potential attack vectors or areas of vulnerability.

yAcademy and the auditors make no warranties regarding the security of the code and do not warrant that the code is free from defects. yAcademy and the auditors do not represent nor imply to third parties that the code has been audited nor that the code is free from defects. By deploying or using the code, Personae Labs and users of the contracts agree to use the code at their own risk.

Code Breakdown Matrix

Section	Mark	Description
benchmark	Good	Typescript files to prove public key membership & address membership in web browser & local environment
circuit_reader	Good	Circom Circuit reader written in Rust to read r1cs files, constraint vectors etc.
circuits	Good	Consists an implementation of Poseidon hash function, ecdsa membership, address & public key verification & addition, multiplication, doubling of secp256k1 curve points as specified in Halo2 book in circom
lib	Good	Membership Prover & Verifier Classes written in typescript
poseidon	Good	Rust implementation of Poseidon over the base field of secp256k1 & contains sagemath files to produce parameters
secq256k1	Good	Rust implementation of secp256k1 curve for big int & 256 bit numbers
spartan_wasm	Good	Wasm Module in Rust to generate proof & verify using Spartan
Spartan-secq	Good	Modified version of the original spartan with curve secp256k1

Code Evaluation Matrix

Category	Mark	Description
Cryptography	Good	To hash the secret values, Poseidon hash function has been used. This uses fewer constraints per bit compared to other functions lowering down the time consumed
Libraries	Good	The circuits use the defacto circomlib
Circuit Dependence Graph	Good	The signals in the circuit are properly constrained with a well formed CDG
Documentation	Good	The documentation is clear & concise
Proof Systems	Good	Proof generation is done using Spartan-secq using a secp256k1 curve, which has security level of 128 bits

Findings Explanation

Findings are broken down into sections by their respective impact:

• Critical, High, Medium, Low impact
  • These are findings that range from attacks that may cause loss of funds, impact control/ownership of the contracts, or cause any unintended consequences/actions that are outside the scope of the requirements
• Informational
  • Findings including recommendations and best practices

---

Critical Findings

None.

High Findings

• Under constrained circuits compromising the soundness of the system

File : packages/circuits/eff_ecdsa_membership/secp256k1/mul.circom

    signal slo <-- s & (2 ** (128) - 1);
    signal shi <-- s >> 128;

The signals slo & shi are underconstrained.

Developer Response

    signal slo <-- s & (2 ** (128) - 1);
    signal shi <-- s >> 128;
    slo + shi * 2 ** 128 === s;

Adding the line slo + shi * 2 ** 128 === s; would fix this, but it turns out that actually, that calculation of k = (s + tQ) % q doesn't have to be constrained at all (so the entire template K is unnecessary). Regardless, your discovery made me realize K is unnecessary, which results in solid constraint count reduction!

Medium Findings

None.

Low Findings

None.

Informational Findings

1. Over allocation of components

File : circuits/eff_ecdsa_membership/secp256k1/mul.circom

    var bits = 256;
    component PComplete[bits-3]; 
    component accComplete[3];

    for (var i = 0; i < 3; i++) {
        PComplete[i] = Secp256k1AddComplete(); // (Acc + P)

Recommended Solution

component PComplete[3]

2. Over allocation of components

File : circuits/eff_ecdsa_membership/secp256k1/mul.circom

    component PIncomplete[bits-3]; 
    component accIncomplete[bits];

    for (var i = 0; i < bits-3; i++) {
        if (i == 0) {
            PIncomplete[i] = Secp256k1AddIncomplete(); // (Acc + P)
            ...
            accIncomplete[i] = Secp256k1AddIncomplete(); // (Acc + P) + Acc

Since the loop runs for bits-3 times, component accIncomplete[bits-3] would be the correct declaration of components.