ergotree_interpreter/sigma_protocol/
dlog_protocol.rs

1//! Discrete logarithm signature protocol
2
3use super::wscalar::Wscalar;
4use super::ProverMessage;
5use ergo_chain_types::EcPoint;
6use ergotree_ir::serialization::SigmaSerializable;
7
8/// First message from the prover (message `a` of `SigmaProtocol`) for discrete logarithm case
9#[derive(PartialEq, Eq, Debug, Clone)]
10#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
11#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
12pub struct FirstDlogProverMessage {
13    #[cfg_attr(feature = "json", serde(rename = "a"))]
14    pub(crate) a: Box<EcPoint>,
15}
16
17impl From<EcPoint> for FirstDlogProverMessage {
18    fn from(ecp: EcPoint) -> Self {
19        FirstDlogProverMessage { a: ecp.into() }
20    }
21}
22
23impl ProverMessage for FirstDlogProverMessage {
24    fn bytes(&self) -> Vec<u8> {
25        #[allow(clippy::unwrap_used)]
26        // EcPoint serialization can only on OOM
27        self.a.sigma_serialize_bytes().unwrap()
28    }
29}
30
31/// Second message from the prover (message `z` of `SigmaProtocol`) for discrete logarithm case
32#[derive(PartialEq, Eq, Debug, Clone, derive_more::From, derive_more::Into)]
33#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
34pub struct SecondDlogProverMessage {
35    /// message `z`
36    pub z: Wscalar,
37}
38
39/// Interactive prover
40pub mod interactive_prover {
41    use std::ops::Mul;
42
43    use super::{FirstDlogProverMessage, SecondDlogProverMessage};
44    use crate::sigma_protocol::crypto_utils;
45    use crate::sigma_protocol::wscalar::Wscalar;
46    use crate::sigma_protocol::{private_input::DlogProverInput, Challenge};
47    use ergo_chain_types::{
48        ec_point::{exponentiate, generator, inverse},
49        EcPoint,
50    };
51    use ergotree_ir::sigma_protocol::dlog_group;
52    use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
53    use k256::Scalar;
54
55    /// Step 5 from <https://ergoplatform.org/docs/ErgoScript.pdf>
56    /// For every leaf marked “simulated”, use the simulator of the sigma protocol for that leaf
57    /// to compute the commitment "a" and the response "z", given the challenge "e" that
58    /// is already stored in the leaf
59    pub(crate) fn simulate(
60        public_input: &ProveDlog,
61        challenge: &Challenge,
62    ) -> (FirstDlogProverMessage, SecondDlogProverMessage) {
63        //SAMPLE a random z <- Zq
64        let z = dlog_group::random_scalar_in_group_range(crypto_utils::secure_rng());
65
66        //COMPUTE a = g^z*h^(-e)  (where -e here means -e mod q)
67        let e: Scalar = challenge.clone().into();
68        let minus_e = e.negate();
69        let h_to_e = exponentiate(&public_input.h, &minus_e);
70        let g_to_z = exponentiate(&generator(), &z);
71        let a = g_to_z * &h_to_e;
72        (
73            FirstDlogProverMessage { a: a.into() },
74            SecondDlogProverMessage { z: z.into() },
75        )
76    }
77
78    /// Step 6 from <https://ergoplatform.org/docs/ErgoScript.pdf>
79    /// For every leaf marked “real”, use the first prover step of the sigma protocol for
80    /// that leaf to compute the necessary randomness "r" and the commitment "a"
81    pub fn first_message() -> (Wscalar, FirstDlogProverMessage) {
82        let r = dlog_group::random_scalar_in_group_range(crypto_utils::secure_rng());
83        let g = generator();
84        let a = exponentiate(&g, &r);
85        (r.into(), FirstDlogProverMessage { a: a.into() })
86    }
87
88    /// Step 9 part 2 from <https://ergoplatform.org/docs/ErgoScript.pdf>
89    /// compute its response "z" according to the second prover step(step 5 in whitepaper)
90    /// of the sigma protocol given the randomness "r"(rnd) used for the commitment "a",
91    /// the challenge "e", and witness w.
92    pub(crate) fn second_message(
93        private_input: &DlogProverInput,
94        rnd: Wscalar,
95        challenge: &Challenge,
96    ) -> SecondDlogProverMessage {
97        let e: Scalar = challenge.clone().into();
98        // modulo multiplication, no need to explicit mod op
99        let ew = e.mul(private_input.w.as_scalar_ref());
100        // modulo addition, no need to explicit mod op
101        let z = rnd.as_scalar_ref().add(&ew);
102        SecondDlogProverMessage { z: z.into() }
103    }
104
105    /// The function computes initial prover's commitment to randomness
106    /// ("a" message of the sigma-protocol) based on the verifier's challenge ("e")
107    /// and prover's response ("z")
108    ///  
109    /// g^z = a*h^e => a = g^z/h^e
110    pub fn compute_commitment(
111        proposition: &ProveDlog,
112        challenge: &Challenge,
113        second_message: &SecondDlogProverMessage,
114    ) -> EcPoint {
115        let g = generator();
116        let h = *proposition.h.clone();
117        let e: Scalar = challenge.clone().into();
118        let g_z = exponentiate(&g, second_message.z.as_scalar_ref());
119        let h_e = exponentiate(&h, &e);
120        g_z * &inverse(&h_e)
121    }
122}
123
124#[allow(clippy::panic)]
125#[cfg(test)]
126#[cfg(feature = "arbitrary")]
127mod tests {
128    use super::super::*;
129    use super::*;
130    use crate::sigma_protocol::private_input::DlogProverInput;
131
132    use proptest::prelude::*;
133
134    proptest! {
135
136        #![proptest_config(ProptestConfig::with_cases(16))]
137
138        #[test]
139        #[cfg(feature = "arbitrary")]
140        fn test_compute_commitment(secret in any::<DlogProverInput>(), challenge in any::<Challenge>()) {
141            let pk = secret.public_image();
142            let (r, commitment) = interactive_prover::first_message();
143            let second_message = interactive_prover::second_message(&secret, r, &challenge);
144            let a = interactive_prover::compute_commitment(&pk, &challenge, &second_message);
145            prop_assert_eq!(a, *commitment.a);
146        }
147    }
148}
ergotree_interpreter/sigma_protocol/dlog_protocol.rs

ergotree_interpreter/sigma_protocol/
dlog_protocol.rs
