Index Mathematics Conjectures nbv lettuce Widgets

slip_r1cs_arg_verify

stdlib/slip/slip_r1cs_arg_verify.nbv

slip_r1cs_arg_verify(static wtns_len, static r_a, static r_b, static r_c, static kappa, static k, static k_gamma, static transcript_id, static a_s, static a_l, static la_absorb, static la_exp, vec)

Verifier of the dags SLIP R1CS argument (sumcheck version, dags slip/spec.pdf sections "Protocol", "R1CS" and "As-Is Binary Regions", binary opening challenges) as an nbv program, for recursion.

vec is the output of dags SLIPR1CSArg::into_vector: the widths n_s, n_l, the row and witness masks as bits, then every term in transcript order: T_s, T_l, the linear claims, the round polynomials round by round (r1cs sumcheck then linear sumcheck, D base elements per extension coefficient, D = ext_degree()), the row evaluations (quadratic then linear witness) and the openings. The widths and masks become public statics, so the circuit is specialized to one layout; like the dags verifier it accepts any layout with heights at most the field's binding capacity. The transcript is replayed with the lattice sponge (stdlib/lattice), which matches dags Oraccle<LatticeSponge<H>> for the field's squeeze, so this verifier exists in every field with lattice_permutation and ext_degree shims (Mersenne61, Milli and Dilithium).

Calls
dilithium/ext/ext_degree, ext/ext_eq_eval, ext/ext_eq_table, ext/ext_mle_eval, ext/ext_mul, ext/ext_mul_base, ext/ext_one, ext/ext_poly_eval, ext/ext_recompose, ext/ext_sum, inner_prod, lattice/lattice_bits, lattice/lattice_oraccle_commit, lattice/lattice_oraccle_init, lattice/lattice_oraccle_sample_vec, mat_vec_mul, ext/mle_eq_table, r1cs/r1cs_into_output, slice, slice_from_start, slip/slip_mask_transcript, slip/slip_placements, split_at, sum, bits/to_bits_exact, valloc
Precompiles
assert_eq!, assert_lt!, assert_lte!, chunks_sum_map!, clone!, concat!, constrain_eq!, div_ceil!, div_exact!, div_floor!, field_bit_width!, flat_map!, if_lt!, into_public_static!, len!, log2_ceil!, loop!, loop_flat_map!, shadow_loop!

Source

# Verifier of the dags SLIP R1CS argument (sumcheck version, dags slip/spec.pdf sections
# "Protocol", "R1CS" and "As-Is Binary Regions", binary opening challenges) as an nbv
# program, for recursion.
#
# `vec` is the output of dags SLIPR1CSArg::into_vector: the widths n_s, n_l, the row and
# witness masks as bits, then every term in transcript order: T_s, T_l, the linear claims,
# the round polynomials round by round (r1cs sumcheck then linear sumcheck, D base elements
# per extension coefficient, D = ext_degree()), the row evaluations (quadratic then linear
# witness) and the openings. The widths and masks become public statics, so the circuit is
# specialized to one layout; like the dags verifier it accepts any layout with heights at
# most the field's binding capacity. The transcript is replayed with the lattice sponge
# (stdlib/lattice), which matches dags Oraccle<LatticeSponge<H>> for the field's squeeze, so
# this verifier exists in every field with `lattice_permutation` and `ext_degree` shims
# (Mersenne61, Milli and Dilithium).
(
  # r1cs constraint matrices, including the output and field safety rows
  static wtns_len,
  static r_a,
  static r_b,
  static r_c,
  # dags SLIPParams and SLIPChallenges::transcript_id of the argument
  static kappa,
  static k,
  static k_gamma,
  static transcript_id,
  # SIS matrices, row major kappa x n_s and kappa x n_l (dags sis_matrix)
  static a_s,
  static a_l,
  # lattice sponge matrices (dags LatticeSponge::matrices), absorption then expansion
  static la_absorb,
  static la_exp,
  vec
)

