Difference between revisions of "User talk:Holy-Fire"
(→Proof of Stake design outline)
m (Removed Luke-jr's vandalism of my talk page)
|Line 1:||Line 1:|
== Proof of Stake design outline ==
== Proof of Stake design outline ==
Revision as of 18:34, 6 January 2013
Proof of Stake design outline
Constants (for example)
- POSGEN = 250000 // genesis block from which the fork (that includes the PoS protocol change) begins
- SIGBLOCK = 100 // signatures block at every SIGBLOCK block
- POWCONFIRMS = 6 // cementing rule for regular PoW after 12 blocks
- POSPOWRATIO = 0.1 // proportion of the reward at each PoS checkpoint that goes to stake holders
- STAKECUTOFF = 50 // must hold at least STAKECUTOFF bitcoins to provide a signature
Starting at POSGEN, every block B for which (B->count mod SIGBLOCK == 0) is considered to be a signatures block whose hash B->hash should be signed by privkeys that control at least STAKECUTOFF bitcoins, who would broadcast their signature via a message STAKEMSG to the Bitcoin network.
Each address should provide its STAKEMSG signature only once, to any branch that it saw (preferably a branch whose signatures block was signed with the most bitcoins so far), and it may choose to do saw anywhere between position B->count and (B->count)+SIGBLOCK (exclusive).
Nodes should re-broadcast these STAKEMSG messages that signed B->hash, and miners should include STAKEMSGs in the blocks between B->count and (B->count)+SIGBLOCK (exclusive). There would be an optional txn fee that the stakeholders can pay by attaching this fee to their STAKEMSGs, in order to give incentive to the miners to include STAKEMSGs in the blocks.
The coinbase (txn fees + reward subsidy) of block (B->count)+SIGBLOCK is divvied up as follows:
- (i) coinbase*POSPOWRATIO is divided among the stake holders who signed block B->count
- (ii) coinbase*(1-POSPOWRATIO) goes to the miner who generated the block
- In (i) we divide proportionally among stakeholders according to the amount of bitcoins that they controlled at block B->count
An address must have at least STAKECUTOFF bitcoins at block B->count in order to to provide a STAKEMSG. This means for example that if an address with more than STAKECUTOFF bitcoins has transferred all of its bitcoin the an empty address between B->count and (B->count)+SIGBLOCK then this address can still provide a STAKEMSG after this txn, but the empty address cannot because at block B->count it had 0 bitcoins.
Each ECDSA signature is 512 bits, the total number of bitcoins is 21000000, so 64 bytes * 21000000/STAKECUTOFF gives a theoretical limit of about 26 megabytes for the total size of STAKEMSGs in SIGBLOCK blocks, assuming that STAKECUTOFF==50 (the ECDSA pubkey can be extracted from the signature, therefore we can assume that the overhead is small). The theoretical limit is the worst-case scenario, in practice it's expected that addresses that control much more than STAKECUTOFF would participate in order to get higher proportion of the reward, etc.
Nodes should refuse to switch to a different branch with higher PoW difficulty if that forked branch starts more than POWCONFIRMS blocks before their current branch. The advantage of this is that it provides good security from double-spending by an attacker who prepares a secret fork, i.e. if after more than POWCONFIRMS you see that the distributed mining power continues to work on the branch that you have then it gives confidence that an attacker couldn't reverse a txn that occured in those POWCONFIRMS blocks. The disadvantage is that an attacker could try to create havoc and dilute the distributed mining power, by releasing his competing fork of POWCONFIRMS blocks and splitting the nodes into different branches because of network propagation time, but at the next signatures block after at most SIGBLOCK blocks it is highly likely that the network will re-unite.
Nodes should switch to a branch which replaces more than SIGBLOCK of the blocks in their current branch only if it has more signature blocks, and the sum of all bitcoins controlled by the addresses that provided the signatures in these blocks is larger (if an address participated in several of these signatures blocks then it is counted multiple times in the sum). Here too the advantage is that you can much more secure from double-spending attacks if the height of the relevant txn is more than N*SIGBLOCK blocks, because an attacker would have to collude with malicious stakeholders N times (as well as needing hashpower to create a secret fork of more than N*SIGBLOCK PoW blocks) in order to reverse this txn.
Another advantage is that the signatures blocks may be regarded as checkpoints, so they could replace the need for harcoded developers' checkpoints in the official client, which protects from malicious developers.
Client behavior (+more protocol rules)
We wish to alleviate the risk that the stakeholders take when they need to use their passphrase to provide signatures, especially when the addresses that they control hold large amounts of bitcoins. Additionally, it's preferred that the client application would behave automatically instead of prompting for passphrase at every signatures block.
We basically want a digital signatures scheme in which the keygen generates a triple (privkey1,privkey2,pubkey0) where privkey1 and privkey2 are unrelated to each other, you can sign either with privkey1 or with privkey2, and verify the resulting signature with pubkey0. It'd be used for PoS by using privkey1 to do actual txns and using privkey2 only for providing the PoS signatures to the signatures blocks. This means that if privkey2 gets stolen then it doesn't amount to much, you can transfer your bitcoins to another address and re-generate a new privkey2 for it, so it's ok to store privkey2 in the clear.
We cannot implement this scheme directly with ECDSA, but we can do something that's pretty close: simply by having two pairs (privkey1,pubkey1) and (privkey2,pubkey2) and linking between them, e.g. by signing with privkey1 a message that says that pubkey2 is the public key of your 2nd pair, and from then on you can start using privkey2 to provide the PoS signatures.
What it would mean for the blockchain is that when you provide a STAKEMSG, there would be an additional field that you can include in it, and this field would contain pubkey2, meaning that starting from the next checkpoint block you are allowed to use privkey2 in order to provide signatures for the address that's controlled by privkey1.
The protocol rule would be that only first pubkey2 that the stakeholder provides is respected, meaning the nodes should start scanning at POSGEN for the first STAKEMSG that linked pubkey2 to pubkey1 (DoS attacks?), and then deduce how many bitcoins pubkey1 controls. Maybe the client should cache this data (security risk?).
The pubkey that would be extracted from subsequent STAKEMSGs is pubkey2 rather than pubkey1, therefore in order to tell how many bitcoins are controlled by those STAKEMSGs we store in every STAKEMSG an additional field that specifies the height of B->count relative to the block in which pubkey1 and pubkey2 were linked (and then the protocol rule would be that only this particular linkage should be respected). If we use e.g. 3 bytes for the relative height field, then privkey1 will be needed to create a new linkage block after about 320 years (assuming 10min blocks).
Note: if the pubkey2 field of STAKEMSG is empty then the signature field of STAKEMSG signed just B->hash, and if the pubkey2 field of STAKEMSG isn't empty then the signature field of STAKEMSG signed "B->hash + pubkey2".
With ECDSA signatures are 512 bits and compressed pubkeys are 258 bits, so it's not so bad because the STAKEMSGs with the extra pubkey2 field would be infrequent. In fact, we can save more space by defining the protocol so that only hash(pubkey2) is put in the extra field, because of the feature of ECDSA that you can extract pubkeys from signatures. This means that the extra field can be just (say) 128 bits hash, but more computing power will be needed to verify the signatures blocks.
This means that you wouldn't need to enter your passphrase in order to provide PoS signatures, so that the client app can work automatically, as preferred.
Security from attacker that denies txns
Note: this is unrelated to proof-of-stake?
Motivation: while proof-of-stake provides stronger security from double-spending attacks, an attacker with 51% hashpower (and without any stake) can still attack the network by generating empty blocks, thereby denying everyone from transacting. If the attacker releases his branch at certain intervals before the signatures block, then the competing branch by the rest of the distributed hashpower might have never been created because the miners would try to extend the attacker's branch, which means that the stakeholders would only have a single branch to sign. Suppose that we have simple protocol rule that requires at least one txn in every block, if there aren't any txns during some time period then that's ok because there wouldn't be a need to generate a new block then, but still this simple rule isn't helpful because the attacker can just transfer some coins to himself in the blocks of his secret branch. What we really want is BDD, meaning that after the attacker spends his coins in the block that he generated, he cannot use those coins again.
Protocol rule: we require that the total BDD weight of one of the last (say) 10 block is at least (say) 20% of the average BDD weight of blocks in the last day, or else we require the difficulty of the 10th block to correspond to twice as much time (this is the basic idea, a version with more continuous parameters could be better). This means that if an attacker tries to deny most/all txns, he will have to generate some 20min blocks, while the rest of the distributed hashpower only needs to generate 10min blocks, so the attacker has a significant disadvantage as he tries to compete with the honest hashpower.
One drawback is that during a 'slow day' without many txns, the performance of the network could degrade to 20min blocks at certain time periods, even though it isn't being attacked at all.
Problem: if it's a slow day on the real network, then an attacker could prepare a branch that outcompetes the distributed network, because if he spends old coins in his branch then he will need less difficulty.
Proof of Stake proposals attempt to address 3 major issue:
(1) Better security from double-spending attacks
(2) Better security from denial-of-txns attacks
(3) Being more energy-efficient than PoW
This design outline claims to address (1) and (2) in the sense that it provides better security without introducing new risks. It doesn't attempt to address (3) directly, but the added security that proof-of-stake provides may result in less need for PoW hashpower.
Proof of Stake idea1 (by coblee)
Instead of including in the blockchain all the signatures that the stakeholder provide, we only include a single winning signature. The stakeholders try to sign the block hash with their privkeys, and we then hash each such signature and get its current hash-weight (the smaller hash-weight the better). The winning privkey is the one with the biggest coins-held/hash-weight value (maybe more sophisticated calculation instead of this division). Assuming that the hash function is random, this calculation should imply that an address that holds 2N coins is twice as likely to win compared to an address that holds N coins.
Unclear: all blocks should be signed by stakeholders, or only checkpoint blocks in order to allow better network propagation etc.
The protocol rule is that the branch with the biggest function(difficulty, signatures) wins. If an attacker who holds N coins tries to compete with the distributed network that holds M coins, and we assume M>N, then the distributed network holds more stake and is therefore more likely to generate signatures with better weights, thereby creating a branch that outcompetes the attacker's branch.
The benefits of this idea are: less blockchain bloat, and less network communication because nodes shouldn't propagate the non-winning signature if they're already aware of another signature that outcompeted it.
Problem: if each wallet tries to sign with all of its privkeys, then we wouldn't want to establish linkages in the blockchain between all of its signing-pubkeys with its normal-pubkeys.
Possible solution: deterministic wallet, so when your signature wins you include in the txn a field that specifies its idx in the deterministic wallet, i.e. if the linkage is between pubkey1 and pubkey2, then the pubkey that corrensponds to the privkey that signed is hash(pubkey2|idx) and all the nodes can verify it.
Proof of Stake idea2 (by coblee)
99% of the reward of each block goes to the miner, and 1% of the reward is given to a pseudorandom address.
The pseudorandom address is selected deterministically as a function of the block hash, so that an address that holds more coins is more likely to be selected, as follows: we use to block hash to get a random index of 1 satoshi among all the satoshis that have been produced so far, and follow the txns in which this satoshi moved, until we reach an unspent txn, so the address that controls this satoshi is selected. This means that if one person holds 200 coins in several addresses, and another person holds 100 coins in several addresses, then it is twice as likely that one of the addresses of the first person will be selected.
Then in the next (say) 120 blocks, the stakeholder who received that 1% of the reward should spend it, and thereby provide proof of stake for the branch. The branch with higher function(difficulty, proof-of-stake) wins. If the winning address didn't spend the coins within 120 blocks, then it loses them. An attacker who tries to prepare a forked branch cannot spend these 1% coins because he doesn't control the privkeys of these addresses.
Benefits: having encrypted wallet with passphrase could be OK, only when your address is selected you need to access your privkey, and there's a certain time interval in which you may do it. No need for nodes to propagate the winning signature, as in idea1.
Variation: stakeholders lose a little (e.g. 0.5 coins) if they don't provide proof-of-stake, and keep their entire stake otherwise. The address that was selected should do a txn that references the block in which it was selected, and is otherwise required to keep holding at least 0.5 coins in the next 120 blocks (or less than 0.5 if it had less when it was selected). If within 120 blocks it doesn't do the txn that references the block that it was supposed to provide proof-of-stake for, then it loses 0.5 coins (or less if it had less).