Re: [Bitcoin-development] Proposal: Vote on the blocksize limit with proof-of-stake voting
Reserving my judgement until I've though about it more (design by committee scares me, and this voting sounds expensive), I think the SPV-verifiable moving median can be done by binning the space of block size limits, and for each node in the UTXO tree, a value for each bin is stored which is the sum of the corresponding bins of each of the children. The childless nodes - which correspond to the individual UTXOs - increment the appropriate bin of their parents according to the rules you mentioned. The bin values in the root node of the UTXO tree would then be added to those, weighted appropriately, of the previous N blocks. The hash of a node would be that of the bin values, concatenated with the child nodes' hashes. In this way, any step of the calculation of the median would produce a localized error in the UTXO tree that's easily verified. The number of bins would have to be kept relatively small in order to keep this from adding too much data to the UTXO tree branches though. On Mon, Jun 10, 2013 at 2:30 AM, Peter Todd wrote: > On Mon, Jun 10, 2013 at 04:09:26AM +, John Dillon wrote: > > My general comments on the idea are that while it's hard to say if a > vote by proof-of-stake is really representative, it's likely the closest > thing we'll ever get to a fair vote. Proof-of-stake is certainely better > than just letting miners choose; as you point out miners can always > choose to decrease the blocksize anyway so we only need a vote on > allowable increases. Proof-of-stake also clearly favors those who > actually have invested in Bitcoin over those who only talk about > Bitcoin. > > I'll also say that while I know people will complain about putting > politics into a technical problem, as I keep saying, is *is* a political > issue. The limitations may be technical, but the ultimate issue is a > very political decision about what we want Bitcoin to be. Yes, there > will be people campaigning left and right to get users to vote for > various limits with their coins, deal with it. Democracy is messy. > > Voting would take a lot of the nastier politics out of the situation, > perhaps somewhat ironically. It would quite clearly take control away > from the core development team, and the Bitcoin Foundation, and put it > back in the hands of the community; you can't argue conspiracy theories > that the Foundation is trying to control Bitcoin when there is a > completely transparent voting system in place. People will complain that > big Bitcoin players are throwing their weight around, but the blockchain > itself is a voting mechanism that is anything but 1 person = 1 vote. > > Of course I wouldn't be the slightest bit surprised if users happily > vote themselves into something looking like a centralized PayPal > replacement in the long run, but at least if that happens the process by > which they get there will be transparent and relatively democratic. > > > > A vote will consist of a txout with a scriptPubKey of the following form: > > > > OP_RETURN magic vote_id txid vout vote scriptSig > > > > Where scriptSig is a valid signature for a transaction with nLockTime > > 500,000,000-1 spending txid:vout to scriptPubKey: > > > > OP_HASH160 H(OP_RETURN magic vote_id txid vout vote) OP_EQUAL > > I just wanted to point out how general this mechanism is. Regardless of > what the scriptPubKey form is, standard, P2SH, multisig, whatever to > vote is to simply prove you could have spent the txout. > > > vote_id is the ID of the specific vote being made, and magic is included > to > > allow UTXO proof implementations a as yet unspecified way of identifying > votes > > and including the weighted median as part of the UTXO tree sums. (it also > > allows SPV clients to verify the vote if the UTXO set is a Patricia tree > of > > scriptPubKeys) vote is just the numerical vote itself. > > Ah, you're assuming a direct Patricia tree. Keep in mind that > scriptPubKey's can be up to 10,000 bytes long, and an attacker can use > that (with 10,000 other txouts) to create some extremely deep trees. I > said on IRC a few days ago about how skeptical I am of implementing > consensus critical systems with such huge differences in average and > worst case, but I'll admit this is a decent use-case. > > Having said that, proof to SPV clients leaves open the interesting > possibility that a third-party holding Bitcoins on your behalf can prove > that they voted according to your wishes, or even prove they voted > according to all their users wishes. Basically we'd add a rule for the > UTXO tree where a specific OP_RETURN form is included in the UTXO tree, > even though it is unspendable, and is removed from the tree if the > master txout is spent. Note that in this case by "prove they voted" we > mean the service actually taking the step of ensuring their vote was > recorded in the blockchain. > > > The vote must compute > > the median, rather than the mean, so as to not allow someone to skew the > vote > > by simply
Re: [Bitcoin-development] Proposal: Vote on the blocksize limit with proof-of-stake voting
On Mon, Jun 10, 2013 at 04:09:26AM +, John Dillon wrote: My general comments on the idea are that while it's hard to say if a vote by proof-of-stake is really representative, it's likely the closest thing we'll ever get to a fair vote. Proof-of-stake is certainely better than just letting miners choose; as you point out miners can always choose to decrease the blocksize anyway so we only need a vote on allowable increases. Proof-of-stake also clearly favors those who actually have invested in Bitcoin over those who only talk about Bitcoin. I'll also say that while I know people will complain about putting politics into a technical problem, as I keep saying, is *is* a political issue. The limitations may be technical, but the ultimate issue is a very political decision about what we want Bitcoin to be. Yes, there will be people campaigning left and right to get users to vote for various limits with their coins, deal with it. Democracy is messy. Voting would take a lot of the nastier politics out of the situation, perhaps somewhat ironically. It would quite clearly take control away from the core development team, and the Bitcoin Foundation, and put it back in the hands of the community; you can't argue conspiracy theories that the Foundation is trying to control Bitcoin when there is a completely transparent voting system in place. People will complain that big Bitcoin players are throwing their weight around, but the blockchain itself is a voting mechanism that is anything but 1 person = 1 vote. Of course I wouldn't be the slightest bit surprised if users happily vote themselves into something looking like a centralized PayPal replacement in the long run, but at least if that happens the process by which they get there will be transparent and relatively democratic. > A vote will consist of a txout with a scriptPubKey of the following form: > > OP_RETURN magic vote_id txid vout vote scriptSig > > Where scriptSig is a valid signature for a transaction with nLockTime > 500,000,000-1 spending txid:vout to scriptPubKey: > > OP_HASH160 H(OP_RETURN magic vote_id txid vout vote) OP_EQUAL I just wanted to point out how general this mechanism is. Regardless of what the scriptPubKey form is, standard, P2SH, multisig, whatever to vote is to simply prove you could have spent the txout. > vote_id is the ID of the specific vote being made, and magic is included to > allow UTXO proof implementations a as yet unspecified way of identifying votes > and including the weighted median as part of the UTXO tree sums. (it also > allows SPV clients to verify the vote if the UTXO set is a Patricia tree of > scriptPubKeys) vote is just the numerical vote itself. Ah, you're assuming a direct Patricia tree. Keep in mind that scriptPubKey's can be up to 10,000 bytes long, and an attacker can use that (with 10,000 other txouts) to create some extremely deep trees. I said on IRC a few days ago about how skeptical I am of implementing consensus critical systems with such huge differences in average and worst case, but I'll admit this is a decent use-case. Having said that, proof to SPV clients leaves open the interesting possibility that a third-party holding Bitcoins on your behalf can prove that they voted according to your wishes, or even prove they voted according to all their users wishes. Basically we'd add a rule for the UTXO tree where a specific OP_RETURN form is included in the UTXO tree, even though it is unspendable, and is removed from the tree if the master txout is spent. Note that in this case by "prove they voted" we mean the service actually taking the step of ensuring their vote was recorded in the blockchain. > The vote must compute > the median, rather than the mean, so as to not allow someone to skew the vote > by simply setting their value extremely high. Someone who still remembers > their > statistics classes should chime in on the right way to compute a median in a > merkle-sum-tree. I think the definition of the median requires knowledge of all the points so it'll have to be a separate sorted tree - kinda complex unfortunately if you really do want to be able to do full proof to SPV clients. Maybe just putting the hash of the overall results in the coinbase is enough for now. The term to google is "moving median" - looks complex. > Of course in the future the voting mechanism can be used for additional votes > with an additional vote_id. For instance the Bitcoin community could vote to > increase the inflation subsidy, another example of a situation where the > wishes > of miners may conflict with the wishes of the broader community. Good idea on keeping the code general. > For any given block actual limit in effect is then the rolling median of the > blocks in the last year. At the beginning of every year the value considered > to > be the status quo resets to the mean of the limit at the beginning and end of > the interval. (again, by "year" we really mean 52,560 blocks) The
Re: [Bitcoin-development] Proposal: Vote on the blocksize limit with proof-of-stake voting
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 On Mon, Jun 10, 2013 at 4:44 AM, Edmund Broadley wrote: > I really like this idea. I also like that users with no clue will leave > their vote to the default chosen by the software developers, which hopefully > will be 1MB. I like how coin age is factored in do votes are hopefully > proportional to bitcoin assert ownership. The default should *not* be set by wallets at all in fact. The default is that by not voting, you accept the status quo, which is defined as the mean of the old and new limits in the past year. So lets say the limit is 1MB, and through voting it ends up at 2MB in one year. Until that time by not voting you are in effect voting for the limit to be 1MB, but after the next interval you not voting is equivalent to voting for a 1.5MB limit. A subtle issue is then txout age, and at that point a 1.5 year old txout should be like voting for the 1MB limit still, albeit weighted less. What you don't want is your lack of vote to suddenly turn into a 1.5MB vote. This makes sure that at all levels the increases are gradual rather than abrupt, although the rate of increase may still be quite fast if the community votes that way. (first derivative of the limit is a close approximation to a continuous function) -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJRtV0iAAoJEEWCsU4mNhiPRDIH+wapKxD0fc2div9gkhxZ4qVt 9Wh4u1vKM4RsxdPgh9uKFJomjErBXBROJ57cJqB1rwHt1xhUyHgbC8JstU0PWzUM Ygwgibe9nsSjqHp2w15Bat+NmkYpxrjmVhf9woZkPQl+A1bWd3MFXOGoTIPPCl3I KkMTaR3VbZDwqg0DlteZMR2im2DkT4zDsCkSb8KSCoaeTEdafkPceVHWU6isWxV9 Y0TGFCKaoMjxqxnkgH+vHsJlIM4E3rb0NHTo8rHD7Hm1txw/4/fVwE56/9U+8FaK XAPXS0gkIR83V7cWMLa/q6LpZyzJmfFXCZhjT4YxVqeq/wB/SR9j2hhNdLnjuCo= =y1c+ -END PGP SIGNATURE- -- How ServiceNow helps IT people transform IT departments: 1. A cloud service to automate IT design, transition and operations 2. Dashboards that offer high-level views of enterprise services 3. A single system of record for all IT processes http://p.sf.net/sfu/servicenow-d2d-j ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Proposal: Vote on the blocksize limit with proof-of-stake voting
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 It has been suggested that we leave the decision of what the blocksize to be entirely up to miners. However this leaves a parameter that affects every Bitcoin participant in the control of a small minority. Of course we can not force miners to increase the blocksize if they choose to decrease it, because the contents of the blocks they make are their decision and their decision only. However proposals to leave the maximum size unlimited to allow miners to force us to accept arbitrarily large blocks even if the will of the majority of Bitcoin participants is that they wish to remain able to validate the blockchain. What we need is a way to balance this asymetrical power relationship. Proof-of-stake voting gives us a way of achieving that balance. Essentially for a miner to prove that the majority will of the poeple is to accept a larger blocksize they must prove that the majority has in fact voted for that increase. The upper limit on the blocksize is then determined by the median of all votes, where each txout in the UTXO set is one vote, weighted by txout value. A txout without a corresponding vote is considered to be a vote for the status quo. To allow the voting process to continue even if coins are "lost" votes, including default votes, are weighted inversely according to their age in years after 1 year. IE a vote with weight 1BTC that is 1.5 years old will be recorded the same as a <1 year old vote weighted as 0.67BTC, and a 1 day old and 6 months old UTXO are treated equivalently. The 1 year minimum is simply to make voting required no more than once per year. (of course, a real implementation should do all of these figures by block height, IE after 52,560 blocks instead of after 1 year) A vote will consist of a txout with a scriptPubKey of the following form: OP_RETURN magic vote_id txid vout vote scriptSig Where scriptSig is a valid signature for a transaction with nLockTime 500,000,000-1 spending txid:vout to scriptPubKey: OP_HASH160 H(OP_RETURN magic vote_id txid vout vote) OP_EQUAL vote_id is the ID of the specific vote being made, and magic is included to allow UTXO proof implementations a as yet unspecified way of identifying votes and including the weighted median as part of the UTXO tree sums. (it also allows SPV clients to verify the vote if the UTXO set is a Patricia tree of scriptPubKeys) vote is just the numerical vote itself. The vote must compute the median, rather than the mean, so as to not allow someone to skew the vote by simply setting their value extremely high. Someone who still remembers their statistics classes should chime in on the right way to compute a median in a merkle-sum-tree. The slightly unusual construction of votes makes implementation by wallet software as simple as possible within existing code-paths. Votes could still be constructed even in wallets lacking specific voting capability provided the wallet software does have the ability to set nLockTime. Of course in the future the voting mechanism can be used for additional votes with an additional vote_id. For instance the Bitcoin community could vote to increase the inflation subsidy, another example of a situation where the wishes of miners may conflict with the wishes of the broader community. Users may of course actually create these specially encoded txouts themselves and get them into the blockchain. However doing so is not needed as a given vote is only required to actually be in the chain by a miner wishing to increase the blocksize. Thus we should extend the P2P protocol with a mechanism by which votes can be broadcast independently of transactions. To prevent DoS attacks only votes with known vote_id's will be accepted, and only for txid:vout's already in the blockchain, and a record of txouts for whom votes have already broadcast will be kept. (this record need not be authoritative as its purpose is only to prevent DoS attacks) Miners wishing to increase the blocksize can record these votes and include them in the blocks they mine as required. To reduce the cost of including votes in blocks 5% of every block should be assigned to voting only. (this can be implemented by a soft-fork) For any given block actual limit in effect is then the rolling median of the blocks in the last year. At the beginning of every year the value considered to be the status quo resets to the mean of the limit at the beginning and end of the interval. (again, by "year" we really mean 52,560 blocks) The rolling median and periodic reset process ensures that the limit changes gradually and is not influenced by temporary events such as hacks to large exchanges or malicious wallet software. The rolling median also ensures that for a miner the act of including a vote is never wasted due to the txout later being spent. Implementing the voting system can happen prior to an actual hard-fork allowing for an increase and can be an important part of determining if the