1. 引言
Mina系列博客有：
- Mina概览
- Mina的支付流程
- Mina的zkApp
- Mina中的Pasta（Pallas和Vesta）曲线
- Mina中的Schnorr signature
视频可参看：
- 2020年5月 The Pickles Inductive SNARK Composition System
Pickles是一个新的证明系统和相关的工具包，它是第一个能部署的无需可信设置可递归合成的SNARK。
在Coda testnet(3.3)中，Mina团队发布了Pickles。
Pickles包含了2个要素：
- core zkSNARK
- 开发者工具包：包含大量库功能和Pickles归纳证明系统
Pickles的zkSNARK在许多方面显著改进了 Coda以前基于Groth16的递归SNARK：
- 1）通过从大的753位field 切换到小的255位field，提高了整个Coda的效率：
- VRF evaluation速度提升了16x
- Hash运算速度提升了8x
- 账本存储需求降低了3x
- 2）移除了可信设置。Pickles为：基于Halo的inner product argument + batch处理技术 + 定制的约束 + 大量优化。
- 3）支持定制的约束，以实现高效递归，特别是允许高效：
- Poseidon hash运算
- 椭圆曲线scaling计算、加法计算和doubling计算。
Pickles开发者工具包中的Pickles归纳证明系统 对现有递归解决方案进行了大幅改进，将底层密码学中的各种乱七八糟的细节进行了抽象，使得所涉及的递归证明系统适于应用开发者。
4. Pickles性能比对Pickles是唯一一个支持任意分支递归（这对扩展性至关重要）的无需可信设置的zk-SNARK。此外，其Prover证明速度很快，与基于AIR的STARKs不同，Pickles可以一个小的proof size来支持通用电路。下表概述了Pickles如何与其他系统对比： 
对于大多数可验证应用来说，仅是隔离运行是不够的，除了以上3点（即 部署路线、开发者工具 和 可扩展性），还要求：
- 4）能够在经过充分验证的生态系统中与其他应用程序进行组合式交互。
Pickles为Mina支持zkApps的基础技术。
6. 实际Pickles实现Mina中的详细Pickles代码实现见：
- https://github.com/MinaProtocol/mina/tree/develop/src/lib/pickles
Pickles是Mina的归纳zk-SNARK合成系统。支持使用zk-SNARK构造证明，并以灵活的方式将它们结合起来，以提供增量可验证计算。
为了高效实现增量可验证计算，Pickles采用了 一对名为Pasta的友好曲线。在实际Mina源代码中，分别将这组曲线称为“tick”和“tock”：
- Tick：对应为Vesta曲线（在Pickles内部又将其称为Step），constraint domain size为 2 18 2^{18} 218，用于区块证明和交易证明。
- Tock：对应为Pallas曲线（在Pickles内部又将其称为Wrap），constraint domain size为 2 17 2^{17} 217，用于签名。
由于Tock Prover的工作量更少（仅运行递归验证，不运行任何其它逻辑），因此需要的constraints更少，相应具有更小的constraint domain size。
Tock用于证明 Tick证明的验证，输出为 Tick证明； Tick用于证明 Tock证明的验证，输出为 Tock证明。 具体为：
- Prove t o c k ( Verify ( T i c k ) ) = T i c k p r o o f \text{Prove}_{tock}(\text{Verify}(Tick))=Tick_{proof} Provetock(Verify(Tick))=Tickproof
- Prove t i c k ( Verify ( T o c k ) ) = T o c k p r o o f \text{Prove}_{tick}(\text{Verify}(Tock))=Tock_{proof} Provetick(Verify(Tock))=Tockproof
Mina中，Tick和Tock最多可验证2个对方类型的证明，尽管，理论上来说可同时验证的数量可以更多。
当前，Mina中的情况为：
- 每个Tock中总是包裹了1个Tick证明。
- 1个Tick证明可验证2个Tock证明：
- Blockchain SNARK的输入为 前一blockchain SNARK proof + transaction proof。
- 验证2笔Tock transaction proof。
Mina中的Pickles模块主要包含：
- 1）backend模块：主要定义了Tick和Tock模块。
- 2）limb_vector模块：主要是将大的Field和Scalar值以u64数组表示。
- 3）one_hot_vector模块：
- 4）pseudo模块：
- 5）precomputed模块：根据gen_values/gen_values.ml，为vesta和pallas曲线生成的Lagrange pre-computations。详细值见：src/lib/crypto/kimchi_backend/pasta/precomputed.ml。
- 6）plonk_checks模块：定义了vanishing_polynomial_domain、plonk_domain、domain等类型，以及map_reduce、pow2pow、vanishing_polynomial、domain、all_but、actual_evaluation、evals_of_split_evals、scalars_env、perm_alpha0（2+15=17）、ft_eval0、derive_plonk、checked等函数。
- 7）composition_types模块：包含digest、index、spec、bulletproof_challenge、composition_types等子模块
- 8）step_branch_data模块：step_branch_data为The data obtained from “compiling” an inductive rule into a circuit，结构定义为：【其中的create函数为compile an inductive rule。】
(* The data obtained from "compiling" an inductive rule into a circuit. *)
type ( 'a_var
, 'a_value
, 'max_branching
, 'branches
, 'prev_vars
, 'prev_values
, 'local_widths
, 'local_heights )
t =
| T :
{ branching : 'branching Nat.t * ('prev_vars, 'branching) Hlist.Length.t
; index : Types.Index.t
; lte : ('branching, 'max_branching) Nat.Lte.t
; domains : Domains.t
; rule :
( 'prev_vars
, 'prev_values
, 'local_widths
, 'local_heights
, 'a_avar
, 'a_value )
Inductive_rule.t
; main :
step_domains:(Domains.t, 'branches) Vector.t
-> ( (Unfinalized.t, 'max_branching) Vector.t
, Impls.Step.Field.t
, (Impls.Step.Field.t, 'max_branching) Vector.t )
Types.Pairing_based.Statement.t
-> unit
; requests :
(module Requests.Step.S
with type statement = 'a_value
and type max_branching = 'max_branching
and type prev_values = 'prev_values
and type local_signature = 'local_widths
and type local_branches = 'local_heights)
}
-> ( 'a_var
, 'a_value
, 'max_branching
, 'branches
, 'prev_vars
, 'prev_values
, 'local_widths
, 'local_heights )
t
- 9）step_main模块：
step_main函数为对应the input inductive rule的SNARK函数。 - 10）wrap_main模块：
wrap_main函数为用于包裹来源于the given set of keys的任意proof的SNARK函数。 - 11）dlog_main模块：
Mina Pickles的backend模块中主要定义了Tick模块和Tock模块：
module Tick = struct
include Kimchi_backend.Pasta.Vesta_based_plonk
module Inner_curve = Kimchi_backend.Pasta.Pasta.Pallas
end
module Tock = struct
include Kimchi_backend.Pasta.Pallas_based_plonk
module Inner_curve = Kimchi_backend.Pasta.Pasta.Vesta
end
plonk_checks模块中包含：
- 1）scalars模块：由gen_scalars/gen_scalars.ml生成。
- 2）plonk_checks模块：定义了vanishing_polynomial_domain、plonk_domain、domain等类型，以及map_reduce、pow2pow、vanishing_polynomial、domain、all_but、actual_evaluation、evals_of_split_evals、scalars_env、perm_alpha0（2+15=17）、ft_eval0、derive_plonk、checked等函数。
scalars模块中：
- 1）gate类型有：
module Gate_type = struct
module T = struct
type t = Poseidon | VarBaseMul | EndoMul | CompleteAdd | EndoMulScalar
- 2）Column类型有：
module Column = struct
open Core_kernel
module T = struct
type t = Witness of int | Index of Gate_type.t | Coefficient of int
- 3）Env类型有：
module Env = struct
type 'a t =
{ add : 'a -> 'a -> 'a
; sub : 'a -> 'a -> 'a
; mul : 'a -> 'a -> 'a
; pow : 'a * int -> 'a
; square : 'a -> 'a
; zk_polynomial : 'a
; omega_to_minus_3 : 'a
; zeta_to_n_minus_1 : 'a
; var : Column.t * curr_or_next -> 'a
; field : string -> 'a
; cell : 'a -> 'a
; alpha_pow : int -> 'a
; double : 'a -> 'a
; endo_coefficient : 'a
; mds : int * int -> 'a
; srs_length_log2 : int
}
end
- 4）Ticke和Tock模块中包含了constant_term和index_terms约束实现：
module type S = sig
val constant_term : 'a Env.t -> 'a
val index_terms : 'a Env.t -> 'a Lazy.t Column.Table.t
end
(* The constraints are basically the same, but the literals in them differ. *)
type 'field vanishing_polynomial_domain =
< vanishing_polynomial : 'field -> 'field >
type 'field plonk_domain =
< vanishing_polynomial : 'field -> 'field
; shifts : 'field Dlog_plonk_types.Shifts.t
; generator : 'field
; size : 'field >
type 'field domain = < size : 'field ; vanishing_polynomial : 'field -> 'field >
composition_types模块包含：
- 1）digest模块：主要包含field的bit与limb_vector表示之间的相互转换。
- 2）index模块：主要包含field的char与bit表示之间的相互转换。
- 3）spec模块：主要定义了Basic结构类型——分为Index、Field、Bool、Digest、Challenge、Bulletproof_challenge等子类型。以及rec T、rec typ、rec pack、rec etyp等递归变量，以及pack_basic、pack、typ_basic、typ、packed_typ_basic、packed_typ等函数。
- 4）bulletproof_challenge模块：主要定义了bulletproof_challenge结构 及 相应的pack、unpack和typ函数。
module Stable = struct
module V1 = struct
type 'challenge t = { prechallenge : 'challenge }
module Stable = struct
module V2 = struct
type 'f t = 'f Kimchi.Protocol.scalar_challenge = { inner : 'f }
- 5）composition_types模块：定义了index_to_field_elements变量。包含了Dlog_based、Nvector、Wrap_bp_vec、Step_bp_vec和Challenges_vector模块。 其中：
- 5.1）Challenges_vector模块中定义了变量和值的vector表示：
module Challenges_vector = struct type 'n t = (Backend.Tock.Field.t Snarky_backendless.Cvar.t Wrap_bp_vec.t, 'n) Vector.t module Constant = struct type 'n t = (Backend.Tock.Field.t Wrap_bp_vec.t, 'n) Vector.t end end
Dlog_based模块中包含：
- 1）Proof_state模块
- 2）Pass_through模块：Pass_through结构定义为：
type ('g, 's, 'sg, 'bulletproof_challenges) t =
{ app_state : 's
; dlog_plonk_index : 'g Plonk_verification_key_evals.t
; sg : 'sg
; old_bulletproof_challenges : 'bulletproof_challenges
}
(* Plonk_verification_key_evals.t结构为： *)
type 'comm t =
{ sigma_comm : 'comm Dlog_plonk_types.Permuts_vec.Stable.V1.t
; coefficients_comm : 'comm Dlog_plonk_types.Columns_vec.Stable.V1.t
; generic_comm : 'comm
; psm_comm : 'comm
; complete_add_comm : 'comm
; mul_comm : 'comm
; emul_comm : 'comm
; endomul_scalar_comm : 'comm
}
- 3）Statement模块：Statement结构定义为：
type ( 'plonk
, 'scalar_challenge
, 'fp
, 'fq
, 'me_only
, 'digest
, 'pass_through
, 'bp_chals
, 'index )
t =
{ proof_state :
( 'plonk
, 'scalar_challenge
, 'fp
, 'fq
, 'me_only
, 'digest
, 'bp_chals
, 'index )
Proof_state.Stable.V1.t
; pass_through : 'pass_through
}
Proof_state结构定义为：
module Stable = struct
module V1 = struct
type ( 'plonk
, 'scalar_challenge
, 'fp
, 'fq
, 'me_only
, 'digest
, 'bp_chals
, 'index )
t =
{ deferred_values :
( 'plonk
, 'scalar_challenge
, 'fp
, 'fq
, 'bp_chals
, 'index )
Deferred_values.Stable.V1.t
; sponge_digest_before_evaluations : 'digest
(* Not needed by other proof system *)
; me_only : 'me_only
}
Proof_state模块中包含了：
- 1.1）Deferred_values模块：
(* Defered_values结构定义为： *) module Stable = struct [@@@no_toplevel_latest_type] module V1 = struct type ( 'plonk , 'scalar_challenge , 'fp , 'fq , 'bulletproof_challenges , 'index ) t = { plonk : 'plonk ; combined_inner_product : 'fp ; b : 'fp ; xi : 'scalar_challenge ; bulletproof_challenges : 'bulletproof_challenges ; which_branch : 'index } (*Defered_values.Plonk.Minimal结构定义为：*) module V1 = struct type ('challenge, 'scalar_challenge) t = { alpha : 'scalar_challenge ; beta : 'challenge ; gamma : 'challenge ; zeta : 'scalar_challenge } (* Defered_values.Plonk.In_circuit定义为： *) type ('challenge, 'scalar_challenge, 'fp) t = { alpha : 'scalar_challenge ; beta : 'challenge ; gamma : 'challenge ; zeta : 'scalar_challenge (* TODO: zeta_to_srs_length is kind of unnecessary. Try to get rid of it when you can. *) ; zeta_to_srs_length : 'fp ; zeta_to_domain_size : 'fp ; poseidon_selector : 'fp ; vbmul : 'fp ; complete_add : 'fp ; endomul : 'fp ; endomul_scalar : 'fp ; perm : 'fp ; generic : 'fp Generic_coeffs_vec.t } - 1.2）Me_only模块：
(* Me_only结构定义为： *) type ('g1, 'bulletproof_challenges) t = { sg : 'g1; old_bulletproof_challenges : 'bulletproof_challenges } - 1.3）Minimal模块
- 1.4）In_circuit模块：定义了变量spec：
let spec =
let open Spec in
Struct
[ Vector (B Field, Nat.N15.n)
; Vector (B Challenge, Nat.N2.n)
; Vector (Scalar Challenge, Nat.N3.n)
; Vector (B Digest, Nat.N3.n)
; Vector (B Bulletproof_challenge, Backend.Tick.Rounds.n)
; Vector (B Index, Nat.N1.n)
]
[1] Mina protocol手册之Pickles [2] Mina官方2020年8月博客 Meet Pickles SNARK: Enabling Smart Contracts on Coda Protocol
