zkstacks - User contributions [en]

List of all relevant zk-papers

2021-05-05T14:25:43Z

Srikar: /* ZK-Starks */

===The Fundamentals===
*[[The Knowledge Complexity of Interactive Proof Systems]]
*[[Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes]]
*[[Private Coins versus Public Coins in Interactive Proof Systems]]

===Quantum===

===Blockchain and Cryptocurrency===

===Zk-Snarks===

===Zk-Starks===

List of all relevant zk-papers

2021-05-05T13:41:06Z

Srikar:

List of all relevant zk-papers

2021-05-05T13:40:46Z

Srikar:

*[[The Knowledge Complexity of Interactive Proof Systems]]
*[[Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes]]
*[[Private Coins versus Public Coins in Interactive Proof Systems]]

===Quantum===

===Blockchain and Cryptocurrency===

===Zk-Snarks===

===ZK-Starks===

Glossary

2021-05-05T13:39:29Z

Srikar:

In the zk world, there are many terms and definitions that might not be familiar to the uninitiated reader. This introduces a large hurdle for those interested in this exploding field. This Glossary attempts to bridge that gap. 

== Glossary ==
* [[Zap]]
* [[SNARK]]
* [[STARK]]
* [[BulletProof]]
* [[Pedersen Commitment]]
* [[Homomorphic encryption]]
* [[Arthur-Merlin Games]]
* [[Sigma Protocol]]
* [[Yao's Millionaire Problem]]
* [[Fiat-Shamir Heuristic]]
* [[Random Oracle Model]]
* [[Public Coin Protocols]]
* [[Private Coin Protocols]]
* [[Non Interactive Zero Knowledge Proofs (NIZK)]]
* [[Standard model]]
* [[Common Reference String]]
* [[Statistical Soundness]]
* [[Computational Soundness]]
* [[SNARG]]
* [[ECRH]]
* [[Promise Problem]]
* [[Statistical Difference]]
* [[Witness indistinguishability]]
* [[Bilinear Pairing]]
* [[Completeness]]
* [[Auxillary Input ZK]]
* [[Twist Security]]
* [[Weil pairing]]
* [[Miller's Algorithm]]
* [[QAP]]
* [[QSP]]
* [[SSP]]
* [[Progression Free Sets]]
* [[LIP]]
* [[Generic Group Model]]
* [[Type 1 Bilinear Group]]
* [[Type 2 Bilinear Group]]
* [[Type 3 Bilinear Group]]
* [[NILP]]
* [[Paillier Encryption]]
* [[Algebraic Group Model]]
* [[Knowledge of Exponent Assumption]]
* [[Preprocessing SNARK]]
* [[Computation Commitments]]
* [[SXDH assumption]]
* [[Sum-Check Protocol]]
* [[Assistant]]
* [[Inner Product Proof System]]
* [[Bilinear Inner Product Proof System]]
* [[Extractable Polynomial Commitment Scheme]]
* [[Polynomial Commitment Scheme]]
* [[Sum-Check Protocol]]
* [[Non-Falsifiable Assumption]]
* [[Round by Round Soundness]]
* [[IOP]]
* [[Reed Solomon Fingerprinting]]
* [[FRI]]
* [[Kate Commitments]]
* [[DARK]]
* [[Poseidon Hash Function]]
* [[Mimic hash function]]

Zk Implementation Tutorial from 0-1

2021-05-04T22:38:50Z

Srikar: Created page with "Before beginning with the ZK journey, it is good to keep in mind the hardware requirements and the machines being used. AWS - EC2 instance -"

Before beginning with the ZK journey, it is good to keep in mind the hardware requirements and the machines being used.
AWS - EC2 instance -

Main Page

2021-05-04T22:36:51Z

Srikar:

This wiki intends to be a complete and (mostly) self-contained repository of zero knowledge protocols related work for researchers and interested practitioners. 

== Contents ==
* [[Key Theorems and Proofs]]
* [[Zk in Implementation]]
* [[Glossary]]
* [[List of all relevant zk-papers]]
* [[Zk in Blockchain and Cryptocurrency]]
* [[Common Questions and Nuances]]
* [[Open Problems]]
* [[Zk Implementation Tutorial from 0-1]]

DARK

2021-05-04T22:32:34Z

Srikar: Created page with "Refers to a Diophantine Argument of Knowledge."

Refers to a Diophantine Argument of Knowledge.

How does generating the SRS with secure MPC work?

2021-05-04T19:27:29Z

Srikar:

A good blog post from the Qedit team [https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7]

How does generating the SRS with secure MPC work?

2021-05-04T19:27:21Z

Srikar: Created page with "A good blog post from the Qedit team https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7"

A good blog post from the Qedit team [[https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7]]

Common Questions and Nuances

2021-05-04T19:26:57Z

Srikar:

* [[What is the relationship between a zk-snark and a Linear Interactive Proof?]]
* [[What is the difference between the Common Reference String Model and the ROM Model]]
* [[Why does Fiat-Shamir and ROM model fail in practice?]]
* [[What is the Linear in a Linear Interactive Proof?]]
* [[What is a holographic proof?]]
* [[Why does using an asymmetric billinear group setting yield more efficiency than the symmetric case in Groth16 and Pinocchio?]]
* [[How do SNARKs compose?]]
* [[What are Non-Falsifiable Assumptions?]]
* [[What is the difference between a transparent SNARK and a STARK?]]
* [[What are the R1CS constraints of a cryptocurrency system like ZCash?]]
* [[How does generating the SRS with secure MPC work?]]

Zk in Implementation

2021-05-04T19:25:11Z

Srikar:

* [[Pinocchio]]
* [[Groth16]]
* [[Hyrax]]
* [[Marlin]]
* [[Plonk]]
* [[Sonic]]
* [[BulletProofs]]
* [[Fractal]]
* [[SuperSonic]]
* [[Spartan]]
* [[Kopis]]
* [[Xiphos]]
* [[LibSnark Library]]
* [[JSnark Library]]
* [[ZKBoo]]
* [[Ligero]]
* [[Aurora]]
* [[Libra]]

SNARK

2021-05-04T17:41:51Z

Srikar: /* Subversion ZK */

===Succinct Non-Interactive ARgument of Knowledge===

Glossary

2021-05-04T06:50:09Z

Srikar:

Plonk

2021-05-04T06:42:04Z

Srikar:

Plonk is a general purpose zk-scheme that has a universal and updateable setup [https://vitalik.ca/general/2019/09/22/plonk.html].
The primitives and tools used:
* [[Kate Commitments]]
*

Plonk

2021-05-04T06:41:56Z

Srikar:

Plonk is a general purpose zk-scheme that has a universal and updateable setup [https://vitalik.ca/general/2019/09/22/plonk.html].
The primitives and tools used:
* [Kate Commitments]
*

Plonk

2021-05-04T06:40:14Z

Srikar:

Plonk is a general purpose zk-scheme that has a universal and updateable setup [https://vitalik.ca/general/2019/09/22/plonk.html].

Plonk

2021-05-04T06:38:45Z

Srikar:

Plonk is a general purpose zk-scheme that has a universal and updateable setup [https://vitalik.ca/general/2019/09/22/plonk.html].<ref>https://vitalik.ca/general/2019/09/22/plonk.html</ref>

Plonk

2021-05-04T06:37:40Z

Srikar: Created page with "Plonk is a general purpose zk-scheme that has a universal and updateable setup [https://vitalik.ca/general/2019/09/22/plonk.html]."

Plonk is a general purpose zk-scheme that has a universal and updateable setup [https://vitalik.ca/general/2019/09/22/plonk.html].

IP = PSPACE

2021-05-03T12:33:30Z

Srikar:

General proof sketch:

1. We consider the language <math>\#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.

<math> \#SAT_D = \{\langle \phi, K\rangle: \text{ K is the number of satisfying assignments of }\phi\} </math>

where <math>\phi</math> is a 3CNF formula. Prove that <math>\#SAT_D \in \mathsf{IP}</math> via arithmetization and the sumcheck protocol.

2. Arithmetization is the idea of converting boolean formulae to an algebraic form. So, <math>x\land y</math> can be represented by <math>x\cdot y</math> and <math>\neg x</math> can be represented by <math>1-x</math> and <math>x\lor y</math> can be represented by <math>1 - (1- x)(1-y)</math>.

3. Sumcheck protocol: add general description of the sumcheck protocol

4. Using a very similar idea we then prove that <math>\mathsf{TQBF} \in \mathsf{IP}</math> and since <math>\mathsf{TQBF}</math> is <math>\mathsf{PSPACE}</math>-complete, we have that <math>\mathsf{PSPACE} \in \mathsf{IP}</math>.

5. And we know that <math>\mathsf{IP} \in \mathsf{PSPACE}</math> by the following argument. We know that the prover can use an arbitrary function, it can in principle use unbounded computational power. Therefore, given any verifier, the optimum prover strategy can be computed using <math>poly(|x|)</math> and <math>2^{poly(\abs{x})}</math> time. This is by brute forcing through the possible space of prover verifier communication, optimizing for the probability of acceptance by the verifier. This takes polynomial space, hence <math>\mathsf{IP} \in \mathsf{PSPACE}</math>.

IP = PSPACE

2021-05-03T12:33:16Z

Srikar:

General proof sketch:

1. We consider the language <math>#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.

<math> \#SAT_D = \{\langle \phi, K\rangle: \text{ K is the number of satisfying assignments of }\phi\} </math>

where <math>\phi</math> is a 3CNF formula. Prove that <math>\#SAT_D \in \mathsf{IP}</math> via arithmetization and the sumcheck protocol.

2. Arithmetization is the idea of converting boolean formulae to an algebraic form. So, <math>x\land y</math> can be represented by <math>x\cdot y</math> and <math>\neg x</math> can be represented by <math>1-x</math> and <math>x\lor y</math> can be represented by <math>1 - (1- x)(1-y)</math>.

3. Sumcheck protocol: add general description of the sumcheck protocol

4. Using a very similar idea we then prove that <math>\mathsf{TQBF} \in \mathsf{IP}</math> and since <math>\mathsf{TQBF}</math> is <math>\mathsf{PSPACE}</math>-complete, we have that <math>\mathsf{PSPACE} \in \mathsf{IP}</math>.

5. And we know that <math>\mathsf{IP} \in \mathsf{PSPACE}</math> by the following argument. We know that the prover can use an arbitrary function, it can in principle use unbounded computational power. Therefore, given any verifier, the optimum prover strategy can be computed using <math>poly(|x|)</math> and <math>2^{poly(\abs{x})}</math> time. This is by brute forcing through the possible space of prover verifier communication, optimizing for the probability of acceptance by the verifier. This takes polynomial space, hence <math>\mathsf{IP} \in \mathsf{PSPACE}</math>.

Kate Commitments

2021-05-03T07:09:55Z

Srikar:

It is a type of [[Polynomial Commitment Scheme]]. This ETH-Research post [https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html] is a good overview.

Kate Commitments

2021-05-03T07:09:16Z

Srikar:

It is a type of [[Polynomial Commitment Scheme]]. This post [[https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html]]

Kate Commitments

2021-05-03T07:08:39Z

Srikar:

It is a type of [[Polynomial Commitment Scheme]]

Kate Commitments

2021-05-03T07:07:45Z

Srikar: Created page with "It is a type of Polynomial Commitments."

It is a type of [[Polynomial Commitments]].

Polynomial Commitment Scheme

2021-05-03T07:05:45Z

Srikar: Created blank page

Zk in Implementation

2021-05-03T03:22:08Z

Srikar:

Zk in Blockchain and Cryptocurrency

2021-05-02T17:06:41Z

Srikar:

*[[Zk Rollups]]
*[[ZCash]]
*[[Zk Sync]]
*[[Coda Protocol - Recursive Snarks]]
*[[Starkware]]
*[[Aleo]]

Zk in Blockchain and Cryptocurrency

2021-05-02T17:06:19Z

Srikar:

*[[Zk Rollups]]
*[[ZCash]]
*[[Zk Sync]]
*[[Coda Protocol - Recursive Snarks]]
*[[Starkware]]

Zk in Blockchain and Cryptocurrency

2021-05-02T17:03:06Z

Srikar:

*[[Zk Rollups]]

Zk in Blockchain and Cryptocurrency

2021-05-02T17:02:57Z

Srikar: Created page with "Zk Rollups"

[[Zk Rollups]]

Main Page

2021-05-02T17:02:40Z

Srikar:

Key Theorems and Proofs

2021-05-02T17:01:52Z

Srikar:

*[[IP = PSPACE]]
*[[Fiat Shamir is Secure in ROM]]
*[[Fiat Shamir is Insecure if ROM does not exist]]
*[[One-shot ZK is impossible in the standard model]]
*[[NIZK is possible in the CRS model]]
*[[Complexity class SZKP is closed under complement]]
*[[CZKA versus co-CZKA symmetry theorem]]
*[[SZKA versus CZKP symmetry theorem]]
*[[SZK/OWF Characterization Theorem]]

Main Page

2021-05-02T17:01:39Z

Srikar:

Main Page

2021-05-02T17:01:33Z

Srikar:

This wiki intends to be a complete and (mostly) self-contained repository of zero knowledge protocols related work for researchers and interested practitioners. 

== Contents ==
* [[Key Theorems and Proofs]]
* [[Zk in Implementation]]
* [[Glossary]]
* [[List of all relevant zk-papers]]
* [[Common Questions and Nuances]]
* [[Open Problems]]

<math E=mc^2 /math>

Main Page

2021-05-02T17:01:07Z

Srikar:

This wiki intends to be a complete and (mostly) self-contained repository of zero knowledge protocols related work for researchers and interested practitioners. 

== Contents ==
* [[Key Theorems and Proofs]]
* [[Zk in Implementation]]
* [[Glossary]]
* [[List of all relevant zk-papers]]
* [[Common Questions and Nuances]]
* [[Open Problems]]

<math>E=mc^2</math>

Main Page

2021-05-02T17:00:58Z

Srikar: /* Contents */

This wiki intends to be a complete and (mostly) self-contained repository of zero knowledge protocols related work for researchers and interested practitioners. 

== Contents ==
* [[Key Theorems and Proofs]]
* [[Zk in Implementation]]
* [[Glossary]]
* [[List of all relevant zk-papers]]
* [[Common Questions and Nuances]]
* [[Open Problems]]

math>E=mc^2</math>

What are the R1CS constraints of a cryptocurrency system like ZCash?

2021-04-28T14:59:06Z

Srikar:

This was answered fairly well by the stackexchange post: https://crypto.stackexchange.com/questions/65927/what-is-the-precise-np-statement-of-zcash

In particular, some high level constraints are:

1. For every shielded transfer, the input values sum to the output values
2. The sender proves that they have the spending keys for the input
3. The private sending keys are linked to a signature over the whole transaction in such a way that it cannot be forged by someone who does not know the keys

What are the R1CS constraints of a cryptocurrency system like ZCash?

2021-04-28T14:59:00Z

Srikar:

This was answered fairly well by the stackexchange post: https://crypto.stackexchange.com/questions/65927/what-is-the-precise-np-statement-of-zcash

In particular, some high level constraints are:

1. For every shielded transfer, the input values sum to the output values \\
2. The sender proves that they have the spending keys for the input
3. The private sending keys are linked to a signature over the whole transaction in such a way that it cannot be forged by someone who does not know the keys

What are the R1CS constraints of a cryptocurrency system like ZCash?

2021-04-28T14:58:50Z

Srikar: Created page with "This was answered fairly well by the stackexchange post: https://crypto.stackexchange.com/questions/65927/what-is-the-precise-np-statement-of-zcash In particular, some high l..."

Common Questions and Nuances

2021-04-28T14:55:31Z

Srikar:

LibSnark Library

2021-04-28T14:50:03Z

Srikar: Created page with "The libsnark library contains an implementation for zk preprocessing of the R1CS NP-Complete language."

The libsnark library contains an implementation for zk preprocessing of the R1CS NP-Complete language.

Zk in Implementation

2021-04-28T14:49:28Z

Srikar:

* [[Pinocchio]]
* [[Groth16]]
* [[Hyrax]]
* [[Marlin]]
* [[Plonk]]
* [[Sonic]]
* [[BulletProofs]]
* [[Fractal]]
* [[SuperSonic]]
* [[Spartan]]
* [[Kopis]]
* [[Xiphos]]
* [[LibSnark Library]]

Glossary

2020-10-22T09:39:25Z

Srikar: /* Glossary */

Glossary

2020-10-20T16:55:48Z

Srikar: /* Glossary */

Glossary

2020-10-20T16:52:41Z

Srikar: /* Glossary */

Glossary

2020-10-19T23:44:53Z

Srikar:

Glossary

2020-10-19T19:21:06Z

Srikar: /* Glossary */

Glossary

2020-10-19T18:35:44Z

Srikar: /* Glossary */

Glossary

2020-10-19T18:31:19Z

Srikar: /* Glossary */

Glossary

2020-10-19T16:32:02Z

Srikar: /* Glossary */