[cryptography] The Wandering Music Band

realcr realcr at gmail.com
Thu Jan 8 13:16:06 EST 2015

> Sorry, I should've read your formulation more carefully.

Don't worry about it :) We wrote lots of stuff since the first message,
it's hard to trace it back to the original message.

@Natanael: I think I understand now that our different opinions are due to
different concepts of adversarial model.

You are implicitly assuming that NONE of the previous versions of the group
> will ever have a majority of members that are dishonest and pretend the
> later reassignments didn't happen.

Michael wrote:

the same problem exists if any version of the band contains a dishonest
> majority.

My short answer to this: (The long answer follows below)

- You have to wait a very long time until there is not a majority of
correct nodes in the band.
- The network is maintained in such a way that you pay for membership.
Therefore the Adversary will not be able to stay long enough.

The long Answer:

Assume that there is some network of nodes. Some of those nodes are
correct, and some of them are corrupt.
Correct nodes are honest. They run your code. Corrupt nodes can do
anything. (They can collude, etc). All the corrupt nodes are controlled by
one Adversary.

Also assume that it costs something to be in the network. Something that
you pay periodically.
(It will take me some time to explain what is that thing, so just assume
it's true). In addition, it is given that the Adversary is bounded.
More specifically, the Adversary can maintain (1/4)n corrupt nodes for some
time. The rest (3/4)n nodes are correct.

Let S be the band. It is some set of k nodes, where at least (2/3)k are
correct nodes.

In every step one of the following happens:

- A random node (from the set S) leaves the set.
- A random node (from the world) joins the set.

The set is always of size at least k. k ~ polylog(n). You can think of k as
log(n)^2, for example.

I conjecture that the amount of correct nodes in the band will stay above
(2/3)k for many steps.
To make this conjecture more rigorous, I include here a very approximate

Assume that in every step we get a random set, chosen uniformly from all
the nodes in the world.
If we assume that the world is really big, a binomial distribution should
be a good approximation.

We should calculate the probability of having less than (2/3)k correct
nodes in a random set of size k.
That would be about p_f := Pr[ B(k,3/4) <= (2/3)k ].  (p_f stands for
probability for failure).
By Chernoff's inequality, we get that p_f = Pr[ B(k,3/4) <= (2/3)k ] <=
exp(-C * (1/k) * ((3/4)k - (2/3)k)^2) = exp(-C * k)

If we pick k = log(n)^2, we get p <= exp(-C * log(n)^2) = 1 / ( n^(
log(n)*C ) ).

If I have not made any fatal mistake here (I might have, I calculated it
just now :) ), then we conclude the following:
If the network is of size n=2^30, then one have to wait about (2^30)^30 =
2^900 steps until there is no majority of correct nodes in the band.
I consider 2^900 steps to be "never happens".

Of course this is not the real calculation. The real one involves some
Markov chain, and I don't know how to solve it.
But I think it does give some idea regarding what I should expect.​
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150108/b23321f0/attachment.html>

More information about the cryptography mailing list