Marlin refactoring #34

lgiussan · 2021-11-12T11:50:01Z

This pull request addresses Issue #27.
The high level changes are the following:

There is no longer the need to explicitly pad R1CS matrices with dummy variables or constraints to make them square. Instead the padding is implicit in matrix-vector operations.
The UnnormalizedBivariateLagrangePoly is replaced with the normalized LagrangeKernel.
Matrix arithmetization is updated to use LagrangeKernel.
Prover no longer needs to supply an oracle for T_eta(alpha, X).
The query of the verifier to the oracle for T_eta(alpha, X) during outer sumcheck is substituted with the computation of the unique value v which satisfies the outer sumcheck. Later v is used in place of T_eta(alpha, beta) in the inner sumcheck. Explicit checking of the outer sumcheck equality is no longer needed with this optimization.
The names of some variables, functions, and files have been changed to better reflect the notation of https://arxiv.org/abs/2107.04315

DanieleDiBenedetto · 2022-01-14T12:17:03Z

Okey I left unresolved the comment related to stuff that should be addressed in the monorepo.
When the monorepo branch is stable let's bring the current Marlin inside it.
Then we will open a PR addressing the remaining changes so we can keep track of them
PS. The ToBytes deprecation was already performed by me in ginger-lib's sponge branch, so no need to address it here anymore.

src/iop/prover.rs

UlrichHaboeck75

Most of my comments address outdated inline comments. However, two "major" findings:

The max_degree() function, which is used in the setup, does not use the correct formula.
The prover third round for the inner sumcheck seems to do some computations twice.

Details are found below.

README.md

src/iop/mod.rs

src/iop/prover.rs

UlrichHaboeck75 · 2022-02-28T18:05:31Z

src/iop/sparse_linear_algebra.rs

