Skip to content

zBlock-1/spartan-ecdsa-audit-report

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

25 Commits
 
 
 
 

Repository files navigation

yAcademy Spartan-ecdsa Review

Review Resources:

Auditors:

Table of Contents

Review Summary

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.

Scope

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.

Code Evaluation Matrix


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 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, proof malleability, 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

1. High - Input signal s is not constrained in eff_ecdsa.circom

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.

Technical Details

Given check $\ s * T + U == pubKey$ ,

$$s * T + U == pubKey$$ $$s = 0 , \forall T \in secp256k1$$ $$s * T + U = 0 * T + U = O + U = U == pubKey$$ $$or$$ $$T = 0 , \forall s \in secp256k1$$ $$s * T + U = s * 0 + U = O + U = U == pubKey$$

where U = (pubX, pubY). -U would work as well, where -U = (pubX, -pubY). Here is a POC to explain the same.

Impact

High. The missing constraints can be used to generate fake proof.

Recommendation

Add the constraints to the circuit and/or documentation

Developer Response

Acknowledged

Reported by Antonio Viggiano, Igor Line, Oba

2. High - Knowledge of any member signature allow to generate proof of membership

Knowledge of any valid signature by an account stored in the merkle tree allows generating membership proof

Technical Details

There is no check on message supplied by the user. Anyone can submit valid past signatures with arbitrary message hash

Impact

High. The missing constraints can be used to generate fake proof.

Recommendation

Add the constraints to the circuit and/or documentation

Developer Response

Acknowledged

Reported by Antonio Viggiano, Igor Line, Oba

3. High - Under constrained circuits compromising the soundness of the system

In the file mul.circom, the signals slo & shi are assigned but not constrained.

Technical Details

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

Impact

High. Underconstraining allows malicious provers to generate fake proofs.

Developer Response

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!

Reported by nullity

4. High - X, Y pair may be an invalid point on the curve

Circuits do not check whether the point $(x,y)$ is on the curve $E$.

Technical Details

The pair $(x,y)$ forms a group $G$ of order $N$ under $E(\mathbb{F}_p)/\mathcal{P}$ where $E$ represents an elliptic curve, $x, y &lt; P$, $\mathbb{F}_p$ denotes a finite field, and $\mathcal{P}$ represents the prime order of the base point. There is no check validating that $(x,y)$ $\in$ $G$.

Impact

User may provide a public key (which is just a point $(x,y)$) that is not a valid point on the curve. This may leak the private key if the point is chosen from small order $N'$ of another curve $C'$

Recommendation

Validate the given point $(x,y)$ outside of the circuit.

Developer Response

Acknowledged

Reported by Rajesh

Medium Findings

None.

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 when $yP + yQ = 1$, the points $P$ and $Q$ either do not exist on the curve or are highly improbable to occur.

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 $p$ & $-p$

Developer Response

Acknowledged

Reported by Bahurum, 0xnagu

Informational Findings

1. Informational - Over-allocation of circom components

In mul.circom:Secp256k1Mul, the value accIncomplete and PComplete are over-allocated.

Technical Details

In mul.circom:Secp256k1Mul, the value accIncomplete and PComplete are over-allocated.

    component accIncomplete[bits];
    // ...
    component PComplete[bits-3]; 

Impact

Optimization.

Recommendation

Reduce the allocation of these component arrays to accIncomplete[bits-p3] and PIncomplete[3].

Developer Response

Acknowledged

Reported by Antonio Viggiano, Igor Line, Oba, nullity, parsley

2. Informational - Check if the input scalar is within the valid range

Technical Details

Add assertions and constraints to check for invalid inputs and edge cases

Impact

Informational.

Recommendation

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);

Developer Response

Acknowledged

Reported by 0xnagu

3. Informational - Unused value bits

Technical Details

In eff_ecdsa.circom, the value bits is assigned but never read.

Impact

Informational.

Recommendation

Remove the unused value.

Developer Response

Acknowledged

Reported by Antonio Viggiano, Igor Line, Oba, garfam, parsley, Bahurum, lwltea

4. Informational - No constraints on input signals

Technical Details

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.

Impact

Informational.

Recommendation

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.

Developer Response

Acknowledged

Reported by whoismatthewmc

5. Informational - Missing & Extra Imports in eff_ecdsa.circom

Technical Details

The add.circom import is missing in eff_ecdsa.circom. The bitify.circom is imported in eff_ecdsa.circom but not used.

Impact

Informational. This is not an issue as add.circom is imported in mul.circom which is in turn imported in eff_ecdsa.circom.

Recommendation

But recommendation is to explicitly import like include "./secp256k1/add.circom"; & remove bitify.circom import.

Developer Response

Acknowledged

Reported by lwltea, Vincent Owen

6. Informational - Constraints for add.cicom for values to be non-zero

In signal assignments containing division, the divisor needs to be constrained to be non-zero.

Technical Details

   │
31 │     lambda <-- dy / dx;
   │                     ^^ The divisor `dx` must be constrained to be non-zero.

Impact

Informational.

Recommendation

Do an additional check for non-zero values.

Developer Response

Acknowledged

Reported by Chen Wen Kang, Vincent Owen

7. Informational - More tests for the circuits

Additional tests are always good to have in order to cover more unexpected cases.

Technical Details

eff_ecdsa.test.ts and eff_ecdsa_to_addr.test.ts only have 1 positive tests.

Impact

Informational.

Recommendation

Adding more tests for the circuits.

Developer Response

Acknowledged

Reported by Chen Wen Kang, Vincent Owen

Final remarks

  • 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.

About

Fellows submit their reports as issues in this repo

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published