Index Mathematics Conjectures nbv lettuce Widgets

Specification, adapted from src/commitments/slip/spec.tex in lettuce

Succinct Lattice Inner Product

1 Sketch

The LaBRADOR argument of knowledge [3] introduces the concept of dot product constraints of the form:

⋅˜∈ℤq/(XN+1)
∑i,jra˜ij⟨w˜i,w˜j⟩+∑ir⟨𝝓˜i,w˜i⟩=b˜

We propose a modified protocol operating entirely in the scalar field ℤq with q=261−1 (Mersenne61). The protocol has three layers:

  1. An SIS (Ajtai) commitment to the rows of a binary witness matrix, ti=Awi. This is the only source of binding.
  2. A sumcheck [2] over the column index of the witness. The constraints on the witness are aggregated with uniform challenges into a single sum over the columns, which the sumcheck reduces to the evaluation of every witness row at one random point. The aggregation challenges are in ℤq and repeated; the round challenges come from the cubic extension 𝔽=𝔽q3 so that the rounds resist grinding under Fiat-Shamir (Section 5.4). The round polynomials and the evaluations are sent in the clear and are bound to the witness by the final step.
  3. An amortized opening with short integer challenges, z=∑iciwi. The verifier checks z against the SIS commitment and against the row evaluations.

The opening challenges are binary. A binary challenge space is small, so k independent random combinations are opened, but every difference of two challenges is ±1 on a single row and the extracted openings are exact short preimages (Section 5.2). Larger short challenge sets would need fewer openings but carry an extraction slack, the property LaBRADOR obtains from short invertible ring challenges, and are not used.

Earlier versions of this document sent Gram matrices of the witness, r2 elements per aggregation challenge, in place of the sumcheck. The sumcheck sends O(log⁡n+r) elements per aggregation repetition, so the witness can be tall and narrow, which shrinks the openings.

Zero knowledge is not a goal of this protocol: the openings reveal the witness.

2 Protocol

2.1 Notation and Parameters

Bold indicates vector, bold uppercase indicates matrix. Vectors are column vectors. a∘b is the element-wise product. Elements of ℤq are compared and normed through their centered representatives in (−q2,q2), and |x|∞ is the largest centered absolute value of an entry.

Sumcheck. For a polynomial P of degree at most d in each of ℓ variables, the sumcheck protocol [2] reduces the claim ∑l∈{0,1}ℓP(l)=S to one evaluation of P. In round j∈[ℓ] the prover sends the univariate polynomial sj(t)=∑l′∈{0,1}ℓ−j−1P(r0,...,rj−1,t,l′) as d+1 coefficients in 𝔽, the verifier checks sj(0)+sj(1)=Sj against the current claim S0=S, samples rj←$𝔽 and sets Sj+1=sj(rj). After the last round the verifier checks Sℓ=P(r). A false claim passes with probability at most dℓ/q3. When P is built from multilinear extensions of vectors, P(r) is a function of the vectors’ evaluations u˜(r)∈𝔽, which the prover sends and the verifier checks against the commitment. The prover’s tables are over ℤq in the first round and over 𝔽 after the first fold.

2.2 Commitment

Prover commits to each row of the witness with the SIS matrix:

Awi→ti∈T∈ℤqr×κ

Prover sends T→ verifier.

2.3 Aggregation

The relation to argue is given as a polynomial F of degree at most 2 in the row values, typically a random combination of quadratic constraints with coefficients sampled here, and a claimed value S of its sum over the columns. Verifier samples kγ independent repetitions, m∈[kγ], of

𝝆(m)←$ℤqℓ,β(m)←$ℤq

together with the coefficients of F(m), and sends them to prover. 𝝆(m) weights the columns through eq(𝝆(m),⋅), the role the uniform vector 𝜸 played in earlier versions, and β(m) separates the rows of the binary witness check. Both parties agree on the claim

∑l∈{0,1}ℓeq(𝝆,l)[F(w1(l),...,wr(l))+∑irβiwi(l)(1−wi(l))]=S(1)

writing wi(l) for the entry of row i in column l. The second term is the binary witness check: it vanishes identically when W is binary, and the random β and 𝝆 make a non-binary row detectable (Section 5.4). The prover sends the claimed values S(m) (when they are not implied), then verifier samples a batching challenge μ←$𝔽 and the kγ claims are combined into one:

∑l∈{0,1}ℓ∑mkγμmeq(𝝆(m),l)[F(m)(w1(l),...,wr(l))+∑irβ(m)iwi(l)(1−wi(l))]=∑mkγμmS(m)(2)

The repetitions share the witness rows and differ in their eq vectors, so the batched polynomial has the same degree as a single one and the prover folds one copy of the witness.

2.4 Sumcheck

Prover and verifier run the sumcheck of (2): the polynomial has degree 3 in each variable, so round j consists of one polynomial of 4 coefficients in 𝔽 sent by prover, then one challenge rj∈𝔽 sent by verifier. After the last round prover sends the row evaluations at the challenge point:

w˜i(r)→vi∈v∈𝔽r

2.5 Opening

