ddk_trie/
lib.rs

1//! # Dlc-trie
2//! Package for storing and retrieving DLC data using tries.
3
4#![crate_name = "ddk_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 ddk_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 ddk_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    #[allow(clippy::too_many_arguments)]
123    fn generate_verify(
124        &'a mut self,
125        secp: &Secp256k1<secp256k1_zkp::All>,
126        fund_pubkey: &PublicKey,
127        funding_script_pubkey: &Script,
128        fund_output_value: Amount,
129        outcomes: &[RangePayout],
130        cets: &[Transaction],
131        precomputed_points: &[Vec<Vec<PublicKey>>],
132        adaptor_sigs: &[EcdsaAdaptorSignature],
133        adaptor_index_start: usize,
134    ) -> Result<usize, Error> {
135        let trie_info = self.generate(adaptor_index_start, outcomes)?;
136        verify_helper(
137            secp,
138            cets,
139            adaptor_sigs,
140            fund_pubkey,
141            funding_script_pubkey,
142            fund_output_value,
143            precomputed_points,
144            trie_info.into_iter(),
145        )
146    }
147
148    /// Generate the trie while creating the set of adaptor signatures.
149    #[allow(clippy::too_many_arguments)]
150    fn generate_sign(
151        &'a mut self,
152        secp: &Secp256k1<All>,
153        fund_privkey: &SecretKey,
154        funding_script_pubkey: &Script,
155        fund_output_value: Amount,
156        outcomes: &[RangePayout],
157        cets: &[Transaction],
158        precomputed_points: &[Vec<Vec<PublicKey>>],
159        adaptor_index_start: usize,
160    ) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
161        let trie_info = self.generate(adaptor_index_start, outcomes)?;
162        sign_helper(
163            secp,
164            cets,
165            fund_privkey,
166            funding_script_pubkey,
167            fund_output_value,
168            precomputed_points,
169            trie_info.into_iter(),
170        )
171    }
172
173    /// Verify that the provided signatures are valid with respect to the
174    /// information stored in the trie.
175    #[allow(clippy::too_many_arguments)]
176    fn verify(
177        &'a self,
178        secp: &Secp256k1<All>,
179        fund_pubkey: &PublicKey,
180        funding_script_pubkey: &Script,
181        fund_output_value: Amount,
182        adaptor_sigs: &[EcdsaAdaptorSignature],
183        cets: &[Transaction],
184        precomputed_points: &[Vec<Vec<PublicKey>>],
185    ) -> Result<usize, Error> {
186        verify_helper(
187            secp,
188            cets,
189            adaptor_sigs,
190            fund_pubkey,
191            funding_script_pubkey,
192            fund_output_value,
193            precomputed_points,
194            self.iter(),
195        )
196    }
197
198    /// Produce the set of adaptor signatures for the trie.
199    fn sign(
200        &'a self,
201        secp: &Secp256k1<All>,
202        fund_privkey: &SecretKey,
203        funding_script_pubkey: &Script,
204        fund_output_value: Amount,
205        cets: &[Transaction],
206        precomputed_points: &[Vec<Vec<PublicKey>>],
207    ) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
208        let trie_info = self.iter();
209        sign_helper(
210            secp,
211            cets,
212            fund_privkey,
213            funding_script_pubkey,
214            fund_output_value,
215            precomputed_points,
216            trie_info,
217        )
218    }
219}
220
221#[derive(Debug)]
222/// Holds information provided when iterating a DlcTrie.
223pub struct TrieIterInfo {
224    indexes: Vec<usize>,
225    paths: Vec<Vec<usize>>,
226    value: RangeInfo,
227}
228
229#[cfg(not(feature = "parallel"))]
230fn sign_helper<T: Iterator<Item = TrieIterInfo>>(
231    secp: &Secp256k1<All>,
232    cets: &[Transaction],
233    fund_privkey: &SecretKey,
234    funding_script_pubkey: &Script,
235    fund_output_value: Amount,
236    precomputed_points: &[Vec<Vec<PublicKey>>],
237    trie_info: T,
238) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
239    let mut unsorted = trie_info
240        .map(|x| {
241            let adaptor_point = utils::get_adaptor_point_for_indexed_paths(
242                &x.indexes,
243                &x.paths,
244                precomputed_points,
245            )?;
246            let adaptor_sig = ddk_dlc::create_cet_adaptor_sig_from_point(
247                secp,
248                &cets[x.value.cet_index],
249                &adaptor_point,
250                fund_privkey,
251                funding_script_pubkey,
252                fund_output_value,
253            )?;
254            Ok((x.value.adaptor_index, adaptor_sig))
255        })
256        .collect::<Result<Vec<(usize, EcdsaAdaptorSignature)>, Error>>()?;
257    unsorted.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
258    Ok(unsorted.into_iter().map(|(_, y)| y).collect())
259}
260
261#[cfg(feature = "parallel")]
262fn sign_helper<T: Iterator<Item = TrieIterInfo>>(
263    secp: &Secp256k1<All>,
264    cets: &[Transaction],
265    fund_privkey: &SecretKey,
266    funding_script_pubkey: &Script,
267    fund_output_value: Amount,
268    precomputed_points: &[Vec<Vec<PublicKey>>],
269    trie_info: T,
270) -> Result<Vec<EcdsaAdaptorSignature>, Error> {
271    let trie_info: Vec<TrieIterInfo> = trie_info.collect();
272    let mut unsorted = trie_info
273        .par_iter()
274        .map(|x| {
275            let adaptor_point = utils::get_adaptor_point_for_indexed_paths(
276                &x.indexes,
277                &x.paths,
278                precomputed_points,
279            )?;
280            let adaptor_sig = ddk_dlc::create_cet_adaptor_sig_from_point(
281                secp,
282                &cets[x.value.cet_index],
283                &adaptor_point,
284                fund_privkey,
285                funding_script_pubkey,
286                fund_output_value,
287            )?;
288            Ok((x.value.adaptor_index, adaptor_sig))
289        })
290        .collect::<Result<Vec<(usize, EcdsaAdaptorSignature)>, Error>>()?;
291    unsorted.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
292    Ok(unsorted.into_iter().map(|(_, y)| y).collect())
293}
294
295#[cfg(not(feature = "parallel"))]
296#[allow(clippy::too_many_arguments)]
297fn verify_helper<T: Iterator<Item = TrieIterInfo>>(
298    secp: &Secp256k1<All>,
299    cets: &[Transaction],
300    adaptor_sigs: &[EcdsaAdaptorSignature],
301    fund_pubkey: &PublicKey,
302    funding_script_pubkey: &Script,
303    fund_output_value: Amount,
304    precomputed_points: &[Vec<Vec<PublicKey>>],
305    trie_info: T,
306) -> Result<usize, Error> {
307    let mut max_adaptor_index = 0;
308    for x in trie_info {
309        let adaptor_point =
310            utils::get_adaptor_point_for_indexed_paths(&x.indexes, &x.paths, precomputed_points)?;
311        let adaptor_sig = adaptor_sigs[x.value.adaptor_index];
312        let cet = &cets[x.value.cet_index];
313        if x.value.adaptor_index > max_adaptor_index {
314            max_adaptor_index = x.value.adaptor_index;
315        }
316        ddk_dlc::verify_cet_adaptor_sig_from_point(
317            secp,
318            &adaptor_sig,
319            cet,
320            &adaptor_point,
321            fund_pubkey,
322            funding_script_pubkey,
323            fund_output_value,
324        )?;
325    }
326    Ok(max_adaptor_index + 1)
327}
328
329#[cfg(feature = "parallel")]
330fn verify_helper<T: Iterator<Item = TrieIterInfo>>(
331    secp: &Secp256k1<All>,
332    cets: &[Transaction],
333    adaptor_sigs: &[EcdsaAdaptorSignature],
334    fund_pubkey: &PublicKey,
335    funding_script_pubkey: &Script,
336    fund_output_value: Amount,
337    precomputed_points: &[Vec<Vec<PublicKey>>],
338    trie_info: T,
339) -> Result<usize, Error> {
340    let trie_info: Vec<TrieIterInfo> = trie_info.collect();
341    let max_adaptor_index = trie_info
342        .iter()
343        .max_by(|x, y| x.value.adaptor_index.cmp(&y.value.adaptor_index))
344        .unwrap();
345    trie_info.par_iter().try_for_each(|x| {
346        let adaptor_point =
347            utils::get_adaptor_point_for_indexed_paths(&x.indexes, &x.paths, precomputed_points)?;
348        let adaptor_sig = adaptor_sigs[x.value.adaptor_index];
349        let cet = &cets[x.value.cet_index];
350        ddk_dlc::verify_cet_adaptor_sig_from_point(
351            secp,
352            &adaptor_sig,
353            cet,
354            &adaptor_point,
355            fund_pubkey,
356            funding_script_pubkey,
357            fund_output_value,
358        )
359    })?;
360
361    Ok(max_adaptor_index.value.adaptor_index + 1)
362}
ddk_trie/lib.rs

ddk_trie/
lib.rs
