Proof of Stake
Proof of Stake is a proposed alternative to Proof of Work. Like proof of work, proof of stake provides a mechanism for determining who signs bitcoin transactions (see "main" bitcointalk thread, and a Bounty Thread).
It was probablly first proposed here by Quantum Mechanic. With Proof of Work, the probability of mining a block depends on the work done by the miner (e.g. CPU/GPU cycles spent checking hashes). With Proof of Stake, the resource that's compared is the amount of Bitcoin a miner holds - someone holding 1% of the Bitcoin can mine 1% of the "Proof of Stake blocks".
Some argue that methods based on Proof of Work alone might lead to a low network security due to Tragedy of the Commons, and Proof of Stake is one way of changing the miner's incentives in favor of higher network security.
Here is one attempt to describe an implementation of Proof of Stake.
Motivation For Proof of Stake
- A proof-of-stake system might provide increased protection from a malicious attack on the network. Additional protection comes from two sources:
1) Executing an attack would be much more expensive. 2) Reduced incentives for attack. The attacker would need to own a near majority of all bitcoin. Therefore, the attacker suffer severely from his own attack.
- When block rewards are produced through txn fees, a proof of stake system would result in lower equilibrium txn fees. Lower long-run fees would increase the competiveness of bitcoin relative to alternative payments systems. Intuitively reduced fees are do to vast reductions in the scale of wastage of resources.
The Monopoly Problem
If a single entity (hereafter a monopolist) took control of the majority of txn verification resources, he could use these resources to impose conditions on the rest of the network. Potentially, the monopolist could choose to do this in malicious ways, such as double spending or denying service. If the monopolist chose a malicious strategy and maintained his control for a long period, confidence in bitcoin would be undermined and bitcoin purchasing power would collapse. Alternatively, the monopolist could choose to act benevolently. A benevolent monopolist would exclude all other txn verifiers from fee collection and currency generation, but would not try to exploit currency holders in any way. In order to maintain a good reputation, he would refrain from double spends and maintain service provision. In this case, confidence in Bitcoin could be maintained under monopoly since all of its basic functionality would not be affected.
Both benevolent and malevolent monopoly are potentially profitable, so there are reasons to suspect that an entrepreneurial miner might attempt to become a monopolist at some point. Due to the Tragedy of the Commons effect, attempts at monopoly become increasingly likely over time.
How Proof of Stake Addresses Monopoly Problems
Monopoly is still possible under proof-of-stake. However, proof-of-stake would be more secure against malicious attacks for two reasons.
Firstly, proof-of-stake makes establishing a verification monopoly more difficult. At the time of writing, an entrepreneur could achieve monopoly over proof-of-work by investing at most 10 million USD in computing hardware. The actual investment necessary might be less than this because other miners will exit as difficulty increases, but it is difficult to predict exactly how much exit will occur. If price remained constant in the face of extremely large purchases (unlikely), such an entrepreneur would need to invest at least 20 million USD to obtain monopoly under proof-of-stake. Since such a large purchase would dramatically increase bitcoin price, the entrepreneur would likely need to invest several times this amount. Thus, even now proof-of-stake monopoly would be several-fold more costly to achieve than proof-of-work monopoly. Over time the comparison of monopoly costs will become more and more dramatic. The ratio of bitcoin's mining rewards to market value is programmed to decline exponentially. As this happens, proof-of-work monopoly will become easier and easier to obtain, whereas obtaining proof-of-stake monopoly will become progressively more difficult as more of the total money supply is released into circulation.
Secondly, and perhaps more importantly, a proof-of-stake monopolist is more likely to behave benevolently exactly because of his stake in Bitcoin. In a benevolent monopoly, the currency txn continue as usual, but the monopolist earns all txn fees and coin generations. Other txn verifiers are shut out of the system, however. Since mining is not source of demand for bitcoin, bitcoin might retain most of its value in the event of a benevolent attack. Earnings from a benevolent attack are similar regardless of whether the attack occurs under proof-of-stake or proof-of-work. In a malicious attack, the attacker has some outside opportunity which allows profit from bitcoin's destruction (simple double-spends are not a plausible motivation; ownership of a competing payment platform is). At the same time, the attacker faces costs related to losses on bitcoin-specific investments which are necessary for the attack. It can be assumed that a malicious attack causes the purchasing power of bitcoin to fall to zero. Under such an attack, the proof-of-stake monopolist will lose his entire investment. By contrast, a malicious proof-of-work monopolist will be able to recover much of their hardware investment through resale. Recall also, that the necessary proof-of-work investment is much smaller than the proof-of-stake investment. Thus, the costs of a malicious attack are several-fold lower under proof-of-work. The low costs associated with malicious attack make a malicious attack more likely to occur.
Why Proof of Stake Would Likely Decrease Long-run Txn Fees Considerably
In a competitive market equilibrium, the total volume of txn fees must be equal to opportunity cost of all resources used to verify txns. Under proof-of-work mining, opportunity cost can be calculated as the total sum spent on mining electricity, mining equipment depreciation, mining labor, and a market rate of return on mining capital. Electricity costs, returns on mining equipment, and equipment depreciation costs are likely to dominate here. If these costs are not substantial, then it will be exceptionally easy to monopolize the mining network. The fees necessary to prevent monopolization will be onerous, possibly in excess of the 3% fee currently charged for credit card purchases. Under pure proof-of-stake, opportunity cost can be calculated as the total sum spent on mining labor and the market interest rate for risk-free bitcoin lending (hardware-related costs will be negligible). Since bitcoins are designed to appreciate over time due to hard-coded supply limitations, interest rates on risk-free bitcoin-denominated loans are likely to be negligible. Therefore, the total volume of txn fees under pure proof-of-stake will just need to be just sufficient to compensate labor involved in maintaining bandwidth and storage space. The associated txn fees will be exceptionally low. Despite these exceptionally low fees, a proof-of-stake network will be many times more costly to exploit than the proof-of-work network. Approximately, a proof-of-work network can be exploited using expenditure equal to about one years worth of currency generation and txn fees. By contrast, exploitation of a proof-of-stake network requires purchase of a majority or near majority of all extant coins.
Implementation
There are currently a few distinct proposals on how to implement PoS
Cunicula's Implementation of Mixed Proof-of-Work and Proof-of-Stake
This suggestion is of a mixed Proof-of-Work / Proof-of-Stake system.
Cunicula's Note
Check the page history for the older implementation. I am replacing my description with a new system which I believe to be much more secure. The new system is a greatly improved version of Colbee's proof of activity.
Glossary
Voluntary Signatures - Voluntary signatures result from a random auditing processes. As blocks are mined, keys are selected for auditing based on random selection. The signatures provide public evidence that a public key owner is running a full node. Passing the audit allows a private key to remain active.
Active Keys - By default, public keys that appear in the blockchain are active. Public keys that provide voluntary signatures when requested remain active. Active public keys are eligible to participate in lotteries to sign PoW blocks and mine PoS blocks. This is remunerative. Public keys that fail to provide signatures become dead private keys.
Dead Keys - Keys that have failed to provide signatures lose lottery eligibility. Dead keys can no longer mine PoS blocks. However, these dead keys can still be used to generate txns. Network maintenance is supported primarily through mandatory fees levied on coins sent by dead keys. After coins are sent using a dead key, the key becomes active again.
Mandatory Signature Sequence - In order for a PoW block to be valid and enter the blockchain, it must be signed by a sequence of 5 randomly selected active keys. The fifth signatory in the sequence mines a PoS block.
PoS block - The fifth signatory of a PoW block must mint his own block without any PoW submission at all. This block is called a PoS block.
Coin-age - Coin age refers to the age of txn inputs. Coin age is equal to the number of coins sent times the average age on these coins. Age is measured in blocks. Age is reset to 1 block whenever a coin is sent AND whenever a coin provides a signature (both mandatory and voluntary signatures count). Coin-age is used to calculate mandatory fees.
Demurrage Fee - Chain Security is supported primarily through a demurrage tax on sent inputs. This tax proportional to average input age as measured in coin-years. I suggest 5% per coin-year as a reasonable fee. Active keys avoid demurrage fees simply by remaining active. Dead keys must pay demurrage. The opportunity to evade demurrage motivates activity.
Optional Fee - Fees are used to ration block space. Blocks select prioritize txns with high fees. If demurrage fees alone are insufficient to motivate txn inclusion, the user can add an optional fee to his txn.
Fee Fund - Both optional fees and demurrage fees enter a fund, rather than being distributed directly to miners. Fees are added to the fund immediately, so there is a weak incentive to include high fee txns in blocks. The PoW miner receives a distribution equal to 0.1% of the accumulated fund. The first four mandatory signatories also receive 0.1% each. The PoS block miner receives 0.1% as well, but his takings will differ slightly because the fund is updated based on txns included in his block. Use of a fund reduces volatility in mining reward.
Root Private Key - The root private key has full spending and signing authority. When significant balances are held, this key should be kept as an offline backup to guard against theft.
Stake Signing Key - Private Key can delegate signing and sending authority to one other private key. The delegated key can sign blocks and has limited authority to send coins. Authority to send coins is determined by two positive constants, t and k. The following txn rule limits the stake signing keys' spending authority:
Change Returned to Public Key >= all coins sent to other addresses * {max(k,k*(t/coin-years on public key)}
k=9 and t=1/12 are suggested as possible parameters. These parameters allows the stake signing key to spend up to 10% of the total key balance per month. The max value at risk in event of theft of
this key is 10%. Holders of large balances 'zero-out' their coin-age frequently via mining and face less theft risk. If this occurs once per week, for example, the large balance holder will only
risk be able to spend up to 2.3% of their balance per week and will only lose 2.3% in the event of theft. Once theft is detected, all remaining coins can be moved to a secure computer using the
root private key.
Does this system exhibit Constant-Returns-to-Scale ?
While the formal theory behind this has yet to be laid out in detail, simulations indicate that the system is fully described by a constant returns-to-scale Cobb-Douglas production function. Generation rate over a long time span is almost perfectly predicted by the following equation, where Q is generation per unit time, k is the number of coins invested in generation, h is hashing power, A is an arbitrary constant which is inversely proportional to difficulty, and p is the parameter described in the previous section.
Q = A*k^(p)*h^(1-p)
How could we see constant returns to scale here?
Returns-to-scale in this system are subtle. If you double hashing power at one point in time, then you double the probability that you will find a block in the current hashing round. Therefore, intuitively one might think that doubling hashing power would allow you to generate double the amount of bitcoin generated per unit time on average. However, this is not true. Outcomes in each round of hashing affect outcomes in subsequent rounds of hashing. In this system, failure to find a block in the current period leads to decreased expected waiting time in the next round (since if you fail in the current round you get the consolation prize that the next round will have an easier target). This decrease in future waiting time provides some compensation for not mining the block immediately. Thus, doubling your chance of mining the block immediately does not double your output over a longer period.
Stylized Example (You get an outcome that works like this when p is close to 1)
Consider a system where: you have a 0% chance of mining coins at less than 6 coin confirmations, a 50% chance of mining coins at 6 coin confirmations, and a 100% chance of mining coins at 7 or more coin confirmations.
Half the time you will mine your coin after 6 confirmations. The other half you will mine your coin after 7. Therefore, it will take 6.5 rounds on average to mine a block.
Now what if you double hashing power. Remember that this doubles your chance of mining a block at any given stage. Now.. you have a 0% chance of mining coins at less than 6 coin confirmations, a 100% chance of mining coins at 6 or more coin confirmations,
Therefore, it will take 6 rounds on average to mine a block.
Here you have doubled hashing power, but only increased average output per unit time by a small amount.
Infeasibility of Pure Proof of Stake Under this System
Note: in the limit when p -> 1 (that is p approaches pure proof of stake), you approach a situation where you have a 0% chance of mining coins at less than x coin confirmations, but a 100% chance at x+1 coin confirmations, where x depends soley on difficulty. Mining becomes completely deterministic and doubling hashing power has no effect on output at all. Essentially miners take turns to mine blocks. The frequency with which a miner's turn comes up is equal to his ownership share in the total volume of coins actively used for mining. This sounds really good, but a fatal problem arises if participation falls. A fall in participation would make it impossible for anyone to mine blocks. Particularly, worrisome is that if participation is at 100%, a loss of some coins would interrupt the blockchain forever with no possible remedy except location of the missing coins. Even without a loss of coins, simply transferring coins across wallets can disrupt turn-taking and freeze the blockchain forever. For these reasons, it is necessary for block mining to retain a random element and not follow a deterministic, pure proof of stake system, i.e. p can safely be 0.8 or 0.9 or even 0.99, but 0.9999999999999999 would make complete failure of the blockchain a certainty.
Meni's implementation
This proposal is for a proof-of-work (PoW) skeleton on which occasional checkpoints set by stakeholders are placed. In one variant, double-spending is prevented by waiting for a transaction to be included in a checkpoint; the variant described here uses cementing to prevent double-spending, and checkpoints to resolve cementing conflicts.
Proof of work
Miners use their hashrate to find blocks and build the blockchain exactly as with the pure PoW system. They receive any new generated coins from the block; there will be two kinds of transaction fees, one of which is a mining fee given to the miner who finds the block, just like the PoW transaction fees.
Signatures
One block every 100 blocks (a different number can be used instead) is a signature block. When a signature block is found and confirmed with several subsequent blocks, stakeholders (people who have bitcoins) are expected to sign it by using a private key associated with their address which contains coins to sign the block hash. If there are several blocks of the same height, an address should not sign more than one of them. The signatures are broadcast on the network and included in a future block. For every candidate block, the total weight of all signatures is tallied (the weight of an address is determined mostly by the number of coins in it, as of the last signature block). Stakeholders will be able to collect signature fees when providing a signature, proportionally to their weight.
At the basic level, there are no rules to choosing which of several conflicting blocks to sign, stakeholders should just choose one.
Cementing
Cementing is a node's reluctance to do a blockchain reorganization. A node will reject any new block found if it contradicts a 6-block deep branch it is already aware of and currently considers valid. That is, once a node receives 6 confirmations for a block, it will not accept a competing block even if it is part of a longer branch.
In a pure PoW system this is problematic to do because a node could be stuck on "the wrong version" - if an attacker isolates the node and feeds him bogus data, it will not embrace the true, longer chain when he learns of it. However, using PoS to have the final say in such situations makes this possible.
Branch selection
When a node needs to select which of several branches is valid, it chooses one based on the following criteria in increasing importance (each one is overridden by the next):
- Branch length (total difficulty of all blocks), as in a PoW system.
- Cementing - an already cemented block will not be replaced by a longer branch.
- Signatures - even a cemented block will be overridden by a signature block with signature weight more than half the total possible weight by some margin.
If the conflict is so long that it contains more than one spot for a signature block, the conflicting signature blocks will be traversed earliest to latest, each time choosing the branch with the majority vote. After the newest uncontested signature block it proceeds to use cementing and branch length.
A signature block with no clear majority will be considered tied, and will not override the other criteria. Signature fees will not be given out but instead carried over to the next signature spot, to encourage stakeholders to participate then.
Double-spending prevention
A good level of security can be achieved by waiting for a block to be cemented. By that time it is safe to assume that the network recognizes this block and will not easily switch to a different block, even if a longer branch is presented.
A more authoritative confirmation is enabled by waiting for a signature block. Once a block achieves a majority (and some more time is allowed for this majority to spread in the network), it is extremely unlikely that the network will ever switch away from this block.
Weights
The weight of every address starts at 0. When an address provides a signature, its weight increases so that after several signatures, the weight approaches the number of coins in the address as of the last signature block. For example,
New weight = 0.9 * Old weight + 0.1 * Balance
If a signature is not provided by the address in a signature block, its weight decreases:
New weight = 0.9 * Old weight
This way, addresses whose owners do not wish to participate in signing do not hamper the ability to reach a majority.
If an address signs two conflicting blocks, its weight is reset to 0. This is to limit the power of malicious stakeholders.
If coins move to a new address, weight is proportionally taken away from the addressed, but is not transferred to the new address. The new stakeholder will have to build up his weight.
Malicious stakeholders
The system is resilient against stakeholders who misuse their signature power, even if they have a majority of the bitcoins. Since their only obligation is to not sign conflicting blocks, the only way they could double-spend is if they first sign one block so it achieves a majority, then sign a different one so that it achieves a bigger majority. Generally this will not work. A short while after a majority is achieved, most of the network will be aware of the relevant signatures. If a different signature is broadcast, the conflict will be detected and both signatures will be ignored. This will cause the current majority block to become tied, but the network is already cemented on it and will vote for this branch in the next signature block. The weight of the attacker will by then reduce to 0 so he will be unable to create more disruption.
Another attack is refusing to sign blocks to keep them tied. Since this causes a decay of the weight, they can only stand in the way of a majority for a short time.
Denial of service
The method as described does not solve a denial of service scenario. A majority miner could create only blocks with no transactions (or with many transactions missing) and reject all other blocks.
This may be solvable by adding some measure of the transaction in a block to the selection criteria, such as Bitcoin days destroyed.
Also, proposals to replace the block chain with a directed acyclic graph have been made, and could be used to make it easier to include transactions.
Key difference between the two proposals
In Cunicula's system, voting power is determined by combining (multiplicatively) your hashrate and stake. This would be problematic if small players could not compete effectively with large players. Though we are waiting on a formal mathematical proof, evidence to date suggests that small and large players would have an equal competitive footing. Simulations described in this thread [1] indicate that small players are competitive with large players because the multiplicative combination of hashrate and stake exhibits constant returns. Evidence in the thread suggests that these simulation results are accepted by both Cunicula and Meni.)
In Meni's, there's a skeleton based purely on hashrate, and superimposed on it are occasional checkpoints set by stakeholders. You can contribute PoW without having stake, and you can contribute PoS without having work, and in both cases your voting power and reward is linearly proportional to the resources you have.
PPCoin
PPCoin is the first known implementation of a combined PoS/PoW system (released August 19 2012).