GitHub Logo HIP-351: Add UtilPrngTransaction

Author Jaewook Kim, Leemon Baird
Discussions-To https://github.com/hashgraph/hedera-improvement-proposal/discussions/350
Status Final
Needs Council Approval Yes
Review period ends Tue, 17 May 2022 07:00:00 +0000
Type Standards Track
Category Service
Created 2022-02-05
Updated 2023-05-22
Release v0.28.0

Abstract

Many decentralized applications require pseudorandom number generation. I propose a new UtilPrngTransaction and corresponding Solidity precompiled contracts to generate pseuodrandom numbers for use by both smart contracts and users.

Motivation

Pseudorandom numbers are widely used in applications such as Games, and Lotteries, and to randomly select one of multiple NFTs mined in an NFT project and transmit it to the NFT buyer.

For example, in the case of Ethereum, a smart contract can use the blockhash or timestamp as a “random” number, or use the Chainlink VRF random number oracle.

If a user or application creates random numbers, it is also difficult to prove to a third party that they were generated in a way that the user or application couldn’t influence or control.

Therefore, I propose a new Transaction and precompiles that generates a pseudorandom number.

Rationale

User stories

This can be used in the developer’s centralized application by submitting a HAPI UtilPrngTransaction.

In a function such as NFTTransfer, the user could use the number as a serial number, and a third party could later verify with a mirror node that the number was truly generated by the Hedera network, without being influenced by the user.

A smart contract could use the precompiled contract to obtain pseudorandom numbers for applications such as games that need them.

Specification

When the UtilPrngTransaction executes, its record will contain the 384-bit array of pseudorandom bytes. The transaction itself will have a single optional parameter, int32 range. If the parameter is given and is positive, then the record will contain a 32-bit pseudorandom integer r, where 0 <= r < range instead of containing the 384 pseudorandom bits.

There will also be one Solidity precompiled contract to return a 256-bit pseudorandom seed. A pseudorandom 32-bit integer r, where 0 <= r < range can be generated from the seed by calculating integer value of the first 32 bits of the seed % range

If a smart contract needs more than 256 pseudorandom bits, then it can use these 256 bits as the seed of a cryptographically secure pseudorandom number generator (CSPRNG). That CSPRNG could be written in Solidity. A future HIP might propose a particular CSPRNG to be provided as another precompile. But that is outside the scope of this HIP.

If the nth transaction in consensus order is either the UtilPrngTransaction or a call to a smart contract that will use the precompile, then it generates the pseudorandom number in the following way.

The Hedera network currently creates a record giving the results and consensus timestamp for each transaction. It also maintains a running hash of these records, where each record is concatenated with the current running hash, and the hash of that pair becomes the new running hash.

When the nth transaction needs a pseudorandom number, it is given the running hash of all records up to and including the record for transaction n-3. If it needs 384 bits, then it uses the entire hash. If it needs 256 bits, it uses the first 256 bits of the hash. If it needs a random number r that is in the range 0 <= r < range, then it lets x be the first 32 bits of the hash (interpreted as a signed integer), and generates the pseudorandom number in Java as:

r = (range * (long) x) >>> 32

This is used instead of using x % range because multiplication is faster than division (or remainder) on most processors.

The choice of using the hash up to transaction n-3 rather than n-1 is to ensure the transactions can be processed quickly. Because the thread calculating the hash will have more time to complete it before it is needed. The use of n-3 rather than n-1000000 is to make it hard to predict the pseudorandom number in advance.

Backwards Compatibility

There are no backwards compatibility issues. This is a new transaction.

Security Implications

The pseudorandom number generator proposed here is not cryptographically secure. It may be secure enough for practical applications, but the user should carefully consider whether it is secure enough for any given purpose. The following describes some (but not all) of the potential limitations.

When generating random numbers in a given range, if that range is not a power of 2, then the numbers will not have perfectly equal probability. For example, to simulate a 6-sided die, let range=6, then the outcomes of 0, 1, 2, or 3 each have a probability of 0.1666666667, while the outcomes of 4 or 5 each have a probability of 0.1666666665. These probabilities are close, but not equal. But simulating an 8-sided die or a 2-sided coin flip does give equal probabilities for each side, because 8 and 2 are both powers of 2.

