R1CS(Rank-1 Constraint System)是一种用于构建零知识证明的系统,它可以用于证明一个人知道满足一组多项式等式的解,而不必透露任何关于解的信息[1]。传统的R1CS系统需要在证明过程中使用大量的随机性,这会导致证明的生成和验证过程非常复杂和耗时。

R1CS的转换过程通常包括以下几个步骤:

  1. Flattening:将计算问题的代码转换为一系列基本操作,如赋值和算术运算[2]
  2. R1CS转换:将Flattening的结果转化为一阶约束系统R1CS,其中R1CS由三个向量构成的向量组组成。解向量满足约束条件[2]
  3. 零知识证明系统构建:基于R1CS的约束条件和解向量,构建一个实际的零知识证明系统,使得证明者可以证明自己知道满足约束条件的解,而不需要透露解的具体信息[2]

R1CS的应用非常广泛,特别是在零知识证明和密码学领域。它可以用于构建各种零知识证明系统,如zk-SNARKs(零知识可验证的非交互式证明系统),用于验证计算的正确性而不泄露敏感信息[2]

Rank-1 Constraint Systems

Notation

In order to explain how zk-SNARKs work, we’ll borrow notation common in the Bulletproofs literature, as it may be familiar with readers.

  • We use uppercase letters like , , and to describe elements of a group which is of prime order . In practice these will be elements of either or .
  • We use lowercase letters like , and to describe scalars — elements of .
  • We use boldface to describe vectors: is a vector of scalars and is a vector of group elements. We use to describe vectors of polynomials with indeterminate . We use to describe vectors of scalars that are sequences of powers of some .
  • We use the notation to describe the inner product of two vectors — in other words, the elements of each vector are multiplied pairwise, and the products are summed together. Note that produces a scalar and produces a group element.

R1CS

zk-SNARKs are zero-knowledge proofs which allow us to prove that we performed a computation over some witness without revealing that witness. We express our computations in the form of arithmetic constraint systems.

Given an assignment of variables in , a rank-1 constraint system is a system of quadratic constraints of the form , where are linear combinations of our variable assignment. If we always set , then these constraint systems can express any bounded computation.

  • We can boolean constrain a variable with the constraint , because squaring is the identity for only and in a field.
  • Given a boolean constrained variable , we can express as .
  • Given two boolean constrained variables , we can express as .

As an example, consisider the constraint system:

The first two constraints are boolean constraints over and , respectively. The third constraint is actually an XOR constraint: you’ll see through substitution that must equal .

All of the terms of the constraint system are linear combinations of every variable; in other words, the above constraint system can be equivalently expressed with a zero coefficient for every omitted variable:

Let’s begin to describe our constraint system using the inner product notation and coefficients represented by fixed vectors :

More generally, our goal is to demonstrate that we know a satisfying assignment for which holds for all given fixed coefficients . If we can do this without revealing , and non-interactively with succinct proofs, we’ll have a zk-SNARK.