"Heads or tails" cointoss with Bitcoin transactions?

[goodlord666]

Hello,

it would be awesome if it were possible to do an unpredictable cointoss using bitcoin transactions such that you make a transaction of any amount and then have a public record of whether the cointoss turned out to be "heads" or "tails" (or 1/0).

We had a brief discussion on this recently here:
https://bitcointalk.org/index.php?topic=75252.msg1193694#msg1193694

But as it seems, the technology doesn't currently offer that possibility.

One could easily predetermine a future generated block, such as the next one, and see whether the timestamp turns out to be an even or an odd number. That would be sufficiently random and unpredictable, as well as publicly undisputable (for most earthly uses, anyway).

However, waiting on a block to be generated isn't practical for this.

Is it not possible to have the network append a small grain of random data to a tx msg that could not be predicted by the one making the transaction and thus make it serve as a reliable cointoss? Such as every node on the network flipping one bit in the tx msg (or not) as it passes it along?

It'd just be kinda cool.

gl

[DeathAndTaxes]

If your random "source" comes from nodes it will be manipulated.  One could simply design a node which never loses.  There is no such thing as "the network" it is a network of individual nodes.

tx can't be modified because the exact tx is signed by the sender and that signature is only valid for the exact tx sent.  Even if you could modify the message your method would be trivial to defeat.  The attacker would simply only relay the tx to nodes under his control and thus control the number of binary "flips".

When building any system using the bitcoin network you should assume everything you receive is from malicious nodes and thus is untrusted until verified.

[kjj]

satoshidice generated a huge pile of secrets, like many years worth.  They published hashes of each secret, and each day they reveal the prior day's secret.  You can compare the secret with your transaction hash and confirm that they aren't cheating.

That is one option.  The other option would be to put a delay in, and use the hash of the next block following the incoming transaction to decide if the flip won or not.

[Revalin]

Using the timestamp or other block data would make this vulnerable to a Finney attack.  You could mutually post an encrypted rock paper scissors roll in transactions, then mutually reveal the keys to see the results after they confirm.

There's no practical reason to do it in the blockchain; it would be faster to just do it in email or a TCP connection; but it could be done for novelty's sake.

It occurs to me that IP over blockchain would be possible.  I'm actually surprised no one has tried it.  If you think satoshidice is spammy you ain't seen nothing yet.  

[runeks]

Is it not possible to have the network append a small grain of random data to a tx msg that could not be predicted by the one making the transaction and thus make it serve as a reliable cointoss? Such as every node on the network flipping one bit in the tx msg (or not) as it passes it along?

The creator of the transaction can add random information to the transaction if he wants. But other nodes receiving the transaction can't, because the transaction needs to be signed in order to be valid.

I think the problem here is more so related to the fact that a coin toss is non-deterministic, while all computer operations are deterministic. In other words, no one can practice a coin toss at home that always produces either heads or tails (not that I'm aware of at least), and then perform this toss when taking your bet. This is entirely possible with a computer, because you are in total control of the initial state and the operations that alter the initial state to produce some output.

In effect you are relying on some third party to provide you with random information. This is analogous to not performing a coin toss with a friend, but having a third friend toss the coin with a "coin tossing machine", which can replicate earlier tosses perfectly. You have no way of knowing if the coin toss done by the machine is really random, because nothing about the output  will tell you if it was random or not.

I think we are dealing with an age old problem of creating non-determinism out of a deterministic system. To the best of my knowledge it hasn't been solved yet.

[helloworld]

It occurs to me that IP over blockchain would be possible.  I'm actually surprised no one has tried it.  If you think satoshidice is spammy you ain't seen nothing yet.  

Could it also be used as a storage space, a bit like how Freenet works?

[DeathAndTaxes]

This is analogous to not performing a coin toss with a friend, but having a third friend toss the coin with a "coin tossing machine", which can replicate earlier tosses perfectly. You have no way of knowing if the coin toss done by the machine is really random, because nothing about the output will tell you if it was random or not.

[Revalin]

I think we are dealing with an age old problem of creating non-determinism out of a deterministic system. To the best of my knowledge it hasn't been solved yet.

Modern computer systems are nondeterministic.  Bitcoin is sufficiently affected by network latency and being a randomly-wired network that it's chaotic to the point of being impossible to create a discrete model; you have to do it statistically.  The same goes for /dev/random / urandom which is are collected / seeded from high quality chaos such as keyboard interrupts.

Computers also have true random number generators.  Thermal noise in a resistor is popular and inexpensive method to capture quantum mechanical randomness.

[Revalin]

Could it also be used as a storage space, a bit like how Freenet works?

It already is.  There are a lot of small plaintext strings in the blockchain already, and likely a bunch of encrypted data that we can't measure.  It's pretty expensive storage per byte though.

[Mike Hearn]

The creator of the transaction can add random information to the transaction if he wants.

Signature are themselves random, so every transaction is random including if you recreate it/resign it a few times from scratch.

However, that's obviously pointless for the requested use case because you can just keep resigning until you get the result you want, or pick k such that it gives the desired result.

The best way to use Bitcoin as an RNG is to just look at some bits of the hash of the block buried N blocks deep. If you want instant randomness, Bitcoin can't do that.

However there may be other cryptographic protocols that can, eg, MPC.