Questions tagged [snarks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
48 views

zkSNARKS: What prevents the prover from chosing a different polynomial than the one he is expected to know

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here the Prover knows a polynomial of degree 3, 2 of the solutions of the ...
1
vote
1answer
20 views

zkSNARKS - unable to understand the usage of polynomial to verify some condition

From Vitalik Buterin's Blogpost - An approximate introduction to how zk-SNARKs are possible From the sub-topic "Comparing a polynomial to itself", I understood till here In other words, any ...
0
votes
0answers
31 views

Proving the output of a generic function

Is there any generic construction to prove the correctness of the output of a function? In other words, is there a general way to produce a witness for the statement $y = f(x)$? More formally, let $f: ...
1
vote
1answer
60 views

Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists?

From what I know, proving the existance of a Knowledge Extractor implies perfect soundness. So why in zk-SNARKs (and similar) we talk about Arguments of Knowledge, where the soundness property is only ...
0
votes
0answers
43 views

Are zk-STARKs a Sigma protocol? Is the communication interactive? And other doubts

I've heard that STARKS are not a non-interactive protocol, if so: What is (briefly) the mechanism they use to operate? Can they be considered a Sigma protocol? Why SNARKs are not interactive, instead?...
1
vote
0answers
79 views

Why the Kate Commitment and the Algebraic Group Model is used a lot in zk-SNARKs proving system since 2019?

I am engaged in the research of zk-SNARKs. After I read some papers about zk-SNARKs, I realize the Kate Commitment and the Algebraic Group Model is used a lot since 2019. They are used in Sonic, Plonk,...
2
votes
2answers
161 views

A field element as the exponent of a group element

The R1CS constraints are expressed over finite fields. Many proofing systems, such as zk-SNARK, use prover keys such as $g^{\alpha^0}, g^{\alpha^1}, ..., g^{\alpha^n}$ where $\alpha$ is a field ...
2
votes
0answers
93 views

It is possible to verify the computation of a hash function without actually proving it in zero knowledge?

Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively. ...
0
votes
0answers
17 views

Does libsnark support generation of a trusted setup/public parameters via MPC?

Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs states: We design, build, and evaluate a multi-party protocol for securely sampling encodings of random evaluations of certain ...
3
votes
1answer
45 views

Definition of Circuit Satisfiability In The Context of zk-SNARKs

A standard theorem is that boolean circuit satisfiability is NP-complete (shown in CLRS, for example). I am interested in what these statements formally mean. From CLRS, I can cite that $$\text{...
0
votes
0answers
53 views

How does one construct a SNARK circuit for proving the knowledge of a SHA256 pre-image?

Usually one explains how the R1CS/QAPs and SNARKs work using examples of circuits with multiplication and addition nodes, and constructing polynomials from that is relatively straightforward. SHA-2 ...
4
votes
1answer
108 views

Which is the relation between Zero-Knowledge Proofs of Knowledge and circuits?

With the risen popularity of Zero-Knowledge Proofs of Knowledge (ZKPoKs) such as Pinocchio, Groth16 and Sonic, to name some ZKPoKs that are popularly known as zk-SNARKs, I got engaged to understand ...
1
vote
1answer
44 views

ZK-SNARK basics: knowing t(x), what prevents the prover from creating random h(x) to forge L, R, and O

After reading a number of ZK-SNARK explainers from here, here, and here, I still don't understand a few things. The setup of the algorithm uses QAP to calculate polynomial P(x) = L(x) * R(x) - O(x), ...
2
votes
1answer
154 views

IS zk-SNARK not suitable for constructing anonymous authentication scheme?

zk-SNARK was a powerful tool for privacy-respecting e-cash. However, recent years, in the literatures about anonymous authentication scheme, such as group signatures, anonymous credential, blind ...
5
votes
3answers
625 views

Why it is said that “zk-SNARKs need a trusted setup” to work?

What is the meaning of a "trusted setup" in this context? It is often said all around that zk-STARKs and Bulletproofs does not require a trusted setup. How do zk-STARKs and Bulletproofs ...
3
votes
1answer
134 views

CRS vs SRS in zk-SNARK

Are Common Reference String (CRS) and Structured Reference String (SRS) is the same in preprocessing phase of zk-SNARK? Is there any difference between them?
1
vote
1answer
185 views

Hash and (MAC) based signatures using zk-SNARK

I was wondering if we could use any general symmetric key MAC, a collision resistant hash $H$ and zk-SNARK (or any general NIZK scheme) to construct a signature scheme. I have a MAC key $k$, which is ...
0
votes
1answer
231 views

Construction of R1CS vs QAP

I have been following the medium post of Vitalik, where he shows step by step how to convert program --> Circuit --> R1CS --> QAP. I am aware of the Pinocchio protocol, where they utilize the ...
0
votes
1answer
102 views

Difference between a Polynomial Opening & a Polynomial Commitment

Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two ...
2
votes
0answers
113 views

Efficiently prove the correctness of Paillier encryption in or "outside" a zk-SNARK

I'm working with a zk-SNARK library [1] that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier [2] ciphertext $c$ ...
4
votes
1answer
293 views

How to construct a circuit in zkSNARK

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is: using a circuit to represent a problem, generate an R1CS from the circuit, transform R1CS to QAP and then ...
1
vote
1answer
136 views

Conditional decryption

Is it possible for one party to encrypt some data and have another party (unknown to the first party) view that original data if a certain condition is met? I cannot find any information about this ...
3
votes
1answer
108 views

libsnark generator toxic waste

I'm looking through the test and examples of libsnark, let's take for example here: https://github.com/christianlundkvist/libsnark-tutorial/blob/master/src/test-gadget.cpp at line 19 there's: ...
1
vote
0answers
111 views

two-to-one hash in libsnark, what is it "exactly"?

I'm reviewing this test which prepares a zero knowledge proof of the preimage of an hash: https://github.com/mariogemoll/libsnark-tutorial/blob/sha256/src/test-knowledge-of-preimage.cpp In my (wrong) ...
1
vote
0answers
39 views

Fixed variable in Groth16

In the paper On the Size of Pairing-based Non-interactive Arguments by Jens Groth, it is always referred in the equations to satisfy that $a_0 = 1$ and the others $a_1, ..., a_m \in \mathbb{F}$. I am ...
4
votes
2answers
131 views

Can zksnark prove DLP?

Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?
5
votes
1answer
473 views

Why invent new hash functions for zero-knowledge proofs?

Recently, new hash functions were invented. Their primary purpose is serving the needs of zero-knowledge proof systems. I'm talking about Poseidon-256, Starkad-256, etc. See the paper. What is the ...
1
vote
1answer
192 views

Examples of flattening code to create an R1CS

When preparing logic for use in a zkSnark, one needs to first "flatten" the code so it can be written as a series of constraints. I'm finding it hard to find examples of doing this. For instance, how ...
1
vote
1answer
195 views

Converting R1CS to QAP - checking the last step

from reading Vitalik Buterin's excellent post on creating a QAP from an R1CS, I understood to translate a function into three groups of vectors, the number of vectors being the number of "gates" or ...
0
votes
2answers
81 views

Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate?

In the context of zk-SNARKS, we are given an arithmetic circuit $C$, public outputs $y_1, \ldots, y_n = \mathbf{y}$ and some public inputs $x_1, \ldots, x_ℓ$. The prover wants to prove knowledge of ...