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 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} = ⟨ \vec{t}, \vec{x} ⟩

where

\vec{t} = (t_{0}, t_{1}, t_{2}, \dots, t_{d - 1}) \in 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

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

Pedersen Hash

P (\vec{t}, \vec{x}) = ⟨ \vec{t}, \vec{g} ⟩ + ⟨ \vec{x}, \vec{h} ⟩ \in 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})

com (\vec{t}, \vec{x}) = P (\vec{t}, \vec{x}) + ⟨ \vec{t}, \vec{x} ⟩ u \in G

# 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{aligned} C_{L} & = com ({\vec{t}}_{R}, {\vec{x}}_{L}, {\vec{g}}_{L}, {\vec{h}}_{R}) \in G \\ C_{R} & = com ({\vec{t}}_{L}, {\vec{x}}_{R}, {\vec{g}}_{R}, {\vec{h}}_{L}) \in G \end{aligned}

The verifier responds with a random challenge

r \in F_q

which is used to update the parameters for the next step

\begin{aligned} \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{aligned}

The trick here is that the last step lets the verifier indirectly compute the updated commitment

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)

The Verifier’s View

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

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

Public Parameters

Pedersen Hash

Recursive Argument

The Verifier’s View

References