static e = field_bit_width!
# extension degree of the sumcheck challenges, round polynomials and row evaluations
static d = ext_degree()
# dags SLIPParams::binding_capacity: 2^floor((log2(q) - 1) / 2) with log2(q) = e - 1, at most
# 4096
static capacity_bits = div_floor! e - 2, 2
static mut binding_capacity = 1
loop! capacity_bits, i {
  binding_capacity = binding_capacity * 2
}
if_lt! 4096, binding_capacity {
  binding_capacity = 4096
}
static height = div_exact! (len! r_a), wtns_len
assert_eq! height, div_exact! (len! r_b), wtns_len
assert_eq! height, div_exact! (len! r_c), wtns_len

# check that r1cs is well formed and extract conjectured outputs
(static output, static indices) = r1cs_into_output(wtns_len, ...clone! r_a, r_b, r_c)

##################################################
# layout: the widths and masks are public

(let n_s, let vec) = split_at(1, vec)
(let n_l, let vec) = split_at(1, vec)
(let rows_mask, let vec) = split_at(height, vec)
(let wtns_mask, let vec) = split_at(wtns_len, vec)
static n_s = into_public_static! n_s
static n_l = into_public_static! n_l
static rows_mask = into_public_static! rows_mask
static wtns_mask = into_public_static! wtns_mask
assert_lt! 0, n_s
assert_lt! 0, n_l
loop! height, i {
  assert_lte! rows_mask[i], 1
}
loop! wtns_len, i {
  assert_lte! wtns_mask[i], 1
}

static u_s = sum(clone! rows_mask)
static u_l = sum(clone! wtns_mask)
static c_s = div_ceil! height - u_s, n_s
static d_s = div_ceil! u_s, n_s
static c_l = div_ceil! wtns_len - u_l, n_l
static d_l = div_ceil! u_l, n_l
static r_s = 3 * e * c_s + 3 * d_s
static r_l = e * c_l + d_l
static blocks_s = c_s + d_s
static blocks_l = c_l + d_l
assert_lte! r_s, binding_capacity
assert_lte! r_l, binding_capacity
assert_eq! kappa * n_s, (len! a_s), "slip quadratic SIS matrix dimension"
assert_eq! kappa * n_l, (len! a_l), "slip linear SIS matrix dimension"
# sumcheck variables: the bits of a column index
static vars_s = log2_ceil! n_s
static vars_l = log2_ceil! n_l
static mut rounds = vars_s
if_lt! vars_s, vars_l {
  rounds = vars_l
}

(static row_block, static row_col) = slip_placements((clone! rows_mask), n_s, c_s)
(static wtns_block, static wtns_col) = slip_placements((clone! wtns_mask), n_l, c_l)

(let t_s, let vec) = split_at(r_s * kappa, vec)
(let t_l, let vec) = split_at(r_l * kappa, vec)
(let claims, let vec) = split_at(k_gamma, vec)
# 4 extension coefficients per r1cs sumcheck round, 3 per linear sumcheck round
(let round_polys, let vec) = split_at(d * (4 * vars_s + 3 * vars_l), vec)
(let v_s, let vec) = split_at(d * r_s, vec)
(let v_l, let vec) = split_at(d * r_l, vec)
(let z_s, let vec) = split_at(k * n_s, vec)
(let z_l, let vec) = split_at(k * n_l, vec)
assert_eq! 0, (len! vec), "slip argument has unconsumed elements"

##################################################
# transcript, in the order of dags SLIPR1CSArg

let state = lattice_oraccle_init()
let state = lattice_oraccle_commit("slip_r1cs_argument", state)
let state = lattice_oraccle_commit([n_s c_s d_s n_l c_l d_l transcript_id], state)
let state = lattice_oraccle_commit(slip_mask_transcript(clone! rows_mask), state)
let state = lattice_oraccle_commit(slip_mask_transcript(clone! wtns_mask), state)
let state = lattice_oraccle_commit((clone! t_s), state)
let state = lattice_oraccle_commit((clone! t_l), state)

