[protocol] FLIP: On-Chain randomness history for commit-reveal schemes

[tarakby]

This FLIP proposes a safe pattern to address transaction abortion after the random is revealed.

[dete]

Thanks for putting this FLIP together, @tarakby! Unlocking secure randomness for smart contract developers is super exciting!

Some suggestions:

1. It seems to me that the cost of storing 32 bytes for all blocks indefinitely may actually acceptable! It removes the need for devs to handle the (rare) edge case where the random seed for their use-case is more than two weeks in the past. Based on your ~20Mb estimate per week, it's ~1 GB per year. I think we can cope with that level of state growth today, and it's only going to be shrink relative to the total state space size as we go into the future.
2. I think "random beacon" is an accurate description of the block randomness, and will be more meaningful for most folks than "SoR". As such, I suggest the function should be RandomBeaconHistory.getBeaconValue(atBlockHeight: x). It should throw if x is greater than or equal to the current block height, or less than the block height at which random beacon history was recorded.
3. I would probably go so far as to make RandomBeaconHistory private to the Service Account, and then ensure we ship a contract on the Service Account which wraps it into something easily used by most devs. I'll include a first-draft of what I mean below.

Note: I didn't see any docs for the PRG object. Is that proposed or existing? My assumption below is that it's either new, or it can be modified to work with byte arrays instead of UInt64.

import PRG

