The client knows from the history which outputs were added as part of the mix, and which were the result of explicit change addresses. This information needs to be tracked anyway because joined coins are not completely anonymous. At best each join adds only a few bits of entropy, and any competent implementation would have to track how much entropy is added with each mix, and therefore would be perfectly capable of setting entropy=0 for change outputs.

EDIT: BTW, in case anyone hasn't seen it, I'm running a crowdfund to finish the chaum blinded signature version of the protocol that I've started working on.

Don't reuse the input address. Don't ever reuse addresses, particularly in protocol.

This is what I still don't understand about your proposal (my fault: it's complex and I haven't had time to devote to it). But what I do understand is that you are accomplishing it through having multiple classes of assets partially-backed by USD, and periodically pricing derivatives on top of these via auction.

That's doable in Freimarkets. Whether that fully represents your proposal or accomplishes what you want I'm not yet sure of.


Semantics. You need someone signing. That could be a trusted oracle, or it could be a multi-sig plurality of the participants, all of whom are watching the out-of-band data stream, or any other concensus procedure that results in a cryptographic signature. Whatever that process is, that's the oracle.


You definitely need to overhaul the scripting system - that's what Freimarkets represents. But I don't see the connection to mining at all.

BTW cunicula, I still owe you a response about USD parity in the other thread, using Freimarkets as a base. I assume this is the fully fleshed out version of the same idea, correct? I'm still wrapping my head around it to see if it would do what you advertise, but the specific requirements of market clearing demurrage rates through periodic auctions are implementable as Freimarkets assets.

