Topic: Nothing at stake robust Pure Proof of stake - page 3. (Read 5365 times)

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.

hmm.. A lot of POS talk lately. It is a nice garden to play thought experiments in, I'll admit.. 

If I write my own POS chain, from the genesis block, in secret, I can make sure that my chain doesn't have any/many double signatures ?

I can make it anything I like.. and obviously wouldn't release it until it had a greater 'V(u)' than the current valid chain.

The only way I know of choosing the 'valid' chain, if you can call it that, is by centralised checkpoints..

As for a punitive scheme, check out Slasher by Vitalik.. https://blog.ethereum.org/2014/10/03/slasher-ghost-developments-proof-stake/

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.