zkp 為使用merlin 的Schnorr零知識證明工具包，基于ristretto group做的實例化。【ristretto為對cofactor>1曲線的抽象，ristretto對外表現(xiàn)為將non-prime-order的曲線抽象為a prime-order group。具體的細節(jié)可參見博客1ristretto對cofactor>1的橢圓曲線(如Curve25519等)的兼容（含Curve25519 cofactor的sage驗證）、博客2ristretto255 point壓縮和解壓縮算法（1）——affine坐標系下、博客3ristretto255 point壓縮和解壓縮算法（2）——extended坐標系下】

在Merlin中，一個transcript即為a public-coin argument，通過Transcript::new()函數(shù)來創(chuàng)建。Prover的消息通過append_message()（老的版本采用的是commit_bytes()）函數(shù)來添加到transcript中。Verifier的challenges則通過challenge_bytes()函數(shù)來計算。

Merlin的transcript應(yīng)由協(xié)議的API消費者創(chuàng)建，而不能由protocol內(nèi)部創(chuàng)建。

Merlin提供的接口是面向字節(jié)的byte-oriented，而實際證明協(xié)議中，需要的是特定格式的數(shù)據(jù)，如接收challenge scalars，而不是challenge bytes。這個轉(zhuǎn)化，可通過博客Merlin——零知識證明（2）應(yīng)用篇中的transcript protocol來實現(xiàn)。不同的協(xié)議，可以自定義實現(xiàn)自己的trait TranscriptProtocol。

1. 性能測試

在4核8G Ubuntu16.04系統(tǒng)上運行。

cargo +nightly bench running 8 tests test batch_verify_batchable_dleq_1 ... bench: 198,877 ns/iter (+/- 27,535) test batch_verify_batchable_dleq_16 ... bench: 1,452,702 ns/iter (+/- 208,581) test batch_verify_batchable_dleq_4 ... bench: 450,939 ns/iter (+/- 45,632) test batch_verify_batchable_dleq_64 ... bench: 5,339,812 ns/iter (+/- 273,354) test create_batchable_dleq ... bench: 221,563 ns/iter (+/- 21,566) test create_compact_dleq ... bench: 221,027 ns/iter (+/- 14,245) test verify_batchable_dleq ... bench: 183,422 ns/iter (+/- 11,620) test verify_compact_dleq ... bench: 210,587 ns/iter (+/- 12,661)

由此可知，batch_verifier.rs中的verify_batchable()函數(shù)verify proof的效率要由于verifier.rs中的實現(xiàn)。

2. 代碼解析

sig_and_vrf_example.rs中sign/verify驗證的是Schnorr簽名的流程，最關(guān)鍵的是這段代碼：（可參考博客Schnorr signature (Schnorr 簽名)數(shù)學(xué)原理、
elliptic-curve簽名驗證verify signature in EdDSA）

注意，由于使用的是Merlin transcript，變量的賦值順序會影響transcript state，所以Prover和Verifier應(yīng)嚴格按照相同的次序【將interactive變?yōu)閚on-interactive】來進行Merlin transcript的更新，否則會出現(xiàn)verify失敗的情況。