Verifier samples a binary challenge matrix C←${0,1}r×k with columns c(1),...,c(k) and sends it to prover. (Non-interactively, the entries are the low e−1 bits of ⌈rk/(e−1)⌉ transcript oracle elements, a fixed shape that a circuit can reproduce; each bit is biased by at most 2e−1/q.) Prover opens k random combinations of the witness rows:

W⊤C→Z∈ℤqn×k,z(j)=∑irci(j)wi

Prover sends Z→ verifier. As integers 0≤z(j)≤r.

2.6 Verification

Verifier runs the sumcheck checks: in round j, sj(0)+sj(1)=?Sj, and after the last round

Sℓ=?∑mkγμmeq(𝝆(m),r)[F(m)(v1,...,vr)+∑irβ(m)ivi(1−vi)]sumcheck final check(3)

where eq(𝝆(m),r) costs ℓ multiplications in 𝔽.

For each opening j∈[k], writing z=z(j) and c=c(j), verifier checks:

Az=?T⊤c=∑ircitiopening of the SIS commitment(4)
|z|∞≤?rnorm check(5)
⟨z,eq(r,⋅)⟩=?∑irci⋅vievaluation check(6)

The norm check is implemented as the range zl+r∈[0,2b) with b=⌈log2⁡(2r+1)⌉, which a circuit checks with a bit decomposition; it allows positive entries up to about 2r, which the norm bounds below absorb. Equation (4) with (5) binds every opening to the commitment T, so z=∑iciw¯i for the extracted rows w¯i (Section 5.2). The evaluations v are fixed before C is sampled, and the left hand side of (6) is ∑iciw¯˜i(r), so (6) is a degree one check in c that forces vi=w¯˜i(r) (Section 5.3). Given correct evaluations, the sumcheck forces (2) to hold for the extracted witness, which forces every repetition’s claim (1) unless μ is a root of a nonzero polynomial of degree kγ−1, and (1) is a random combination over (𝝆,β,coefficients of F) of every constraint and every row’s binarity, zero for a bad witness with probability about (ℓ+r)/q per repetition (Section 5.4).

The verifier’s work on the openings is kκn multiplications for (4) and 3kn for (6) (products of ℤq by 𝔽), plus one vector eq(r,⋅) of which the first n entries are used. The earlier pairwise Gram checks, k2n multiplications, are gone.

3 R1CS

Given a rank one constraint system (R1CS) defined as the matrices 𝒜︀,ℬ︀,𝒞︀∈ℤqc×w, and which is satisfied by any vector x∈ℤqw such that:

𝒜︀x⋅ℬ︀x−𝒞︀x=0∈ℤqc

All indices in this section start at 0. Define a bit decomposition function which accepts a vector and decomposes each element to bits vertically as a matrix, and a vector chunking function which splits a vector into l chunks of equal length, padding the final chunk with zeroes:

to_bits:ℤqm→{0,1}e×m,chunks:(l,ℤqm)→ℤql×⌈ml⌉

We construct the argument from two witnesses. All quadratically related variables, the values 𝒜︀x,ℬ︀x,𝒞︀x, are stored in the quadratic witness W(s). The variables themselves, x, are stored in the linear witness W(l). Each is split into column chunks stacked vertically, c(s) for the quadratic and c(l) for the linear witness, which trades the width of the openings against the height of the commitments and evaluations (Section 4). The witness dimensions are:

r(s)=3ec(s),n(s)=⌈cc(s)⌉,r(l)=ec(l),n(l)=⌈wc(l)⌉,ℓs=⌈log2⁡n(s)⌉,ℓl=⌈log2⁡n(l)⌉

The program is padded with zero rows to height c(s)n(s) and with zero columns to width c(l)n(l), and x is padded with zeroes to length c(l)n(l). Padded rows are trivially satisfied, and padded entries of x do not affect any constraint.

Witnesses. Write aa, ba, ca for chunk a of 𝒜︀x, ℬ︀x, 𝒞︀x under chunks(c(s),⋅), and xb for chunk b of chunks(c(l),x). The witnesses are stacks of blocks:

W(s)=[W0(s)⋮Wc(s)−1(s)]∈{0,1}r(s)×n(s),Wa(s)=[to_bits(aa)to_bits(ba)to_bits(ca)]
W(l)=[to_bits(x0)⋮to_bits(xc(l)−1)]∈{0,1}r(l)×n(l)

Block a of the quadratic witness occupies rows o=3ea to o+3e−1 and block b of the linear witness occupies rows eb to eb+e−1. The recomposed values of a block are the multilinear combinations of its rows

a¯a=∑ie2iwo+i(s),b¯a=∑ie2iwo+e+i(s),c¯a=∑ie2iwo+2e+i(s),x¯b=∑ie2iweb+i(l)

which for an honest prover are aa, ba, ca, xb. Their multilinear extensions are the same combinations of the rows’ extensions. The linear witness only enters through linear relations, so it needs to be short (for the SIS opening) but not binary.

Commitment. Prover sends

T(s)=W(s)A(s)⊤,T(l)=W(l)A(l)⊤

with A(s)∈ℤqκ×n(s) and A(l)∈ℤqκ×n(l).

Aggregation. For m∈[kγ] verifier samples