It is likely that attackers will know the random number before the user or smart contract who requested it. They may know it several seconds in advance, and might act on that knowledge in some way. So the user should not rely on being the first to know it.

If Alice gives the number to Bob and claims that it came from a UtilPrngTransaction, she could be lying, and could have created the number herself. To prevent that, Bob could ask exactly which transaction it came from, and could then check that by querying multiple mirror nodes. However, Alice could have actually submitted multiple transactions requesting random numbers, and then revealed to Bob only the single number that was most advantageous to herself. In that way, Alice would be able to influence the result. Bob could try to mitigate that by querying for all transactions submitted by Alice recently. Though Alice could avoid that by making multiple requests, each paid for by a different account, and then revealing to Bob only the account that gave the number she preferred. The best mitigation of that attack is for Alice and Bob to first agree on which account will submit the request, and roughly when it will be submitted. Then Alice can submit it. Then Bob can query multiple mirror nodes to discover all transactions from that account during that period.

It appears to be difficult for a malicious node in the network to influence the random number. To do so, it would need to influence the order of transactions, their consensus timestamps, and the results of each transaction. All of that appears difficult to do, given the nature of the hashgraph algorithm itself. Timestamps come from the median of many votes. And the order comes from those timestamps. And an attacker would have difficulty predicting ahead of time all of the transactions that will be submitted to the network between when a UtilPrngTransaction is submitted and when it reaches consensus. It would be harder for a Hedera node to influence this hash than for a miner in a Proof of Work blockchain to influence the nonce when they mine a block. For these reasons, it appears to be difficult for them to influence it. But cannot be mathematically ruled out.

It appears to be even more difficult for a user submitting a UtilPrngTransaction to predict what the number will be. Because there is no way to predict what other transactions will come before it in consensus order, what their timestamps will be, and what their records will show as the result of executing them. So predicting the random number would appear to be difficult. But cannot be mathematically ruled out.

It is also theoretically possible that a flaw in SHA-2 will be found such that every SHA-384 hash has some property that is predictable in advance. For example, there might be some function of its bits that always returns a 0. No such patterns are currently known, and there is currently no reason to expect such patterns to be discovered. But it cannot be mathematically ruled out.

Reference Implementation

The solidity precompiled contract is to reside at address 0x169 and implement the below interface,

interface IPrngSystemContract {
    // Generates a 256-bit pseudorandom seed using the first 256-bits of running hash of n-3 transaction record.
    // Users can generate a pseudorandom number in a specified range using the seed by (integer value of seed % range)
    function getPseudorandomSeed() external returns (bytes32);
}

Smart contracts can use a new system contract to generate pseudorandom numbers. A typical use case that implements this interface might be,

import "./IPrngSystemContract.sol";

contract PrngSystemContract {
    address constant PRECOMPILE_ADDRESS = address(0x169);

    function getPseudorandomSeed() external returns (bytes32 randomBytes) {
        (bool success, bytes memory result) = PRECOMPILE_ADDRESS.call(
            abi.encodeWithSelector(IPrngSystemContract.getPseudorandomSeed.selector));
        require(success);
        randomBytes = abi.decode(result, (bytes32));
    }
    
    /**
     * Returns a pseudorandom number in the range [lo, hi) using the seed generated from "getPseudorandomSeed"
     */
    function getPseudorandomNumber(uint32 lo, uint32 hi) external returns (uint32) {
        (bool success, bytes memory result) = PRECOMPILE_ADDRESS.call(
            abi.encodeWithSelector(IPrngSystemContract.getPseudorandomSeed.selector));
        require(success);
        uint32 choice;
        assembly {
            choice := mload(add(result, 0x20))
        }
        return lo + (choice % (hi - lo));
    }
}

How to Teach This

Rejected Ideas

Open Issues

No blocking issues are known at this time.

References

Copyright/license

This document is licensed under the Apache License, Version 2.0 – see LICENSE or (https://www.apache.org/licenses/LICENSE-2.0)

Citation

Please cite this document as: