From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1VhG6r-0004lT-GK for bitcoin-development@lists.sourceforge.net; Fri, 15 Nov 2013 09:54:41 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.55 as permitted sender) client-ip=62.13.149.55; envelope-from=pete@petertodd.org; helo=outmail149055.authsmtp.co.uk; Received: from outmail149055.authsmtp.co.uk ([62.13.149.55]) by sog-mx-2.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1VhG6p-0003FJ-H5 for bitcoin-development@lists.sourceforge.net; Fri, 15 Nov 2013 09:54:41 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt9.authsmtp.com (8.14.2/8.14.2) with ESMTP id rAF9sIbk022949; Fri, 15 Nov 2013 09:54:18 GMT Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rAF9sDUh015774 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Fri, 15 Nov 2013 09:54:15 GMT Date: Fri, 15 Nov 2013 04:54:13 -0500 From: Peter Todd To: John Dillon Message-ID: <20131115095413.GA17034@savin> References: <528367F5.9080303@ceptacle.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="lrZ03NoBR/3+SXJZ" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: e3e2d567-4ddb-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aQdMdwcUFloCAgsB AmUbW11eVVl7WGU7 bAxPbAVDY01GQQRq WVdMSlVNFUsqcGoI RWp7ChlzcgJBfDB1 bUVjXD4OXxF4IUN7 RVNQQTlUeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4mADM6 DwsDGC0rEFdNQiQ1 Lhk7LxYSEUtZOUw2 OkYlUE4ZNBlwQgNZ BURQBCYLb1dJEWIh Ch5cQV9cHjpHQhBG CwElZRZWDyZbVSdv Dk9CQBIUCjFIOOAX X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) 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 SPF_PASS SPF: sender matches SPF record 0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [URIs: blockchain.info] X-Headers-End: 1VhG6p-0003FJ-H5 Cc: Bitcoin Dev , Michael Gronager Subject: Re: [Bitcoin-development] Even simpler minimum fee calculation formula: f > bounty*fork_rate/average_blocksize 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: Fri, 15 Nov 2013 09:54:41 -0000 --lrZ03NoBR/3+SXJZ Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Nov 13, 2013 at 08:01:27PM +0000, John Dillon wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA256 >=20 > > Last week I posted a writeup: "On the optimal block size and why > > transaction fees are 8 times too low (or transactions 8 times too big)". > > > > Peter Todd made some nice additions to it including different pool sizes > > into the numbers. >=20 > Peter claims on IRC that he is writing a paper of some kind on this topic= =2E I > suggest he submit it to that crypto-currency thing the foundation is > sponsoring. Given the Nov 24th deadline, I also suggest at least making p= art of > it public ASAP so some peer review can be done. It would be a shame for a > simple math error to cause embarassment later. Here's what I've got to date. The first two sections is just a relatively simple proof that mining is more profitable as centralization increases under any circumstance, even before any real-world factors are taken into account. (other than non-zero latency and bandwidth) Nice homework problem, and neat that you can easily get a solid proof, but academic because it doesn't say anything about the magnitude of the incentives. The latter part is the actual derivation with proper model of supply-and-demand for fees. Or will be: while you can of course solve the equations with mathematica or similar - getting a horrid mess - I'm still trying to see if I can simplify them sanely in a way that's step-by-step understandable. Taking me longer than I'd like; sobering to realize how rusty I am. That said if any you do just throw it at Mathematica, looks like you get a result where the slope of your expected block return is at least quadratic with increasing hashing power. (though I spent all of five minutes eyeballing that result) \documentclass{article} \usepackage{url} \usepackage{mathtools} \begin{document} \title{Expected Return} \author{Peter Todd} \date{FIXME} \maketitle \section{Expected return of a block} \label{sec:exp-return-of-a-block} Let $f(L)$, a continuous function,\footnote{Transactions do of course give a discontinuous $f$. For a large $L$ the approximation error is negligible.} = be the fee-per-byte available to a rational miner for the last transaction included in a block of size $L$. $f(L)$ is a continuous function defined fo= r $L \ge 0$. Supply and demand dictates that: \begin{equation} f(L) \ge f(L+\epsilon) \label{eq:f-increases} \end{equation} A reasonable example for $f$ might be $f(L) =3D kL$, representing the deman= d side of a linear supply and demand plot. For a block of size $L$ that is optimal= ly filled with transactions the value of those fees is just the integral: \begin{equation} E_f(L) =3D \int_0^L f(l)\,dl \end{equation} Let $P(Q,L)$, a continuous function, be the probability that a block of size $L$ produced by a miner with relative hashing power $Q$ will be orphaned. Because a miner will never orphan their own blocks the following holds true: \begin{equation} P(Q,L) \le P(Q + \epsilon,L) \label{eq:p-increases} \end{equation} Similarly because larger blocks take longer to propagate and thus risk gett= ing orphaned by another miner finding a block at the same time: \begin{equation} P(Q,L) \ge P(Q,L + \epsilon) \end{equation} By combining $P(Q, L)$, $E_f(L)$ and the inflation subsidy $B$, gives us the expected return of a block for a given size and hashing power:\footnote{Note how real world marginal costs can be accommodated easily in the definitions= of $f$ and $B$.} \begin{equation} E(Q,L) =3D P(Q,L)[E_f(L) + B] \end{equation} The optimal size is simply the size $L$ at which $E(Q, L)$ no longer increa= ses: \begin{equation} \frac{d}{dL}\big[E(Q, L(Q))\big] =3D 0 \end{equation} We will define the function $L(Q)$ as the optimal value for a given $Q$. A miner creating optimal blocks will thus have an expected return per block f= ound of $E'(Q)=3DE(Q,L(Q))$. Note how this definition is per unit hashing power = by virtue of being per block found. \section{Optimal return $E'$ vs. hashing power $Q$} We want to know if a large miner has a larger return for a given amount of hashing power. We do this by taking the derivative with respect to $Q$ of t= he expected return given optimal strategy: \begin{align*} \frac{d}{dQ}\big[E'(Q)\big] &=3D \frac{d}{dQ}\big[P(Q,L(Q))\big]\big[E_= f(L(Q)) + B\big] + P(Q,L(Q))\frac{d}{dQ}\big[E_f(L(Q))\big] \\ &=3D \frac{dL(Q)}{dQ}\Big[\frac{dP(Q,L(Q))}= {dQ}\big[E_f(L(Q)) + B\big] + P(Q,L)\frac{dE_f(L(Q))}{dQ}\Big] \end{align*} We know that $L(Q)$, $E_f$, $P$, and $B$ are all $\ge 0$. Thus for $dE'/dQ$= to be negative requires either $dL/dQ$ to be negative, or for $dL/dQ$ to be positive and one of $dP/dQ$ or $dE_f/dQ$ negative. Suppose $dP/dQ$ negative and $dL/dQ$ positive: \begin{align} \frac{dL(Q)}{dQ} > 0 &\implies L(Q + \epsilon) > L(Q) \notag \\ \frac{dP(L(Q))}{dQ} < 0 &\implies P(Q + \epsilon, L(Q + \epsilon)) < P(= Q, L(Q)) \label{eq:dl-pos-dp-neg} \end{align} But that contradicts our definition \eqref{eq:p-increases} of $P$ as contin= uous and increasing. Suppose instead that $dE_f/dQ$ is negative and $dL/dQ$ positive: \begin{align} \frac{dL(Q)}{dQ} > 0 &\implies L(Q) < L(Q + \epsilon) \notag \\ \frac{dE_f(L(Q))}{dL} < 0 &\implies E_f(L(Q)) > E_f(L(Q + \epsilon)) \n= otag \\ &\implies \int_0^{L(Q)} f(l)\,dl > \int_0^{L(= Q+\epsilon)} f(l)\,dl \notag \\ &\implies f(l) < 0 \label{eq:dl-pos-de-neg} \end{align} Again we have a contradiction with our definition \eqref{eq:f-increases} of $f$. Finally suppose $dL/dQ$ is negative: \begin{align} \frac{dL(Q)}{dQ} < 0 &\implies L(Q) > L(Q + \epsilon) \notag \\ &\implies P(Q + \epsilon, L(Q + \epsilon)) < P(Q, = L(Q)) \notag \\ &\implies \frac{dP(Q, L(Q))}{dQ} < 0 \notag \\ &\implies \frac{dL(Q)}{dQ}\frac{dP(Q, L(Q))}{dQ} >= 0 \label{eq:dl-neg-dp-neg} \\ &\implies E_f(L(Q + \epsilon)) < E_f(L(Q)) \implie= s \frac{dE_f(L(Q))}{dQ} < 0 \notag \\ &\implies \frac{dL(Q)}{dQ}\frac{dE_f(L(Q))}{dQ} > = 0 \label{eq:dl-neg-de-neg} \end{align} Even if $dL/dQ$ is negative \eqref{eq:dl-neg-dp-neg} and \eqref{eq:dl-neg-de-neg} show that $dE'/dQ > 0$. In conjunction with \eqref{eq:dl-pos-dp-neg} and \eqref{eq:dl-pos-de-neg} we prove that increas= ed hashing power always leads to increased return on investment per unit hashi= ng power. \subsection{Real-world implications to centralization} While the author has shown that they still remember first-year, is this res= ult relevant? The proof holds regardless of what any of the functions actually are, provi= ded that they meet the requirements set out in section \ref{sec:exp-return-of-a-block}. The requirements are met by any reasonable real-world scenario\footnote{Negative fees are not reasonable!}, and show an incentive for mining to centralize even in an ideal situation where all min= ers are on a level playing field and have no fixed costs. However the proof is abstract, and doesn't tell us anything about how strong that pressure is; it may be insignificant enough to be outweighed by effects such as social pressure. We need to investigate $dE'/dQ$ in detail. \section{Detailed derivation of of $P(Q,L)$} \subsection{Assumptions} The difficulty is assumed to be in a steady state condition and the percentage of hashing power for any given miner is fixed. Unconfirmed transactions are assumed to be known to all miners, giving everyone an equal opportunity of mining any given transaction. We assume that the graph of all Bitcoin miners is fully connected and that the bandwidth, $1/k$, and latency, $t_0$, is identical for all connections and unchanging. We assume that miners always attempt to build upon the first block they see on the longest chain known to them, and when they find a block, they always broadcast it to all other miners simultaneously. From that we see that the time taken for a block of size $L$ to propagate to $100\%$ of the hashing power is simply: \begin{equation} t(L) =3D t_0 + kL \end{equation} \subsection{Analysis} When miner $Q$ finds a block during the condition of full consensus the outcomes can be described by the following state tree. The numbers in brac= kets are the "scorecard" of blocks found by $Q$ and all other miners should a gi= ven state be reached: \begin{description} \item[1)] No other block is found prior to full propagation. (1:0) \item[2)] $Q$ finds another block prior to full propagation. (2:0) \begin{description} \item[2.1)] $Q$'s second block is not orphaned. (2:0) \item[2.2)] $Q$'s second block is orphaned. (2:3) \end{description} \item[3)] $(1-Q)$ finds another block prior to full propagation. (1:1) \begin{description} \item[3.1)] $(1-Q)$'s block is orphaned. (2:1) \item[3.2)] $(1-Q)$'s block is not orphaned. (1:2) \end{description} \end{description} Miner $Q$ wins if states $1$, $2.1$, or $3.1$ are reached. Though it is possible to derive an equation for $P$ that accurately models possible stat= es - the author did exactly that in a fit of madness - the resulting equation is unwieldly and offers no additional insight. We want to end up with a $dE'/dQ$ that captures second order effects. Since $L(Q)$ and thus $E'(Q)$ will depend on $Q$ our approximation of $P$ should = be such that $dP/dQ$ is at least linear. With $\lambda$ as the block interval the probabilities of reaching states $= 1$, $2$, and $3$ are as follows: \begin{align} p_1 &=3D 1 - \frac{t}{\lambda} \\ p_2 &=3D \frac{t}{\lambda} Q \\ p_3 &=3D \frac{t}{\lambda} (1-Q) \end{align} We could assume that states $2$ and $3$ both lead to the block being orphan= ed, thus giving us: \begin{equation} P(Q, L) =3D 1 - \frac{t}{\lambda} =3D 1 - \frac{t_o + kL}{\lambda} \end{equation} However this gives us a linear $E(Q, L)$, linear $L(Q)$, and thus only a quadratic $E'(Q)$. We need at least one more state in our model; state $2.1= $ is a good choice. Reaching state $2.2$ is exceptionally improbable - the miners $(1-Q)$ have to find three blocks in time $t$ - so ignoring state $2.2$ and thus using the probability for state $2$ instead has negligible impact on t= he model. Meanwhile state $3$ requires that state $3.1$ be used directly and w= ould result in a third-order terms in $P$ when treating state $3$ as an always l= oss is a conservative lower-bound. This gives us: \begin{align} P(Q, L) &=3D p_1 + p_2 =3D 1 - \frac{t}{\lambda} + \frac{t}{\lambda} Q = =3D 1 - (1-Q)\frac{t}{\lambda} \notag \\ &=3D 1 - (1-Q)\frac{t_o + kL}{\lambda} \end{align} \subsection{Detailed derivation of E'(Q)} Some preliminaries: \begin{align} \frac{dP(Q,L)}{dL} &=3D -(1-Q)\frac{k}{\lambda} \\ \notag\\ \frac{dE(Q,L)}{dL} &=3D \frac{dP(Q,L)}{dL}\big[E_f(L) + B\big] + P(Q,L)= \frac{dE_f(L)}{dL} \notag\\ &=3D \frac{dP(Q,L)}{dL}\big[E_f(L) + B\big] + P(Q,L)= \,f(L) \end{align} We're not going to get very far without a definition for $f$ so we'll use a simple linear demand model: \begin{align} f(L) &=3D a - bL \\ E_f(L) &=3D aL - \frac{1}{2}bL^2 \end{align} Now we set $dE/dL=3D0$ and solve for $L$. To simplify the problem we will c= onsider the no-subsidy, $B=3D0$ case: \begin{align} 0 &=3D \frac{dP(Q,L)}{dL}E_f(L) + P(Q,L)\,f(L) \\ &=3D -(1-Q)\frac{k}{\lambda}\big[aL - \frac{1}{2}bL^2] + \big[1 - (1-= Q)\frac{t_o + kL}{\lambda}\big](a - bL) \\ \end{align} \end{document} > > Luckily the fork frequency and the average block size are easily > > measurable. blockchain.info keeps historical graphs of number of > > orphaned blocks pr day >=20 > Are those stats accurate? Have any pool operators at least confirmed that= the > orphaned blocks that blockchain.info reports match their own records? >=20 > My gut feeling is to relay all orphaned blocks. We know that with a high > investment and sybil attack as blockchain.info has done you can have bett= er > awareness of orphaned blocks than someone without those resources. If hav= ing > that awareness is ever a profitable thing we have both created an incenti= ve to > sybil attack the network and we have linked profitability to high up-front > capital investments. >=20 > On those grounds alone I will argue that we should relay all orphans to e= ven > the playing field. If there is a circumstance where we do not want the at= tacker > to have that knowledge we have failed anyway, as blockchain.info's sybil = attack > on the network clearly shows. Agreed. --=20 'peter'[:-1]@petertodd.org 0000000000000004fe7b45f3bbc4c7edbd9ff86c963fe77282453e1b38f66503 --lrZ03NoBR/3+SXJZ Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQGrBAEBCACVBQJShe9EXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDY1ODQ1OWNkNjRlNjMyNDNlNzE5MTA2MDE0MjU3ODcwZDA3 MzIwN2MyZDU0NjAxMzcvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfvQywf/dU2yK1Wupzm4PTm0KVOEtFpb W0sCpS6HBoyg8iDVobxiZtLixAdHRc0eDEdkqt5wKzhKppX9ReQP0aytG9IvCVZv d62y78C8CtOy2Sn5ykLWvy6wQRnwIyrCPPoar9+GXgNPmvaptVqSmpn081KcdSk8 ujgYzrtKi9qfwnz62FOdkm8MqQdPUUp0ilOORze5X0/ZLNqjtsnIePFnGCoflK+V wljC28rpYZ+XMRMWNLO6hSDWgNYu5Mc+2v/YITo6202lzPEfLSTvdRN4zswNMAEY AgU9jdEMwG1jG3mhh6BFEVjlbzfCuyi0FFpPQZVu0+5HZX7RtATwQeAi62idzQ== =wulC -----END PGP SIGNATURE----- --lrZ03NoBR/3+SXJZ--