[cryptography] The Wandering Music Band

Natanael natanael.l at gmail.com
Thu Jan 8 08:39:11 EST 2015

Den 8 jan 2015 13:00 skrev "realcr" <realcr at gmail.com>:
>> You still don't get any meaningful security if old band members are
assumed to be untrusted and you don't use a public checkpointing mechanism.
Transfer of the title of being the real group must be a one-time only thing
for each version of the group, and must be impossible to backtrack from.
Bitcoin enforces this by design.
> If you are worried about Synchronization issues within the band itself: I
don't need Bitcoin to solve it. The Band is small, and it has a majority of
correct members.
> Therefore I can use some secure multiparty computation to take decisions
within the band, and also remove and add members securely.

Synchronization among existing band members is not the problem I'm talking
about here. As I tried to explain previously, making sure that the verifier
can be certain there is no reassignment of the title of being the official
band that is more recent than the one he is shown is the problem. The
verifier MUST be certain that no further reassignments could have been made
without his knowledge.

This is the same thing as what Michael also described.

If band S_n contains none of the original members, *S_1 will still have
their fully cryptographically valid (although deprecated!) private keys and
title transfer chain*, all they have to do is to pretend no further
reassignments have happened.

Every previous version of the group that do not share any of the current
members can conspire against the current version of the group, with them
being *helpless* in trying to prevent it. Your only plausible defense
against this is fairly short expiration dates and frequent reassignment.

Versions that share group members with the current version can persuade
those members to join the conspiracy.

You don't seem to grasp the consequence of this situation based on your
replies. 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.

Over long periods of time, you may have hundreds of unique sets of group
members composed of several dozens of individuals not part of the current
group, ALL of which only needs a small majority of colluding members to
generate a fake chain of history.

The probability of old members defecting and of group versions with
majorities of colluding members appearing increases over time.

You can only avoid this by having all transfers being public verifiable

Blockchain based systems are the only ones designed to require no
centralized trusted third party and yet provide an assurance that all the
statements made in its data structure is fully self consistent.

Other hash chained mechanisms like Git and digital notary services prove
nothing other than the existence of the claims, not their validity. With
such systems one must show ALL entries to the verifier, which is much much
worse than Bitcoin. Otherwise you have no chain of transfers you can
declare official.

You need reliably self-consistent data structures from a trusted source.
Bitcoin provides an economic assurance of trust (it is unprofitable to
create fake chains).

Using a federation of trusted notaries á la Ripple is your only other
choice. But who do you trust for this?

>> I think you overestimate the impact of using Bitcoin.
> My problem was that the naive solution makes every band keep a linear
amount of signatures with respect to time, which is too much.
> As a solution you proposed Bitcoin, where all the network participants
will remember everything from the beginning of time. That's the opposite of
what I'm trying to do.
> I made sure that every operation in the network result in no more than
O(polylog(n)) operations. I am definitely not going to use Bitcoin on it,
where every transaction costs O(n) network complexity.
> (Not mentioning the proof of work calculations). It doesn't make sense to

The version with Zero-knowledge proofs requires just a few megabytes of
storage for verifying nodes and for the band with full security (blockchain
headers, two transactions, the latest ZKP).

Although generating the ZKP wasn't log(n), I accidentally skipped a few
steps, but O(n+log(n)) of TOTAL computational cost in any given timeframe
(generating proofs for every colored coin transaction being linked to the
previous one plus merging those checkpoints with another set of ZKP's)
isn't much. You don't need to verify the raw blockchain data twice. Just
that the current transaction follows the previous ones proven by the ZKP.

The proof-of-work is independent of the group members, you don't need to be
a miner.

Storing the full blockchain will not be very expensive, even a growth rate
of a terabyte a year is manageable for full nodes thanks to cheap
harddrives. And everything not in the UTXO set (transactions already spent,
such as old colored coin transactions) can be archived in low bandwidth
secondary systems.

>> It isn't all our nothing as not all members need to be full nodes, in
fact none of them have to be.
> What if everyone did that?  Bitcoin will stop working properly. (Or it
will become central, and that is what Bitcoin tries to avoid from the first

It isn't very expensive, and even 10 000 transactions per second is
manageable with a 100 Mbps connection.

> I It might be true, but it is still O(n) network complexity per
transaction, and lots of proof of work calculations.
> The naive solution proposed in my first message will still outperform the
most efficient Bitcoin based solution. (Because it is O(log(n)) network

The proof-of-work difficulty is fully independent of the transactions
involved. The proof-of-work self-adjusts to make sure there's on average
one block every 10 minutes. The proof-of-work is done by computing SHA256
on a Merkle tree hash of the transactions plus a nonce. Neither storage,
bandwidth nor computation is a big problem.

Again, federated trusted notaries is your only other reasonable choice, but
as I said above, who do you trust for this job?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150108/b284a3cb/attachment.html>

More information about the cryptography mailing list