Trust minimized random seed

[ukneshi]

I posted a question on https://crypto.stackexchange.com/questions/99478/p256-seed-problem, but I figured this might be a better place for such discussion.

The question is how do you generate a seed for which everyone knows it couldn't have been set up with a malicious intent.
It's very easy to trust yourself in picking it, but picking a global seed seems a hard problem. As the question on crypto stackexchange describes, I've been reading about cryptography and elliptic curves and found out some don't trust P256 seed choice which is defined in https://csrc.nist.gov/csrc/media/publications/fips/186/3/archive/2009-06-25/documents/fips_186-3.pdf on page 89 to be

SEED = c49d3608 86e70493 6a6678e1 139d26b7 819f7e90

The issue seems to be how to agree on a seed in a trust-minimized way.

This is what made me wonder if computational energy from Bitcoin could be used.

Suppose we do the following. We define the max Bitcoin block number e.g. 730445 which is the latest Bitcoin block. The starting point is the Bitcoin genesis block. We now repeat the process:

1. Hash the block hash to obtain X
2. seed += X[0]
3. Compute the next block height as X % 730445
4. Repeat 1 until we have a long enough seed.

Suppose Satoshi was an evil mastermind who predicted this. Even so, they couldn't have known what the next hash contribution will be given a large enough interval because this would have required them to guess the hash of the blockhash at height 720921 since hash(genesis) % 730445 = 720921.

This would generate a seed based on randomized energy contribution to the Bitcoin over the last decade.

I have made a prototype of this https://controlc.com/71836119 which yields 0db5a6b3f17115c58a074eea763768d5. Would you trust 0db5a6b3f17115c58a074eea763768d5 as a seed?

[1714776742]

1714776742

[1714776742]

1714776742

[1714776742]

1714776742

[1714776742]

1714776742

[1714776742]

1714776742

[kaggie]

Not necessarily?

Your choice of the hashes still isn't verifiably random.
How would I not know that you didn't stop on a particular hash because you thought it was more weak? Also, by doing a hash of a hash, how do I know that you aren't losing entropy by doing a second hash?

Whether any variable is random is not at issue. The issue is whether the logic for why that value was chosen is published. There may be a certain set of numbers that make the spectral weakness, like even versus odd.

If you use your hash method, you might have to do some additional verification, like slide 17 of 26 here: https://bada55.cr.yp.to/slides-dan+tanja-20140513-4x3.pdf

[odolvlobo]

Suppose we do the following. We define the max Bitcoin block number e.g. 730445 which is the latest Bitcoin block. The starting point is the Bitcoin genesis block. We now repeat the process:

1. Hash the block hash to obtain X
2. seed += X[0]
3. Compute the next block height as X % 730445
4. Repeat 1 until we have a long enough seed.

The problem here is that the algorithm for creating a seed using known values could be selected in order to generate a predetermined value. I think a better way might to announce the algorithm before its data is known. For example, a hash of the next 256 block IDs. Note that this is not complete trustworthy because miners could potentially manipulate the block IDs, but the cost of doing that would be huge, so it is unlikely to happen.

I am not an cryptography expert, just a fanboi.

[bitmover]

Suppose we do the following. We define the max Bitcoin block number e.g. 730445 which is the latest Bitcoin block. The starting point is the Bitcoin genesis block. We now repeat the process:

1. Hash the block hash to obtain X
2. seed += X[0]
3. Compute the next block height as X % 730445
4. Repeat 1 until we have a long enough seed.

I am not a Cryptography expert. But  , as far as I know  this is a pattern.

Seeds should never be generated on patterns,  because this means they are not truly random. Patterns are never truly random.

This is even why humans are  a bad source of random.

good and secure seeds shoud be truly random, without any pattern.

[ukneshi]

Thank you for you responses.

You all have valid points. I'll try to entertain myself with these questions further.

The problem here is that the algorithm for creating a seed using known values could be selected in order to generate a predetermined value. I think a better way might to announce the algorithm before its data is known. For example, a hash of the next 256 block IDs. Note that this is not complete trustworthy because miners could potentially manipulate the block IDs, but the cost of doing that would be huge, so it is unlikely to happen.

Good point. Would the following be a computationally sound approach?

Pick a generator G as defined on secpk256k1. Hash the `x` coordinate of G to get the x coordinate of the next curve point creating a new NUMS point. Repeat the process to get 100 NUMS points. Once quantum computers are around and we find the discrete logs of these NUMS points, we should (?) be fairly sure we could not have known them today when we defined the algorithm.

[BlackHatCoiner]

How would I not know that you didn't stop on a particular hash because you thought it was more weak?

This is true, and if you simply state the targeted block height on a paper or a website, new readers can't verify that you didn't change it afterwards you found a, satisfactory for you, hash.

People have to somehow verify that you picked a block height at the time it hadn't been mined yet. That's what I propose:

• Include a statement into an OP_RETURN transaction. It will contain the targeted block's height and will be confirmed before it gets mined.
• Once the targeted block is mined, hash all the hundreds of thousands of block headers.
• Publish a signed message with the public key you used to create the OP_RETURN output and the hash that is resulted as a message.

Now readers can verify that you can't have behaved maliciously.

