Review Resources:
Auditors:
- 0xnagu
- Antonio Viggiano
- Bahurum
- Chen Wen Kang
- garfam
- Igor Line
- lwltea
- nullity
- Oba
- parsley
- Rajesh
- Vincent Owen
- whoismatthewmc
- Review Summary
- Scope
- Code Evaluation Matrix
- Findings Explanation
- Final Remarks
- Automated Program Analysis
Spartan-ecdsa
Spartan-ecdsa is a library for proving and verifying ECDSA (secp256k1) signatures in zero-knowledge. Group membership proving time is 10x faster in Spartan-ecdsa compared to efficient-zk-ecdsa, the previous implemenation by Personae Labs. It is developed using the Spartan proof system which does not require trusted setup. However, Spartan uses secp256k1 curve intead of curve25519-dalek in Spartan.
The Spartan-ecdsa circuits, commit 3386b30d9b, were reviewed by 13 auditors between June 19, 2023 and July 5, 2023.
The scope of the review consisted of the following circuits at commit 3386b30d9b:
- eff_ecdsa.circom
- tree.circom
- add.circom
- double.circom
- mul.circom
- poseidon.circom
- pubkey_membership.circom
After the findings were presented to the Spartan-ecdsa team, fixes were made and included in several PRs.
This review is for identifying 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, Spartan-ecdsa and users of the circuits agree to use the code at their own risk.
| Category | Mark | Description |
|---|---|---|
| Access Control | N/A | Spartan-ecdsa is a permissionless protocol, and as such no access control is required |
| Mathematics | Good | Sage scripts were created to assess the security of some parameters used in the algorithms |
| Complexity | High | Complexity is reduced compared to previous implementations due to doing right-field arithmetic on secq and eliminating SNARK-unfriendly range checks and big integer math. This led to an overall reduction of R1CS constraints from 1.5M to ~5k. |
| Libraries | Average | Well-known libraries such as circomlib are used, but Poseidon was custom-implemented with Spartan-ecdsa's own constants since the finite field that Spartan uses isn't supported |
| Decentralization | Good | Spartan-ecdsa is a permissionless protocol |
| Cryptography | Good | Spartan-ecdsa operates on the secp256k1 curve which provides a security level of 128 bits. It makes use of the Poseidon hash function known for its zk-friendlinesss, simplicity, and resistance against various cryptanalytic attacks. However, it's essential to note that cryptographic algorithms and functions are always subject to ongoing analysis, and new attacks or weaknesses may be discovered in the future. |
| Code stability | Average | The code was reviewed at a specific commit. The code did not change during the review. However, due to its focus on efficiency, it is likely to change with the addition of features or updates, or to achieve further performance gains. |
| Documentation | Low | Spartan-ecdsa documentation comprises blog posts from Personae Labs, the Github README documentation, and reference materials from Filecoin and Neptune. It is recommended to aggregate the resources necessary of the protocol under a single repository |
| Monitoring | N/A | The protocol is intended to be integrated by a dApps who will be responsible for any monitoring needed |
| Testing and verification | Low | The protocol contains only a few tests for the circuits. During audit, the circom-mutator testing tool was developed for finding potential blind spots in the test coverage of circom projects. The circom-mutator tool found that several edge cases were not tested by the project. It is recommended to add more tests to increase test coverage |
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, proof malleability, or cause any unintended consequences/actions that are outside the scope of the requirements
- Informational
- Findings including Recommendations and best practices
None.
It is possible to submit s = 0, Ux = pubX, Uy = pubY or s = 0, Ux = pubX, Uy = -pubY and get back (pubX, pubY), though this is not a valid signature.
Given check
where U = (pubX, pubY). -U would work as well, where -U = (pubX, -pubY). Here is a POC to explain the same.
High. The missing constraints can be used to generate fake proof.
Add the constraints to the circuit and/or documentation
Acknowledged
Reported by Antonio Viggiano, Igor Line, Oba
Knowledge of any valid signature by an account stored in the merkle tree allows generating membership proof
There is no check on message supplied by the user. Anyone can submit valid past signatures with arbitrary message hash
High. The missing constraints can be used to generate fake proof.
Add the constraints to the circuit and/or documentation
Acknowledged
Reported by Antonio Viggiano, Igor Line, Oba
In the file mul.circom, the signals slo & shi are assigned but not constrained.
signal slo <-- s & (2 (128) - 1);
signal shi <-- s >> 128;
High. Underconstraining allows malicious provers to generate fake proofs.
Adding the line
slo + shi * 2 128 === s;would fix this, but it turns out that actually, that calculation ofk = (s + tQ) % qdoesn'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!
Reported by nullity
Circuits do not check whether the point
The pair
User may provide a public key (which is just a point
Validate the given point
Acknowledged
Reported by Rajesh
None.
Secp256k1AddComplete() returns an incorrect value when yP + yQ = 1.
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.
Low. secp256k1 arithmetics is incorrect in some edge cases.
Document the proof that when
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;
There should be similar informational warnings to the client implementations for many edge cases like zero point, points at infinity, additions/multiplications with
Acknowledged
In mul.circom:Secp256k1Mul, the value accIncomplete and PComplete are over-allocated.
In mul.circom:Secp256k1Mul, the value accIncomplete and PComplete are over-allocated.
component accIncomplete[bits];
// ...
component PComplete[bits-3];
Optimization.
Reduce the allocation of these component arrays to accIncomplete[bits-p3] and PIncomplete[3].
Acknowledged
Reported by Antonio Viggiano, Igor Line, Oba, nullity, parsley
Add assertions and constraints to check for invalid inputs and edge cases
Informational.
Add a constraint to ensure that the input scalar is within the valid range of the secp256k1 elliptic curve. You can do this by adding an assertion to check if the scalar is less than the curve's order.
// Add this line after the signal input scalar declaration
assert(scalar < 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141);
Acknowledged
Reported by 0xnagu
In eff_ecdsa.circom, the value bits is assigned but never read.
Informational.
Remove the unused value.
Acknowledged
Reported by Antonio Viggiano, Igor Line, Oba, garfam, parsley, Bahurum, lwltea
There are no constraints on input signals in any of the circuits (presumably to reduce the number of constraints to a bare minimum). This could potentially cause issues for third party developers integrating Spartan-ECDSA.
Informational.
In order to keep the number of constraints to a minimum, simply document the absence of input signal constraints clearly and suggest that they be validated in the application code.
Acknowledged
Reported by whoismatthewmc
The add.circom import is missing in eff_ecdsa.circom. The bitify.circom is imported in eff_ecdsa.circom but not used.
Informational. This is not an issue as add.circom is imported in mul.circom which is in turn imported in eff_ecdsa.circom.
But recommendation is to explicitly import like include "./secp256k1/add.circom"; & remove bitify.circom import.
Acknowledged
Reported by lwltea, Vincent Owen
In signal assignments containing division, the divisor needs to be constrained to be non-zero.
│
31 │ lambda <-- dy / dx;
│ ^^ The divisor `dx` must be constrained to be non-zero.
Informational.
Do an additional check for non-zero values.
Acknowledged
Reported by Chen Wen Kang, Vincent Owen
Additional tests are always good to have in order to cover more unexpected cases.
eff_ecdsa.test.ts and eff_ecdsa_to_addr.test.ts only have 1 positive tests.
Informational.
Adding more tests for the circuits.
Acknowledged
Reported by Chen Wen Kang, Vincent Owen
- The Spartan-ecdsa circuits assume that the underlying hash function (Poseidon) is:
- Collision-resistant
- Resistant to differential, algebraic, and interpolation attacks
- Behaves as a random oracle
- The Merkle tree used for membership proof is assumed to be secure against second-preimage attacks.
- Social engineering attacks are still a valid way to break the system. ECDSA has several nonce based attacks. It is very important that the client side confirguration doesn't leak any nonce data or any app metadata that can reduce the security of guessing nonce for the ECDSA.
- We recommend clarifying the proper usage of each template, where assertions about the valuation of its inputs (pre-conditions) should be satisfied when calling the template.
- We recommend writing a checklist to be ensured on the client side. This can help dApp developers avoid common mistakes such as missing validation of inputs which can lead to soundness bugs.
- Overall, the code demonstrates good implementation of mathematical operations and basic functionality. However, it could benefit from more documentation and tests.