Run the compressed (non-zero) proof of knowledge of the response vector as described in the Protocol 4 in the paper. The relation in this proof is Q = g_hat * z_hat + k * L_tilde(z_hat) and knowledge of z_hat needs to be proven but the proof is not zero-knowledge
(
mut z_hat: Vec<G::ScalarField>,
mut g_hat: Vec<G>,
k: &G,
mut L_tilde: L,
)
| 117 | /// Protocol 4 in the paper. The relation in this proof is Q = g_hat * z_hat + k * L_tilde(z_hat) |
| 118 | /// and knowledge of z_hat needs to be proven but the proof is not zero-knowledge |
| 119 | pub fn compressed_response<D: Digest, L: LinearForm<G::ScalarField>>( |
| 120 | mut z_hat: Vec<G::ScalarField>, |
| 121 | mut g_hat: Vec<G>, |
| 122 | k: &G, |
| 123 | mut L_tilde: L, |
| 124 | ) -> Response<G> { |
| 125 | let mut bytes = vec![]; |
| 126 | |
| 127 | let mut As = vec![]; |
| 128 | let mut Bs = vec![]; |
| 129 | |
| 130 | // There are many multiplications done with `k`, so creating a table for it |
| 131 | let lg2 = z_hat.len() & (z_hat.len() - 1); |
| 132 | let k_table = WindowTable::new(lg2, k.into_group()); |
| 133 | |
| 134 | // In each iteration of the loop, size of `z_hat`, `g_hat` and `L_tilde` is reduced by half |
| 135 | while z_hat.len() > 2 { |
| 136 | let m = g_hat.len(); |
| 137 | // Split `g_hat` into 2 halves, `g_hat` will be the 1st half and `g_hat_r` will be the 2nd |
| 138 | let g_hat_r = g_hat.split_off(m / 2); |
| 139 | // Split `z_hat` into 2 halves, `z_hat` will be the 1st half and `z_hat_r` will be the 2nd |
| 140 | let z_hat_r = z_hat.split_off(m / 2); |
| 141 | // Split `L_tilde` into 2 halves, `L_tilde_l` will be the 1st half and `L_tilde_r` will be the 2nd |
| 142 | let (L_tilde_l, L_tilde_r) = L_tilde.split_in_half(); |
| 143 | |
| 144 | // A = g_hat_r * z_hat_l + k * L_tilde_r(z_hat_l) |
| 145 | let A = G::Group::msm_unchecked(&g_hat_r, &z_hat) |
| 146 | + k_table.multiply(&L_tilde_r.eval(&z_hat)); |
| 147 | |
| 148 | // B = g_hat_l * z_hat_r + k * L_tilde_l(z_hat_r) |
| 149 | let B = G::Group::msm_unchecked(&g_hat, &z_hat_r) |
| 150 | + k_table.multiply(&L_tilde_l.eval(&z_hat_r)); |
| 151 | |
| 152 | A.serialize_compressed(&mut bytes).unwrap(); |
| 153 | B.serialize_compressed(&mut bytes).unwrap(); |
| 154 | let c = field_elem_from_try_and_incr::<G::ScalarField, D>(&bytes); |
| 155 | let c_repr = c.into_bigint(); |
| 156 | |
| 157 | // Set `g_hat` as g' in the paper |
| 158 | g_hat = g_hat |
| 159 | .iter() |
| 160 | .zip(g_hat_r.iter()) |
| 161 | .map(|(l, r)| (l.mul_bigint(c_repr) + r).into_affine()) |
| 162 | .collect::<Vec<_>>(); |
| 163 | // Set `L_tilde` to L' in the paper |
| 164 | L_tilde = L_tilde_l.scale(&c).add(&L_tilde_r); |
| 165 | // Set `z_hat` as z' in the paper |
| 166 | z_hat = z_hat |
| 167 | .iter() |
| 168 | .zip(z_hat_r.iter()) |
| 169 | .map(|(l, r)| *l + *r * c) |
| 170 | .collect::<Vec<_>>(); |
| 171 | As.push(A); |
| 172 | Bs.push(B); |
| 173 | } |
| 174 | |
| 175 | Response { |
| 176 | z_prime_0: z_hat[0], |