4 ms·

1. everyone generates n-bit random number. 2. all random numbers are XOR'ed together. The result is as random as the most random number provided. XOR can be

by nabla9 6y ago

1. everyone generates n-bit random number. 2. all random numbers are XOR'ed together. The result is as random as the most random number provided. XOR can be done in any order and any combination and it produces the same result. Complexity is log(n) XOR operations. No need for everyone to be connected to each other

sanity31415 6y ago
Appreciate the suggestion. That's fairly similar to the first algorithm I described except without the initial hash commit step, but I think it shares the same problem which is that I don't see how it could scale up to tens of thousands of peers, with peers constantly leaving and joining the network.
- nabla9 6y ago
  Nodes can come and go. They just have to talk few neighbors. If you want every node over some time period participating, you can't do faster than than log2(n) XOR operations. (in above comment I said O(n) xor's, that's obviously wrong. You need only log(N) xor's)
Someone 6y ago
But in many cases, you want all parties to be able to confirm fair play. In this example, if any of ‘everyone’ can see all the other n-bit random numbers before broadcasting their n-bit number, that party had complete control over the result of step 2. One way to solve that is by appointing a party P to do step 2, have all parties communicate their number to P in private, and then have P do the XOR. Problem with that is that you have to trust party P. Even if you require it to not only report the result of step 2, but also all the numbers generated in step 1, P can collude with one of them to generate any result those two parties want to generate, and all parties can claim they didn’t send P the number P says they sent him if they’re not happy with the result of step 2. A better approach: - each party picks a random encryption key - each party encrypts their n-bit number with that key - each party broadcasts the encrypted number to the world - once a party knows that all parties have seen all encrypted numbers (how to know that is left as an exercise for the reader), it broadcasts its encryption key. - eventually, all parties will have seen all encryption keys. - once a party has all encryption keys, it can decrypt the encrypted n-bit numbers and XOR the results. Even ignoring the exercise for the reader, the above likely has holes. I’m not an expert in this field. https://en.wikipedia.org/wiki/Byzantine_fault https://en.wikipedia.org/wiki/Byzantine_fault probably is a better starting point for this kind of problem (but doesn’t give a solution to this specific problem)

by nabla9 6y ago

sanity31415 6y ago

Appreciate the suggestion. That's fairly similar to the first algorithm I described except without the initial hash commit step, but I think it shares the same problem which is that I don't see how it could scale up to tens of thousands of peers, with peers constantly leaving and joining the network.

nabla9 6y ago
Nodes can come and go. They just have to talk few neighbors. If you want every node over some time period participating, you can't do faster than than log2(n) XOR operations. (in above comment I said O(n) xor's, that's obviously wrong. You need only log(N) xor's)

Someone 6y ago

But in many cases, you want all parties to be able to confirm fair play. In this example, if any of ‘everyone’ can see all the other n-bit random numbers before broadcasting their n-bit number, that party had complete control over the result of step 2. One way to solve that is by appointing a party P to do step 2, have all parties communicate their number to P in private, and then have P do the XOR. Problem with that is that you have to trust party P. Even if you require it to not only report the result of step 2, but also all the numbers generated in step 1, P can collude with one of them to generate any result those two parties want to generate, and all parties can claim they didn’t send P the number P says they sent him if they’re not happy with the result of step 2. A better approach: - each party picks a random encryption key - each party encrypts their n-bit number with that key - each party broadcasts the encrypted number to the world - once a party knows that all parties have seen all encrypted numbers (how to know that is left as an exercise for the reader), it broadcasts its encryption key. - eventually, all parties will have seen all encryption keys. - once a party has all encryption keys, it can decrypt the encrypted n-bit numbers and XOR the results. Even ignoring the exercise for the reader, the above likely has holes. I’m not an expert in this field. https://en.wikipedia.org/wiki/Byzantine_fault https://en.wikipedia.org/wiki/Byzantine_fault probably is a better starting point for this kind of problem (but doesn’t give a solution to this specific problem)