If the private key is recoverable through reused R values, then all keys and addresses in that account is vulnerable.

xbit

Because the sourceforge mailing list archive seems broken:

https://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg04918.html

The generic term is Secure Multiparty Computation (usually abbrevated as MPC). I've been thinking of doing all kinds of round-based games this way together with Bitcoin and optionally with anonymizing networks like I2P. All kinds of cools things could be done this way, including reputation tracking and setting up tournaments. If done right it could practically be cheat proof. (It would however be harder to verify that somebody with 1000 wins haven't been playing against his own 1000 fake accounts.)

Are anybody interested in a notary based system with temporary pay-to-script-hash wallets (P2SH) using multisig transactions?

My scheme requires no Bitcoin protocol change, and requires very limited trust in notaries which can be replaced quickly and where malice is easy to prove (just show two conflicting transactions that both got signed, these can be distributed globally in seconds to everybody that has set their clients to trust that notary). This means that notaries has practically nothing at all to gain on an attack, and still makes 0-confirmation transactions trustable.

http://roamingaroundatrandom.wordpress.com/2013/11/30/bitcoin-idea-temporary-notarized-wallets-secure-zero-confirmation-payments-using-temporary-notarized-p2sh-multisignature-wallets/

I've got an idea for how to use notaries and P2SH addresses with multisignature transactions to make zero-confirmations transactions secure for merchants.

The full text is here: http://roamingaroundatrandom.wordpress.com/2013/11/30/bitcoin-idea-temporary-notarized-wallets-secure-zero-confirmation-payments-using-temporary-notarized-p2sh-multisignature-wallets/1

The thread on Reddit: http://www.reddit.com/r/Bitcoin/comments/1rsg78/bitcoin_idea_temporary_notarized_wallets_secure/

The TL:DR (kind of);

Using the scripts feature and pay-to-script-hash addresses, you create an address that for the first 24 hours only allow you to spend if a notary sign your transaction. Notaries have no incentive to enable a doublespend since it would be discovered nearly instantly and can be easily proven causing a total loss of trust. A merchant that trust the notary in use can accept transactions from these addresses with zero confirmations if there's about an hour or more left of the time window for notarization requirement, as they can be confident that no doublespend transactions will be accepted by the network as it won't have a valid signature, so they can be confident that the notarized transaction with the payment to them will be confirmed in the blockchain long before the buyer has any chance of making a doublespend transaction.

After 24h there's no longer any notary signature requirement, so if the notary shuts down your money isn't lost.

You should add Shamir's Secure Sharing Scheme support for additional security AND loss/destruction prevention.

The technical part of it sounds a lot like my idea about a generic crypto device that I've written about before. Although I want it to have a screen and input of it's own. Posted it on reddit on /r/crypto and /r/netsec, but can't find a link...

Edit: found it: http://www.reddit.com/r/crypto/comments/yjxdo/device_concept_universal_personal_cryptography/

Your node offers storage space for a price. Clients pay. You store the files. You can integrate proof of storage and more and use Bitcoin's scripts to make sure neither side is at a significant risk of getting screwed over. It's not like it can't mimic most of the features of Bitstorage.

Sarchar: That can be added easily. You could simply rent out storage space.

Please look up Tahoe-LAFS, and how it can be used with I2P! Tahoe-LAFS is developed by experienced computer scientists and cryptography experts. I2P is an anonymization network. The combination is a far more flexible and advanced decentralized storage system than Freenet, and is under active development with flexible access control features.

https://www.i2p2.de and https://tahoe-lafs.org

There's actually an efficient MPC protocol now that appears to be as secure as my scheme requires! (Which I personally use to call SMPC = *secure* multiparty computation)

http://phys.org/news/2013-09-breakthrough-cryptography-result.html - also links to it's paper

Hopefully it will be released as open source as well.

I don't see how that solves anything. You just openly linked your own inputs together yourself, then.


General SMC/MPC (myself I usually abbreviate it as SMPC) does exist. But it seems to be less efficient than specific ones like for sorting. I am eagerly waiting for efficient general SMPC to become usable for average joes.

Why have servers at all? With I2P it would also be really easy to use DHT to set things up. Instead of a unique URL you could have a unique random string of any kind. Or even fully random peer selection.

Backdoor covenant - Normally like a regular coin, but an arbitary payload can be attached to it at any point in time through a transaction by the creator of the covenant. When spending it, there's a check for the lastest signed payload for it in the blockchain, and that is then executed.

Viral Proof-of-Work-Verified Payload Backdoor Covenant - Like the above, but here you are required to attach the covenant to another coin when spending this one, and *anybody* can attach a payload to it through proof-of-work, where the payload with the computationally hardest proof-of-work generated so far is the one who is executed when you spend the coin. The proof-of-work is of course individual for each instance of the VPoWVPBC.

The risk of DoS in many of these cases could make the entire scheme unusable for as long as it's decentralized, as you can't really effectively ban the attacker. If the attacker can run 20x as many fake nodes as there are real nodes and abuse the scheme to only spend a trivial amount of computing power and bandwidth, while making the real users waste lots of it, then the system is trivially rendered unusable. Just throw a botnet at it and it's dead.

That's why I'm thinking hard on DoS prevention.

Edit: Also, regarding change addresses: You should split up your change in several parts. If everybody does that and thus generally also refers to multiple inputs for the transaction as a result, then correlation based on the BTC sums is much harder.

Edit: https://bitcointalk.org/index.php?topic=12751.msg315793#msg3157931 - So somebody else had the same basic idea over 2 years ago. Although my version (who originally was almost identical to his) now accounts for various types of possible attacks.

It isn't certain that you'd be able to tell WHICH input that the attacker used, at least not with my scheme where you hide who's using what input. Revealing who's using what input might not be optimal if a user want to use inputs already tied to himself AND some inputs that aren't already, and doesn't want the unlinked ones to become linked to him.

Also, it's hard to convince other that the attacker maliciously broke the scheme where none of the participants has any long-term pseudonym, thus it's hard to blacklist that one input. Also, a single input can STILL be used many times simultaneously, even if not many times in a row.

I don't have enough experience with programming, and absolutely not of crypto implementations, to be able to make a proper proof-of-concept of this, sorry. I'm hoping that somebody else *who does* will find this interesting enough to implement.