Gregory Maxwell has outlined a protocol for constructing shared transactions which obscure linking of inputs to outputs and thereby increase privacy (by 'mixing' coins to disassociate taint), or enable join transactions such as a matched donation (“I'll contribute 10btc to cause XYZ if someone else does too”) or colored coin exchange. All of this is possible without a single change to bitcoin. Even though the transaction is constructed in public, ownership of the outputs is masked using chaum blind signatures.

As a weekend project I have started an implementation of CoinJoin using the JSON-RPC API, Bitmessage for distributed, p2p communication, and a SQL storage layer. I have posted the initial framework to Github, here:

https://github.com/maaku/coinjoin

Now that the scope of the project has been explored, it is unfortunately too large an undertaking to accomplish as a side project. I am therefore asking for donations so I can spend a significant portion of my working time devoted to it over the next couple of months.

For $12.5k I intend to write a command line program which can be daemonized (run in the background), and which collects incoming transactions and change outputs from a running instance of Bitcoin-Qt, organizes mixing transactions with other users anonymously over Bitmessage to achieve the desired level of privacy, and finally returns the anonymized coins to your wallet. It will be usable, though not user-friendly (no graphical tools, yet). Most importantly, it will implement a cryptographic protocol for privacy enhancing distributed mixing of coins which could eventually become a standard part of wallet applications.

If you would like to contribute to this project, please consider sending some coins to the following signed address. I will “bill” my time hourly up to the donation amount received, and post all source code to github (MIT license).

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Donation address for implementing
"CoinJoin" mixing daemon.

1CJRGzzZzjYbubXzmJERCoWqxNxgbjf5XG
-----BEGIN PGP SIGNATURE-----

iQIcBAEBAgAGBQJSLlNHAAoJECsa1YSJj/UDxI8P/3EBzwuCxjLzm/vxfQGnQDRR
rdcn6vHZGNDbxjuuLxDXUgPlAWSQ4/Cl+mYfzlDy3TtPX7tOTnEIZK3G5VPPuGuW
pEIl7r2FGQlKFxzyVFx0aYQ3f1VlHgvDhZM60DbhhHfm+uzgBYvIGVTXPWKHZTZ6
4KsV5Y8Y9jOA1C7KqAsI7rLuI59R3A/ovq7ItDpi5DsJb8KqZnKlVjcRWrrBd5Om
74h4WnI9dkaCFqY+alqb7uuGeEPld6eMPwCt7CneAdNu7AG21nW3Q4BR9Un/j861
Yxr9udod2uFzI7ULhj4MmbD20XSKVTUkFXo1BBzxa01yK9v/3JzRj97mT30kfY4h
QHn+pKmGTbVMJy+aiyLW+wX6UswKfF6krHeVa1BhEeQXSjhdNIp1y+2n1cbCqo5y
53MsxPD3pVMTf88uf4O7Eh7Srw1St1x4dXz5nBIdFQHm0IZ7dwrA3fojrLdrGjKP
DOnuH1Fr2NFDWnemwiJlab4AVS5F5/5Cm1jaYBWdl9LcKLr5O15M8OtZDNrcdRjJ
GupnNmn85E4Y6TLMUIqppwfqClLeVlaeam0DvChuRFy4QUAa521HBIpYQhUr8cq0
0O2tw0jnTZf/nMo+9Tk3vNPADQn26utUNCJdGQZTGfschxHWYijoEmTSG77KZRok
E/tYjHxnbnmL8l+5UMem
=ioqh
-----END PGP SIGNATURE-----

Final revision of the index structure has been committed to python-bitcoin. It is now a level-compressed and node-compressed binary prefix tree. This is a pretty big change from the original proposal, but clearly the right decision to make in light of the performance numbers. The purpose of a 256-way radix tree was to reduce the number of hash operations, but that came at the price of greatly increased node sizes. This made index traversal more complex, and resulted in enormous proof sizes. Alternatives such as having a Merkle-ized internal node structure would have resulted in the exact same performance as a binary tree, but with much greater code complexity.

There may be one more minor change (eliminating the no longer needed coinbase flags from the ultraprune structure), but after that hash values and proof structure should remain unchanged from then until the deployment to the Satoshi client. The design phase is now over.

I also made some slight but important adjustments to how the utxosync.py program constructs the root hash. Insertion of coinbase transactions into the ledger is delayed by 99 blocks, meaning that an output shows up in the ledger only once it is eligible to be spent in the next block, according to the network rules. The primary reason is that the index of a block cannot contain its own coinbase, if the hash of the index is itself going to be committed to the coinbase. Otherwise you'd have a circular hash dependency (input depends on output), which is obviously impossible to resolve.

The final performance characteristics: average-case proof size of 64 * log2(utxo transactions) for the txid index, which is currently about 1.35kB. Average case for the address index is: 65 * log2(utxo outputs), currently 1.45kB. The worst case size for a txid proof is 16.25kB, although that will never happen because setting it up would require a SHA-256 pre-image attack. Worst case for the address index is 65 bytes * number of bits in the scriptPubKey, which doesn't require a pre-image but can be protected by not reusing addresses.

Syncing with the block chain takes a few seconds per block, or a few dozen for the really big blocks, with 95% of that being spent in the SQL database, and 4 of the remaining 5% spent marshaling data. As mentioned earlier, moving to LevelDB and a compiled language should eliminate most of that, hopefully resulting in two orders of magnitude speedup. So performance is looking good, so far.

---

I have approx two weeks left on the first round of funding the members of this forum have so generously provided. I will use that time finish and push the pruning and proof generation code, and time permitting expand the utxosync.py script into a small Django web API for querying the UTXO indicies. This could be used for prototyping wallet software that uses the new proofs. However this will provide no increase in security until bitcoin is soft-forked to include UTXO index commitments, or a merged-mined meta-chain is implemented.

This brings me to the next round funding. I am requesting a final 3 months of time to implement the final revision of the index structure in C++ and using LevelDB, optimize it to achieve sub-second update times (or as close to that performance goal as possible), and either (1) submit a documented pull request adding coinbase UTXO hash commitments to the Satoshi client, or (2) write a proxy server for miners to do their own commitments on a merged-mined meta chain. Which outcome depends on whether acceptance of a coinbase commitment pull request is likely to happen, which in turn depends on the achievable performance metrics which we do not know for certainty at this time.

Because of unexpected costs (insurance) and volatility, I'm forced to increase my monthly cost to 65btc, and will fully cash it out on receipt. I am therefore requesting a total of 195btc to finish the implementation as described above. If this is received by the end of the month, then I can promise the deliverable by the end of the year. Otherwise I will continue work, but at a rate in proportion to funds received, as funds are received ("billing" my time hourly). Please send donations to the same address:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Donation address for implementing phase 2
of "Ultimate blockchain compression"

13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
-----BEGIN PGP SIGNATURE-----

iQIcBAEBAgAGBQJSLkT7AAoJECsa1YSJj/UDJ0IP/26oyR1COsLs/f+rEvz33kFP
0HtGvsjbEoF+7cetJpIV0eyFomngOWpafr0uhy+uO6mGguPHbXPJlmcgywFdKDwB
pQrRVYcT2DQx+Hfwnhn51QNIJoB6LhnykUi9KrDar8FwbNfYOgLaSUDGqKShtDOC
lc/qVkP56cCvalcqs6a6Q8O0D69BLO+TwifMPJmtdzdnn/2Fs9ONdgXpnnNLGwpJ
g/LWPy9Zdjspq7qoH/p3kFWo2S8TmX5EShsMDM8C4oUTnMjXbBvodJQwm6AzC0KY
XWdg+/W82YpMpmAmhSxqw43/VzUrODw9WAn7cXrCA86/IwhihZnNhLsELYP7Cd77
kgBWR9HE+NILWTRn+x8CONfi6+gk8ZqYsKmcj+PcYbf1u2BAknKb1EVpTwNp2ehD
8y6oNFj99vkDfZz8hSmt8HLn7YbU9jnmJcFqXwCwDFZD+nvWi1dHFeqnJppH3lWX
HaIF3V+psYQuMpglk+fFVrbmF+omCzsd7dArCXk4n+txA8rGIVBD2nWz4MUUxB9e
TLIeVr4EkH+yjvEK00VzjryfINE6mG58hetm1/y4Y/1EvoDATOyZhR91UFB6x/21
+pCagBDSVquc7DVYk7e275PnKSxjM4miAcf88jkO6TvcdiUaiYnYGxZQRCBY89/6
WgWf1x6CQvknPrYT6sZv
=hg1Y
-----END PGP SIGNATURE-----

As always, I welcome questions and comments regarding this proposal and my work towards implementing it, particularly from funders or developers of lightweight clients that might use it.

Because even if the information they used to construct the S-boxes is now public, it still reveals the limit of the NSA's knowledge. What if X for some X in the intelligence agencies of Russia, China, Israel has Super Cryptanalysis Technique that the NSA doesn't know about. Then the NSA publishes what technique was used to come up with the S-boxes / curve parameters and -- egads! The NSA didn't check for weaknesses from Super Cryptanalysis Technique! That's exploitable knowledge.

This is why these things are kept secret for something like 70 years. Because showing the sum total of what you know reveals what you didn't know you didn't know.

It is not at all weird. Like I posted earlier, this was the case with the DES S-boxes as well, which was a similar opportunity to back-door symmetric encryption. In that case the NSA took the high route and strengthened the algorithm against attacks that would not be (re-)discovered by industry and academia until decades later. So when NSA employees stepped in and did a similar thing with ECC curve parameters, there was no compelling reason at the time not to trust them.

Of course looking back, DES was only strengthened against attacks that were known by IBM employees at the time, but kept classified. Other forms of attack have shown theoretical success in recent years, and may or may not have been known to the NSA at that time. Maybe this is being paranoid? But with these new revelations, what level of paranoia is justified?

Fool me once, shame on me, fool me twice...

Once again I defer to gmaxwell. I drive by their headquarters in Scotts Valley about once a month .. but apparently this is just the headquarters of their U.S. branch. They are in fact a Canadian company.

Bitcoin uses a curve whose magic numbers were specified by Certicom - thanks for the correction, gmaxwell - a U.S. subsidary of Research in Motion (makers of Blackberry, who have been funneling user communications into the NSA since the early days, apparently) that owns most of the patents related to ECC. Whether that is more or less threatening in light of recent revelations, I'll let you decide.

Schneier's reasoning is basically this: we don't know what cryptanalysis the NSA is capable of (Schneier might after seeing the leaked documents, but he's not letting on). But it is likely that if there were a weakness it would likely affect only certain categories of curves. The random curves were (presumably) chosen at random, but so were the Koblitz curves: there are many possible Koblitz curves, and the specific ones enumerated in the standard (like secp256k1) were purportedly chosen at random from the set of possible Koblitz curves of that length. But here's the rub: how do we know the NSA didn't search through the space of Koblitz curves looking for one that was secure as far as academia knew, but susceptible to attacks based on mathematics only the NSA knew?

Pre-Snowden, this would have been considered tinfoil hat paranoia because it is not a new concern. The exact same situation existed with DES, which was the federal standard for cryptography for decades. Designed by IBM but with parameters chosen by the NSA, some paranoids thought they had inserted a back door (there was even a Senate investigation). But as we later found out, the tweaked S-boxes strengthened the algorithm against differential cryptanalytic attacks, which weren't known to the public until recently.

The rules of the game until now had been: we work with the NSA through NIST competitions to standardize cryptography. The NSA continues to collect the intelligence it needs through exploiting side channels, weak random number generators, bugs, and even strong-arm techniques, but the algorithms are secure. You can trust the math.

These new revelations apparently throw that out the window. In recent years the NSA actively pushed NIST for standards that it knew were insecure. Not easy-to-get-wrong, like DSA (choose a predictable K value, or reuse an old value and you reveal your private key - a slight of hand that puts the master keys inside the RNG, something which the app has little control over and the NSA can influence), but rather fundamentally broken in subtle ways. How do we know they did not do the same for ECDSA, or any other standardized crypto system that has chosen parameters?

Schneier is justified in his recommendation, IMHO. But there is one bright spot: even if the standard ECDSA curves were broken in this way, if you do not reuse addresses it would not concern you as no public key or ciphertext is available until the coins are spent. So don't re-use bitcoin addresses (you shouldn't anyway).

EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this.

I have pushed to three related code updates, representing work done during the month of August towards implementation of the UTXO index structures for bitcoin. As I've mentioned earlier on my blog, I'm doing the preliminary exploration work in Python, and so far that's paid off. I've gone through three iterations of the prefix-tree design, at each step uncovering weaknesses that require various modifications to the original design. The design, implement, test, benchmark, redesign cycle is averaging about a week, much faster than developing directly in C++ would have been. Python is, however, much slower, chiefly because of the time spent marshaling in and out of the block store or constructing hash preimages, and the resulting dynamic string manipulations. Now that the design is starting to solidify, I will probably do one more iteration before moving to C++ and beginning implementation for the Satoshi client.

The code updates include a new release of python-bitcoin, which contains the UTXO index data structures. Of particular interest to other developers would be the modules patricia.py, ledger.py, and merkle.py. The patricia.py module contains the PatriciaNode class which implements the node-compressed, level-compressed trie structure and whose API looks very similar to an ordered dictionary. ledger.py contains the supporting structures necessary to TxIdIndex and ContractIndex - the two authenticated indices underlying the “Ultimate blockchain compression” proposal. The merkle.py module contains a similarly constructed albeit not finished implementation of prunable Merkle trees. You can access this code here:

https://github.com/monetizeio/python-bitcoin/

The second project, which I'm releasing now for the first time, is a SQL blockchain storage backend using the absolutely wonderful SQLAlchemy object relational mapper. For this project, using SQL for storage has been beneficial as many profiling tools exist, and it allows arbitrary queries to be constructed after-the-fact to help diagnose bottlenecks. There are, however, obvious performance limitations and nobody should ever consider using a SQL backend for a fully validating node. Some people may find it useful for specialized applications requiring join queries, or perhaps a block explorer-like website. The code is available on github, and interfaces with python-bitcoin:

https://github.com/monetizeio/sqlalchemy-bitcoin/

Finally, in case anyone wants to play around with what I've been working on, there's a tool for synchronizing the SQL storage backend with the block chain via bitcoind's JSON-RPC interface. I *only* recommend using this for testnet data, and preferably the smaller testnet-in-a-box chain. Performance is abysmal, but for known reasons explained above. Back-of-the-envelope calculations based on profiling data show that a compiled implementation with smart memory management and a fast key/value data store should operate at least 100x faster, which would be enough to handle the live bitcoin block chain. Code is available here:

https://github.com/maaku/utxo-ledger/

I will be posting more updates soon.

I suppose he then planted the 1/3 article in The Times?

The google keyword you are looking for is “colored coin”.

Shameless plug for my own proposal: https://bitcointalk.org/index.php?topic=280292.0

I pushed the beginnings of a framework for a CoinJoin implementation using RSA blinded signature operations. It's written in Python and under the MIT license:

https://github.com/maaku/coinjoin

So far it's a storage layer for the various objects and message involved in the protocol, some simple primitives for the blinding operations, and a few utilities for pulling outputs from JSON-RPC. I'm working on more primitives that I will probably add next week, including tools for creating messages at various stages, and eventually getting this running over BitMessage.

Patches welcome.

JR, put OP_RETURN in front of the data script. That can't take more than a few seconds to change, and a few minutes to communicate. You may even be able to use dust/empty outputs in this case (you should, but not sure if the client supports it yet).

You've asked questions the answers to which are offtopic and I don't want to be seen as hijacking the thread. But you're the OP so I'll continue unless you think we should move it elsewhere.


That's a very understandable critique. We spent most of our whitepaper talking about the technology not the use cases because the use cases are nearly infinite. Basically any form of market exchange, derivative, or synchronization primitive is implementable, on-chain or off-chain.

You can issue assets representing the usual suspects of stocks, bonds, & precious metal receipts, as well as various options or other derivatives thereof. You can issue smart property tokens representing physical ownership of specific items, or for use as capability access tokens. You can issue a basket currency or ETF tracking other in-chain or off-chain goods. You can issue IOUs to create a ripple-like credit market. You can do various kinds of auctions/exchanges to trade any of these assets for any other. You can do new forms of transactions like pre-authorized matching donations.

There are probably hundreds of applications, so I'll stop here. Each one would probably require a page or more to fully describe how it'd be implemented (we have a few examples in the whitepaper) and what the ramifications would be. Unlike BitShares and MasterCoin, the Freimarkets proposal is fully general - it's not meant to enable certain specific applications, but rather provide the primitives necessary to do almost anything imaginable.

It's sortof like if bitcoin were the rules of addition and subtraction, and that's all the math we knew. Then Jorge and I propose to add multiplication, division, exponentiation and logarithms. Yes we could spend a great deal of time explaining how you could use exponents to construct a formula for compound interest, but that'd be missing the forest for the trees.


I'd love to debate specifics with you, although I'm tempted to just point at the whitepaper. You can put just what you need to in the block chain, or threaten to do so with locked transactions. In some cases you want the whole transaction public, in other cases it suffices to just commit a semaphore on which off-chain are conditional. In most cases you don't need to touch the public chain at all, even if your transaction crosses multiple private servers.

Actually, a core part of our (jtimon & my) proposal is the idea of private accounting servers - a high-volume, non-public block chain secured by auditor signature instead of proof-of-work. I do not expect that the public block chain would be used for very many market transactions, except for those situations where the burden public assets is actually required. Using the public chain has considerable costs which are paid for in transaction fees. Off-chain accounting will always be cheaper, and transaction confirmation faster, so traders will naturally prefer to use such systems when they can.

But even if they don't, note that market transactions do not increase the size of the UTXO set. The fee system is sufficient for regulating write access to the blockchain in this case.

Or prefix the data output with OP_RETURN, which is guaranteed to be prunable. If the output is never meant to be spent, then it is irresponsible not to do this.

That's what I've proposed:

https://bitcointalk.org/index.php?topic=280292.0