𝝆(m)←$ℤqℓs,𝝍(m)←$ℤqc(s),δ(m),β(m),λ(m)←$ℤq

and both parties compute 𝜸(m)=eq(𝝆(m),⋅)∈ℤqn(s), the column weights. The weight can only depend on the column, which is shared by every block of W(s); 𝝍(m) separates the blocks and δ(m) separates 𝒜︀,ℬ︀,𝒞︀. Each R1CS row an(s)+l gets the coefficient

τan(s)+l(m)=ψa(m)γl(m),𝝉(m)∈ℤqc(s)n(s)

and both parties compute the combined linear constraint vector, split into chunks matching the linear witness:

𝝉(m)⊤𝒜︀+δ(m)⋅𝝉(m)⊤ℬ︀+δ(m)2⋅𝝉(m)⊤𝒞︀→𝝓(m)⊤∈ℤqc(l)n(l),chunks(c(l),𝝓(m))→𝚽(m)∈ℤqc(l)×n(l)(7)

Prover sends the linear claim of every repetition, the value of the combined linear constraints on the witness:

⟨𝝓(m),x¯⟩=∑bc(l)⟨𝝓b(m),x¯b⟩→S(m)∈ℤq

and verifier samples the batching challenge μ←$𝔽.

Sumchecks. Two sumchecks are run, each batching every repetition, with the prover’s rows as the tables. The r1cs sumcheck, over the columns of the quadratic witness, has degree 3 per variable and claims

∑l∈{0,1}ℓs∑mkγμmeq(𝝆(m),l)[∑ac(s)ψa(m)(a¯a(l)b¯a(l)−c¯a(l))+∑ir(s)β(m)iwi(s)(l)(1−wi(s)(l))+λ(m)∑ac(s)ψa(m)(a¯a(l)+δ(m)b¯a(l)+δ(m)2c¯a(l))]=∑mkγμmλ(m)S(m)(8)

The first term is the quadratic constraints of every block, the second the binary witness check, the third the left hand side of the linear consistency with the linear witness, which equals ⟨𝝓(m),x¯⟩ for a consistent witness. The witness dependent products a¯ab¯a and wi(1−wi) are shared by the repetitions, so the batching costs the prover little. The linear sumcheck, over the columns of the linear witness, has degree 2 per variable and claims

∑l∈{0,1}ℓl∑mkγμm∑bc(l)𝝓b(m)(l)x¯b(l)=∑mkγμmS(m)(9)

Both sumchecks run in lockstep: transcript round j carries the round polynomial of the r1cs sumcheck (4 coefficients in 𝔽, while j<ℓs) then of the linear sumcheck (3 coefficients, while j<ℓl), followed by the challenges rj,rj′←$𝔽 in the same order. After the last round prover sends the row evaluations at the two challenge points:

w˜i(s)(r)→v(s)∈𝔽r(s),w˜i(l)(r′)→v(l)∈𝔽r(l)

Opening. Verifier samples C(s)←${0,1}r(s)×k and C(l)←${0,1}r(l)×k and prover sends

Z(s)=W(s)⊤C(s)∈ℤqn(s)×k,Z(l)=W(l)⊤C(l)∈ℤqn(l)×k

Verification. Verifier runs the round checks of both sumchecks. The final check of the r1cs sumcheck is (3) with the bracket of (8) evaluated at v(s), with a¯a=∑ie2ivo+i(s) and so on. The final check of the linear sumcheck is

Sℓl′=?∑mkγμm∑bc(l)𝝓˜b(m)(r′)∑ie2iveb+i(l),𝝓˜b(m)(r′)=⟨𝝓b(m),eq(r′,⋅)⟩(10)

where the verifier evaluates the public chunks 𝝓b(m) itself, 3n(l) multiplications per chunk, no more than computing 𝝓(m) in the first place. For the quadratic witness verifier runs (4), (5) and (6) with r=r(s) and (A(s),T(s),Z(s),C(s),v(s),r), and for the linear witness with r=r(l) and (A(l),T(l),Z(l),C(l),v(l),r′).

Correctness. With binary W(s) the binary term of (8) vanishes, the quadratic term of repetition m is ∑aψa∑lγl(a¯alb¯al−c¯al)=0 for a satisfying witness, and its linear term is λ∑a,lτan(s)+l(a¯al+δb¯al+δ2c¯al)=λ𝝉⊤(𝒜︀+δℬ︀+δ2𝒞︀)x¯=λ⟨𝝓,x¯⟩=λS(m). The sum of repetition m in (9) is ⟨𝝓(m),x¯⟩=S(m) by definition.

Soundness. Section 5: the openings bind v(s),v(l) to the extracted witnesses (error 2ϵ1k over both witnesses), given correct evaluations the sumchecks force (8) and (9) for the extracted witness (error (3ℓs+2ℓl)/q3), the batching forces them for every repetition (error 2(kγ−1)/q3), and for a repetition the left hand side of (8) minus λ⟨𝝓,x¯⟩ is a nonzero polynomial of degree at most ℓs+r(s)+4 in the challenges of the repetition whenever the extracted witness is not binary, violates a quadratic constraint, or is inconsistent between the two witnesses. The error per repetition is

ϵagg=ℓs+r(s)+4q

