I have a network of $N \gg 1$ nodes. Some relatively low fraction $p$ (e.g., $p \simeq 0.01$) of them is under the control of a malicious attacker. Nodes can talk to each others and verify each other's identity (i.e., when a node communicates with another one it can verify the other's identity and membership to the network).
Now, I need my nodes to agree on a random number. It should be the same random number for all the nodes, and it should indeed be random. In other words, the malicious attacker shouldn't be able to steer the distributed random number generation to produce a number of its choice, unless $p$ is larger than some reasonably large amount (e.g. $0.1$).
Is there any way to do so with $O(N \log(N))$ communication complexity? For example, a trivial way of doing this with $O(N^2)$ communication complexity is that each node generates a random number, hashes it with a secure hash and communicates it to all the other nodes. When all the commitments are exchanged, everyone sends out its own random number, and all the numbers are XOR-ed or modulo-summed or so. But this is expensive in terms of communication, and definitely not scalable.
What I need this for
I am developing a peer to peer storage network, where a potentially very large set of nodes contribute to storing each other's data. I am working under the assumption that only that fraction $p$ of the nodes is malicious and willing, e.g., to corrupt or make unavailable some data. Now, I am using a redundancy protocol where a group of, e.g., 36 nodes store each other's data using an erasure code that allows up to 12 nodes to be wiped before the data is lost. This is nicely reliable, as long as the attacker has no way to infiltrate more than $12$ nodes in any specific group. Since $p$ is small, if I have a way of organizing the nodes into groups at random, the probability of any group having more than $12$ malicious nodes is vanishingly small.
This is why I need globally verifiable random numbers: I need all my nodes to be certain that the groups they have been organized into are really random.