Spartan ECDSA review report

[bahurum]

Spartan ECDSA review report

Review Resources:

• Efficient ECDSA
• Spartan ECDSA

Auditors:

• Bahurum

Table of Contents

1. Review Summary
2. Scope
3. Findings Explanation
4. Low Findings
5. Informational Findings
6. Final remarks

Review Summary

Spartan ECDSA from Personae Labs

Personae Lab's Spartan ECDSA allows for fast verification of ECDSA secp256k1 signatures using SpartanNIZK and right field arithmetics.

The contracts of Personae Lab's Spartan ECDSA Repo were reviewed by 1 auditor between june 20 and july 5, 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 3386b30d9b5b62d8a60735cbeab42bfe42e80429 for the spartan-ecdsa repo.

Scope

The scope of the review consisted of the following circom files at the specific commit:

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

Code Evaluation Matrix

Category	Mark	Description
Mathematics	Good	Implementation of circuits checks with math specification
Complexity	Average	Minimalisitc code, but circuit optimization sometimes reduces readability
Libraries	Good	Uses well-known circom libraries
Documentation	Average	Good documentation, code comments can be improved
Testing and verification	Good	Good test coverage

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

No critical, high or medium severity vulnerabilites were found during this review, so there are no corresponding sections for them.

While results of Circomspect on the files in scope were considered, they were all false positives and all the findings below have been spot through manual analysis.

---

Low Findings

1. Low - Unchecked edge case in complete addition

Secp256k1AddComplete() returns an incorrect value when yP + yQ = 1.

Technical Details

zeroizeA.out should be 0 when P and Q are different points, but when xP != xQ and yP + yQ = 1 it would be 1.

In this case the output point would be the point at infinity instead of the actual sum.

Impact

Low. Secp256k1 arithmetics is incorrect in some edge cases.

Recommendation

Document the proof that P,Q on the curve such that yP + yQ = 1 do not exist or are practically impossible to occurr.

If this can't be done, then add a isYEqual component as done for X and use AND() instead of IsEqual()

    component zeroizeA = AND();
    zeroizeA.in[0] <== isXEqual.out;
    zeroizeA.in[1] <== isYEqual.out;

Developer Response

Informational Findings

1. Informational - Unused variable

In EfficientECDSA template the variable bits is declared but never used.

Impact

Informational. No impact on the generated circuit.

Recommendation

Consider removing the declaration of the unused variable.

Final remarks

No major security issues were found during the review.
The circuits appear to be constrained correctly.

However, the code implements several complex mathematical calculation and the correctness of the specification has not been verified.

Finally, the code relies on custom versions of circom and SpartanNIZK that support secp256k1 curves. They are out of scope for this review but the modifications could have introduced bugs not present in the orginal versions.