*By Fredrik Dahlgren, Principal Safety Engineer*

** TL;DR:** We have now launched model 0.8.0 of Circomspectour static analyzer and linter for Circom. Since our preliminary launch of Circomspect in September 2022, we now have added 5 new evaluation passes, assist for tags, tuples, and nameless parts, hyperlinks to in-depth descriptions of every recognized concern, and squashed numerous bugs. Please obtain the brand new model and inform us what you assume!

## New evaluation passes

The brand new evaluation passes, added to the device’s preliminary 9, test for a variety of points that might happen in Circom code:

- Failure to correctly constrain intermediate alerts
- Failure to constrain output alerts in instantiated templates
- Failure to constrain divisors in division operations to nonzero values
- Use of BN254-specific templates from Circomlib with a special curve
- Failure to correctly constrain inputs to Circomlib’s
`LessThan`

circuit

Aside from discovering the difficulty associated to the Circomlib LessThan circuit mentioned beneath, these evaluation passes would even have caught the “million dollar ZK bug” lately recognized by Veridise within the `circom-pairing`

library.

To grasp the kinds of points that Circomspect can establish, let’s dig into the ultimate instance on this record. This evaluation go identifies a difficulty associated to the `LessThan`

circuit applied by Circomlibthe de facto customary library for Circom. To completely perceive the difficulty, we first have to take a step again and perceive how signed values are represented by Circom.

## Signed arithmetic in GF(p)

Circom applications function on variables known as alerts, which signify parts within the finite subject `GF(p)`

of integers modulo a chief quantity `p`

. It’s common to establish the weather in `GF(p)`

with the unsigned integers within the half-open interval `[0, p)`

. However, it is sometimes convenient to use field elements to represent signed quantities in the same way that we may use the elements in `[0, 2`

to represent signed 32-bit integers. Mirroring the definition for two’s complement used to represent signed integer values, we define ^{32})`val(x)`

as follows:

We then say that *a is less than b* in `GF(p)`

if `val(a) < val(b)`

as signed integers. This means that `q = floor(p/2)`

is the greatest signed value representable in `GF(p)`

, and that `-q = q + 1`

is the least signed value representable in `GF(p)`

. It also means, perhaps somewhat surprisingly, that `q + 1`

is actually less than `q`

. This is also how the comparison operator `<`

is implemented by the Circom compiler.

As usual, we say that `a`

*is positive* if `a > 0`

and *negative* if `a < 0`

. One way to ensure that a value a is nonnegative is to restrict the size (in bits) of the binary representation of `a`

. In particular, if the size of a is strictly less than `log(p) - 1`

bits, then `a`

must be less than or equal to `q`

and, therefore, nonnegative.

## Circomlib’s ‘LessThan’ template

With this out of the way, let’s turn our attention to the LessThan template defined by Circomlib. This template can be used to constrain two input signals `a`

and `b`

to ensure that `a < b`

, and is implemented as follows:

Looking at the implementation, we see that it takes an input parameter n and two input signals `in[0]`

and `in[1]`

and it defines a single output sign out. Moreover, the template makes use of the `Num2Bits`

template from Circomlib to constrain the output sign out.

The `Num2Bits`

template from Circomlib takes a single parameter `n`

and can be utilized to transform a subject component to its n-bit binary illustration, which is given by the array out of measurement `n`

. For the reason that measurement of the binary illustration is bounded by the parameter n, the enter to `Num2Bits`

can also be implicitly constrained to `n`

bits. Within the implementation of `LessThan`

above, the expression `(1 << n) + in[0] - in[1]`

is handed as enter to `Num2Bits`

which constrains absolutely the worth `|in[0] - in[1]|`

to `n`

bits.

To grasp the subtleties of the implementation of the `LessThan`

template, let’s first think about the anticipated use case when each inputs to `LessThan`

are at most `n`

bits, the place `n`

is sufficiently small to make sure that each inputs are nonnegative.

We have now two circumstances to contemplate. If `in[0] < in[1]`

then `in[0] - in[1]`

is a unfavorable `n-`

bit worth, and `(1 << n) + in[0] - in[1]`

is a optimistic n-bit worth. It follows that bit `n`

within the binary illustration of the enter to `Num2Bits`

is `0`

and thus out should be equal to `1 - 0 = 1`

.

However, if `in[0] ≥ in[1]`

then `in[0] - in[1]`

is a nonnegative n-bit worth (since each inputs are optimistic), and `(1 << n) + in[0] - in[1]`

is a optimistic `(n + 1)`

-bit worth with essentially the most vital bit equal to `1`

It follows that bit `n`

within the binary illustration of the enter to `Num2Bits`

is `1`

and out should be given by `1 - 1 = 0`

.

This all is smart and provides us some confidence if we need to use `LessThan`

for vary proofs in our personal circuits. Nonetheless, issues develop into extra sophisticated if we overlook to constrain the scale of the inputs handed to `LessThan`

.

## Utilizing alerts to signify unsigned portions

To explain the primary kind of concern that will have an effect on circuits outlined utilizing `LessThan`

think about the case wherein alerts are used to signify unsigned values like financial quantities. Say that we need to permit customers to withdraw funds from our system with out revealing delicate info, like the full steadiness belonging to a single person or the quantities withdrawn by customers. We may use `LessThan`

to implement the a part of the circuit that validates the withdrawn quantity towards the full steadiness as follows:

Now, suppose {that a} malicious person with a zero steadiness decides to withdraw `p - 1`

tokens from the system, the place `p`

is the scale of the underlying prime subject. Clearly, this shouldn’t be allowed since `p - 1`

is a ridiculously massive quantity and, in any case, the person has no tokens obtainable for withdrawal. Nonetheless, trying on the implementation of `LessThan`

we see that on this case, the enter to `Num2Bits`

will probably be given by `(1 << 64) + (p - 1) - (0 + 1) = (1 << 64) - 2 `

(as all arithmetic is finished modulo `p`

). It follows that bit 64 of the binary illustration of the enter will probably be `0`

and the output from `LessThan`

will probably be `1 - n2b.out[64] = 1 - 0 = 1`

. This additionally signifies that `ValidateWithdrawal`

will establish the withdrawal as legitimate.

The issue right here is that `p - 1`

additionally represents the signed amount –`1`

in `GF(p)`

. Clearly, `-1`

is lower than `1`

and we now have not constrained the withdrawn quantity to be nonnegative. Including a constraint limiting the scale of the quantity to be lower than `log(p) - 1`

bits would be certain that the quantity should be optimistic, which might stop this concern.

Extra usually, for the reason that enter parameter `n`

to `LessThan`

restricts solely the scale of the distinction `|in[0] - in[1]|`

we sometimes can’t use `LessThan`

to stop overflows and underflows. This can be a refined level that many builders miss. For instance, consider the section on arithmetic overflows and underflows from the zero-knowledge (ZK) bug tracker maintained by 0xPARC. In an earlier version0xPARC steered utilizing `LessThan`

to constrain the related alerts in an instance that was virtually an identical to the weak `ValidateWithdrawal`

template outlined above!

One other vulnerability of this kind was discovered by Daira Hopwood in an early version of the ZK space-conquest game Darkish Forest. Right here, the vulnerability allowed customers to colonize planets far exterior the taking part in subject. The builders addressed the difficulty by including a variety proof based mostly on the `Num2Bits`

template that restricted the size of the coordinates to 31 bits.

## Utilizing alerts to signify signed portions

Now, suppose alerts are used to signify signed portions. Specifically, let’s think about what would occur if we handed `q = flooring(p/2)`

and `q + 1`

as inputs to `LessThan`

. We’ll present that regardless that `q + 1 < q`

in keeping with the Circom compiler, `q`

is definitely lower than `q + 1`

in keeping with `LessThan`

. Returning to the enter to `Num2Bits`

within the definition of `LessThan`

we see that if `in[0] = q`

and `in[1] = q + 1`

the enter to Num2Bits is given by the next expression:

(1 << n) + in[0] - in[1] = (1 << n) + q - (q + 1) = (1 << n) - 1

It follows that the `n`

th bit within the binary illustration of this worth is `0`

and the output from `LessThan`

is `1 - n2b.out[n] = 1 - 0 = 1`

. Thus, `q < q + 1`

in keeping with `LessThan`

, *regardless that q + 1 < q in keeping with the compiler!*

It’s price reiterating right here that the enter parameter `n`

to `LessThan`

doesn’t prohibit the scale of the inputs, solely absolutely the worth of their distinction. Thus, we’re free to go very massive (or very small) inputs to `LessThan`

. Once more, this concern will be prevented if the scale of each of the inputs to the `LessThan`

template are restricted to be lower than `log(p) - 1`

bits.

## Circomspect to the rescue (half 1)

To search out problems with this kind, Circomspect identifies places the place LessThan is used. It then tries to see whether or not the inputs to LessThan are constrained to lower than `log(p) - 1`

bits utilizing the `Num2Bits`

template from Circomlib, and it emits a warning if it finds no such constraints. This enables the developer (or reviewer) to shortly establish places within the codebase that require additional overview.

As proven within the screenshot above, every warning from Circomspect will now sometimes additionally comprise a hyperlink to an outline of the potential concern, and proposals for methods to resolve it.

## Circomspect to the rescue (half 2)

We might additionally like to say one other of our new evaluation passes. The most recent model of Circomspect identifies places the place a template is instantiated however the output alerts outlined by the template should not constrained.

For instance, think about the `ValidateWithdrawal`

template launched above. Suppose that we rewrite the template to incorporate vary proofs for the enter alerts `quantity`

and `whole`

. Nonetheless, in the course of the rewrite we by accident overlook to incorporate a constraint making certain that the output from `LessThan`

is `1`

. Which means that customers could possibly withdraw quantities which are better than their whole steadiness, which is clearly a severe vulnerability!

There are examples (like `Num2Bits`

) wherein a template constrains its inputs and no additional constraints on the outputs are required. Nonetheless, forgetting to constrain the output from a template usually signifies a mistake and requires additional overview to find out whether or not it constitutes a vulnerability. Circomspect will flag places the place output alerts should not constrained to make sure that every location will be manually checked for correctness.

## Let’s discuss!

We at Path of Bits are enthusiastic about contributing to the rising vary of instruments and libraries for ZK which have emerged in the previous couple of years. In case you are constructing a undertaking utilizing ZK, we might love to speak to you to see if we can assist in any method. In case you are occupied with having your code reviewed by us, or in the event you’re trying to outsource components of the event to a trusted third celebration, please get in touch with our staff of skilled cryptographers.

*Associated*

Writer: Path of Bits

Date: 2023-03-21 08:00:24