Should we really be conflating chain building and consensus forming?  Mining could be done just as it is now, but with only the fee incentive driving it.  Fees are naturally driven down to the marginal cost of processing them, so this would lead to just the right amount of mining.

The consensus forming, i.e. the determination of which chain wins, is a separate issue, and can be done by separate players - in our case, the people placing bets.  And that would just be done as any other transaction.  The winner has an address "on file" for his loot to be sent to, so logistically this doesn't seem like a problem.

Plus I wasn't really clear on what it meant for a miner to mine a block in your proposal.  Does it just mean build a valid block in the usual way but which spends the reward to his previously published address?  Then anyone could submit such a block, right?  Are we actually on the same page?

Leaving the distributed lottery technical issues aside for a moment,

This would provide a huge incentive to roll back the chain.  With PoW you can't reclaim work done on alternative chains, so I think coins bet on alternate chains should be deemed toast (but only keep track of branches for so long).

If they were all granted to the winner, then it makes betting all the more attractive.  The more coins put on the line, the better, right?

Interestingly then, with these properties and where

w_i = size of wager i
W = sum(w_i) = pot size
B = block reward (inflation reward + fees)
P = probability of reorg

then the expected return on wager i is

E(R_i) = (B + W) * w_i / W * (1 - P)

Assuming the average expected return tends roughly to the average wager as the number of bets becomes large (efficient market hypothesis?), then

P = 1 / (1 + W / B)

i.e. the probability of a reorg can be estimated from the ratio of the total wager to the block reward in a very straightforward way.  Kind of a nice feature, if the assumption is actually valid.

With a "house edge" of f, i.e. the average expected return actually tends to (1 - f) * w_ave because people are irrational gambling freaks, then this formula becomes

P = (1 + f * W / B) / (1 + W / B)

I guess this parameter would have to be estimated in practice from the actual frequency of reorgs.

It's also obvious from the first formula that it's in every habitual player's interest to minimize P going forward by cooperating.

I would expect you to include a merkle branch to the other tx that spends the same txout.

Edit: In more detail, I would have different standards by which to judge different error messages as correct.  Such as the above for double spend error messages.  For the invalid txin one, I'd expect to not be able to find a merkle branch linking to the corresponding txout from any other peer upon request.  If I do find a valid one, then I ignore your future error messages.

Sorry, I don't mean to be brief, I expect I'm going wrong somewhere in my thinking - I'm just trying to get to the bottom of it.

It would make me wonder why you didn't just announce the tx way back in the chain that was the root of the problem from the start.  I would definitely be ignoring your error messages after trying to send me on an obvious wild goose chase.

I love your inkscape graphics.  I downloaded it cause of your mention

Doesn't it make more sense to start downloading from the bottom of the tree instead of the top?  Say, partition the address space up, and request all UTxOs that lie a given partition - aong with the full bounding branches - and then compute the missing node hashes up to the root.  Inclusion of each partition in some known block is verified, and then we'd just have catch up the delayed partitions separately using full tx data.  The deterministic property of the tree makes the partition syncing trivial, and I assume tx data will be available within some relatively large time window for reorgs and serving, etc.

My brain is fried right now too, I'll have a closer look at what you wrote after some sleep.  Maybe I'm oversimplifying it...

How about this: download whatever non-sychronized UTxO set you can from peers, then start downloading blocks backwards, adding any missing new txouts and removing any that were spent during the download.  Then once you're a few blocks before the time you started the download you could build the tree and make sure it hashes properly.

If a miner tried to include such a transaction, couldn't an error message point to the exact invalid txin, and issue a challenge to go find the appropriate merkle branch to prove it's valid?  And if nobody can produce it, then they'd reject the block.  Isn't it kind of the same with full clients?  Any piece of missing data, and a block can't be verified.

I understand SPV clients can't achieve certainty that a block is valid, but it seems like the trust can at least be upgraded from "I trust the the txs in the longest chain because it's expensive to forge blocks" to this plus "I also believe that I'm not special and thus likely not being surrounded in the network to censor error messages, which would presumably be flying around in abundance in the event of cheating".  This proposal is meant only meant to bring coinbase cheating within the scope of this trust model upgrade.

It's been talked about here before that when invalid blocks exist in the longest chain, honest nodes could broadcast short error messages to SPV clients with enough information for them to be able to prove that the block is indeed invalid, and thus be able to reject it.  Unfortunately, one of the most important error messages - that a miner has cheated on his fee reward - requires that the SPV client download the entire block in order to prove it's invalid.  This would become expensive for a smartphone at high transaction rates.

