1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// Copyright 2024 Aleo Network Foundation
// This file is part of the snarkVM library.

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at:

// http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use super::*;

impl<E: Environment> FromBits for Field<E> {
    /// Initializes a new field from a list of **little-endian** bits.
    ///   - If `bits_le` is longer than `E::Field::size_in_bits()`, the excess bits are enforced to be `0`s.
    ///   - If `bits_le` is shorter than `E::Field::size_in_bits()`, it is padded with `0`s up to field size.
    fn from_bits_le(bits_le: &[bool]) -> Result<Self> {
        // Retrieve the data and field size.
        let size_in_data_bits = Field::<E>::size_in_data_bits();
        let size_in_bits = Field::<E>::size_in_bits();

        // Ensure the list of booleans is within the allowed size in bits.
        let num_bits = bits_le.len();
        if num_bits > size_in_bits {
            // Check if all excess bits are zero.
            let should_be_zero = bits_le[size_in_bits..].iter().fold(false, |acc, bit| acc | bit);
            // Ensure `should_be_zero` is `false`.
            ensure!(!should_be_zero, "The excess bits are not zero.");
        }

        // If `num_bits` is greater than `size_in_data_bits`, check it is less than `Field::MODULUS`.
        if num_bits > size_in_data_bits {
            // Recover the field as a `BigInteger` for comparison.
            // As `bits_le[size_in_bits..]` is guaranteed to be zero from the above logic,
            // and `bits_le` is greater than `size_in_data_bits`, it is safe to truncate `bits_le` to `size_in_bits`.
            let field = E::BigInteger::from_bits_le(&bits_le[..size_in_bits])?;

            // Ensure the field is less than `Field::MODULUS`.
            ensure!(field < E::Field::modulus(), "The field is greater than or equal to the modulus.");

            // Return the field.
            Ok(Field { field: E::Field::from_bigint(field).ok_or_else(|| anyhow!("Invalid field from bits"))? })
        } else {
            // Construct the sanitized list of bits padded with `false`
            let mut sanitized_bits = vec![false; size_in_bits];
            // Note: This is safe, because we just checked that the length of bits isn't bigger
            // than `size_in_data_bits` which is equal to `size_in_bits - 1`.
            sanitized_bits[..num_bits].copy_from_slice(bits_le);

            // Recover the native field.
            let field = E::Field::from_bigint(E::BigInteger::from_bits_le(&sanitized_bits)?)
                .ok_or_else(|| anyhow!("Invalid field from bits"))?;

            // Return the field.
            Ok(Field { field })
        }
    }

    /// Initializes a new field from a list of big-endian bits *without* leading zeros.
    fn from_bits_be(bits_be: &[bool]) -> Result<Self> {
        // Reverse the given bits from big-endian into little-endian.
        // Note: This is safe as the bit representation is consistent (there are no leading zeros).
        let mut bits_le = bits_be.to_vec();
        bits_le.reverse();

        Self::from_bits_le(&bits_le)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use snarkvm_console_network_environment::Console;

    type CurrentEnvironment = Console;

    const ITERATIONS: usize = 100;

    fn check_from_bits_le() -> Result<()> {
        let mut rng = TestRng::default();

        for i in 0..ITERATIONS {
            // Sample a random element.
            let expected: Field<CurrentEnvironment> = Uniform::rand(&mut rng);
            let given_bits = expected.to_bits_le();
            assert_eq!(Field::<CurrentEnvironment>::size_in_bits(), given_bits.len());

            let candidate = Field::<CurrentEnvironment>::from_bits_le(&given_bits)?;
            assert_eq!(expected, candidate);

            // Add excess zero bits.
            let candidate = [given_bits, vec![false; i]].concat();

            let candidate = Field::<CurrentEnvironment>::from_bits_le(&candidate)?;
            assert_eq!(expected, candidate);
            assert_eq!(Field::<CurrentEnvironment>::size_in_bits(), candidate.to_bits_le().len());
        }
        Ok(())
    }

    fn check_from_bits_be() -> Result<()> {
        let mut rng = TestRng::default();

        for i in 0..ITERATIONS {
            // Sample a random element.
            let expected: Field<CurrentEnvironment> = Uniform::rand(&mut rng);
            let given_bits = expected.to_bits_be();
            assert_eq!(Field::<CurrentEnvironment>::size_in_bits(), given_bits.len());

            let candidate = Field::<CurrentEnvironment>::from_bits_be(&given_bits)?;
            assert_eq!(expected, candidate);

            // Add excess zero bits.
            let candidate = [vec![false; i], given_bits].concat();

            let candidate = Field::<CurrentEnvironment>::from_bits_be(&candidate)?;
            assert_eq!(expected, candidate);
            assert_eq!(Field::<CurrentEnvironment>::size_in_bits(), candidate.to_bits_be().len());
        }
        Ok(())
    }

    #[test]
    fn test_from_bits_le() -> Result<()> {
        check_from_bits_le()
    }

    #[test]
    fn test_from_bits_be() -> Result<()> {
        check_from_bits_be()
    }
}