Quiz【Lecture 2】 Overview of Modern SNARK Constructions

[Demian101]

下方提交

[Pupil1999]

Student name: Walker

Q1

How are SNARKs different from IPs?

1. SNARKs are arguments and not proofs, i.e., they only provide computational soundness - True
2. All SNARKs have sublinear proof size - True
3. All SNARKs have linear provers - False
4. All SNARKs have sublinear verifier - True
5. All SNARKs prove NP statements - True
6. SNARKs are non-interactive - True
7. SNARKs are knowledge-sound - True

Reasons:

1. I'm confused. IP also only has computational soundness, so why it's different from SNARK?
2. by definition
3. Some have prover in $O(ClogC)$.
4. by definition
5. No need to prove P, caz prover can compute itself right?
6. by definition
7. by definition

Q2

Which of the following are true about preprocessing SNARKs?

1. Preprocessing is required to speed up SNARK prover - False
2. We can not construct SNARKs for general circuits without preprocessing - True
3. If the secrets used in the trusted setup are revealed, the SNARK prover can violate soundness - True
4. SNARKs with transparent setup can not be made zero-knowledge since the setup can not have secrets - False

Reasons:

1. Preprocessing is used to instantiate the system, and by the way, speed up both sides in some cases.
2. Preprocessings are necessary to instantiate the system, they differ in whether they are transparent or not.
3. For example, in KZG commitment, the reveal of $\tau$ can lead to committing to a polynomial but opening at another polynomial.
4. Witness is not hidden in setup.

Q3

Which of the following are true about the components used to construct SNARKs?

1. Functional commitment schemes are SNARKs that support a restricted class of functions - True
2. An unbounded prover can't break the knowledge soundness of an Interactive oracle proof (IOP) - True
3. SNARKs can only be made from IOPs that use efficiently-realizable oracles because the verifier has to query these oracles - False
4. Functional commitments are used to instantiate the oracles in IOPs - True
5. To make a SNARK zero-knowledge, we use a hiding functional commitment scheme - True

Reasons:

1. Functional commitments can prove that someone knows a polynomial by querying a point on it. Now we have some schemes for univariate or multivariate polynomials, but we don't have schemes for, say, exponential functions.
2. IOP is information-theoretically sound.
3. Verifier can aggregate queries into one.
4. IOP + Commitment = Snark
5. Yes, just add some random numbers.

Q4

Which of the following are true about the SNARK for polynomial equality testing?

1. The oracles in the corresponding IOP have a degree bound to ensure that the oracle is efficiently realizable - False
2. The oracles in the corresponding IOP have a degree bound to ensure that any inconsistencies in the input polynomials are detected - True
3. The corresponding IOP can be made non-interactive using the Fiat-Shamir transform because it is public-coin - True
4. We can replace the polynomial commitment with a vector commitment that commits to all evaluations of the polynomial to construct this SNARK, albeit at a performance penalty - False

Reasons:
1.2. The verifier is convinced that the committed polynomial has degree lower than the bound.
4. It's not succinct that we just send every committed evaluations.

[kurtpan666]

Q1:

1. SNARKs are arguments and not proofs, i.e., they only provide computational soundness - True

• Statistical/Information-theoretically Sound Proofs = Proofs
• Computationally Sound Proofs = Arguments
• IPs are against unbounded malicious prover , therefore satisfies the definition of a Proof (not only an Argument).

3. All SNARKs have linear provers - False

• Quasi-linear prover is enough for most cases

5. All SNARKs prove NP statements - True

• In the random oracle model, it is known that there are SNARGs for every NP language [Kil92, Mic94].
• All ZKPs prove NP statements - False : $IP \subseteq CZK$
• ZKPs for languages in $\mathcal{BPP}$ are trivial (verifier can decide for himself), but SNARKs are not trivial even for (subsets of) $\mathcal{P}$. This is not necessary for "hard languages", but useful whenever it can compress computation and can speed up verification.

Q2:

1. Preprocessing is required to speed up SNARK prover - False

• Preprocessing is required to speed up SNARK verifier- True (V has not time to read C w/o preprocessing)

2. We can not construct SNARKs for general circuits without preprocessing - True

• but we do can construct NARKs/NIZKPoK for general circuits without preprocessing , and also can construct SNARKs for specific circuits without preprocessing, also general interactive ZKP for general circuits without preprocessing.

Q3

1. We DO have SoTA Functional Commitments for All Functions, with Transparent Setup and from SIS, including any non-linear functions.

[Einstellung]

student name: 饭卡

1. How are SNARKs different from IPs?

• SNARKs are arguments and not proofs, i.e., they only provide computational soundness (True)

