In the RISC0-ARM, the code to show correctness of the compliance units results in large computational traces, which in turn yields large proving times. For example, the computational trace for compliance units with only 2 resources (the smallest possible size) has roughly 2 million cycles. Under the hood, RISC0 splits the trace in two segments and proves each separately. So, proving correctness of compliance units requires producing at least two STARK proofs, three if the segment proofs are aggregated, and four if the aggregation is wrapped into a groth16 proof (the latter is needed for on-chain verification, so it is the most likely case).
The main source of inefficiency are the constraints related to the delta proof, which involve elliptic curve (EC) operations. In general, emulating EC arithmetic in circuits (zkVMs or any other generic SNARK) is costly, as these are typically non-native operations. In this post I will explain how we can offload EC arithmetic from the compliance unit’s code run inside zkVMs using the sigmabus technique. But we warned: offloading EC arithmetic comes with its own drawbacks and limitations, as we shall see.
Notation. I will use \mathbb{G} to denote a cyclic group of prime order p and \mathbb{F} its scalar field (in practice \mathbb{G} is an elliptic curve). Uppercase letters for group elements G\in\mathbb{G}. Lowercase letters for scalars s\in\mathbb{F}. I will use multiplicative notation for the group operation G_3 = G_1\cdot G_2, and denote vector, or matrices, of objects in bold \mathbf{G},\mathbf{s}. The inner product of two \mathbb{F}-vectors \mathbf{x},\mathbf{y} of the same length n is \langle \mathbf{x}, \mathbf{y}\rangle =\sum_{i=1}^n x_iy_j.
Disclaimer. The post is a bit mathy, I tried my best but there might be typos or errors. Apologize in advance.
Delta proof
The kind of a resource is derived from its logic and label by hashing onto the group, Hash(\mathsf{logic},\mathsf{label})=K \in \mathbb{G}. The quantity of the resource is represented as a scalar q\in\mathbb{F}.
Fix a generator H of \mathbb{G}. A delta proof (delta commitment from now on) for a compliance unit with n resources is a Pedersen commitment D to the vector \mathbf{x}\in\mathbb{F}^n under commitment key (\mathbf{K},H)\in\mathbb{G}^{n+1}. Namely:
where r is the commitment randomness. If the i-th resource is consumed x_i = q_i, and if it is created x_i = -q_i. The only public values are the delta commitment D and the generator H.
In a transaction with c compliance units, we can homomorphically add all resource quantities for the same kind using the m delta commitments. If all the quantities per kind add up to zero, then E= \prod_l^c D_l = H^{\sum r_l}. The delta proof of the transaction consists in a valid ECDSA signature, with generator H, on a challenge message. The prover uses as signing key \mathsf{sk} = \sum_j^c r_j, and the public key is \mathsf{pk} = E= H^{\mathsf{sk}}. This is sound because if for some kind the pertaining quantities do not add up to zero, but still the prover can generate a valid signature, then the prover has found a non-trivial relation between the group elements (\mathbf{K},H); which is highly unlikely because each kind K_i is derived via hashing, and therefore its dlog in base H (or in any base other than K_i) is unknown.
The fact that the kinds \mathbf{K} are private (not known to the verifier), and that the prover cannot know their dlogs in base H, are the main reasons in the limitations of adapting sigmabus in the compliance circuit. More on this later.
Sigmabus
Given a circuit \mathsf{C} that, among other things, exponentiates a group element G resulting in Y = G^y. The idea of the sigmabus paper is to replace \mathsf{C} with another circuit \mathsf{C}' that takes Y as public input. This makes \mathsf{C}' much smaller than \mathsf{C}, and hence proving its satisfiability with a generic SNARK faster. Assuming that dlog_G(Y) is indeed the same scalar y used in the original circuit, then both circuits \mathsf{C}, \mathsf{C}' are functionally equivalent.
To remove the assumption, the prover provides a proof of knowledge of the dlog of Y. Which can be done with the Schnorr protocol, an example of a sigma protocol, whose prover is very efficient: its complexity is dominated by a single exponentiation! A verifying transcript of the Schnorr protocol is the triplet
where y is the witness (secret) dlog of Y, c the verifier’s challenge, and z the prover’s response. The verifier checks
Now, to enforce the same y is used in the sigma protocol and in the circuit \mathsf{C}' the following is also done:
-
the response z and challenge c are passed as public input to \mathsf{C}', and the random scalar s as witness. The additional constraint z \stackrel{?}{=} s+cy over the scalar field \mathbb{F} is enforced in the circuit,
-
the prover could however still compute Y' = G^{y'} for incorrect y' \neq y, run honestly the Schnorr protocol using y' for Y', and pass Y',y',s' = z-y'c to the circuit \mathsf{C}'. To rule out this and other misbehaviours, the prover must commit to y,s (via hashing, using a random salt), and generate the challenge e using the commitments \mathsf{c}_y,\mathsf{c}_s. The commitments are also passed as public inputs to \mathsf{C}' to enforce correct hashing (the salts passed as witness).
The authors also note that their technique can be naturally extended to check linear combination in the exponent, not just exponentiations.
Sigmabus for the compliance circuit
What first comes to mind is to use sigmabus to enforce the linear combination of Eq. (1) above. This would remove EC arithmetic from the compliance circuit. The problem is that if we do so, the kinds \mathbf{K} must be known to the verifier, as they become the basis in the sigma protocol: the verifier needs them to check Eq. (2) with G=K_i.
We could try to use a sigma protocol that treats the basis as witnesses. In principle it is possible, but the obvious way of doing it (at least to me) requires a sigma response Z living in the group not in the scalar field. Since the response is constrained, we’d be back with EC arithmetic in the circuit \mathsf{C}', which is what we are trying to avoid. (I gave up on this direction, but I may be missing something…)
The other possibility is that we change how kinds are generated. So now we are going to hash onto the scalar field. The kind is:
and we set K = G^{k} for some fixed generator. Which means the delta commitment for a compliance unit with n resources in Eq. (1) becomes:
Now it is possible to use the sigmabus technique. We prove knowledge of the scalar y committed in D with a sigma protocol (hashing witnesses and prover’s randomness as described above), and then enforce the inner product constraint y \stackrel{?}{=} \sum_i^n k_i x_i in the compliance circuit using the kind and quantities .
Wait… this is not secure. The dlogs of the basis \mathbf{K} are known. A malicious prover can simply find a non-zero linear combination for all the kinds involved in the final transaction, and derive the quantities from there. In other words, can make an unbalanced transaction pass as balanced.
Adding redundancy
To fix this, we use redundancy. Unfortunately, this means we need to impose an upper bound in the number of resources that participate in a transaction. Say there are up to u resources. For each compliance unit, the prover generates u+1 delta commitments. In the j-th commitment it uses \mathbf{k}^j = (k_1^j,\ldots,k_n^j) to derive the committed scalar y_j:
Recall k_1,\ldots,k_n are the kinds for the n resources of the compliance unit.
If the transaction contains c compliance units, each with delta commitments vector \mathbf{D}_l= (D_{l,0},\ldots, D_{l,u}) for l\leq c, we combine the j-th commitments from each unit the same way as before:
Since all inner products should vanish, an honest prover knows the dlog of all the E_j's in base H. Therefore, they know the dlog of any public linear combination of the E_j's. So, they hash e=Hash(E_1,\ldots,E_u)\in\mathbb{F}, and sign the challenge message with the signing key corresponding to public key E = \prod_{j=0}^{u} E_j^{e^{j+1}}.
Later we will see why the delta proof is sound.
The point is that for each compliance unit, the commitments vector \mathbf{D} = (D_0,\ldots,D_u) is generated off-circuit. The compliance circuit receives them as input, along with their purportedly dlogs and enforces a bunch of inner products constraints between the (positive or negative) quantities and the j-th power of the kinds. These are all constraints over \mathbb{F}.
We have eliminated EC arithmetic in the compliance circuit and replace it with inner product constraints and hashing 
Code and proof format
Prover
For each compliance unit the prover runs code inside and outside what will be proved with the generic SNARK. u is a fixed upper bound, n the number of participating resources in the unit.
Outside the compliance circuit (sigmabus prover)
The prover first computes the u+1 delta commitments. Let us write D_j = G^{y_j}H^{r_j}. It then runs the following non-interactive sigma protocol to prove knowledge of the scalars y_j committed in D_j.
Input:
-
public: generators G,H, delta commitments \mathbf{D}\in\mathbb{G}^{u+1}
-
private: dlogs \mathbf{y} and randomness \mathbf{r} both in \mathbb{F}^{u+1}
Steps:
-
sample \mathbf{y}',\mathbf{r}'\stackrel{\$}{\gets} \mathbb{F}^{u+1}
-
compute S_j = G^{y'_j}H^{r'_j}, for j=0,\ldots,u
-
commit to \mathbf{y}_j,\mathbf{r}_j,\mathbf{y}'_j,\mathbf{r}'_j in \mathsf{comm}, by hashing with a random salt \rho.
-
compute c = Hash(G,H,\mathbf{D},\mathbf{S},\mathsf{comm})\in\mathbb{F} // verifier’s challenge
-
compute \mathbf{z}_1 = \mathbf{y}'+c\mathbf{y} and \mathbf{z}_2 = \mathbf{r}'+c\mathbf{r}
-
the sigmabus proof \pi is \mathsf{comm} and (c,\mathbf{z}_1,\mathbf{z}_2)\in\mathbb{F}^{2u+3}
We have described the communication-efficient version where the first prover’s message (\mathbf{S}) is omitted from the proof \pi.
Inside the compliance circuit
We only list the parts affecting the delta proof. Everything else remains as implemented now.
Input
-
public: delta commitments \mathbf{D}, sigmabus proof \pi=(\mathsf{comm},c,\mathbf{z}_1,\mathbf{z}_2)
-
private:
-
dlogs \mathbf{y} and randomness \mathbf{r}
-
sigmabus prover’s randomness \mathbf{y}',\mathbf{r}' and salt \rho
-
logics, labels, and quantities of the n resources
Steps:
-
compute kinds k_i = Hash(\mathsf{logic}_i,\mathsf{label}_i)\in\mathbb{F} for i = 1,\ldots, n
-
compute k_i^j for j=0,\ldots u. Let \mathbf{k}^j = (k_1^j,\ldots,k_n^j)
-
for the i-th quantity q_i\in\mathbb{F}, if its resource is consumed set x_i = q_i, else set x_i = -q_i
-
enforce y_j \stackrel{?}{=} \langle \mathbf{k}^j,\mathbf{x} \rangle for j=0,\ldots u.
-
enforce \mathsf{comm} \stackrel{?}{=} \mathsf{hash}(\mathbf{y}_j,\mathbf{r}_j,\mathbf{y}'_j,\mathbf{r}'_j,\rho)
-
enforce \mathbf{z}_1 \stackrel{?}{=} \mathbf{y}'+c\mathbf{y} and \mathbf{z}_2 = \mathbf{r}'+c\mathbf{r}
-
(other constraints unrelated to delta proof)
Deriving the signing key
Let r_{l,j} be the randomness used to generate the j-th delta commitment \mathbf{D}_{l,j} in the l-th compliance unit. The signing key is derived as:
-
compute the group elements E_1,\ldots, E_u as in Eq. 3.
-
compute e = Hash(\mathbf{E})\in\mathbb{F}.
-
the signing key is \mathsf{sk} = \sum_{j=0}^{u} e^{j+1}(\sum_{l=1}^c r_{l,j})
Verifier
In addition to verify all the compliance proofs, the verifier also verifies the sigmabus proofs (attached in the transaction) and the signature.
Sigmabus verifier
Inputs:
-
generators G,H, delta commitments \mathbf{D}\in\mathbb{G}^{u+1},
-
sigmabus proof \pi is \mathsf{comm} and (c,\mathbf{z}_1,\mathbf{z}_2)\in\mathbb{F}^{2u+3}
Steps:
-
recompute first messages: S_j = G^{z_{1,j}}H^{z_{2,j}}D_j^{-c} for j = 0,\ldots u
-
check c \stackrel{?}{=} Hash(G,H,\mathbf{D},\mathbf{S},\mathsf{comm})
-
if the check passes accept, else reject
Signature verification
Input:
-
all delta commitment vectors \mathbf{D}_1,\ldots,\mathbf{D}_c from the c compliance units
-
the signature \delta
-
the signed message \mathsf{m}
Steps
-
compute the group elements E_1,\ldots, E_u as in Eq. 3.
-
compute e = Hash(\mathbf{E})\in\mathbb{F}.
-
compute public key \mathsf{pk} = \prod_{j=0}^u E_j^{e^{j+1}}
-
verify \delta on \mathsf{m} using \mathsf{pk}
The new delta proof works and it is sound
We have changed the delta proof. It is in fact a generalization of what we have currently implemented. The main difference is that the exponents of the kind group elements K_i are known. Next we show completeness and soundness for the new delta proof.
Take a transaction with r\leq u resources, and suppose there are d \leq r distinct kinds k_1,\ldots, k_d across these r resources. For each distinct kind k_j, let s_j be the sum of the (positive or negative) resource quantities associated to it.
Why it works
Using linear algebra, it is not difficult to see that after combining each of the u+1 delta commitments from each compliance unit as in Eq. 3, we obtain the following linear system in the exponent of G:
For balanced transactions (honest provers), \mathbf{s} = \mathbf{0}, so also \mathbf{y}=\mathbf{0}, and everything works fine.
Why it is sound
It is sound for the following reasons:
-
If the signature on the linear combination E= \prod_{j=0}^u E_j^{e^{j+1}} is valid, then \mathbf{y}=\mathbf{0}. This follows because the valid signature proves the exponent of E in base G is zero. If it were not, the prover either has found a non-zero dlog relation for G,H, which is believed to be a computational hard problem,or has forged a signature.
-
Now, recall e = Hash(E_0,\ldots,E_u). Thus E is a random linear combination known after the individual E_j's are computed. The probability that any individual y_j = dlog_G(E_j)\neq 0 but dlog_G(E)=0 is u/p by Schwartz-Zippel. (This is a standard argument.) This probability is tiny for a large enough p.
-
The linear system from Eq. 4 defines a map f: \mathbb{F}^d\rightarrow\mathbb{F}^u given by f(\mathbf{s}) = \mathbf{V}\mathbf{s}. Now, s_j truly is the sum of the quantities for a single kind (kind k_j), provided different logics/labels map to different kinds. The latter is true with overwhelming probability as the kinds are generated with a collision-resistant hash function.
-
The linear map f is injective, which means the only preimage of \mathbf{0} is also the zero vector \mathbf{s}=\mathbf{0}. f is injective by construction (and the reason we need to add redundancy). The matrix \mathbf{V} is a Vandermonde matrix, which has rank d because the kinds k_1,\ldots,k_d are pairwise different by definition.
Note the argument above to show the new Delta proof is sound does not degrade security. I mean, it does not introduce new computational assumptions. The new part (second and fourth bullet points) is information-theoretic.
Conclusion
In this post I have explained how to offload EC arithmetic from the compliance circuit. The key idea is defining resource’s kind by hashing to the scalar field instead of hashing to elliptic curve directly, and then add redundancy to argue soundness. We would need to prototype the proposal to confirm it is indeed more efficient than what we currently have.
A final thought: can we avoid redundancy?
Generating u delta commitments per compliance unit is too limiting. Mainly because u is fixed in advance. Can we avoid it?
For soundness, the question is how easy is to find a non-trivial linear combination \langle \mathbf{k},\mathbf{x}\rangle = 0 with \mathbf{x}\neq \mathbf{0}. The vector \mathbf{x} is derived from the quantities, if the quantities are small, say 32-bit integers (currently they are 128-bit integers) it might not be that easy. We could explore further this line of thought.