Gabizon等人2019年论文《PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge》。
本文主要针对的代码库为：
- https://github.com/dusk-network/plonk 【rust语言实现，在v0.1.0版本配有examples】
Plonk论文中，constraint 类型分为：【可参考Module dusk_plonk::notes ::prove_verify 文档】
- gate constraint：用于表示add,mul,and,xor等常规gate的运算关系。
- copy constraint：用于表示wires之间的关系，which have equality, from the entire circuit。copy constraint可通过permutation argument来验证。本质上，可通过Verifier给出的随机值来验证wires是否是不重复的。
主要见https://github.com/dusk-network/plonk/tree/master/src/commitment_scheme，采用的曲线为bls12-381。
- BlsScalar：表示scalar field
- G1Affine，G1Projective：表示group point，实际commitment采用G1Affine来表示，而借助.into()函数可将G1Projective转换为G1Affine形式。
identity是指无穷远点 ( 0 , 1 , 1 ) (0,1,1) (0,1,1)。满足任意点与该identity相加均为该点。
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
/// Holds a commitment to a polynomial in a form of a `G1Affine` Bls12_381 point.
pub struct Commitment(
/// The commitment is a group element.
pub G1Affine,
);
https://github.com/dusk-network/plonk代码库中，实际实现是参考了 Kate等人2010年论文[kzg10]《Polynomial Commitments∗》中 不具有hiding属性的 3.2节“ P o l y C o m m i t D L PolyCommit_{DL} PolyCommitDL” 的属性，只是实际实现，采用的不是 symmetric pairing e : G × G → G T e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T e:G×G→GT，而 unsymmetric pairing e : G 1 × G 2 → G T e:\mathbb{G}_1\times \mathbb{G}_2\rightarrow \mathbb{G}_T e:G1×G2→GT。
2.1 [kzg10] 单个多项式polynomial commitment以degree 为 t t t的单个多项式 ϕ ( x ) ∈ Z p [ x ] \phi(x)\in\mathbb{Z}_p[x] ϕ(x)∈Zp[x]为例，构建polynomial commitment的数学背景为： ϕ ( x ) − ϕ ( z ) x − z \frac{\phi(x)-\phi(z)}{x-z} x−zϕ(x)−ϕ(z) 不存在余数 for z ∈ Z p z\in\mathbb{Z}_p z∈Zp。 g g g为generator of G 1 \mathbb{G}_1 G1， h h h为generator of G 2 \mathbb{G}_2 G2。
- S e t u p ( t ) → p p Setup(t)\rightarrow pp Setup(t)→pp：输出的public parameters p p pp pp中包含 Prover用于生成proof的commit_key 和 Verifier用于verify的opening_key。 public parameters 又称为 structured reference string (srs)。 选择 β ∈ R Z p \beta\in_R\mathbb{Z_p} β∈RZp为secret key S K SK SK，相应的： commit_key为： ( g , g β , ⋯ , g β t ) ∈ G 1 t + 1 (g,g^{\beta},\cdots,g^{\beta^t})\in\mathbb{G}_1^{t+1} (g,gβ,⋯,gβt)∈G1t+1 【Prover使用】 opening_key为： g ∈ G 1 , ( h , h β ) ∈ G 2 2 g\in\mathbb{G}_1,(h,h^{\beta})\in\mathbb{G}_2^2 g∈G1,(h,hβ)∈G22 【Verifier使用】
/// The Public Parameters can also be referred to as the Structured Reference String (SRS).
/// It is available to both the prover and verifier and allows the verifier to
/// efficiently verify and make claims about polynomials up to and including a configured degree.
#[derive(Debug, Clone)]
pub struct PublicParameters {
/// Key used to generate proofs for composed circuits.
pub commit_key: CommitKey,
/// Key used to verify proofs for composed circuits.
pub opening_key: OpeningKey,
}
/// Setup generates the public parameters using a random number generator.
/// This method will in most cases be used for testing and exploration.
/// In reality, a `Trusted party` or a `Multiparty Computation` will used to generate the SRS.
/// Returns an error if the configured degree is less than one.
pub fn setup(
max_degree: usize,
mut rng: &mut R,
) -> Result {
// Cannot commit to constants
if max_degree < 1 {
return Err(Error::DegreeIsZero);
}
// Generate the secret scalar beta
let beta = util::random_scalar(&mut rng);
// Compute powers of beta up to and including beta^max_degree
let powers_of_beta = util::powers_of(&beta, max_degree);
// Powers of G1 that will be used to commit to a specified polynomial
let g = util::random_g1_point(&mut rng);
let powers_of_g: Vec=
util::slow_multiscalar_mul_single_base(&powers_of_beta, g);
assert_eq!(powers_of_g.len(), max_degree + 1);
// Normalise all projective points
let mut normalised_g = vec![G1Affine::identity(); max_degree + 1];
G1Projective::batch_normalize(&powers_of_g, &mut normalised_g);
// Compute beta*G2 element and stored cached elements for verifying multiple proofs.
let h: G2Affine = util::random_g2_point(&mut rng).into();
let beta_h: G2Affine = (h * beta).into();
Ok(PublicParameters {
commit_key: CommitKey {
powers_of_g: normalised_g,
},
opening_key: OpeningKey::new(g.into(), h, beta_h),
})
}
- C o m m i t ( commit_key , ϕ ( x ) ) → C Commit(\text{commit\_key},\phi(x))\rightarrow \mathcal{C} Commit(commit_key,ϕ(x))→C：对多项式 ϕ ( x ) = ∑ j = 0 d e g ( ϕ ) ϕ j x j \phi(x)=\sum_{j=0}^{deg(\phi)}\phi_jx^j ϕ(x)=∑j=0deg(ϕ)ϕjxj进行commit，输出相应的commitment C = g ϕ ( β ) = ∏ j = 0 d e g ( ϕ ) ( g β j ) ϕ j \mathcal{C}=g^{\phi(\beta)}=\prod_{j=0}^{deg(\phi)}(g^{\beta^j})^{\phi_j} C=gϕ(β)=∏j=0deg(ϕ)(gβj)ϕj。
/// Commits to a polynomial returning the corresponding `Commitment`.
///
/// Returns an error if the polynomial's degree is more than the max degree of the commit key.
pub fn commit(&self, polynomial: &Polynomial) -> Result {
// Check whether we can safely commit to this polynomial
self.check_commit_degree_is_within_bounds(polynomial.degree())?;
// Compute commitment
let commitment = msm_variable_base(&self.powers_of_g, &polynomial.coeffs);
Ok(Commitment::from_projective(commitment))
}
- O p e n _ s i n g l e ( commit_key , ϕ ( x ) , v , z ) → π Open\_single(\text{commit\_key},\phi(x), v, z)\rightarrow \pi Open_single(commit_key,ϕ(x),v,z)→π：即证明 ϕ ( z ) = v \phi(z)=v ϕ(z)=v，输出为opening proof π \pi π。 实际的witness为 ψ ( x ) = ϕ ( x ) − ϕ ( z ) x − z \psi(x)=\frac{\phi(x)-\phi(z)}{x-z} ψ(x)=x−zϕ(x)−ϕ(z) 对应的commitment π = g ψ ( β ) \pi=g^{\psi(\beta)} π=gψ(β)。
/// Creates an opening proof that a polynomial `p` was correctly evaluated at p(z) and produced the value
/// `v`. ie v = p(z).
/// Returns an error if the polynomials degree is too large.
pub fn open_single(
&self,
polynomial: &Polynomial,
value: &BlsScalar,
point: &BlsScalar,
) -> Result {
let witness_poly = self.compute_single_witness(polynomial, point);
Ok(Proof {
commitment_to_witness: self.commit(&witness_poly)?,
evaluated_point: *value,
commitment_to_polynomial: self.commit(polynomial)?,
})
}
/// 这段注释有问题。。。。。。
/// For a given polynomial `p` and a point `z`, compute the witness
/// for p(z) using Ruffini's method for simplicity.
/// The Witness is the quotient of f(x) - f(z) / x-z.
/// However we note that the quotient polynomial is invariant under the value f(z)
/// ie. only the remainder changes. We can therefore compute the witness as f(x) / x - z
/// and only use the remainder term f(z) during verification.
pub fn compute_single_witness(&self, polynomial: &Polynomial, point: &BlsScalar) -> Polynomial {
// Computes `f(x) / x-z`, returning it as the witness poly
polynomial.ruffini(*point)
}
- V e r i f y E v a l _ s i n g l e ( opening_key , π , z , v , C ) → 0 or 1 VerifyEval\_single(\text{opening\_key},\pi,z,v,\mathcal{C})\rightarrow 0\text{ or } 1 VerifyEval_single(opening_key,π,z,v,C)→0 or 1：Verifier根据Prover提供的proof和之前对polynomial的commitment C \mathcal{C} C 来确认相应的evaluation是否正确。 即仅需验证： e ( C / g v , h ) ⋅ e ( π , h ( z − β ) ) = 1 e(\mathcal{C}/g^v, h)\cdot e(\pi,h^{(z-\beta)})=1 e(C/gv,h)⋅e(π,h(z−β))=1 是否成立即可。
/// Checks that a polynomial `p` was evaluated at a point `z` and returned the value specified `v`.
/// ie. v = p(z).
pub fn check(&self, point: BlsScalar, proof: Proof) -> bool {
let inner_a: G1Affine =
(proof.commitment_to_polynomial.0 - (self.g * proof.evaluated_point)).into();
let inner_b: G2Affine = (self.beta_h - (self.h * point)).into();
let prepared_inner_b = G2Prepared::from(-inner_b);
let pairing = dusk_bls12_381::multi_miller_loop(&[
(&inner_a, &self.prepared_h),
(&proof.commitment_to_witness.0, &prepared_inner_b),
])
.final_exponentiation();
pairing == dusk_bls12_381::Gt::identity()
}
[kzg10]单个多项式 polynomial commitment scheme示例为：
#[test]
fn test_basic_commit() {
let degree = 25;
let (proving_key, opening_key) = setup_test(degree);
let point = BlsScalar::from(10);
let poly = Polynomial::rand(degree, &mut rand::thread_rng());
let value = poly.evaluate(&point);
let proof = proving_key.open_single(&poly, &value, &point).unwrap();
let ok = opening_key.check(point, proof);
assert!(ok);
}
2.2 batch open different polynomials at same points
proof 个数为 O
(
1
)
O(1) O(1)，与points个数无关。
具体测试用例为：
#[test]
fn test_aggregate_witness() {
let max_degree = 27;
let (proving_key, opening_key) = setup_test(max_degree);
let point = BlsScalar::from(10);
// Committer's View
let aggregated_proof = {
// Compute secret polynomials and their evaluations
let poly_a = Polynomial::rand(25, &mut rand::thread_rng());
let poly_a_eval = poly_a.evaluate(&point);
let poly_b = Polynomial::rand(26 + 1, &mut rand::thread_rng());
let poly_b_eval = poly_b.evaluate(&point);
let poly_c = Polynomial::rand(27, &mut rand::thread_rng());
let poly_c_eval = poly_c.evaluate(&point);
proving_key
.open_multiple(
&[poly_a, poly_b, poly_c],
vec![poly_a_eval, poly_b_eval, poly_c_eval],
&point,
&mut Transcript::new(b"agg_flatten"),
)
.unwrap()
};
// Verifier's View
let ok = {
let flattened_proof = aggregated_proof.flatten(&mut Transcript::new(b"agg_flatten"));
opening_key.check(point, flattened_proof)
};
assert!(ok);
}
/// Creates an opening proof that multiple polynomials were evaluated at the same point
/// and that each evaluation produced the correct evaluation point.
/// Returns an error if any of the polynomial's degrees are too large.
pub fn open_multiple(
&self,
polynomials: &[Polynomial],
evaluations: Vec,
point: &BlsScalar,
transcript: &mut Transcript,
) -> Result {
// Commit to polynomials
let mut polynomial_commitments = Vec::with_capacity(polynomials.len());
for poly in polynomials.iter() {
polynomial_commitments.push(self.commit(poly)?)
}
// Compute the aggregate witness for polynomials
let witness_poly = self.compute_aggregate_witness(polynomials, point, transcript);
// Commit to witness polynomial
let witness_commitment = self.commit(&witness_poly)?;
let aggregate_proof = AggregateProof {
commitment_to_witness: witness_commitment,
evaluated_points: evaluations,
commitments_to_polynomials: polynomial_commitments,
};
Ok(aggregate_proof)
}
/// Computes a single witness for multiple polynomials at the same point, by taking
/// a random linear combination of the individual witnesses.
/// We apply the same optimisation mentioned in when computing each witness; removing f(z).
pub(crate) fn compute_aggregate_witness(
&self,
polynomials: &[Polynomial],
point: &BlsScalar,
transcript: &mut Transcript,
) -> Polynomial {
let challenge = transcript.challenge_scalar(b"aggregate_witness");
let powers = util::powers_of(&challenge, polynomials.len() - 1);
assert_eq!(powers.len(), polynomials.len());
let numerator: Polynomial = polynomials
.iter()
.zip(powers.iter())
.map(|(poly, challenge)| poly * challenge)
.sum();
numerator.ruffini(*point)
}
Verifier 进行flatten的主要作用为：
- 获取相同的随机值 γ \gamma γ，计算 ( 1 , γ , ⋯ , γ t − 1 ) (1,\gamma,\cdots,\gamma^{t-1}) (1,γ,⋯,γt−1)。
-
flattened_poly_commitments对应为 F
F F，flattened_poly_evaluations对应为 v
v v。
/// Flattens an `AggregateProof` into a `Proof`.
/// The transcript must have the same view as the transcript that was used to aggregate the witness in the proving stage.
pub fn flatten(&self, transcript: &mut Transcript) -> Proof {
let challenge = transcript.challenge_scalar(b"aggregate_witness");
let powers = powers_of(&challenge, self.commitments_to_polynomials.len() - 1);
// Flattened polynomial commitments using challenge
let flattened_poly_commitments: G1Projective = self
.commitments_to_polynomials
.iter()
.zip(powers.iter())
.map(|(poly, challenge)| poly.0 * challenge)
.sum();
// Flattened evaluation points
let flattened_poly_evaluations: BlsScalar = self
.evaluated_points
.iter()
.zip(powers.iter())
.map(|(eval, challenge)| eval * challenge)
.fold(BlsScalar::zero(), |acc, current_val| acc + current_val);
Proof {
commitment_to_witness: self.commitment_to_witness,
evaluated_point: flattened_poly_evaluations,
commitment_to_polynomial: Commitment::from_projective(flattened_poly_commitments),
}
}
2.3 batch open different polynomials at different points
2.3.1 当proof 个数与points个数一致时
当proof 个数与points个数一致时，即为每个point的evaluation生成一个proof，对应示例为：
#[test]
fn test_batch_verification() {
let degree = 25;
let (proving_key, vk) = setup_test(degree);
let point_a = BlsScalar::from(10);
let point_b = BlsScalar::from(11);
// Compute secret polynomial a
let poly_a = Polynomial::rand(degree, &mut rand::thread_rng());
let value_a = poly_a.evaluate(&point_a);
let proof_a = proving_key
.open_single(&poly_a, &value_a, &point_a)
.unwrap();
assert!(vk.check(point_a, proof_a));
// Compute secret polynomial b
let poly_b = Polynomial::rand(degree, &mut rand::thread_rng());
let value_b = poly_b.evaluate(&point_b);
let proof_b = proving_key
.open_single(&poly_b, &value_b, &point_b)
.unwrap();
assert!(vk.check(point_b, proof_b));
assert!(vk
.batch_check(
&[point_a, point_b],
&[proof_a, proof_b],
&mut Transcript::new(b""),
)
.is_ok());
}
相应batch算法实现为：
- V e r i f y E v a l _ b a t c h ( opening_key , π 1 , ⋯ , π n , z 1 , ⋯ , z n , v 1 . ⋯ , v n , C 1 , ⋯ , C n ) → 0 or 1 VerifyEval\_batch(\text{opening\_key},\pi_1,\cdots,\pi_n,z_1,\cdots,z_n,v_1.\cdots,v_n,\mathcal{C}_1,\cdots,\mathcal{C}_n)\rightarrow 0\text{ or } 1 VerifyEval_batch(opening_key,π1,⋯,πn,z1,⋯,zn,v1.⋯,vn,C1,⋯,Cn)→0 or 1：Verifier根据Prover提供的proofs π 1 , ⋯ , π n \pi_1,\cdots,\pi_n π1,⋯,πn和之前对polynomials f 1 , ⋯ , f n f_1,\cdots,f_n f1,⋯,fn的commitments C 1 , ⋯ , C n \mathcal{C}_1,\cdots,\mathcal{C}_n C1,⋯,Cn 来确认相应的evaluations v 1 = f 1 ( z 1 ) , ⋯ , v n = f n ( z n ) v_1=f_1(z_1),\cdots,v_n=f_n(z_n) v1=f1(z1),⋯,vn=fn(zn)是否正确。 Verifier选择随机值 γ \gamma γ，并计算 ( 1 , γ , ⋯ , γ n − 1 ) (1,\gamma,\cdots,\gamma^{n-1}) (1,γ,⋯,γn−1)。 计算： C s u m = ∑ i = 1 n γ i − 1 ( C i + π i ⋅ z i ) − ∑ i = 1 n γ i − 1 v i = ∑ i = 1 n γ i − 1 β ( f i ( β ) − f i ( z i ) ) β − z i \mathcal{C}_{sum}=\sum_{i=1}^{n}\gamma^{i-1}(\mathcal{C}_{i}+\pi_{i}\cdot z_i)-\sum_{i=1}^n\gamma^{i-1}v_i=\sum_{i=1}^n\gamma^{i-1}\frac{\beta(f_i(\beta)-f_i(z_i))}{\beta-z_i} Csum=∑i=1nγi−1(Ci+πi⋅zi)−∑i=1nγi−1vi=∑i=1nγi−1β−ziβ(fi(β)−fi(zi)) π s u m = − ∑ i = 1 n γ i − 1 π i = − ∑ i = 1 n γ i − 1 f i ( β ) − f i ( z i ) β − z i \pi_{sum}=-\sum_{i=1}^{n}\gamma^{i-1}\pi_i=-\sum_{i=1}^{n}\gamma^{i-1}\frac{f_i(\beta)-f_i(z_i)}{\beta-z_i} πsum=−∑i=1nγi−1πi=−∑i=1nγi−1β−zifi(β)−fi(zi) 即仅需验证： e ( C s u m , h ) ⋅ e ( π s u m , h β ) = 1 e(\mathcal{C}_{sum}, h)\cdot e(\pi_{sum},h^{\beta})=1 e(Csum,h)⋅e(πsum,hβ)=1 是否成立即可。
/// Checks whether a batch of polynomials evaluated at different points, returned their specified value.
pub fn batch_check(
&self,
points: &[BlsScalar],
proofs: &[Proof],
transcript: &mut Transcript,
) -> Result<(), Error> {
let mut total_c = G1Projective::identity();
let mut total_w = G1Projective::identity();
let challenge = transcript.challenge_scalar(b"batch"); // XXX: Verifier can add their own randomness at this point
let powers = util::powers_of(&challenge, proofs.len() - 1);
// Instead of multiplying g and gamma_g in each turn, we simply accumulate
// their coefficients and perform a final multiplication at the end.
let mut g_multiplier = BlsScalar::zero();
for ((proof, challenge), point) in proofs.iter().zip(powers).zip(points) {
let mut c = G1Projective::from(proof.commitment_to_polynomial.0);
let w = proof.commitment_to_witness.0;
c += w * point;
g_multiplier += challenge * proof.evaluated_point;
total_c += c * challenge;
total_w += w * challenge;
}
total_c -= self.g * g_multiplier;
let affine_total_w = G1Affine::from(-total_w);
let affine_total_c = G1Affine::from(total_c);
let pairing = dusk_bls12_381::multi_miller_loop(&[
(&affine_total_w, &self.prepared_beta_h),
(&affine_total_c, &self.prepared_h),
])
.final_exponentiation();
if pairing != dusk_bls12_381::Gt::identity() {
return Err(Error::PairingCheckFailure);
};
Ok(())
}
实际，Plonk中针对的场景为，evaluation points中实际仅有2组不同，分别表示为 z , z ′ z,z' z,z′，具体示例为：【即proof 个数与不同的points个数一致】
#[test]
fn test_batch_with_aggregation() {
let max_degree = 28;
let (proving_key, opening_key) = setup_test(max_degree);
let point_a = BlsScalar::from(10);
let point_b = BlsScalar::from(11);
// Committer's View
let (aggregated_proof, single_proof) = {
// Compute secret polynomial and their evaluations
let poly_a = Polynomial::rand(25, &mut rand::thread_rng());
let poly_a_eval = poly_a.evaluate(&point_a);
let poly_b = Polynomial::rand(26, &mut rand::thread_rng());
let poly_b_eval = poly_b.evaluate(&point_a);
let poly_c = Polynomial::rand(27, &mut rand::thread_rng());
let poly_c_eval = poly_c.evaluate(&point_a);
let poly_d = Polynomial::rand(28, &mut rand::thread_rng());
let poly_d_eval = poly_d.evaluate(&point_b);
let aggregated_proof = proving_key
.open_multiple(
&[poly_a, poly_b, poly_c],
vec![poly_a_eval, poly_b_eval, poly_c_eval],
&point_a,
&mut Transcript::new(b"agg_batch"),
)
.unwrap();
let single_proof = proving_key
.open_single(&poly_d, &poly_d_eval, &point_b)
.unwrap();
(aggregated_proof, single_proof)
};
// Verifier's View
let ok = {
let mut transcript = Transcript::new(b"agg_batch");
let flattened_proof = aggregated_proof.flatten(&mut transcript);
opening_key.batch_check(
&[point_a, point_b],
&[flattened_proof, single_proof],
&mut transcript,
)
};
assert!(ok.is_ok());
}
3. 借助(I)FFT来加速多项式乘法运算
3.1 (I)FFT加速多项式乘法运算
(I)FFT 仅适于 multiplicative subgroup of size that is a power-of-2。 具体代码见https://github.com/3for/plonk/blob/master/src/fft/目录：
/// Performs O(nlogn) multiplication of polynomials if F is smooth.
impl<'a, 'b> Mul<&'a Polynomial> for &'b Polynomial {
type Output = Polynomial;
#[inline]
fn mul(self, other: &'a Polynomial) -> Polynomial {
if self.is_zero() || other.is_zero() {
Polynomial::zero()
} else {
let domain = EvaluationDomain::new(self.coeffs.len() + other.coeffs.len())
.expect("field is not smooth enough to construct domain");
let mut self_evals = Evaluations::from_vec_and_domain(domain.fft(&self.coeffs), domain);
let other_evals = Evaluations::from_vec_and_domain(domain.fft(&other.coeffs), domain);
self_evals *= &other_evals;
self_evals.interpolate()
}
}
}
/// Defines a domain over which finite field (I)FFTs can be performed. Works
/// only for fields that have a large multiplicative subgroup of size that is
/// a power-of-2.
#[derive(Copy, Clone, Eq, PartialEq)]
pub struct EvaluationDomain {
/// The size of the domain.
pub size: u64,
/// `log_2(self.size)`.
pub log_size_of_group: u32,
/// Size of the domain as a field element.
pub size_as_field_element: BlsScalar,
/// Inverse of the size in the field.
pub size_inv: BlsScalar,
/// A generator of the subgroup.
pub group_gen: BlsScalar,
/// Inverse of the generator of the subgroup.
pub group_gen_inv: BlsScalar,
/// Multiplicative generator of the finite field.
pub generator_inv: BlsScalar,
}
3.2 coset FFT
coset FFT的主要作用是将n域的系数扩展至4n域内，从而加速 点值表示方式下 的求商运算 得 quotient polynomial： t
(
X
)
=
z
(
X
)
−
z
H
(
X
)
z
H
(
X
)
=
f
(
X
)
X
n
−
1
t(X)=\frac{z(X)-z_H(X)}{z_H(X)}=\frac{f(X)}{X^n-1} t(X)=zH(X)z(X)−zH(X)=Xn−1f(X)。缺点是增加了Prover需要维护的信息量，由n扩充至4n。
假设order为 p p p的有限域内，相应的generator为 g g g，有 g p − 1 ≡ 1 m o d p g^{p-1}\equiv 1\mod p gp−1≡1modp。 以domain_n n = 8 n=8 n=8为例，假设有 w 8 ≡ 1 m o d p w^8\equiv 1\mod p w8≡1modp。 则相应的domain_4n 中有， v 32 ≡ 1 m o d p v^{32}\equiv 1\mod p v32≡1modp。
let q_m_eval_4n =
Evaluations::from_vec_and_domain(domain_4n.coset_fft(&selectors.q_m), domain_4n);
其中domain_n的q_m多项式：
- 以系数表示为 ( c 0 , c 1 , c 2 , c 3 , c 4 , c 5 , c 6 , c 7 ) (c_0,c_1,c_2,c_3,c_4,c_5,c_6,c_7) (c0,c1,c2,c3,c4,c5,c6,c7)；
- 以点值表示为 ( ( 1 , q m 0 ) , ( w , q m 1 ) , ( w 2 , q m 2 ) , ⋯ , ( w 7 , q m 7 ) ) ((1,qm_0), (w,qm_1),(w^2,qm_2),\cdots,(w^7,qm_7)) ((1,qm0),(w,qm1),(w2,qm2),⋯,(w7,qm7))
coset_fft()函数是将系数扩充至domain_4n，多项式q_m_4n：
- 以系数表示为 ( c 0 , c 1 g , c 2 g 2 , c 3 g 3 , c 4 g 4 , c 5 g 5 , c 6 g 6 , c 7 g 7 , 0 , ⋯ , 0 ) (c_0,c_1g,c_2g^2,c_3g^3,c_4g^4,c_5g^5,c_6g^6,c_7g^7,0,\cdots,0) (c0,c1g,c2g2,c3g3,c4g4,c5g5,c6g6,c7g7,0,⋯,0)【总长度为8*4=32】
- 以点值表示为 ( ( 1 , q m 4 n 0 ) , ( v , q m 4 n 1 ) , ⋯ , ( v 31 , q m 4 n 31 ) ) ((1,qm4n_0),(v,qm4n_1),\cdots,(v^{31},qm4n_{31})) ((1,qm4n0),(v,qm4n1),⋯,(v31,qm4n31))。【代码中q_m_eval_4n即为相应的点值表示。】
// Compute 4n evaluations for X^n -1 v_h_coset_4n: domain_4n.compute_vanishing_poly_over_coset(domain.size() as u64),
compute_vanishing_poly_over_coset()中的 evaluationsv_h为： [ g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 g 8 − 1 g 8 v 8 − 1 g 8 v 16 − 1 g 8 v 24 − 1 ] \begin{bmatrix} g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1\\ g^8-1 & g^8v^8-1 & g^8v^{16}-1 & g^8v^{24}-1 \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡g8−1g8−1g8−1g8−1g8−1g8−1g8−1g8−1g8v8−1g8v8−1g8v8−1g8v8−1g8v8−1g8v8−1g8v8−1g8v8−1g8v16−1g8v16−1g8v16−1g8v16−1g8v16−1g8v16−1g8v16−1g8v16−1g8v24−1g8v24−1g8v24−1g8v24−1g8v24−1g8v24−1g8v24−1g8v24−1⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
相应的插值点为： [ 1 v v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 v 13 v 14 v 15 v 16 v 17 v 18 v 19 v 20 v 21 v 22 v 23 v 24 v 25 v 26 v 27 v 28 v 29 v 30 v 31 ] \begin{bmatrix} 1 & v & v^2 & v^3\\ v^4 & v^5 & v^6 & v^7\\ v^8 & v^9 & v^{10} & v^{11}\\ v^{12} & v^{13} & v^{14} & v^{15}\\ v^{16} & v^{17} & v^{18} & v^{19}\\ v^{20} & v^{21} & v^{22} & v^{23}\\ v^{24} & v^{25} & v^{26} & v^{27}\\ v^{28} & v^{29} & v^{30} & v^{31} \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡1v4v8v12v16v20v24v28vv5v9v13v17v21v25v29v2v6v10v14v18v22v26v30v3v7v11v15v19v23v27v31⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
4. permutation argument具体代码实现见：https://github.com/3for/plonk/blob/master/src/permutation/permutation.rs。
粒度在Variable（以此为键值），每个变量可为多个门的左侧输入、右侧输入、输出或者是Fourth值，这些信息维护在相应的Vec中。
/// Permutation provides the necessary state information and functions
/// to create the permutation polynomial. In the literature, Z(X) is the "accumulator",
/// this is what this codebase calls the permutation polynomial.
#[derive(Debug)]
pub struct Permutation {
// Maps a variable to the wires that it is associated to
pub(crate) variable_map: HashMap,
}
/// The value is a reference to the actual value that was added to the constraint system
#[derive(Debug, Eq, PartialEq, Clone, Copy, Hash)]
pub struct Variable(pub(crate) usize);
impl Into<(BlsScalar, Variable)> for Variable {
fn into(self) -> (BlsScalar, Variable) {
(BlsScalar::one(), self)
}
}
/// Stores the data for a specific wire in an arithmetic circuit
/// This data is the gate index and the type of wire
/// Left(1) signifies that this wire belongs to the first gate and is the left wire
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub enum WireData {
/// Left Wire of n'th gate
Left(usize),
/// Right Wire of n'th gate
Right(usize),
/// Output Wire of n'th gate
Output(usize),
/// Fourth Wire of n'th gate
Fourth(usize),
}
假设总共有 n n n个gate，令 ω \omega ω为 n n n-th root of unity，即在scalar 域内，满足 ω n = 1 \omega^n=1 ωn=1。 令 H = { 1 , ω , ⋯ , ω n − 1 } H=\{1,\omega,\cdots,\omega^{n-1}\} H={1,ω,⋯,ωn−1}，取 k 1 , k 2 , k 3 ∈ F k_1,k_2,k_3\in\mathbb{F} k1,k2,k3∈F，满足 H , k 1 ⋅ H , k 2 ⋅ H , k 3 ⋅ H H,k_1\cdot H,k_2\cdot H, k_3\cdot H H,k1⋅H,k2⋅H,k3⋅H 为distinct cosets of H H H in F ∗ \mathbb{F}^* F∗。
/// Constants used in the permutation argument to ensure that the wire subsets are disjoint. pub(crate) const K1: BlsScalar = BlsScalar::from_raw([7, 0, 0, 0]); pub(crate) const K2: BlsScalar = BlsScalar::from_raw([13, 0, 0, 0]); pub(crate) const K3: BlsScalar = BlsScalar::from_raw([17, 0, 0, 0]);
以 n = 4 n=4 n=4为例，具体见test_permutation_compute_sigmas_only_left_wires，采用lagrange插值，插值点为 ( 1 , ω , ⋯ , ω 3 ) (1,\omega,\cdots,\omega^3) (1,ω,⋯,ω3)，使得：
- 对于Left wire有： L 0 = L ( 1 ) = 1 , L 1 = L ( ω ) = ω , L 2 = L ( ω 2 ) = ω 2 , L 3 = L ( ω 3 ) = ω 3 L_0=L(1)=1,L_1=L(\omega)=\omega,L_2=L(\omega^2)=\omega^2,L_3=L(\omega^3)=\omega^3 L0=L(1)=1,L1=L(ω)=ω,L2=L(ω2)=ω2,L3=L(ω3)=ω3。
- 对于Right wire有： R 0 = R ( 1 ) = K 1 , R 1 = R ( ω ) = K 1 ω , R 2 = R ( ω 2 ) = K 1 ω 2 , R 3 = R ( ω 3 ) = K 1 ω 3 R_0=R(1)=K_1,R_1=R(\omega)=K_1\omega,R_2=R(\omega^2)=K_1\omega^2,R_3=R(\omega^3)=K_1\omega^3 R0=R(1)=K1,R1=R(ω)=K1ω,R2=R(ω2)=K1ω2,R3=R(ω3)=K1ω3。
- 对于Output wire有： O 0 = O ( 1 ) = K 2 , O 1 = O ( ω ) = K 2 ω , O 2 = O ( ω 2 ) = K 2 ω 2 , O 3 = O ( ω 3 ) = K 2 ω 3 O_0=O(1)=K_2,O_1=O(\omega)=K_2\omega,O_2=O(\omega^2)=K_2\omega^2,O_3=O(\omega^3)=K_2\omega^3 O0=O(1)=K2,O1=O(ω)=K2ω,O2=O(ω2)=K2ω2,O3=O(ω3)=K2ω3。
- 对于Fourth wire有： F 0 = F ( 1 ) = K 3 , F 1 = F ( ω ) = K 3 ω , F 2 = F ( ω 2 ) = K 3 ω 2 , F 3 = F ( ω 3 ) = K 3 ω 3 F_0=F(1)=K_3,F_1=F(\omega)=K_3\omega,F_2=F(\omega^2)=K_3\omega^2,F_3=F(\omega^3)=K_3\omega^3 F0=F(1)=K3,F1=F(ω)=K3ω,F2=F(ω2)=K3ω2,F3=F(ω3)=K3ω3。
permutation是根据实际各个wire与Variable之间的逻辑关系，进行了调整后再插值：
let num_wire_mappings = 4;
// ！此处即为实际各个wire与Variable之间的逻辑关系！
// Add four wire mappings
perm.add_variables_to_map(var_zero, var_zero, var_five, var_nine, 0);
perm.add_variables_to_map(var_zero, var_two, var_six, var_nine, 1);
perm.add_variables_to_map(var_zero, var_three, var_seven, var_nine, 2);
perm.add_variables_to_map(var_zero, var_four, var_eight, var_nine, 3);
/*
var_zero = {L0, R0, L1, L2, L3}
var_two = {R1}
var_three = {R2}
var_four = {R3}
var_five = {O0}
var_six = {O1}
var_seven = {O2}
var_eight = {O3}
var_nine = {F0, F1, F2, F3}
Left_sigma = {R0, L2, L3, L0}
Right_sigma = {L1, R1, R2, R3}
Out_sigma = {O0, O1, O2, O3}
Fourth_sigma = {F1, F2, F3, F0}
*/
let sigmas = perm.compute_sigma_permutations(num_wire_mappings);
let left_sigma = &sigmas[0];
let right_sigma = &sigmas[1];
let out_sigma = &sigmas[2];
let fourth_sigma = &sigmas[3];
// Check the left sigma polynomial
assert_eq!(left_sigma[0], WireData::Right(0));
assert_eq!(left_sigma[1], WireData::Left(2));
assert_eq!(left_sigma[2], WireData::Left(3));
assert_eq!(left_sigma[3], WireData::Left(0));
// Check the right sigma polynomial
assert_eq!(right_sigma[0], WireData::Left(1));
assert_eq!(right_sigma[1], WireData::Right(1));
assert_eq!(right_sigma[2], WireData::Right(2));
assert_eq!(right_sigma[3], WireData::Right(3));
// Check the output sigma polynomial
assert_eq!(out_sigma[0], WireData::Output(0));
assert_eq!(out_sigma[1], WireData::Output(1));
assert_eq!(out_sigma[2], WireData::Output(2));
assert_eq!(out_sigma[3], WireData::Output(3));
// Check the output sigma polynomial
assert_eq!(fourth_sigma[0], WireData::Fourth(1));
assert_eq!(fourth_sigma[1], WireData::Fourth(2));
assert_eq!(fourth_sigma[2], WireData::Fourth(3));
assert_eq!(fourth_sigma[3], WireData::Fourth(0));
let domain = EvaluationDomain::new(num_wire_mappings).unwrap();
let w: Fr = domain.group_gen;
let w_squared = w.pow(&[2, 0, 0, 0]);
let w_cubed = w.pow(&[3, 0, 0, 0]);
// Check the left sigmas have been encoded properly
// Left_sigma = {R0, L2, L3, L0}
// Should turn into {1 * K1, w^2, w^3, 1}
let encoded_left_sigma = perm.compute_permutation_lagrange(left_sigma, &domain);
assert_eq!(encoded_left_sigma[0], Fr::one() * &K1);
assert_eq!(encoded_left_sigma[1], w_squared);
assert_eq!(encoded_left_sigma[2], w_cubed);
assert_eq!(encoded_left_sigma[3], Fr::one());
// Check the right sigmas have been encoded properly
// Right_sigma = {L1, R1, R2, R3}
// Should turn into {w, w * K1, w^2 * K1, w^3 * K1}
let encoded_right_sigma = perm.compute_permutation_lagrange(right_sigma, &domain);
assert_eq!(encoded_right_sigma[0], w);
assert_eq!(encoded_right_sigma[1], w * &K1);
assert_eq!(encoded_right_sigma[2], w_squared * &K1);
assert_eq!(encoded_right_sigma[3], w_cubed * &K1);
// Check the output sigmas have been encoded properly
// Out_sigma = {O0, O1, O2, O3}
// Should turn into {1 * K2, w * K2, w^2 * K2, w^3 * K2}
let encoded_output_sigma = perm.compute_permutation_lagrange(out_sigma, &domain);
assert_eq!(encoded_output_sigma[0], Fr::one() * &K2);
assert_eq!(encoded_output_sigma[1], w * &K2);
assert_eq!(encoded_output_sigma[2], w_squared * &K2);
assert_eq!(encoded_output_sigma[3], w_cubed * &K2);
// Check the fourth sigmas have been encoded properly
// Out_sigma = {F1, F2, F3, F0}
// Should turn into {w * K3, w^2 * K3, w^3 * K3, 1 * K3}
let encoded_fourth_sigma = perm.compute_permutation_lagrange(fourth_sigma, &domain);
assert_eq!(encoded_fourth_sigma[0], w * &K3);
assert_eq!(encoded_fourth_sigma[1], w_squared * &K3);
assert_eq!(encoded_fourth_sigma[2], w_cubed * &K3);
assert_eq!(encoded_fourth_sigma[3], K3);
fn compute_permutation_lagrange(
&self,
sigma_mapping: &[WireData],
domain: &EvaluationDomain,
) -> Vec{
let roots: Vec= domain.elements().collect();
let lagrange_poly: Vec= sigma_mapping
.iter()
.map(|x| match x {
WireData::Left(index) => {
let root = &roots[*index];
*root
}
WireData::Right(index) => {
let root = &roots[*index];
K1 * root
}
WireData::Output(index) => {
let root = &roots[*index];
K2 * root
}
WireData::Fourth(index) => {
let root = &roots[*index];
K3 * root
}
})
.collect();
lagrange_poly
}
test_correct_permutation_poly中：【仍然以 n = 4 n=4 n=4为例， ω 4 = 1 \omega^4=1 ω4=1】
- numerator_components为： ( n 0 , n 1 , n 2 , n 3 ) (n_0,n_1,n_2,n_3) (n0,n1,n2,n3)
- denominator_components为： ( d 0 , d 1 , d 2 , d 3 ) (d_0,d_1,d_2,d_3) (d0,d1,d2,d3)
- 根据permutation，有： n 0 n 1 n 2 n 3 d 0 d 1 d 2 d 3 = 1 \frac{n_0n_1n_2n_3}{d_0d_1d_2d_3}=1 d0d1d2d3n0n1n2n3=1。
- z_vec为： ( 1 , n 0 d 0 , n 0 n 1 d 0 d 1 , n 0 n 1 n 2 d 0 d 1 d 2 ) (1,\frac{n_0}{d_0},\frac{n_0n_1}{d_0d_1},\frac{n_0n_1n_2}{d_0d_1d_2}) (1,d0n0,d0d1n0n1,d0d1d2n0n1n2)
- z_poly多项式的点值表示为： ( ( 1 , 1 ) , ( ω , n 0 d 0 ) , ( ω 2 , n 0 n 1 d 0 d 1 ) , ( ω 3 , n 0 n 1 n 2 d 0 d 1 d 2 ) ) = ( ( 1 , Z ( 1 ) ) , ( ω , Z ( ω ) ) , ( ω 2 , Z ( ω 2 ) ) , ( ω 3 , Z ( ω 3 ) ) ) ((1,1),(\omega,\frac{n_0}{d_0}),(\omega^2,\frac{n_0n_1}{d_0d_1}),(\omega^3,\frac{n_0n_1n_2}{d_0d_1d_2}))=((1,Z(1)),(\omega,Z(\omega)),(\omega^2,Z(\omega^2)),(\omega^3,Z(\omega^3))) ((1,1),(ω,d0n0),(ω2,d0d1n0n1),(ω3,d0d1d2n0n1n2))=((1,Z(1)),(ω,Z(ω)),(ω2,Z(ω2)),(ω3,Z(ω3)))。【compute_permutation_poly()函数实际计算的即为z_poly多项式。】
-
从而有 Z
(
ω
i
)
Z
(
ω
i
+
1
)
=
d
i
n
i
\frac{Z(\omega^i)}{Z(\omega^{i+1})}=\frac{d_i}{n_i} Z(ωi+1)Z(ωi)=nidi，for 1
≤
i
<
n
1\leq i
关注打赏
1688896170
查看更多评论