比如离散对数问题，我们只假设攻击者有有限的计算资源。

• All SNARKs have sublinear proof size (True)

随着输入大小的增加，SNARK的大小增加的更慢，这使得SNARK在处理大数据集时特别有用，因为它可以生成大小相对更小的证据。

• All SNARKs have linear provers (False)

创建prove的过程所需的时间可能超过线性。

• All SNARKs have sublinear verifier (True)

• All SNARKs prove NP statements (False)

非NP也行。

• SNARKs are non-interactive (True)
• SNARKs are knowledge-sound (True)

2. Which of the following are true about preprocessing SNARKs?

• Preprocessing is required to speed up SNARK prover (False)

Setup是用来构建非交互式的重要步骤，而不是用来加速。

• We can not construct SNARKs for general circuits without preprocessing (True)

构造SNARK需要setup

• If the secrets used in the trusted setup are revealed, the SNARK prover can violate soundness (True)

Setup阶段会生成一些toxic waste,这些信息不能被公开，否则会造成SNARK不安全性。

• SNARKs with transparent setup can not be made zero-knowledge since the setup can not have secrets (False)

"透明"的设置意味着没有秘密参数，任何人都可以验证设置过程的正确性。然而，这并不排除零知识性质。实际上，有一些 SNARK 构造（如 PLONK 或 Halo）具有透明的设置，并且仍然具有零知识性质。

3. Which of the following are true about the components used to construct SNARKs?

   • Functional commitment schemes are SNARKs that support a restricted class of functions (True)

   功能承诺方案可以在构建支持限制类函数的 SNARKs 时发挥关键作用。这是因为这些功能承诺方案可以锁定数据，同时允许 SNARK 对这些数据执行特定的计算，而不会泄露其他信息。

   • An unbounded prover can't break the knowledge soundness of an Interactive oracle proof (IOP) (True)
   • SNARKs can only be made from IOPs that use efficiently-realizable oracles because the verifier has to query these oracles (False)

   因为虽然在IOPs（Interactive Oracle Proofs）中，验证者确实需要查询预言机，但是在SNARKs（Succinct Non-interactive ARguments of Knowledge）中，验证者不直接查询预言机。在构建SNARKs时，我们通常会使用一种称为Fiat-Shamir变换的技术，将交互式证明协议（如IOPs）转换为非交互式的证明协议。

   • Functional commitments are used to instantiate the oracles in IOPs (True)

   在构建 SNARKs 的过程中，我们通常会使用功能承诺方案来实例化 IOP 中的预言。

   • To make a SNARK zero-knowledge, we use a hiding functional commitment scheme (True)

   在构建零知识 SNARKs 的过程中，我们通常会使用隐藏的功能承诺方案。隐藏的功能承诺方案可以确保即使一个恶意的验证者可以访问承诺，也无法获得任何关于承诺值的信息。

4. Which of the following are true about the SNARK for polynomial equality testing?

   • The oracles in the corresponding IOP have a degree bound to ensure that the oracle is efficiently realizable (False)

   • The oracles in the corresponding IOP have a degree bound to ensure that any inconsistencies in the input polynomials are detected (True)

   在交互式预言机证明（Interactive Oracle Proofs, IOPs）中，预言机通常会承载一个多项式的信息。验证者会对这个预言机进行一系列的查询（例如，请求多项式在某些点的值）以检测多项式是否满足特定的性质。为了确保验证者可以有效地检测到任何的不一致性，预言机中的多项式通常会有一个度数上限。

   这个度数上限保证了多项式的复杂性在一个可控的范围内，使得验证者可以通过有限的查询检测到任何不一致性。如果多项式的度数过高，验证者可能需要进行过多的查询才能检测到不一致性，这会降低证明系统的效率。

   • The corresponding IOP can be made non-interactive using the Fiat-Shamir transform because it is public-coin (True)

   如果一个 IOP 是公共硬币的（也就是说，验证者的所有查询都是随机选择的），那么我们可以使用 Fiat-Shamir 变换将其转化为一个非交互式的证明系统。这是因为 Fiat-Shamir 变换的基本思想就是将验证者的随机查询替换为一个由证明者和验证者共享的随机源，从而消除了证明者和验证者之间的交互过程。

   • We can replace the polynomial commitment with a vector commitment that commits to all evaluations of the polynomial to construct this SNARK, albeit at a performance penalty (False)

   除了导致性能显著下降之外，这可能还会引入其他的问题，例如，向量承诺可能无法提供多项式承诺所能提供的某些密码学性质，这可能会影响SNARK的安全性和有效性。