Proof size. About

(r(s)+r(l))κ+kγ+3(4ℓs+3ℓl+r(s)+r(l))+k(n(s)+n(l))

elements of ℤq (three per element of 𝔽), linear in the heights and in the widths. Section 4 describes how to choose the dimensions.

3.1 As-Is Binary Regions

In many circuits most witness entries and most constraint values are 0 or 1. In SHAKE256 every entry of x is a bit, and all but one row have (𝒜︀x)i,(ℬ︀x)i,(𝒞︀x)i∈{0,1}. Bit decomposing such a value costs e witness cells, of which e−1 are zero. Instead the prover stores binary values as is, in regions of the witness matrices that are not recomposed with powers of two. Booleanity is not detected from the R1CS (compilers fold it into linear combinations); the prover chooses the regions from the witness values, and soundness does not depend on the choice.

Masks. Prover chooses a row mask 𝝁(s)∈{0,1}c and a witness mask 𝝁(l)∈{0,1}w. The honest choice is μi(s)=1 exactly when (𝒜︀x)i,(ℬ︀x)i,(𝒞︀x)i∈{0,1}, and μj(l)=1 exactly when xj∈{0,1}. The masks are sent with T(s),T(l), before any aggregation challenge, and cost c+w bits.

Layout. Rows with μi(s)=0, taken in increasing order, fill the decomposed region of W(s) exactly as before: the row at position p goes to block ⌊p/n(s)⌋, column pmodn(s). Rows with μi(s)=1 fill the as-is region in the same way, where as-is block a is the three rows

Wo′(s),Wo′+1(s),Wo′+2(s)=a¯a,b¯a,c¯a,o′=3ec(s)+3a

holding the values themselves. Witness entries are placed the same way in W(l): entries with μj(l)=0 are bit decomposed into blocks of e rows, entries with μj(l)=1 fill as-is blocks of a single row placed after the decomposed rows. With u(s)=|{i:μi(s)=1}| and u(l)=|{j:μj(l)=1}|:

c(s)=⌈c−u(s)n(s)⌉,d(s)=⌈u(s)n(s)⌉,r(s)=3ec(s)+3d(s)
c(l)=⌈w−u(l)n(l)⌉,d(l)=⌈u(l)n(l)⌉,r(l)=ec(l)+d(l)

The prover chooses the widths n(s),n(l) (Section 4 describes how) and sends them with the masks; the block counts follow. Soundness depends on the layout only through the heights, which enter the norm bounds, so the verifier accepts any widths with r(s),r(l)≤Rmax, a protocol parameter from which the SIS norm bound is computed (Section 5.5), and does not need to reproduce the prover’s choice. Unused cells are zero. With all-zero masks this is the layout above.

Aggregation. 𝝍(m)∈ℤqc(s)+d(s) has one entry per block of either region, as-is block a using ψc(s)+a(m). Row i placed in block β (of either region), column l, gets τi(m)=ψβ(m)γl(m), and 𝝓(m) is computed from 𝝉(m) as in (7). It is split into one chunk 𝝓β(m)∈ℤqn(l) per block β of W(l), holding the entries of 𝝓(m) for the witness entries placed in that block, at their columns, and S(m) sums over all these chunks.

Sumchecks. In every repetition the r1cs sumcheck (8) gains the as-is blocks with weight 1 in place of 2i: the quadratic term ∑ad(s)ψc(s)+a(wo′(l)wo′+1(l)−wo′+2(l)) and the linear term λ∑ad(s)ψc(s)+a(wo′(l)+δwo′+1(l)+δ2wo′+2(l)), and the binary term already covers every row. The linear sumcheck (9) gains ∑bd(l)𝝓c(l)+b(l)wec(l)+b(l)(l). The final checks read the as-is rows of v directly in the same way.

Soundness. The masks are fixed before the aggregation challenges are sampled, and the argument of Section 3 goes through for every choice of masks. The binary check forces every row of W(s) to be binary, so the as-is quadratic term is ∑lγl(a¯alb¯al−c¯al) on the values themselves. The linear witness needs no binary check: an as-is entry is read directly as xj′, and the extracted x′ satisfies the R1CS whatever its values. A mask choice can therefore only affect completeness: a non-binary as-is value in W(s) fails the binary check, and a large as-is entry in W(l) fails the norm check. Small non-binary entries of W(l) pass the norm check and may also be stored as is. ϵagg is unchanged with the heights above.

Proof size. About

(r(s)+r(l))κ+kγ+3(4ℓs+3ℓl+r(s)+r(l))+k(n(s)+n(l))+c+we

elements of ℤq, with the heights above. For SHAKE256 the heights shrink by about a factor e for the same widths.

Witness dependent shape. The layout depends on the witness values, so the proof shape and verifier work can vary between witnesses of the same circuit. A recursive verifier with a static circuit needs a fixed layout, e.g. masks fixed by the program.

4 Witness Layout

