Questions tagged [snarks]
SNARKS (short non-interactive arguments of knowledge) are space efficient zero-knowledge proof that do not require input from a verifier.
94
questions
0
votes
1
answer
39
views
Sumcheck Protocol: How to represent a matrix as an MLE which takes row & column numbers as parameters?
This is from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
Page 43
For it to make sense to talk about multilinear extensions, we need to view the adjacency matrix $A$ not as a matrix, ...
- 2,169
0
votes
0
answers
33
views
can ownership proofs be added to circuits to make them zk-snark resistant to quantum proof forgery attacks?
According to my previous question the proofs cannot be broken by quantum computation, you cannot obtain the witness of the generated zk-snark proof.
link to my previous question.
Now if the concern is ...
- 3
0
votes
1
answer
80
views
can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?
can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?
I understand the concern that ZK-snarks and some of their cryptography may be broken by quantum ...
- 3
1
vote
1
answer
94
views
Recursive snarks with a genus-2 no-cycle hyperelliptic curve?
Any hyperelliptic curve having base field characteristic dividing group order?
A subgroup of order equal to the basefield characteristic, a large prime?
Having hard DLP in that subgroup?
Having ...
- 2,247
1
vote
1
answer
92
views
Encryption scheme with variable and provable key-length
I'm currently studying the possibility of a novel ransomware technique, where an adversary instead of forcing the victim to pay a ransom, forces them to brute force a key of given length and thus ...
- 227
1
vote
1
answer
42
views
Amplifying the completeness and soundness of a proof scheme
A (interactive) proof system for a language $\mathcal{L}$ is defined by two algorithms $\mathcal{P}$, a prover, and $\mathcal{V}$, an efficient verifier, with the following requirements:
Completeness:...
- 445
1
vote
0
answers
44
views
How do we represent a Gate involving a constant to the left or right of the operator in PLONK?
Let's say I have the following equation to be arithmetised in PLONK
$x^3 + x + 5 = 35$ and the witness is $x = 3$
$3 * 3 = 9$
$9 * 3 = 27$
$27 + 3 = 30$
$30 + 5 = 35$
Now the 4th gate can be expressed ...
- 2,169
1
vote
0
answers
31
views
Disjunctive ZK Proof of knowledge of discrete log
I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements:
$(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$
, the prover knows at least one ...
- 21
1
vote
1
answer
52
views
Practical feasibility of proving a plaintext hash relationship with a zk-SNARK
I am interested in the practicality of using generic SNARK techniques to prove the following relation.
Let E and E' be two ...
- 73
1
vote
1
answer
107
views
PLONK's computation of the first Lagrange polynomial at $\zeta$
From the PLONK paper.
On Page 31, Point 6
Compute the Lagrange Polynomial Evaluation $L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$
I don't think this formula is correct.
We have $n$ ...
- 2,169
0
votes
0
answers
29
views
What is the running time of precomputation for the PLONK zk-SNARK?
I have been looking for benchmarks on the precomputation phase of PLONK (https://eprint.iacr.org/2019/953.pdf), but found none. Is there a resource where one can get a feel for this? Either in terms ...
- 243
0
votes
1
answer
54
views
Why does the permutation polynomial have the First Lagrange base added to it in PLONK?
From the PLONK paper.
On page 19 & ahead, the permutation check is described.
In particular, on page 20, the protocol is described.
Step 5 of the check is described as
Verifier checks if for all $...
- 2,169
1
vote
0
answers
196
views
ZK-STARK soundness
I've been reading about ZK-STARK. There's an example that appears in several blogs. The most detailed explanation of that specific example which I have found so far is in this blog.
The description of ...
2
votes
0
answers
91
views
PLONK: Rationale Behind Specific Polynomial Evaluations in Round 4
In round 4, protocol evaluates a(zeta), b(zeta), c(zeta), Sσ1(zeta), Sσ2(zeta). I know linearisation trick in round 5 implies the identity of other terms. Can we ...
- 122
0
votes
1
answer
92
views
R1CS and zkSNARK
so recently I've been exploring zk-SNARKs algorithm, and I have a maybe stupid question. For example, let's take $x^2+x+1$ and make an algebraic circuit from it:
$y=x*x$
$sum=x+1$
$out=sum+y$
(First ...
- 1
0
votes
2
answers
132
views
PLONK: Reducing the number of Field Elements Trick
From the PLONK paper.
Page 18
We describe an optimization by Mary Maller to reduce the number of $F$-elements in the proof from $M$. We begin with an illustrating example. Suppose $V$ wishes to check ...
- 2,169
0
votes
1
answer
98
views
PCD vs Recursive SNARK vs Non-uniform IVC
I was wondering if anyone could clarify the differences between PCD vs Recursive SNARKs(like pickles) vs Non-uniform IVC(like hypernova)
They all seem very similar to me
0
votes
1
answer
42
views
Is there a SNARK system that will give the same proof bytes for different witnesses?
Suppose the circuit is a hash function with the input being the pre-image (private) and the output being the digest (public). If one knows of a collision can they create 2 different proofs that are ...
- 5
0
votes
0
answers
52
views
Is it posible to generate SNARK of MPC share validity?
Assume we have a central issuing authority that sends each participant a share that reconstructs in key $P_k$. I.e. Shamir Secret Share with $2$ out of $N$ format where $N>3$.
This central ...
- 1
0
votes
1
answer
117
views
The Multiplication of z(x) and z(Xw) in the Quotient Polynomial from the PLONK
From the PLONK paper.
Page 29, Round 3
Why multiply z(x) and z(Xw) in the quotient polynomial? (why does internal wiring have to multiply input permutation)
Why the second term have to "shift by ...
- 122
1
vote
0
answers
83
views
How many pairings are needed to verify beta term in GGPR13 zk-snark? Pinocchio paper says 3 but I count 4
The Pinocchio paper contains a description of the GGPR protocol (Protocol 1), and states that verification requires "8 pairings for the $\alpha$ terms, and 3 for the $\beta$ term". However I ...
- 121
0
votes
0
answers
45
views
The PLONK Gate constraint equation seems to designed more for accomodating adding a constant in a Gate but not multiplying with a constant
From the PLONK paper.
Page 23, 6 Constraint System
The constraint system $C = (V, Q)$ is defined as follows.
$V$ is of the form $V = (a, b, c)$, where $a$, $b$, $c \in [m]^n$. We think of $a$, $b$, $...
- 2,169
1
vote
1
answer
85
views
Which Rust library is recommended if I would like to implement PLONK? [closed]
I think it should have APIs for polynomials, FFT and bilinear mapping if KZG commitment scheme is used.
- 61
0
votes
1
answer
111
views
Verification in Bulletproof commitment scheme
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 44 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf), the ...
- 181
1
vote
1
answer
37
views
Any SuperSingular curve or similar with Fp = Fq which is not badly broken unless big field orders are used?
AFAIK, SuperSingular curves appear to be broken by MOV:
A. J. Menezes, T. Okamoto and S. A. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field," in IEEE ...
- 325
3
votes
1
answer
155
views
PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?
From the PLONK paper.
Page 29, Round 3
The paper doesn't explain the need or the use of the quotient challenge $\alpha$.
I understand why each of the polynomials is multiplied by $\frac {1}{Z_H}$ but ...
- 2,169
3
votes
1
answer
61
views
What does preprocessed polynomial mean in the context of PLONK?
The PLONK paper uses the term preprocessed polynomial a lot of times.
For e.g. page 14
The protocol definition includes a set of preprocessed polynomials $g1, . . . , g_l \in F<d[X]$
Page 20
...
- 2,169
2
votes
1
answer
92
views
Is the permuation check range in the PLONK Paper incorrect?
From the PLONK paper.
On pages 19 & 20, the paper describes the prescribed permutation check in PLONK.
---------------------------------------------------------------------------------------------...
- 2,169
1
vote
1
answer
116
views
Question about the PLONK permutation check
From the PLONK paper.
On pages 19 & 20, the paper describes the prescribed permutation check in PLONK.
In the last step of the proof, these are the checks
a) $L_1(a)(Z(a) - 1) = 0$
b) $Z(a)f'(a) =...
- 2,169
1
vote
1
answer
103
views
How exactly bilinear pairing multiplication in the exponent of g is used in zk-SNARK polynomial verification step?
I am reading this explanation of zkSnark written by Maksym Petkus - https://arxiv.org/pdf/1906.07221.pdf
In page 24, the zk-SNARK of polynomial is explained. In setup phase, the proving and ...
1
vote
2
answers
122
views
Where can I find 2 of the steps/proofs described in Dan Boneh's video on PLONK in the PLONK Paper? The 2 don't seem to match
This is Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=vxyoPM2m7Yg
I went through the video multiple times & also tried to go through the original PLONK paper - https://eprint.iacr....
- 2,169
1
vote
0
answers
29
views
Why do we need the random number in Pinochioo protocol compared with GGPR
I find it hard to fully grasp the whole Pinocchio protocol
.
I understand that the $\alpha$ s are for restricting the prover to compute only the corresponding set-up values.
But it's not clear for me ...
- 41
2
votes
1
answer
47
views
Can we pad witness of bulletproof and dory to be exponential size?
Bulletproof and dory reduce the witness size by a half during each interaction, until the witness is compressed to be only one element. But what about the witness is not precisely exponential size? ...
- 61
3
votes
1
answer
94
views
How do I construct a recursive polynomial as required in PLONK?
I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s
At around 19 minutes, he gets to the Prod Check Gadget.
Background:
$\omega \in F_p$ is the ...
- 2,169
1
vote
1
answer
54
views
Prod Check Gadget in PLONK - any polynomial which satisfies the prod check seems to be the trivial polynomial
In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget
$\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$)
$H = \{1, \omega, \...
- 2,169
1
vote
1
answer
99
views
PLONK Prod Check Proof - why does it have to be proven upto the last element of the set? It should be enough to prove it upto last but one element
I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s
At around 19 minutes, he gets to the Prod Check Gadget.
Background:
$\omega \in \mathbb F_p$ is ...
- 2,169
2
votes
1
answer
96
views
PLONK Product Check Proof. Why is the 2nd condition required?
I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s
At around 19 minutes, he gets to the Prod Check Gadget.
Background:
$\omega \in \mathbb F_p$ is ...
- 2,169
0
votes
1
answer
76
views
Looking for the proof of the prod check gadget referred to by Boneh in his PLONK video
I am going through Dan Boneh's video tutorial on PLONK Polynomial IOPs - https://www.youtube.com/watch?v=vxyoPM2m7Yg
He describes 3 type of proof gadgets he will use
He gives a proof of the Zero Test ...
- 2,169
2
votes
1
answer
241
views
What is the difference between those two KZG Polynomial Commitment Schemes?
In short what are the differences (pros & cons) between multiplying by powers of Tau
(from this lecture https://youtu.be/tAdLHQVW)
and raising to powers of Tau
(from this lecture https://youtu.be/...
- 152
4
votes
1
answer
100
views
Make sure of Quadratic Arithmetic Program validity
In the process of learning zk-SNARKs, I'm faced with this problem:
I understand why if the prover sends a polynomial $P$ that can be divided by $T$, the target polynomial, the prover knows a valid ...
- 91
1
vote
0
answers
51
views
About SNARKs general recipes (regarding required assumptions)
I'm following ZK MOOC: https://zk-learning.org/
After some previous readings about these topics, I was believing to have understood that, stated that non-interactivity isn't attainable in standard/...
- 710
3
votes
0
answers
56
views
Arithmetic Circuit to Square Arithmetic Program (SAP)
I'm trying to figure out how to convert a circuit into a Square Arithmetic Program (SAP). This is to eventually use it for zk-SNARKs such as Groth16.
I do however understand how to convert arithmetic ...
- 31
0
votes
1
answer
122
views
What is the need to convert simple polynomial to QAP in zk-SNARKs?
From Vitalik Buterin's Blogpost - Quadratic Arithmetic Programs: from Zero to Hero.
In the blog, a cubic equation:x**3 + x + 5 == 35 is chosen. It has been assumed ...
6
votes
1
answer
515
views
Arithmetic Circuits to R1CS. Do we consider addition gates or not?
Here is Ariel Gabizon's Blog for the process of converting Arithmetic Circuits into R1CS -
https://electriccoin.co/blog/snark-explain5/
Here, he writes
We assume multiplication gates have exactly two ...
- 2,169
4
votes
1
answer
100
views
Why does the challenge need to be prime in Wesolowski's succinct argument of $y=x^{e}$?
In Wesolowski's VDF (verifiable delay function) a prover produces a pair $(x, y)$ and needs to argue to the verifier that the pair satisfies $y = x^e \pmod N$ for some $e$ computable to both. The ...
- 181
4
votes
2
answers
234
views
What would be the degree (or range of the degree) of the polynomial used in real life zkSnarks as used in blockchains?
I am reading this explanation of zkSnarks written by Maksym Petkus - Why and How zk-SNARK Works
They work through the concept of zkSnarks using a polynomial which the prover knows & he has to ...
- 2,169
1
vote
0
answers
38
views
zk snark desgined for Exponentiation computation
I know that there are papers for both theoretic and practical zk snark computation. And most of them could support general computations. i.e: support multiplication and addition
But what I am ...
- 327
2
votes
1
answer
42
views
How to prove that a line belongs to a final hash without knowing/re-hashing all other lines?
Let's suppose :
I have a record/database (D) of 754 lines and each line correspond to a SHA256 hash.(Hn)
I hash all this record to a final and unique SHA256 hash like this : ...
- 51
2
votes
1
answer
345
views
Generic name for R1CS vs. AIR
In the zero-knowledge cryptography nomenclature, we have multiple representations of arbitrary computation suitable for submission to various proof backends (e.g. Groth16). Two specific examples ...
- 121
1
vote
0
answers
160
views
Compiling a ZK-SNARK into a Signature of Knowledge by way of FS/BCS transformations
In a sigma protocol, a well known transformation to a signature is Fiat-Shamir, where message derived randomness is mixed into the randomness of the challenge. A natural example is Schnorr signatures. ...
- 413