[Time for a break]

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.