The proof size of Section 3.1 is linear in the heights, through the SIS commitments (κ per row) and the evaluations (3 per row), and linear in the widths through the openings (k per column). With the cell count of a witness fixed by the program, rn≈N, the size r(κ+3)+kn is minimized at r≈kN/(κ+3), which is tall: with κ=16 and k=131 a column costs about seven times a row. For all but small programs this exceeds Rmax and the heights are set by Rmax instead, the widths following as N/Rmax. The sumcheck rounds, 4ℓs+3ℓl per repetition, are negligible.

The prover chooses the widths n(s),n(l) by enumerating, for each region of each witness, the widths that give 1,2,... blocks, discarding the combinations with r(s)>Rmax or r(l)>Rmax, and taking the pair with the smallest estimated size. The estimate is the proof size formula with kγ recomputed for each candidate (it depends on ℓs,r(s) through ϵagg) and the masks left out, which are the same for every layout. The search is deterministic in the mask counts so the verifier could reproduce it, but need not: it accepts any widths within Rmax.

For a random R1CS with decomposed regions only, in Mersenne61 with Rmax=4096, κ=16:

c=wc(s),n(s)c(l),n(l)k,kγelementsGram version
10420,50035,286131,32.1⋅1051.1⋅106
5⋅10522,2272867,7463131,34.1⋅1061.5⋅107

The last column is the size the Gram matrix version of this protocol reached with its own optimal layout. The openings are now the dominant term, so a larger Rmax (with a correspondingly larger SIS norm bound) is what would shrink the proof further.

5 Cryptanalysis

This section analyzes the protocol of Section 2 and its R1CS instantiation in Section 3 over q=261−1. Checks on the same challenge do not multiply, the overall soundness error is a sum of the error terms below.

5.1 Binding of the Opening

Equation (4) with the norm check (5) is an opening of an SIS commitment. The openings of a column only depend on that column’s challenge through the check, so given two accepting transcripts (C,Z), (C′,Z′) whose challenge matrices satisfy cj−cj′=Δei for some column j and Δ≠0, with the other columns arbitrary, the openings of column j satisfy

A(zj−zj′)=Δ⋅ti,|zj−zj′|∞≤2r

with Δ=±1 for binary challenges, so w¯i=Δ(zj−zj′) is an exact short opening of ti. Two such openings of the same ti differ by an SIS solution of ℓ∞ norm at most 4r, so w¯i is determined by ti.

5.2 Knowledge Extraction

Fix the prover’s randomness and everything up to the opening challenge, so T, the round polynomials and the evaluations v(m) are fixed. Let X={0,1}r be the challenge space of one column, m=|𝒞︀|=2, N=|X|=mr, and let S⊆Xk be the set of challenge matrices the prover answers acceptably, ϵ=|S|/Nk. For a column j and a value c∈X write ρj(c) for the density of S among the matrices with j-th column c (the other columns uniform). A direction-i line is a set {c+tei} of m column values differing only in row i.

To extract row i the extractor needs an accepting pair with cj−cj′=Δei for some column j, i.e. two accepting matrices whose j-th columns lie on the same direction-i line. It samples a base C∈S and then, for a column j and another value c′ on the direction-i line through cj, samples matrices with j-th column c′ and fresh uniform other columns until one is accepted. This succeeds quickly when some line mate c′ of some column has ρj(c′)≥τ.

Lemma 1. For every row i and τ>0, the probability over a uniform base C∈S that, for every column j, every other value on the direction-i line through cj has ρj<τ is at most (m−k+kτ)/ϵ.

Proof. Call a column value heavy if ρj≥τ and light otherwise. A base with the stated property has, in every column j, either a light j-th column or a heavy j-th column all of whose line mates are light. Heavy values with only light line mates are at most one per line, so at most N/m per column, and bases of the second kind in every column number at most (N/m)k. Bases of the first kind in some column j carry mass ∑light cρj(c)Nk−1<τNk, so at most kτNk in total. Divide by |S|=ϵNk. ∎

With τ=ϵ/(4k) the probability is at most m−k/ϵ+14, so for ϵ≥4m−k at least half of the bases have a line mate of density at least ϵ/(4k) in some column. Trying the k(m−1) line mates in round robin finds an accepting partner after O(k2m/ϵ) prover invocations in expectation; rows that fail are retried from a fresh base. Every row is extracted independently, so the extractor obtains exact openings w¯i, with |w¯i|∞≤2r, of every row of both witnesses with O(rk2/ϵ) invocations, whenever ϵ≥4ϵ1k (ϵ1=1/2). This is the knowledge error of the opening round, of the same order as the evaluation binding terms of Section 5.3.

For an accepting opening z∗ with challenge column c∗, the vector z∗−∑ici∗w¯i is an integer vector in the kernel of A of ℓ∞ norm at most r+2r2, hence zero unless it is an SIS solution of that norm. So z∗=∑ici∗w¯i in ℤqn for every accepting opening, which is what the next subsection assumes. The binary witness check then forces every row of W¯(s) into {0,1}n, and the R1CS relation is over ℤq, so the linear witness W¯(l) needs no integrality beyond being short.

5.3 Binding of the Sumcheck Evaluations

By Section 5.2 every accepting opening equals z=∑iciw¯i for the extracted rows, unless SIS is broken. The evaluations v are fixed before C is sampled, so the evaluation check (6) reads

∑irci(w¯˜i(r)−vi)=0∈𝔽