It would also open SPV clients up to attack, since the error message is cheap to broadcast, but expensive to investigate.  Mike Hearn suggested that to mitigate this, these error messages should only be investigated at branching points in the block chain, since presumably there would be some honest miners out there branching off.  The block size limit will also limit the damage an attacker could do to SPV clients.  But if this limit is to eventually be lifted, the hard fork required affords us the opportunity to solve this problem altogether.

This can be done by changing the Merkle tree of transactions slightly.  Instead of taking leaf node value = hash(tx) and branch node value = hash(child 1 value || child 2 value), we would have leaf node value = hash(tx || tx fee) and branch node value = hash(child 1 value || child 2 value || tx fee of child 1 + tx fee of child 2).  Working up the tree recursively, the tx fee value of the root node will be the total fee rewarded to the miner.  An incorrect fee value must then result in an invalid branch in the Merkle tree, which could then be relayed unobtrusively in an error message to an SPV client.

Would it be something that would make it into any hard fork that raises the block size limit?  Other than this one, I can't think of any other block error messages that require the download of more than two Merkle branches to investigate.  Are there any I'm missing?

Yeah, whoops.

Regarding the issue of synching ones Reiner tree: is it really a problem this proposal needs to solve?  Couldn't the client just wait to build/update it til after he's caught up with the network in the usual way?

I like the way this one imposes an unrecoverable cost to casting a vote on a chain (not counting the auction scheme you mentioned).  I think this is one of the key ingredients that makes PoW work.

What would the operation look like from a lightweight client's point of view?  The winners still have to find a small enough hash of their block, correct?  Is this what keeps time and prevents a flood of block submissions?

I don't like how it's guaranteed that the miner that risks the most wins though.  I have a feeling an alternative should be mimicking PoW in its game dynamics.  So could the bets be made more like lottery tickets?  Is there any crypto-magic that can be used to randomly select a winner, with odds weighted by amount wagered?

Some incomplete thoughts on how to pick the winner:

Each bet i of N_i satoshis includes a secret number M_i hashed into it.  Then a fair random number, M = H(M_1 || M_2 || ... || M_n) can be available later on when all n bets, totaling N satoshis, are in.  Then M mod N is between N_1 + N_2 + ... + N_k and N_1 + N_2 + ... + N_(k+1) for only one k between 1 and n.  This k is the winner, and his odds are exactly proportional to his wager.

There's a problem though when a player doesn't reveal their secret.  I'm thinking this could be solved by having a 1-1 function on the secret numbers that's not too hard to invert, but will take enough time for all the bets to have come in.  Any thoughts on what this might be?  Too insecure/hard to coordinate?

The motivation for finding an alternative makes perfect sense; with PoW miners are expending value to the aether, so if this value leak in the bitcoin economy can be plugged by making mining a zero sum game (non-miners included as players), then great.

Edit: not actually zero sum, since the non-miners win by having a cool currency, but you get my drift.

I think part of the charm of the Reddit bot is that it makes doing the +1 thing actually meaningful.  It's an overt, public show of thanks for a specific post.

With that in mind, the payment URIs contained in the signatures could contain a message labeling the post being tipped (unique URI per post).  As well, if the tipper is logged in, the URI could also include a message with the tipper's username.  This data would be relayed back to the forum from the tipper so that it knows which post to announce the tip on, and who it came from.

Edit: One last detail about tippers taking the glory, but then double spending their gift: the forum could police this by not sending private keys out to tipees directly, but through blockchain transactions instead.  Then if a user retracts their tips within, say, a month, the forum would know it was the tipper and not the tipee spending them, and could take away the tipper's glory privileges going forward.

Okay I'll stop now.  Too much coffee this morning  

After actually bothering to read the details of Mike's proposal, the forum knows the private keys it's sending, and can withhold and spend enough of them to itself in order to satisfy their fee.  It could send the private key of the change address of this fee transaction to itself to the person being tipped.

Edit: Agh in too much of a hurry...  The tipper then wouldn't be able to double spend the fee change as desired, so the onus would have to be on him to include a private key with exactly the right amount.

Regarding the last point, the forum could require payment URIs send it a fee in order to publish it, couldn't it?  That would solve the tip inflation problem, and provide a source of revenue for the forum.

