Circomspect has extra passes! | Path of Bits Weblog

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:

1. Failure to correctly constrain intermediate alerts
2. Failure to constrain output alerts in instantiated templates
3. Failure to constrain divisors in division operations to nonzero values
4. Use of BN254-specific templates from Circomlib with a special curve
5. 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, 232) to represent signed 32-bit integers. Mirroring the definition for two’s complement used to represent signed integer values, we define 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:

The LessThan template defined by Circomlib

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 Num2Bitswhich 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 0and 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 1It follows that bit n within the binary illustration of the enter to Num2Bits is 1and 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 LessThanthink 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:

The ValidateWithdrawal template ought to be certain that customers can’t withdraw greater than their whole steadiness.

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 LessThanwe 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 0and 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 1and 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 LessThanwe see that if in[0] = q and in[1] = q + 1the 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 nth bit within the binary illustration of this worth is 0and 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.

The output from the most recent model of Circomspect working on the ValidateWithdrawal template outlined above.

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!

We rewrite ValidateWithdrawal to incorporate vary proofs for the 2 inputs quantity and whole, however by accident overlook to constrain the output sign lt.out to be 1!

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.

Circomspect now generates a warning if it finds that the output alerts outlined by a template should not correctly constrained.

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