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}