Photo by Florian Olivo on Unsplash

Implement a Pseudo-Random Number Generator in 26 bytes smart contract

I've been following Decentralized Random Number Generator (DRNG) topic since 2015. It's a long and joyfully journey since I have time at the R&D department to research and get involved in development. Now, it becomes a force of habit to read the new papers and see how people prove their approach.

I've done some experiments with Ethereum Virtual Machine Opcode recently and an idea kicked in, how to write a minimal smart contract that performs Pseudo-Random Number Generator (PRNG). The idea is pretty simple, If you're using a hash function over a static value in n times you will receive different results since its collision resistance property. You might have some more detail here, http://www.ijcee.org/papers/439-JE503.pdf. They proved and passed the given static test by NIST.

I propose a deadly simple idea, where we maintain an immortalvalue by performing a hash on a combination of previous immortal and 32nd older block hash.

Immortal := keccak256(Immortal XOR blockhash(block.number - 32))

What is the point here?

In the idea from above apparently, the result is predictable since the algorithm and inputs are publishing on the blockchain. Anyone could able to perform off-chain computation. The thing is they can't predict how many times the other smart contract would trigger this contract. It made the cost to precalculate overwhelming transaction's value.

To actually manipulate the result miner would able to perform mine selected transactions by a given order but in the exchange, they need to risk their coinbase reward.

In case the adversary isn't a miner, they would able to have an advantage by creating a bunch of transactions by sequence with the highest gasPrice to make sure that they can occupy a range of values.

How could this proposal help?

The algorithm is safe and acceptable for a wide range of PRNG applications and situations where the cost to manipulate outweigh the transaction value.

We could use the PRNG as an additional salt to improve the result which was provided by the oracle or commit scheme. Oracle and commit scheme work as a black box on blockchain to maintain unpredictable property of randomness meanwhile PRNG improve trustworthiness.

Randomness := RPNGResult XOR OracleResult

Implementation

EVM is quite a simple virtual machine, it has a stack with 1024 in the depth. Of course, it has memory and storage. The number of opcodes isn’t too much.

In the attempt to write a pure opcode smart contract, I wrote my own assembler to compile from assembly to EVM opcode.

Here is a file that contained the list of opcodes:

chiro-hiro/thedivine

We define following this guideline:

Ethereum Virtual Machine Opcodes

My assembler:

Implement:

; EVM Assembly The Divine by Chiro Hiro <chiro8x@gmail.com>
PUSH1 0x20
RETURNDATASIZE
CALLER
ORIGIN
XOR
PUSH1 0x0a
JUMPI
REVERT
JUMPDEST
DUP2
DUP2
DUP1
SLOAD
DUP3
NUMBER
SUB
BLOCKHASH
XOR
DUP2
MSTORE
SHA3
DUP2
SSTORE
RETURN

• PUSH1 0x20 push 0x20 to the top of the stack
• RETURNDATASIZE push 0x00 to stack, because we didn’t perform any call then its result is 0x00 . It’s cheaper thanPUSH1 0x00
• CALLER push msg.sender to sack
• ORIGIN push tx.origin to stack
• XOR consume two items on the top of the stack and pushing the result msg.sender xor tx.origin to stack
• PUSH1 0x0a push JUMPDEST to stack
• JUMPI consume two items on the top of the stack, if msg.sender == tx.origin do REVERT otherwise, jump to JUMPDEST
• DUP2 duplicate the 2nd item in the stack
• DUP2 duplicate the 2nd item in the stack
• DUP1 duplicate the item on the top stack, our stack would look like this [0x00,0x00,0x20,0x00,0x20], we assume that the top of the stack in the left.
• SLOAD load storage at index 0x00 return immortal on the top of the stack
• DUP3 we used DUP3 to duplicate 0x20 since BLOCKHASH can’t perform with current block, the idea is we perform it on 32nd older block.
• NUMBER return current block height block.number to stack
• SUB consume two value on the top of the stack then push block.number - 32 to stack
• BLOCKHASH get block hash of block.number - 32 push to stack, blockhash and immortal are on the top of the stack
• XOR EVM has wordsize is of 256 bits so we better use XOR to combine two 256 bits values instead of performing con cat in the memory. After this step blockhash xor imomrtal will be on the top of the stack.
• DUP2 will duplicate 0x00 , now 0x00 is on top of the stack
• MSTORE assign memory memory[0, 32] = blockhash xor imomrtal , stack right now[0x00,0x20,0x00,0x20]
• SHA3 compute the digest of value in the memory at[0x00:0x20] then push the result to the stack
• DUP2 duplicate 0x00 value in stack, the stack is [0x00,keccak256(blockhash xor immortal),0x00,0x20]
• SSTORE consume two items on the top of the stack and overwrite immortal at 0x00
• RETURN consume two last items in the stack and leave.

When we run the assembler, the result of compile the assembly is shown:

Output:
60203d333218600a57fd5b8181805482430340188152208155f3
Tx deploy data:
601a803d90600a8239f360203d333218600a57fd5b8181805482430340188152208155f3

Conclusion

• We prevent normal address to trigger PRNG
• Code was optimized to minimal gas consumption
• Each call cost around 5190 gas, mostly from SLOAD andSSTORE
• This code work on any EVM
• The more the other contracts use this PRNG the less chance for an adversary to predict or manipulate the result

Source code available here:

chiro-hiro/thedivine