# aggregation challenges of every repetition from one squeeze: per repetition rho (vars_s),
# psi (one per quadratic witness block), delta, beta, lambda
let state = lattice_oraccle_commit("slip_aggregation", state)
static per_rep = vars_s + blocks_s + 3
(let state, let agg) = lattice_oraccle_sample_vec(k_gamma * per_rep, state, (clone! la_absorb), (clone! la_exp))

# the linear claims and the batching challenge mu
let state = lattice_oraccle_commit("slip_linear_claims", state)
let state = lattice_oraccle_commit((clone! claims), state)
(let state, let mu) = lattice_oraccle_sample_vec(d, state, (clone! la_absorb), (clone! la_exp))

# mu^m for m in [k_gamma]
let mu_pows = ext_one()
shadow_loop! k_gamma - 1, m {
  let mu_pows = concat! (clone! mu_pows), ext_mul(slice((clone! mu_pows), d * m, d), clone! mu)
}

# initial claims: the r1cs sumcheck claims sum_m mu^m lambda_m S_m, the linear sumcheck
# sum_m mu^m S_m
let mut claim_l = ext_sum(loop_flat_map! k_gamma, m {
  ext_mul_base(slice((clone! mu_pows), d * m, d), claims[m])
})
let mut claim_s = ext_sum(loop_flat_map! k_gamma, m {
  static lambda_i = m * per_rep + vars_s + blocks_s + 2
  ext_mul_base(slice((clone! mu_pows), d * m, d), claims[m] * agg[lambda_i])
})

##################################################
# sumcheck rounds: round j carries the r1cs round polynomial (while j < vars_s) then the
# linear one (while j < vars_l), and the challenges in the same order from one squeeze

let mut point_s[d * vars_s]
let mut point_l[d * vars_l]
static mut pos = 0
shadow_loop! rounds, j {
  static mut count = 0
  static mut poly_len = 0
  if_lt! j, vars_s {
    count = count + 1
    poly_len = poly_len + 4 * d
  }
  if_lt! j, vars_l {
    count = count + 1
    poly_len = poly_len + 3 * d
  }
  let polys = slice((clone! round_polys), pos, poly_len)
  pos = pos + poly_len
  let state = lattice_oraccle_commit("slip_sumcheck_round", state)
  let state = lattice_oraccle_commit([j], state)
  let state = lattice_oraccle_commit((clone! polys), state)
  (let state, let chal) = lattice_oraccle_sample_vec(d * count, state, (clone! la_absorb), (clone! la_exp))
  static mut off = 0
  if_lt! j, vars_s {
    let poly = slice((clone! polys), 0, 4 * d)
    # s(0) + s(1) = claim
    constrain_eq! (clone! claim_s), slice((clone! poly), 0, d) + ext_sum(clone! poly)
    let r = slice((clone! chal), 0, d)
    claim_s = ext_poly_eval(poly, clone! r)
    loop! d, c {
      point_s[d * j + c] = r[c]
    }
    off = 4 * d
  }
  if_lt! j, vars_l {
    let poly = slice((clone! polys), off, 3 * d)
    constrain_eq! (clone! claim_l), slice((clone! poly), 0, d) + ext_sum(clone! poly)
    let r = slice((clone! chal), d * (count - 1), d)
    claim_l = ext_poly_eval(poly, clone! r)
    loop! d, c {
      point_l[d * j + c] = r[c]
    }
  }
}

let state = lattice_oraccle_commit("slip_sumcheck_evaluations", state)
let state = lattice_oraccle_commit((clone! v_s), state)
let state = lattice_oraccle_commit((clone! v_l), state)

##################################################
# final check of the r1cs sumcheck: the batched polynomial at the row evaluations

