Tx fees aren't the only way to buy network security.  For example, Mike Hearn talked about using assurance contracts to do it here: https://bitcointalk.org/index.php?topic=157141.0.  It's pretty silly IMO to assume that people with a whole bunch of stored value at risk of becoming worthless wouldn't find ways to collectively ensure it doesn't.  Plus that's decades away, and not really worth thinking about now, as things will likely look so much different at that point.

Bitcoin competes (very well) with gold, silver, and art, which are all very valuable, but garner little interest from the average person: https://www.youtube.com/watch?v=ndshbH3qZ6Y.  Though it would be nice if Bitcoin were to become widely used for payments, it doesn't need to in order to be valuable.

A valid coin is simply an unspent output from a past transaction.  Every coin has an associated script, and in order to spend the coin, you must provide the script with an input such that it evaluates to 'true'.  The most common example is where the script contains a hash of a public key, i.e. a bitcoin 'address', and the input you must provide is the full public key and a signature from the corresponding private key.  Here it is in detail: https://en.bitcoin.it/wiki/Script#Standard_Transaction_to_Bitcoin_address. Different coins can have the same script, or 'address', and the blockchain still sees them as distinct.  An "outsider" can send me a coin with the same script as one of my own, but the only way these coins can be combined, from the blockchain's point of view, is if I spend them together in a transaction later on.  If my coin is colored, then I obviously wouldn't do this on purpose if it would ruin the coin's coloring.

Oh, sorry for the ignorance.  Though I don't quite understand what you mean by this...

Fair enough, being able to revoke names after a transfer is probably going too far.  The goal is really only to be able to announce in an unjammable way that one's control over a name has been compromised.  I'm thinking this could be done by allowing a name to be 'double spent' at any point along its history (up to a reasonable limit), where the transaction merely adds a change-of-ownership flag at that point, and therefore doesn't mess with the name's value or who owns it.

Edit: I guess you could just reuse the same address during value updates, and only change addresses when you're transferring ownership.  Address reuse isn't as bad with Namecoin since there's no linking of coins like with Bitcoin, but this would mean public keys are revealed well in advance of a transfer, making them more prone to attack in the event that weaknesses are found in the signing algorithm.  Would these special flagging transactions be worth adding in order to keep public keys secret?

I've been spending a bit of time learning about Namecoin, and a couple questions/thoughts came to mind: 

1) Would it make more sense for the Namecoin blockchain to only know about (name, hash(value)) pairs instead of the full values?  Storage and serving of full values could then remain optional for blockchain-verifying nodes, and there would be a great deal of flexibility with how (hash(value), value) pairs are stored and served - e.g. a DHT could be used to store and serve these, but there doesn't have to be one single way.  Then nodes could be discerning about what data they want to store and serve, while still being able to verify the Namecoin blockchain.  It would also reduce the necessary burden on miners, making them more likely to mine.

2) Proper name revocation seems to be a necessary feature for Namecoin to function as a PKI, so I'm wondering if this is addressed?  If yes, then if the private key controlling my name is compromised and an attacker transfers control of the name to himself, do I have any time window to revoke the name altogether?  If I revoke a name, how long before somebody can claim it?  If name revocation isn't currently possible, do the devs think it would be a valuable enough feature to support?

It's important to point out that this is of zero relevance to any individual, as they are not a bank, and thus have no access to any currency's RTGS system.

Some anonymizing systems are designed to obfuscate links.  For more obfuscation, you need more non-colluding participants for 'cover traffic'.  These participants are known as the 'anonymity set'.

From Wikipedia: "Money laundering is the process of concealing illicit sources of money to make it appear like legitimately earned money."

I imagine if zerocoin were cheaply available, it would be used to ensure legitimate expectations of privacy vastly more often than it would be used for concealing the proceeds of crime (most people are not criminals, and almost everybody would choose to have the extra privacy if it was essentially free).

For this reason I prefer to call them 'mixes' rather than 'laundries', but that's just me...

I noted somewhere a while back in this thread that a group of 2-way nodes can be 'pruned' to produce a (e.g.) 256-way one for storage, and a 256-way one can be 'filled in' after retrieving it from storage to produce a group of 2-way ones.  Not sure what the optimal radix size is for storage, but database operations are definitely the primary concern.

If a write-back cache policy is used so that the 'trunk' of the tree isn't being constantly rewritten on the disk, then using a bitwise trie would mean not having to rebuild full Merkle trees from scratch for each of the upper nodes during every update.  Not sure if this is a big deal though.