Write ϵ1=12: a uniform column c∈{0,1}r is orthogonal to a fixed nonzero u∈𝔽r with probability at most ϵ1, because for a coordinate i with ui≠0 and any values of the other coordinates at most one value of ci satisfies ⟨c,u⟩=0. A wrong v therefore passes one column with probability at most ϵ1, and all k columns with probability at most ϵ1k. The R1CS argument checks two witnesses, so all evaluations are correct except with probability 2ϵ1k.

The pairwise Gram checks of earlier versions, which needed (k+1)ϵ1k and set k=136, are no longer needed: nothing quadratic in the witness is sent, the quadratic constraints are evaluated inside the sumcheck on the evaluations.

5.4 Soundness of the R1CS Argument

Fix the extracted witnesses W¯(s),W¯(l) and suppose the evaluations are correct. The linear sumcheck (9) ends in the verifier’s own evaluation of the public 𝝓b(m) and the bound x¯b(r′), so by the sumcheck soundness its batched claim holds for the extracted witness except with probability 2ℓl/q3, and then S(m)=⟨𝝓(m),x¯⟩ for every m unless μ is a root of a nonzero polynomial of degree kγ−1, probability (kγ−1)/q3. Likewise the r1cs sumcheck forces the sum of (8) over the extracted witness except with probability 3ℓs/q3, and the batching forces every repetition’s sum to equal λ(m)S(m) except with probability (kγ−1)/q3. For a repetition m both together say that

F(𝝆,𝝍,δ,β,λ):=∑leq(𝝆,l)[Q(l)+B(l)]+λ(∑leq(𝝆,l)L(l)−⟨𝝓,x¯⟩)=0

with Q,B,L the quadratic, binary and linear terms of the bracket of (8) for repetition m. F is a polynomial in the ℤq challenges of the repetition, all sampled after T(s),T(l), i.e. after the extracted witness is fixed. Its degree is at most ℓs in 𝝆 (∑leq(𝝆,l)ul is the multilinear extension u˜(𝝆)), 1 in 𝝍, 2 in δ, r(s)−1 in β and 1 in λ, so at most ℓs+r(s)+4 in total. It is nonzero for a bad witness:

By Schwartz-Zippel F=0 with probability at most

ϵagg=ℓs+r(s)+4q

per repetition, and all kγ independent repetitions pass a bad extracted witness with probability at most ϵaggkγ. The total soundness error is bounded by

ϵ≤6ϵ1k+ϵaggkγ+3ℓs+2ℓl+2(kγ−1)q3+Advκ,n,q,βSIS

with the 4ϵ1k of the extractor (Lemma 1), 2ϵ1k of the evaluation binding, and the SIS norm bound β≈2r2 in ℓ∞ from Section 5.2.

Fiat-Shamir. After the Fiat-Shamir transform an attacker can grind whole transcripts, so the error of every squeeze has to be below 2−128 on its own, and errors of different squeezes do not compose. The squeezes and their errors are: the aggregation challenges of all repetitions, ϵaggkγ (every repetition sits behind the one squeeze); the batching challenge μ, (kγ−1)/q3 per sumcheck; each r1cs sumcheck round, 3/q3; each linear sumcheck round, 2/q3; the opening challenge, 6ϵ1k. The round challenges are why 𝔽 is needed: with rj∈ℤq a prover holding a bad witness could, in round j, send a polynomial with the correct sum sj(0)+sj(1) but otherwise free coefficients and grind them until rj is a root of sj−sj∗, which takes about q/3≈259 squeezes and puts the sumcheck on a true claim from then on. Repeating the sumcheck in ℤq does not help, since nothing forces the rescues of different repetitions into the same round: they add work instead of multiplying the error. With rj∈𝔽 the same attack costs q3/3≈2181 squeezes. The aggregation challenges can stay in ℤq because the repetitions sit behind a single squeeze and the claims of all of them are batched before any round challenge is sampled.

Row separators. The powers βi cost one squeeze and r(s) multiplications but put the degree r(s)−1 into ϵagg. Sampling an independent βi per row would reduce the degree to 1 and ϵagg to about (ℓs+6)/q at the cost of r(s) squeezes per repetition; for Mersenne61 both give kγ=3.

5.5 Parameters for Mersenne61

Openings. Every extracted row is an exact opening. The norm check is |z|∞≤r, two openings of the same ti differ by at most 2r in ℓ∞, and the kernel vector z∗−∑ici∗w¯i has ℓ∞ norm at most r+2r2. The number of openings is the smallest k with 6⋅2−k≤2−128,

k=131

so about 131(n(s)+n(l)) field elements of openings.

Repetitions. The prover chooses the witness widths, so the heights are only known to satisfy r≤Rmax. With Rmax=212 and widths up to 215, ϵagg≤(15+4096+4)/q≈2−49, so kγ=3 gives ϵagg3≈2−147; kγ=2 gives only about 2−98. The implementation computes kγ from the actual ℓs,r(s) of the layout, which for Mersenne61 is 3 for every layout within Rmax. The extension field terms are at most (3⋅15+2⋅15+4)/q3≈2−176.

