Skip to main content

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
2 votes
1 answer
96 views

Question about P and NP problem

There is a definition for NP shown below. Could anyone please explain why "By restricting the definition of NP to witness strings of length zero, we capture the same problems as those in P."?...
0 votes
0 answers
31 views

Questions about groth16 paper "On the Size of Pairing-based Non-interactive Arguments"

i have many questions when reading groth16 paper "On the Size of Pairing-based Non-interactive Arguments" and the following are some of those. As the following graph shows. 1, What is "...
1 vote
1 answer
425 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 ...
0 votes
0 answers
27 views

Hash-based Polynomial Commitment Scheme for Small Polynomials

I am building a SNARK project which needs to use PCS (polynomial commitment scheme). Because of some constraints, I want the field of PCS to have no additional structures and thus I only want to use ...
0 votes
0 answers
24 views

In groth16, how restricting public Inputs to the prime field instead of the snark scalar field can be used?

Recently such an overflow was fixed in snarkjs but given the small difference between the 2 and that it was restricted to the prime field anyway, how could this be exploited ?
0 votes
0 answers
62 views

Is the PLONK paper incorrect? [duplicate]

I'm having some confuses while implementing the PLONK by following the instruction in the Plonk paper. Could someone please help me with it? In step 6th of the "Verifier preprocessed input" ...
1 vote
2 answers
150 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....
0 votes
1 answer
31 views

GKR & Sum-check Protocol - how are the random numbers split across different variables?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge Section 4.6.5 - Page 64 - Description of GKR Protocol $S_0$ is the number of gates in layer 0. $k_0 = ...
0 votes
1 answer
54 views

Can Cryptographic Proofs Directly Attest to Function Call Results?

In systems where computations are performed in remote or potentially untrusted environments(e.g. Ethereum NaaS providers such as Infura), how can we gain confidence in the accuracy of the results? ...
1 vote
1 answer
113 views

GKR Protocol - does it matter which gate in each layer the SumCheck Protocol is run on?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge Page 61, Lemma 4.7 $W_i(z) = \sum_{b,c \in \lbrace 0,1 \rbrace^{k_{i+1}}} add_i (z,b,c)\cdot (W_{i+1}(...
1 vote
0 answers
67 views

How secure is this hash combination function for merkle trees?

I am exploring the class of functions that I have seen called "hash combination functions". These functions are arguably distinct from hash functions, generally providing second-preimage ...
2 votes
1 answer
192 views

GKR Protocol - is it one Sum-Check per layer or is it one Sum-Check per gate?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge On Page 59, In the first message, $P$ tells $V$ the (claimed) output(s) of the circuit. The protocol ...
0 votes
1 answer
319 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 ...
0 votes
1 answer
65 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, ...
0 votes
0 answers
41 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 ...
0 votes
1 answer
88 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 ...
1 vote
1 answer
103 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 ...
0 votes
1 answer
186 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
1 vote
1 answer
83 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 ...
1 vote
0 answers
104 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 ...
1 vote
1 answer
96 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:...
1 vote
0 answers
46 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 ...
1 vote
0 answers
39 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 ...
2 votes
1 answer
181 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$ ...
0 votes
0 answers
43 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 ...
0 votes
1 answer
63 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 $...
1 vote
0 answers
323 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 ...
0 votes
2 answers
152 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 votes
0 answers
95 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 ...
3 votes
1 answer
187 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 ...
0 votes
1 answer
46 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 ...
0 votes
0 answers
58 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 ...
0 votes
1 answer
125 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 ...
2 votes
1 answer
433 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/...
0 votes
0 answers
51 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$, $...
1 vote
0 answers
87 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 ...
1 vote
1 answer
135 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.
0 votes
1 answer
151 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 ...
1 vote
1 answer
49 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 ...
3 votes
1 answer
71 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 votes
1 answer
114 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. ---------------------------------------------------------------------------------------------...
1 vote
1 answer
164 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) =...
1 vote
1 answer
169 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 ...
7 votes
2 answers
2k 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
0 answers
30 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 ...
2 votes
1 answer
53 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? ...
1 vote
1 answer
103 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 ...
3 votes
1 answer
97 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 ...
1 vote
1 answer
61 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 votes
1 answer
109 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 ...