[cryptography] The Wandering Music Band

realcr realcr at gmail.com
Thu Jan 8 08:21:25 EST 2015

```>
> Now the original members b,c,d create an alternative history:

I assume that the original band has a majority of correct members.
Therefore at least two out of {b,c,d} are correct, and they will not create
alternate history.

The original formulation is included:

Assume that the world contains correct people (People you can trust) and
> corrupt people (Those you can't trust).
> Also assume that the world has a majority of correct people (If it helps,
> you may assume 3/4 correct people).
>
> I am given a set S which contains k members (The music band). Assume that
> a majority of this set is correct.
>
> From time to time:
> -  A random person (From the world) joins the band. (With good probability
> this new member is correct).
> -  A random person (From the band) leaves the band.
>

On Thu, Jan 8, 2015 at 2:38 PM, Michael Rogers <michael at briarproject.org>
wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> On 08/01/15 07:03, realcr wrote:
> > I think the naive solution I proposed in my first message is more
> > efficient than using Bitcoin, because it does not involve proof of
> > work or flooding stuff.
> >
> > Shortly: Whenever a person is added to the band, all the members
> > sign on the new list. Whenever a member leaves the band, all the
> > members sign on the new list. The band members keep the signatures
> > forever, so they can always prove they where formed originally from
> > the original band S.
>
> I think there might be a problem if a majority of members leave the
> band one by one and then construct an alternative history:
>
> band_0 = {a,b,c,d}  // original lineup
> band_1 = {a,b,c}    // d leaves
> band_2 = {a,b,c,e}  // e joins
> band_3 = {a,b,e}    // c leaves
> band_4 = {a,b,e,f}  // f joins
> band_5 = {a,e,f}    // b leaves
> band_6 = {a,e,f,g}  // g joins
>
> Now the original members b,c,d create an alternative history:
>
> band_0 = {a,b,c,d}  // original lineup
> band_1' = {b,c,d}   // a leaves
> band_2' = {b,c,d,h} // h joins
>
> Which is the true lineup, band_6 or band_2'?
>
> A verifier who's seen both histories can tell that b and c have signed
> inconsistent statements. But how can a verifier know whether they've
> seen all histories that might exist?
>
> Cheers,
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.12 (GNU/Linux)
>
> iQEcBAEBCAAGBQJUrnpiAAoJEBEET9GfxSfMEqIIAK8ZHAE4XzAmVYg3A7z2kWJA
> mUHNoNMHf7198NLH9ddMrLOmKbGYWRko/6VY6dStx8Na3E0O1nAZVO2vdK9oTlBJ
> v6O6mmgAuAnG4oKAn3+KQHhGIxIUmsOn7vHTgF6X6l7JlgEnEhwNQ2GZ5azbyEnb
> iSxAjy1cnH4uWV8On8nFrBRfv1BkcizoclX1hBxF9b2v0+psNLbS0/EIFuGkonfx
> CYGRC117saH9t//kwEZEAk2b8PeNENb/memS4beBJdQNe0oMaiKV/rxXgf2IwnpX