commit_verify/
embed.rs

1// Client-side-validation foundation libraries.
2//
3// SPDX-License-Identifier: Apache-2.0
4//
5// Written in 2019-2024 by
6//     Dr. Maxim Orlovsky <orlovsky@lnp-bp.org>
7//
8// Copyright (C) 2019-2024 LNP/BP Standards Association. All rights reserved.
9//
10// Licensed under the Apache License, Version 2.0 (the "License");
11// you may not use this file except in compliance with the License.
12// You may obtain a copy of the License at
13//
14//     http://www.apache.org/licenses/LICENSE-2.0
15//
16// Unless required by applicable law or agreed to in writing, software
17// distributed under the License is distributed on an "AS IS" BASIS,
18// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19// See the License for the specific language governing permissions and
20// limitations under the License.
21
22//! Embedded commitments (commit-embed-verify scheme).
23
24use crate::CommitmentProtocol;
25
26/// Error during commitment verification
27#[derive(Copy, Clone, Eq, PartialEq, Debug, Display, Error, From)]
28#[display(doc_comments)]
29pub enum EmbedVerifyError<E: std::error::Error> {
30    /// commitment doesn't match the message.
31    CommitmentMismatch,
32
33    /// the message is invalid since a valid commitment to it can't be created.
34    ///
35    /// Details: {0}
36    #[from]
37    InvalidMessage(E),
38
39    /// the proof is invalid and the commitment can't be verified since the
40    /// original container can't be restored from it.
41    InvalidProof,
42
43    /// the proof does not match to the proof generated for the same message
44    /// during the verification.
45    ProofMismatch,
46}
47
48/// Trait for equivalence verification. Implemented for all types implementing
49/// `Eq`. For non-`Eq` types this trait provides way to implement custom
50/// equivalence verification used during commitment verification procedure.
51pub trait VerifyEq {
52    /// Verifies commit-equivalence of two instances of the same type.
53    fn verify_eq(&self, other: &Self) -> bool;
54}
55
56impl<T> VerifyEq for T
57where T: Eq
58{
59    fn verify_eq(&self, other: &Self) -> bool { self == other }
60}
61
62/// Proofs produced by [`EmbedCommitVerify::embed_commit`] procedure.
63pub trait EmbedCommitProof<Msg, Container, Protocol>
64where
65    Self: Sized + VerifyEq,
66    Container: EmbedCommitVerify<Msg, Protocol>,
67    Protocol: CommitmentProtocol,
68{
69    /// Restores original container before the commitment from the proof data
70    /// and a container containing embedded commitment.
71    ///
72    /// # Error
73    ///
74    /// If the container can't be restored from the proof returns
75    /// [`EmbedVerifyError::InvalidProof`].
76    fn restore_original_container(
77        &self,
78        commit_container: &Container,
79    ) -> Result<Container, EmbedVerifyError<Container::CommitError>>;
80}
81
82/// Trait for *embed-commit-verify scheme*, where some data structure (named
83/// *container*) may commit to existing *message* (producing *commitment* data
84/// structure and a *proof*) in such way that the original message can't be
85/// restored from the commitment, however the fact of the commitment may be
86/// deterministically *verified* when the message and the proof are *revealed*.
87///
88/// To use *embed-commit-verify scheme* one needs to implement this trait for
89/// a data structure acting as a container for a specific commitment under
90/// certain protocol, specified as generic parameter. The container type must
91/// specify as associated types proof and commitment types.
92///
93/// Operations with *embed-commit-verify scheme* may be represented in form of
94/// `EmbedCommit: (Container, Message) -> (Container', Proof)` (see
95/// [`Self::embed_commit`] and `Verify: (Container', Message, Proof) -> bool`
96/// (see [`Self::verify`]).
97///
98/// This trait is heavily used in **deterministic bitcoin commitments**.
99///
100/// # Protocol definition
101///
102/// Generic parameter `Protocol` provides context & configuration for commitment
103/// scheme protocol used for this container type.
104///
105/// Introduction of this generic allows to:
106/// - implement trait for foreign data types;
107/// - add multiple implementations under different commitment protocols to the
108///   combination of the same message and container type (each of each will have
109///   its own `Proof` type defined as an associated generic).
110///
111/// Usually represents a non-instantiable type, but may be a structure
112/// containing commitment protocol configuration or context objects.
113///
114/// ```
115/// # use commit_verify::CommitmentProtocol;
116///
117/// // Uninstantiable type
118/// pub enum Lnpbp6 {}
119///
120/// impl CommitmentProtocol for Lnpbp6 {}
121///
122/// // Protocol definition
123/// pub enum Lnpbp1 {}
124/// // ...
125/// ```
126pub trait EmbedCommitVerify<Msg, Protocol>
127where
128    Self: Sized,
129    Protocol: CommitmentProtocol,
130{
131    /// The proof of the commitment produced as a result of
132    /// [`Self::embed_commit`] procedure. This proof is later used
133    /// for verification.
134    type Proof: EmbedCommitProof<Msg, Self, Protocol>;
135
136    /// Error type that may be reported during [`Self::embed_commit`] procedure.
137    /// It may also be returned from [`Self::verify`] (wrapped into
138    /// [`EmbedVerifyError`] in case the proof data are invalid and the
139    /// commitment can't be re-created.
140    type CommitError: std::error::Error;
141
142    /// Creates a commitment to a message and embeds it into the provided
143    /// container (`self`) by mutating it and returning commitment proof.
144    ///
145    /// Implementations must error with a dedicated error type enumerating
146    /// commitment procedure mistakes.
147    fn embed_commit(&mut self, msg: &Msg) -> Result<Self::Proof, Self::CommitError>;
148
149    /// Verifies commitment with commitment proof against the message.
150    ///
151    /// Default implementation reconstructs original container with the
152    /// [`EmbedCommitProof::restore_original_container`] method and repeats
153    /// [`Self::embed_commit`] procedure checking that the resulting proof and
154    /// commitment matches the provided `self` and `proof`.
155    ///
156    /// # Errors
157    ///
158    /// Errors if the commitment doesn't pass the validation (see
159    /// [`EmbedVerifyError`] variants for the cases when this may happen).
160    fn verify(
161        &self,
162        msg: &Msg,
163        proof: &Self::Proof,
164    ) -> Result<(), EmbedVerifyError<Self::CommitError>>
165    where
166        Self: VerifyEq,
167        Self::Proof: VerifyEq,
168    {
169        let mut container_prime = proof.restore_original_container(self)?;
170        let proof_prime = container_prime.embed_commit(msg)?;
171        if !proof_prime.verify_eq(proof) {
172            return Err(EmbedVerifyError::InvalidProof);
173        }
174        if !self.verify_eq(&container_prime) {
175            return Err(EmbedVerifyError::CommitmentMismatch);
176        }
177        Ok(())
178    }
179
180    /// Phantom method used to add `Protocol` generic parameter to the trait.
181    ///
182    /// # Panics
183    ///
184    /// Always panics when called.
185    #[doc(hidden)]
186    fn _phantom(_: Protocol) {
187        unimplemented!("EmbedCommitVerify::_phantom is a marker method which must not be used")
188    }
189}
190
191/// Helpers for writing test functions working with embed-commit-verify scheme.
192#[cfg(test)]
193pub(crate) mod test_helpers {
194    use core::fmt::Debug;
195    use core::hash::Hash;
196    use std::collections::HashSet;
197
198    use super::*;
199    use crate::{ConvolveCommit, ConvolveCommitProof};
200
201    pub enum TestProtocol {}
202    impl CommitmentProtocol for TestProtocol {}
203
204    pub const SUPPLEMENT: [u8; 32] = [0xFFu8; 32];
205
206    /// Runs round-trip of commitment-embed-verify for a given set of messages
207    /// and provided container.
208    pub fn embed_commit_verify_suite<Msg, Container>(messages: Vec<Msg>, container: Container)
209    where
210        Msg: AsRef<[u8]> + Eq + Clone,
211        Container: EmbedCommitVerify<Msg, TestProtocol> + Eq + Hash + Debug + Clone,
212        Container::Proof: Clone,
213    {
214        messages.iter().fold(
215            HashSet::<Container>::with_capacity(messages.len()),
216            |mut acc, msg| {
217                let mut commitment = container.clone();
218                let proof = commitment.embed_commit(msg).unwrap();
219
220                // Commitments MUST be deterministic: the same message must
221                // always produce the same commitment
222                (1..10).for_each(|_| {
223                    let mut commitment_prime = container.clone();
224                    commitment_prime.embed_commit(msg).unwrap();
225                    assert_eq!(commitment_prime, commitment);
226                });
227
228                // Testing verification
229                assert!(commitment.clone().verify(msg, &proof).is_ok());
230
231                messages.iter().for_each(|m| {
232                    // Testing that commitment verification succeeds only
233                    // for the original message and fails for the rest
234                    assert_eq!(commitment.clone().verify(m, &proof).is_ok(), m == msg);
235                });
236
237                acc.iter().for_each(|cmt| {
238                    // Testing that verification against other commitments
239                    // returns `false`
240                    assert!(cmt.clone().verify(msg, &proof).is_err());
241                });
242
243                // Detecting collision: each message should produce a unique
244                // commitment even if the same container is used
245                assert!(acc.insert(commitment));
246
247                acc
248            },
249        );
250    }
251
252    /// Runs round-trip of commitment-embed-verify for a given set of messages
253    /// and provided container.
254    pub fn convolve_commit_verify_suite<Msg, Source>(messages: Vec<Msg>, container: Source)
255    where
256        Msg: AsRef<[u8]> + Eq + Clone,
257        Source: ConvolveCommit<Msg, [u8; 32], TestProtocol> + VerifyEq + Eq + Hash + Debug + Clone,
258        Source::Commitment: Clone + Debug + Hash + VerifyEq + Eq,
259        [u8; 32]: ConvolveCommitProof<Msg, Source, TestProtocol, Suppl = [u8; 32]>,
260    {
261        messages.iter().fold(
262            HashSet::<Source::Commitment>::with_capacity(messages.len()),
263            |mut acc, msg| {
264                let (commitment, _) = container.convolve_commit(&SUPPLEMENT, msg).unwrap();
265
266                // Commitments MUST be deterministic: the same message must
267                // always produce the same commitment
268                (1..10).for_each(|_| {
269                    let (commitment_prime, _) =
270                        container.convolve_commit(&SUPPLEMENT, msg).unwrap();
271                    assert_eq!(commitment_prime, commitment);
272                });
273
274                // Testing verification
275                assert!(SUPPLEMENT.verify(msg, &commitment).is_ok());
276
277                messages.iter().for_each(|m| {
278                    // Testing that commitment verification succeeds only
279                    // for the original message and fails for the rest
280                    assert_eq!(SUPPLEMENT.verify(m, &commitment).is_ok(), m == msg);
281                });
282
283                acc.iter().for_each(|commitment| {
284                    // Testing that verification against other commitments
285                    // returns `false`
286                    assert!(SUPPLEMENT.verify(msg, commitment).is_err());
287                });
288
289                // Detecting collision: each message should produce a unique
290                // commitment even if the same container is used
291                assert!(acc.insert(commitment));
292
293                acc
294            },
295        );
296    }
297}
298
299#[cfg(test)]
300mod test {
301    use core::fmt::Debug;
302
303    use amplify::confinement::{SmallBlob, SmallVec, U32};
304    use sha2::Sha256;
305
306    use super::test_helpers::*;
307    use super::*;
308    use crate::digest::DigestExt;
309    use crate::test_helpers::gen_messages;
310    use crate::{ConvolveCommit, ConvolveCommitProof};
311
312    #[derive(Clone, PartialEq, Eq, Debug, Hash, Error, Display)]
313    #[display("error")]
314    struct Error;
315
316    #[derive(Clone, PartialEq, Eq, Debug, Hash)]
317    struct DummyVec(SmallBlob);
318
319    #[derive(Clone, PartialEq, Eq, Debug, Hash)]
320    struct DummyProof(SmallBlob);
321
322    impl<T> EmbedCommitProof<T, DummyVec, TestProtocol> for DummyProof
323    where T: AsRef<[u8]> + Clone
324    {
325        fn restore_original_container(
326            &self,
327            _: &DummyVec,
328        ) -> Result<DummyVec, EmbedVerifyError<Error>> {
329            Ok(DummyVec(self.0.clone()))
330        }
331    }
332
333    impl<T> EmbedCommitVerify<T, TestProtocol> for DummyVec
334    where T: AsRef<[u8]> + Clone
335    {
336        type Proof = DummyProof;
337        type CommitError = Error;
338
339        fn embed_commit(&mut self, msg: &T) -> Result<Self::Proof, Self::CommitError> {
340            let proof = self.0.clone();
341            let result = &mut self.0;
342            result.extend(msg.as_ref().iter().copied()).unwrap();
343            Ok(DummyProof(proof))
344        }
345    }
346
347    impl<T> ConvolveCommit<T, [u8; 32], TestProtocol> for DummyVec
348    where T: AsRef<[u8]> + Clone
349    {
350        type Commitment = [u8; 32];
351        type CommitError = Error;
352
353        fn convolve_commit(
354            &self,
355            supplement: &[u8; 32],
356            msg: &T,
357        ) -> Result<(Self::Commitment, [u8; 32]), Self::CommitError> {
358            let mut engine = Sha256::default();
359            engine.input_raw(supplement);
360            engine.input_with_len::<U32>(msg.as_ref());
361            Ok((engine.finish(), *supplement))
362        }
363    }
364
365    impl<T> ConvolveCommitProof<T, DummyVec, TestProtocol> for [u8; 32]
366    where T: AsRef<[u8]> + Clone
367    {
368        type Suppl = [u8; 32];
369
370        fn restore_original(&self, _: &[u8; 32]) -> DummyVec { DummyVec(default!()) }
371
372        fn extract_supplement(&self) -> &Self::Suppl { self }
373    }
374
375    #[test]
376    fn test_embed_commit() {
377        embed_commit_verify_suite::<SmallVec<u8>, DummyVec>(gen_messages(), DummyVec(default!()));
378    }
379
380    #[test]
381    fn test_convolve_commit() {
382        convolve_commit_verify_suite::<SmallVec<u8>, DummyVec>(
383            gen_messages(),
384            DummyVec(small_vec![0xC0; 15]),
385        );
386    }
387}