Commitment

Two security properties about commitment:

  • Binding: Two different statements can't make the same commitment
  • Hiding: Given a commitment, nothing is known about the statement

Commitment scheme 中的 Setup(\(1^\lambda\)) 中

In the context of a commitment scheme, Setup(\(1^\lambda\)) refers to a probabilistic polynomial-time (PPT) algorithm that takes a security parameter (in unary) and generates public parameters. The notation \(1^\lambda\) means that the input to the algorithm is a string of \(\lambda\) ones, which is used as the security parameter.

In computer science, unary refers to a numeral system in which each natural number is represented by a corresponding number of 1s. For example, the number 3 would be represented as "111" in unary. Therefore, in the context of a security parameter, \(1^\lambda\) means that the input to the algorithm is a string of \(\lambda\) ones. In the unary numeral system, the number 10 is represented by ten ones: "1111111111".

PPT Algorithm stands for Probabilistic Polynomial-Time Algorithm. It is an algorithm that runs in polynomial time but also has access to some oracle that provides true random bits12. The algorithm is used in cryptography and is a type of randomized algorithm

Overview of Modern SNARKs

The modern SNARK has three gradients: arithmetization, IOP interactive oracle proof, and a commitment scheme, which leads to a non-interactive proof system. Arithmetization involves reducing the complexity of checking correctness into a less complex circuit satisfaction problem by making computations compatible with IOP. IOP is an idealized protocol that involves interaction between the prover and verifier, where the verifier sends a message and the prover responds with an oracle. The commitment scheme compiles the idealized protocol to a real-world realization using cryptographic assumptions. Finally, a Fiat-Shamir transform is used to obtain a non-interactive proof by hashing the history of interaction into a transcript and deriving randomness in a public way.

Arithmetization --> IOP interactive oracle proof --compiled by --> commitment scheme -->a real-world proof system （a non-interactive proof）

  1. Arithmetization To make a real world program or computation compatible with the IOP, we need to arithmetize it. we need to reduce the complexity of checking the correctness into a less complex circuit satisfaction problem. We reduce the check to just a few probabilistic algebraic checks.

    The correctness of the computation or arbitrary computation is reduced by arithmetization to some circuit satisfaction problems. and we then pick a suitable IOP to check the circuit satisfaction problem, and then we instantiate the IOP using the cryptographic compiler to get a proof system.

  2. The interactive oracle proof is an information-theoretical object. It makes some very idealized assumptions.

    IOP describes a serious interaction between the prover and verifier. The verifier sends a message to the prover, and the prover responds with oracle, which looks like a locked box. The prover can read the whole message sent by the verifier, but the verifier can only have restricted access to the prover's message that the verifier only read the prover's message using point queries that are randomized.

    IOP is information-theoretic so that it makes Soundness and zk guarantees that hold against the computationally unbounded prover and verifier. It's an idealized protocol that holds against idealized parties and adversaries.

    A cryptographic primitive known as a commitment scheme is a way to implement the physical boxes algorithmically. In other word, commitment scheme compiles the IOP from an idealized protocol to a real-world realization

    To realize or instantiate the idealized protocols, what we need is to introduce certain cryptographic assumptions (for example, discrete log assumption, and collisions of the hash functions).

    cryptographic compilers introduce a cryptographic assumption

  3. In Practice, we then get a non-interactive proof by using a Fiat-Shamir transform

    what the transform does is that it hashes the history of the interaction into a transcript, and uses the transcript the derive randomness in a public way so that the prover cannot predict the challenge picked by the verifier.

Commitment scheme

  1. Setup(1^) -> pp
  2. Commit(pp; m) -> (C; r)
  3. Open(pp; C; m, r) -> - 0\1

Vector commitments

Pederson commitment

The Pederson commitment scheme has hiding and binding properties based on the discrete log hard problem. It works over a finite field with prime order p, Fp.

The zero Knowledge property is not being cared about in the Pederson commitment.

  1. Setup(1^) -> pp=[\(|G|_p\) group with order p, \(G_1,G_2 \in G\)], where \(G_1\), \(G_2\) is two generator

  2. Commit(pp; m) -> (\(C=[m]G_1+[r]G_2\); r is random chosed from Fp) \([m]G_1\) is the additive notation, which means m times group operation of \(G_1\). It can also be seen as a sclar \(r\) multiply the group element \(G_1\). The multiplicative notation, g^m, can also be seen in other place, which also means m times group operation of \(g\)

  3. Open(pp; C; m, r) -> - \(C ?= [m]G_1+[r]G_2\)

    Normally, the open can be separated into two steps: Prove and Verify.

    1. Prove(pp, C, m, r) -> \(\pi\), where the proof is (m, r) in the Pederson commitment. The proof will not reveal the m and r in the KZG commitment.
    2. Verify(pp, C, \(\pi\)) -> 0,1

Pedersen is a homomorphic commitment scheme (additive homomorphism) that is computationally hiding and binding. \(Commitment(m_1 ◦ m_2) = Commitment(m_1) ◦ Commitment(m_2)\)

KZG10 is homomorphic polynomial commitments, but Merkle tree vector commitment is not one.

Homomorphic commitments: we require our commitments to support an homomorphic operation ◦. Requiring homomorphism rules out Merkle Trees as a solution. Homomorphic properties of commitments to “structured objects” have wide applications in cryptography (see, e.g., [KZG10] for homomorphic polynomial commitments). The homomorphic property is a natural one and allows many useful applications ref: Zero-Knowledge for Homomorphic Key-Value Commitments with Applications to Privacy-Preserving Ledgers

Vector Pederson Commitment

Vector Pederson Commitment is an extension used in the inner-product argument, which used in bulletproof. It's a really good proving system for efficient range proof.

It works over the message space of vectors, \(F^k_p\). vectors with k element from Fp.

  1. \(Setup(1^\lambda, k) -> {G_i}_{i=0}^{k-1}\)
  2. \(Commit(pp, m; r)​=[m_0​]G_0​+⋯+[m_{n−1}​]G_{n−1}​+[r]H=∑^{n−1}_{i=0}​[m_i​]G_i​\)+[r]H.​

The proof size of vector Pedersen commitment is linear, which is huge.

ref: Cryptographic groups - The halo2 Book

Vector Merkle tree Commitment

The commitment works over the message space string, \({0,1}_k\)

  1. \(Commitment(pp, \vec{m}) -> C = root(Merkle(\vec{m}))\)
  2. Open:
    1. \(Prove(pp, i, C, \vec{m}) -> \pi = (m[i], path)\)
    2. \(Verify(pp, i, C, \pi) -> 0/1\)

Polynomial commitments

KZG10

TODO

  • [ ]

Notice

道理上来讲，根据运算的记号不同（是 + 还是 x）针对群的乘法运算，用指数记法 G^{x}，针对群的加法运算： [x]G 和 xG 都可,都是对运算进行 x 遍，但是推荐 [x]G

实际上一般 paper 里面，基本混用，能看明白，表达清楚就好,就是符号记法习惯，为了与朴素加法乘法相容。

双线性映射：https://mp.weixin.qq.com/s/ug6PVMvR3UtGQgXZopWqgQ

二次非剩余的例子就是如何把 coNP 问题转化为交互式零知识证明,如果用经典的证明方式，除非遍历所有可能取值，否则无法证明对 NP 问题无解

References

  1. PPT Algorithm https://www.cs.miami.edu/home/burt/learning/csc609.221/notes/ppt-notes.pdf
  2. [./media/commitments.pdf]