Nothing at stake robust Pure Proof of stake

[benjamin_bit]

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.    

[spartacusrex]

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/

[benjamin_bit]

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/

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.

[jl2012]

Inputs that provide conflicting signatures can be blacklisted using an approach analogous to colored coins.  

So a previous owner of a coin will always have the power to burn the coin, no matter where and when it is sent. If the time is long enough even a single satoshi may taint a huge amount of coins. He may profit through a leveraged short before the attack.

[benjamin_bit]

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.

[benjamin_bit]

Inputs that provide conflicting signatures can be blacklisted using an approach analogous to colored coins.  

So a previous owner of a coin will always have the power to burn the coin, no matter where and when it is sent. If the time is long enough even a single satoshi may taint a huge amount of coins. He may profit through a leveraged short before the attack.

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.

[Ix]

Click my signature if you'd like to see my take on the solution.

[spartacusrex]

What if I created my own genesis block, with new accounts I have access to?

And a small botnet loyal to me. Playing along with the network.

How would a new user know my chain vs the original?

[benjamin_bit]

What if I created my own genesis block, with new accounts I have access to?

And a small botnet loyal to me. Playing along with the network.

How would a new user know my chain vs the original?

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.

[spartacusrex]

No, I don't use the old addresses. No extra coins.

They're new users. Don't have to convince them.

I do give most old users their balance back though so they don't mind which chain.

Keep the rest..

[achimsmile]

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

I disagree.

[ShroomsKit_Disgrace]

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

I disagree.

We both disagree.

[BootstrapCoinDev]

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.

As soon as an attack on the network happens (which must happen eventually for any alt to be viable tried and tested), the only problem is transaction processing is hindered and people choose to put the processing on hold. While this in itself can be very bad for business, the coins as they exist now in the network are STILL THERE and not lost in any way
In the long run a 51% attack will help strengthen the network and causes NO PROBLEMS for coins already confirmed in wallets.

[achimsmile]

Some good arguments by Vitalik:

https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

N@S seems like an urban legend.

[spartacusrex]

Err.. So Vitalik agrees.

'.the solution is simple: the first time they sign up, and every time they stay offline for a very very long time, they need only get a recent block hash from a friend, a blockchain explorer, or simply their software provider, and paste it into their blockchain client as a “checkpoint”. '

Trust.

BUT - he is saying that's no problem.

I disagree.

[Daedelus]

Hi benjamin_bit

Are you linked to Kushti and his PoS working group?

[Ix]

Trust.

BUT - he is saying that's no problem.

I disagree.

Do you have any reason for disagreeing, or just stubbornness? In my paper on the Decrits consensus algorithm, I called it common sense, because that's exactly what it is -- not trust. In bitcoin, in lieu of common sense, you have an algorithm that will idiotically allow anyone with enough hash power to commit fraud against you. To reduce the likelihood of this fraud, hundreds of millions and what will eventually be billions of dollars of wasted electricity and capital must be spent annually to make it more difficult. In stake algorithms, you have virtually no cost to protect against this, you must only rely on the user to be modestly aware of what millions or billions of other people who were watching the network think is the correct chain of events, and this is only if you specifically are being targeted for fraud. And how are you being targeted if you aren't even watching the network?

And with the DCA I even solved the problem so that you don't have to even use common sense if you haven't monitored the network recently -- except if a massive, one-time attack has occurred in the mean time. And again, it only matters if you were being targeted. Unlikely that you would part with a massive amount of goods without monitoring the network, though.

[benjamin_bit]

Hi benjamin_bit

Are you linked to Kushti and his PoS working group?

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

[benjamin_bit]

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.

[true-asset]

What do you guys think of Staked Proof of Work? https://docs.google.com/document/d/1LzY_dQz4jVDrHZq6BawSzT9rNRx_CaZou_fpEcu6CU4/edit?usp=sharing (ignore the Polychains part - that is really a separate technology).