Edit: Never mind about that last point.  Merkle tree leaves are rarely ever added or removed in the upper nodes, so updating the Merkle tree would usually only require changing a single path.

I'm not sure I follow.  I understand that one of the main benefits of the idea is to be able to prove to a lightweight client that a coin is currently valid; whereas now, when given a Merkle path to a tx in some block, a lightweight client doesn't necessarily know if a txout in this tx was spent in another tx after that block.  That seems like a big improvement.  But the problem isn't that the malicious peer isn't serving data at all, it's that he's serving it in a misleading way.  Isn't it true that either keying ensures peers can't mislead lightweight clients in this way?

I appreciate that.  The distributed node idea assumed a couple significant protocol changes, and I just wanted to be sure they wouldn't break anything.

How about "Authenticated dictionary of unspent coins"?

I like it cause it's self-explanatory

Right, I guess that's why it's the natural keying for distributed nodes.

The question then is which one's digest gets included in the block header?  Having both would be nice, but maintaining the (hash(script): txid:n) one seems to make distributing a node a lot more complex and expensive.  The downside to only having the (txid:n, script) one's digest committed in the block header is that you can't concisely prove a utxo with a given script doesn't exist.  But you can still concisely prove when one does, and that seems to be what's really important.  Also, if only one of the trees needs the authenticating structure, then this would be less overhead.

Okay, but I don't think an individual block really needs to encode an explicit ordering of transactions, as the tx DAG is the same for any valid ordering.  As long as a node can find some ordering that's consistent, then that's good enough.

@retep, here's roughly how I imagine sharding a node could be done without diluting hashing power across multiple separate chains (that sounds terrible!):

First I'll assume we include in the block headers the digest of a utxo tree keyed by (txid:n, script) instead of by (script, txid:n), as this will turn out to be much more natural, for this purpose at least.  Second, I'll assume the tx digest is created from the authenticated prefix tree of their txids, which will also turn out to be much more natural.  (Last minute thought: doesn't the tx ordering matter in the usual tx Merkle tree, i.e. earlier txs can't spent TxOuts created by later txs?  Or can it just be assumed that the block is valid if there exists some valid ordering which is up to the verifier to construct?)  The radix size turns out not to matter, but let's call it k.

Distributed block construction

Division of labor is as follows: We have a coordinator who directs the efforts of N well-mirrored branch curators who separately update each of the utxo tree branches below level logk(N), and process subblocks of any number of transactions.

A branch curator downloads the incoming txs whose txids lie in his particular branch.  Notice that due to our convenient choice of keying, all of his newly created TxOuts will lie in his own branch.  For each TxIn in a given tx, he needs to download the corresponding TxOut from his relevant well-mirrored counterparts. Note that TxOuts will always be uniquely identifiable with only a few bytes, even for extremely large utxo sets. Also, having to download the TxOuts for the corresponding TxIns isn't typically that much extra data, relatively speaking - ~40 bytes/corresponding TxOut, compared to ~500 bytes for the average tx having 2-3 TxIns.  With just these TxOuts, he can verify that his txs are self-consistent, but cannot know whether any given TxOut has already been spent.

This is where the coordinator comes into play.  He cycles through the N branches, and for each branch, nominates one of the curator mirrors that wishes to submit a subblock.  This branch curator then gathers a bunch of self-consistent txs, and compresses the few byte ids of their TxIns into a prefix tree.  He sends his respective counterparts - or rather, one of their mirrors who are up to date with the previous subblock - the appropriate branches, and they send back subbranches of those that are invalid with respect to the previous subblock.  Note that this communication is cheap - a few bytes per tx.  He then removes the invalid txs from his bunch, informs his counterparts of the TxIns that remain so they can delete the corresponding utxos from their respective utxo tree branches, deletes those relevant to him, inserts all of his newly created TxOuts into his utxo tree branch, and builds his tx tree.  He submits his tx and utxo tree root hashes to the coordinator, who also gathers the other branch curators' updated utxo tree root hashes.  This data is used to compute the full tx and utxo tree root hashes, which is then finally submitted to miners.

When the coordinator has cycled through all N branches, he goes back to the first who we note can perform very efficient updates to his existing tx tree.

Some notes:

