9 ms·

Predicting Random Numbers in Ethereum Smart Contracts

261 points by alexlash 9y ago

baby 9y ago
That is a really really interesting post. I always figured that these were only exploitable from a miner's point of view, but no! Creating a contract that will access the same randomness and THEN query the targeted contract will work, since they both happen in the same block hence the randomness will be the same.
- rocqua 9y ago
  It seems like commit-reveal is really the only thing that makes sense.
- AgentME 9y ago
  Yeah, I used this trick to empty out a few tens of dollars worth of Ethereum from a few naively-coded roulette contracts that were sitting around with a little money left in them. Say a contract exists in the blockchain that owns a little bit of ether and has code so that if you send it a certain amount of money, it does some magic to randomly determine whether to send you more money back. I found a few contracts like that. All I had to do was code a contract that would send money to the target contract, check its own balance (to see if it won some money from the target), and then abort the entire transaction if its own balance isn't greater than it started with. The code was really simple: https://gist.github.com/AgentME/d4cc6aa355900853b8ede3a84b10ad68 https://gist.github.com/AgentME/d4cc6aa355900853b8ede3a84b10... ("Tens of dollars" was in present prices. I assume it was an even tinier amount of money when the creator or previous users put the money in. I think there's multiple interesting moral problems here: if you decide to ignore any "code is law" notions about Ethereum and call what I did as stealing, is the crime lessened by the fact that they thought it was worth even less when they put it into the contract? Also, who exactly did I steal from? The users who put the money into the contract believed they had gambled it away. Does it make a difference if they believed that money was going into an un-owned pot to be winnings for the next person? Do I count as a "winner", since I did claim it in a way it was coded to accept? ... Maybe a related problem: If someone doing some kind of art/performance statement purposefully hid money underground in a random place on public property unlocked, unmarked, and location unknown to themselves such that they thought no one else or even themselves could ever find it, and then I find it with x-ray goggles and take it, am I stealing?)
  - temp-dude-87844 9y ago
    The questions of morality are largely orthogonal to questions whether surrounding institutions have strategies to address behavior considered 'problematic'. In the overworld, we have institutions which continuously interpret, enforce, refine, and revise both the letter and the spirit of contracts and law. Ethereum developers and VIPs have already shown that they'll use hard forks to steer the community towards their preferred direction, and individuals will have to decide which chain to pursue. Since your actions are small beans and unlikely to prompt the Ethereum decision makers to reverse these transactions, you and others can likely keep doing such things in the future, and those affected will have little choice but to accept it.
    - drdeca 9y ago
      Ok, but their question was morality, not what will be enforced, so, I'm not sure why you are bringing up what will be enforced?
      - AgentME 9y ago
        I think they are interestingly intertwined questions. If something happens that's egregiously morally out of bounds, then people will find or create ways to enforce against it. From the other angle, existing enforcement mechanisms will impose themselves as trying to define what moral is. In a way, besides the little selfish gains, I may be fatalistically trying to define "code is law" as moral because it is what I am presently capable of enforcing. Maybe I'm just talking myself in a circle; it's good fuel to ruminate on.
        BraveNewCurency 9y ago
        > If something happens that's egregiously morally out of bounds, then people will find or create ways to enforce against it. I think you left out "and a lot of money is involved". Do you think there would have been an emergency hard fork if the DAO only had $100 in it? I sincerely doubt it. > existing enforcement mechanisms will impose themselves as trying to define what moral is. Morality and Law (code or not) are different things. You can't code morality - you can only encode the programmer's morality. (Which is not the same thing, because the programmer can change his/her mind.)
deegles 9y ago
It's too bad it's not possible to store a secret in a contract (as far as I know). It would be interesting to store a private key that would be revealed only after a certain block number (let's say calculated to be 10 years in the future) as a sort of time capsule for files.
- hodl 9y ago
  You could with an oracle. Without an oracle I think this would be impossible. How will the chain know the key in 10 years but not Bob now?
  - gwern 9y ago
    Time-locks: https://www.gwern.net/Self-decrypting-files https://www.gwern.net/Self-decrypting-files You can implement them trapdoor/proof-of-work style using squaring or hashing with a reward that can be claimed only by publicly revealing the secret. Eventually you will be able to use witness encryption so you can encrypt a secret to the property 'Bitcoin blockchain has reached 500 additional blocks' which can only be decrypted by providing the valid PoW-hashes of 500 blocks etc.
    - AlexCoventry 9y ago
      > Eventually you will be able to use witness encryption so you can encrypt a secret to the property 'Bitcoin blockchain has reached 500 additional blocks' which can only be decrypted by providing the valid PoW-hashes of 500 blocks etc. How do you prevent abusing that by running it in a simulation in which the difficulty crashes?
      - gwern 9y ago
        The difficulty resets only every ~2 weeks of blocks, so tanking the difficulty still requires the investment of a vast amount of hash power in order to create a parallel chain. Secondly, as I understand witness encryption, if you're able to encode the hash rules as the condition, it would be easy to throw in an additional condition like 'all hash difficulties (# of leading zeros) must be >= difficulty XYZ', and simply ban large difficulty reductions. Which works as long as Bitcoin remains popular and justifying high-difficulty blocks, and if it crashes, your timelock is no longer secure so you don't want it to open and to failsafe.
deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
adamnemecek 9y ago
Isn't Elasticsearch an extreme overkill for 3500 contracts?
- Groxx 9y ago
  Almost definitely, but it's probably the only real option to feed data to a rich filtering / display UI like Kibana, for easier exploration. Probably worth the effort if you know how to do it.
jashmenn 9y ago
If this sort of thing interests you, checkout Dfinity's random beacons - They use threshold cryptography (think of it as a type of "multisig") to solve the commit-reveal problem (where the last party to reveal their commitment can abandon, so they have an advantage). They build on it to create a provable, deterministic source of randomness which can't be exploited in this same way. Here's a video that goes into more detail: https://www.youtube.com/watch?v=xf1dql4Zoqw https://www.youtube.com/watch?v=xf1dql4Zoqw
- printf_kek0 9y ago
  > deterministic source of randomness There is a manifest contradiction here created by this choice of words.
  - oh_sigh 9y ago
    IIRC It is entirely deterministic, if all parties are in cahoots with each other and sharing their secrets. But, if they are not, then it is effectively a non-deterministic random.
  - AlexCoventry 9y ago
    A coin flip is deterministic if you know its initial conditions and environment with sufficient precision. Deterministic cryptographic primitives can similarly be viewed as random, from the perspective of an observer who doesn't know the relevant secrets.
- tfha 9y ago
  There's a general class of crypto for solving this problem called a VRF. Algorand also has a very clever way to solve the randomness problem, including a method to foil an attacker that is even able to get lucky repeatedly.
  - warkdarrior 9y ago
    Did you mean Verifiable Random Functions (VRFs)?
johntb86 9y ago
What use cases are there for random numbers in smart contracts? From the article, it seems like gambling is the main use.
- nopit 9y ago
  Gambling is pretty much the only use for smart contracts in general.
  - nym 9y ago
    Supposedly, this is a 51.96 billion market globally. https://www.statista.com/statistics/270728/market-volume-of- https://www.statista.com/statistics/270728/market-volume-of- online-gaming-worldwide/
  - weego 9y ago
    Maybe by people coming into the industry. The established industry in general is far too risk averse to use smart contracts in their current state
- realusername 9y ago
  It's pretty much the same use case as any standard code, smart contracts are just decentralised code after all.
- mcherm 9y ago
  Suppose I wanted to create a "game" running on Etherium's global computer; perhaps one that allowed people to own and breed virtual cats. I might want a random component in my "breed" behavior. Imagine I want to create a smart contract where tasks are created by customers and assigned randomly to "turks" who submit completed tasks and are paid (if the task is accepted). A random number might be one useful part of the task assignment process. ANY program that would random numbers is a potential candidate.
loverofthings 9y ago
Well, let's ignore the reuse of the seeds, let's focus on generating random numbers in a range 0-N using a uniform random generator that gives numbers from 0-M where M >= N. Code snippets shown use modulus (x % (N+1)) to accomplish that. This will result in the numbers not at all uniformly distributed. Of course, the differences in probability aren't that huge but the contracts are mathematically not fair. import numpy as np n, m = 2, 20 binc = np.bincount(np.random.randint(0, m, size=20000000) % (n+1)) print 1.0*binc/sum(binc); [0.3501464 0.3497516 0.300102 ] When we're generating 0-2, from 0-20, we get 0 and 1 more often than 2.
tehlike 9y ago
Relevant thread wrt rng in smartcontracts: https://news.ycombinator.com/item?id=16281347 https://news.ycombinator.com/item?id=16281347

261 points by alexlash 9y ago

baby 9y ago

That is a really really interesting post. I always figured that these were only exploitable from a miner's point of view, but no! Creating a contract that will access the same randomness and THEN query the targeted contract will work, since they both happen in the same block hence the randomness will be the same.

rocqua 9y ago
It seems like commit-reveal is really the only thing that makes sense.
AgentME 9y ago
Yeah, I used this trick to empty out a few tens of dollars worth of Ethereum from a few naively-coded roulette contracts that were sitting around with a little money left in them. Say a contract exists in the blockchain that owns a little bit of ether and has code so that if you send it a certain amount of money, it does some magic to randomly determine whether to send you more money back. I found a few contracts like that. All I had to do was code a contract that would send money to the target contract, check its own balance (to see if it won some money from the target), and then abort the entire transaction if its own balance isn't greater than it started with. The code was really simple: https://gist.github.com/AgentME/d4cc6aa355900853b8ede3a84b10ad68 https://gist.github.com/AgentME/d4cc6aa355900853b8ede3a84b10... ("Tens of dollars" was in present prices. I assume it was an even tinier amount of money when the creator or previous users put the money in. I think there's multiple interesting moral problems here: if you decide to ignore any "code is law" notions about Ethereum and call what I did as stealing, is the crime lessened by the fact that they thought it was worth even less when they put it into the contract? Also, who exactly did I steal from? The users who put the money into the contract believed they had gambled it away. Does it make a difference if they believed that money was going into an un-owned pot to be winnings for the next person? Do I count as a "winner", since I did claim it in a way it was coded to accept? ... Maybe a related problem: If someone doing some kind of art/performance statement purposefully hid money underground in a random place on public property unlocked, unmarked, and location unknown to themselves such that they thought no one else or even themselves could ever find it, and then I find it with x-ray goggles and take it, am I stealing?)
- temp-dude-87844 9y ago
  The questions of morality are largely orthogonal to questions whether surrounding institutions have strategies to address behavior considered 'problematic'. In the overworld, we have institutions which continuously interpret, enforce, refine, and revise both the letter and the spirit of contracts and law. Ethereum developers and VIPs have already shown that they'll use hard forks to steer the community towards their preferred direction, and individuals will have to decide which chain to pursue. Since your actions are small beans and unlikely to prompt the Ethereum decision makers to reverse these transactions, you and others can likely keep doing such things in the future, and those affected will have little choice but to accept it.
  - drdeca 9y ago
    Ok, but their question was morality, not what will be enforced, so, I'm not sure why you are bringing up what will be enforced?
    - AgentME 9y ago
      I think they are interestingly intertwined questions. If something happens that's egregiously morally out of bounds, then people will find or create ways to enforce against it. From the other angle, existing enforcement mechanisms will impose themselves as trying to define what moral is. In a way, besides the little selfish gains, I may be fatalistically trying to define "code is law" as moral because it is what I am presently capable of enforcing. Maybe I'm just talking myself in a circle; it's good fuel to ruminate on.
      - BraveNewCurency 9y ago
        > If something happens that's egregiously morally out of bounds, then people will find or create ways to enforce against it. I think you left out "and a lot of money is involved". Do you think there would have been an emergency hard fork if the DAO only had $100 in it? I sincerely doubt it. > existing enforcement mechanisms will impose themselves as trying to define what moral is. Morality and Law (code or not) are different things. You can't code morality - you can only encode the programmer's morality. (Which is not the same thing, because the programmer can change his/her mind.)

deegles 9y ago

It's too bad it's not possible to store a secret in a contract (as far as I know). It would be interesting to store a private key that would be revealed only after a certain block number (let's say calculated to be 10 years in the future) as a sort of time capsule for files.

hodl 9y ago
You could with an oracle. Without an oracle I think this would be impossible. How will the chain know the key in 10 years but not Bob now?
- gwern 9y ago
  Time-locks: https://www.gwern.net/Self-decrypting-files https://www.gwern.net/Self-decrypting-files You can implement them trapdoor/proof-of-work style using squaring or hashing with a reward that can be claimed only by publicly revealing the secret. Eventually you will be able to use witness encryption so you can encrypt a secret to the property 'Bitcoin blockchain has reached 500 additional blocks' which can only be decrypted by providing the valid PoW-hashes of 500 blocks etc.
  - AlexCoventry 9y ago
    > Eventually you will be able to use witness encryption so you can encrypt a secret to the property 'Bitcoin blockchain has reached 500 additional blocks' which can only be decrypted by providing the valid PoW-hashes of 500 blocks etc. How do you prevent abusing that by running it in a simulation in which the difficulty crashes?
    - gwern 9y ago
      The difficulty resets only every ~2 weeks of blocks, so tanking the difficulty still requires the investment of a vast amount of hash power in order to create a parallel chain. Secondly, as I understand witness encryption, if you're able to encode the hash rules as the condition, it would be easy to throw in an additional condition like 'all hash difficulties (# of leading zeros) must be >= difficulty XYZ', and simply ban large difficulty reductions. Which works as long as Bitcoin remains popular and justifying high-difficulty blocks, and if it crashes, your timelock is no longer secure so you don't want it to open and to failsafe.

deleted 9y ago

[deleted]

deleted 9y ago

[deleted]

adamnemecek 9y ago

Isn't Elasticsearch an extreme overkill for 3500 contracts?

Groxx 9y ago
Almost definitely, but it's probably the only real option to feed data to a rich filtering / display UI like Kibana, for easier exploration. Probably worth the effort if you know how to do it.

jashmenn 9y ago

If this sort of thing interests you, checkout Dfinity's random beacons - They use threshold cryptography (think of it as a type of "multisig") to solve the commit-reveal problem (where the last party to reveal their commitment can abandon, so they have an advantage). They build on it to create a provable, deterministic source of randomness which can't be exploited in this same way. Here's a video that goes into more detail: https://www.youtube.com/watch?v=xf1dql4Zoqw https://www.youtube.com/watch?v=xf1dql4Zoqw

printf_kek0 9y ago
> deterministic source of randomness There is a manifest contradiction here created by this choice of words.
- oh_sigh 9y ago
  IIRC It is entirely deterministic, if all parties are in cahoots with each other and sharing their secrets. But, if they are not, then it is effectively a non-deterministic random.
- AlexCoventry 9y ago
  A coin flip is deterministic if you know its initial conditions and environment with sufficient precision. Deterministic cryptographic primitives can similarly be viewed as random, from the perspective of an observer who doesn't know the relevant secrets.
tfha 9y ago
There's a general class of crypto for solving this problem called a VRF. Algorand also has a very clever way to solve the randomness problem, including a method to foil an attacker that is even able to get lucky repeatedly.
- warkdarrior 9y ago
  Did you mean Verifiable Random Functions (VRFs)?

johntb86 9y ago

What use cases are there for random numbers in smart contracts? From the article, it seems like gambling is the main use.

nopit 9y ago
Gambling is pretty much the only use for smart contracts in general.
- nym 9y ago
  Supposedly, this is a 51.96 billion market globally. https://www.statista.com/statistics/270728/market-volume-of- https://www.statista.com/statistics/270728/market-volume-of- online-gaming-worldwide/
- weego 9y ago
  Maybe by people coming into the industry. The established industry in general is far too risk averse to use smart contracts in their current state
realusername 9y ago
It's pretty much the same use case as any standard code, smart contracts are just decentralised code after all.
mcherm 9y ago
Suppose I wanted to create a "game" running on Etherium's global computer; perhaps one that allowed people to own and breed virtual cats. I might want a random component in my "breed" behavior. Imagine I want to create a smart contract where tasks are created by customers and assigned randomly to "turks" who submit completed tasks and are paid (if the task is accepted). A random number might be one useful part of the task assignment process. ANY program that would random numbers is a potential candidate.

loverofthings 9y ago

Well, let's ignore the reuse of the seeds, let's focus on generating random numbers in a range 0-N using a uniform random generator that gives numbers from 0-M where M >= N. Code snippets shown use modulus (x % (N+1)) to accomplish that. This will result in the numbers not at all uniformly distributed. Of course, the differences in probability aren't that huge but the contracts are mathematically not fair. import numpy as np n, m = 2, 20 binc = np.bincount(np.random.randint(0, m, size=20000000) % (n+1)) print 1.0*binc/sum(binc); [0.3501464 0.3497516 0.300102 ] When we're generating 0-2, from 0-20, we get 0 and 1 more often than 2.

tehlike 9y ago

Relevant thread wrt rng in smartcontracts: https://news.ycombinator.com/item?id=16281347 https://news.ycombinator.com/item?id=16281347