[cryptography] The Wandering Music Band

Natanael natanael.l at gmail.com
Wed Jan 7 17:35:09 EST 2015

Den 7 jan 2015 22:14 skrev "realcr" <realcr at gmail.com>:
> Hey,
> Thank you for all the responses. I figured out that I left some important
details out, probably because I thought about it for a long time. I'm sorry
about that.
> I will try to formulate it again:
> 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.
> (
> The band always have at least k people.

It's the chain of signatures always published in an accessible way so that
the original members can't "doublespend" and claim to be the task group?
Otherwise the blockchain approach is useful for you.

The Bitcoin blockchain solves the problem of trustlessly transferring
ownership. The group setting is also solved as-is thanks to both the
multisignature support (m-of-n for up to 15 people), and thanks to ECDSA
threshold group signatures if you prefer these (I'm assuming they also
don't limit you to 15 members).

Group S_1 creates a "colored coin" by sending the smallest denomination of
Bitcoin to an address created using the public keys of all current members
(must not be mixed with other coins). The threshold is defined such that m
must be larger than half of n (the size of the group).

When any change is made, group S_2 is then created and the colored coin is
sent to a new address created from the public keys of all members in this
new group, and the threshold is adjusted if necessary.

Keeping only the blockchain headers and asking Bitcoin nodes for the
transactions following the original colored coin transaction (SPV security
model), you can track it to the latest address, and thus to the latest
version of the group, the current descendant (S_n).

You can verify that the group member(s) you meet is indeed part of the
current version of the group by asking them to sign a nonce as a challenge
with their private key and show the rest of the public keys from the group
(such that the Bitcoin address can be recreated, to verify his public key
is part of the group).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150107/5477b166/attachment.html>

More information about the cryptography mailing list