+            let dist = Bernoulli::new(fill_factor).unwrap();
+            let val: Vec<F> = (0..num_elems)
+                .map(|_| match dist.sample(rng) {
+                    true => UniformRand::rand(rng),


Does UniformRand sample from the entire field?

src/iop/sparse_linear_algebra.rs

…ubdomain

lgiussan · 2022-03-04T15:50:40Z

Besides the requested changes, I did an additional change. At matrix construction time I re-index the columns of the matrix to be coherent with the treatment of public input domain X as a subdomain of the domain H. In this way there is no need to re-index matrix columns during computations.

UlrichHaboeck75

I added minor comments, which are not mandatory for a merge.

UlrichHaboeck75 · 2022-03-04T15:45:41Z

src/iop/indexer.rs

+            a_arith: a_star_arith,
+            b_arith: b_star_arith,
+            c_arith: c_star_arith,


I would have renamed also here the *_star_arith to *_star.

UlrichHaboeck75 · 2022-03-04T15:55:59Z

src/iop/indexer.rs

 ) -> Option<(SparseMatrix<F>, SparseMatrix<F>, SparseMatrix<F>)> {
-    balance_matrices(&mut cs.at, &mut cs.bt);


What is the reason for moving the balancer out of the function?

Now function to_matrix_helper()needs to take in input domain_h and domain_x, which are returned by function build_domains(). And build_domains() should be called after having called balance_matrices(), because balancing the matrices could possibly affect the size of the domains (more precisely of domain_k and domain_b).

UlrichHaboeck75 · 2022-03-04T16:03:13Z

src/iop/prover.rs

+    /// Lagrange domain `domain_h`.
+    pub fn full_variable_vector(&self) -> Vec<F> {
+        let domain_x_size = self.domain_x.size();
+        let mut padded_public_input = vec![F::zero(); self.domain_h.size()];


Just a side question: Why don't we use slices in stead of vectors here? Do we really need the functionalities provided for vectors (such as appending/concatenating)?

The reason is that slices are just a pointer (plus length) to a contiguous sequence of data. A function cannot return references to data allocated inside the function itself, because they would be dangling references after the function returns.

UlrichHaboeck75 · 2022-03-04T16:24:07Z

src/iop/prover.rs

+        let c_scaled_val_row_col_on_b = compute_scaled_val_row_col(c_arith, scaled_eta_c);
+        end_timer!(scale_val_row_col_time);
+
+        let step = Self::get_subdomain_step(&domain_b, &domain_k)?;


I would move the declaration of step after Line 701.

UlrichHaboeck75 and others added 30 commits August 29, 2021 10:57

added inline docu and TODOs

f34881c

corrected docu on the matrix arithmetization

e757cdc

minor changes

c715661

modified README

84b214d

extended README for co-Marlin with two kernels

c803cef

minor adds

0e12360

adapted readme to the current repo state

c9a4d7d

adapted readme.md, minor additional inline comments

a787380

further TODO's for refactoring Step 1

aae25de

Merge branch 'refactor_constraint_system' into marlin_refactoring

deced53

Move matrix arithmetization utilities to indexer.rs

9c3b921

Rename AHPForR1CS to IOP

4100a98

Rename oracle polynomials

6fd9718

Align with new ConstraintSystem constructor interface

60db3d7

added comments on the degree of the prover polys

69950e9

Remove zk_bound logic

22489a2

Fix matrix balancing

41a5a38

Merge branch 'inline_docu' into marlin_refactoring

8a9e209

Fix bug in assertion on polynomial degree

4e1040a

Remove prover messages

457ab55

Simplify verifier first message

bd03496

Remove degree bounds

314e910

Rename Matrix to SparseMatrix

bc38f53

Rearrange circuit-specific setup functions

7a513b1

Rename some variables and functions

5a746d5

Move computation of y_A and y_B to prover first round

dba6b4f

Add H and K sizes to MatrixArithmetization struct

ca6334d

Rename domain B to mul_domain

5ce0cf1

Exploit the fact that eta_a == 1

b34e381

Fix dependencies

20de557

lgiussan added 5 commits January 11, 2022 10:52

Reintroduce MatrixEvals struct

ce6395a

Join two separate loops into one

d91c5bc

Add unit test for matrix arithmetization

5debbd5

Remove some outdated comments

90d5bc7

Add unit tests for matrix balancer

5cc4ec5

lgiussan requested a review from DanieleDiBenedetto January 11, 2022 14:08

DanieleDiBenedetto approved these changes Jan 14, 2022

View reviewed changes

DanieleDiBenedetto requested changes Feb 15, 2022

View reviewed changes

src/iop/prover.rs Outdated Show resolved Hide resolved

This was linked to issues Feb 21, 2022

Cleaning up / refactoring Marlin #27

Open

Optimized zk randomization #26

Open

UlrichHaboeck75 suggested changes Feb 28, 2022

View reviewed changes

lgiussan added 7 commits March 3, 2022 19:23

Fix comments

e0300d1

Fix degree bounds

b56e000

Minor changes

d8e5099

Clarify logic of conditionals inside fn verify_sumchecks()

42fa234

Re-index matrix columns to be coherent with treatment of input as a s…

d8c25d4

…ubdomain

Avoid duplicating some computations inside prover rounds

7dd96de

Improve tests

5b57d52

UlrichHaboeck75 approved these changes Mar 4, 2022

View reviewed changes

Minor changes

47ab73e

UlrichHaboeck75 mentioned this pull request Mar 9, 2022

T dlog acc marlin HorizenOfficial/ginger-lib#169

Closed

DanieleDiBenedetto approved these changes Mar 15, 2022

View reviewed changes

lgiussan added 2 commits March 16, 2022 15:52

Align with refactor-ginger-dev

4d11f6c

Merge branch 'dev' into marlin_refactoring

97d1242

DanieleDiBenedetto approved these changes Mar 16, 2022

View reviewed changes

lgiussan and others added 2 commits March 16, 2022 18:13

Use commit_many() from poly-commit

b23dd3e

Removed unneeded lifetime parameters

ec104e4

DanieleDiBenedetto closed this Feb 27, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Marlin refactoring #34

Marlin refactoring #34

lgiussan commented Nov 12, 2021 •

edited

Loading

DanieleDiBenedetto commented Jan 14, 2022 •

edited

Loading

UlrichHaboeck75 left a comment

UlrichHaboeck75 Feb 28, 2022

lgiussan commented Mar 4, 2022

UlrichHaboeck75 left a comment

UlrichHaboeck75 Mar 4, 2022

lgiussan Mar 7, 2022

UlrichHaboeck75 Mar 4, 2022

lgiussan Mar 7, 2022

UlrichHaboeck75 Mar 4, 2022

lgiussan Mar 7, 2022

UlrichHaboeck75 Mar 4, 2022

lgiussan Mar 7, 2022

		) -> Option<(SparseMatrix<F>, SparseMatrix<F>, SparseMatrix<F>)> {
		balance_matrices(&mut cs.at, &mut cs.bt);

Marlin refactoring #34

Marlin refactoring #34

Conversation

lgiussan commented Nov 12, 2021 • edited Loading

DanieleDiBenedetto commented Jan 14, 2022 • edited Loading

UlrichHaboeck75 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lgiussan commented Mar 4, 2022

UlrichHaboeck75 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lgiussan commented Nov 12, 2021 •

edited

Loading

DanieleDiBenedetto commented Jan 14, 2022 •

edited

Loading