# (a, b, c) of every quadratic witness block at the point: recomposed from the bit rows of
# the decomposed blocks, the three rows of the as-is blocks
# (row offsets o count rows, D coefficients each)
let block_values = concat! (loop_flat_map! c_s, blk {
  static o = 3 * e * blk
  concat! ext_recompose(slice((clone! v_s), d * o, d * e)), ext_recompose(slice((clone! v_s), d * (o + e), d * e)), ext_recompose(slice((clone! v_s), d * (o + 2 * e), d * e))
}), (loop_flat_map! d_s, blk {
  static o = 3 * e * c_s + 3 * blk
  slice((clone! v_s), d * o, 3 * d)
})
assert_eq! 3 * d * blocks_s, len! block_values

# a b - c per block, and w (1 - w) per row, shared by the repetitions
let ab_c = loop_flat_map! blocks_s, blk {
  static o = 3 * d * blk
  ext_mul(slice((clone! block_values), o, d), slice((clone! block_values), o + d, d)) - slice((clone! block_values), o + 2 * d, d)
}
let binary = loop_flat_map! r_s, i {
  let w = slice((clone! v_s), d * i, d)
  ext_mul((clone! w), ext_one() - w)
}

let r1cs_final = ext_sum(loop_flat_map! k_gamma, m {
  static base = m * per_rep
  let rho = slice((clone! agg), base, vars_s)
  let psi = slice((clone! agg), base + vars_s, blocks_s)
  let delta = agg[base + vars_s + blocks_s]
  let beta = agg[base + vars_s + blocks_s + 1]
  let lambda = agg[base + vars_s + blocks_s + 2]
  let delta2 = delta * delta
  # a + delta b + delta^2 c per block
  let abc_lin = loop_flat_map! blocks_s, blk {
    static o = 3 * d * blk
    slice((clone! block_values), o, d) + ext_mul_base(slice((clone! block_values), o + d, d), delta) + ext_mul_base(slice((clone! block_values), o + 2 * d, d), delta2)
  }
  let quadratic = ext_mle_eval((clone! psi), clone! ab_c)
  let linear = ext_mle_eval(psi, abc_lin)
  # beta^i for i in [r_s]
  let beta_pows = [1]
  shadow_loop! r_s - 1, i {
    let beta_pows = concat! (clone! beta_pows), beta_pows[i] * beta
  }
  let binary_m = ext_mle_eval(beta_pows, clone! binary)
  let eq_m = ext_eq_eval(rho, clone! point_s)
  ext_mul(ext_mul(eq_m, quadratic + binary_m + ext_mul_base(linear, lambda)), slice((clone! mu_pows), d * m, d))
})
constrain_eq! claim_s, r1cs_final

##################################################
# the aggregated linear constraint phi of every repetition, split into the blocks of the
# linear witness, and the final check of the linear sumcheck

# position of every witness entry in the blocks, 0 for padding
static n_len = blocks_l * n_l
static mut phi_pos[n_len]
loop! wtns_len, j {
  phi_pos[wtns_block[j] * n_l + wtns_col[j]] = j + 1
}

let eq_l = ext_eq_table(clone! point_l)
# x_b of every linear witness block at the point
let x_values = concat! (loop_flat_map! c_l, b {
  ext_recompose(slice((clone! v_l), d * e * b, d * e))
}), (loop_flat_map! d_l, b {
  slice((clone! v_l), d * (e * c_l + b), d)
})
assert_eq! d * blocks_l, len! x_values

