penumbra_sdk_proof_setup/single/
dlog.rs

1use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
2use rand_core::CryptoRngCore;
3
4use crate::single::group::{GroupHasher, Hash, F, G1};
5
6// Note: one choice you could make for these structs is to have them take
7// references to their data, instead of copying them. However, operations like
8// scalar multiplication take a move instead of a reference, at least in arkworks,
9// so you don't avoid a move by doing that.
10
11#[derive(Clone, Copy, Debug)]
12pub struct Statement {
13    pub result: G1,
14    pub base: G1,
15}
16
17#[derive(Clone, Copy, Debug)]
18pub struct Witness {
19    pub dlog: F,
20}
21
22/// A Proof of knowledge of the discrete logarithm of some element relative to another.
23#[derive(Clone, Copy, Debug, CanonicalSerialize, CanonicalDeserialize)]
24pub struct Proof {
25    big_k: G1,
26    s: F,
27}
28
29impl Proof {
30    /// Hash this proof
31    pub fn hash(&self) -> Hash {
32        let mut hasher = GroupHasher::new(b"PC$:proof");
33        hasher.eat_g1(&self.big_k);
34        hasher.eat_f(&self.s);
35        hasher.finalize_bytes()
36    }
37}
38
39// This method is pulled out to be used in both proving and verifying.
40
41/// Generate the challenge, given the context, statement, and nonce commitment.
42fn challenge(ctx: &[u8], statement: &Statement, big_k: &G1) -> F {
43    let mut hasher = GroupHasher::new(b"PC$:proof_chal");
44    hasher.eat_bytes(ctx);
45    hasher.eat_g1(&statement.result);
46    hasher.eat_g1(&statement.base);
47    hasher.eat_g1(big_k);
48    hasher.finalize()
49}
50
51/// Create a proof that one knows a discrete logarithm relative to a given base element.
52///
53/// This requires the statement, describing the base element, and the result of scalar
54/// multiplication, along with a witness, holding the scalar used for this multiplication.
55///
56/// We also take in a context string; the proof will only verify with a matching string.
57/// This allows binding a proof to a given context.
58pub fn prove<R: CryptoRngCore>(
59    rng: &mut R,
60    ctx: &[u8],
61    statement: Statement,
62    witness: Witness,
63) -> Proof {
64    let k = F::rand(rng);
65    let big_k = statement.base * k;
66
67    let e = challenge(ctx, &statement, &big_k);
68
69    let s = k + e * witness.dlog;
70
71    Proof { big_k, s }
72}
73
74/// Verify a proof that one knows a discrete logarithm relative to a given base element.
75///
76/// This requires the statement, describing the base element, and the result of scalar
77/// multiplication, and the proof to verify, in lieu of a witness.
78///
79/// We also take in a context string; the proof will only verify with a string matching
80/// the one used to create the proof.
81#[must_use]
82pub fn verify(ctx: &[u8], statement: Statement, proof: &Proof) -> bool {
83    let e = challenge(ctx, &statement, &proof.big_k);
84    statement.base * proof.s == proof.big_k + statement.result * e
85}
86
87#[cfg(test)]
88mod test {
89    use super::*;
90
91    use ark_ec::Group;
92    use rand_core::OsRng;
93
94    const TEST_CTX: &[u8] = b"Test Context";
95    const NOT_TEST_CTX: &[u8] = b"Not Test Context";
96
97    fn make_proof() -> (Statement, Witness, Proof) {
98        let dlog = F::rand(&mut OsRng);
99        let base = G1::generator();
100        let result = base * dlog;
101
102        let statement = Statement { result, base };
103        let witness = Witness { dlog };
104        let proof = prove(&mut OsRng, TEST_CTX, statement, witness);
105
106        (statement, witness, proof)
107    }
108
109    #[test]
110    fn test_proof_happy_path() {
111        let (statement, _, proof) = make_proof();
112        assert!(verify(TEST_CTX, statement, &proof));
113    }
114
115    #[test]
116    fn test_different_big_k_makes_proof_fail() {
117        let (statement, _, mut proof) = make_proof();
118        proof.big_k = G1::generator();
119        assert!(!verify(TEST_CTX, statement, &proof));
120    }
121
122    #[test]
123    fn test_different_s_makes_proof_fail() {
124        let (statement, _, mut proof) = make_proof();
125        proof.s = F::rand(&mut OsRng);
126        assert!(!verify(TEST_CTX, statement, &proof));
127    }
128
129    #[test]
130    fn test_different_ctx_makes_proof_fail() {
131        let (statement, _, proof) = make_proof();
132        assert!(!verify(NOT_TEST_CTX, statement, &proof));
133    }
134
135    #[test]
136    fn test_bad_statement_makes_proof_fail() {
137        let (mut statement, _, proof) = make_proof();
138        statement.result = statement.base;
139        assert!(!verify(NOT_TEST_CTX, statement, &proof));
140    }
141}
penumbra_sdk_proof_setup/single/dlog.rs

penumbra_sdk_proof_setup/single/
dlog.rs
