Xorshift128plus

1import Crypto
2
3/// Defines a xorsift128+ pseudo random generator (PRG) struct used to generate random numbers given some
4/// sourceOfRandomness and salt.
5///
6/// See FLIP 123 for more details: https://github.com/onflow/flips/blob/main/protocol/20230728-commit-reveal.md
7/// And the onflow/random-coin-toss repo for implementation context: https://github.com/onflow/random-coin-toss
8///
9access(all) contract Xorshift128plus {
10
11    /// While not limited to 128 bits of state, this PRG is largely informed by xorshift128+
12    ///
13    access(all) struct PRG {
14
15        // The states below are of type Word64 (instead of UInt64) to prevent overflow/underflow as state evolves
16        //
17        access(all) var state0: Word64
18        access(all) var state1: Word64
19
20        /// Initializer for PRG struct
21        ///
22        /// @param sourceOfRandomness: The entropy bytes used to seed the PRG. It is recommended to use at least 16
23        /// bytes of entropy.
24        /// @param salt: The bytes used to salt the source of randomness
25        ///
26        init(sourceOfRandomness: [UInt8], salt: [UInt8]) {
27            pre {
28                sourceOfRandomness.length >= 16:
29                "Provided entropy lengh=".concat(sourceOfRandomness.length.toString())
30                .concat(" - at least 16 bytes of entropy should be used when initializing the PRG")
31            }
32
33            let tmp: [UInt8] = sourceOfRandomness.concat(salt)
34            // Hash is 32 bytes
35            let hash: [UInt8] = Crypto.hash(tmp, algorithm: HashAlgorithm.SHA3_256)
36            // Reduce the seed to 16 bytes
37            let seed: [UInt8] = hash.slice(from: 0, upTo: 16)
38
39            // Convert the seed bytes to two Word64 values for state initialization
40            let segment0: Word64 = Xorshift128plus._bigEndianBytesToWord64(bytes: seed, start: 0)
41            let segment1: Word64 = Xorshift128plus._bigEndianBytesToWord64(bytes: seed, start: 8)
42
43            // Ensure the initial state is non-zero
44            assert(
45                segment0 != 0 || segment1 != 0,
46                message: "PRG initial state is 0 - must be initialized as non-zero"
47            )
48            
49            self.state0 = segment0
50            self.state1 = segment1
51        }
52
53        /// Advances the PRG state and generates the next UInt64 value
54        /// See https://arxiv.org/pdf/1404.0390.pdf for implementation details and reasoning for triplet selection.
55        /// Note that state only advances when this function is called from a transaction. Calls from within a script
56        /// will not advance state and will return the same value.
57        ///
58        /// @return The next UInt64 value
59        ///
60        access(all) fun nextUInt64(): UInt64 {
61            var a: Word64 = self.state0
62            let b: Word64 = self.state1
63
64            self.state0 = b
65            a = a ^ (a << 23) // a
66            a = a ^ (a >> 17) // b
67            a = a ^ b ^ (b >> 26) // c
68            self.state1 = a
69
70            let randUInt64: UInt64 = UInt64(Word64(a) + Word64(b))
71            return randUInt64
72        }
73
74        /// Advances the PRG state and generates the next UInt256 value by concatenating 4 UInt64 values
75        ///
76        /// @return The next UInt256 value
77        ///
78        access(all)
79        fun nextUInt256(): UInt256 {
80            var res = UInt256(self.nextUInt64())
81            res = res | UInt256(self.nextUInt64()) << 64
82            res = res | UInt256(self.nextUInt64()) << 128
83            res = res | UInt256(self.nextUInt64()) << 192
84
85            return res
86        }
87    }
88
89    /// Helper function to convert an array of big endian bytes to Word64
90    ///
91    /// @param bytes: The bytes to convert
92    /// @param start: The index of the first byte to convert
93    ///
94    /// @return The Word64 value
95    ///
96    access(contract) fun _bigEndianBytesToWord64(bytes: [UInt8], start: Int): Word64 {
97        pre {
98            start + 8 <= bytes.length:
99            "Defined start=".concat(start.toString())
100            .concat(" - at least 8 bytes from the start are required for conversion")
101        }
102        var value: UInt64 = 0
103        var i: Int = 0
104        while i < 8 {
105            value = value << 8 | UInt64(bytes[start + i])
106            i = i + 1
107        }
108        return Word64(value)
109    }
110}
111