Bitcoin Forum

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.    

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.

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.

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 (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.

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.

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

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.

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..

I disagree.

We both disagree.

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.

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.

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.

Hi benjamin_bit

Are you linked to Kushti and his PoS working group?

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.

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

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.
8) 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.

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).

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.

Etlase2! (That is you ?) hello..  :)

Love that you're still plugging Decrits.

As for this POS/POW conundrum, I am realising that this is a psychological/philosophical argument. Mathematically some people will not be swayed - on both sides  ;D

POS systems need a startup value to initialise (basically). That's fine. But where this 'number' comes from, always troubles me. Average Joe User will not be anywhere near it. His software client will deal with it, and that will come from some github repo that someone else has compiled. Probably the same main repo most people use. That is the weak link and where the eventual attack will come IMHO.

And that's about it. However you wrap it up, some of us find that discomforting just as some find POW untenable.

You cannot hack a POW chain in this way. The chain itself is INDEPENDENT of the software, unlike POS systems. POW chains can be compared to another POW chain on it's own merits/work.

I'm thinking that eventually the attack on POS will come from a large POW stake holder. Sort of like currency wars. One coin attacking another.

Sounds exciting.
 

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. 

No, it is not.

As I said - the VALID POW chain can still be determined without any outside assistance.

Once you have hacked the repo - i can always / later verifiably proove that this POW chain is better than that one. By summing the work.

You can't with POS.

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.

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. 
 

I think it doesn't work.

1) If I get control of a private key that in the past had lots of coins that were used for staking, by creating a parallel chain I can make some inputs of the valid chain "unclean", effectively reducing its V(u).

2) If I get control of a private key that in the past had lots of coins that were not used for staking, then my coins are "clean" and I can rewrite history from that moment in time by creating a chain with more V(u).

By combining 1 and 2, the nothing at stake problem is still a problem.

I'm working on a variation of PoS that will help with this. Please wait for it, the whitepaper is still being reviewed.

The more I read your posts the more retarded I become  :(

ok, I didn't understand blacklisting worked this way. I'll have to think about it a little more, but this at least gives me a new way to blacklist coins in the "valid" chain, now I have two methods for making it's V(u) lower.

For V(u) you should count accumulated work according to difficulty, not number of blocks.

What makes you think the same isn't true in some POS implementations

Which POS are you criticising, an actual one or a straw man you invented?

Just realised I posted this in the wrong thread earlier... :-[



Just so you don't miss it benjamin_bit...

https://nxtforum.org/consensus-research/multibranch-forging-approach/

First findings of the POS research group.

Pure POS.

I'm not trying to debunk POS. I really like certain aspects of it. Just some points, as with POW, still seem unfinished \ problematic.

This thread is about pure POS N@S resistance, and I have not seen an answer to that yet. Anywhere..

Can you refer me to \ explain a version of POS which can compare valid chains without any external 'number' to bootstrap the process?

(I'm not talking short range attacks, but long-range-total-chain rewrites)

Thanks.

I find your criticism valid and it applies to all forms of POS that I know of. However I don't see it as problematic, as long as you have a way to get that "external 'number'" in a secure/trusted/decentralized enough way.

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.


 

An attacker can blacklist his coin by signing multiple chain,
then he can switch his coin for new ones on an exchange,
and then blacklist them again,
rise and repeat.

Most of the coin would end up been blacklisted -> centralization -> poor security.

As a side note, if you prevent multiple input, you will end up with blockchain bloat very quickly.

Thanks gatra. That about covers my worries for long range attacks.

Thinking about the internal chain consensus rules, maybe a different approach might produce some new ideas.

It seems the 'issue' is that a rational miner will try to mine multiple chains, not just because he can, but more importantly because he might make more money that  way.

Why not remove that incentive altogether instead of punishing/blacklisting him for trying.

Currently in Pure POS systems, the miners still 'compete' for who gets to mint the next block. Whoever does, gets the spoils. Thereby incentivising multiple chain mining. I know TF in NXT picks a miner, but that does not stop miners trying to extend earlier chains in history to find a different TF path through the miners. If you see what I mean..

What if you say anyone can mint the next block, and then pay EVERYONE, EVERY block. Therefore every chain pays the same. Therefore there is no incentive to mine multiple chains.

You could use a 'Hash Clock' to pick a miner at random every 10 seconds or so (Like POW but more hashing power has no effect), and then you would calculate the value BLOCK FEES / TOTAL COINS.

This would give you a tiny percentage that you could multiply ALL ACCOUNT balances by to spread the fees proportionally to everyone..

So if the block fees were 1 unit, and the coin had 100 coins in all, every account would increase by 1/100, 1%.

This would mean that you would not need to actually run a node to be paid, BUT, if you were a large stakeholder and wanted your investment to be secured, why wouldn't you run a node ?

I can see that there are issues with the idea, why anyone would run a node, as there would be no gain financially from doing so.

The network would not run if enough miners did not choose to run a node. So I wonder - would stake holders choose to run a node - for the good/health of the network ?
 

I have an idea about changing they way the fees work in a pure POS currency.

Could you smooth the amount of fees generated over time alongside Proof of Stake as a low curve over a long medium of time such as a couple weeks? The way I see this working is that it would create a type of floating number which is the difference between the expected inflation and it's actual inflation and could be used to check past work through checks of the oldest, most trusted nodes? I feel like this kind of stuff will be some of the bigger changes to Proof of Stake, because then every block gets paid a minimum amount of fees depending on the amount of volume in a period. Make the whole general consensus that either you are supporting it's security or you are losing a small amount per year. Say you have lower inflation but higher fees then all nodes would be incentivized to claim their blocks and support consensus.

I'm still not convinced... I have problems with the following:

So if you send and then mint you get blacklisted. But that doesn't cover all the cases. If I get past ownership of coins that never minted, I can use that to mint in a second chain, at least up to the moment were those coins changed ownership. So I used "past input ownership" to create part of a second chain. By jumping thru different past ownerships I can get very close to the present and accumulate more work in my chain to the point that I might not even need current ownership.

you say "this satoshi" however there are no satoshis, only ins and outs. You can have colored coins and forbid loss of color, and that would be ok, but unless you color every satoshi (which is not practical), I don't see how you could match one satoshi from one chain to one in another chain. Colored coins can track coins in one chain, but when you have 2 competing forks, it's not that straightforward

the incentive to mine multiple chains is not only the payout for finding a block, but the possibility to perform a double spend!

if you give something to everyone, it's the same as doing nothing. Everyone ends up with the same % of the market cap. So this doesn't make much sense.

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).
 

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

@ Ben, research in the the 'Nothing at Stake' assertions has been published >>> https://bitcointalk.org/index.php?topic=897488.0

Please comment in the thread >>> https://bitcointalk.org/index.php?topic=897488.0. It would be good if we could get heads together from all aspects of cyrpto in the same place.