Questions tagged [snarks]

SNARKS (short non-interactive arguments of knowledge) are space efficient zero-knowledge proof that do not require input from a verifier.

Filter by
Sorted by
Tagged with
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, ...
user93353's user avatar
  • 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 ...
dreamer's user avatar
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 ...
dreamer's user avatar
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 ...
Vadym Fedyukovych's user avatar
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 ...
limeeattack's user avatar
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:...
vxek's user avatar
  • 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 ...
user93353's user avatar
  • 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 ...
drydrydesert's user avatar
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 ...
884d88baaa's user avatar
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$ ...
user93353's user avatar
  • 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 ...
joakimb's user avatar
  • 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 $...
user93353's user avatar
  • 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 ...
artificial_inspector's user avatar
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 ...
Paul Yu's user avatar
  • 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 ...
alygg's user avatar
  • 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 ...
user93353's user avatar
  • 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
questionman123's user avatar
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 ...
Stent's user avatar
  • 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 ...
Peersky's user avatar
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 ...
Paul Yu's user avatar
  • 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 ...
Ethan's user avatar
  • 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$, $...
user93353's user avatar
  • 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.
Walker's user avatar
  • 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 ...
tesoke's user avatar
  • 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 ...
CPereez19's user avatar
  • 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 ...
user93353's user avatar
  • 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 ...
user93353's user avatar
  • 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. ---------------------------------------------------------------------------------------------...
user93353's user avatar
  • 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) =...
user93353's user avatar
  • 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 ...
INDUKURI MANI VARMA 21911012's user avatar
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....
user93353's user avatar
  • 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 ...
Wang Linger's user avatar
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? ...
Walker's user avatar
  • 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 ...
user93353's user avatar
  • 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, \...
user93353's user avatar
  • 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 ...
user93353's user avatar
  • 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 ...
user93353's user avatar
  • 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 ...
user93353's user avatar
  • 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/...
ShAr's user avatar
  • 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 ...
upavloff's user avatar
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/...
baro77's user avatar
  • 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 ...
Dontmilkme's user avatar
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 ...
INDUKURI MANI VARMA 21911012's user avatar
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 ...
user93353's user avatar
  • 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 ...
MERTON's user avatar
  • 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 ...
user93353's user avatar
  • 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 ...
js wang's user avatar
  • 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 : ...
JeremyDEX's user avatar
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 ...
jmcph4's user avatar
  • 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. ...
Lev's user avatar
  • 413