Questions tagged [snarks]
The snarks tag has no usage guidance.
30
questions
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 ...