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:
We propose a modified protocol operating entirely in the scalar field with (Mersenne61). The protocol has three layers:
- An SIS (Ajtai) commitment to the rows of a binary witness matrix, . This is the only source of binding.
- 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 and repeated; the round challenges come from the cubic extension 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.
- An amortized opening with short integer challenges, . The verifier checks against the SIS commitment and against the row evaluations.
The opening challenges are binary. A binary challenge space is small, so independent random combinations are opened, but every difference of two challenges is 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, elements per aggregation challenge, in place of the sumcheck. The sumcheck sends 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. is the element-wise product. Elements of are compared and normed through their centered representatives in , and is the largest centered absolute value of an entry.
-
, .
-
Prover knows a witness with rows .
-
is a public uniformly random matrix expanded from a seed. is chosen for SIS hardness (Section 5.5).
-
is the opening challenge set.
-
is the number of opened random combinations and the number of independent aggregation repetitions.
-
is the cubic extension field of elements ( and is the smallest non-cube, so is irreducible). An element is written as three coefficients. A product of an element of by one of costs multiplications, of two elements of about .
-
. A vector is read as a function on the boolean hypercube through the bits of the column index, low bit first, with the columns equal to zero. Its multilinear extension is
and is the vector of over the column indices. costs multiplications given the vector, which costs .
Sumcheck. For a polynomial of degree at most in each of variables, the sumcheck protocol [2] reduces the claim to one evaluation of . In round the prover sends the univariate polynomial as coefficients in , the verifier checks against the current claim , samples and sets . After the last round the verifier checks . A false claim passes with probability at most . When is built from multilinear extensions of vectors, is a function of the vectors’ evaluations , which the prover sends and the verifier checks against the commitment. The prover’s tables are over 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:
Prover sends verifier.
2.3 Aggregation
The relation to argue is given as a polynomial of degree at most in the row values, typically a random combination of quadratic constraints with coefficients sampled here, and a claimed value of its sum over the columns. Verifier samples independent repetitions, , of
together with the coefficients of , and sends them to prover. weights the columns through , the role the uniform vector played in earlier versions, and separates the rows of the binary witness check. Both parties agree on the claim
writing for the entry of row in column . The second term is the binary witness check: it vanishes identically when is binary, and the random and make a non-binary row detectable (Section 5.4). The prover sends the claimed values (when they are not implied), then verifier samples a batching challenge and the claims are combined into one:
The repetitions share the witness rows and differ in their 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 in each variable, so round consists of one polynomial of coefficients in sent by prover, then one challenge sent by verifier. After the last round prover sends the row evaluations at the challenge point:
2.5 Opening
Verifier samples a binary challenge matrix with columns and sends it to prover. (Non-interactively, the entries are the low bits of transcript oracle elements, a fixed shape that a circuit can reproduce; each bit is biased by at most .) Prover opens random combinations of the witness rows:
Prover sends verifier. As integers .
2.6 Verification
Verifier runs the sumcheck checks: in round , , and after the last round
where costs multiplications in .
For each opening , writing and , verifier checks:
The norm check is implemented as the range with , which a circuit checks with a bit decomposition; it allows positive entries up to about , which the norm bounds below absorb. Equation (4) with (5) binds every opening to the commitment , so for the extracted rows (Section 5.2). The evaluations are fixed before is sampled, and the left hand side of (6) is , so (6) is a degree one check in that forces (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 , and (1) is a random combination over of every constraint and every row’s binarity, zero for a bad witness with probability about per repetition (Section 5.4).
The verifier’s work on the openings is multiplications for (4) and for (6) (products of by ), plus one vector of which the first entries are used. The earlier pairwise Gram checks, multiplications, are gone.
3 R1CS
Given a rank one constraint system (R1CS) defined as the matrices , and which is satisfied by any vector such that:
All indices in this section start at . 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 chunks of equal length, padding the final chunk with zeroes:
We construct the argument from two witnesses. All quadratically related variables, the values , are stored in the quadratic witness . The variables themselves, , are stored in the linear witness . Each is split into column chunks stacked vertically, for the quadratic and 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:
The program is padded with zero rows to height and with zero columns to width , and is padded with zeroes to length . Padded rows are trivially satisfied, and padded entries of do not affect any constraint.
Witnesses. Write , , for chunk of , , under , and for chunk of . The witnesses are stacks of blocks:
Block of the quadratic witness occupies rows to and block of the linear witness occupies rows to . The recomposed values of a block are the multilinear combinations of its rows
which for an honest prover are , , , . 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
with and .
Aggregation. For verifier samples
and both parties compute , the column weights. The weight can only depend on the column, which is shared by every block of ; separates the blocks and separates . Each R1CS row gets the coefficient
and both parties compute the combined linear constraint vector, split into chunks matching the linear witness:
Prover sends the linear claim of every repetition, the value of the combined linear constraints on the witness:
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 per variable and claims
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 for a consistent witness. The witness dependent products and are shared by the repetitions, so the batching costs the prover little. The linear sumcheck, over the columns of the linear witness, has degree per variable and claims
Both sumchecks run in lockstep: transcript round carries the round polynomial of the r1cs sumcheck ( coefficients in , while ) then of the linear sumcheck ( coefficients, while ), followed by the challenges in the same order. After the last round prover sends the row evaluations at the two challenge points:
Opening. Verifier samples and and prover sends
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 , with and so on. The final check of the linear sumcheck is
where the verifier evaluates the public chunks itself, multiplications per chunk, no more than computing in the first place. For the quadratic witness verifier runs (4), (5) and (6) with and , and for the linear witness with and .
Correctness. With binary the binary term of (8) vanishes, the quadratic term of repetition is for a satisfying witness, and its linear term is . The sum of repetition in (9) is by definition.
Soundness. Section 5: the openings bind to the extracted witnesses (error over both witnesses), given correct evaluations the sumchecks force (8) and (9) for the extracted witness (error ), the batching forces them for every repetition (error ), and for a repetition the left hand side of (8) minus is a nonzero polynomial of degree at most 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
Proof size. About
elements of (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 or . In SHAKE256 every entry of is a bit, and all but one row have . Bit decomposing such a value costs witness cells, of which 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 and a witness mask . The honest choice is exactly when , and exactly when . The masks are sent with , before any aggregation challenge, and cost bits.
Layout. Rows with , taken in increasing order, fill the decomposed region of exactly as before: the row at position goes to block , column . Rows with fill the as-is region in the same way, where as-is block is the three rows
holding the values themselves. Witness entries are placed the same way in : entries with are bit decomposed into blocks of rows, entries with fill as-is blocks of a single row placed after the decomposed rows. With and :
The prover chooses the widths (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 , 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. has one entry per block of either region, as-is block using . Row placed in block (of either region), column , gets , and is computed from as in (7). It is split into one chunk per block of , holding the entries of for the witness entries placed in that block, at their columns, and sums over all these chunks.
Sumchecks. In every repetition the r1cs sumcheck (8) gains the as-is blocks with weight in place of : the quadratic term and the linear term , and the binary term already covers every row. The linear sumcheck (9) gains . The final checks read the as-is rows of 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 to be binary, so the as-is quadratic term is on the values themselves. The linear witness needs no binary check: an as-is entry is read directly as , and the extracted satisfies the R1CS whatever its values. A mask choice can therefore only affect completeness: a non-binary as-is value in fails the binary check, and a large as-is entry in fails the norm check. Small non-binary entries of pass the norm check and may also be stored as is. is unchanged with the heights above.
Proof size. About
elements of , with the heights above. For SHAKE256 the heights shrink by about a factor 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 ( per row), and linear in the widths through the openings ( per column). With the cell count of a witness fixed by the program, , the size is minimized at , which is tall: with and a column costs about seven times a row. For all but small programs this exceeds and the heights are set by instead, the widths following as . The sumcheck rounds, per repetition, are negligible.
The prover chooses the widths by enumerating, for each region of each witness, the widths that give blocks, discarding the combinations with or , and taking the pair with the smallest estimated size. The estimate is the proof size formula with recomputed for each candidate (it depends on through ) 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 .
For a random R1CS with decomposed regions only, in Mersenne61 with , :
| elements | Gram version | ||||
|---|---|---|---|---|---|
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 (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 . 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 , whose challenge matrices satisfy for some column and , with the other columns arbitrary, the openings of column satisfy
with for binary challenges, so is an exact short opening of . Two such openings of the same differ by an SIS solution of norm at most , so is determined by .
5.2 Knowledge Extraction
Fix the prover’s randomness and everything up to the opening challenge, so , the round polynomials and the evaluations are fixed. Let be the challenge space of one column, , , and let be the set of challenge matrices the prover answers acceptably, . For a column and a value write for the density of among the matrices with -th column (the other columns uniform). A direction- line is a set of column values differing only in row .
To extract row the extractor needs an accepting pair with for some column , i.e. two accepting matrices whose -th columns lie on the same direction- line. It samples a base and then, for a column and another value on the direction- line through , samples matrices with -th column and fresh uniform other columns until one is accepted. This succeeds quickly when some line mate of some column has .
Lemma 1. For every row and , the probability over a uniform base that, for every column , every other value on the direction- line through has is at most .
Proof. Call a column value heavy if and light otherwise. A base with the stated property has, in every column , either a light -th column or a heavy -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 per column, and bases of the second kind in every column number at most . Bases of the first kind in some column carry mass , so at most in total. Divide by . ∎
With the probability is at most , so for at least half of the bases have a line mate of density at least in some column. Trying the line mates in round robin finds an accepting partner after prover invocations in expectation; rows that fail are retried from a fresh base. Every row is extracted independently, so the extractor obtains exact openings , with , of every row of both witnesses with invocations, whenever (). 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 with challenge column , the vector is an integer vector in the kernel of of norm at most , hence zero unless it is an SIS solution of that norm. So in for every accepting opening, which is what the next subsection assumes. The binary witness check then forces every row of into , and the R1CS relation is over , so the linear witness needs no integrality beyond being short.
5.3 Binding of the Sumcheck Evaluations
By Section 5.2 every accepting opening equals for the extracted rows, unless SIS is broken. The evaluations are fixed before is sampled, so the evaluation check (6) reads
Write : a uniform column is orthogonal to a fixed nonzero with probability at most , because for a coordinate with and any values of the other coordinates at most one value of satisfies . A wrong therefore passes one column with probability at most , and all columns with probability at most . The R1CS argument checks two witnesses, so all evaluations are correct except with probability .
The pairwise Gram checks of earlier versions, which needed and set , 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 and suppose the evaluations are correct. The linear sumcheck (9) ends in the verifier’s own evaluation of the public and the bound , so by the sumcheck soundness its batched claim holds for the extracted witness except with probability , and then for every unless is a root of a nonzero polynomial of degree , probability . Likewise the r1cs sumcheck forces the sum of (8) over the extracted witness except with probability , and the batching forces every repetition’s sum to equal except with probability . For a repetition both together say that
with the quadratic, binary and linear terms of the bracket of (8) for repetition . is a polynomial in the challenges of the repetition, all sampled after , i.e. after the extracted witness is fixed. Its degree is at most in ( is the multilinear extension ), in , in , in and in , so at most in total. It is nonzero for a bad witness:
- If row of is not binary, the coefficient of is the multilinear extension of the nonzero vector at , a nonzero polynomial; distinct rows have distinct powers of and cannot cancel.
- If is binary but block violates , the coefficient of is the multilinear extension of at , nonzero.
- If is binary and satisfies every block but , the coefficient of is , where the of distinct rows are linearly independent polynomials, so it is nonzero when any row’s bracket is a nonzero polynomial in .
By Schwartz-Zippel with probability at most
per repetition, and all independent repetitions pass a bad extracted witness with probability at most . The total soundness error is bounded by
with the of the extractor (Lemma 1), of the evaluation binding, and the SIS norm bound 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 on its own, and errors of different squeezes do not compose. The squeezes and their errors are: the aggregation challenges of all repetitions, (every repetition sits behind the one squeeze); the batching challenge , per sumcheck; each r1cs sumcheck round, ; each linear sumcheck round, ; the opening challenge, . The round challenges are why is needed: with a prover holding a bad witness could, in round , send a polynomial with the correct sum but otherwise free coefficients and grind them until is a root of , which takes about squeezes and puts the sumcheck on a true claim from then on. Repeating the sumcheck in does not help, since nothing forces the rescues of different repetitions into the same round: they add work instead of multiplying the error. With the same attack costs squeezes. The aggregation challenges can stay in 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 cost one squeeze and multiplications but put the degree into . Sampling an independent per row would reduce the degree to and to about at the cost of squeezes per repetition; for Mersenne61 both give .
5.5 Parameters for Mersenne61
Openings. Every extracted row is an exact opening. The norm check is , two openings of the same differ by at most in , and the kernel vector has norm at most . The number of openings is the smallest with ,
so about field elements of openings.
Repetitions. The prover chooses the witness widths, so the heights are only known to satisfy . With and widths up to , , so gives ; gives only about . The implementation computes from the actual of the layout, which for Mersenne61 is for every layout within . The extension field terms are at most .
SIS. The size optimizer drives the heights to for all but small programs (Section 4), so the norm bound is computed at : in , and with about in (the norm check range adds at most another factor ). A larger costs SIS security directly. is not fixed here: it should be set with a lattice estimator for at the witness width . The proof size is about
elements of .
5.6 Open Items
- SIS parameters. for each witness width, from a lattice estimator. With the heights at the trade between , and the openings should be revisited.
- 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.
- 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.
- 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 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 , the distance of a simulated oracle from a theoretical oracle for an output equal in length to the number of distinguishable states of reality . Concretely this may be taken as something like the Lloyd bound or the holographic storage bound . We apply a conservative bound and take , defined as the product of the number of distinguishable states of energy and the distinguishable states of matter. Taking each as we get .
6.1 Probable Finite Oracles
Given an output vector of length from a simulated oracle. Call output from a corresponding theoretical oracle. Call the linear distance from the simulated oracle to the theoretical oracle for an output of length . A simulated oracle is statistically likely to exist provided . Oracles with 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 ,
so the verifier can check openings of without a second commitment.
A.1 Space Efficient Linear Relations From Short Vectors
Given a witness matrix prover forms two commitments representing the sums of rows and sums of columns respectively:
Prover sends verifier and verifier samples and . Prover computes challenge commitments:
Prover sends verifier and verifier checks the following relations:
Iff are sampled randomly after commitment, and , 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 . Thus the evaluation of and 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 and . Given a binary witness matrix define the bitwise not matrix such that and .
Prover begins by forming short commitments to the witness matrix:
Prover sends verifier and verifier samples . Prover forms a vertical challenge commitment:
Prover sends verifier and verifier samples . Prover forms a horizontal challenge commitment:
Prover sends verifier and verifier checks the following relations:
Verifier then interprets and as points on two boolean hyperspheroids with basis vectors and respectively, each of cardinality . Verifier selects the antipodal point to get element-wise boolean negation of the witness on the hypersphere:
Verifier can then compute the expected SIS preimages using linear operations:
Verifier then checks the following relations:
The short commitments and represent a binary matrix as 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 dimension hypersphere as a function family with prime . 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 . 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: . Hypercubes, by definition, have the additional structure , which hyperspheres do not.
For any point define a theoretical hypersphere with basis vector . The probability of any dimension random hypersphere having a binary point in a field with cardinality is . This becomes negligible for e.g. and . In practice we’ll use 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 using random linear combinations of . 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 and a hypersphere with basis define the bitwise not/anti-podal point .
References
- 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
- Carsten Lund and Lance Fortnow and Howard Karloff and Noam Nisan, Algebraic Methods for Interactive Proof Systems, Journal of the ACM 39(4), 1992
- Ward Beullens and Gregor Seiler, LaBRADOR: Compact Proofs for R1CS from Module-SIS, Cryptology ePrint Archive, Paper 2022/1341, 2022, PDF