Proof of stake brainstorming

[cunicula]

First off, I don't care whether you think proof-of-stake is useful or not. I want this thread to be about implementations only. I won't respond to off-topic posts.

Here is an idea I would like constructive feedback on:

Suppose that each wallet has two addresses (****a and ****b). The addresses are publically known to be associated with a single private key.
Users sign a block by including a txn in that block that moves X coins from address ****a to address ****b. In order for this signature to be valid, the X coins in address ****a must have at least (c/X) [rounded up] confirmations before they are sent, where c is some constant. This means that that the frequency with which a wallet can sign transactions (and thus add to the blockchain) is proportional to the number of coins it holds. The wallet would receive some interest on coins transferred from ****a to ****b to reward participation. Coins would have to be transmitted back from ****b to ****a before they could be sent to other addresses or used to verify additional blocks.

To make sure that blocks have time to propagate across nodes, it may be necessary that blocks arrive 5 or more minutes apart. One way to do force this is through hashing. For example you could require that transfer of coins from ****a to ****b is accompanied by solution to a hashing problem. Difficulty could be set so that blocks arrive at appropriate intervals on average. I am curious about whether and why this time gap is necessary and if there are alternative means of enforcing it besides hashing (i.e. some sort of decentralized timestamp).

Cue for responses:

Is the system above a reasonable method of implementing proof-of-stake or is it misguided in some way? Is it essential to force a time gap between blocks? Are there other decentralized ways to force this time gap besides hashing?

[ByteCoin]

Reading somewhat between the lines, what you appear to be doing is providing a mechanism for tying up portions of a user's coins for a number of blocks, the reward for which is some additional coins. Presumably the "tying up" transaction would contain a hash of a number of third-party transactions which the author approves of and wishes to confirm.

You say it would take c/X confirmations before the funds are untied. Are all confirmations created equal? Let's say I have 50 units of your funds. I can confirm a transaction by tying up all 50 units for c/50 blocks and that provides one confirmation. I could alternatively split it into 50 lots of 1 unit and confirm a transaction 50 times buy tying up 50 lots of 1 unit for c/1 blocks.

Minor issues that need clarification are: How do you have two addresses for one private key? Do all transfers tie the funds up for c/X confirmations?

A fundamental problem with the scheme is that people with a lot of funds who never spend them get more funds fastest. I don't think that this is a good way to bootstrap a currency.

It would be worth you editing your post to include a link to an explanation of "proof of stake" and a bit more about your goals by contrast with the existing system.

Interesting idea though...

ByteCoin

[Meni Rosenfeld]

You need to clarify exactly what is the problem you are trying to solve before analyzing solutions. Heck, I understand the problem and the solution approach and could barely follow you.

I'll assume the problem is this:

We need some rule to determine which branch of the block chain to consider valid. The current rule (using the branch representing the highest total difficulty) is vulnerable to attacks by an entity with high hashrate. Proof-of-stake systems seek to modify the decision rule so that attacking the network can only be done by those who have many bitcoins, and thus, have the least incentive to do so.

So, if this is the goal, we cannot assess how close your suggestion is to achieving it, because you haven't specified what would be the rule to choose between branches.

For just the technical part of actually signing a block, my preferred approach is this: Every address is associated with two key pairs. The address itself is a hash of the concatenation of the two public keys. Doing normal bitcoin transactions involve revealing both public keys, as well as signing the transaction with private key A. Signing a block involves revealing both public keys and signing the block hash with private key B. The weight of the signature depends on the number of coins belonging to the address up to the signed block (or alternatively, X blocks back). Key B doesn't need to be as well-protected as key A - if it's compromised, the owner just sends the coins to a different address. So he can maintain voting rights with bitcoins safely stored in a time capsule.

I'll add my thoughts about how to incorporate it in a system later.

[cunicula]

Thanks for the great comments, Meni and gigabyte. Sorry about being discombobulated. It is because I don't have a full understanding yet. For now, I will keep the first post as is because I like how the discussion is going. Later (once other posters have sorted me out sufficiently), I will edit the intro.

What is important about the current system (and the proof-of-stake solution I am imagining) is that you don't need to aggregate votes from multiple nodes before signing individual blocks. Aggregation emerges from competition to lengthen the blockchain. The longer blockchain is the valid chain.

Here is an analogy which might help.

