Den 8 jan 2015 13:00 skrev "realcr" <rea...@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 information. 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 me. 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 place.) 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 complexity). 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?
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography