As Barbie said: Math is hard

Like it or not a lot of wallet and related software out there is being developed by people who would be able to handle some hashing and encryption primitives, but not that.


Ask yourself: why do you need Tor or I2P for this protocol? Remember that even requiring Tor is a big barrier to use.

Anyway as I've said before given that we want the majority of all transactions to be done with CoinJoin, and because the overhead of arranging CoinJoin tx's can be a small multiple of existing tx traffic, there's every reason to broadcast CoinJoin traffic on the Bitcoin p2p protocol itself. This also demands low bandwidth solutions, which multi-party RSA isn't.


I'm focused on mixing because it's the most pressing need right now - indeed the reason why I suggested the idea of a bounty and the name "CoinJoin" to gmaxwell in the first place. Auction bids and groups buys are much more niche things, and farther off in the future. In any case the privacy problems of them that make blinding useful are greatly lessened if obtaining anonymous coins is easy in the first place.

Your example of a facilitator is also much less important if CoinJoin is well used: if 10% of the transaction volume used CoinJoin you'd only have to wait a matter of seconds or maybe minutes anyway to mix coins.


That's fine, but I do want people to understand that if that's what you are doing, their money will take a lot longer to be turned into the goal of "fairly anonymous coinjoin tx's everywhere" than it could otherwise. To be frank if you were focused on something targeted and pragmatic I myself would be willing to donate to the effort, but as it stands I'm not.


Well, myself I envisioned the CoinJoin fund as, well, a fund to be best used towards a goal. Put another way I always saw it more like donating to the Bitcoin Foundation, who in turn would vet proposals by others and allocate funds; this doesn't have to be a bounty in any way, and I think it was a mistake on gmaxwell's part to use that term.

FWIW I strongly think this is the wrong approach for a few reasons.

First of all we really want CoinJoin transactions to be the standard way to make a transaction, and integrated into many different wallets by default. To meet that goal you need an standard based on very simple cryptography that anyone can write - mucking about with RSA primitives, while easy for a cryptographer, still doesn't meet that standard and it won't be re-implemented widely. In addition requiring Bitmessage also makes implementations much more difficult due to the extra dependency.

The second issue is more subtle: fancy multi-party chaum blinding protocols don't have any advantages over 2-party mixes unless you can achieve sybil resistance effectively, and if they decrease adoption of CoinJoin resisting sybil attacks is much harder. Now if you're doing a mix among, say, people with active bitcointalk accounts or people with good OTR ratings chaum blinding is valuable: it's hard to acquire those identities and the participants would rather the other participants not know where their funds went.

But if you'll do the transaction with whomever is currently available, like over Bitmessage as you propose, the only thing preventing a sybil is the cost in transactions fees - trivial if there aren't that many participants. The (three-letter-agency) can just as easily pretend to be the other 4 partners in the transaction; it's just as dangerous to use a chaum blinded mix as a series of 2-party mixes. But if coinjoin is implemented in a way that everyone can use it in their wallets, which requires transactions to be fast and implementations to be easy to make, that same three-letter-agency has to spend a significant fraction of all transaction fees to have a good chance of sybil attacking coinjoin.

In contrast my two-party-mix protocol requires only off-the-shelf cryptographic primitives, uses only one primitive - encryption to a ECC pubkey - not already used by standard Bitcoin wallets, includes a inherently DoS-resistant way to arrange the mixes over the existing P2P network, makes the PoW mechanism denominated in Bitcoins so attackers with custom hardware have no advantage over the defenders, has very low bandwidth costs, and can be easily done as a "by default" thing that wallets do for every transaction made.

I really think you should either make the bounty be for implementing that protocol, or make the bounty be for implementing a toolkit for groups - like the bitcointalk example - to arrange chaum-blinded mixes for their members. It's the latter application where the complexity of chaum blinding is really valuable, but for the former using chaum blinding is a good example of cryptographers getting enamored by fancy math and forgetting about the human factors of the systems they build.

FWIW I'm planning on writing a two-party-mix implementation myself, but I've got a day-job and I know I won't be able to finish it as fast as you could if you received funding; seeing it actually get implemented and integrated into widely-used wallets is much more important to me that getting credit for making it happen.

Rewards at the following P2SH addresses are available for anyone able to demonstrate collision attacks against a variety of cryptographic algorithms. You collect your bounty by demonstrating two messages that are not equal in value, yet result in the same digest when hashed. These messages are used in a scriptSig, which satisfies the scriptPubKey storing the bountied funds, allowing you to move them to a scriptPubKey (Bitcoin address) of your choice.

Further donations to the bounties are welcome, particularly for SHA1 - address 37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP - for which an attack on a single hash value is believed to be possible at an estimated cost of $2.77M (4)

Details below; note that the "decodescript" RPC command is not yet released; compile bitcoind from the git repository at http://github.com/bitcoin/bitcoin

SHA1:

$ btc decodescript 6e879169a77ca787
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP"
}


SHA256:

$ btc decodescript 6e879169a87ca887
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA256 OP_SWAP OP_SHA256 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "35Snmmy3uhaer2gTboc81ayCip4m9DT4ko"
}


RIPEMD160:

$ btc decodescript 6e879169a67ca687
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_RIPEMD160 OP_SWAP OP_RIPEMD160 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "3KyiQEGqqdb4nqfhUzGKN6KPhXmQsLNpay"
}


RIPEMD160(SHA256()):

$ btc decodescript 6e879169a97ca987
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "39VXyuoc6SXYKp9TcAhoiN1mb4ns6z3Yu6"
}


SHA256(SHA256()):

$ btc decodescript 6e879169aa7caa87
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_HASH256 OP_SWAP OP_HASH256 OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "3DUQQvz4t57Jy7jxE86kyFcNpKtURNf1VW"
}

and last but not least, the absolute value function:

$ btc decodescript 6e879169907c9087
{
    "asm" : "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_ABS OP_SWAP OP_ABS OP_EQUAL",
    "type" : "nonstandard",
    "p2sh" : "3QsT6Sast6ghfsjZ9VJj9u8jkM2qTfDgHV"
}

For example, this pair of transactions created, and then collected, an
absolute value function bounty:

0100000001f3194f7c2a39809d6ea5fa2db68326932df146aaab7be2f398a524bd269d0b6200000 0008a473044022039bc13cb7fe565ff2e14b16fbc4a9facd36b25a435d2f49de4534463212aeaee 022076413c7591385cd813df37d8104dd8110745c28178cef829b5ab3e56b7c30d22014104d3477 5baab521d7ba2bd43997312d5f663633484ae1a4d84246866b7088297715a049e2288ae16f16880 9d36e2da1162f03412bf23aa5f949f235eb2e7141783ffffffff03207e7500000000001976a9149 bc0bbdd3024da4d0c38ed1aecf5c68dd1d3fa1288ac0000000000000000126a6e879169907c9087 086e879169907c908740420f000000000017a914fe441065b6532231de2fac563152205ec4f59c7 48700000000

0100000001f18cda90bbbcfb031c65ceda17c82dc046c7db0b96242ba4c5b53c411d8c056e02000 0000c510181086e879169907c9087ffffffff01a0bb0d00000000001976a9149bc0bbdd3024da4d 0c38ed1aecf5c68dd1d3fa1288ac00000000

Specifically with the scriptSig: 1 -1 6e879169907c9087


Notes:

1) We advise mining the block in which you collect your bounty yourself; scriptSigs satisfying the above scriptPubKeys do not cryptographically sign the transaction's outputs. If the bounty value is sufficiently large other miners may find it profitable to reorganize the chain to kill your block and collect the reward themselves. This is particularly profitable for larger, centralized, mining pools.

2) Note that the value of your SHA256, RIPEMD160, RIPEMD160(SHA256()) or SHA256^2 bounty may be diminished by the act of collecting it.

3) Due to limitations of the Bitcoin scripting language bounties can only be collected with solutions using messages less than 521 bytes in size.

4) "When Will We See Collisions for SHA-1?" - Bruce Schneier -https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

With any luck you'll face competition from clones that realize the entire idea is just dumb. Are you planning to release the sourcecode to MasterCoin? Because if you don't, we'll all just say how it's probably got hidden backdoors that are going to steal all your (master)coins, and if you do release it, we can just take that code and remove the silly requirement for the exodus address/MasterCoins. Or just stick with, who was it, TierNolan and co's colored coins stuff?

