search

zBlock-1 / RLN-audit-report

3 stars 6 forks source link

Sprint 1 - Rate Limiting Nullifier (RLN) Protocol - Antonio Viggiano, Igor Line, Oba #6

Open obatirou opened 1 year ago

obatirou commented 1 year ago

yAcademy Rate Limiting Nullifier Review

Review Resources:

Auditors:

Table of Contents

  1. Review Summary
  2. Scope
  3. Automated program analysis tools
  4. Code Evaluation Matrix
  5. Findings Explanation
  6. High Findings
  7. Medium Findings
  8. Low Findings
  9. Optimizations
  10. Informational Findings

Review Summary

Rate Limiting Nullifier

RLN (Rate-Limiting Nullifier) is a zk-gadget/protocol that enables spam prevention mechanism for anonymous environments.

Users register an identityCommitment, which is stored in a Merkle tree, along with a stake. When interacting with the protocol, the user generate a zero knowledge proof that ensures their identity commitment is part of the membership Merkle tree and they have not exceeded their rate limit. It leverages Shamir secret sharing for that. If they exceed their rate limit, their secret is revealed and their stake can be slashed.

The circuits of the RLN protocol were reviewed over 10 days. The code review was performed by 3 auditors between May 31, 2023 and June 14, 2023. The repository was not under active development during the review, and review was limited to the latest commit at the start of the review. This was commit 37073131b9c5910228ad6bdf0fc50080e507166a for the circom-rln repo.

In addition, the contracts of the rln-contracts repo, commit dfcdb2beff91583d02636570242cfdd8469b61c1, were provided as a reference implementation on how the circuits would be integrated. Although these contracts were considered out of scope, we have also included some related findings in this report.

Scope

The scope of the review consisted of the following circuits at the specific commit:

After the findings were presented to the RLN team, fixes were made and included in several PRs.

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, RLN and users of the contracts agree to use the code at their own risk.

Automated program analysis tools

Picus developed by Veridise and Ecne developped by Franklyn Wang are automatic proof search tools. Those tools can identifies underconstrained bugs by finding valid multiple set of input signals sharing the same output signal, breaking the uniquess property.

Results

Ecne did not found any bug on rnl.circom or withdraw.circom. Picus did not found any bug on withdraw.circom. We were not able to run it on rln.circom due to memory problems. Picus was not able to terminate after 6h with 12G of ram and 6CPU allocated.

Code Evaluation Matrix

Category Mark Description
Access Control N/A RLN is a permissionless protocol, and as such no access control is required
Mathematics Good Well known libraries such as circomlib were used whenever possible. In particular to calculate the Poseidon hash function of necessary parameters
Complexity Good The code is easy to understand and closely follows the specification
Libraries Good Well known libraries such as circomlib were used whenever possible
Decentralization Good RLN is a permissionless protocol
Code stability Good The code was reviewed at a specific commit. The code did not changed during the review. Moreover, it is not likely to change significantly with the addition of features or updates
Documentation Good RLN documentation comprises a specification RFC, a Github documentation website, a Github README documentation, and a Hackmd presentation. It is recommended to reduce the number of resources necessaries to fully understand the protocol.
Monitoring N/A The protocol is intended to be implemented by a dapp, which will be responsible for the monitoring
Testing and verification Average The protocol contains only a few tests for the circuits. It is recommended to add more tests to increase the test coverage.

Findings Explanation

Findings are broken down into sections by their respective impact:

Critical Findings

None.

High Findings

None.

Medium Findings

1. Medium - Unused public inputs optimized out by the circom compiler

The circuit withdraw.circom contains a potential issue related to public inputs being optimized out by the circom compiler.

Technical Details

The withdraw.circom circuit specifies address as a public input but does not use this input in any constraints. Consequently, the unused input could be pruned by the compiler, making the zk-SNARK proof independent of this input. This may result in a potentially exploitative behavior.

Impact

Medium. Despite circom not generating constraints for unused inputs, snarkjs, which is used by RLN, does generate these constraints. The protocol also tested ark-circom, which also adds the constraint ommitted by circom. However, if some zk-SNARK implementation does not include these constraints, this can lead to a potential loss of funds by users of the protocol.