/// This proof has `m+1` 32-byte elements, where `m` is the number of /// secret variables. This means there is no space savings for a /// `CompactProof` over a `BatchableProof` when there is only one /// statement. #[derive(Clone, Serialize, Deserialize)] pub struct CompactProof {/// The Fiat-Shamir challenge.pub challenge: Scalar,/// The prover's responses, one per secret variable.pub responses: Vec<Scalar>, }/// A Schnorr proof in batchable format. /// /// This proof has `m+n` 32-byte elements, where `m` is the number of /// secret variables and `n` is the number of statements. #[derive(Clone, Serialize, Deserialize)] pub struct BatchableProof {/// Commitments to the prover's blinding factors.pub commitments: Vec<CompressedRistretto>,/// The prover's responses, one per secret variable.pub responses: Vec<Scalar>, } #[macro_export] macro_rules! define_proof {($proof_module_name:ident // Name of the module to create,$proof_label_string:expr // A string literal, used as a domain separator,( $($secret_var:ident),+ ) // Secret variables, sep by commas,( $($instance_var:ident),* ) // Public instance variables, separated by commas,( $($common_var:ident),* ) // Public common variables, separated by commas:// List of statements to prove// Format: LHS = ( ... RHS expr ... ),$($lhs:ident = $statement:tt),+) => {......}/// Named parameters for [`prove_compact`] and [`prove_batchable`].#[derive(Copy, Clone)]pub struct ProveAssignments<'a> {$(pub $secret_var: &'a Scalar,)+$(pub $instance_var: &'a RistrettoPoint,)+$(pub $common_var: &'a RistrettoPoint,)+}/// Named parameters for [`verify_compact`] and [`verify_batchable`].#[derive(Copy, Clone)]pub struct VerifyAssignments<'a> {$(pub $instance_var: &'a CompressedRistretto,)+$(pub $common_var: &'a CompressedRistretto,)+} /// Given a transcript and assignments to secret and public variables, produce a proof in batchable format.pub fn prove_batchable(transcript: &mut Transcript,assignments: ProveAssignments,) -> (BatchableProof, CompressedPoints) {let (prover, compressed) = build_prover(transcript, assignments);(prover.prove_batchable(), compressed)}fn build_prover<'a>(transcript: &'a mut Transcript,assignments: ProveAssignments,) -> (Prover<'a>, CompressedPoints) {use self::internal::*;use $crate::toolbox::prover::*;let mut prover = Prover::new(PROOF_LABEL.as_bytes(), transcript);let secret_vars = SecretVars {$($secret_var: prover.allocate_scalar(TRANSCRIPT_LABELS.$secret_var.as_bytes(),*assignments.$secret_var,),)+};struct VarPointPairs {$( pub $instance_var: (PointVar, CompressedRistretto), )+$( pub $common_var: (PointVar, CompressedRistretto), )+}let pairs = VarPointPairs {$($instance_var: prover.allocate_point(TRANSCRIPT_LABELS.$instance_var.as_bytes(),*assignments.$instance_var,),)+$($common_var: prover.allocate_point(TRANSCRIPT_LABELS.$common_var.as_bytes(),*assignments.$common_var,),)+};// XXX return compressed pointslet public_vars = PublicVars {$($instance_var: pairs.$instance_var.0,)+$($common_var: pairs.$common_var.0,)+};let compressed = CompressedPoints {$($instance_var: pairs.$instance_var.1,)+$($common_var: pairs.$common_var.1,)+};proof_statement(&mut prover, secret_vars, public_vars);(prover, compressed)}/// The transcript labels used for each secret variable.pub const TRANSCRIPT_LABELS: TranscriptLabels = TranscriptLabels {$( $secret_var: stringify!($secret_var), )+$( $instance_var: stringify!($instance_var), )+$( $common_var: stringify!($common_var), )+};/// The underlying proof statement generated by the macro invocation.////// This function exists separately from the proving/// and verification functions to allow composition of/// different proof statements with common variable/// assignments.pub fn proof_statement<CS: SchnorrCS>(cs: &mut CS,secrets: SecretVars<CS>,publics: PublicVars<CS>,) {$(cs.constrain(publics.$lhs,__compute_formula_constraint!( (publics, secrets) $statement ),);)+} pub struct Prover<'a> {transcript: &'a mut Transcript,scalars: Vec<Scalar>,points: Vec<RistrettoPoint>,point_labels: Vec<&'static [u8]>,constraints: Vec<(PointVar, Vec<(ScalarVar, PointVar)>)>, }/// A secret variable used during proving. #[derive(Copy, Clone)] pub struct ScalarVar(usize); /// A public variable used during proving. #[derive(Copy, Clone)] pub struct PointVar(usize);/// Allocate and assign a secret variable with the given `label`.pub fn allocate_scalar(&mut self, label: &'static [u8], assignment: Scalar) -> ScalarVar {self.transcript.append_scalar_var(label);self.scalars.push(assignment);ScalarVar(self.scalars.len() - 1)}/// The compact and batchable proofs differ only by which data they store.fn prove_impl(self) -> (Scalar, Vec<Scalar>, Vec<CompressedRistretto>) {// Construct a TranscriptRnglet mut rng_builder = self.transcript.build_rng();for scalar in &self.scalars {rng_builder = rng_builder.commit_witness_bytes(b"", scalar.as_bytes());}let mut transcript_rng = rng_builder.finalize(&mut thread_rng());// Generate a blinding factor for each secret variablelet blindings = self.scalars.iter().map(|_| Scalar::random(&mut transcript_rng)).collect::<Vec<Scalar>>();// Commit to each blinded LHSlet mut commitments = Vec::with_capacity(self.constraints.len());for (lhs_var, rhs_lc) in &self.constraints {let commitment = RistrettoPoint::multiscalar_mul(rhs_lc.iter().map(|(sc_var, _pt_var)| blindings[sc_var.0]),rhs_lc.iter().map(|(_sc_var, pt_var)| self.points[pt_var.0]),);let encoding = self.transcript.append_blinding_commitment(self.point_labels[lhs_var.0], &commitment);commitments.push(encoding);}// Obtain a scalar challenge and compute responseslet challenge = self.transcript.get_challenge(b"chal");let responses = Iterator::zip(self.scalars.iter(), blindings.iter()).map(|(s, b)| s * challenge + b).collect::<Vec<Scalar>>();(challenge, responses, commitments)}/// Consume this prover to produce a compact proof.pub fn prove_compact(self) -> CompactProof {let (challenge, responses, _) = self.prove_impl();CompactProof {challenge,responses,}}/// Consume this prover to produce a batchable proof.pub fn prove_batchable(self) -> BatchableProof {let (_, responses, commitments) = self.prove_impl();BatchableProof {commitments,responses,}}

參考資料：
[1] zkp
[2] merlin
[3] Schnorr signature (Schnorr 簽名)數(shù)學(xué)原理
[4] Merlin——零知識證明（2）應(yīng)用篇
[5] https://medium.com/@hdevalence/merlin-flexible-composable-transcripts-for-zero-knowledge-proofs-28d9fda22d9a

總結(jié)

以上是生活随笔為你收集整理的dalek-cryptography/zkp——基于merlin的Schnorr零知识证明的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。