Replacing the SIEVE Intermediate Representation
Written: , Published: , Author: Kimberlee Model, Tags: SIEVE IR, outdated,
During most of 2021, the Wizkit team worked with other SIEVE Performers to develop and implement the SIEVE IR. Since it was finalized during summer 2021, we continued to push the envelope beyond what was demonstrated during the Phase I Testing Event. We’ve also been one of the most active voices, within the SIEVE program, critically analyzing this IR. In this blog post, we put the results of the critique to good use in making design suggestions for the next IR revision.
As we enter Phase II, Wizkit’s intention is to approach this round of IR development without much emphasis on maintaining backwards compatibility. In this redesign, our view is that the biggest drawback to rectify is the treatment of the IR as a clean hand-off from TA1 (the human-facing language) to TA2 (the ZK proof system).
To really illustrate this point, essentially every TA2 backend in the SIEVE program has a format that they would prefer over the IR. Wizkit’s EMP backend prefers to encode its circuits in compiled C++, while our Virgo backend prefers to extract its own structuring from a non-uniform circuit, and yet other backends just want R1CS. Additionally, as TA2s gain functionality (such as batch/vector optimization, free disjunctions, or ZK RAM), the IR must match that functionality, leaving behind gaps where the program must shift resources around the moving IR.
Similarly, the program has encountered a number of situations where prime-specificity in the IR has been an issue. First, across certain backends, sharing the same prime is not possible. Some backends (for example EMP’s QuickSilver) require Mersenne Primes while other backends (such as Ligero) require Proth Primes which enable FFTs. These sets are disjoint (aside from 3).
To further complicate this, some circuits are specific to a prime. For example, the size and layout of a Fermat’s Little Theorem multiplexer depends on its prime due to its use of the fast exponent algorithm. Another prime specific circuit is the EC-DSA public key signature — its implementation requires the use of specific pair of primes. Yet other circuits, such as business logic, are largely agnostic to the prime so long as it is sufficiently large to avoid overflow.
These complications over primes have become a concern of the IR within the SIEVE program. To resolve these issues, the program has discussed a number of solutions. A parameter negotiation could allow TA2 to indicate preferred primes to TA1. TA2 could be required to embed unsupported prime fields into supported ones. The IR could allow for unspecified primes or even ring ZK (e.g. mod 2n). As we add prime generalities to the IR, the boundary between TA1 and TA2 is further blurred into a gray-zone where both sets of expertise are necessary.
The Layered Approach
With this in mind, our team encourages a two-layer approach to the IR. The top layer, or translation IR (also referred to as "IR2"), has the semantics of translating to the bottom layer. The bottom layer, or circuit abstraction, is a largely flat non-uniform circuit similar to IR-Simple or IR0 (at this point those two terms are largely interchangeable). The translation becomes a gray area where TA1 and TA2 must cooperate to produce either the circuit abstraction or a more suitable ZK format. We also acknowledge that the integrated front/back-end effort may opt to directly evaluate the translation IR.
A benefit of the translation is that it can overcome naturally occuring incompatibilities such as prime mismatches. Say that TA1 calls for a prime that a given TA2 cannot support. In IR1, this was generally a show-stopper. However, for IR2, the translation is an ideal place to replace an arithmetic circuit with a multi-bit boolean circuit or to embed a prime in an alternate field, for example using xJsnark. The same could be done with RAM reductions, for TA2s that don’t natively support RAM. In this way, TA1 may remain involved even after their compiler has emitted valid IR, compensating for the IR’s movement into traditionally "TA1 territory", and gaining functionality in the process.
Independent Functions
Functions in IR1 were heavily dependent on both the size of the circuit and the circuit’s underlying field. In IR2, the program seeks to develop a standard library of common functionality which frontends can utilize and backends can optimize. Obviously, one cannot consider a library standard if it is heavily tied to attributes of a particular circuit.
With this in mind, the translation IR needs to decouple from both fields/primes and circuit sizes. Rather than generating a new matrix multiplier for each matrix size and each field, a single function should handle all combinations of field and matrix size. In order for this to happen we need to reexamine the IR’s first-class datatypes.
In IR1, the only first-class was a wire, the medium for propagating field elements. In IR2, we’ll need at least three first-classes:
-
Wires
-
Fields
-
Circuit size parameters such as publicly known lengths, arrays, and indices
These three types are the minimum required to implement any standard library functionality. In general, IR2’s core language should be the minimum feature set required to host its standard library.
Switching between Multiple Fields
A particular functionality, which both TA2s are beginning to support and TA1s are eager to adopt, is field switching — the ability for a backend to convert wires from one field to another within a single circuit. Because field switching involves a single circuit mixing fields, this is a further reason to adopt a first-class field type. To go with this a new conversion gate must also be added to the IR’s core.
Encapsulated Datastructures
The IR needs an aggregate type to enable to enable backends to implement and optimize their own datastructures.
Essentially, this type must expose custom behaviors while encapsulating implementation and data.
We’ve been calling this a capsule to distinguish from the object-oriented class terminology (although we’re still thinking about other potential names, like abstraction or interface).
While this capsule type would be polymorphic much like an object-oriented class, there is a key distinction.
A capsule is provided and overridden by the backend — the IR’s interpreter — whereas a class is overridden by subclasses in the same language.
The first formative example we have for this is for ring ZK.
The ring element is encapsulated by the capsule, hidden from the frontend.
The frontend interacts only with the capsule's behaviors: addition, multiplication, etc.
The backends may provide alternative implementations or even replace with a native implementation.
| Multi-Bit Ring Implementation | Large-Field Ring Implementation |
|---|---|
capsule UInt32
private bool bits[32];
@method(add, /* ... */)
/* boolean adder */
@end
@method(mul, /* ... */)
/* boolean multiplier */
@end
@end
|
capsule UInt32
private BigField value;
public currWidth;
@method(add, /* ... */)
/* add, with occasional renormalize */
@end
@method(mul, /* ... */)
/* multiply, with occasional renormalize */
@end
@end
|
This pseudo code should illustrate the capsule, and how it may be polymorphized by the backend.
It is not meant to to illustrate IR2 syntax details; those are yet to be determined.
The second example we have is ZK RAM. In this case, the IR can implement a very naive RAM-like structure, and the backend may either override a native ZK RAM implementation, use a circuit-manipulating RAM reduction during translation, or fall back to the naive implementation.
capsule RAM(Field Elt, Field Idx, public len)
private Elt buffer[len];
@method(get, @in: private Idx idx, @out: private Elt ret)
ret <- Elt(0);
ctr <- Idx(0);
@for e in this.buffer (@modifies ret, ctr)
ret += e * (ctr == idx);
ctr += 1;
@end
@end
@method(set, @in: private Idx idx, private Elt elt,
@modifies: buffer)
/* ... */
@end
@end
Again, the pseudocode is illustrative of the capsule's naivety and the opportunity for backend optimization, rather than exact IR syntax.
Pulling it Back Together
Our team is excited to make right some of what we see as the IR’s shortcomings. We believe that pairing a translation IR with a circuit abstraction is the best solution to cover both varying ZK format preferences amongst TA2s and increased variety of new functionality amongst all TA2s. In developing the IR we want its core to be as minimal a feature set as possible, whilst enabling common functionality to be implemented in shared and standard libraries.