Currently, miners finds a solution to minimization problem (1) with a value under the difficulty criteria. They submit this to sign block 1. After block 1, the minimization problem (1) changes to minimization problem (2). Subsequent signers may choose to confirm the validity of this block (or not). If they choose to confirm validity, they find a solution to the minimization problem (2), and use this to sign block 2. Alternately, they can reject validity. To do this, they find a solution to minimization problem (1) and use this to sign block (1). The new signature creates an alternate sequence of blocks (block 1 and block 2) vs. (block 1 and block 2a). The client treats the longest sequence of blocks as the valid sequence.

Consider an alternative to hashing:

Multiple miners find solutions to minimization problem (1). They find a range of minimum values (some very low-some high). They use these minimum values to vote on block 1. Votes associated with a low minimum value are assigned heavy weight. Votes with a high minimum value are signed low weight. If the value-weighted majority agrees that block 1 is valid, then block 1 is signed. Otherwise, block 1 is not signed.

What is wrong with this alternative? (and by analogy what might be wrong with Meni's proof-of-stake solution)

You need to collect information from many miners before you can add to the chain. Meni's proof-of-stake solution has this same feature (except you need to collect info from many stakeholders). In this thread, Quantum Mechanic proposes proof-of-stake: https://bitcointalk.org/index.php?topic=27787.0. Hashcoin (and later Mike Hearn) object that collection of information from many stakeholders before block signing poses severe bandwidth and storage problems. I am not aware of a counterargument. My point is that proof-of-stake can operate the same way as proof-of-work. A miners' frequency of block signing can be determined by stake rather than work. No voting is required. Solutions come from individual miners and the length of a chain of solutions indicates chain validity. Since miners need to wait for confirmations to add solutions, it is not practical for individuals to sign multiple blocks in a row.

[cunicula]

You say it would take c/X confirmations before the funds are untied. Are all confirmations created equal? Let's say I have 50 units of your funds. I can confirm a transaction by tying up all 50 units for c/50 blocks and that provides one confirmation. I could alternatively split it into 50 lots of 1 unit and confirm a transaction 50 times buy tying up 50 lots of 1 unit for c/1 blocks.

Yes, all confirmations are equal. Otherwise, you would have incentives to combine money into one wallet or separate money into different wallets. [There is still a minor issue like this related to rounding. Shouldn't be a big deal.]

Minor issues that need clarification are: How do you have two addresses for one private key? Do all transfers tie the funds up for c/X confirmations?

I not sure about the two addresses. Better to ask someone who knows about programming, private, public keys, etc., I'm winging it here. Meni has a suggestion. I have a suggestion below where you don't need two addresses. Instead you have the blockchain escrow coins.

Do all transfers tie the funds up for c/X confirmations?

No you can transfer funds freely, you only need to worry about c/X confirmations if you are trying to sign a block. One way of implementing this is through a central escrow address [shared by everyone], as follows:

(e.g. Signing block 1: Address A coins -> Escrow Address B ...  In block 2: Escrow Address B coins + txn fees + any generated reward coins -> Address A

Without inclusion of this send, block 2 cannot be valid. In this way, you don't need special addresses for each user. Escrow Address B just holds coins in escrow for return in the next block. The only purpose here is to prove coin control and reset the number of confirmations on coins in address A.  As long as you are not sending coins to escrow address B, you don't need to worry about confirmations.

[Meni Rosenfeld]

In the current system, it is not known what the next block will be before it is found. Every miner know a certain set of transactions and tries to find a block including them. When a block is found, which is a relatively rare event, it is broadcast and any remaining floating transactions will remain and can be included in the next block.

If you want several miners to verify a block before it is accepted, it means that they have to agree on the transactions to include before starting to verify it. This is a synchronization nightmare.


My own system is along the following lines.

Hash-based mining will continue more or less as usual. However, branch choice will depend not only on length, but on two additional factors: Signatures, to prevent double spending; and circulation, to prevent interfering with transaction confirmation.

Every 100th block (or 64th, or some other number) will be a signature block. It is mined normally, but once it is found and confirmed with 10 additional blocks, stakeholders (people who have coins as of the signature block) are invited to sign the block's hash with their private key (which can be separate from their transaction private key). Choosing between two branches will be very heavily influenced by the weight of the signatures on the last signature block.

An attacker with high hashrate who tries to build an alternative long branch will be rejected because it conflicts with a signed branch. Thus, someone who makes a large transfer can guarantee its security if he waits for a signature block.

To prevent the results from being skewed by coins whose owners are not interested in signing, the voting weight of an address will decrease for every block it doesn't sign. It will increase back to the normal weight for every block it signs. If coins are moved to a new address, the weight will reset to 0. Also, if an address signs two conflicting blocks, its weight will reset to 0.

If keeping the network secure, and thus maintaining the value of their stake, is not incentive enough, there will be a system to have a part of the transaction fees reserved for stakeholders, or maybe a separate signature fee (paid by those who wish to incentivize stakeholders to sign the next signature block).

This leaves the problem of an attacker trying to disrupt the network by reversing blocks and thus stopping transactions from being confirmed. For this, two more terms can be considered in evaluating a branch:

1. Circulation - how many different coins have circulated in the last 10 blocks. An attacker can try to displace all blocks, except for his own blocks which only include transactions sending money to himself (to make them appear like legitimate block). Unless he has lots of bitcoins, he will need to send the same coins back and forth. Branches where this is detected - that is, the total number of different coins circulated is low - will be penalized. This may be hard to compute, but some sort of useful approximation may be tractable.
2. Inclusivity - A block will be penalized for every transaction it excludes which has a high enough fee and has been floating for a while. A few transactions occasionally missing is ok, but when it becomes systematic it indicates someone trying to block a specific transaction.

[cunicula]

Meni, that is interesting.

Here are some questions about your idea:

Suppose that a malicious individual has access to major hashing power. Their intention is to stop transactions by flooding the network with invalid blocks.
Could they add invalid blocks to every fork they see? If so, it might take a very long time before a sequence of 100 (or 64) valid blocks in a row was created. Would this prevent any fork from ever reaching a new signature checkpoint?  Essentially could an attacker get the network stuck between checkpoints in your system? If this is a problem why not require signatures for every single block? Is there a sychronization problem related to adding these signatures?

Here is a revised version of my idea:

Miners who submit blocks must also submit coins for escrow in the blockchain. The escrowed coins must satisfy a 'coin-confirmation constraint'. By 'coin-confirmation constraint', I mean the product of the number of coins sent and the number of confirmations on those coins must be greater than or equal to some number. The blockchain escrows the sent coins and then returns them to the sender when the next block is found. There should not be a synchronization problem here because a single miner both finds the block and includes his coins in that block.

The 'coin-confirmation' threshold would be set relatively low so that say only 10% of extant coins would have to be actively used in mining to keep the system churning out blocks. If miners began to run short of coins, they would want to purchase them to prevent any blocks they find from going to waste. In fact, they would want to keep an oversupply of coins. If they happened to get lucky hashing, they would need to have these extra coins ready for inclusion in blocks.  Miners' demand for an excess coin hoard would prevent the system from ever getting stuck.

[Meni Rosenfeld]

Suppose that a malicious individual has access to major hashing power. Their intention is to stop transactions by flooding the network with invalid blocks.

Could they add invalid blocks to every fork they see? If so, it might take a very long time before a sequence of 100 (or 64) valid blocks in a row was created. Would this prevent any fork from ever reaching a new signature checkpoint?  Essentially could an attacker get the network stuck between checkpoints in your system? If this is a problem why not require signatures for every single block? Is there a sychronization problem related to adding these signatures?

I'm not sure you are fully aware what a >50% attacker can or cannot do.
He cannot add blocks which don't comply with the protocol, these will simply be rejected.
He cannot add transactions which send coins from addresses he hasn't the key for.
He can add blocks that exclude any or all floating transactions. By putting such blocks in a long enough branch, he can reverse blocks which do include these transactions.

So, whatever he does, eventually 100 blocks will be reached. It doesn't matter if some of these are useless blocks created by the attacker.

A possible problem is that he will cause the difficulty to increase and thus transactions will take more time to enter a block (since some of the blocks are the attacker's and don't include useful transactions), but that is a minor problem.


Having signatures for every block requires a lot of data to be passed around, and doesn't help much.

Here is a revised version of my idea:

Miners who submit blocks must also submit coins for escrow in the blockchain. The escrowed coins must satisfy a 'coin-confirmation constraint'. By 'coin-confirmation constraint', I mean the product of the number of coins sent and the number of confirmations on those coins must be greater than or equal to some number. The blockchain escrows the sent coins and then returns them to the sender when the next block is found. There should not be a synchronization problem here because a single miner both finds the block and includes his coins in that block.

The 'coin-confirmation' threshold would be set relatively low so that say only 10% of extant coins would have to be actively used in mining to keep the system churning out blocks. If miners began to run short of coins, they would want to purchase them to prevent any blocks they find from going to waste. In fact, they would want to keep an oversupply of coins. If they happened to get lucky hashing, they would need to have these extra coins ready for inclusion in blocks.  Miners' demand for an excess coin hoard would prevent the system from ever getting stuck.

This is interesting, but 10% of all coins owned by miners is way too high - especially since we are seeking to keep the network secure while reducing the overhead of mining. And with less than that, I don't think the disincentive to attackers is high enough.

[cunicula]

Okay, thanks that's helpful. How do stakeholders decide whether to sign the block with their private key or not? Can an attacker include double spends in every fork, so that there are no valid chains to sign?

Regarding my suggestion, I don't see any problem with 10% or 20% of coins being locked up in mining. These are just coins that won't circulate freely in the money supply. Since coins don't cost anything to create, there is no additional overhead (i.e., use of non blockchain resources) involved. In fact it should be resource saving because it would reduce demand for electricity and computing hardware (mining-related demand for these items would be partially diverted to bitcoin purchases). It also improves the security of accepting coins based on a small number of confirmations. The scarce resources we need to worry about are storage and bandwidth if anything. The approach I'm suggesting is very economical as far as these resources are concerned.

I'm just seeing a long list of benefits with no obvious downside. Could you explain more clearly what you think the problem is? In particular, can you define what you mean by overhead? And why it is useful to minimize your concept of overhead as opposed to some other one?

[Meni Rosenfeld]

Okay, thanks that's helpful. How do stakeholders decide whether to sign the block with their private key or not? Can an attacker include double spends in every fork, so that there are no valid chains to sign?

Double-spending means:
1. Buyer (attacker) sends money to seller.
2. Seller gives goods to buyer.
3. Buyer creates a new branch in which the coins are sent back to himself.

The proof-of-stake is only relevant for people willing to wait for it. If stakeholders have several candidate branches, each should choose one randomly or according to some rule. One of the branches will come out ahead as the most signed. For every transaction that was agreed upon, there are two possibilities - either it is included in the signed branch, in which case it is secure forever and the seller can send the goods; or it was replaced by another transaction, in which case the seller doesn't send the goods. So, if you wait for proof-of-stake, you'll never have a payment reversed after you've sent the goods.

Regarding my suggestion, I don't see any problem with 10% or 20% of coins being locked up in mining.

If I understand your suggestion correctly, it requires that 10% of the coins are owned by the miners. This means that miners possess 10% of the wealth of the world (at least, the part of it that is in the form of bitcoins). This means mining is a huge enterprise, instead of a lean service provider. What if I told you that for the internet to work, 10% of the global wealth needs to be at the hands of ISPs?

[cunicula]

If there is no mechanism for stakeholders to choose between chains, then why include stakeholders at all? Why not just have the miner who finds every 100th block flag it as a checkpoint (and prohibit reorgs past this point)? 

As regards my suggestion, your concerns seem to be based on a misunderstanding of opportunity cost. The relevant question is the opportunity cost associated with mining via stakeholding, not the value of the bitcoin used to mine. The majority of bitcoins are just sitting in wallets with lots of confirmations. Using this money to mine has minimal opportunity cost since it is being held as a store of value anyways. I think that people holding bitcoin could be persuaded to mine even if the rate of return on their assets was extremely small (say 1% per annum). Remember that they can 'withdraw' their money from mining and spend it with minimal delay. If people are willing to participate even with a very low rate of return, then the opportunity cost associated with participation is necessarily extremely small. By contrast, the opportunity cost of mining via hashing is quite high because GPUs and electricity are not held as stores of value. Consequently, for computing power-based mining, the value of resources used in the mining process is the opportunity cost. What I am proposing involves a tremendous reduction in mining overhead (properly measured as opportunity cost) not an increase as you suggest.

[Meni Rosenfeld]

If there is no mechanism for stakeholders to choose between chains, then why include stakeholders at all? Why not just have the miner who finds every 100th block flag it as a checkpoint (and prohibit reorgs past this point)?

Because there's no "the" miner. There are several miners, some of whom may be attackers, each of whom may find his own version of, say, block number 143100. Each of these blocks will have its finder flag that "My block is the real one!". How would a node know which branch to use?

If you suggest that a block will be automatically flagged if the branch built upon it is sufficiently ahead of all other branches, you leave the possibility that a node will be introduced first to a wrong version and then refuse to conform to the right version when he finds it.

Blocks aren't good or evil, all you have is synchronization, everyone should a agree on the same block. With stakeholder signatures you have that - once a block is signed, everyone can verify this and agree on the block. The only people who have some limited ability to mess this up are stakeholders, who have the least incentive to do so.

As regards my suggestion, your concerns seem to be based on a misunderstanding of opportunity cost. The relevant question is the opportunity cost associated with mining via stakeholding, not the value of the bitcoin used to mine. The majority of bitcoins are just sitting in wallets with lots of confirmations. Using this money to mine has minimal opportunity cost since it is being held as a store of value anyways. I think that people holding bitcoin could be persuaded to mine even if the rate of return on their assets was extremely small (say 1% per annum). Remember that they can 'withdraw' their money from mining and spend it with minimal delay. If people are willing to participate even with a very low rate of return, then the opportunity cost associated with participation is necessarily extremely small. By contrast, the opportunity cost of mining via hashing is quite high because GPUs and electricity are not held as stores of value. Consequently, for computing power-based mining, the value of resources used in the mining process is the opportunity cost. What I am proposing involves a tremendous reduction in mining overhead (properly measured as opportunity cost) not an increase as you suggest.

More likely, my concerns were based on a misunderstanding of your suggestion. Upon further reflection, it looks like it is not too dissimilar to my own, yet I believe mine is superior. You'll need hashing anyway because it's intractable to collect proof-of-stake for every single block. And there doesn't seem to be an advantage in holding coins in escrow (which is additional overhead) over collecting signatures, with voting weight which depends on the history of the coins.

[cunicula]

I agree that you need to include hashing to prevent some kind of information overload, but that isn't very relevant. You could have a system where 10 terahash is sufficient or one in which 50 gigahash is sufficient. If the systems provide equivalent security then the 50 gigahash system is obviously preferable. There should be very little incentive to amass lots of hashing power in an efficiently  designed stakeholding system.

I see what you mean by our schemes being similar.  I just feel like mine is more robust. I'm not clear on how people are rewarded for choosing certain checkpoints in your system, how the system handles mistakes (reversing a block with a majority of signatures), or whether the system is vulnerable to disruptive attacks between checkpoints. I think a system which handles all blocks similarly and does not use arbitrary checkpoints is preferable.

Anyways, no one pays attention to these issues so it is a moot point for the time being. Thanks for providing some great feedback.

[maaku]

Mini, instead of having an address represent a pair of keys, what about using the key associated with existing bitcoin addresses to sign a delegation certificate, which basically says "the owner of bitcoin address A approves of any blocks signed with key B". Delegation certificates could even be revoked, obviating the need to transfer money around if the block-verifying key is exposed.

It's a more general solution, doesn't require changing the bitcoin address format, and could be implemented without touching the block chain on an overlay network used by miners.

[Meni Rosenfeld]

Mini, instead of having an address represent a pair of keys, what about using the key associated with existing bitcoin addresses to sign a delegation certificate, which basically says "the owner of bitcoin address A approves of any blocks signed with key B". Delegation certificates could even be revoked, obviating the need to transfer money around if the block-verifying key is exposed.

It's a more general solution, doesn't require changing the bitcoin address format, and could be implemented without touching the block chain on an overlay network used by miners.

Sounds good.

[cunicula]

Mini, instead of having an address represent a pair of keys, what about using the key associated with existing bitcoin addresses to sign a delegation certificate, which basically says "the owner of bitcoin address A approves of any blocks signed with key B". Delegation certificates could even be revoked, obviating the need to transfer money around if the block-verifying key is exposed.

It's a more general solution, doesn't require changing the bitcoin address format, and could be implemented without touching the block chain on an overlay network used by miners.

If the key B can be transferred independently of key A, then this would separate ownership rights from voting rights. Voting rights would be worth very little to individuals because of the tragedy of the commons problem (you just rely on other people not to sell off their voting rights to would-be monopolists/attackers). A free market for pure voting rights is highly undesirable. It is important to ensure that the voter and the coin-owner are the same person.