L2 – 深入理解zkSync电路预处理
zkSync使用PLONK零知识证明算法生成证明。证明的生成逻辑是通过增强的bellman库实现。matter-labs开源了相关的代码,请查看plonk-release分支。zkSync虽然采用PLONK零知识证明算法,但是电路的搭建开发采用的R1CS形式。为了生成zkSync的电路证明,逻辑上需要两步:1/电路转换 2/ PLONK证明计算。电路转换就是zkSync电路预处理过程。本文重点分析zkSync电路预处理过程。
https://github.com/matter-labs/bellman.git
文章中涉及的代码的最后一个提交信息如下:
commit f551a55d83d2ea604b2dbfe096fd9dcfdaedb189 (HEAD -> master)
Merge: 06c10c0 87d8496
Author: Alexander <alex.m.vlasov@gmail.com>
Date: Tue Oct 13 17:06:24 2020 +0200
Merge pull request #30 from matter-labs/plonk_release_cpu_flags_fix
Fix CPU flags in blake2s
一切从core/prover/src/plonk_step_by_step_prover.rs的next_round函数开始。在已知电路的情况下,通过如下的三步计算生成证明:
1. let setup = SetupForStepByStepProver::prepare_setup_for_step_by_step_prover(
instance.clone(),
self.config.download_setup_from_network,
)
2. let vk = PlonkVerificationKey::read_verification_key_for_main_circuit(block_size)
3. let verified_proof = precomp
.setup
.gen_step_by_step_proof_using_prepared_setup(instance, &vk)
第一步就是预处理,第二步是获取verification密钥,第三步开始生成证明。其中instance就是FranklinCircuit对象。核心逻辑是prepare_setup_for_step_by_step_prover函数。该函数实现在core/models/src/prover_utils/mod.rs中:
pub fn prepare_setup_for_step_by_step_prover<C: Circuit<Engine> + Clone>(
circuit: C,
download_setup_file: bool,
) -> Result<Self, failure::Error> {
let hints = transpile(circuit.clone())?;
let setup_polynomials = setup(circuit, &hints)?;
let size = setup_polynomials.n.next_power_of_two().trailing_zeros();
let setup_power_of_two = std::cmp::max(size, SETUP_MIN_POW2); // for exit circuit
let key_monomial_form = Some(get_universal_setup_monomial_form(
setup_power_of_two,
download_setup_file,
)?);
Ok(SetupForStepByStepProver {
setup_power_of_two,
setup_polynomials,
hints,
key_monomial_form,
})
}
电路预处理的两个步骤:1/ Transpile 2/ Setup。Transpile是将电路从R1CS形式,转换成PLONK表示形式。从Transpile讲起。
Transpile
transpile函数实现在src/plonk/mod.rs,实现电路的转换,从R1CS转换到PLONK形式。
pub fn transpile<E: Engine, C: crate::Circuit<E>>(circuit: C) -> Result<Vec<(usize, TranspilationVariant)>, SynthesisError> {
let mut transpiler = Transpiler::<E, PlonkCsWidth4WithNextStepParams>::new();
circuit.synthesize(&mut transpiler).expect("sythesize into traspilation must succeed");
let hints = transpiler.into_hints();
Ok(hints)
}
仔细看看Transpiler的定义:
pub struct Transpiler<E: Engine, P: PlonkConstraintSystemParams<E>> {
current_constraint_index: usize,
current_plonk_input_idx: usize,
current_plonk_aux_idx: usize,
scratch: HashSet<crate::cs::Variable>,
deduplication_scratch: HashMap<crate::cs::Variable, usize>,
transpilation_scratch_space: Option<TranspilationScratchSpace<E>>,
hints: Vec<(usize, TranspilationVariant)>,
n: usize,
}
pub enum TranspilationVariant {
IntoQuadraticGate,
IntoAdditionGate(LcTransformationVariant),
MergeLinearCombinations(MergeLcVariant, LcTransformationVariant),
IntoMultiplicationGate((LcTransformationVariant, LcTransformationVariant, LcTransformationVariant))
}
特别注意Transpiler中的hints,是电路的每个门(模块)的类型。其实Transpile是电路转换的预处理,Transpile的结果就是获取hints。一个R1CS电路是如何转换成PLONK电路的核心逻辑在Transpile的enforce函数。熟悉R1CS形式的小伙伴知道,一个R1CS的约束形式是A*B=C。其中A/B/C都有可能是多个变量的线性组合。
let (a_has_constant, a_constant_term, a_lc_is_empty, a_lc) = deduplicate_and_split_linear_term::<E, Self>(a(crate::LinearCombination::zero()), &mut self.deduplication_scratch);
let (b_has_constant, b_constant_term, b_lc_is_empty, b_lc) = deduplicate_and_split_linear_term::<E, Self>(b(crate::LinearCombination::zero()), &mut self.deduplication_scratch);
let (c_has_constant, c_constant_term, c_lc_is_empty, c_lc) = deduplicate_and_split_linear_term::<E, Self>(c(crate::LinearCombination::zero()), &mut self.deduplication_scratch);
对输入的每一个R1CS约束,查看A/B/C的类型,是否是固定值,是否是多变量组合。针对A/B/C的不同组合,确定不同的转换逻辑。以C*LC=C为例:
(true, false, true) | (false, true, true) => {
…
let (_, _, hint) = enforce_lc_as_gates(
self,
lc,
multiplier,
free_constant_term,
false,
&mut space
).expect("must allocate LCs as gates for constraint like c0 * LC = c1");
…
}
以(A0) * (B0 + Blc) = C0为例,其中,A0,B0,C0都是固定值。整个约束可以变换为:
A0*B0-C0 + A0*Blc = 0
这个形式是个通用形式,也就是enforce_lc_as_gates需要解决的问题。A0*B0-C0就是free_constant_term,A0就是multiplier,Blc就是lc。
介绍具体的转换逻辑之前,介绍一下TranspilationScratchSpace。TranspilationScratchSpace存储一个门电路对应的相关信息,包括变量,系数等等。
struct TranspilationScratchSpace<E: Engine> {
scratch_space_for_vars: Vec<PlonkVariable>,
scratch_space_for_coeffs: Vec<E::Fr>,
scratch_space_for_booleans: Vec<bool>,
}
注意的是,一个约束的系数比变量的个数要多。
如果一个lc不超过4个变量的组合,一个PLONK约束就可以表示。也就是不需要乘法,只需要5个加法(其中有个固定值)。
如果超过4个变量,需要多个门进行组合。额外需要的门数计算如下:
let cycles = ((lc.0.len() – P::STATE_WIDTH) + (P::STATE_WIDTH – 2)) / (P::STATE_WIDTH – 1);
除了第一个门能支持4个变量外,其他额外的门只能处理3个变量(P::STATE_WIDTH – 1)。门与门之间通过中间变量进行“连接”:
setup函数实现在src/plonk/mod.rs。setup主要是计算sigma函数和门系数函数。事实上,这两个函数“就是”PLONK算法对应的电路表示。
pub fn setup<E: Engine, C: crate::Circuit<E>>(
circuit: C,
hints: &Vec<(usize, TranspilationVariant)>
) -> Result<SetupPolynomials<E, PlonkCsWidth4WithNextStepParams>, SynthesisError> {
use crate::plonk::better_cs::cs::Circuit;
let adapted_curcuit = AdaptorCircuit::<E, PlonkCsWidth4WithNextStepParams, _>::new(circuit, &hints);
let mut assembly = self::better_cs::generator::GeneratorAssembly::<E, PlonkCsWidth4WithNextStepParams>::new();
adapted_curcuit.synthesize(&mut assembly)?;
assembly.finalize();
let worker = Worker::new();
assembly.setup(&worker)
}
AdaptorCircuit是”R1CS“电路的Wrapper。AdaptorCircuit除了包括一个R1CS的Circuit外,还包括Transpile生成的hints信息。GeneratorAssembly实现了PLONK算法对应的门管理的逻辑。简单的说,一个R1CS的Circuit的Synthesize的过程如下图:
Adaptor实现了R1CS的ContraintSystem接口,并在enforce函数实现了R1CS电路转换。GeneratorAssembly中维护了PLONK电路对应的门的形式。GeneratorAssembly的finalize函数将电路的门的个数补齐到2的幂次。
特别注意的是,PLONK电路并不是完全和论文中一致。在bellman的实现中,一个门电路采用的是四个变量:a,b,c和d,而不是三个变量:a,b和c。
pub struct PlonkCsWidth4WithNextStepParams;
impl<E: Engine> PlonkConstraintSystemParams<E> for PlonkCsWidth4WithNextStepParams {
const STATE_WIDTH: usize = 4;
const HAS_CUSTOM_GATES: bool = false;
const CAN_ACCESS_NEXT_TRACE_STEP: bool = true;
type StateVariables = [Variable; 4];
type ThisTraceStepCoefficients = [E::Fr; 6];
type NextTraceStepCoefficients = [E::Fr; 1];
type CustomGateType = NoCustomGate;
}
PlonkCsWidth4WithNextStepParams结构体中的STATE_WIDTH就是一个门对应的变量个数。
GeneratorAssembly的setup函数从门的表示,获取sigma函数和门对应的系数多项式。
pub fn setup(self, worker: &Worker) -> Result<SetupPolynomials<E, PlonkCsWidth4WithNextStepParams>, SynthesisError> {
assert!(self.is_finalized);
let n = self.n;
let num_inputs = self.num_inputs;
let [sigma_1, sigma_2, sigma_3, sigma_4] = self.make_permutations(&worker);
let ([q_a, q_b, q_c, q_d, q_m, q_const],
[q_d_next]) = self.make_selector_polynomials(&worker)?;
drop(self);
let sigma_1 = sigma_1.ifft(&worker);
let sigma_2 = sigma_2.ifft(&worker);
let sigma_3 = sigma_3.ifft(&worker);
let sigma_4 = sigma_4.ifft(&worker);
let q_a = q_a.ifft(&worker);
let q_b = q_b.ifft(&worker);
let q_c = q_c.ifft(&worker);
let q_d = q_d.ifft(&worker);
let q_m = q_m.ifft(&worker);
let q_const = q_const.ifft(&worker);
let q_d_next = q_d_next.ifft(&worker);
let setup = SetupPolynomials::<E, PlonkCsWidth4WithNextStepParams> {
n,
num_inputs,
selector_polynomials: vec![q_a, q_b, q_c, q_d, q_m, q_const],
next_step_selector_polynomials: vec![q_d_next],
permutation_polynomials: vec![sigma_1, sigma_2, sigma_3, sigma_4],
_marker: std::marker::PhantomData
};
Ok(setup)
}
逻辑比较清晰明了,计算permutation和selector多项式的点值表示,并换算到系数表示。make_selector_polynomials函数实现selector多项式的点值计算,相对简单。详细说说permutation的计算过程。
partitions数组的长度为所有变量的个数,记录的每个变量在每个门对应的位置。举个例子:
partitions[3] = ((0, 1),(3, 2))
第三个变量用在第一个门的第一个变量(0,1)和第三个门的第二个变量(3,2)。partitions帮助找出了使用同一个变量的所有的门的信息。通过partitions的信息可以构造sigma函数。
每个门由4个变量组成,每个门的每个变量的位置有独立连续的编号,如下图所示:
for (i, partition) in partitions.into_iter().enumerate().skip(1) { //枚举所有的变量
// copy-permutation should have a cycle around the partition
…
let permutation = rotate(partition.clone());
permutations[i] = permutation.clone();
for (original, new) in partition.into_iter() //构造同一变量对应的门的位置对
.zip(permutation.into_iter())
{
let new_zero_enumerated = new.1 – 1;
let mut new_value = domain_elements[new_zero_enumerated]; //新对应的门的变量的编号
new_value.mul_assign(&non_residues[new.0]); //乘以偏移,得到统一编号
// check to what witness polynomial the variable belongs
let place_into = match original.0 { //获取同一个变量对应的原有位置信息
0 => {
sigma_1.as_mut()
},
1 => {
sigma_2.as_mut()
},
2 => {
sigma_3.as_mut()
},
3 => {
sigma_4.as_mut()
},
_ => {
unreachable!()
}
};
let original_zero_enumerated = original.1 – 1;
place_into[original_zero_enumerated] = new_value; //进行置换
}
}
sigma_1/sigma_2/sigma_3/sigma_4就是需要求取的“置换”函数。整个逻辑如下图所示:
总结:
zkSync虽然采用PLONK零知识证明算法,但是电路的搭建开发采用的R1CS形式。zkSync电路处理包括:1/电路转换 2/PLONK证明计算。Transpile实现了电路的格式转换。电路转换的目的是获取:1/sigma函数 2/ 门系数多项式。
比推快讯
更多 >>- OKX Ventures宣布投资Wild Forest
- Ola:面向早期Massive用户的首次代币分配快照拟于5月11日进行
- Liquidium宣布完成新一轮融资并已购入1 DeGod、1y00t和1 BTC DeGod
- 美SEC主席:收到的有关加密货币的问题“比例过大”
- 灰度撤回其以太坊期货ETF申请
- 美众议院民主党拟于本周提出针对加密货币混合服务的法案
- 摩根士丹利将美联储首次降息时间的预期从7月推迟到9月
- 彭博分析师:灰度现货比特币ETF净流入可能是短期交易的结果
- 前 NFL 巨星Rob Gronkowski同意支付 190 万美元以和解 Voyager Digital 投资者诉讼
- BTC短线跌破63000美元
- Advanced Blockchain AG在瑞士成立加密风投机构ABX Ventures
- Aragon 联合创始人推出自托管钱包 Tuyo
- 美联储Neel Kashkar:今年仍有可能降息
- Solana生态DePin项目Ambient完成200万美元融资,Borderless Capital 领投
- 美国国务院拟悬赏1000万美元以获取LockBit勒索软件组织头目信息
- 分析师:Robinhood第一季度营收有望创近三年新高,加密交易收入同比增幅或达一倍以上
- MoonPay 与 BitPay 合作简化加密货币交易
- Lava Foundation 完成1100万美元融资,未来几个月将推出Lava主网和空投
- Zora网络收购NFT铸造聚合器mint.fun
- 美联储Neel Kashkar:最有可能在较长时间内维持利率不变
- 扩容解决方案提供商ZKM完成500万美元Pre-A融资,OKX Ventures 领投
- 前红杉中国合伙人曹曦旗下投资公司Monolith Management拥有超过2400万美元的贝莱德现货比特币ETF
- 美国9只现货比特币ETF 昨日增持4412枚BTC,价值约2.8亿美元
- 渣打银行:美国财政主导地位和特朗普上台或将使比特币受益
- ETH 反弹突破 3100 美元,24小时涨幅1.13%
- BTC回升至64000美元
- 过去2个月某巨鲸/机构从Flow Traders收到2,261枚BTC,价值约1.49亿美元
- 贝莱德和富达比特币ETF共拥有超42万枚BTC,价值约 270 亿美元
- CBOE向SEC提交富兰克林比特币ETF规则修改申请
- 建仓成本仅为2030美元的巨鲸拟赎回8453枚stETH,价值3017万美元
- 数据:迄今为止DeFi 漏洞已造成近 590 亿美元的损失
- SEC主席: 在发出多个Wells通知后,投资者缺乏必要的加密信息披露
- Tabi Chain将推出第1季空投活动,将分配8亿枚TABI代币
- Ethernity推出以太坊二层网络Ethernity Chain,生态由ERN提供支持
- MetaPhone完成100万美元融资
- 美联储卡什卡利:我对中性利率的估计值从2%适度上调至2.5%
- Botanix Labs获总计1150万美元融资
- QCP Capital:比特币期权交易员押注9月看涨价格将突破10万美元
- 目前丢失状态的BTC估值约为1210亿美元
- Steve Eisman:加密货币与纳斯达克指数有75%相关性
- Gary Gensler:许多加密货币根据法律都是证券
- Scroll生态项目PenPad完成新一轮融资
- 香港首批现货虚拟资产ETF资产管理规模已超24亿港元
- 美国超20%摇摆州选民将加密货币视为关键议题