pixel_sig/
util.rs

1use crate::amcl_wrapper::group_elem::GroupElement;
2use crate::errors::PixelError;
3use amcl_wrapper::field_elem::FieldElement;
4use crate::{VerkeyGroup, SignatureGroup};
5
6/// second element is a vector of length l+2 and is of form [h, h_0, h_1, h_2, ..., h_l]
7pub struct GeneratorSet(pub VerkeyGroup, pub Vec<SignatureGroup>);
8
9impl GeneratorSet {
10    pub fn new(T: u128, prefix: &str) -> Result<Self, PixelError> {
11        Ok(GeneratorSet(
12            VerkeyGroup::from_msg_hash(prefix.as_bytes()),
13            Self::create_generators(T, prefix)?,
14        ))
15    }
16
17    /// Returns generators to be used in the protocol. Takes time period T and a prefix string that is
18    /// used to create generators by hashing the prefix string concatenated with integers. T+1 must be a power of 2.
19    pub fn create_generators(T: u128, prefix: &str) -> Result<Vec<SignatureGroup>, PixelError> {
20        let l = calculate_l(T)? as usize;
21        let mut params = Vec::with_capacity(l + 2);
22        for i in 0..(l + 2) {
23            let s: String = prefix.to_string() + &i.to_string();
24            params.push(SignatureGroup::from_msg_hash(s.as_bytes()));
25        }
26        Ok(params)
27    }
28}
29
30// TODO: Abstract left and right in an enum with values 1 and 2 rather than using hardcoded 1 and 2.
31// This also helps input validation in lots of places.
32
33/// Takes max time period to be supported T. Returns l where 2^l - 1 = T.
34pub fn calculate_l(T: u128) -> Result<u8, PixelError> {
35    if (T < 3) || (T == u128::max_value()) {
36        return Err(PixelError::InvalidMaxTimePeriod { T });
37    }
38
39    if !(T + 1).is_power_of_two() {
40        return Err(PixelError::NonPowerOfTwo { T });
41    }
42
43    let mut l = 0;
44    let mut t = T;
45    while t != 0 {
46        t = t >> 1;
47        l += 1;
48    }
49
50    Ok(l)
51}
52
53/// Convert path of node to node number (prefix). Path is from root to the node and
54/// `l = depth + 1` where `depth` is the depth of the tree.
55/*
56    // Note: This is different from paper as of 30/6/19. The formula in paper is incorrect.
57
58    If node is left child of parent then this node's number is 1 more than parent's node number
59    If node is right child of parent then this node's number is 1 + parent's node number + half of the number of children of the parent.
60    A more verbose form of the code would ne
61    if node is left_of(parent) {
62        node_num(node) = 1 + node_num(parent)
63    } else {
64        node_num(node) = 1 + node_num(parent) + (2^ (l - depth(node)) - 2) / 2
65        node_num(node) = 1 + node_num(parent) + (2^ (l - depth(node) - 1))
66    }
67*/
68pub fn path_to_node_num(path: &[u8], l: u8) -> Result<u128, PixelError> {
69    // TODO: Check that path always contains 1 or 2.
70    if (path.len() as u8) >= l {
71        return Err(PixelError::InvalidPath {
72            path: path.to_vec(),
73            l,
74        });
75    }
76    let mut t = 1u128;
77    for i in 1..(path.len() + 1) {
78        // t += 1 + 2^{l-i} * (path[i-1]-1)
79        t += 1 + (((1 << (l - i as u8)) as u128 - 1) * (path[i - 1] - 1) as u128) as u128;
80    }
81    Ok(t)
82}
83
84/// Convert node number (prefix) to path of node. Path is from root to the node and
85/// `l = depth + 1` where `depth` is the depth of the tree.
86pub fn from_node_num_to_path(t: u128, l: u8) -> Result<Vec<u8>, PixelError> {
87    if t > ((1 << l) - 1) as u128 {
88        return Err(PixelError::InvalidNodeNum { t, l });
89    }
90    if t == 1 {
91        return Ok(vec![]);
92    } else {
93        let two_l_1 = (1 << (l - 1)) as u128; // 2^{l-1}
94        if t <= two_l_1 {
95            // If node number falls in left half of tree, put a 1 in path and traverse the left subtree
96            let mut path = vec![1];
97            path.append(&mut from_node_num_to_path(t - 1, l - 1)?);
98            return Ok(path);
99        } else {
100            // If node number falls in right half of tree, put a 2 in path and traverse the right subtree.
101            // The right subtree will have 2^{l-1} nodes less than the original tree since left subtree had 2^{l-1}-1 nodes.
102            let mut path = vec![2];
103            path.append(&mut from_node_num_to_path(t - two_l_1, l - 1)?);
104            return Ok(path);
105        }
106    }
107}
108
109/// Returns path of all successors of the node given by time t. Successors corresponds to the set
110/// containing all the right-hand siblings of nodes on the path from t to the root.
111/// The siblings are ordered from lowest number to highest.
112pub fn node_successor_paths(t: u128, l: u8) -> Result<Vec<Vec<u8>>, PixelError> {
113    if t > ((1 << l) - 1) as u128 {
114        return Err(PixelError::InvalidNodeNum { t, l });
115    }
116    if t == 1 {
117        return Ok(vec![]);
118    } else {
119        let mut curr_path = vec![];
120        let mut successors = vec![];
121        let path = from_node_num_to_path(t, l)?;
122        for p in path {
123            if p == 1 {
124                let mut s = curr_path.clone();
125                s.push(2);
126                successors.push(s);
127            }
128            curr_path.push(p)
129        }
130        successors.reverse();
131        return Ok(successors);
132    }
133}
134
135/// Calculate h_0*h_1^path[0]*h_2^path[2]*......
136pub fn calculate_path_factor_using_t_l(
137    t: u128,
138    l: u8,
139    gens: &GeneratorSet,
140) -> Result<SignatureGroup, PixelError> {
141    // TODO: Find better name for this function
142    let path = from_node_num_to_path(t, l)?;
143    calculate_path_factor(path, gens)
144}
145
146/// Calculate h_0*h_1^path[0]*h_2^path[2]*......
147pub fn calculate_path_factor(path: Vec<u8>, gens: &GeneratorSet) -> Result<SignatureGroup, PixelError> {
148    // TODO: Find better name for this function
149
150    if gens.1.len() < (path.len() + 2) {
151        return Err(PixelError::NotEnoughGenerators { n: path.len() + 2 });
152    }
153    let mut sigma_1_1 = gens.1[1].clone(); // h_0
154
155    // h_0*h_1^path[0]*h_2^path[2]*......
156    for (i, p) in path.iter().enumerate() {
157        if *p == 1 {
158            sigma_1_1 += &gens.1[2 + i]
159        } else {
160            sigma_1_1 += &gens.1[2 + i].double()
161        }
162    }
163
164    Ok(sigma_1_1)
165}
166
167#[cfg(test)]
168mod tests {
169    use super::*;
170    use std::collections::HashSet;
171    use std::iter::FromIterator;
172
173    #[test]
174    fn test_calculate_l() {
175        assert!(calculate_l(u128::max_value()).is_err());
176
177        let valid_Ts: HashSet<u128> = HashSet::from_iter(vec![3, 7, 15, 31, 63].iter().cloned());
178
179        assert_eq!(calculate_l(3).unwrap(), 2);
180        assert_eq!(calculate_l(7).unwrap(), 3);
181        assert_eq!(calculate_l(15).unwrap(), 4);
182        assert_eq!(calculate_l(31).unwrap(), 5);
183
184        for i in 1..65 {
185            if !valid_Ts.contains(&i) {
186                assert!(calculate_l(i).is_err());
187            }
188        }
189    }
190
191    #[test]
192    fn test_path_to_node_num() {
193        assert!(path_to_node_num(&[1, 2, 1], 3).is_err());
194        assert!(path_to_node_num(&[1, 2, 1, 1], 3).is_err());
195
196        assert!(path_to_node_num(&[1, 1, 2, 1], 4).is_err());
197        assert!(path_to_node_num(&[2, 1, 2, 1, 1], 4).is_err());
198
199        assert_eq!(path_to_node_num(&[], 3).unwrap(), 1);
200        assert_eq!(path_to_node_num(&[1], 3).unwrap(), 2);
201        assert_eq!(path_to_node_num(&[2], 3).unwrap(), 5);
202        assert_eq!(path_to_node_num(&[2, 1], 3).unwrap(), 6);
203        assert_eq!(path_to_node_num(&[2, 2], 3).unwrap(), 7);
204        assert_eq!(path_to_node_num(&[1, 1], 3).unwrap(), 3);
205        assert_eq!(path_to_node_num(&[1, 1, 1], 4).unwrap(), 4);
206        assert_eq!(path_to_node_num(&[1, 1, 2], 4).unwrap(), 5);
207        assert_eq!(path_to_node_num(&[1, 2], 4).unwrap(), 6);
208        assert_eq!(path_to_node_num(&[1, 2, 1], 4).unwrap(), 7);
209        assert_eq!(path_to_node_num(&[1, 2, 2], 4).unwrap(), 8);
210        assert_eq!(path_to_node_num(&[2], 4).unwrap(), 9);
211    }
212
213    #[test]
214    fn test_from_node_num_to_path() {
215        assert!(from_node_num_to_path(8, 3).is_err());
216        assert!(from_node_num_to_path(9, 3).is_err());
217        assert!(from_node_num_to_path(10, 3).is_err());
218
219        assert!(from_node_num_to_path(16, 4).is_err());
220        assert!(from_node_num_to_path(17, 4).is_err());
221        assert!(from_node_num_to_path(20, 4).is_err());
222
223        assert_eq!(from_node_num_to_path(1, 3).unwrap(), Vec::<u8>::new());
224        assert_eq!(from_node_num_to_path(2, 3).unwrap(), vec![1]);
225        assert_eq!(from_node_num_to_path(3, 3).unwrap(), vec![1, 1]);
226        assert_eq!(from_node_num_to_path(4, 3).unwrap(), vec![1, 2]);
227        assert_eq!(from_node_num_to_path(5, 3).unwrap(), vec![2]);
228        assert_eq!(from_node_num_to_path(6, 3).unwrap(), vec![2, 1]);
229        assert_eq!(from_node_num_to_path(7, 3).unwrap(), vec![2, 2]);
230        assert_eq!(from_node_num_to_path(15, 4).unwrap(), vec![2, 2, 2]);
231        assert_eq!(from_node_num_to_path(14, 4).unwrap(), vec![2, 2, 1]);
232        assert_eq!(from_node_num_to_path(13, 4).unwrap(), vec![2, 2]);
233        assert_eq!(from_node_num_to_path(10, 4).unwrap(), vec![2, 1]);
234        assert_eq!(from_node_num_to_path(11, 4).unwrap(), vec![2, 1, 1]);
235        assert_eq!(from_node_num_to_path(12, 4).unwrap(), vec![2, 1, 2]);
236        assert_eq!(from_node_num_to_path(8, 4).unwrap(), vec![1, 2, 2]);
237    }
238
239    // TODO: Test to and from conversion of path and node number using randoms
240
241    #[test]
242    fn test_node_successors_7() {
243        let T = 7;
244        let l = calculate_l(T).unwrap();
245        let successors = node_successor_paths(1, l).unwrap();
246        assert!(successors.is_empty());
247        let successors = node_successor_paths(2, l).unwrap();
248        assert_eq!(successors, vec![vec![2]]);
249        let successors = node_successor_paths(3, l).unwrap();
250        assert_eq!(successors, vec![vec![1, 2], vec![2]]);
251        let successors = node_successor_paths(4, l).unwrap();
252        assert_eq!(successors, vec![vec![2]]);
253        let successors = node_successor_paths(5, l).unwrap();
254        assert!(successors.is_empty());
255        let successors = node_successor_paths(6, l).unwrap();
256        assert_eq!(successors, vec![vec![2, 2]]);
257        let successors = node_successor_paths(7, l).unwrap();
258        assert!(successors.is_empty());
259    }
260
261    #[test]
262    fn test_node_successors_15() {
263        let T = 15;
264        let l = calculate_l(T).unwrap();
265        let successors = node_successor_paths(1, l).unwrap();
266        assert!(successors.is_empty());
267        let successors = node_successor_paths(2, l).unwrap();
268        assert_eq!(successors, vec![vec![2]]);
269        let successors = node_successor_paths(3, l).unwrap();
270        assert_eq!(successors, vec![vec![1, 2], vec![2]]);
271        let successors = node_successor_paths(4, l).unwrap();
272        assert_eq!(successors, vec![vec![1, 1, 2], vec![1, 2], vec![2]]);
273        let successors = node_successor_paths(5, l).unwrap();
274        assert_eq!(successors, vec![vec![1, 2], vec![2]]);
275        let successors = node_successor_paths(6, l).unwrap();
276        assert_eq!(successors, vec![vec![2]]);
277        let successors = node_successor_paths(7, l).unwrap();
278        assert_eq!(successors, vec![vec![1, 2, 2], vec![2]]);
279        let successors = node_successor_paths(9, l).unwrap();
280        assert!(successors.is_empty());
281        let successors = node_successor_paths(10, l).unwrap();
282        assert_eq!(successors, vec![vec![2, 2]]);
283        let successors = node_successor_paths(11, l).unwrap();
284        assert_eq!(successors, vec![vec![2, 1, 2], vec![2, 2]]);
285        let successors = node_successor_paths(12, l).unwrap();
286        assert_eq!(successors, vec![vec![2, 2]]);
287        let successors = node_successor_paths(15, l).unwrap();
288        assert!(successors.is_empty());
289    }
290}
pixel_sig/util.rs

pixel_sig/
util.rs