[garlonicon]

For example, a hash of the next 256 block IDs. Note that this is not complete trustworthy because miners could potentially manipulate the block IDs, but the cost of doing that would be huge, so it is unlikely to happen.

This is not going to work. People often repeat the same mistake: they think that if getting block hash of the next block is unsafe, then we should increase the number of blocks. The problem is: the blockchain is already a chain of blocks, so nothing is changed by doing this. If you have a function that can pick some random element, and you have f(a,b,c,d), then even if you have a chain of dependencies, where a->b->c->d, then someone can still change the whole result, just by changing the last element alone.

We already have SHA-256 hashes, those hashes are random enough, if used correctly. But the problem is not the randomness alone: the problem is that if miners know the result, then they can control it fully, and only pick those results that are profitable for them, by "gaming the system". For the same reason, any miner-based lottery will evolve to the case, where miners are like casinos, so they "always win the game" (or at least "always get the house edge"), just like they win block rewards. That's because any miner can be a player at the same time, and also because the winner has to be publicly announced and accepted by miners.

[odolvlobo]

For example, a hash of the next 256 block IDs. Note that this is not complete trustworthy because miners could potentially manipulate the block IDs, but the cost of doing that would be huge, so it is unlikely to happen.

This is not going to work. People often repeat the same mistake: they think that if getting block hash of the next block is unsafe, then we should increase the number of blocks. The problem is: the blockchain is already a chain of blocks, so nothing is changed by doing this. If you have a function that can pick some random element, and you have f(a,b,c,d), then even if you have a chain of dependencies, where a->b->c->d, then someone can still change the whole result, just by changing the last element alone.

Thanks for pointing that out. It is a good insight.

However, note that block ids are not completely random, as a significant number of bits are always going to be 0, so using multiple ids increases the entropy. Furthermore, since a miner has a limited number of bits to work with, the influence of any single block id on the result is reduced, making it more difficult for someone to benefit from the manipulation.

[pooya87]

But the problem is not the randomness alone: the problem is that if miners know the result, then they can control it fully, and only pick those results that are profitable for them, by "gaming the system".

Decentralized nature of bitcoin can help here too. If we use multiple blocks, enough to ensure multiple different miners are finding those blocks then it becomes impossible for a single miner to game the system, it also decreases the chance of all miners cooperating for a malicious intent.

[garlonicon]

If we use multiple blocks, enough to ensure multiple different miners are finding those blocks then it becomes impossible for a single miner to game the system

It does not matter. If you have a function f(a,b,c,d), the attacker can treat "a,b,c" as a black-box constant and change d-only to choose the final result. That means, even if some miner cannot change what other miners did, then that miner alone can for example execute some hash function 2^32 times, that will make the whole seed 2^32 times weaker.

Imagine that you want to get a random number from 1 to 6. Is it possible to do that in decentralized way, just by trusting that miners collectively will pick something random? No, of course not. No matter what previous miners did, the last miner can roll the dice 6 times and on average it will be enough to get any result that miner wants. If you have some huge number like seed, it is not so trivial to get any result you want. But you still can compute something N times and make the seed N times weaker than it should be.

Also notice one thing: if you have something that is based on some block hash, then it is already based on the whole chain of blocks from the Genesis Block to the chosen block. So, the question is: if all block headers contain a field called "previous block hash", then why taking N blocks is better than taking a single block?

[pooya87]

No matter what previous miners did, the last miner can roll the dice 6 times and on average it will be enough to get any result that miner wants.

You are assuming that finding a block is easy. The miner has to compute a massive number of hashes to find a single hash for that block, if that result is not desirable they have to compute the same massive number of hashes to compute another hash. It is not financially feasible to do so, not to mention that mining is a competitive thing and if the first miner doesn't publish the first result other miners will find their own block and publish it.

[BlackHatCoiner]

Also notice one thing: if you have something that is based on some block hash, then it is already based on the whole chain of blocks from the Genesis Block to the chosen block. So, the question is: if all block headers contain a field called "previous block hash", then why taking N blocks is better than taking a single block?

That is true. Note that we're trying to minimize the trust required, not to eliminate it completely. As said by pooya87, they ought to be very discouraged to carry out such attack financially.

Same happens with Bitcoin and the Lightning Network. There's trust that an entity won't behave maliciously and reverse blocks or broadcast an old commitment while you're not online, but they're very discouraged to do so financially and therefore, trust is highly minimized.

[kaggie]

The problem is that you want two counteracting things:

1) A number which is not influenced for random behavior
2) A number which everyone knows for deterministic behavior

1 and 2 simply can never be ideal together. When everyone knows the number, then we are all susceptible to whatever weaknesses that number carries. We need some determinism to decrypt.

The next best thing is ensuring that whatever number is chosen does not have spectral weakness, which takes openness and planning to achieve.

Also consider that these are limited algorithms. There would be more interesting algorithms -- possibly by varying the seed along the process, but you still need something deterministic, and varying the seed might make it less random.

How about this: why are you limited to those 5 words in the seed number? Can you use more numbers, or a longer number? There would be something historical about this, probably accessibility for the most number of people, but for advanced users? You should be able to get a longer seed number that are much harder to determine patterns for.