entropy harvest plays an significant role in this.
For instance, if a computer hasn't been running for significant amount of time,
and you generate an SSH certificate / key using network packets / terminal keystroke and entrophy source before system becomes fully operational
(or worse yet, say some linux distro automatically generate SSH key the first time you install)
it harvest entrophy from network I/O with sequence of packets that create the initial seed so your keys are weak (adding Diffie helman key exchanged and field sieve attacks) it makes poor operational practice / implementation for good cryptographic randomness.
Mostly the algorithm isn't bad, but the use case and how it is implemented made things far worse then you could imagine.
Topic: Random number (Read 514 times)
But how can random numbers be random?
What do you think? All random number must have it's reason it's generated (entropy source, pattern, etc.)
Is it possible at all to create a number generator that will not have any algorithm, and really give a random number?
All random number have it's entropy which makes "complete random" is impossible, the best we could do is :
- Make sure our random function isn't predictable
- Have good entropy source
The naive way of constructing this makes it then take 20 minutes computation to verify, which isn't that attractive if you imagine the verifier is some lame mobile client and the attacker is a mining farm. 
Yeah, although in my case it was totally fine. As it's not really required (or expected) that everyone verifies, it's just an option if you want. And had the nice property of being drop-dead simple
Quote
I keep seeing people propose this an their proposals always turn out to be totally broken, but in fact there is a way to do this that I call tapering.
Step 1. A block is 3xVDFed to pick a random value.
Step 2. The next block is 2xVDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 3. The next block is VDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 4. The last step 1 outcome is accepted.
This will terminate in a couple steps on average.
Step 1. A block is 3xVDFed to pick a random value.
Step 2. The next block is 2xVDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 3. The next block is VDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 4. The last step 1 outcome is accepted.
This will terminate in a couple steps on average.
Oh, I see. That's pretty clever, never thought of something like that.
Similar topic already discussed at https://bitcointalk.org/index.php?topic=5072435.0;all
The easiest/laziest solution would be :
1. Only use blockchain as entropy source when the cost to manipulate blockchain is higher than it's "reward"
2. Use many blocks in a sequence as entropy source since it's difficult to manipulate n blocks in a sequence.
The easiest/laziest solution would be :
1. Only use blockchain as entropy source when the cost to manipulate blockchain is higher than it's "reward"
2. Use many blocks in a sequence as entropy source since it's difficult to manipulate n blocks in a sequence.
So basically there's no solution, because Bitcoin blocks come too rarely and no one would wait more than a few seconds for a random number. My guess is that we'll first see a bullet-proof random number generator on Ethereum.
That made it pretty impractical to manipulate the lotto (after finding a block, a miner would have to wait 20 minutes to check if it was good or not), unless the miner was prepared/able to 51% attack bitcoin at the same time 
The naive way of constructing this makes it then take 20 minutes computation to verify, which isn't that attractive if you imagine the verifier is some lame mobile client and the attacker is a mining farm. Fortunately you can use a verifiable delay function.2. Use many blocks in a sequence as entropy source since it's difficult to manipulate n blocks in a sequence.
How does that work? If you get n blocks in a sequence -- the result is always going to be influenced by the last block in the sequence, who would be able to perform the same sort of attacks as if you just had used that 1 block.I keep seeing people propose this an their proposals always turn out to be totally broken, but in fact there is a way to do this that I call tapering.
Step 1. A block is 3xVDFed to pick a random value.
Step 2. The next block is 2xVDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 3. The next block is VDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 4. The last step 1 outcome is accepted.
This will terminate in a couple steps on average.
You can make all kinds of variations on this, e.g. start the reset probability high and slope it down. But the general idea is that while single block may be biased, multiple blocks are at least somewhat mutually independent. Effort you spend grinding out a low block in step 1 is likely to get discarded by step 2/3 resets... but all can do is accept or reset the process, so those blocks doesn't have much influence on the outcome.
I'm sure effort that has gone into research on "randomness extractors" could be used to generalize this to achieve a guaranteed worst case bias achievable under useful assumptions- Essentially that work is trying to address this problem: You have a function with multiple inputs, the attack has control over some not all of them, can observe at least some of the ones he can't control, and you don't know what inputs are attacker controlled/observed... what function allows you to extract the most uniform number, in spite of the attackers efforts, and how far from uniform can the attacker make it?
Unfortunately, almost all randomness extractor work is highly theoretical, non-constructive, and nearly incomprehensible to me... so I can't even tell if any of the existing approaches is applicable.
In any case, if large amounts of bias is needed by the attacker, I think these techniques can make achieving it much more costly.
Tapering works nice with VDFs, since you can attempt to make the time that the random value will be known long after the decision to use it or not needs to be made.
Another hardening approach you can use that I've described before is bonding:
Block X pays a bitcoin to pubkey A.
Block X+1 picks a random value.
Some expensive work function operates on the random value using the private key for pubkey A.
Block >X+10 spend A's coins off to someplace else.
Now: to rig the random value the miner and the private key holder for A must collude. "A" can't influence the outcome at all (except say by just never releasing the private key), but the miner cannot grind without their help. Why a bitcoin and privatekey instead of just a hash commitment in A's transaction? So that if A tells the miner(s) the secret before X+2, the miners could just steal the coins instead of helping A's randomness.
Another hardening approach you can use that I've described before is multiparty verifiable oracles:
BLS signatures are completely deterministic the signature of message X is always S. BLS signatures can also easily support N of M threshold signing. So you have published N of M BLS threshold public key... to produce a final random value, you have a transaction (or OTS timestamp) commit to your BLS pubkey, then get a blockchain produced random value from a later block and sign it. The signature is your final random result.
Now creation of a biased random result requires a collusion of N parties plus the miner, jamming release of the random value requires >M-N parties to fail.
That made it pretty impractical to manipulate the lotto (after finding a block, a miner would have to wait 20 minutes to check if it was good or not), unless the miner was prepared/able to 51% attack bitcoin at the same time
The naive way of constructing this makes it then take 20 minutes computation to verify, which isn't that attractive if you imagine the verifier is some lame mobile client and the attacker is a mining farm. Fortunately you can use a verifiable delay function.2. Use many blocks in a sequence as entropy source since it's difficult to manipulate n blocks in a sequence.
How does that work? If you get n blocks in a sequence -- the result is always going to be influenced by the last block in the sequence, who would be able to perform the same sort of attacks as if you just had used that 1 block.I keep seeing people propose this an their proposals always turn out to be totally broken, but in fact there is a way to do this that I call tapering.
Step 1. A block is 3xVDFed to pick a random value.
Step 2. The next block is 2xVDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 3. The next block is VDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 4. The last step 1 outcome is accepted.
This will terminate in a couple steps on average.
You can make all kinds of variations on this, e.g. start the reset probability high and slope it down. But the general idea is that while single block may be biased, multiple blocks are at least somewhat mutually independent. Effort you spend grinding out a low block in step 1 is likely to get discarded by step 2/3 resets... but all can do is accept or reset the process, so those blocks doesn't have much influence on the outcome.
I'm sure effort that has gone into research on "randomness extractors" could be used to generalize this to achieve a guaranteed worst case bias achievable under useful assumptions- Essentially that work is trying to address this problem: You have a function with multiple inputs, the attack has control over some not all of them, can observe at least some of the ones he can't control, and you don't know what inputs are attacker controlled/observed... what function allows you to extract the most uniform number, in spite of the attackers efforts, and how far from uniform can the attacker make it?
Unfortunately, almost all randomness extractor work is highly theoretical, non-constructive, and nearly incomprehensible to me... so I can't even tell if any of the existing approaches is applicable.
In any case, if large amounts of bias is needed by the attacker, I think these techniques can make achieving it much more costly.
Tapering works nice with VDFs, since you can attempt to make the time that the random value will be known long after the decision to use it or not needs to be made.
Another hardening approach you can use that I've described before is bonding:
Block X pays a bitcoin to pubkey A.
Block X+1 picks a random value.
Some expensive work function operates on the random value using the private key for pubkey A.
Block >X+10 spend A's coins off to someplace else.
Now: to rig the random value the miner and the private key holder for A must collude. "A" can't influence the outcome at all (except say by just never releasing the private key), but the miner cannot grind without their help. Why a bitcoin and privatekey instead of just a hash commitment in A's transaction? So that if A tells the miner(s) the secret before X+2, the miners could just steal the coins instead of helping A's randomness.
Another hardening approach you can use that I've described before is multiparty verifiable oracles:
BLS signatures are completely deterministic the signature of message X is always S. BLS signatures can also easily support N of M threshold signing. So you have published N of M BLS threshold public key... to produce a final random value, you have a transaction (or OTS timestamp) commit to your BLS pubkey, then get a blockchain produced random value from a later block and sign it. The signature is your final random result.
Now creation of a biased random result requires a collusion of N parties plus the miner, jamming release of the random value requires >M-N parties to fail.
1. Only use blockchain as entropy source when the cost to manipulate blockchain is higher than it's "reward"
It's worth noting that you can increase the cost of manipulating the blockchain. For instance I used to run a lotto, where I'd use a bitcoin block hash to determine the winner. However, because the prizes were reasonably big compared to the blockreward it would've been (very) profitable for a miner to manipulate. So I stretched the hash with an operation that might take like 20 minutes or something.
That made it pretty impractical to manipulate the lotto (after finding a block, a miner would have to wait 20 minutes to check if it was good or not), unless the miner was prepared/able to 51% attack bitcoin at the same time
2. Use many blocks in a sequence as entropy source since it's difficult to manipulate n blocks in a sequence.
How does that work? If you get n blocks in a sequence -- the result is always going to be influenced by the last block in the sequence, who would be able to perform the same sort of attacks as if you just had used that 1 block.
The best should not even have a random number but in some way log every random number to not have something duplicated.
Random numbers from sha256 are also easibility crackable nowadays especially since you are returning the value as plain text
A listener in between can read that value and use it for himself (hacker).
Random numbers from sha256 are also easibility crackable nowadays especially since you are returning the value as plain text
A listener in between can read that value and use it for himself (hacker).
Chains like Luckycoin and Dogecoin make use of randomness when determining block rewards, so it is possible.
There's a lot of lottery drawings by members of this forum. Instead of selling an item, they sell a lottery ticket to try and win that item. They agree on a way to randomly generate a number, so that the seller can't defraud the bettors. Here's how they solve this problem:
The seller announces they are going to host a lottery with a prize. The lottery will end after a certain bitcoin block in the future is mined; say 1000 blocks from now. After that block number that was agreed upon beforehand is mined, the lottery is over and the winner is announced. The seller announces how the winner will be chosen with this block when the lottery begins. Usually, what they do is, they agree to take the last 4 bits of the hash of that future block. The bettors buy tickets with a unique 4-bit number attached - no two tickets have the same number. If their number is the number taken from the last 4 bits of the block hash, then they won! Nobody can know the hash of the block until it is mined. Even if you are a miner, and you only want to mine a block that ends with your lottery ticket number, making a block that does not end with your lottery ticket number and choosing to discard it for that reason is an immediate BTC12.5 loss. And you probably won't solve another block in time before someone else does anyway, so you couldn't guarantee you will win. The only way to profitably tamper with this drawing without a massive risk (which likely outweighs the value of the lottery prize) is with a successful 51% attack, or perhaps an as-of-yet unknown SHA-256 vulnerability.
You don't have to use 4-bit numbers; you could do 8-bit, or 64-bit, or any number, as long as it cannot exceed the current difficulty target, which is a very massive number. Technically, every block hash is a random number between zero and the difficulty target.
There's a lot of lottery drawings by members of this forum. Instead of selling an item, they sell a lottery ticket to try and win that item. They agree on a way to randomly generate a number, so that the seller can't defraud the bettors. Here's how they solve this problem:
The seller announces they are going to host a lottery with a prize. The lottery will end after a certain bitcoin block in the future is mined; say 1000 blocks from now. After that block number that was agreed upon beforehand is mined, the lottery is over and the winner is announced. The seller announces how the winner will be chosen with this block when the lottery begins. Usually, what they do is, they agree to take the last 4 bits of the hash of that future block. The bettors buy tickets with a unique 4-bit number attached - no two tickets have the same number. If their number is the number taken from the last 4 bits of the block hash, then they won! Nobody can know the hash of the block until it is mined. Even if you are a miner, and you only want to mine a block that ends with your lottery ticket number, making a block that does not end with your lottery ticket number and choosing to discard it for that reason is an immediate BTC12.5 loss. And you probably won't solve another block in time before someone else does anyway, so you couldn't guarantee you will win. The only way to profitably tamper with this drawing without a massive risk (which likely outweighs the value of the lottery prize) is with a successful 51% attack, or perhaps an as-of-yet unknown SHA-256 vulnerability.
You don't have to use 4-bit numbers; you could do 8-bit, or 64-bit, or any number, as long as it cannot exceed the current difficulty target, which is a very massive number. Technically, every block hash is a random number between zero and the difficulty target.
for randomness, the best is to let computers do the job. Humans are a bad in generating random numbers.
It is not that easy. Sorry, but your proposal does not solve anything.
How to be sure that Alice doesn't know Bob and they didn't agree beforehand on the X and Y values.
Let's suppose they don't know each other. Bob will be able to know the number Alice provided by using any block explorer.
SHA256 is not that safe when it comes to hashing numbers. It will be easy to crack it using rainbow tables.
What is the point of submitting C=sha256(X) if you are going to submit X (plain text)!!
How to be sure that Alice doesn't know Bob and they didn't agree beforehand on the X and Y values.
Let's suppose they don't know each other. Bob will be able to know the number Alice provided by using any block explorer.
SHA256 is not that safe when it comes to hashing numbers. It will be easy to crack it using rainbow tables.
What is the point of submitting C=sha256(X) if you are going to submit X (plain text)!!
Random numbers in the decentralized system are a problem that is not easy. Especially in Public Blockchain, incentive maintenance is also one of the major difficulties. I have studied this issue for a long time and come up with a suitable solution that can give a solution to avoid manipulation. Thank you
https://i.ibb.co/PhdVLB2/0-C888-F0-B-EAEF-43-A8-ABD0-B49985203-DD5.jpg
https://i.ibb.co/PhdVLB2/0-C888-F0-B-EAEF-43-A8-ABD0-B49985203-DD5.jpg
Jump to: