Bump to draw attention to updated answer in above post (#44).

Sorry I didn't read this carefully enough. Mea culpa. My previous answer was wrong. I have edited my answer.
In your example, Satoshi x mints on one chain at time x and sends a txn at time x+t on a second chain. So yes, you are correct.
I should have defined the rule as follows:

That should cover all possible cases.
  


 


It is not difficult to track Satoshi serial numbers. Recall that you cannot send txns that use more than one input. Thus, you can only split inputs into two or more outputs. You can never recombine two or more outputs into one input. This implies that we can record the set of satoshi numbers associated with each output using just two numbers.
e.g. This output contains satoshi 10,000,000,000,000,000 (inclusive) up to satoshi 20,000,000,000,000,000 (exclusive).
Whereas before the blockchain would simply write this output contains 10,000,000,000,000,000 satoshis.

You don't actually have to record any new data in the blockchain. Instead, you can derive the data from the blockchain. Just define the output listed first in a txn as containing the lowest numbered satoshis and scan the blockchain.
Even if you recorded the data directly in the blockchain, the extra space required would be tiny.
The added data would be equivalent to writing the amount of sent coins twice instead of once.
That's like an extra 7-8 bytes per txn, almost nothing.

Finally, I included these rules to provide a simplified example. The rules are restrictive and probably not a sensible arrangement. However, the simplified rules define a long-run consensus. There is no use of checkpoints here (outside of agreement on a common genesis block).
 

I also agree that you need some sort of arbitrary assignment of initial ownership to bootstrap a PoS currency. That is not my focus here.

My point is as follows:
Given the txn rules I defined, the current owners of the majority of clean inputs always control long-run chain selection. Attackers can exploit past input ownership to blacklist current inputs. This reduces the set of clean inputs and therefore reduces attack costs. However, you can never attack soley through past input ownership. Attackers always need current input ownership as well, otherwise their attack will fail.

Does anyone disagree with the bolded statement at this point? Or have we reached consensus on this point?


If we accept these ideas, I will describe a system for removing inputs from the blacklist.


 

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

Take a look at this thread, which covers the same topic.
Essentially to resolve nothing at stake, you need to prohibit all forms of txns among POS miners.
You do not need checkpoints.
I discuss the theory behind this. It sounds very restrictive, but there are some ways of loosening it up.

In the thread, I defined chain selection criteria that allow you to do exactly this. So yes, you can do this with POS. That is the whole point of this thread.
If you don't think I have defined criteria that allow proof that one POS chain is better than other chains in a comparison set, please explain why not.  

There is some distinction in that the ordering over sets of POW chains are transitive.
Orderings over sets of POS chains are not transitive. However, given a set of pos chains with at least one clean Satoshi, there is a well-defined ordering of chains from best to worst within the reference set. 
 

Ideally, I'd like someone knowledgeable to comment on this AND either
a) agree that the system defines a long-run consensus that is robust to nothing@stake.
b) disagree and explain how a nothing@stake attack would disrupt consensus

If (b), then we could debate a substantive issue.
If (a), then we could move on to replenishing minting Satoshi. It's an interesting issue. However, there is no point in discussing it if we don't reach consensus on the existence of consensus here.

If a Trojan horse in the github repo is the source of the attack vulnerability, then bitcoin is just as vulnerable.
It's not worth discussing this issue further because it has no theoretical content. 

That document is very short on specifics, which is a negative signal. It seems to be some form of mixed proof of stake \ proof of work.
If you go that (and it is a sensible route IMO), then iddo et al.'s proof of activity seems like a better choice.
See the link I provided in a previous post.
Note: There is no currently released coin using iddo et al.'s system.

One simple way of thinking about this is as follows.

1) Fork the current bitcoin blockchain to produce a genesis block with diffuse ownership. Call the genesis block, block 0.
2) Order all satoshi in the genesis block from 1 to N, where N is the total number of satoshi.
3) Allow satoshi that have never moved since genesis to mint blocks.
4) All nodes agree on the current minute. If not, then replace minute in what follows with some larger unit of time that all nodes can agree on.
5) Satoshi 1 can build a block during the first minute since genesis. Call this block 1.
    Satoshi 2 can build a block during the second minute since genesis. (provided it didn't move in block 1)
    Satoshi 3 can build a block during the third minute since genesis. (provided it didn't move in blocks 1 or 2)
    Satoshi 4 can build a block during the fourth minute since genesis. (provided it didn't move in blocks 1, 2, or 3)
    ...
6) If Satoshi x mints a block on one chain at minute x and sends a txn on a fork at a time x-t, where t>=0, then this satoshi is blacklisted. To verify this, we can require that txn include a block number y and prohibit inclusion of txns in a block minted by satoshi x when y<x.
7) If Satoshi x mints blocks on multiple chains at minute x, then this satoshi is blacklisted.
Given a comparison set of competing chains U, define the value of a specific blockchain, u in U, as V(u). Compute V(u) as
V(u) = the total number of blocks on blockchain u - the number of blocks on blockchain u minted by blacklisted satoshi
9) Whichever blockchain has the highest V(u) is the main chain.

I claim that, as long as at least one minting satoshi is not blacklisted, this system generates a long-run consensus.

We can think about incentives to avoid blacklisting and ways of replenishing the set of minting satoshis later.
The point is that there is a well-defined consensus here. There is no nothing@stake problem because anyone who attempts to use a minting satoshi for multiple purposes gets ignored during chain selection.    

Note: if you want to know if Vitalik 'agrees' with this, then you should ask him to read the specific statement written above.

No, I'm following that, but I don't have time to participate in a group at this point.

As in bitcoin, you would have to convince users to download a new client that allows more coins in the genesis block.
The botnet wouldn't help you in anyway.

Yes, exactly.
However,
1) If you restrict txns to map no more than one input to each output, then you cannot use a satoshi to taint a huge amount of coins. Essentially this restriction implies that there is nothing prunable in the blockchain. If you do this, x satoshi inputs would taint exactly x satoshi outputs, no more and no less.  [I added this to the list of necessary mods to PoA].

2) Taint is not burning the coin. it affects the algorithm used to compare competing candidate chains. It does not affect eligibility for minting rewards, txn rules, etc.. It only comes in to play when multiple competing chain are present. Under normal circumstances, it has no effect on behavior. [It could, but I haven't said that it does. If we allow such effects, it would be necessary to be very careful to limit their potential impact.] I think tainted coins would trade at parity with untainted coins. Who cares enough about voting on the winning chain to pay extra for the privilege of having their vote counted?

3) If you use a fully deterministic system related to Nxt's proposed transparent forging, then you can limit risk of taint to a very small number of coins. Essentially you could limit risk of taint to single satoshis if you allow for 100% deterministic mining.  

My plan is to go on to specific details on (3) after questions on the thread die down. Maybe tomorrow or the day after that.
I think you are a nxt developer, so you might find this interesting.

Finally about attacks. To execute a double-spending attack you would set aside a majority of 'clean' sleeper coins. You could not mine or spend these sleeper coins on the main chain. Once they are used for mining or spent, then they become useless for attack purposes. You would then reveal the sleeper coins all in one go by mining on an attack chain. This only works if you control a majority of 'clean satoshis', so that you can overtake the main chain as a solo miner. It is essentially a legitimate exercise of authority associated with 51% ownership. It is intended behavior.  
You are right though that you can use past ownership of coins to swing things in your favor to some degree. Essentially, you would want to taint as many coins as possible to increase the influence of your clean coins. Unless you have handled 100% of satoshi's over the chain's lifespan, however, you can't taint every single satoshi out there.

Since you brought up the relationship between this idea and other research, one very simple way of describing my idea is through  reference to PoA a la iddo et al.
http://eprint.iacr.org/2014/452.pdf
PoA is a mixed proof of work/proof of stake system. See the linked paper for details.

The only modifications necessary to incorporate my rules are:
1) Prohibit reuse of public keys
2) The criteria for blockchain selection is select the chain with the max summed difficutly summed difficulty, where summation of difficult is over blocks at height t that are signed exclusively by satoshis in the set Zt.

Edit:
3) Restrict txns to map no more than one input to each output. Essentially this restriction implies that there is nothing prunable in the blockchain.

Rules (1) and (3) are intended to prevent intentional blacklisting of other people's coins.

As long as you can rule out a conspiracy involving 100% of historic inputs, you still have consensus.

Building directly on the genesis block is a special case because it involves 100% of historic inputs. If you built a fork directly on the genesis block, then 100% of satoshis would have double signatures by definition. Every satoshi would get blacklisted and the set of clean satoshis, Z_t, would be an empty set for all t>=1. There would be no consensus chain. It would be impossible for new participants to distinguish between competing chains.

So yes, you do need a checkpoint in this case, but the attack doesn't succeed if the objective is double-spending. And this attack is a bit unusual in any case. It is not very restrictive to have a single checkpoint some time after genesis. It is also possible to have a genesis block where inputs are divided across a wide range of owners. If you used an existing coin's current ownership structure to assign coins at genesis you would not have this problem.

If you built on the historic chain from a point where you don't control 100% of inputs, then we still have consensus. For example, say that one block after genesis the founder receives 99% of all inputs and some other guy receives 1% of all inputs. The founder does not have control over this residual 1% and uses his 99% to attack. If the founder kept his 99%, then he is supposed to win in any case. If the fonder spent any his 99% of inputs after this event, he could no longer use his historic 99% ownership to attack the chain. In this case, inputs he uses to SPEND on one chain and SIGN PoS blocks on another chain will be blacklisted and ignored completely for consensus purposes. Selection of the consensus chain woud revert to current holders of the remaining 1% of inputs (or some fraction thereof if some of this 1% has been blacklisted.) Blacklisted inputs are not part of the set Z_t. Therefore, blocks signed by these inputs do not contribute to V(u).

Finally, there is nothing punitive here so far. Blacklisting does not necessarily need to affect rewards for minting or the ability to mint blocks and send txns. So far it only matters for selection of consensus chains.

This is an outline for a pure proof-of-stake consensus mechanism that is robust to the so-called ‘nothing at stake’ problem.

Why address the so-called nothing-at-stake problem?

Nothing-at-stake is probably the most commonly raised objection to proof-of-stake currencies. While some (including myself) view the nothing-at-stake issue more as a theoretical curiosity than an actual practical problem, others identify nothing-at-stake as a critical failure and dismiss proof-of-stake on this basis. Addressing the nothing-at-stake problem may persuade critics of proof-of-stake currencies to reconsider their position.

What is the nothing-at-stake problem?

Nothing-at-stake really refers to two separate problems. The first problem is the potential for current stake owners to simultaneously sign two or more competing forks in order to maximize their block output per unit time. This implies that only the fraction of miners who sign a single chain are true sources of consensus. In this case, an unethical PoS miner applies the same signature to two or more blocks at the same block height. Such ‘duplicate PoS signatures’ are useless for consensus purposes. The second problem is double-spending by past owners of stake, who may have no current ownership of the currency. Past owners of stake could build upon blockchain history from a point where they owned currency. If they are able to overtake the main chain by building in this manner, they can reclaim ownership of coins long after they sell them. In this case, an unethical PoS miner uses the same public key to both a) sign a block and b) send a txn. To ensure that such behavior is easily detectable, I will assume in what follows that txn rules prohibit reuse of public keys. Under such rules, using a single public key to both sign a block and initiate a txn would be prohibited.

Shutting down nothing-at-stake.

Both of the nothing at stake problems require attackers to generate conflicting signatures. While attackers may operate in secret for some time period, after an attack chain is released the existence of conflicting signatures becomes public knowledge. One way of preventing attackers from influencing blockchain consensus is by identifying the set of inputs that have provided conflicting signatures in candidate chains. Inputs that provide conflicting signatures can be blacklisted using an approach analogous to colored coins. That is, blacklisting would be an inheritable property that is transmitted from txn inputs to txn outputs. Importantly, evidence of conflicting signatures does not need to be recorded directly within the block chain. Instead, it can be deduced through comparison of a set of candidate chains.

Consensus Rule

Consider a set of candidate blockchains, U. Each blockchain in U is a candidate for the valid chain. All of the chains share a common genesis block, have a constant number of satoshis, and the same block generation and txn rules. In other words, they are all part of the same altcoin.
We will use U to compute the block-height varying sets of satoshis called X_t, Y_t, Z_t. These sets are defined over U and are common to all blockchains in the comparison set.

Let X_t be the full set of satoshis in each chain at block height t. X_t is time invariant ad does not vary across chains, so we could write X_t=X.

Let Y_t be the set of satoshis that can be associated with a conflicting signatures at some block height x, where x<=t. We 'associate' a satoshi with a conflicting signature when that satoshi was under the control of a public key that provided a conflicting signature, or can be traced to a parent input that was under the control of a public key that provided a conflicting signature. Y_t is the set of blacklisted satoshis at block height t.
  
Note that Y_t is a subset of X_t. Unlike X_t, Y_t gets larger as the blockheight grows. This is the case because txn outputs inherit blacklisting from txn inputs. Also, not that the set Y_t can only increase if we add another blockchain to our comparsion set U.

Let Z_t be the complement of Y_t over the set X_t, i.e. the union of Z_t and Y_t is X_t.  This is the set of all ‘clean’ inputs at time t. Up to time t, these inputs have never signed two conflicting forks or attempted to use spent inputs to provide a PoS signature. We use block signatures provided by these inputs to determine the consensus chain.
  
For each chain u in U, sum up all of the blocks that were signed using satoshis in the set Z_h at the block height h when the the signature was provided. Define this sum as V(u). Pick whichever chain, u, has the highest value for V(u) as the valid chain. This is the chain that is the most strongly supported by 'clean inputs.'

Time for a break

I plan to continue later and will provide a specific description of block minting rules that allow for pure PoS consensus under this scheme. It’s time consuming to write down all these ideas on paper. If you’re interested in what you read so far, post in the thread with questions and comments to encourage me to continue. Otherwise, I will likely choose to work on something else and leave this thread incomplete.