2022-12-11
Recursive arguments are a technique for compressing what would be a linear sized proof into a logarithmic one. They first showed up in the context of electronic voting as a way to prove an honest permutation of ballots and have since been used to build more general succinct arguments.
Given a polynomial \(t(x) \in \mathbb{F}\_q[x]\) we’d like to argue the validity of a commitment to the evaluation of \(t\) at a given point. Polynomial evaluation can be expressed as an inner product of the form \(t(x) = \sum_{i = 0}^{d-1} t_i x^i = \langle \vec{t}, \vec{x} \rangle\) where \(\vec{t} = (t_0, t_1, t_2, \dots, t_{d-1}) \in \mathbb{F}_{q}^{d}\) is a vector of coefficients and \(\vec{x} = (1, x, x^2, \dots, x^{d-1})\) is a vector of successive powers of \(x\).
Fix some cyclic group \(\mathbb{G}\) where the discrete log problem is hard and generate the following public parameters.
# Polynomial degree
d = (1 << 10)
# Curve of prime order
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
E = EllipticCurve(GF(p), [0, 7])
q = E.order()
# Scalar field
K = GF(q)
# Group generators
g = [E.random_element() for _ in range(d)]
h = [E.random_element() for _ in range(d)]
u = E.random_element()The Pedersen hash of two vectors is the group element satisfying
\[P(\vec{t},\vec{x}) = \langle \vec{t}, \vec{g}\rangle + \langle \vec{x}, \vec{h}\rangle \in \mathbb{G}\]
where \(\vec{g}\) and \(\vec{h}\) are the fixed generator vectors defined above. This hash function is desirable because of its additive properties
\[P(\vec{t},\vec{x}) + P(\vec{v},\vec{y}) = P(\vec{t} + \vec{v}, \vec{x} + \vec{y})\]
\[\alpha P(\vec{t},\vec{x}) = P(\alpha \vec{t}, \alpha \vec{x})\]
We can extend this to commit to the inner product of the two vectors
\[\text{com}(\vec{t}, \vec{x}) = P(\vec{t},\vec{x}) + \langle \vec{t}, \vec{x}\rangle u \in \mathbb{G}\]
Where \(u\) is the fixed group generator defined above.
# Inner product
ip = lambda t,x: sum([i*j for (i,j) in zip(t, x)])
# Pedersen hash
com = lambda t,x,g,h: ip(t, g) + ip(x, h) + ip(t, x)*u
# Sample coefficient vectors
t = vector(K, [K.random_element() for _ in range(d)])
x = vector(K, [K.random_element() for _ in range(d)])
# Derive commitment
c = com(t, x, g, h)At this point, we’ve commit to the coefficients of two vectors along with their inner product using a single group element. The next step is to generate a proof of knowledge of this commitment’s pre-image to convince a verifier that \(C\) is of the right form.
# Left half of a vector
L = lambda v: v[:len(v)//2]
# Right half of a vector
R = lambda v: v[len(v)//2:]Let \(\vec{v}\_{L}\) and \(\vec{v}\_{R}\) denote the left and right half of a vector \(\vec{v}\). At each step of the argument, the prover sends two intermediate commitments that account for vectors of half the original size.
\[ \begin{equation} \begin{cases} C_{L} &= \text{com}(\vec{t}_{R}, \vec{x}_{L}, \vec{g}_{L}, \vec{h}_{R}) \in \mathbb{G} \\ C_{R} &= \text{com}(\vec{t}_{L}, \vec{x}_{R}, \vec{g}_{R}, \vec{h}_{L}) \in \mathbb{G} \end{cases} \end{equation} \]
The verifier responds with a random challenge \(r \in \mathbb{F}\_{q}\) which is used to update the parameters for the next step
\[ \begin{equation} \begin{cases} \vec{x} &\leftarrow \vec{x}_{L} + r^{-1}\vec{x}_{R}\\ \vec{g} &\leftarrow \vec{g}_{L} + r^{-1}\vec{g}_{R}\\ \vec{t} &\leftarrow \vec{t}_{L} + r\vec{t}_{R}\\ \vec{h} &\leftarrow \vec{h}_{L} + r\vec{h}_{R}\\ C &\leftarrow r C_{L} + C + r^{-1} C_{R}\\ \end{cases} \end{equation} \]
The trick here is that the last step lets the verifier indirectly compute the updated commitment
\[r C_{L} + C + r^{-1} C_{R} = \text{com}(\vec{t}, \vec{x}, \vec{g}, \vec{h})\]
without ever using the vectors themselves. If we continue to halve at each step, we’ll eventually reach our base case where \(\vec{t}\) and \(\vec{x}\) are of length one. At this point, we send over the two scalars and conclude the proof.
Technical note: as is common with interactive proofs, we apply the Fiat-Shamir transform and replace the random challenge with a hash of the intermediate commitments to make the scheme non-interactive.
# Fiat-Shamir transform
def fst(l, r):
from hashlib import blake2b
# Integer to bytes
i2b = lambda i: i.to_bytes((i.bit_length() + 7) >> 3, 'big')
h = blake2b()
h.update(b'fiat-shamir-transform')
payload = b''.join([i2b(int(i)) for i in l[:] + r[:]])
h.update(payload)
return K(int(h.hexdigest(), base=16))
def prove(t, x, g, h):
if len(t) == 1:
return [t, x]
else:
# Decompose
cL = com(R(t), L(x), L(g), R(h))
cR = com(L(t), R(x), R(g), L(h))
# Derive challenge
r = fst(cL, cR)
r_inv = r^-1
# Update parameters
x = vector(K, L(x)) + r_inv*vector(K, R(x))
g = [i+j for (i,j) in zip(L(g), [r_inv*k for k in R(g)])]
t = vector(K, L(t)) + r*vector(K, R(t))
h = [i+j for (i,j) in zip(L(h), [r*k for k in R(h)])]
return [cL, cR] + prove(t, x, g, h)
proof = prove(t, x, g, h)
assert(len(proof) == 2*log(d, 2) + 2)At this point, the verifier has the following view
The original commitment: \(C \in \mathbb{G}\)
The set of intermediate commitments: \(\\{ C_L^{(i)}, C_R^{(i)} \\}_{0 \leq i \leq \log d}\)
The set of challenge values: \(\\{r_i\\}_{0 \leq i \leq \log d}\)
The verifier proceeds through the set of intermediate commitment pairs, deriving the challenge at each step while keeping track of the updated generator vectors (\(\vec{g}, \vec{h}\)) and commitment \(C\). After reaching the base case, the verifier uses the vectors of length one (\(\vec{t}, \vec{x}\)) to check
\[C \stackrel{?}{=} \text{com}(\vec{t}, \vec{x}, \vec{g}, \vec{h})\]
If this relation holds, the verifier is convinced that (1) the intermediate values were generated honestly and (2) the original commitment is of the correct form.
def verify(c, g, h, proof):
if len(proof) == 2:
t, x = proof[0], proof[1]
return c == com(t, x, g, h)
else:
(cL, cR) = proof[:2]
# Derive challenge
r = fst(cL, cR)
r_inv = r^-1
# Update parameters
g = [i+j for (i,j) in zip(L(g), [r_inv*k for k in R(g)])]
h = [i+j for (i,j) in zip(L(h), [r*k for k in R(h)])]
c = (r*cL) + c + (r_inv*cR)
return verify(c, g, h, proof[2:])
assert(verify(c, g, h, proof))