SIS. The size optimizer drives the heights to Rmax for all but small programs (Section 4), so the norm bound is computed at Rmax: 2Rmax2=225 in ℓ∞, and with n≤220 about β≈235 in ℓ2 (the norm check range adds at most another factor 4). A larger Rmax costs SIS security directly. κ is not fixed here: it should be set with a lattice estimator for SISκ,n,q,β at the witness width n. The proof size is about

(r(s)+r(l))κ+kγ+3(4ℓs+3ℓl+r(s)+r(l))+k(n(s)+n(l))

elements of ℤq.

5.6 Open Items

  1. SIS parameters. κ for each witness width, from a lattice estimator. With the heights at Rmax the trade between Rmax, κ and the openings should be revisited.
  2. Appendix A has not been revised to the SIS opening or the sumcheck; it still uses uniform 𝝂 challenges, short sum-of-rows commitments and Gram matrices, which are not binding on their own.
  3. Fiat-Shamir. Section 5.4 bounds the error of every squeeze; a formal knowledge soundness proof of the non-interactive protocol remains to be written down.
  4. Prover memory. The prover folds the tables of both witnesses, one copy for all repetitions; after the first fold they live in 𝔽 (three elements per cell) at half the width. The first round is computed from the ℤq tables.

6 (Non)-Existence of Infinite and Finite Oracles

Infinite length oracles do not exist by combinatorial bounds on information and computation. Finite oracles can be proven neither to exist nor not to exist, but a lower bound on the probability of non-existence can be realized by taking the number of distinguishable states of reality as the maximum oracle output length. Denote λ(M), the distance of a simulated oracle from a theoretical oracle for an output equal in length to the number of distinguishable states of reality M. Concretely this may be taken as something like the Lloyd bound M≈2399 or the holographic storage bound M≈2406. We apply a conservative bound and take M=|energy|⋅|matter|, defined as the product of the number of distinguishable states of energy and the distinguishable states of matter. Taking each as 2256 we get M=2256⋅2256=2512.

6.1 Probable Finite Oracles

Given x∈ℤqm an output vector of length m from a simulated oracle. Call 𝝌∈ℤqm output from a corresponding theoretical oracle. Call λℓ1(m)=⟨1,|x−𝝌|⟩ the linear distance from the simulated oracle to the theoretical oracle for an output of length m. A simulated oracle is statistically likely to exist provided Pr⁡[λℓ1(m)=0]>1−1M. Oracles with Pr⁡[λℓ1(M)=0]>1−1M are statistically indistinguishable from theoretical oracles for all representable simulations of the oracle.

6.2 Infinite Oracles do not Exist

The maximum length of a theoretical oracle is bounded by emergence and dissolution of free energy by big bang and heat death respectively. Oracles exist as a function of information, therefore time is finite relative to oracles as information ceases to exist after heat death, as entropy exists maximally. Time continues to exist, but the arrow of time (a product of information and entropy), ceases to exist. This is analagous to time becoming an algebraic object without total order: points in time become comparable only by equality and relative distance, not by direction. By the existence of entropy, at a point in time forward relative to time itself, total order will emerge in time, at which point entropy is locally minimized and information emerges (a big bang event). Therefore, non-existence of information does not preclude knowledge extraction by quantum observers, which are capable of observing time relative to time itself as a function of their own existence and non-existence.

A Hypersphere Relations

Not yet revised to the SIS opening. The subsections below are the earlier hypersphere constructions. On their own they are not binding: their responses are checked only through a few scalar inner products, so a prover can solve for them after seeing the challenge. Composed with the SIS commitment of Section 2 they become meaningful, because every opening is pinned to the committed witness. In particular the anti-podal point of an opening is an opening of the bitwise complement: for c¯=∑ici,

A(c¯⋅1−z)=c¯⋅A1−T⊤c

so the verifier can check openings of W!=1−W without a second commitment.

A.1 Space Efficient Linear Relations From Short Vectors

Given a witness matrix W∈{0,1}r×n prover forms two commitments representing the sums of rows and sums of columns respectively:

∑irwi→t∈ℤn
⟨wi,1⟩→ti′∈t′∈ℤr

Prover sends t,t′→ verifier and verifier samples 𝝂←$ℤqr and 𝝂′←$ℤqn. Prover computes challenge commitments:

W⊤𝝂→z∈ℤqn
W𝝂′→z′∈ℤqr

Prover sends z,z′→ verifier and verifier checks the following relations:

|t|∞≤?r|t′|∞≤?n
⟨t,1⟩=?⟨t′,1⟩transposition linear structure check
⟨z′,1⟩=?⟨t,𝝂′⟩challenge linear cross check (1)
⟨z,1⟩=?⟨t′,𝝂⟩challenge linear cross check (2)
⟨z,𝝂′⟩=?⟨z′,𝝂⟩argument of transposition relation

Iff 𝝂,𝝂′ are sampled randomly after t,t′ commitment, and r,n≪q, the inner products form two SIS instances on lattice bases that are random relative to the preimage. Computing the inner product is an evaluation of a randomly selected member of the universal hash function family ℋ︀A(x)=Ax. Thus the evaluation of ⟨t,𝝂′⟩ and ⟨t′,𝝂⟩ are each concrete random oracle queries by the leftover hash lemma.