• Mutual trust between all parties was assumed in lots of ways, but this could be weakened using a fraud detection and punishments scheme - ingredients being e.g. authenticated sum trees, fidelity bonds, and lots of eyes to audit each step.  Trusted hardware or SCIP proofs at each step would be the ideal future tech for trust-free cooperation.
• The job of the coordinator is cheap and easy.  The branch curators could all simultaneously replicate all of its functions, except nominating subblock submissions.  For that they'd need a consensus forming scheme.  Perhaps miners including into their coinbase a digest of their preferred next several subblock nominees, and broadcasting sub-difficulty PoW would be a good alternative.
• Subblock nominees could be selected by largest estimated total fee, or estimated total fee / total size of txs, or some more complicated metric that takes into account changes to the utxo set size.
• Revision requests for a chain of subblocks could be managed such that that the whole chain will be valid when each of the subblocks come back revised, thus speeding up the rate at which new blocks can be added to the chain.
• Nearby branch curators will have no overlap in txs submitted, and very little overlap in utxos spent by them (only happens for double spends).

Distributed block verification

To catch up with other miners' blocks, branch curators would download the first few identifying bytes of the txids in their respective branches, to find which txs need to be included in the update.  The ones they don't have are downloaded.  Then in rounds, they would perform collective updates to the tx and utxo trees, so that txs that depend on previous txs will all eventually be covered.  If by the end the tx and utxo tree root hashes match those in the block header, the block is valid.

Future tech: branch curators would instead simply verify a small chain of SCIP proofs

Additional note: branch curators can additionally maintain an index of (script: txid:n) for their branch, in order to aid lightweight clients doing lookups by script.

Cool!

On second thought, I don't think the radix size really matter too much for sharding the node.  The choice of keying OTOH...

@Mike Hearn, I understand it's not currently an issue, or will be for a while.  I should have been clear about that.  This thought came out of an investigation of the technical limits of the system, and a repeated claim that mempool synchronization was a theoretically impossible problem (clearly it's not).

Regarding having nested subtries for coins with the same ScriptSigs, I wonder if it's such a good idea to complicate the design like this in order to accommodate address reuse?  Address reuse is discouraged for privacy and security reasons, and will become increasingly unnecessary with the payment protocol and deterministic wallets.

Also, was there a verdict on the 2-way (bitwise) trie vs. 256-way + Merkle trees in each node?  I've been thinking lately about sharding block creation/verification, and am noticing the advantages of the bitwise trie since its updates require a much more localized/smaller set of data.

The collective wisdom of individual ignorance.

Because you recognize that we're all much better off if I do to some reasonable extent.  Nash equilibrium and all.  Note that this doesn't mean I get to choose what you include, only what you don't exclude, and only if I can prove that there's a reasonable chance that it'll soon make its way into a block.  Of course you're the final arbiter of what's reasonable, so I wouldn't want to overstep my bounds.  But at the same time, if your boundaries are unreasonable, then I'm free to ignore you.

It's well known that if mempools are well-synchronized, then only a few bytes per tx hash (the txid) are required to uniquely identify txs in mempools during the propagation of new blocks.  This has the potential to significantly lower orphan rates and bandwidth requirements of miners, and keep the anonymous mining of large blocks feasible.

I've heard some devs describe the problem of synchronizing mempools as the same one that Bitcoin itself solves - namely, agreeing upon a single consistent transaction ordering - and so a solution isn't theoretically possible.  I can see this would be true if mempools didn't permit conflicting spends and transaction orderings; is this the case?

If mempools are designed to accommodate potentially conflicting spends and transaction orderings, then they can be inclusive to all potentially valid transaction sets waiting to be included in blocks, making the synchronization problem simple.  The only potential problem then would be spam, which could be dealt with by nodes requiring periodic proof of work for persistent mempool inclusion - something miners would be producing anyway, and would have ample incentive to widely distribute.  Furthermore, because having transactions downloaded and verified in advance of receiving them in new blocks lightens the load on a node, it's in one's interest to make sure they've got the txs miners are working into future blocks.  It's also in their interest to kick nodes that don't maintain good synchronization in order to lower overall orphan rates for the good of the network - less wasted hashing power means more secure transactions for all, including them.

Essentially the mempool would encode a set of directed acyclic graphs, each of which describe valid tx orderings, and upon receiving the txids in a new block, a node would check whether the DAG they describe is in the aforementioned set.

I'm admittedly not familiar with how the mempool is currently designed, but the above characterization of the synchronization problem suggested to me that this might be the way to think about a solution.

Question: If votes are intended to be weighted by inverse age, how are the non-votes intended to be weighted, since you can't really say how long ago a non-vote was cast?

I do like this approach as well, and hadn't thought to use fidelity bonds for expensive punishment of misbehaving anonymous 'miner helpers'.  Though it is susceptible to attacks on the p2p network, unlike a SCIP approach, by surrounding groups of nodes and blocking the relay of fraud proofs to them.  Not sure how important this is in practice though.