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; 
Date: Fri, 15 Nov 2013 04:54:13 -0500
From: Peter Todd <pete@petertodd.org>
To: John Dillon <john.dillon892@googlemail.com>
Message-ID: <20131115095413.GA17034@savin>
References: <528367F5.9080303@ceptacle.com>
	<CAPaL=UWZXSwY9dzX30h_ksj2NAdkyLn3Xtfzs7P8Svg5tsE7Xw@mail.gmail.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: <CAPaL=UWZXSwY9dzX30h_ksj2NAdkyLn3Xtfzs7P8Svg5tsE7Xw@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>,
	Michael Gronager <gronager@ceptacle.com>
Subject: Re: [Bitcoin-development] Even simpler minimum fee calculation
 formula: f > bounty*fork_rate/average_blocksize
Precedence: list


--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--