Also, even if you want to use the colored coins paradigm, you actually don't need any data in the blockchain at all beyond what appear to be bog-standard pubkeys. Even better, is that you can design your protocol to really make it censorproof by allowing the colored coins to be included in standard CoinJoin transactions in such a way that anyone looking at the blockchain data will have no way of knowing what outputs were the colored coins.

Frankly the only clever thing you've done is you've taken the same colored coins/side-chains ideas everyone else has and found a way to get Bitcoin users to shovel money at you for it. Too bad really - I guess the rest of us couldn't imagine how you didn't even need to write any code to separate $300k worth of Bitcoins from the idiots who used to own them. (We forgot about The Pirate already!) Hopefully that's not actually true, and it's actually your own money and not many people are getting scammed here.

Anyway, I have better things to do than waste my time talking about ideas sufficiently stupid to be indistinguishable from scams for free, so don't bother replying unless you've got a paying contract. (1.5BTC/hr, escrow required for you)

I will say though, you're so close to doing something useful for me: showing the world how little protection we actually have against the UTXO set being bloated other than the blocksize limit. Do me a favor and keep your stupid protocol just the way it is.

For ECC multiplication there's Python code for it here: https://github.com/richardkiss/pycoin (look at the BIP32 support)

There's probably some BIP32 support written for bitcoinj as well; ask around.

Given how much money you've raised it'd be quite easy to pay someone to add support for OP_RETURN to those clients, among other things.

Read this: https://en.bitcoin.it/wiki/BIP_0034

2-party-mix proposal, as discussed on IRC:

First of all it has to be recognized that in a truly decentralized environment that are almost no protections against sybil attackers; the best you can do is make a sybil attack expensive. Because of this a n-party-mix with fancy cryptography is equivalent to an iterated 2-party mix. (even in an n-party-mix n-1 of the parties might be a sybil attacker) This is not true for the non-decentralized case, such as a mix where access is controlled by possession of a bitcointalk account, or a good OTR reputation.

Secondly in a 2 party mix the other party automatically knows what txins and txouts you are contributing to the mix by process of elimination. There's nothing you can do about that. However you can ensure that only that party knows, provided your counter-party doesn't reveal the info.

Thirdly the anti-dos limited resource should be denominated in Bitcoins, not proof of work or some other similar scheme; you want a large-scale attacker to have costs as similar as possible to a small-scale attacker and PoW functions are very susceptible to large improvements due to optimization. For Bitcoin's that optimization has already happened.

So, building on my previous thoughts earlier in this thread, I'm proposing the following basic mix protocol, here between Alice and Bob:

• 1) Announce: Alice states that she wishes to create a transaction.
• 2) Reply: Bob replies with the txins and txout he wishes to add to the transaction.
• 3) Sign: Alice signs her txins and sends the signatures to Bob.
• 4) Broadcast: Bob signs his txins, and broadcasts the transaction.

Step 1 happens in the clear; steps 2 and 3 can be encrypted to the pubkeys of the respective receivers.

For anti-DoS the act of broadcasting these messages can be made expensive by requiring the senders to include a nLockTime'd transaction spending a txin to a scriptPubKey the sender controls. Usually this txin would be used in the mix, although technically it doesn't have to be. The key idea here is that by broadcasting such a tx the sender is guaranteed to spend some tx fees somehow, either in the nLockTime'd tx, or in a different tx with the same txin. The actual amount of fees required per KB of data broadcast can be adjusted automatically by supply and demand.

Note how since tx fees are what is being used you automatically have sybil resistance: an attacker trying to be the counter-party to a large % of total traffic will need to either spend, or have access to the privkeys of, a large % of all the transactions being done on Bitcoin itself. While any individual transaction may get unlucky and fall victim to an eavesdropper, overall there is a significant privacy benefit.

As for the broadcast medium, like I suggested above, putting this data on the Bitcoin P2P network itself makes the most sense to ensure the widest possible usage. Similarly re: usage, note how the only cryptographic primitive used in the above protocol that is not currently used by Bitcoin wallets is asymmetric encryption. Being only two parties transactions can go through quickly when counter-parties are available, and they can timeout and fallback to standard transactions otherwise. Bandwidth usage is a small multiple of the transactions themselves; potentially less if return-path routing of the replies can be made to work properly.