let linear_final = ext_sum(loop_flat_map! k_gamma, m {
  static base = m * per_rep
  let gamma = slice_from_start(mle_eq_table(slice((clone! agg), base, vars_s)), n_s)
  let psi = slice((clone! agg), base + vars_s, blocks_s)
  let delta = agg[base + vars_s + blocks_s]
  let delta2 = delta * delta
  # tau_i = psi_block(i) gamma_col(i)
  let tau = loop_flat_map! height, i {
    psi[row_block[i]] * gamma[row_col[i]]
  }
  let tau_d = (clone! tau) * valloc(height, delta)
  let tau_d2 = (clone! tau) * valloc(height, delta2)
  # phi = tau^T (A + delta B + delta^2 C)
  let phi = (chunks_sum_map! (clone! r_a), wtns_len, row, i {
    row * valloc(wtns_len, tau[i])
  }) + (chunks_sum_map! (clone! r_b), wtns_len, row, i {
    row * valloc(wtns_len, tau_d[i])
  }) + (chunks_sum_map! (clone! r_c), wtns_len, row, i {
    row * valloc(wtns_len, tau_d2[i])
  })
  let phi_chunks = loop_flat_map! n_len, p {
    static src = phi_pos[p]
    let mut out[1]
    if_lt! 0, src {
      out = phi[src - 1]
    }
    out
  }
  # <phi_b, eq(r', .)> x_b summed over the blocks
  let terms = loop_flat_map! blocks_l, b {
    ext_mul(ext_mle_eval(slice((clone! phi_chunks), b * n_l, n_l), clone! eq_l), slice((clone! x_values), d * b, d))
  }
  ext_mul(ext_sum(terms), slice((clone! mu_pows), d * m, d))
})
constrain_eq! claim_l, linear_final

##################################################
# openings: binary challenge matrices from one squeeze, the low e - 1 bits of every element,
# set after set and column after column; then the SIS, norm and evaluation checks

let state = lattice_oraccle_commit("slip_opening", state)
static bits_per_element = e - 1
static total = r_s * k + r_l * k
static elements = div_ceil! total, bits_per_element
(let state, let entropy) = lattice_oraccle_sample_vec(elements, state, (clone! la_absorb), (clone! la_exp))
let all_bits = slice_from_start((flat_map! entropy, v {
  slice_from_start(lattice_bits(v), bits_per_element)
}), total)
let c_s_bits = slice((clone! all_bits), 0, r_s * k)
let c_l_bits = slice(all_bits, r_s * k, r_l * k)

let eq_s = slice_from_start(ext_eq_table(point_s), d * n_s)
let eq_l = slice_from_start(eq_l, d * n_l)

static norm_bits_s = log2_ceil! 2 * r_s + 1
loop! k, j {
  let c_j = slice((clone! c_s_bits), j * r_s, r_s)
  let z_j = slice((clone! z_s), j * n_s, n_s)
  # A z =? sum_i c_i t_i
  let t_c = loop_flat_map! kappa, row {
    inner_prod((clone! c_j), loop_flat_map! r_s, i {
      t_s[i * kappa + row]
    })
  }
  constrain_eq! mat_vec_mul((clone! a_s), (clone! z_j)), t_c
  # z + r in [0, 2^b)
  loop! n_s, l {
    let _ = to_bits_exact(z_j[l] + r_s, norm_bits_s)
  }
  # <z, eq(r, .)> =? sum_i c_i v_i
  constrain_eq! ext_mle_eval(z_j, (clone! eq_s)), ext_mle_eval(c_j, clone! v_s)
}

static norm_bits_l = log2_ceil! 2 * r_l + 1
loop! k, j {
  let c_j = slice((clone! c_l_bits), j * r_l, r_l)
  let z_j = slice((clone! z_l), j * n_l, n_l)
  let t_c = loop_flat_map! kappa, row {
    inner_prod((clone! c_j), loop_flat_map! r_l, i {
      t_l[i * kappa + row]
    })
  }
  constrain_eq! mat_vec_mul((clone! a_l), (clone! z_j)), t_c
  loop! n_l, l {
    let _ = to_bits_exact(z_j[l] + r_l, norm_bits_l)
  }
  constrain_eq! ext_mle_eval(z_j, (clone! eq_l)), ext_mle_eval(c_j, clone! v_l)
}

(output, indices)