A.2 Space Efficient Additive Inverse Linear Relations

The previous section describes representing a witness matrix as a relation between the matrix and its transposition. This introduces problems with dimensions and multiplicative combinations. A more efficient approach uses two witness matrices such that A+B=1 and A⋅B=0. Given a binary witness matrix W∈{0,1}r×n define the bitwise not matrix W!∈{0,1}r×n such that W+W!=1 and W⋅W!=0.

Prover begins by forming short commitments to the witness matrix:

W⊤⋅1→t∈|ℤqn|∞≤r
W⋅1→g∈|ℤqr|∞≤n

Prover sends t,g→ verifier and verifier samples 𝝂←$ℤqr. Prover forms a vertical challenge commitment:

W⊤⋅𝝂→z∈ℤqn

Prover sends z→ verifier and verifier samples 𝝉←$ℤqn. Prover forms a horizontal challenge commitment:

W⋅𝝉→𝜻∈ℤqr

Prover sends 𝜻→ verifier and verifier checks the following relations:

⟨t,1⟩=?⟨g,1⟩binary structure check
⟨z,1⟩=?⟨g,𝝂⟩linear structure check
⟨𝜻,1⟩=?⟨t,𝝉⟩linear structure check
⟨𝜻,𝝂⟩=?⟨z,𝝉⟩argument of r⋅n independent linear relations

Verifier then interprets z and 𝜻 as points on two boolean hyperspheroids with basis vectors 𝝂 and 𝝉 respectively, each of cardinality r⋅n. Verifier selects the antipodal point to get element-wise boolean negation of the witness on the hypersphere:

r⋅𝝂−z→z!∈ℤqnanti-podal point on 𝝂 boolean hypersphere
n⋅𝝉−𝜻→𝜻!∈ℤqranti-podal point on 𝝉 boolean hypersphere

Verifier can then compute the expected SIS preimages using linear operations:

r⋅1−t→t!∈ℤnbitwise negation in a one-dimensional space
n⋅1−g→g!∈ℤrbitwise negation in a one-dimensional space

Verifier then checks the following relations:

⟨z!,1⟩=?⟨g!,𝝂⟩bitwise inversion linear check
⟨𝜻!,1⟩=?⟨t!,𝝉⟩bitwise inversion linear check
⟨z!,𝝉⟩=?⟨𝜻!,𝝂⟩bitwise inversion random linear relation

The short commitments t and g represent a binary matrix as r+n short elements, formed as two vectors: the sums of rows and the sums of columns.

TODO: formally analyze the cardinality of a theoretical solution space given the verifier equations and some entropy. Cardinality of solution space should be equal to cardinality of domain.

A.3 Geometric Verification of Anti-Podal Points as Second Pre-image

Define an m dimension hypersphere as a function family ℋ︀a(x∈ℤqm)=⟨a,x⟩ with prime q. Representing relations between hyperspheres and hypercubes allows for geometric information theoretic security. e.g. if I argue knowledge of two points on a circle, I’ve implied knowledge of one point on a line. If I argue knowledge of two points on a sphere, I’ve implied knowledge of one point on a plane. If I argue knowledge of one point on a hypercube, I’ve implied knowledge of two points on any higher dimension hypersphere. We’ll use the terms point and pre-image interchangeably, where pre-image additionally implies |x|∞≪q. In this section we’ll examine only binary points/pre-images such that internal sums are structure preserving for later linear projection, transformation, and comparison with hypercube commitments, also known as Ajtai commitments: ℋ︀A(x∈ℤqm)=Ax→c∈ℤqn. Hypercubes, by definition, have the additional structure n, which hyperspheres do not.

For any point x∈{0,1}m define a theoretical hypersphere with basis vector a←$ℤqm. The probability of any m dimension random hypersphere having a binary point in a field with cardinality q is 2mqm. This becomes negligible for e.g. m=10 and q≈232:2102320≈2−310. In practice we’ll use 100<m<1000 for most programs. This is exactly the statistical binding argument from BDLOP [1], but with additional verification of a second pre-image as linear transformations of oracle independent lattices and short commitments/pre-images/points.

That is, with high probability there exists no points on a random hypersphere which can be represented in ℤq using random linear combinations of {0,1}. Knowledge of a single point on such a hypersphere implies knowledge of an anti-podal point, which a verifier can compute and verify. Concretely this should be linear transformations on oracle separated terms. Given a vector x and a hypersphere with basis a define the bitwise not/anti-podal point a−x→x!∈ℤqm.

References

  1. Carsten Baum and Ivan Damgård and Vadim Lyubashevsky and Sabine Oechsner and Chris Peikert, More Efficient Commitments from Structured Lattice Assumptions, Cryptology ePrint Archive, Paper 2016/997, 2016, PDF
  2. Carsten Lund and Lance Fortnow and Howard Karloff and Noam Nisan, Algebraic Methods for Interactive Proof Systems, Journal of the ACM 39(4), 1992
  3. Ward Beullens and Gregor Seiler, LaBRADOR: Compact Proofs for R1CS from Module-SIS, Cryptology ePrint Archive, Paper 2022/1341, 2022, PDF