resource SecureRandom {
  access(self) let initHeight: UInt64
  access(self) let prg: PRG
  access(self var fetchedRandomBeacon = false

  init() {
    let currentBlock = getCurrentBlock()

    initHeight = currentBlock.height
    prg = create PRG()

    prg.addEntropy(currentBlock.timeStamp.toBigEndianBytes())
    prg.addEntropy(currentBlock.id.toBigEndianBytes())
    prg.addEntropy(self.uuid.toBigEndianBytes())
  }

  access(all) fun addEntropy(_ entropyBytes: [UInt8) {
    prg.addEntroy(entropyBytes)
  }

  access(all) fun nextBytes(count: UInt64): [UInt8] {
    pre {
      getCurrentBlock().height > self.initHeight:
            "SecureRandom objects can't be used within the same block they are created to avoid reversion attacks."
    }
    if (!self.fetchedRandomBeacon) {
      prg.addEntropy(RandomBeaconHistory.getBeaconValue(atBlockHeight: self.initHeight))
    }

    return prg.nextBytes(count: count)
  }

  access(all) fun nextUInt64(): UInt64 {
    return UInt64.fromBigEndianBytes(self.nextBytes(count: 8))
  }

  // Returns a random value in the range min <= result < max
  access(all) fun rangedUInt64(min: UInt64, max: UInt64) {
    pre {
      min < max:
        "Max must be strictly greater than min."
    }

    let rangeLength = max - min
    let offset = self.nextUInt64() % rangeLength

    return min + offset
  }

  access(all) fun nextUInt32 ...
  access(all) fun nextUInt16 ...
  access(all) fun nextUInt8 ...

  access(all) fun nextInt64 ...
  access(all) fun nextInt32 ...
  access(all) fun nextInt16 ...
  access(all) fun nextInt8 ...

  access(all) fun nextBool(): Bool {
    let aByte = self.nextBytes(count: 1)
    return ((aByte[0] & 1) == 1)
}

[AlexHentschel]

In the code snippet Dete posted, I think we are missing the statement setting fetchedRandomBeacon to true. I think the access(all) function should read something like:

  access(all) fun nextBytes(count: UInt64): [UInt8] {
    pre {
      getCurrentBlock().height > self.initHeight:
            "SecureRandom objects can't be used within the same block they are created to avoid reversion attacks."
    }
    if (!self.fetchedRandomBeacon) {
      prg.addEntropy(RandomBeaconHistory.getBeaconValue(atBlockHeight: self.initHeight))
      self.fetchedRandomBeacon = true // ADDED THIS LINE
    }

    return prg.nextBytes(count: count)
  }

[AlexHentschel]

From my perspective:

• Tarak suggested function naming SoRHistory.getSoR(UInt64)
• Dete's criticism: too cryptic and not using terminology people are familiar with Dete's suggestion:
• RandomBeaconHistory.getBeaconValue(UInt64)
• Tarak's and my concern: inaccurate terminology (there is a established tech term, for the output of the random beacon: 'SourceOfRandomness'). I think it would really benefit clarity and precision of our work, if we used that term.

I think the following would be a good middle ground: RandomBeaconHistory.SourceOfRandomnessForBlock(UInt64)

Reasoning:

• the random beacon produces the SoR. Therefore, I feel RandomBeaconHistory is technically reasonably accurate to use as the first word. It will help devs with familiar terminology.
• non cryptic (no abbreviations)
• we use the technically correct term Source Of Randomness for the random beacon output. Lastly, I feel the terminology is also consistent with the whitepaper and code-base

[tarakby]

Thanks @dete for taking the time and providing a feedback.

I answer your suggestions to keep the discussion going and get other people's opinion:

1. This sounds reasonable, I'll update (https://github.com/onflow/flips/pull/123/commits/30a320184ca5341d6d9c3a407f528b380fc35c79)
2. I agree SoR isn't clear, it should be at least expanded into SourceOfRandomness. I also agree that RandomBeacon is a more common term, although it doesn't mean the exact same thing as source of randomness. My understanding is that "Random Beacon" is the sub-protocol generating randomness and its output is a "source of randomness". I believe the naming suggested by Alex addresses your concern while keeping the naming accurate RandomBeaconHistory.SourceOfRandomnessAtBlock(UInt64). Please let me know if it doesn't.

3. I'll comment on your suggestion in different points:

   • To answer your question about the PRG. No this FLIP did not provide a PRG implementation. It only provides a way to store previous block's sources, to make on-chain commit-reveal schemes possible (not possible without the proposed protocol update). Once this is unlocked, developers are able to implement any PRG they need, and can use the random sources as seeds for their PRGs. On this FLIP, I didn't want to tie developers to a single PRG instance. The FLIP implementation can propose one PRG implementation of course, but I thought it should be possible for developers to freely seed other PRGs of their choice.
   • To continue with my argument above, I think including the PRG into the SecureRandom resource does not allow users to choose their PRG freely. Making RandomBeaconHistory private may also restrict the ways to use the random sources. The FLIP aims to provide the missing tools for developers (past random seeds), and allow them to implement the rest of the on-chain logic.
   • SecureRandom: the main issue this FLIP wants to solve is the random output being revertible. It seems to me that the methods of SecureRandom (considered on their own) are still revertible, as in randoms can always be post-selected). My understanding is that the full commit-reveal design pattern is what makes randomness secure, and not a single resource. Specifically, the financial commitment step in a contract design, along with committing to a certain random (not known at the time of committing), is what makes post-selecting obsolete. A non-trusted user can always revert the transaction result, but they can't revert the financial commitment. It seems to me that the SecureRandom resource only commits to a certain random. I hope I understood your suggestion correctly and didn't miss an important point.

   I'm curious to know what other Cadence developers think of Dete's suggestion and my answer (specifially #3) cc @janezpodhostnik @sisyphusSmiling

[bluesign]

Can't we just store this on protocol state ? in block especially, Cadence has access to getBlock, then maybe even we can make SecureRandom as some native cadence function.

So I can write something like: var prng = getBlock(at: some height).SecureRandom(salt: someSalt)

or maybe better:

var prng = SecureRandom(height: someHeight, salt: someSalt) ( without any contract etc )

Example would be: (without any import needed )

fun randomCoin(atBlockHeight blockHeight: UInt64, salt: UInt64): UInt8 {
    let prg = SecureRandom(height: blockHeight, salt: salt) 
    let rand = prg.Uint64()
    return UInt8(rand & 1)
}

[AlexHentschel]

The following is subtle, but an important detail that hopefully addresses your question @bluesign:

• Nodes are not required to have block history beyond the start of the current epoch. While we could change this in theory, in practise this is non-negotiable (intractable engineering effort and undermining core value propositions of Flow for node operators). Implications:

  • The protocol currently does not guarantee availability of past Source of Randomness [SoR] (consider an EN joining and executing the first block of an Epoch). Therefore, transactions cannot assume that past SoRs can be made available via the FVM.

• Consider that we are running cadence code on the state of block X. If cadence can interact with the state of block X, the QC certifying block X is guaranteed to be known.

  However, the commit and reveal scheme generally interacts with commitments that were stored in ancestors of blocks X! For example:

  • in the state of block X, there is a commitment to run some gambling code.
  • The commitment was made by a transaction in bock Y = X - 100.
  • The gambling contract specifies that when making a commitment in block Y, the SoR of the future block Z = Y+1 is to be used.
  • Meaning: the code is running on the state of block X. While executing, the cadence code needs access to the SoR for block X - 99. While we guarantee the knowledge of the QC for X, we do not guarantee knowledge of QCs for X's ancestor (including X-99).

In other words, we need a solution to store a long history of SoRs for each block. The execution state is the best place to store this history in my opinion, because: (i) persists across sporks, (ii) it is already fork aware, meaning we can store a different SoR history for each fork out of the box.

[tarakby]

Thanks @AlexHentschel. @bluesign, Alex's answer is briefly explained in this FLIP section under notes (the first one). Nodes are not guaranteed to keep history of past block's data other than the current epoch, and hence the use of execution state (via a contract).

Regarding Cadence's getBlock, the block returned has minimal information, but not the consensus Qorum Certificate (which contains the source of randomness).

[bluesign]

thanks @AlexHentschel this is pretty good argument, I didn't know that we couldn't get previous spork block information within Cadence.

@tarakby yeah I was thinking exposing SoR there at first ( or just cadence exposing SecureRandom struct ) but I missed the part we don't have access to past block.

I still think that exposing PRG.createPRG(sourceOfRandomness, salt) is little dangerous, instead exposing some SecureRandom cadence type would be much easier for developers.

[tarakby]

I still think that exposing PRG.createPRG(sourceOfRandomness, salt) is little dangerous, instead exposing some SecureRandom cadence type would be much easier for developers.

I agree PRG.createPRG(sourceOfRandomness, salt) still requires developers to be careful and know what they are doing. IMO, the main added value of this FLIP is:

• without this FLIP, even a careful developer cannot work around revertible randomness by a non-trusted user.
• with this FLIP implemented, a careful developer is able to develop secure randomness.

In the current form, the FLIP doesn't prevent developers from making mistakes unfortunately, but it makes secure randomness implementable (which is already a good progress). If we can update this FLIP to also prevent misuses, that would be even better! suggestions are welcome! Dete's suggested a SecureRandom resource above, but randomness seems revertible to me (or I completely missed the idea).

[bluesign]

Dete's suggested a SecureRandom resource above, but randomness seems revertible to me (or I completely missed the idea).

It is creating the resource, but value you can get on next block. ( so technically you cannot know the result yet in the same transaction )

[janezpodhostnik]

I think including the PRG into the SecureRandom resource does not allow users to choose their PRG freely. Making RandomBeaconHistory private may also restrict the ways to use the random sources.

I agree. I thing making RandomBeaconHistory as concise and minimal as possible would be the best as it can then serve as a reusable building block for the community to build their own tools on top of, if they are not sattisfied with the default PRG that will be provided. I also don't see an issue with making it public.

[tarakby]

Thank you for all the comments!

The FLIP is taking the following direction so far:

• It is about protocol changes (FVM update - system transaction update) that make a commit-reveal scheme for safe randomness possible, by recording all the random beacon history.
• The protocol data history above is stored in the execution state using a new RandomBeaconHistory contract. The contract is public and minimal, offering simple queries of random sources per block height.
• This FLIP is not tied to a precise Cadence implementations of safe randomness. A simple example is given, but developers are free to use the history contract as a building block for different designs. Specific Cadence designs can be presented in future FLIPs if needed (the current proposal is a protocol FLIP rather than a Cadence FLIP).
• A Cadence implementation of one PRG instance (algorithm and interface) will be provided as part of this FLIP implementation, but is not tied to the history contract. The history contract can be used with other PRGs or other forms of processing.

Please feel free to add further comments or concerns about the above.

[tarakby]

There seems to be no concerns about the current FLIP state. I will go ahead and update the status to approved unless there are new objections.