The Proper Treatment of Randomness - Martin Derka

all right uh hello everybody my name is martin i am a senior research engineer at quan stamp and i will be talking about randomness unchained uh before we hop into the talk i just want to point out that quan stem is actually sponsoring a bounty at this hackathon so if you're hacking please do listen to the talk you might find some useful information in here thank you very much all right so our bounty is about randomness uh we are asking that you know you develop an app that uh uses randomness on chain in a non-trivial way uh so that this randomness is not exploitable uh there is a qr code that leads to a blog post about what you should be doing with randomness and uh on the official either website you can find a write-up for the bounty as well so let's go to the technical section of the talk if you have ever developed uh in any programming language other than solidity uh you would probably know that the language provides you with a function called random or something similar that generates random numbers solidity doesn't have it and the reason why it doesn't have it is very simple it's because we have a bunch of ethereum miners every single miner is maintaining the state of the blockchain on their local environment and they have to be replaying transactions to update the state and if there was some opportunity for them to generate some random numbers various miners would be arriving to varying results and there would be no integrity of the state guaranteed so therefore a primitive for generating randomness doesn't exist however we want it right because we want to develop lotteries we want to develop nft drops and decide who should be getting which nft and we want to develop games so therefore uh the developers went out of their way to devise various techniques of how to get some randomness on chain so these techniques include some deterministic computations based on blockchain data maybe block hashes or something similar they use something that we call a verifiable random function that you can implement yourself or you can use some existing implementation there is one provided by a chain link it includes a commit and reveal scheme which i will be talking about it's a design pattern and we can also use something that i'm calling a trusted randomness provider it would be a trusted agent that will just generate random data off chain and send them on chain but this is the part that i will not be discussing because this is not really decentralized so all these techniques can actually work if you use them correctly and all of them can fail if you use them wrong and this is what the talk will be about so before i you know jump into uh the recent times i want to backtrack into 2018 and demonstrate to you what can go wrong with randomness on chain so in 2018 we had some application it was a ponzi scheme called fomo 3d on ethereum it was extremely popular and what fomo 3d wanted the users to do was to buy in with some amount of ether buy some kind of thing called a key and while buying the key the fomo 3d application would roll a random number and it would decide or it would make it a random decision and would decide whether user is lucky and if they were lucky it would send them some amount of assets it would be like an air drop type thing so here i have a you know heavy simplification of the code that was present in there i have a method that is called enter it's external payable and on the first line it checks that i'm providing or calling this method with the right amount of money so let's say one ether and then it will take the current block hash it will take it mod 50 so it gives me some two percent probability that i will be lucky and if i'm lucky it will send me one percent of the balance of the contract so that was roughly what happened in fomo this is very clearly exploitable so i can construct a smart contract which will be looking somewhat like this it will implement a function which will on the very first line check that the block hash mod 50 is zero and if that holds then it will buy into formal otherwise it will not so such a function and such a smart contract would be buying into fomo knowing that 100 sure it will be rewarded with an airdrop so this would be the exploit and clearly the developers of fullmo3d knew about it because what they included in their smart contract was a line that required that the size of the byte code associated with the caller of this method would be zero we are assuming that smart contracts would have some byte code on chain right so that was the protection that they chose to use and it was actually wrong because we know that there are several moments in the life cycle of a smart contract when it still doesn't have any code on chain one of them being the moment of construction so i could still exploit it in the very same way by moving the exploit code into a constructor of my smart contract exploit it would do the same thing check that the block hash mod 50 is zero and it would buy into fomo only if it is mod50 so this didn't work the proper way of making sure that smart contracts cannot interact with your own contract is uh the following you would be requiring that the message sender is the transaction origin because we know that smart contracts can never initiate transactions themselves so they will never be the transaction origin i have to step aside here for a second there is a well-known post on stack overflow by vitalik which says that developers should never assume that transaction origin will remain useful or meaningful but for the purposes of this talk it still exists it is useful and meaningful so this is right now a valid way of protecting your smart contract from being interacted with by other smart contracts so presumably this should be working as a valid protection but it doesn't because it's 2022 and now we have a project that is called flashbots so let's talk about flashbots and how we can use them to export many thing many things including randomness so flashbots is a service that provides people with a private mempool into which you can send transactions and flashbots will give you some guarantees about how these transactions will be mined so specifically you can send in batches of transactions and flashballs will guarantee that if they succeed in mining a block with those transactions these transactions in the batch will be sorted in the block consecutively without any transaction coming in between and they will also guarantee to you that all the transactions in the batch will succeed otherwise they will not be projected on chain so you can use this to exploit things uh again i don't want to be stuck in 2018 so i'm fast forwarding into 2020 one i guess and i want to be talking about a smart contract that is a little bit more recent but still exploitable so in 2021 uh at the end of the year uh what the developers released was this interesting game that featured some nfts they were wizards and there were some dragons and somewhere in the game you would be or you would have the opportunity to stake your nfts to collect some in-game assets those nfts would be collecting the in-game assets and eventually you could choose to unstake those nfts and get your in-game assets they called them gp they were the gp tokens it was an erc20 token so you would unstake the nfts and you would presumably get back your gp tokens however somewhere in the unstaking process the developers wanted to make a random decision whether you will actually receive your gps or whether they will be taken away from you and paid to the other participants of the game so uh the method it's this is actually an exact excerpt from etherscan that i have taken so the method for unstaking is called claim many from tower and flight it is the external method and you can see that the developers here were also very aware that smart contracts can cause cause some real mess so they wanted to prevent interaction uh of smart contracts with this method and therefore they included the requirement that transaction origin is the message center right and then this method iterates over all the stake nfts of the particular caller and it will calculate how many gps those nfts collected that's what we are maintaining in this variable ode and if that number is node 0 then it will mint the gps to the particular user the number of gps that are being collected and they should be minted to the user is calculated in the subroutine so i'm going to switch the slide to show the subroutine and particularly in the subroutine i am interested in this highlighted part where if we are unstaking they have some component called randomizer that is supposed to generate a random number then they take that random number they take a bitwise end with one and make sure that the result is one so they are actually checking here that this number is uh odd and if the number is odd they will say no we don't owe you anything all the gps that you have collected will be taken away from you and they will be paid as tax somewhere else right so this is the mechanic how it worked and again this is exploitable using flashbots because what you can do you can construct a transaction batch that looks as follows in the first transaction you will unstake your nft during that unstaking something will happen and presumably you should be getting your gps right so in the second transaction you can actually assume that you yielded the favorable outcome that you have collected the gps and they are currently in your account so you can try to use them you can try to take them and transfer them somewhere else or you can try to transfer them to yourself it doesn't really matter but you will use them if you have them the second transaction would mine without an error if you do not have them so they were stolen and paid as a tax somewhere else then the second transaction would be failing because you are trying to use tokens that you do not own so if you send such a batch to flashbots because they guarantee that this will be mined only if both the transaction pass uh you will have the guarantee that if this transaction mine you actually did collect your gps and if you did not collect your gps then you can just try again and try again and try again and try again because not including these transactions on chain will not cost you anything you don't even have to pay gas right there's no transaction that failed on chain so uh this game mechanic was actually broken from the very beginning and all the people playing this game uh didn't have to pay any kind of taxes or gps or anything like that so this is how you would be using flashbots to exploit randomness that resolves immediately the second thing that i want to talk about it's a different technique for producing randomness is the commit and reveal scheme so commit and reveal is a design pattern it breaks the production of uh randomness and its resolution into two steps in the first step the user has to commit to some action so that they cannot retract their commitment later it's you know done and at some point it will be resolved and so that they cannot infer the outcome of the commitment while they are committing and for some technical reasons we also usually want they cannot recommit and you know resolve the same action again and the point is that the outcome will be decided sometimes later during an event that we call reveal so here is an example how such a code could look uh and is actually wrong so i will explain both first of all i have the two functions that i was referring to i have commit and i have reveal during commit the user comes and we are checking that they do not have an existing commitment yet and if they do not have an existing commitment yet what we will do is we will generate a random number using a black box function that i am here calling getsaferandom the implementation of this function is something that we do not care about in this talk but we are assuming that is absolutely safe not manipulable not predictable it's actually just okay and we will take this random number and we will put it in the mapping comments associated with the caller and then in the second step in the reveal that would be called by the same message sender we check that the message sender has a previous commitment and then we will take that random number from that commitment we will take it mod 2 and if the user is lucky so that number is even then we will send them the balance of the smart contract so this would be an example of a commit and reveal that is unfortunately coded wrong because it violates the assumption that users can know nothing about their commitment at the time of when they are committing the reason why they actually infer all the information they need in here is that this mapping is public right because i can again construct a smart contract which has this function that commits and then it queries the commitment in the mapping of commits and checks that it is actually even and if it is not then it will revert the transaction and nobody committed to anything so this is actually wrong and this also leads us to a suggestion how we should fix it right we should make it private so that this mapping cannot be queried by other smart contracts so this would now appear fixed but again it is not fixed because we have flashbots flashbots would be able to exploit this exactly the same way how i have described previously so we would first commit in the batch of transactions then immediately after we would reveal that would be a different transaction and we would assume that we were lucky that this commit and reveal combination actually yielded the reward that we received some ether in our address and we would try to use it if it did the transaction batch mines if it did not transaction badge doesn't mind it doesn't cost me any ether any anything and i can just try again so what we would need to do to fix this is to ensure that flashbots cannot organize the transaction batch to a single block the way how they usually want to do it right so we would need some block locking mechanism so to fix that i have here introduced another mapping of blocks and during the commitment which looks very similar to what you have seen before i'm recording the number of the block when the user is committing to the action and then during reveal i'm checking that the commitment happened at least 32 blocks in the past and if it did not the user just has to wait a little bit longer and can reveal later so this will prevent the flash bots engine from taking the batch of transactions and putting them consecutively in the single block right because this will just never pass through this requirement this number 32 in here that's a very arbitrary number i just chose 32. the point is that you would want to choose a number that is high enough so that flashbots cannot guarantee or reasonably assume that they would be able to mine so many block consecutively themselves as the single miner right because if you imagine that flashbots were able to acquire sufficient hash power in the network so that you know they have a solid chance of mining let's say two consecutive blocks and you only enforce that you know the commit happened in the past block uh then you know sometimes in the future this might become exploitable again so here we are making a bet that flashbots in the near future or for the time of the relevance of this game or a smart contract will not be able to mine 32 consecutive blocks which sounds like a fairly safe assumption however i have broken this code in a different way which is also something that i have seen in projects that we were auditing at quan stamp so here what i have done is uh i have taken the block hash of the time when uh i am calling the reveal and i am actually taking it modulo of that commit right and that's this variable mod and then i am taking the result and taking mod 2 if that is even i will be rewarding the user so the effect of this is that the outcome of the comment depends on the block that the comment uh the reveal is being uh called from right so if i call reveal in different blocks or varying blocks i will be coming up with varying results and again that is wrong because i can attack it i can uh commit myself using a regular transaction but the commitment just means that at some point i will be revealing but everything will be decided like way way way later during that reveal so i can again use flashbots to attack the revealed mechanic using two transactions i will be calling reveal assume favorable outcome and then try to use my reward and i will be trying over and over and over and because reveal produces different results uh at some point i would succeed so the proper way of fixing the code would be not you know breaking it again but introduce these two mappings and uh waiting sufficient number of blocks so that uh the outcome of the reveal is every single time consistent i wanted to talk about the verifiable random function but i see that i am still running out of time so i am just going to skip it but what i'm going to do is conclude the talk and tell you what you should be doing so your question right now should be what the hell should i use in my application for producing randomness and the answer is clear it really depends on what that application really is so if you are developing an application that is going to be relevant in a very limited time frame say that you are developing an nft drop and you know you are assuming that the drought will be so popular that it will mine within the next three or four blocks right in such a case honestly anything will do because the users to be able to exploit any kind of randomness have to have the opportunity to try over and over and over and over if you are developing something where the user will be lucky when they manage to push through a single transaction then there is no cherry picking of the results they will be lucky if they manage to push a single thing through right so in such a case it doesn't really matter on the other hand if you are going to produce something that has a long time frame it's going to be some lottery where users can bet repeatedly or something like that or or a game then you probably want to use the commit and reveal scheme and if i was able to cover the chain links vrf i would actually be able to explain to you that the synchronous provision of randomness that chain link allows is just a very special case of the commit and reveal scheme so this is your answer with that i have a very short time for questions so please feel free to have questions i just want to point out one stem actually has a booth on the lower floor uh so feel free to pop by we are hiring so we you know if you like to dig into smart contracts and figure out how to exploit them we would very much like to talk to you and yeah questions please okay i don't see any so thank you and next speaker as