FWIW I'm planning on implementing this, either directly in the satoshi client, or as a prototype in python-bitcoinlib. It's a good complement to more complex schemes utilizing multi-party cryptography primitives for mixes among semi-centralized groups.

You know, I just realized something: for every one of these cases it's better if the oracle reveals a seckey to a pubkey than if the oracle reveals a nonce. First of all, it means the oracle can prove they really do have the seckey by just signing a message, and secondly the two participants can take the oracles pubkey, and do an ECC multiplication with another pubkey that the two participants jointly agree on. Now they have a pubkey for which the seckey can only be found if the oracle reveals the oracles seckey, but looking at the blockchain there's no way to know what pubkey from what oracle was used to create the missing seckey, or even to know if the oracle had anything to do with it at all.

For instance, Alice and Bob are placing their bet on the 2013 superbowl. Oscar the oracle says if the Giants win, he will reveal seckey A' which corresponds to pubkey A, and if they lose, he'll reveal seckey B', which corresponds to pubkey B.

Now Alice and Bob jointly agree on a pubkey with a seckey that they both know, C. Then they pay their funds to the following scriptPubKey:

IF
    <A*C> CHECKSIGVERIFY
    <Alice's pubkey> CHECKSIG
ELSE
    <B*C> CHECKSIGVERIFY
    <Bob's pubkey> CHECKSIG
ENDIF

All the other steps are pretty much as above. Note how you don't even need to bother with any privacy stuff. You can also do it with 100% standard transactions with multisig:

2 <alice*A> <alice> <bob*B> <bob> 4 CHECKMULTISIG

Note that while only x-of-3 CHECKMULTISIG is valid as a bare scriptPubKey, you can have more pubkeys if you enclose it in a P2SH scriptPubKey. The only restriction is you have to be able to spend it with a scriptSig of no more than 500 bytes.

Sorry, I should have figured this out earlier!

What version of bitcoin are you running?

Can you paste the output of bitcoind getpeerinfo? (note that doing so may make it possible to find your IP address)

No, I'm dismissing offline transactions with hardware where getting n*100K of data to the device is infeasible. Microcontrollers these days are very fast - the Trezor for instance has a USB interface which is perfectly capable of getting a MB of data (10 txins given the 100K tx limit) over the wire in a second or two. QR codes are an issue, but by then you're talking about a single use-case.


Any protocol upgrade is controversial and takes a long time to implement - might as well knock off some other use cases.

For instance an alternate approach, as Mike hinted at, is a OP_CHECKSIG2. It'd be extremely valuable to make the SIGHASH flags more general, and in addition it would also be very valuable if you could sign a signature to spend a specific set of CTxOut's - scriptPubKey:value - rather than a specific COutPoint - txid:n - which would make transaction mutability far less of an issue. (also forces people to stop re-using addresses) We can add pubkey recovery at that point too, which makes transactions a fair bit smaller.

Again, you've got support from myself and gmaxwell, and it seems Mike, going down that approach. And again, remember that a set-based CHECKSIG with a merkle tree for the txouts allows you participate in big CoinJoin tx's without a lot of device overhead.

The big problem is it's specific to OP_CHECKSIG, and in the future it's quite possible that OP_CHECKSIG will be changed/made obsolete/who knows? Doing this via a SIGHASH bit is inelegant because it's so specific to a single use-case.

With a v2 transaction format, with a merkle tree extending into the tx and including a hash of the CTxOut structure being spent your hardware wallets would just take that data and operate only on that. For instance this is helpful if you are signing just a small part of a much bigger combined transaction with funds from multiple parties - there might be 1000 people chipping in to pay a large bounty for instance, and with a v2 tx format and set-based SIGHASH's your hardware wallet only needs to be given the small part of the txouts you are signing for.

Interestingly in that use-case your signature can still cover all the other txouts safely. Your wallet only needs to know that you've contributed xBTC of funds, and the txouts it knows about, via the merkle paths its been provided, are for (x-fee)BTC of funds. Perfectly safe no-matter what malware is on your computer, yet the outside world only knows that you added funds to some huge txout set. This is perfect for CoinJoin tx's.

The all I see is gmaxwell: "I think the sighash with input value seems pretty inelegant." and Mike saying he likes the idea of doing something, lets talk more at the conference.

