storage_proofs_core/
util.rs

1use std::cmp::min;
2
3use anyhow::ensure;
4use bellperson::{
5    gadgets::boolean::{AllocatedBit, Boolean},
6    ConstraintSystem, SynthesisError,
7};
8use ff::PrimeField;
9use merkletree::merkle::get_merkle_tree_row_count;
10
11use crate::{error::Error, settings};
12
13pub const NODE_SIZE: usize = 32;
14
15/// Returns the start position of the data, 0-indexed.
16pub fn data_at_node_offset(v: usize) -> usize {
17    v * NODE_SIZE
18}
19
20/// Returns the byte slice representing one node (of uniform size, NODE_SIZE) at position v in data.
21pub fn data_at_node(data: &[u8], v: usize) -> anyhow::Result<&[u8]> {
22    let offset = data_at_node_offset(v);
23
24    ensure!(
25        offset + NODE_SIZE <= data.len(),
26        Error::OutOfBounds(offset + NODE_SIZE, data.len())
27    );
28
29    Ok(&data[offset..offset + NODE_SIZE])
30}
31
32/// Converts bytes into their bit representation, in little endian format.
33pub fn bytes_into_bits(bytes: &[u8]) -> Vec<bool> {
34    bytes
35        .iter()
36        .flat_map(|&byte| (0..8).map(move |i| (byte >> i) & 1u8 == 1u8))
37        .collect()
38}
39
40/// Converts bytes into their bit representation, in little endian format.
41pub fn bytes_into_bits_opt(bytes: &[u8]) -> Vec<Option<bool>> {
42    bytes
43        .iter()
44        .flat_map(|&byte| (0..8).map(move |i| Some((byte >> i) & 1u8 == 1u8)))
45        .collect()
46}
47
48/// Converts bytes into their bit representation, in big endian format.
49pub fn bytes_into_bits_be(bytes: &[u8]) -> Vec<bool> {
50    bytes
51        .iter()
52        .flat_map(|&byte| (0..8).rev().map(move |i| (byte >> i) & 1u8 == 1u8))
53        .collect()
54}
55
56/// Converts the bytes into a boolean vector, in little endian format.
57pub fn bytes_into_boolean_vec<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
58    mut cs: CS,
59    value: Option<&[u8]>,
60    size: usize,
61) -> Result<Vec<Boolean>, SynthesisError> {
62    let values = match value {
63        Some(value) => bytes_into_bits(value).into_iter().map(Some).collect(),
64        None => vec![None; size],
65    };
66
67    let bits = values
68        .into_iter()
69        .enumerate()
70        .map(|(i, b)| {
71            Ok(Boolean::from(AllocatedBit::alloc(
72                cs.namespace(|| format!("bit {}", i)),
73                b,
74            )?))
75        })
76        .collect::<Result<Vec<_>, SynthesisError>>()?;
77
78    Ok(bits)
79}
80
81/// Converts the bytes into a boolean vector, in big endian format.
82pub fn bytes_into_boolean_vec_be<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
83    mut cs: CS,
84    value: Option<&[u8]>,
85    size: usize,
86) -> Result<Vec<Boolean>, SynthesisError> {
87    let values = match value {
88        Some(value) => bytes_into_bits_be(value).into_iter().map(Some).collect(),
89        None => vec![None; size],
90    };
91
92    let bits = values
93        .into_iter()
94        .enumerate()
95        .map(|(i, b)| {
96            Ok(Boolean::from(AllocatedBit::alloc(
97                cs.namespace(|| format!("bit {}", i)),
98                b,
99            )?))
100        })
101        .collect::<Result<Vec<_>, SynthesisError>>()?;
102
103    Ok(bits)
104}
105
106#[allow(dead_code)]
107#[inline]
108fn bool_to_u8(bit: bool, offset: usize) -> u8 {
109    if bit {
110        1u8 << offset
111    } else {
112        0u8
113    }
114}
115
116/// Converts a slice of bools into their byte representation, in little endian.
117#[allow(dead_code)]
118pub fn bits_to_bytes(bits: &[bool]) -> Vec<u8> {
119    bits.chunks(8)
120        .map(|bits| {
121            bool_to_u8(bits[7], 7)
122                | bool_to_u8(bits[6], 6)
123                | bool_to_u8(bits[5], 5)
124                | bool_to_u8(bits[4], 4)
125                | bool_to_u8(bits[3], 3)
126                | bool_to_u8(bits[2], 2)
127                | bool_to_u8(bits[1], 1)
128                | bool_to_u8(bits[0], 0)
129        })
130        .collect()
131}
132
133/// Reverse the order of bits within each byte (bit numbering), but without altering the order of bytes
134/// within the array (endianness) — when bit array is viewed as a flattened sequence of octets.
135/// Before intra-byte bit reversal begins, zero-bit padding is added so every byte is full.
136pub fn reverse_bit_numbering(bits: Vec<Boolean>) -> Vec<Boolean> {
137    let mut padded_bits = bits;
138    // Pad partial bytes
139    while padded_bits.len() % 8 != 0 {
140        padded_bits.push(Boolean::Constant(false));
141    }
142
143    padded_bits
144        .chunks(8)
145        .flat_map(|chunk| chunk.iter().rev())
146        .cloned()
147        .collect()
148}
149
150// If the tree is large enough to use the default value (per-arity), use it.  If it's too small to cache anything (i.e. not enough rows), don't discard any.
151pub fn default_rows_to_discard(leafs: usize, arity: usize) -> usize {
152    let row_count = get_merkle_tree_row_count(leafs, arity);
153    if row_count <= 2 {
154        // If a tree only has a root row and/or base, there is
155        // nothing to discard.
156        return 0;
157    } else if row_count == 3 {
158        // If a tree only has 1 row between the base and root,
159        // it's all that can be discarded.
160        return 1;
161    }
162
163    // row_count - 2 discounts the base layer (1) and root (1)
164    let max_rows_to_discard = row_count - 2;
165
166    // When `fixed-rows-to-discard` is set, then the number of rows to discard for the tree_r_last
167    // is hard-coded to 2. If the feature is not set it can be configured with the
168    // `ROWS_TO_DISCARD` setting.
169    #[cfg(feature = "fixed-rows-to-discard")]
170    let rows_to_discard = settings::DEFAULT_ROWS_TO_DISCARD as usize;
171    #[cfg(not(feature = "fixed-rows-to-discard"))]
172    let rows_to_discard = settings::SETTINGS.rows_to_discard as usize;
173
174    // Discard at most 'constant value' rows (coded below,
175    // differing by arity) while respecting the max number that
176    // the tree can support discarding.
177    match arity {
178        2 => min(max_rows_to_discard, 7),
179        4 => min(max_rows_to_discard, 5),
180        _ => min(max_rows_to_discard, rows_to_discard),
181    }
182}
183
184#[cfg(test)]
185mod tests {
186    use super::*;
187
188    use bellperson::{gadgets::num::AllocatedNum, util_cs::test_cs::TestConstraintSystem};
189    use blstrs::Scalar as Fr;
190    use ff::Field;
191    use filecoin_hashers::{sha256::Sha256Function, HashFunction};
192    use fr32::fr_into_bytes;
193    use merkletree::hash::Algorithm;
194    use rand::{Rng, SeedableRng};
195    use rand_xorshift::XorShiftRng;
196
197    use crate::TEST_SEED;
198
199    #[test]
200    fn test_bytes_into_boolean_vec() {
201        let mut cs = TestConstraintSystem::<Fr>::new();
202        let rng = &mut XorShiftRng::from_seed(TEST_SEED);
203
204        for i in 0..100 {
205            let data: Vec<u8> = (0..i + 10).map(|_| rng.gen()).collect();
206            let bools = {
207                let mut cs = cs.namespace(|| format!("round: {}", i));
208                bytes_into_boolean_vec(&mut cs, Some(data.as_slice()), 8)
209                    .expect("bytes into boolean vec failure")
210            };
211
212            let bytes_actual: Vec<u8> = bits_to_bytes(
213                bools
214                    .iter()
215                    .map(|b| b.get_value().expect("get_value failure"))
216                    .collect::<Vec<bool>>()
217                    .as_slice(),
218            );
219
220            assert_eq!(data, bytes_actual);
221        }
222    }
223
224    #[test]
225    fn test_bool_to_u8() {
226        assert_eq!(bool_to_u8(false, 2), 0b0000_0000);
227        assert_eq!(bool_to_u8(true, 0), 0b0000_0001);
228        assert_eq!(bool_to_u8(true, 1), 0b0000_0010);
229        assert_eq!(bool_to_u8(true, 7), 0b1000_0000);
230    }
231
232    #[test]
233    fn test_bits_into_bytes() {
234        assert_eq!(
235            bits_to_bytes(&[true, false, false, false, false, false, false, false]),
236            vec![1]
237        );
238        assert_eq!(
239            bits_to_bytes(&[true, true, true, true, true, true, true, true]),
240            vec![255]
241        );
242    }
243
244    #[test]
245    fn test_bytes_into_bits() {
246        assert_eq!(
247            bytes_into_bits(&[1u8]),
248            vec![true, false, false, false, false, false, false, false]
249        );
250
251        let rng = &mut XorShiftRng::from_seed(TEST_SEED);
252
253        for i in 10..100 {
254            let bytes: Vec<u8> = (0..i).map(|_| rng.gen()).collect();
255
256            let bits = bytes_into_bits(bytes.as_slice());
257            assert_eq!(bits_to_bytes(bits.as_slice()), bytes);
258        }
259    }
260
261    #[test]
262    fn test_reverse_bit_numbering() {
263        for _ in 0..100 {
264            let mut cs = TestConstraintSystem::<Fr>::new();
265            let rng = &mut XorShiftRng::from_seed(TEST_SEED);
266
267            let val_fr = Fr::random(rng);
268            let val_vec = fr_into_bytes(&val_fr);
269
270            let val_num = AllocatedNum::alloc(cs.namespace(|| "val_num"), || Ok(val_fr))
271                .expect("alloc failure");
272            let val_num_bits = val_num
273                .to_bits_le(cs.namespace(|| "val_bits"))
274                .expect("to_bits_le failure");
275
276            let bits =
277                bytes_into_boolean_vec_be(cs.namespace(|| "val_bits_2"), Some(&val_vec), 256)
278                    .expect("bytes_into_boolean_vec_be failure");
279
280            let val_num_reversed_bit_numbering = reverse_bit_numbering(val_num_bits);
281
282            let a_values: Vec<bool> = val_num_reversed_bit_numbering
283                .iter()
284                .map(|v| v.get_value().expect("get_value failure"))
285                .collect();
286
287            let b_values: Vec<bool> = bits
288                .iter()
289                .map(|v| v.get_value().expect("get_value failure"))
290                .collect();
291            assert_eq!(&a_values[..], &b_values[..]);
292        }
293    }
294
295    #[test]
296    fn hash_leaf_bits_circuit() {
297        let mut cs = TestConstraintSystem::<Fr>::new();
298        let mut rng = XorShiftRng::from_seed(TEST_SEED);
299
300        let left_fr = Fr::random(&mut rng);
301        let right_fr = Fr::random(&mut rng);
302        let left: Vec<u8> = fr_into_bytes(&left_fr);
303        let right: Vec<u8> = fr_into_bytes(&right_fr);
304        let height = 1;
305
306        let left_bits: Vec<Boolean> = {
307            let mut cs = cs.namespace(|| "left");
308            bytes_into_boolean_vec(&mut cs, Some(left.as_slice()), 256).expect("left bits failure")
309        };
310
311        let right_bits: Vec<Boolean> = {
312            let mut cs = cs.namespace(|| "right");
313            bytes_into_boolean_vec(&mut cs, Some(right.as_slice()), 256)
314                .expect("right bits failure")
315        };
316
317        let out = Sha256Function::hash_leaf_bits_circuit(
318            cs.namespace(|| "hash_leaf_circuit"),
319            &left_bits,
320            &right_bits,
321            height,
322        )
323        .expect("key derivation function failed");
324
325        assert!(cs.is_satisfied(), "constraints not satisfied");
326        assert_eq!(cs.num_constraints(), 45_387);
327
328        let expected: Fr = Sha256Function::default()
329            .node(left_fr.into(), right_fr.into(), height)
330            .into();
331
332        assert_eq!(
333            expected,
334            out.get_value().expect("get_value failure"),
335            "circuit and non circuit do not match"
336        );
337    }
338}
storage_proofs_core/util.rs

storage_proofs_core/
util.rs