IMO the decentralized/universal nature of Mike's solution is too beneficial to overlook.

Edit: I didn't think about carefully about how people could cheat that...

Funny, I was looking for an associative hashing function as well.  I gave up after thinking they would seem to defeat the purpose of Merkle trees altogether, and thus likely don't exist (yet?).

My point was that for insertion/deletion, only the trie node being attached to/removed from requires an insertion/deletion in the leaves of its Merkle tree.  All of this node's parents simply have to update the value of one of the leaves in the Merkle trees, i.e. no insertions/deletions, and this requires only updating a single branch in each parent's Merkle tree.  The node being attached to/removed from does require an insertion/deletion in its Merkle tree, but this would usually happen lower down the trie, where nodes branch less, and Merkle tree rebalancing is faster.

To make it deterministic, assuming the hash of each node's element is uniformly distributed, this hash value could be used as a "random" number for determining the tower height.  Though, this provides an avenue for attack by users purposely building lots of "tall towers".  To avoid this, each UTxO could also get randomness from the Merkle root of the tx tree that the UTxO showed up in, something a non-miner attacker has no control over.  It might also be hard enough for even a miner to perform the attack, since he has only one lever to control many degrees of freedom with.  This is just off the cuff, though, so I'm sure there are better ways to do it, or perhaps I'm not understanding it correctly.

I think the thing in this paper is patented, though.

Edit: You should name this beautiful thing, cause "hybrid PATRICIA/de la Brandais trie with authenticating Merkle trees" doesn't exactly roll off the tongue

I was thinking that to reduce the number of hashes a lightweight client would need to download when proving inclusion, you could replace the concatenation of the children's values in the formula for the value of branch node B with their Merkle root.  Then a lightweight client would only need log2(256) = 8 hashes 8 + (8 - 1) = 15 hashes per node to prove inclusion in the worst case scenario, instead of 256.

The downside is having to store more hashes (twice as many, worst case), but it actually appears to make updates faster, I guess due to fewer hashes needing to be accessed from memory.  This is because all node values updated during insertion/deletion/leaf update, except the one being attached to or removed from, have only a single leaf in the Merkle tree updated => no unbalancing issues, and only a single Merkle branch needs to be updated.

Also, this paper, 'Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing' seems to offer an alternative solution than trees/tries: http://www.cs.brown.edu/cgc/stms/papers/discex2001.pdf

As a first attempt at pronounceable "words", you can simply alternate between randomly generated consonants and vowels.  For easiest transcribability and memorizability, I figure they should be limited to 3 syllables, i.e. 7 letters and starting/ending with consonants.  Allowing the first letter to be capitalized means five 7-letter words have 5*log2(2*21*5*21*5*21*5*21) ~ 128 bits of entropy.  Example:


I may not remember this unless I'm using it frequently, but I could transcribe it with a pen or a keyboard really easily.  And the paper suggests this is the best we're going to be able to do regarding memorizability, and writing it down usually happens anyway.  So why not also make transcribability a priority?

Example using the more sophisticated FIPS 181 standard:

NB: If FIPS 181 manages to stuff more entropy into each of these words than I did above, then this can be made more compact.  I have no idea about this.

Edit: I just realized the code I used in the first example left out c, h, q, and y, so the passphrase only had ~ 122 bits of entropy.

So to summarize, system-assigned pronouncable passwords should be used over system-assigned passphrases because the latter offers offer no memorizability advantage, and the former is more easily transcribable?

Is anybody here familiar with FIPS 181, and know by how much the pronounceability requirement lowers the entropy?  Is it safe to assume it's negligible (as KeePassX would suggest by giving the same entropy values for pronounceable and non-pronounceable passwords of the same length)?

Haha, good advice.  I learned it the hard way.

I figured I'd do something similar: build a directed graph with adjectives and nouns as the nodes, and increment the weight of a directed edge from an adjective to a noun whenever the adjective was found preceding the noun in a sentence while scanning through a huge pile of text, e.g. Project Gutenberg.  Then I ranked the adjectives by their weighted degree and pruned all but the top A adjectives from the graph.  Then I ranked the nouns by weighted degree and pruned all but the top N = 2^(128/6) / A nouns.  Then any 6 randomly chosen pairs would give 128 bits of entropy.

Turned out to be a lot of work, and didn't seem to be yielding anything that was much better than ThomasV's solution.

Couldn't resist doing that after you'd stated one of the lead client developers is