The seriously-considered proposals are the UTXO commitment proposals. As for other uses for SIGHASH bits, see IRC discussions about the need to be able to specify sets of txins and txouts being committed to. I also posted a quick idea myself for txout summation.

FWIW one of my main objections to this is that we really need general ways to prove fees paid by transactions for inflation fraud proofing, and short proofs of txout existence are very helpful to SPV nodes who are able to use them to check that transactions are valid - you're focusing on something very specific.


Additional merkle roots can be committed to in the coinbase txout; adding them is a soft-fork just like adding additional SIGHASH bits is. The best way to do this is to put the digest of the secondary merkle root in the last txout of the coinbase (with a P2Pool style 0-value OP_RETURN) so the proof can use a SHA256 midstate of the coinbase tx to keep the size independent of the size of the coinbase tx. It's at this point that a "v2" transaction format can be defined to fix all this stuff for once.

I'd be happy to pitch in on a BIP defining that transaction format, and we can do it in a way that leaves room to add the UTXO commitment digest when that is fleshed out as well.

It would be useful if multiple payments to the same address could be summed together. For instance with CoinJoin if Alice, Bob and Charlie wish to, say, pay 1BTC to Wikileaks they can create a single 3BTC txout with Wikileak's public address. However they have to do that interactively.

So I'm proposing SIGHASH_SUM, a new SIGHASH bit that would allow a given txin signature to specify that at least nBTC of value should be added to a txout signed for. Thus if three txin signatures each specify that 1BTC should be added to the txout with Wikileak's public address, the transaction is valid if there exists a single 3BTC txout. Similarly any company accepting multiple payments at once could combine all their customers payments together into a single transaction, with a single txout, thus saving blockchain and UTXO space as well as improving privacy.

Of course this isn't too useful by itself, but the idea can be combined with more sophisticated SIGHASH bits that say that a particular set of txin's and txout must exist, rather than the more restrictive modes available today. But my lunch break is over so I'll write more about that later.

CoinJoin does increase network traffic a bit, but it can be implemented in a way that decreases UTXO and blockchain size.

For instance in addition to everything proposed already, you can make CoinJoin automatically join together requests multiple requests to pay the same address. For instance if Alice, Bob, and Charlie all want to donate 1BTC to Wikileaks's public address their CoinJoin implementation can take note of that and generate a single 3BTC txout with that address. You could even extend the payment protocol with support so that, for instance, BitPay could have all customers in a given 10 second interval join their payments together for totally unrelated items into a single txout.

There are much better ways to do this than using up what limited SIGHASH bits we have, and we already have other uses for SIGHASH bits that should be implemented.

In particular it has been proposed to extend the merkle tree of transactions down into the transactions themselves, which would allow you to easily provide compact proofs of the value of the transaction outputs that a transaction is spending.

tl;dr: Strong NACK on SIGHASH_WITHINPUTVALUE

What's really interesting about this approach is how users and miners are both required to buy into a larger blocksize, which means that adopting a larger blocksize requires the economic majority to convincingly show that they do in fact wish it to happen. Note how SPV users are required to accept the change as well if they want to accept aux-block coins as payment.

Wallets aren't the only thing that matters: businesses will want to use this tech as well to keep their own finances private. The AGPL is IMO right out for that application - even the LGPL is problematic.



Emphasis mine.

Sounds like the intent was for people to make a proposal, do work, and potentially collect a reward. That means there aren't any requirements until a proposal is made. As for donators, they should recognize that they are putting their faith in gmaxwell, theymos and sipa's best judgement. (something I myself am quite confident in)

Now if it was going to be undefined, I'd suggest they say that in 9 months or something funds to to whomever has made the most actual impact to getting CoinJoin technology actually used in this space. As jdillon suggested proposals that integrate into existing wallet software are most important there.

You need to add a statement as to what license the code is released under; without one the code is not open source as all creative works are copyrighted by default.

jdillon: I think all your points are reasonable ones.

I'd advise people doing work on this stuff to write robust mechanisms first, and only then follow up with GUI's and other gloss. The experts who should be playing with these tools initially don't need GUI's to do so.

I'd also advise people to release implementations that only work on testnet until enough time has passed to have some hope that the bugs have been shaken out - it's easy to lose money fast with wallet related code and we can't afford to get people burned initially.