dlc_trie/
lib.rs

1//! # Dlc-trie
2//! Package for storing and retrieving DLC data using tries.
3
4#![crate_name = "dlc_trie"]
5// Coding conventions
6#![forbid(unsafe_code)]
7#![deny(non_upper_case_globals)]
8#![deny(non_camel_case_types)]
9#![deny(non_snake_case)]
10#![deny(unused_mut)]
11#![deny(dead_code)]
12#![deny(unused_imports)]
13#![deny(missing_docs)]
14
15extern crate bitcoin;
16extern crate dlc;
17#[cfg(feature = "parallel")]
18extern crate rayon;
19extern crate secp256k1_zkp;
20#[cfg(feature = "use-serde")]
21extern crate serde;
22
23use bitcoin::{Amount, Script, Transaction};
24use dlc::{Error, RangePayout};
25#[cfg(feature = "parallel")]
26use rayon::prelude::*;
27use secp256k1_zkp::{All, EcdsaAdaptorSignature, PublicKey, Secp256k1, SecretKey};
28#[cfg(feature = "use-serde")]
29use serde::{Deserialize, Serialize};
30
31pub mod combination_iterator;
32pub mod digit_decomposition;
33pub mod digit_trie;
34pub mod multi_oracle;
35pub mod multi_oracle_trie;
36pub mod multi_oracle_trie_with_diff;
37pub mod multi_trie;
38#[cfg(test)]
39mod test_utils;
40mod utils;
41
42pub(crate) type IndexedPath = (usize, Vec<usize>);
43
44/// Structure containing a reference to a looked-up value and the
45/// path at which it was found.
46#[derive(Debug, Clone)]
47pub struct LookupResult<'a, TValue, TPath> {
48    /// The path at which the `value` was found.
49    pub path: Vec<TPath>,
50    /// The value that was returned.
51    pub value: &'a TValue,
52}
53
54/// Enum representing the different type of nodes in a tree
55#[derive(Debug, Clone)]
56pub enum Node<TLeaf, TNode> {
57    /// None is only used as a placeholder when taking mutable ownership of a
58    /// node during insertion.
59    None,
60    /// A leaf is a node in the tree that does not have any children.
61    Leaf(TLeaf),
62    /// A node is parent to at least one other node in a tree.
63    Node(TNode),
64}
65
66#[derive(Eq, PartialEq, Debug, Clone)]
67/// Structure that stores the indexes at which the CET and adaptor signature
68/// related to a given outcome are located in CET and adaptor signatures arrays
69/// respectively.
70pub struct RangeInfo {
71    /// a cet index
72    pub cet_index: usize,
73    /// an adaptor signature index
74    pub adaptor_index: usize,
75}
76
77#[derive(Clone, Debug)]
78#[cfg_attr(
79    feature = "use-serde",
80    derive(Serialize, Deserialize),
81    serde(rename_all = "camelCase")
82)]
83/// Information about the base and number of digits used by the oracle.
84pub struct OracleNumericInfo {
85    /// The base in which the oracle will represent the outcome value.
86    pub base: usize,
87    /// The number of digits that each oracle will use to represent the outcome value.
88    pub nb_digits: Vec<usize>,
89}
90
91impl OracleNumericInfo {
92    /// Return the minimum number of digits supported by an oracle in the group.
93    pub fn get_min_nb_digits(&self) -> usize {
94        *self.nb_digits.iter().min().unwrap()
95    }
96
97    /// Returns whether oracles have varying number of digits.
98    pub fn has_diff_nb_digits(&self) -> bool {
99        self.nb_digits
100            .iter()
101            .skip(1)
102            .any(|x| *x != self.nb_digits[0])
103    }
104}
105
106/// A common trait for trie data structures that store DLC adaptor signature
107/// information.
108pub trait DlcTrie<'a, TrieIterator: Iterator<Item = TrieIterInfo>> {
109    /// Generate the trie using the provided outcomes and oracle information,
110    /// calling the provided callback with the CET index and adaptor point for
111    /// each adaptor signature.
112    fn generate(
113        &'a mut self,
114        adaptor_index_start: usize,
115        outcomes: &[RangePayout],
116    ) -> Result<Vec<TrieIterInfo>, Error>;
117
118    /// Returns an iterator to this trie.
119    fn iter(&'a self) -> TrieIterator;
120
121    /// Generate the trie while verifying the provided adaptor signatures.
122    fn generate_verify(
123        &'a mut self,
124        secp: &Secp256k1<secp256k1_zkp::All>,
125        fund_pubkey: &PublicKey,
126        funding_script_pubkey: &Script,
127        fund_output_value: Amount,
128        outcomes: &[RangePayout],
129        cets: &[Transaction],
130        precomputed_points: &[Vec<Vec<PublicKey>>],
131        adaptor_sigs: &[EcdsaAdaptorSignature],
132        adaptor_index_start: usize,
133    ) -> Result<usize, Error> {
134        let trie_info = self.generate(adaptor_index_start, outcomes)?;
135        verify_helper(
136            secp,
137            cets,
138            adaptor_sigs,
139            fund_pubkey,
140            funding_script_pubkey,
141            fund_output_value,
142            precomputed_points,
143            trie_info.into_iter(),
144        )
145    }
146
147    /// Generate the trie while creating the set of adaptor signatures.
148    fn generate_sign(
149        &'a mut self,
150        secp: &Secp256k1<All>,
151        fund_privkey: &SecretKey,
152        funding_script_pubkey: &Script,
153        fund_output_value: Amount,
154        outcomes: &[RangePayout],
155        cets: &[Transaction],
156        precomputed_points: &[Vec<Vec<PublicKey>>],
157        adaptor_index_start: usize,
158    ) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
159        let trie_info = self.generate(adaptor_index_start, outcomes)?;
160        sign_helper(
161            secp,
162            cets,
163            fund_privkey,
164            funding_script_pubkey,
165            fund_output_value,
166            precomputed_points,
167            trie_info.into_iter(),
168        )
169    }
170
171    /// Verify that the provided signatures are valid with respect to the
172    /// information stored in the trie.
173    fn verify(
174        &'a self,
175        secp: &Secp256k1<All>,
176        fund_pubkey: &PublicKey,
177        funding_script_pubkey: &Script,
178        fund_output_value: Amount,
179        adaptor_sigs: &[EcdsaAdaptorSignature],
180        cets: &[Transaction],
181        precomputed_points: &[Vec<Vec<PublicKey>>],
182    ) -> Result<usize, Error> {
183        verify_helper(
184            secp,
185            cets,
186            adaptor_sigs,
187            fund_pubkey,
188            funding_script_pubkey,
189            fund_output_value,
190            precomputed_points,
191            self.iter(),
192        )
193    }
194
195    /// Produce the set of adaptor signatures for the trie.
196    fn sign(
197        &'a self,
198        secp: &Secp256k1<All>,
199        fund_privkey: &SecretKey,
200        funding_script_pubkey: &Script,
201        fund_output_value: Amount,
202        cets: &[Transaction],
203        precomputed_points: &[Vec<Vec<PublicKey>>],
204    ) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
205        let trie_info = self.iter();
206        sign_helper(
207            secp,
208            cets,
209            fund_privkey,
210            funding_script_pubkey,
211            fund_output_value,
212            precomputed_points,
213            trie_info,
214        )
215    }
216}
217
218#[derive(Debug)]
219/// Holds information provided when iterating a DlcTrie.
220pub struct TrieIterInfo {
221    indexes: Vec<usize>,
222    paths: Vec<Vec<usize>>,
223    value: RangeInfo,
224}
225
226#[cfg(not(feature = "parallel"))]
227fn sign_helper<T: Iterator<Item = TrieIterInfo>>(
228    secp: &Secp256k1<All>,
229    cets: &[Transaction],
230    fund_privkey: &SecretKey,
231    funding_script_pubkey: &Script,
232    fund_output_value: Amount,
233    precomputed_points: &[Vec<Vec<PublicKey>>],
234    trie_info: T,
235) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
236    let mut unsorted = trie_info
237        .map(|x| {
238            let adaptor_point = utils::get_adaptor_point_for_indexed_paths(
239                &x.indexes,
240                &x.paths,
241                precomputed_points,
242            )?;
243            let adaptor_sig = dlc::create_cet_adaptor_sig_from_point(
244                secp,
245                &cets[x.value.cet_index],
246                &adaptor_point,
247                fund_privkey,
248                funding_script_pubkey,
249                fund_output_value,
250            )?;
251            Ok((x.value.adaptor_index, adaptor_sig))
252        })
253        .collect::<Result<Vec<(usize, EcdsaAdaptorSignature)>, Error>>()?;
254    unsorted.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
255    Ok(unsorted.into_iter().map(|(_, y)| y).collect())
256}
257
258#[cfg(feature = "parallel")]
259fn sign_helper<T: Iterator<Item = TrieIterInfo>>(
260    secp: &Secp256k1<All>,
261    cets: &[Transaction],
262    fund_privkey: &SecretKey,
263    funding_script_pubkey: &Script,
264    fund_output_value: Amount,
265    precomputed_points: &[Vec<Vec<PublicKey>>],
266    trie_info: T,
267) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
268    let trie_info: Vec<TrieIterInfo> = trie_info.collect();
269    let mut unsorted = trie_info
270        .par_iter()
271        .map(|x| {
272            let adaptor_point = utils::get_adaptor_point_for_indexed_paths(
273                &x.indexes,
274                &x.paths,
275                precomputed_points,
276            )?;
277            let adaptor_sig = dlc::create_cet_adaptor_sig_from_point(
278                secp,
279                &cets[x.value.cet_index],
280                &adaptor_point,
281                fund_privkey,
282                funding_script_pubkey,
283                fund_output_value,
284            )?;
285            Ok((x.value.adaptor_index, adaptor_sig))
286        })
287        .collect::<Result<Vec<(usize, EcdsaAdaptorSignature)>, Error>>()?;
288    unsorted.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
289    Ok(unsorted.into_iter().map(|(_, y)| y).collect())
290}
291
292#[cfg(not(feature = "parallel"))]
293fn verify_helper<T: Iterator<Item = TrieIterInfo>>(
294    secp: &Secp256k1<All>,
295    cets: &[Transaction],
296    adaptor_sigs: &[EcdsaAdaptorSignature],
297    fund_pubkey: &PublicKey,
298    funding_script_pubkey: &Script,
299    fund_output_value: Amount,
300    precomputed_points: &[Vec<Vec<PublicKey>>],
301    trie_info: T,
302) -> Result<usize, Error> {
303    let mut max_adaptor_index = 0;
304    for x in trie_info {
305        let adaptor_point =
306            utils::get_adaptor_point_for_indexed_paths(&x.indexes, &x.paths, precomputed_points)?;
307        let adaptor_sig = adaptor_sigs[x.value.adaptor_index];
308        let cet = &cets[x.value.cet_index];
309        if x.value.adaptor_index > max_adaptor_index {
310            max_adaptor_index = x.value.adaptor_index;
311        }
312        dlc::verify_cet_adaptor_sig_from_point(
313            secp,
314            &adaptor_sig,
315            cet,
316            &adaptor_point,
317            fund_pubkey,
318            funding_script_pubkey,
319            fund_output_value,
320        )?;
321    }
322    Ok(max_adaptor_index + 1)
323}
324
325#[cfg(feature = "parallel")]
326fn verify_helper<T: Iterator<Item = TrieIterInfo>>(
327    secp: &Secp256k1<All>,
328    cets: &[Transaction],
329    adaptor_sigs: &[EcdsaAdaptorSignature],
330    fund_pubkey: &PublicKey,
331    funding_script_pubkey: &Script,
332    fund_output_value: Amount,
333    precomputed_points: &[Vec<Vec<PublicKey>>],
334    trie_info: T,
335) -> Result<usize, Error> {
336    let trie_info: Vec<TrieIterInfo> = trie_info.collect();
337    let max_adaptor_index = trie_info
338        .iter()
339        .max_by(|x, y| x.value.adaptor_index.cmp(&y.value.adaptor_index))
340        .unwrap();
341    trie_info.par_iter().try_for_each(|x| {
342        let adaptor_point =
343            utils::get_adaptor_point_for_indexed_paths(&x.indexes, &x.paths, precomputed_points)?;
344        let adaptor_sig = adaptor_sigs[x.value.adaptor_index];
345        let cet = &cets[x.value.cet_index];
346        dlc::verify_cet_adaptor_sig_from_point(
347            secp,
348            &adaptor_sig,
349            cet,
350            &adaptor_point,
351            fund_pubkey,
352            funding_script_pubkey,
353            fund_output_value,
354        )
355    })?;
356
357    Ok(max_adaptor_index.value.adaptor_index + 1)
358}
dlc_trie/lib.rs

dlc_trie/
lib.rs
