1# Plonk-CCS (https://eprint.iacr.org/2023/552) Sage prototype
  2
  3# utils
  4def matrix_vector_product(M, v):
  5    n = M.nrows()
  6    r = [F(0)] * n
  7    for i in range(0, n):
  8        for j in range(0, M.ncols()):
  9            r[i] += M[i][j] * v[j]
 10    return r
 11def hadamard_product(a, b):
 12    n = len(a)
 13    r = [None] * n
 14    for i in range(0, n):
 15        r[i] = a[i] * b[i]
 16    return r
 17def vec_add(a, b):
 18    n = len(a)
 19    r = [None] * n
 20    for i in range(0, n):
 21        r[i] = a[i] + b[i]
 22    return r
 23def vec_elem_mul(a, s):
 24    r = [None] * len(a)
 25    for i in range(0, len(a)):
 26        r[i] = a[i] * s
 27    return r
 28# end of utils
 29
 30
 31# can use any finite field, using a small one for the example
 32F = GF(101)
 33#  F = GF(21888242871839275222246405745257275088696311157297823662689037894645226208583)
 34
 35
 36# The following CCS instance values have been provided by Carlos
 37# (https://github.com/CPerezz) and Edu (https://github.com/ed255),
 38# and this sage script was made to check the CCS relation.
 39
 40## Checks performed by this Plonk/CCS instance:
 41# - binary check for x0, x1
 42# - 2*x2 + 2*x3 == x4
 43M0 = matrix([
 44    [F(0),   1, 0, 0, 0, 0, 0],
 45    [0,   0, 1, 0, 0, 0, 0],
 46    [0,   0, 0, 1, 0, 0, 0],
 47    [0,   0, 0, 0, 0, 0, 1],
 48    ])
 49M1 = matrix([
 50    [F(0),   1, 0, 0, 0, 0, 0],
 51    [0,   0, 1, 0, 0, 0, 0],
 52    [0,   0, 0, 0, 1, 0, 0],
 53    [0,   0, 0, 0, 0, 0, 1],
 54    ])
 55M2 = matrix([
 56    [F(0),   1, 0, 0, 0, 0, 0],
 57    [0,   0, 1, 0, 0, 0, 0],
 58    [0,   0, 0, 0, 0, 1, 0],
 59    [0,   0, 0, 0, 0, 0, 1],
 60    ])
 61M3 = matrix([
 62    [F(1), 0, 0, 0, 0, 0,   0],
 63    [1, 0, 0, 0, 0, 0,   0],
 64    [0, 0, 0, 0, 0, 0,   0],
 65    [0, 0, 0, 0, 0, 0,   0],
 66    ])
 67M4 = matrix([
 68    [F(0), 0, 0, 0, 0, 0,   0],
 69    [0, 0, 0, 0, 0, 0,   0],
 70    [2, 0, 0, 0, 0, 0,   0],
 71    [0, 0, 0, 0, 0, 0,   0],
 72    ])
 73M5 = matrix([
 74    [F(0), 0, 0, 0, 0, 0,   0],
 75    [0, 0, 0, 0, 0, 0,   0],
 76    [2, 0, 0, 0, 0, 0,   0],
 77    [0, 0, 0, 0, 0, 0,   0],
 78    ])
 79M6 = matrix([
 80    [F(-1), 0, 0, 0, 0, 0,   0],
 81    [-1, 0, 0, 0, 0, 0,   0],
 82    [-1, 0, 0, 0, 0, 0,   0],
 83    [0, 0, 0, 0, 0, 0,    0],
 84    ])
 85M7 = matrix([
 86    [F(0), 0, 0, 0, 0, 0,   0],
 87    [0, 0, 0, 0, 0, 0,   0],
 88    [0, 0, 0, 0, 0, 0,   0],
 89    [0, 0, 0, 0, 0, 0,   0],
 90    ])
 91
 92z = [F(1), 0, 1, 2, 3, 10, 42]
 93
 94print("z:", z)
 95
 96assert len(z) == M0.ncols()
 97
 98# CCS parameters
 99n = M0.ncols() # == len(z)
100m = M0.nrows()
101t=8
102q=5
103d=3
104S = [[3,0,1], [4,0], [5,1], [6,2], [7]]
105c = [1, 1, 1, 1, 1]
106
107M = [M0,M1,M2,M3,M4,M5,M6,M7]
108
109print("CCS values:")
110print("n: %s, m: %s, t: %s, q: %s, d: %s" % (n, m, t, q, d))
111print("M:", M)
112print("z:", z)
113print("S:", S)
114print("c:", c)
115
116# check CCS relation (this is agnostic to Plonk, for any CCS instance)
117r = [F(0)] * m
118for i in range(0, q):
119    hadamard_output = [F(1)]*m
120    for j in S[i]:
121        hadamard_output = hadamard_product(hadamard_output,
122                matrix_vector_product(M[j], z))
123
124    r = vec_add(r, vec_elem_mul(hadamard_output, c[i]))
125
126print("\nCCS relation check (∑ cᵢ ⋅ ◯ Mⱼ z == 0):", r == [0]*m)
127assert r == [0]*m