Recursive Arguments


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\).

Public Parameters

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
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()

Pedersen Hash

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)

Recursive Argument

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()
    payload = b''.join([i2b(int(i)) for i in l[:] + r[:]])
    return K(int(h.hexdigest(), base=16))

def prove(t, x, g, h):
    if len(t) == 1:
        return [t, x]
        # 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)

The Verifier’s View

At this point, the verifier has the following view

  1. The original commitment: \(C \in \mathbb{G}\)

  2. The set of intermediate commitments: \(\\{ C_L^{(i)}, C_R^{(i)} \\}_{0 \leq i \leq \log d}\)

  3. 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)
        (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))