changed 2 years ago  
Published Linked with GitHub

Taken from https://hackmd.io/WIobK-QvS3enrzc33PD_2Q?both=, this was written by arnaucube.

R1CS to CCS overview

  • R1CS instance: \(S_{R1CS} = (m, n, N, l, A, B, C)\)
  • CCS instance: \(S_{CCS} = (m, n, N, l, t, q, d, M, S, c)\)
  • R1CS-to-CCS parameters:
    \(n=n,~ m=m,~ N=N,~ l=l,~ t=3,~ q=2,~ d=2\)
    \(M=\{A,B,C\}\), \(S=\{\{0,~1\},~ \{2\}\}\), \(c=\{1,-1\}\)

Then, we can see that the CCS relation:
\[\sum_{i=0}^{q-1} c_i \cdot \bigcirc_{j \in S_i} M_j \cdot z ==0\]

in our R1CS-to-CCS parameters is equivalent to

\[c_0 \cdot ( (M_0 z) \circ (M_1 z) ) + c_1 \cdot (M_2 z) ==0\\ \Longrightarrow 1 \cdot ( (A z) \circ (B z) ) + (-1) \cdot (C z) ==0\\ \Longrightarrow ( (A z) \circ (B z) ) - (C z) ==0\]

which is equivalent to the R1CS relation: \(Az \circ Bz == Cz\)

Sage prototype

The following code implements in Sage the translation of R1CS into CCS by following the description from page 4 of the CCS paper.

To run it:

  • need Sage installed
  • copy&paste the follwing code into a sage file (eg. r1cs-to-ccs.sage)
  • and then run it by > sage r1cs-to-ccs.sage
# R1CS-to-CCS (https://eprint.iacr.org/2023/552) Sage prototype

# utils
def matrix_vector_product(M, v):
    n = M.nrows()
    r = [F(0)] * n
    for i in range(0, n):
        for j in range(0, M.ncols()):
            r[i] += M[i][j] * v[j]
    return r
def hadamard_product(a, b):
    n = len(a)
    r = [None] * n
    for i in range(0, n):
        r[i] = a[i] * b[i]
    return r
def vec_add(a, b):
    n = len(a)
    r = [None] * n
    for i in range(0, n):
        r[i] = a[i] + b[i]
    return r
def vec_elem_mul(a, s):
    r = [None] * len(a)
    for i in range(0, len(a)):
        r[i] = a[i] * s
    return r
# end of utils


# can use any finite field, using a small one for the example
F = GF(101)

# R1CS matrices for: x^3 + x + 5 = y (example from article
# https://www.vitalik.ca/general/2016/12/10/qap.html )
A = matrix([
    [F(0), 1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 0],
    [5, 0, 0, 0, 0, 1],
    ])
B = matrix([
    [F(0), 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    ])
C = matrix([
    [F(0), 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0],
    ])

print("R1CS matrices:")
print("A:", A)
print("B:", B)
print("C:", C)


z = [F(1), 3, 35, 9, 27, 30]
print("z:", z)

assert len(z) == A.ncols()

n = A.ncols() # == len(z)
m = A.nrows()
#  l = len(io) # not used for now

# check R1CS relation
Az = matrix_vector_product(A, z)
Bz = matrix_vector_product(B, z)
Cz = matrix_vector_product(C, z)
print("\nR1CS relation check (Az ∘ Bz == Cz):", hadamard_product(Az, Bz) == Cz)
assert hadamard_product(Az, Bz) == Cz


# Translate R1CS into CCS:
print("\ntranslate R1CS into CCS:")

# fixed parameters (and n, m, l are direct from R1CS)
t=3
q=2
d=2
S1=[0,1]
S2=[2]
S = [S1, S2]
c0=1
c1=-1
c = [c0, c1]

M = [A, B, C]

print("CCS values:")
print("n: %s, m: %s, t: %s, q: %s, d: %s" % (n, m, t, q, d))
print("M:", M)
print("z:", z)
print("S:", S)
print("c:", c)

# check CCS relation (this is agnostic to R1CS, for any CCS instance)
r = [F(0)] * m
for i in range(0, q):
    hadamard_output = [F(1)]*m
    for j in S[i]:
        hadamard_output = hadamard_product(hadamard_output,
                matrix_vector_product(M[j], z))

    r = vec_add(r, vec_elem_mul(hadamard_output, c[i]))

print("\nCCS relation check (∑ cᵢ ⋅ ◯ Mⱼ z == 0):", r == [0]*m)
assert r == [0]*m
Select a repo