Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Ulvge-0007My-DX for bitcoin-development@lists.sourceforge.net; Mon, 10 Jun 2013 06:34:40 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.223.171 as permitted sender) client-ip=209.85.223.171; envelope-from=lidstrom83@gmail.com; helo=mail-ie0-f171.google.com; Received: from mail-ie0-f171.google.com ([209.85.223.171]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1Ulvgc-0002li-OZ for bitcoin-development@lists.sourceforge.net; Mon, 10 Jun 2013 06:34:40 +0000 Received: by mail-ie0-f171.google.com with SMTP id qd12so1126758ieb.16 for ; Sun, 09 Jun 2013 23:34:33 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.50.141.234 with SMTP id rr10mr3464702igb.34.1370846073355; Sun, 09 Jun 2013 23:34:33 -0700 (PDT) Received: by 10.64.100.200 with HTTP; Sun, 9 Jun 2013 23:34:33 -0700 (PDT) In-Reply-To: <20130610053002.GA8961@savin> References: <20130610053002.GA8961@savin> Date: Mon, 10 Jun 2013 03:34:33 -0300 Message-ID: From: Daniel Lidstrom To: Peter Todd Content-Type: multipart/alternative; boundary=089e0122a4783e829404dec6f9bf X-Spam-Score: -0.3 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (lidstrom83[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit (lidstrom83[at]gmail.com) 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1Ulvgc-0002li-OZ Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Proposal: Vote on the blocksize limit with proof-of-stake voting X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 10 Jun 2013 06:34:40 -0000 --089e0122a4783e829404dec6f9bf Content-Type: text/plain; charset=ISO-8859-1 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 +0000, 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 > 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. > > Good points, although keep in mind you've created a lot of consensus > critical code that is easiest to implement with floating point... not a > good thing. > > One way to mitigate that risk might be to take advantage of the fact > that unless the rolling median code itself is buggy, a consensus failure > in the calculation is likely to result in different implementations > still having a close agreement on the limit. So maybe we write some code > where we won't build on top of a block that is larger than, say, 95% of > the hard-limit unless another miner does so too? > > > 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 > hard-fork is > > required at all. > > Step #0 would be to think about OP_RETURN actually. FWIW Jeff Garzik has > a pull-req (https://github.com/bitcoin/bitcoin/pull/2738) to enable it, > although only one txout per tx, and only with a 80-byte payload. > > Even just some ad-hoc voting by the "raise-the-limit" crowd would be a > good first step to gaging interest. > > > Coercion and vote buying is of course possible in this system. A miner > could > > say that they will only accept transactions accompanied by a vote for a > given > > limit. However in a decentralized system completely preventing vote > buying is > > of course impossble, and the design of Bitcoin itself has a fundemental > > Is it really? There might be someone clever with a cryptographic voting > protocol, although in the case of Bitcoin we have to let people vote > with arbitrary scriptPubKeys, so almost anything less general than full > on SCIP just means miners force people to use the protocol where > vote-buying is possible. > > > A voting process ensures that any increase to the blocksize genuinely > > represents the desires of the Bitcoin community, and the process > described > > above ensures that any changes happen at a rate that gives all > participants > > time to react. The process also gives a mechanism for the community to > vote to > > decrease the limit if it turns out that the new one was in fact too > high. (note > > how the way the status quo is set ensures the default action is for the > limit > > to gradually decrease even if everyone stops voting) > > Good idea. So it'd decrease to the mean of the old and new limits > basically, and if Bitcoin becomes "too centralized" users can simply do > nothing and the process gradually reverses. > > > As many of you know I have been quite vocal that the 1MB limit should > stay. But > > I would be happy to support the outcome of a vote done properly, > whatever that > > outcome may be. > > Same here. > > -- > 'peter'[:-1]@petertodd.org > 0000000000000068a8ad033afa763246fe451e840eae5215eb3a64e8101a46c3 > > > ------------------------------------------------------------------------------ > 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 > > --089e0122a4783e829404dec6f9bf Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Reserving my judgement until I've though about it= more (design by=20 committee scares me, and this voting sounds expensive), I think the=20 SPV-verifiable moving median can be done by binning the space of block=20 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=20 children.=A0 The childless nodes - which correspond to the individual=20 UTXOs - increment the appropriate bin of their parents according to the=20 rules you mentioned.=A0 The bin values in the root node of the UTXO tree=20 would then be added to those, weighted appropriately, of the previous N=20 blocks.

The hash of a node would be that of the bin values,=20 concatenated with the child nodes' hashes.=A0 In this way, any step of = the calculation of the median would produce a localized error in the UTXO=20 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=20 branches though.


On Mon, Jun 10, 2013 at 2:30 AM, Peter Todd <= pete@petertodd.org<= /a>> wrote:
On Mon, Jun 10, 2013 at 04:09:26AM +0000, Jo= hn 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 closes= t
thing we'll ever get to a fair vote. Proof-of-stake is certainely bette= r
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 =3D 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 fo= rm:
>
> =A0 =A0 OP_RETURN magic vote_id txid vout vote scriptSig
>
> Where scriptSig is a valid signature for a transaction with nLockTime<= br> > 500,000,000-1 spending txid:vout to scriptPubKey:
>
> =A0 =A0 OP_HASH160 H(OP_RETURN magic vote_id txid vout vote) OP_EQUAL<= br>
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 includ= ed to
> allow UTXO proof implementations a as yet unspecified way of identifyi= ng votes
> and including the weighted median as part of the UTXO tree sums. (it a= lso
> allows SPV clients to verify the vote if the UTXO set is a Patricia tr= ee 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<= br> 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<= br> 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&quo= t; 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 t= he vote
> by simply setting their value extremely high. Someone who still rememb= ers their
> statistics classes should chime in on the right way to compute a media= n in a
> merkle-sum-tree.

I think the definition of the median requires knowledge of all the po= ints so
it'll have to be a separate sorted tree - kinda complex unfortunately i= f
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 additiona= l votes
> with an additional vote_id. For instance the Bitcoin community could v= ote to
> increase the inflation subsidy, another example of a situation where t= he 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 cons= idered to
> be the status quo resets to the mean of the limit at the beginning and= end of
> the interval. =A0(again, by "year" we really mean 52,560 blo= cks) The rolling
> median and periodic reset process ensures that the limit changes gradu= ally and
> is not influenced by temporary events such as hacks to large exchanges= or
> malicious wallet software. =A0The rolling median also ensures that for= a miner
> the act of including a vote is never wasted due to the txout later bei= ng spent.

Good points, although keep in mind you've created a lot of consen= sus
critical code that is easiest to implement with floating point... not a
good thing.

One way to mitigate that risk might be to take advantage of the fact
that unless the rolling median code itself is buggy, a consensus failure in the calculation is likely to result in different implementations
still having a close agreement on the limit. So maybe we write some code where we won't build on top of a block that is larger than, say, 95% of=
the hard-limit unless another miner does so too?

> 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 har= d-fork is
> required at all.

Step #0 would be to think about OP_RETURN actually. FWIW Jeff Garzik = has
a pull-req (https://github.com/bitcoin/bitcoin/pull/2738) to enable it,=
although only one txout per tx, and only with a 80-byte payload.

Even just some ad-hoc voting by the "raise-the-limit" crowd would= be a
good first step to gaging interest.

> Coercion and vote buying is of course possible in this system. A miner= could
> say that they will only accept transactions accompanied by a vote for = a given
> limit. However in a decentralized system completely preventing vote bu= ying is
> of course impossble, and the design of Bitcoin itself has a fundementa= l

Is it really? There might be someone clever with a cryptographic voti= ng
protocol, although in the case of Bitcoin we have to let people vote
with arbitrary scriptPubKeys, so almost anything less general than full
on SCIP just means miners force people to use the protocol where
vote-buying is possible.

> A voting process ensures that any increase to the blocksize genuinely<= br> > represents the desires of the Bitcoin community, and the process descr= ibed
> above ensures that any changes happen at a rate that gives all partici= pants
> time to react. The process also gives a mechanism for the community to= vote to
> decrease the limit if it turns out that the new one was in fact too hi= gh. (note
> how the way the status quo is set ensures the default action is for th= e limit
> to gradually decrease even if everyone stops voting)

Good idea. So it'd decrease to the mean of the old and new limits=
basically, and if Bitcoin becomes "too centralized" users can sim= ply do
nothing and the process gradually reverses.

> As many of you know I have been quite vocal that the 1MB limit should = stay. But
> I would be happy to support the outcome of a vote done properly, whate= ver that
> outcome may be.

Same here.

--
'peter'[:-1]@pet= ertodd.org
0000000000000068a8ad033afa763246fe451e840eae5215eb3a64e8101a46c3

---------------------------------------------------------= ---------------------
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-develo= pment@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment


--089e0122a4783e829404dec6f9bf--