Recommendation

As outlined in 0xPARC's zk-bug-tracker, it is advised to add a dummy constraint using the unused signal address in the circuit. This change ensures that the zk-SNARK proof is dependent on the address input.

diff --git a/circuits/withdraw.circom b/circuits/withdraw.circom
index a2051ea..7a4b88d 100644
--- a/circuits/withdraw.circom
+++ b/circuits/withdraw.circom
@@ -6,6 +6,8 @@ template Withdraw() {
     signal input identitySecret;
     signal input address;

+    signal addressSquared <== address * address;
+
     signal output identityCommitment <== Poseidon(1)([identitySecret]);
 }

Developer Response

Good find! We'll add the "dummy constraint" to the circuit.

2. Medium - Missing constraint on x value passed as zero

In rln.circom, passing the x value as zero would directly expose the identitySecret.

Technical Details

In rln.circom, passing the x value as zero would directly expose the identitySecret. However, there is no constraint that prevents this value from being set.

Impact

Medium. Although this can be prevented on the dapp/implementation of the protocol, it is adviseable to also prevent it on the circuit. A buggy UI could pass zero as x and expose the identitySecret leading to loss of funds for the user.

Recommendation

Add a constraint to prevent thex value to be passed as zero.

Developer Response

x is hash of the message, and it's hashed outside of the circuits. Correctness can be checked on the client-side as it's public input. Check for zero should be done outside of the circuit.

Low Findings

1. Low - Inconsistency between contract and circuit on the number of bits for userMessageLimit

During our audit process, we identified an inconsistency between the RLN.sol and rln.circom pertaining to the userMessageLimit. Specifically, the difference lies in the range of values that messageLimit, messageId, and userMessageLimit can take.

Technical Details

In RLN.sol, the calculation of messageLimit is based on the amount divided by MINIMAL_DEPOSIT. Given the current implementation, messageLimit has the potential to accept values up to 2**256 - 1.

On the other hand, in rln.circom, the messageId and userMessageLimit values are limited by the RangeCheck(LIMIT_BIT_SIZE) function to 2**16 - 1.

Although the contracts check that the identity commitment is lower than the size of the set, which is 2**20, it is possible that the DEPTH and LIMIT_BIT_SIZE parameters of the circuit are modified, which would lead to unexpected outcomes if not addressed.

Impact

Low. On the current implementation, this discrepancy does not pose any issues to the protocol.

Recommendation

Short term, add a range check to the circuits to make sure they are constrained to the same range as the smart contract variables. Long term, make sure the input space of the contracts and the circuits are always in sync.

Developer Response

Good find! We'll add this check to the contract:)

Optimization Findings

None.

Informational Findings

1. Informational - Mismatch between specification and implementation

Mismatch between specification and implementation regarding the x message value.

Technical Details

In 58/RLN-V2, the specification states that x is the signal hashed. However, in the rln.circom circuit, x is the message without hash.

Impact

Informational.

Recommendation

Update the implementation to hash the x value according to the specification.

Developer Response

x is hash of the message, and it's hashed outside of the circuits. Correctness can be checked on the client-side as it's public input.

Final remarks

N/A.

curryrasul commented 1 year ago

Hi, thanks for your report!

Unused public inputs optimized out by the circom compiler

Good find! We'll add the "dummy constraint" to the circuit.

Inconsistency between contract and circuit on the number of bits for userMessageLimit

Good find! We'll add this check to the contract:)

Mismatch between specification and implementation

x is hash of the message, and it's hashed outside of the circuits. Correctness can be checked on the client-side as it's public input.

obatirou commented 1 year ago

Hi @curryrasul, thank you for your responses !

One remark is that there was no explicit response for Missing constraint on x value passed as zero From your response for Mismatch between specification and implementation

x is hash of the message, and it's hashed outside of the circuits. Correctness can be checked on the client-side as it's public input.

We can infer that Missing constraint on x value passed as zero is refused and the check for zero should be done outside of the circuit.

Could you confirm this ?

curryrasul commented 1 year ago

Could you confirm this ?

Yes!