ergotree_interpreter/sigma_protocol/
verifier.rs

1//! Verifier
2
3use super::dht_protocol;
4use super::dht_protocol::FirstDhTupleProverMessage;
5use super::fiat_shamir::FiatShamirTreeSerializationError;
6use super::prover::ProofBytes;
7use super::sig_serializer::SigParsingError;
8use super::unchecked_tree::UncheckedDhTuple;
9use super::{
10    dlog_protocol,
11    fiat_shamir::{fiat_shamir_hash_fn, fiat_shamir_tree_to_bytes},
12    sig_serializer::parse_sig_compute_challenges,
13    unchecked_tree::{UncheckedLeaf, UncheckedSchnorr},
14    SigmaBoolean, UncheckedTree,
15};
16use crate::eval::context::Context;
17use crate::eval::EvalError;
18use crate::eval::{reduce_to_crypto, ReductionDiagnosticInfo};
19use dlog_protocol::FirstDlogProverMessage;
20use ergotree_ir::ergo_tree::ErgoTree;
21use ergotree_ir::ergo_tree::ErgoTreeError;
22
23use derive_more::From;
24use thiserror::Error;
25
26/// Errors on proof verification
27#[derive(Error, Debug, From)]
28pub enum VerifierError {
29    /// Failed to parse ErgoTree from bytes
30    #[error("ErgoTreeError: {0}")]
31    ErgoTreeError(ErgoTreeError),
32    /// Failed to evaluate ErgoTree
33    #[error("EvalError: {0}")]
34    EvalError(EvalError),
35    /// Signature parsing error
36    #[error("SigParsingError: {0}")]
37    SigParsingError(SigParsingError),
38    /// Error while tree serialization for Fiat-Shamir hash
39    #[error("Fiat-Shamir tree serialization error: {0}")]
40    FiatShamirTreeSerializationError(FiatShamirTreeSerializationError),
41}
42
43/// Result of Box.ergoTree verification procedure (see `verify` method).
44#[derive(Debug, Clone)]
45pub struct VerificationResult {
46    /// result of SigmaProp condition verification via sigma protocol
47    pub result: bool,
48    /// estimated cost of contract execution
49    pub cost: u64,
50    /// Diagnostic information about the reduction (pretty printed expr and/or env)
51    pub diag: ReductionDiagnosticInfo,
52}
53
54/// Verifier for the proofs generater by [`super::prover::Prover`]
55pub trait Verifier {
56    /// Executes the script in a given context.
57    /// Step 1: Deserialize context variables
58    /// Step 2: Evaluate expression and produce SigmaProp value, which is zero-knowledge statement (see also `SigmaBoolean`).
59    /// Step 3: Verify that the proof is presented to satisfy SigmaProp conditions.
60    fn verify<'ctx>(
61        &self,
62        tree: &ErgoTree,
63        ctx: &Context<'ctx>,
64        proof: ProofBytes,
65        message: &[u8],
66    ) -> Result<VerificationResult, VerifierError> {
67        let expr = tree.proposition()?;
68        let reduction_result = reduce_to_crypto(&expr, ctx)?;
69        let res: bool = match reduction_result.sigma_prop {
70            SigmaBoolean::TrivialProp(b) => b,
71            sb => {
72                match proof {
73                    ProofBytes::Empty => false,
74                    ProofBytes::Some(proof_bytes) => {
75                        // Perform Verifier Steps 1-3
76                        let unchecked_tree = parse_sig_compute_challenges(&sb, proof_bytes)?;
77                        // Perform Verifier Steps 4-6
78                        check_commitments(unchecked_tree, message)?
79                    }
80                }
81            }
82        };
83        Ok(VerificationResult {
84            result: res,
85            cost: 0,
86            diag: reduction_result.diag,
87        })
88    }
89}
90
91/// Verify that the signature is presented to satisfy SigmaProp conditions.
92pub fn verify_signature(
93    sigma_tree: SigmaBoolean,
94    message: &[u8],
95    signature: &[u8],
96) -> Result<bool, VerifierError> {
97    let res: bool = match sigma_tree {
98        SigmaBoolean::TrivialProp(b) => b,
99        sb => {
100            match signature {
101                [] => false,
102                _ => {
103                    // Perform Verifier Steps 1-3
104                    let unchecked_tree = parse_sig_compute_challenges(&sb, signature.to_vec())?;
105                    // Perform Verifier Steps 4-6
106                    check_commitments(unchecked_tree, message)?
107                }
108            }
109        }
110    };
111    Ok(res)
112}
113
114/// Perform Verifier Steps 4-6
115fn check_commitments(sp: UncheckedTree, message: &[u8]) -> Result<bool, VerifierError> {
116    // Perform Verifier Step 4
117    let new_root = compute_commitments(sp);
118    let mut s = fiat_shamir_tree_to_bytes(&new_root.clone().into())?;
119    s.append(&mut message.to_vec());
120    // Verifier Steps 5-6: Convert the tree to a string `s` for input to the Fiat-Shamir hash function,
121    // using the same conversion as the prover in 7
122    // Accept the proof if the challenge at the root of the tree is equal to the Fiat-Shamir hash of `s`
123    // (and, if applicable,  the associated data). Reject otherwise.
124    let expected_challenge = fiat_shamir_hash_fn(s.as_slice());
125    Ok(new_root.challenge() == expected_challenge.into())
126}
127
128/// Verifier Step 4: For every leaf node, compute the commitment a from the challenge e and response $z$,
129/// per the verifier algorithm of the leaf's Sigma-protocol.
130/// If the verifier algorithm of the Sigma-protocol for any of the leaves rejects, then reject the entire proof.
131pub fn compute_commitments(sp: UncheckedTree) -> UncheckedTree {
132    match sp {
133        UncheckedTree::UncheckedLeaf(leaf) => match leaf {
134            UncheckedLeaf::UncheckedSchnorr(sn) => {
135                let a = dlog_protocol::interactive_prover::compute_commitment(
136                    &sn.proposition,
137                    &sn.challenge,
138                    &sn.second_message,
139                );
140                UncheckedSchnorr {
141                    commitment_opt: Some(FirstDlogProverMessage { a: a.into() }),
142                    ..sn
143                }
144                .into()
145            }
146            UncheckedLeaf::UncheckedDhTuple(dh) => {
147                let (a, b) = dht_protocol::interactive_prover::compute_commitment(
148                    &dh.proposition,
149                    &dh.challenge,
150                    &dh.second_message,
151                );
152                UncheckedDhTuple {
153                    commitment_opt: Some(FirstDhTupleProverMessage::new(a, b)),
154                    ..dh
155                }
156                .into()
157            }
158        },
159        UncheckedTree::UncheckedConjecture(conj) => conj
160            .clone()
161            .with_children(conj.children_ust().mapped(compute_commitments))
162            .into(),
163    }
164}
165
166/// Test Verifier implementation
167pub struct TestVerifier;
168
169impl Verifier for TestVerifier {}
170
171#[allow(clippy::unwrap_used)]
172#[allow(clippy::panic)]
173#[cfg(test)]
174#[cfg(feature = "arbitrary")]
175mod tests {
176    use std::convert::TryFrom;
177
178    use crate::sigma_protocol::private_input::{DhTupleProverInput, DlogProverInput, PrivateInput};
179    use crate::sigma_protocol::prover::hint::HintsBag;
180    use crate::sigma_protocol::prover::{Prover, TestProver};
181
182    use super::*;
183    use ergotree_ir::mir::atleast::Atleast;
184    use ergotree_ir::mir::constant::{Constant, Literal};
185    use ergotree_ir::mir::expr::Expr;
186    use ergotree_ir::mir::sigma_and::SigmaAnd;
187    use ergotree_ir::mir::sigma_or::SigmaOr;
188    use ergotree_ir::mir::value::CollKind;
189    use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProp;
190    use ergotree_ir::types::stype::SType;
191    use proptest::collection::vec;
192    use proptest::prelude::*;
193    use sigma_test_util::force_any_val;
194
195    fn proof_append_some_byte(proof: &ProofBytes) -> ProofBytes {
196        match proof {
197            ProofBytes::Empty => panic!(),
198            ProofBytes::Some(bytes) => {
199                let mut new_bytes = bytes.clone();
200                new_bytes.push(1u8);
201                ProofBytes::Some(new_bytes)
202            }
203        }
204    }
205    proptest! {
206
207        #![proptest_config(ProptestConfig::with_cases(16))]
208
209        #[test]
210        fn test_prover_verifier_p2pk(secret in any::<DlogProverInput>(), message in vec(any::<u8>(), 100..200)) {
211            let pk = secret.public_image();
212            let tree = ErgoTree::try_from(Expr::Const(pk.into())).unwrap();
213
214            let prover = TestProver {
215                secrets: vec![PrivateInput::DlogProverInput(secret)],
216            };
217            let res = prover.prove(&tree,
218                &force_any_val::<Context>(),
219                message.as_slice(),
220                &HintsBag::empty());
221            let proof = res.unwrap().proof;
222            let verifier = TestVerifier;
223            prop_assert_eq!(verifier.verify(&tree,
224                                            &force_any_val::<Context>(),
225                                            proof.clone(),
226                                            message.as_slice())
227                            .unwrap().result,
228                            true);
229
230            // possible to append bytes
231            prop_assert_eq!(verifier.verify(&tree,
232                                            &force_any_val::<Context>(),
233                                            proof_append_some_byte(&proof),
234                                            message.as_slice())
235                            .unwrap().result,
236                            true);
237
238            // wrong message
239            prop_assert_eq!(verifier.verify(&tree,
240                                            &force_any_val::<Context>(),
241                                            proof,
242                                            vec![1u8; 100].as_slice())
243                            .unwrap().result,
244                            false);
245        }
246
247        #[test]
248        fn test_prover_verifier_dht(secret in any::<DhTupleProverInput>(), message in vec(any::<u8>(), 100..200)) {
249            let pk = secret.public_image().clone();
250            let tree = ErgoTree::try_from(Expr::Const(pk.into())).unwrap();
251
252            let prover = TestProver {
253                secrets: vec![PrivateInput::DhTupleProverInput(secret)],
254            };
255            let res = prover.prove(&tree,
256                &force_any_val::<Context>(),
257                message.as_slice(),
258                &HintsBag::empty());
259            let proof = res.unwrap().proof;
260            let verifier = TestVerifier;
261            prop_assert_eq!(verifier.verify(&tree,
262                                            &force_any_val::<Context>(),
263                                            proof.clone(),
264                                            message.as_slice())
265                            .unwrap().result,
266                            true);
267
268            // possible to append bytes
269            prop_assert_eq!(verifier.verify(&tree,
270                                            &force_any_val::<Context>(),
271                                            proof_append_some_byte(&proof),
272                                            message.as_slice())
273                            .unwrap().result,
274                            true);
275
276            // wrong message
277            prop_assert_eq!(verifier.verify(&tree,
278                                            &force_any_val::<Context>(),
279                                            proof,
280                                            vec![1u8; 100].as_slice())
281                            .unwrap().result,
282                            false);
283        }
284
285        #[test]
286        fn test_prover_verifier_conj_and(secret1 in any::<PrivateInput>(),
287                                         secret2 in any::<PrivateInput>(),
288                                         message in vec(any::<u8>(), 100..200)) {
289            let pk1 = secret1.public_image();
290            let pk2 = secret2.public_image();
291            let expr: Expr = SigmaAnd::new(vec![Expr::Const(pk1.into()), Expr::Const(pk2.into())])
292                .unwrap()
293                .into();
294            let tree = ErgoTree::try_from(expr).unwrap();
295            let prover = TestProver {
296                secrets: vec![secret1, secret2],
297            };
298            let res = prover.prove(&tree,
299                &force_any_val::<Context>(),
300                message.as_slice(),
301                &HintsBag::empty());
302            let proof = res.unwrap().proof;
303            let verifier = TestVerifier;
304            let ver_res = verifier.verify(&tree,
305                                          &force_any_val::<Context>(),
306                                          proof,
307                                          message.as_slice());
308            prop_assert_eq!(ver_res.unwrap().result, true);
309        }
310
311        #[test]
312        fn test_prover_verifier_conj_and_and(secret1 in any::<PrivateInput>(),
313                                             secret2 in any::<PrivateInput>(),
314                                             secret3 in any::<PrivateInput>(),
315                                             message in vec(any::<u8>(), 100..200)) {
316            let pk1 = secret1.public_image();
317            let pk2 = secret2.public_image();
318            let pk3 = secret3.public_image();
319            let expr: Expr = SigmaAnd::new(vec![
320                Expr::Const(pk1.into()),
321                SigmaAnd::new(vec![Expr::Const(pk2.into()), Expr::Const(pk3.into())])
322                    .unwrap()
323                    .into(),
324            ]).unwrap().into();
325            let tree = ErgoTree::try_from(expr).unwrap();
326            let prover = TestProver { secrets: vec![secret1, secret2, secret3] };
327            let res = prover.prove(&tree,
328                &force_any_val::<Context>(),
329                message.as_slice(),
330                &HintsBag::empty());
331            let proof = res.unwrap().proof;
332            let verifier = TestVerifier;
333            let ver_res = verifier.verify(&tree,
334                                          &force_any_val::<Context>(),
335                                          proof,
336                                          message.as_slice());
337            prop_assert_eq!(ver_res.unwrap().result, true);
338        }
339
340        #[test]
341        fn test_prover_verifier_conj_or(secret1 in any::<PrivateInput>(),
342                                         secret2 in any::<PrivateInput>(),
343                                         message in vec(any::<u8>(), 100..200)) {
344            let pk1 = secret1.public_image();
345            let pk2 = secret2.public_image();
346            let expr: Expr = SigmaOr::new(vec![Expr::Const(pk1.into()), Expr::Const(pk2.into())])
347                .unwrap()
348                .into();
349            let tree = ErgoTree::try_from(expr).unwrap();
350            let secrets = vec![secret1, secret2];
351            // any secret (out of 2) known to prover should be enough
352            for secret in secrets {
353                let prover = TestProver {
354                    secrets: vec![secret.clone()],
355                };
356                let res = prover.prove(&tree,
357                    &force_any_val::<Context>(),
358                    message.as_slice(),
359                    &HintsBag::empty());
360                let proof = res.unwrap_or_else(|_| panic!("proof failed for secret: {:?}", secret)).proof;
361                let verifier = TestVerifier;
362                let ver_res = verifier.verify(&tree,
363                                              &force_any_val::<Context>(),
364                                              proof,
365                                              message.as_slice());
366                prop_assert_eq!(ver_res.unwrap().result, true, "verify failed on secret: {:?}", &secret);
367            }
368        }
369
370        #[test]
371        fn test_prover_verifier_conj_or_or(secret1 in any::<PrivateInput>(),
372                                             secret2 in any::<PrivateInput>(),
373                                             secret3 in any::<PrivateInput>(),
374                                             message in vec(any::<u8>(), 100..200)) {
375            let pk1 = secret1.public_image();
376            let pk2 = secret2.public_image();
377            let pk3 = secret3.public_image();
378            let expr: Expr = SigmaOr::new(vec![
379                Expr::Const(pk1.into()),
380                SigmaOr::new(vec![Expr::Const(pk2.into()), Expr::Const(pk3.into())])
381                    .unwrap()
382                    .into(),
383            ]).unwrap().into();
384            let tree = ErgoTree::try_from(expr).unwrap();
385            let secrets = vec![secret1, secret2, secret3];
386            // any secret (out of 3) known to prover should be enough
387            for secret in secrets {
388                let prover = TestProver {
389                    secrets: vec![secret.clone()],
390                };
391                let res = prover.prove(&tree,
392                    &force_any_val::<Context>(),
393                    message.as_slice(),
394                    &HintsBag::empty());
395                let proof = res.unwrap_or_else(|_| panic!("proof failed for secret: {:?}", secret)).proof;
396                let verifier = TestVerifier;
397                let ver_res = verifier.verify(&tree,
398                                              &force_any_val::<Context>(),
399                                              proof,
400                                              message.as_slice());
401                prop_assert_eq!(ver_res.unwrap().result, true, "verify failed on secret: {:?}", &secret);
402            }
403        }
404
405        #[test]
406        fn test_prover_verifier_atleast(secret1 in any::<DlogProverInput>(),
407                                            secret2 in any::<DlogProverInput>(),
408                                             secret3 in any::<DlogProverInput>(),
409                                             message in vec(any::<u8>(), 100..200)) {
410            let bound = Expr::Const(2i32.into());
411            let inputs = Literal::Coll(
412                CollKind::from_collection(
413                    SType::SSigmaProp,
414                    [
415                        SigmaProp::from(secret1.public_image()).into(),
416                        SigmaProp::from(secret2.public_image()).into(),
417                        SigmaProp::from(secret3.public_image()).into(),
418                    ],
419                )
420                .unwrap(),
421            );
422            let input = Constant {
423                tpe: SType::SColl(SType::SSigmaProp.into()),
424                v: inputs,
425            }
426            .into();
427            let expr: Expr = Atleast::new(bound, input).unwrap().into();
428            let tree = ErgoTree::try_from(expr).unwrap();
429            let prover = TestProver {
430                secrets: vec![secret1.into(), secret3.into()],
431            };
432
433            let res = prover.prove(&tree,
434                &force_any_val::<Context>(),
435                message.as_slice(),
436                &HintsBag::empty());
437            let proof = res.unwrap().proof;
438            let verifier = TestVerifier;
439            let ver_res = verifier.verify(&tree,
440                &force_any_val::<Context>(),
441                proof,
442                message.as_slice());
443            prop_assert_eq!(ver_res.unwrap().result, true)
444        }
445    }
446}
ergotree_interpreter/sigma_protocol/verifier.rs

ergotree_interpreter/sigma_protocol/
verifier.rs
