Smart Contract
RandomBeaconHistory
A.e467b9dd11fa00df.RandomBeaconHistory
1/// RandomBeaconHistory (FLIP 123)
2///
3/// This contract stores the history of random sources generated by the Flow network. The defined Heartbeat resource is
4/// updated by the Flow Service Account at the end of every block with that block's source of randomness.
5///
6/// While the source values are safely generated by the Random Beacon (non-predictable, unbiasable, verifiable) and
7/// transmitted into the execution environment via the committing transaction, using the raw values from this contract
8/// does not guarantee non-revertible randomness. The Hearbeat is intended to be used in conjunction with a commit-reveal
9/// mechanism to provide an onchain source of non-revertible randomness.
10/// It is also recommended to use the source values with a pseudo-random number
11/// generator (PRNG) to generate an arbitrary-long sequence of random values.
12///
13/// For usage of randomness where result abortion is not an issue, it is recommended
14/// to use the Cadence built-in function `revertibleRandom`, which is also based on
15/// the safe Random Beacon.
16///
17/// Read the full FLIP here: https://github.com/onflow/flips/pull/123
18///
19access(all) contract RandomBeaconHistory {
20
21 /// The height at which the first source of randomness was recorded
22 access(contract) var lowestHeight: UInt64?
23 /// Sequence of random sources recorded by the Heartbeat, stored as an array over a mapping to reduce storage
24 access(contract) let randomSourceHistory: [[UInt8]]
25
26 /// The path of the Heartbeat resource in the deployment account
27 access(all) let HeartbeatStoragePath: StoragePath
28
29 // Event emitted when missing SoRs from past heartbeats are detected and will be backfilled:
30 // - `blockHeight` is the height where the gap is detected
31 // - `gapStartHeight` is the height of the first missing entry detected
32 access(all) event RandomHistoryMissing(blockHeight: UInt64, gapStartHeight: UInt64)
33
34 // Event emitted when missing SoRs are backfilled on the current heartbeat:
35 // - `blockHeight` is the height where the backfill happened, it also defines the SoR used to backfill
36 // - `gapStartHeight` is the height of the first backfilled entry
37 // - `count` is the number of backfilled entries
38 // Note that in very rare cases, the backfilled gap may not be contiguous. This event does not
39 // fully define the backfilled entries in this case.
40 access(all) event RandomHistoryBackfilled(blockHeight: UInt64, gapStartHeight: UInt64, count: UInt64)
41
42 /* --- Hearbeat --- */
43 //
44 /// The Heartbeat resource containing each block's source of randomness in sequence
45 ///
46 access(all) resource Heartbeat {
47
48 /// Callable by owner of the Heartbeat resource, Flow Service Account, records the provided random source
49 ///
50 /// @param randomSourceHistory The random source to record
51 ///
52 /// The Flow protocol makes sure to call this function once per block as a system call. The transaction
53 /// comes at the end of each block so that the current block's entry becomes available only in the child
54 /// block.
55 ///
56 access(all) fun heartbeat(randomSourceHistory: [UInt8]) {
57
58 assert(
59 // random source must be at least 128 bits
60 randomSourceHistory.length >= 128 / 8,
61 message: "Random source must be at least 128 bits"
62 )
63
64 let currentBlockHeight = getCurrentBlock().height
65 // init lowestBlockHeight if it is not set yet
66 if RandomBeaconHistory.lowestHeight == nil {
67 RandomBeaconHistory.lowestHeight = currentBlockHeight
68 }
69 var maybeBackfiller = RandomBeaconHistory.borrowBackfiller()
70 // Create & save Backfiller if it is not saved yet
71 if maybeBackfiller == nil {
72 RandomBeaconHistory.account.storage.save(<-create Backfiller(), to: /storage/randomBeaconHistoryBackfiller)
73 maybeBackfiller = RandomBeaconHistory.borrowBackfiller()
74 }
75 let backfiller = maybeBackfiller ?? panic("Problem borrowing backfiller")
76
77 // check for any existing gap and backfill using the input random source if needed.
78 backfiller.backfill(randomSource: randomSourceHistory)
79
80 // we are now at the correct index to record the source of randomness
81 // created by the protocol for the current block
82 RandomBeaconHistory.randomSourceHistory.append(randomSourceHistory)
83 }
84 }
85
86 /* --- Backfiller --- */
87 //
88 /// A recovery mechanism designed to backfill missed sources of randomness in the event of a missed commitment due
89 /// to a system transaction failure.
90 ///
91 access(all) resource Backfiller {
92 /// Start index of the first gap in the `randomSourceHistory` array where random sources were not recorded,
93 /// because of a heartbeat failure.
94 /// There may be non contiguous gaps in the history, `gapStartIndex` is the start index of the lowest-height
95 /// gap.
96 /// If no gaps exist, `gapStartIndex` is equal to the `randomSourceHistory` array length.
97 access(contract) var gapStartIndex: UInt64
98 /// BackFilling is limited to a maximum number of entries per call to limit the computation cost.
99 /// This means a large gap may need a few calls to get fully backfilled.
100 access(contract) var maxEntriesPerCall: UInt64
101
102 init() {
103 self.gapStartIndex = UInt64(RandomBeaconHistory.randomSourceHistory.length)
104 self.maxEntriesPerCall = 100
105 }
106
107 access(all) view fun getMaxEntriesPerCall() : UInt64 {
108 return self.maxEntriesPerCall
109 }
110
111 access(all) fun setMaxEntriesPerCall(max: UInt64) {
112 assert(
113 max > 0,
114 message: "the maximum entry per call must be strictly positive"
115 )
116 self.maxEntriesPerCall = max
117 }
118
119 /// Finds the correct index to fill with the new random source. If a gap is detected, emits the
120 /// RandomHistoryMissing event.
121 ///
122 access(contract) view fun findGapAndReturnCorrectIndex(): UInt64 {
123
124 let currentBlockHeight = getCurrentBlock().height
125 // correct index to fill with the new random source
126 // so that eventually randomSourceHistory[correctIndex] = inputRandom
127 let lowestHeight = RandomBeaconHistory.lowestHeight!
128 let correctIndex = currentBlockHeight - lowestHeight
129
130 // if a new gap is detected, emit an event
131 var arrayLength = UInt64(RandomBeaconHistory.randomSourceHistory.length)
132 if correctIndex > arrayLength {
133 let gapStartHeight = lowestHeight + arrayLength
134 emit RandomHistoryMissing(blockHeight: currentBlockHeight, gapStartHeight: gapStartHeight)
135 }
136 return correctIndex
137 }
138
139 /// Backfills possible empty entries (gaps) in the history array starting from the stored `gapStartIndex`,
140 /// using `randomSource` as a seed for all entries.
141 /// If there are no gaps, `gapStartIndex` is just updated to `RandomBeaconHistory`'s length.
142 //
143 /// When backfilling, all entries use the same entropy. Each entry is extracted from `randomSource` using
144 /// successive hashing. This makes sure the entries are all distinct although they provide
145 /// the same entropy.
146 //
147 /// gaps only occur in the rare event of a system transaction failure. In this case, entries are still
148 /// filled using a source not known at the time of block execution, which guarantees unpredicatability.
149 access(contract) fun backfill(randomSource: [UInt8]) {
150
151 let correctIndex = self.findGapAndReturnCorrectIndex()
152 var arrayLength = UInt64(RandomBeaconHistory.randomSourceHistory.length)
153 // optional optimization for the happy common path: if no gaps are detected,
154 // backfilling isn't needed, return early
155 if correctIndex == self.gapStartIndex {
156 self.gapStartIndex = arrayLength + 1
157 return
158 }
159
160 // If a new gap is detected in the current transaction, fill the gap with empty entries.
161 // This happens in the rare case where a new gap occurs because of a system transaction failure.
162 while correctIndex > UInt64(RandomBeaconHistory.randomSourceHistory.length) {
163 RandomBeaconHistory.randomSourceHistory.append([])
164 }
165
166 arrayLength = UInt64(RandomBeaconHistory.randomSourceHistory.length)
167 var newEntry = randomSource
168 var index = self.gapStartIndex
169 var count = 0 as UInt64
170 while count < self.maxEntriesPerCall {
171 // move to the next empty entry
172 while index < arrayLength && RandomBeaconHistory.randomSourceHistory[index].length > 0 {
173 index = index + 1
174 }
175 // if we reach the end of the array then all existing gaps got filled
176 if index == arrayLength {
177 break
178 }
179 // back fill the empty entry
180 // It is guaranteed that sha3 output (256 bits) is larger than the minimum
181 // required size of an SoR (128 bits)
182 newEntry = HashAlgorithm.SHA3_256.hash(newEntry)
183 RandomBeaconHistory.randomSourceHistory[index] = newEntry
184 index = index + 1
185 count = count + 1
186 }
187
188 // emit an event about backfilled entries
189 if count > 0 {
190 let gapStartHeight = RandomBeaconHistory.lowestHeight! + self.gapStartIndex
191 emit RandomHistoryBackfilled(
192 blockHeight: getCurrentBlock().height,
193 gapStartHeight: gapStartHeight,
194 count: count
195 )
196 }
197
198 // no more backfilling is possible but we need to update `gapStartIndex`
199 // to:
200 // - the next empty index if gaps still exist
201 // - the length of the array at the end of the transaction if there are no gaps
202 while index < arrayLength && RandomBeaconHistory.randomSourceHistory[index].length > 0 {
203 index = index + 1
204 }
205 if index == arrayLength {
206 index = index + 1 // take into account the upcoming append of the SoR at the correct index
207 }
208 self.gapStartIndex = index
209 }
210 }
211
212 /* --- RandomSourceHistory --- */
213 //
214 /// Represents a random source value for a given block height
215 ///
216 access(all) struct RandomSource {
217 access(all) let blockHeight: UInt64
218 access(all) let value: [UInt8]
219
220 init(blockHeight: UInt64, value: [UInt8]) {
221 self.blockHeight = blockHeight
222 self.value = value
223 }
224 }
225
226 /* --- RandomSourceHistoryPage --- */
227 //
228 /// Contains RandomSource values ordered chronologically according to associated block height
229 ///
230 access(all) struct RandomSourceHistoryPage {
231 access(all) let page: UInt64
232 access(all) let perPage: UInt64
233 access(all) let totalLength: UInt64
234 access(all) let values: [RandomSource]
235
236 view init(page: UInt64, perPage: UInt64, totalLength: UInt64, values: [RandomSource]) {
237 self.page = page
238 self.perPage = perPage
239 self.totalLength = totalLength
240 self.values = values
241 }
242 }
243
244 /* --- Contract Methods --- */
245 //
246 /// Getter for the source of randomness at a given block height. Panics if the requested block height either
247 /// precedes or exceeds the recorded history. Note that a source of randomness for block n will not be accessible
248 /// until block n+1.
249 ///
250 /// @param atBlockHeight The block height at which to retrieve the source of randomness
251 ///
252 /// @return The source of randomness at the given block height as RandomSource struct
253 ///
254 access(all) fun sourceOfRandomness(atBlockHeight blockHeight: UInt64): RandomSource {
255 pre {
256 self.lowestHeight != nil: "History has not yet been initialized"
257 blockHeight >= self.lowestHeight!: "Requested block height precedes recorded history"
258 blockHeight < getCurrentBlock().height: "Source of randomness not yet recorded"
259 }
260 let index = blockHeight - self.lowestHeight!
261 assert(
262 index >= 0,
263 message: "Problem finding random source history index"
264 )
265 assert(
266 index < UInt64(self.randomSourceHistory.length) && self.randomSourceHistory[index].length > 0,
267 message: "Source of randomness is currently not available but will be available soon"
268 )
269 return RandomSource(blockHeight: blockHeight, value: self.randomSourceHistory[index])
270 }
271
272 /// Retrieves a page from the history of random sources recorded so far, ordered chronologically
273 ///
274 /// @param page: The page number to retrieve, 0-indexed
275 /// @param perPage: The number of random sources to include per page
276 ///
277 /// @return A RandomSourceHistoryPage containing RandomSource values in choronological order according to
278 /// associated block height
279 ///
280 access(all) fun getRandomSourceHistoryPage(_ page: UInt64, perPage: UInt64): RandomSourceHistoryPage {
281 pre {
282 self.lowestHeight != nil: "History has not yet been initialized"
283 }
284 let values: [RandomSource] = []
285 let totalLength = UInt64(self.randomSourceHistory.length)
286
287 var startIndex = page * perPage
288 if startIndex > totalLength {
289 startIndex = totalLength
290 }
291 var endIndex = startIndex + perPage
292 if endIndex > totalLength {
293 endIndex = totalLength
294 }
295
296 // Return empty page if request exceeds last page
297 if startIndex == endIndex {
298 return RandomSourceHistoryPage(page: page, perPage: perPage, totalLength: totalLength, values: values)
299 }
300
301 // Iterate over history and construct page RandomSource values
302 let lowestHeight = self.lowestHeight!
303 for i, value in self.randomSourceHistory.slice(from: Int(startIndex), upTo: Int(endIndex)) {
304 assert(
305 value.length > 0,
306 message: "Source of randomness is currently not available but will be available soon"
307 )
308 values.append(
309 RandomSource(
310 blockHeight: lowestHeight + startIndex + UInt64(i),
311 value: value
312 )
313 )
314 }
315
316 return RandomSourceHistoryPage(
317 page: page,
318 perPage: perPage,
319 totalLength: totalLength,
320 values: values
321 )
322 }
323
324 /// Getter for the block height at which the first source of randomness was recorded
325 ///
326 /// @return The block height at which the first source of randomness was recorded
327 ///
328 access(all) view fun getLowestHeight(): UInt64 {
329 return self.lowestHeight ?? panic("History has not yet been initialized")
330 }
331
332 /// Getter for the contract's Backfiller resource
333 access(contract) fun borrowBackfiller(): &Backfiller? {
334 return self.account.storage.borrow<&Backfiller>(from: /storage/randomBeaconHistoryBackfiller)
335 }
336
337 init() {
338 self.lowestHeight = nil
339 self.randomSourceHistory = []
340 self.HeartbeatStoragePath = /storage/FlowRandomBeaconHistoryHeartbeat
341
342 self.account.storage.save(<-create Heartbeat(), to: self.HeartbeatStoragePath)
343 }
344}
345