So far I'm thinking that my two-round version SMPC scheme with initial PoW before starting SMPC would be pretty decent, where you'd remember which pseudonyms that mixing has worked with in the past. Participants that don't supply PoW is ignored, and to stop a sybil attack where many nodes don't do PoW to try to make you calculate PoW for nothing you'd connect to multiple dozens of random nodes at once.
Edit: If the SMPC was given bad inputs, it would also reveal who it was that gave it the bad inputs (if it were to finish, but giving bad inputs + interupting the SMPC is just wasteful from an attacker's point of view).

And by the way, I'm one of those who wants the system to be as solid as possible in advance. Nobody deploys bad encryption algorithms and try to patch the algorithm as flaws is found. Not that I think that the other suggestions is bad, but I don't want people to get screwed over because somebody forgot to consider a simple attack that a little bit more analysis would have revealed and maybe shown how to stop.

Ok, so coin age would be your DoS countermeasure?

Note that attackers don't actually have to spend that input if they disrupt the protocol. They can use the same one over and over, even many times simultaneously.

PoW could be an option where participants can set a minimum PoW accepted and a maximum PoW they're themselves willing to perform. So for example if 10 people all have 2^15 work within their range of acceptable PoW (one has 2^15 as their lowest, another as their highest, they'll all generate a common input for PoW and start working on it. Then they start this scheme with the SMPC. That would indeed make the attack costly for somebody trying to break the scheme for as many as possible (DoS) and would make Sybil very costly.

I don't see how that would help countering DoS, you won't likely be reusing inputs so there can't be reputation tracking.


It was a bit more than that IIRC. It was highest bid wins, with winner paying the price set by the second highest bid, and it was NOT just two or three participants, it was a LARGE auction. A very large amount of offered goods and bids.

Besides for risk of sybil+correlation attacks (which can be partially countered through reputation tracking), I like my SMPC scheme.

gmaxwell: Yes, in the last part of that comment, that's what I suggested.

If a pseudonym is reused often, then correlation could be used to link all inputs with the pseudonym that provided them. This could the be further used to see if outputs from mixed transactions that the pseudonym in question has been part in often has some outputs in common, thus deanonymizing users who use this frequently for the same outputs (assuming the recipient has repeating or non-individual payment/donation addresses, which is common).

I've read that SMPC has been used IRL successfully for auctions for farms selling their goods. Can't remember the source. SMPC should be possible to run on most hardware. There's multiple implementations of it, some in Java and some in C.

How would a homomorphic mix work?

Two-round SMPC could certainly work, where the inputs simply are the individual signatures plus the previously unsigned transaction, creating a properly signed transaction.

Edit: SMPC implementations:
FairplayMP: http://www.cs.huji.ac.il/project/Fairplay/
Sepia: http://www.sepia.ee.ethz.ch/
Viff: http://viff.dk/
SIMAP (nothing available for download?): http://ny.alexandra.dk/uk/labs/Security-lab/Pages/Secure-Multiparty-Computation.aspx

I have one suggestion that among others uses Secure Multiparty Computation (SMPC). https://en.wikipedia.org/wiki/Secure_multi-party_computation

Step one: Peer finding is done using a DHT network. This can be done inside I2P or Tor if you want to for increased anonymity. You might want to do reputation tracking where nodes uses public-key based pseudonyms (if you reuse a pseudonym, you must make sure to not spend inputs that can be tied to you personally more than just once (or rather not more often than the average, some identifiable inputs might by chance be involved with the same 3rd party multiple times) with that pseudonym since it otherwise can be directly correlated with your pseudonym).

To make verification of inputs simple and quick, each client keeps an updated Merkle tree hash of all currently valid spendable outputs in the blockchain (basically those that not have been spent yet) in this form: [Address]-[Transaction ID]-[Amount of BTC].

The SMPC uses cryptography to emulate a trusted 3rd party computer, running code all participants have agreed on. Unless a majority of the participants collude (Sybil attacks are a potential issue, be careful about who you run this with), no participant can get any other information out of it than they are *supposed* to get out of it.

Now, everybody puts in their transactions and their private keys for them. The SMPC checks if all participants really have the correct private keys for the (valid) previous outputs they claim as inputs through checking what addresses they correspond to, what transaction ID was claimed and how many bitcoins are claimed, and checks this data against the Merkle hash tree.

It then checks that the outputs aren't larger than the inputs. A transaction is then generated with all the user provided inputs and outputs, and signs it with all the private keys.

The signed transaction is given as an output to all the participants, and any one of them can publish it (or all of them at once).

Nobody can know which transactions came from whom, other than that they know their own. Out comes a signed Bitcoin transaction that includes them all in one. Either everything gets signed properly or it exits with an error. The protocol doesn't allow the generated transaction to be created in any other way than the correct way. All user specified outputs will be included, all user specified inputs will be included, no user can specify larger outputs than inputs (unless everybody agrees), etc...

The only major risk here is that of a Sybil attack (a large number of colluding nodes), and the major risk in here is private-key disclosure, the second is identifying which pseudonym spent what input. I hope that we can get around that somehow. One possible way is to not have the private keys provided to the SMPC, but to use simply prove you have the private key through signing a challenge of some sort, where the challenge can be a random number that is a checksum of all random numbers provided as inputs by the participants, so you only need one signature per participant. The SMPC would then only output an unsigned transaction, where all participants needs to sign it. The question then is how they all share their signatures with the other participants, ideally they should be able to hide that it came from them. Chaumian blinding could maybe be used in this step.

If you decide to not use blinding (to just pass on your signature), and not use any permanent pseudonym of any kind, then you'll have a risk of DoS attempts through both doublespend attempts (making the generated transaction invalid) and through canceled SMPC runs at the last step (thus wasting CPU power).

My intent is to make the system as automatable and fast as possible while maintaining full security.