arkworks-rs / marlin Goto Github PK

Summary of Bug

The branch constraints isn't building with latest dependencies.

Version

(903c741)

Steps to Reproduce

$ cargo build

Can ark-bn254 be plugged in to replace ark-bls12-381? We'd like to do performance comparison with several other zkSnark tools based on bn254.
Thanks!

Summary of Bug

While adding Marlin as a backend for ZoKrates, I'm hitting an underflow panic during the setup phase:

This works (1 public input: the return value):

def main(private field x) -> field:
   return x**2

This fails (1 public input: the return value):

def main(private field x) -> field:
   return x

attempt to subtract with overflow ark-marlin-0.2.0/src/ahp/mod.rs:108:28

It seems like k_size is expected to be bigger than 2, but in this case isn't.

Version

0.2.0

Steps to Reproduce

For these examples I used a universal setup degree of 5 for all parameters.

I run the cmd

cargo test prove_and_verify_with_tall_matrix_big -- --nocapture

and get the print info as below:

running 1 test
Called index
Called prover
Called verifier

Should not verify (i.e. verifier messages should print below):
Inner sumcheck test failed
AHP decision predicate not satisfied
PC::Check failed
Called index
Called prover
Called verifier

Should not verify (i.e. verifier messages should print below):
Inner sumcheck test failed
AHP decision predicate not satisfied
PC::Check failed
Called index
Called prover
Called verifier 
...........

Thanks for the awesome work.

I think poly-commit does have these features.

the package `marlin` depends on `poly-commit`, with features: `parallel, std` but `poly-commit` does not have these features.


failed to select a version for `poly-commit` which could resolve this conflict

If I remove these features, I am still facing other issues probably because of the latest update to zexe library.
I think everything works for commit #4ae139c commit in the zexe library if that helps in any debugging.

when running the following command for profiling

cargo build --features timer

The error appears:

Package `marlin v0.1.0 (/home/zy/Desktop/github/marlin)` does not have these features: `timer`

How to add this feature in the package? It seems that only modifying Cargo.toml is enough, but I am not familiar with rust.....

While running the tests cargo test I am running into the error

error[E0425]: cannot find value 'OsRng' in module 'rand_core'

for lines 160:35 (src/ahp/mod.rs) and 52:35 (src/test.rs)

Am I missing something here? Did someone else run into this issue?

When I test a specific circuit, it seems that the PR to replace inlining with outlining (#50) has introduced potential errors that fail the outer check.

When it happens, the prover will panic.

thread 'main' panicked at 'assertion failed: evals.get_lc_eval(&outer_sumcheck, beta)?.is_zero()', 
/home/wkchen/.cargo/git/checkouts/marlin-cee5d75828d5b0f5/839478d/src/ahp/mod.rs:174:9

This problem is not caught by the tests. As another PR shows (#53), our current test might be too weak.

Thus, my plan is:

• First of all, let me add a PR to turn off outlining so that it does not affect other projects using Marlin.
• Debug the outlining.
• Add tests over more complicated circuits.

cc people in projects that may have a dependency on Marlin @ryanleh

As of subject. There seems to be an incompatibility with the latest zexe.

The culprit is plausibly this commit in zexe:
arkworks-rs/snark@ecc6057#diff-4cca21435ee820e184b16118ad656f07

The current master branch may fail to index a circuit because the index function would call:

let matrices = cs.to_matrices().unwrap();

in make_matrices_square_for_indexer, before calling inline_all_lcs.

As a result, a developer would see "no symbolic LCs".

This problem is indeed fixed in the constraints PR #39 by removing a check in make_matrices_square_for_indexer.

See https://github.com/arkworks-rs/marlin/pull/39/files#diff-4a24591214fb91bafc31f147e9f82b39471e7a773de92a5a36f0776f434c6158R54

But I think we are not going to merge that PR soon, it may be worthwhile to fix this one sooner. (I will work to finish the constraints PR of poly-commit soon.)

This already exists in the diagram branch; we should polish it and add it to master.

I can't tell if this is an issue with Marlin or if I'm misunderstanding the Zexe R1CS API. Any help would be appreciated.

I'm trying to verify an R1CS with the following 3 constraints:

<a, 1> * <a, 1> = <d,1>
<b, 1> * <b, 1> = <e,1>
<f, 1> * <[d,e],[1,1]> = <c,1>

Where [a,b,c,f] are public input with values [3,4,25,0], respectively, and [d,e] are the witness with values [9,16], respectively.

An attempt at hand testing this circuit is attached. Just replace the src/test.rs file with test.rs.txt (renamed back to test.rs) and add num-traits = { version = "0.2", default-features = false } to the Cargo.toml file and you should be able to run Marlin on this circuit by simply calling cargo test.

Thanks!

This issue is just to remark a useful variant of Marlin with the property of commit-and-prove. Basically, the verifier does not know the input but instead obtains a commitment of the input. Later, separately, the prover may open the commitment.

Based on the diagram, it seems the main change is as follows:

• The prover sends a polynomial commitment of x and the evaluation of x on challenge \beta.
• The prover changes the corresponding opening information of the outer sumcheck.
• The verifier changes the outer sumcheck and changes the PC check for this outer sumcheck.

This variant can be a fork or a configuration option. The constraints PR would add an option for recursive, which commits the vanishing polynomials. This could be a separate option.

More discussion on commit-and-prove SNARK can be found in https://eprint.iacr.org/2019/142.

May I ask why ark_snark::UniversalSetupSNARK trait is not implemented for struct Marlin when all of its functions (including those of a trait SNARK) are being implemented with the same func signature?

The current implementation has a restriction that the public input (excluding the common "1") is 2^k-1.

The problem is that in ark-pcd, we want to provide a universal interface regardless of the implementation. But Marlin is special. The glue code would need special wrappers to allocate new input values in the circuits and modify the input to the verifier gadget accordingly.

Thus, how about changing Marlin into supporting many public input sizes? Basically, we modify the indexer, prover, and verifier to pad the formatted public input size to 2^k.

What’s the easiest way to benchmark Marlin at different R1CS instance sizes?

I'm trying to get a dummy test compiling with the IPA_PC scheme and Marlin / Pallas but my compiler says it doesn't implement the PolynomialCommitment trait which I can see it does (unless it just doesn't for this specific curve type)

Am I setting things up incorrectly or does it not work for Fp256?

error[E0277]: the trait bound `InnerProductArgPC<ark_ec::models::short_weierstrass_jacobian::GroupAffine<PallasParameters>, Blake2s, DensePolynomial<Fp256<FrParameters>>>: ark_poly_commit::PolynomialCommitment<Fp256<FrParameters>, DensePolynomial<Fp256<FrParameters>>>` is not satisfied
   --> src/tests.rs:79:19
    |
79  |           let srs = Marlin::<
    |  ___________________^
80  | |             $bench_field,
81  | |             InnerProductArgPC<$affine_curve, Blake2s, DensePolynomial<$bench_field>>,
82  | |             Blake2s,
83  | |         >::universal_setup(65536, 65536, 65536, rng)
    | |__________________________^ the trait `ark_poly_commit::PolynomialCommitment<Fp256<FrParameters>, DensePolynomial<Fp256<FrParameters>>>` is not implemented for `InnerProductArgPC<ark_ec::models::short_weierstrass_jacobian::GroupAffine<PallasParameters>, Blake2s, DensePolynomial<Fp256<FrParameters>>>`

I'm under the impression that this is the implementation that I thought should work: https://github.com/arkworks-rs/poly-commit/blob/constraints/src/ipa_pc/mod.rs#L304. Nonetheless, I'm evoking this with the following args:

fn bench_prove() {
    marlin_prove_bench!(pallas, ark_pallas::Fr, ark_pallas::Affine);
}

fn bench_verify() {
    marlin_verify_bench!(pallas, ark_pallas::Fr, ark_pallas::Affine);
}

Currently Marlin includes its own FiatShamirRng which uses chacha20 and a generic Digest function (instantiated with I think blake2s).

Would you be interested in a PR that replaces it with Merlin?

In contrast to the existing implementation, this provides more secure prover randomness generation, allows binding Marlin proofs to arbitrary structured application data rather than just a single domain separator string, or to transcripts of other proof protocols, and potentially makes the implementation slightly cleaner (although the FiatShamirRng API is already pretty reasonable). It also simplifies the (cryptographic) dependencies, as rather than relying on the security of both chacha20 and blake2s (or some other hash function), the security relies only on keccak-f/1600.

I would be happy to create a PR for this change but only if it's one that you'd actually want.

Summary

My notes on how to implement Marlin + Plookup: https://hackmd.io/@gPH8I-Z5RcSMH2KTXLDeDg/BJcMTU9wO
@Pratyush you may still recognize this.
I don't think I'll have time to work on this; I'll let another enthusiastic cryptographer do so if they so desire.

Problem Definition

Proposal

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

This look like a breaking change in ff_fft crate. I suggest including a working Cargo.lock into the code, or pinning to a specific commit when you use git dependencies.

ff-fft = { git = "https://github.com/scipr-lab/zexe/", default-features = false }

The new polynomial framework would require much change to Marlin's data structures. This is now done together with the constraints PR.

Hello arkworks-rs, thanks for your the greater work Marlin. While reading the paper I encountered a question.

In page 28, section 5.3.2, it says:

However, in the same page equation (6) it says sums to on H. Therefor, according the univariate sumcheck for subgroups protocol introduced in section 5.1, should be written as:

if is not zero. Is my understanding about wrong or something I have missed? Any help is appreciated, thanks.