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 1VeL21-0007BV-Tc for Bitcoin-development@lists.sourceforge.net; Thu, 07 Nov 2013 08:33:38 +0000 X-ACL-Warn: Received: from mail-vb0-f45.google.com ([209.85.212.45]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1VeL1z-000688-IZ for Bitcoin-development@lists.sourceforge.net; Thu, 07 Nov 2013 08:33:37 +0000 Received: by mail-vb0-f45.google.com with SMTP id p6so132078vbe.18 for ; Thu, 07 Nov 2013 00:33:29 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=9PlGuXrhDqVtNcFmKB//F6LEeAEqaDJ94cMm1sqpZAs=; b=JijrXOwSS5zI8G0Vh48w8rLL2/7lgR8mtC2rLSLKNXI0h0qdBPfbjB/Bfe+uLgNYlF Orr5PcEwTLJGyp1jiHxs1l/34LM0P47Tt0EA+fsdXW93U2/ulJurZT+dQpJ16YgeMapP mrBgxRAsjsO7vUkBNBJtZRjXfSc0uSQubcswqNau19RFYPZ0cW4/VX0xRsHBHoZJ+zdA P/OCk1KnHMaA/giU+z7vNg4fO3lrZP2BURuTQl7iLwH62UGS2z/ICckrNbqUxpgLuKLP 7O2pkFQrt5CLf+eaACdNz3Ho/QBZFcAUEhrBLp5ISiBDijIs4g7XmsFSURVTXwWh6fQ4 x0AQ== X-Gm-Message-State: ALoCoQleriaoQ9DGfDhQGj0z5cjKR7XYJB1EiZvwfeRSIZzk935fFn4TU9Ec/wuIsJXsqSA9/ZuC X-Received: by 10.220.183.199 with SMTP id ch7mr5688372vcb.27.1383811696871; Thu, 07 Nov 2013 00:08:16 -0800 (PST) MIME-Version: 1.0 Received: by 10.220.220.139 with HTTP; Thu, 7 Nov 2013 00:07:56 -0800 (PST) In-Reply-To: <20131107034404.GA5140@savin> References: <5279D49D.5050807@jerviss.org> <20131107034404.GA5140@savin> From: Jannes Faber Date: Thu, 7 Nov 2013 09:07:56 +0100 Message-ID: To: Peter Todd Content-Type: multipart/alternative; boundary=001a11c1bce0a0e62e04ea91c4ae X-Spam-Score: 1.1 (+) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. 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: doubleclick.net] 1.0 HTML_MESSAGE BODY: HTML included in message 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid 0.0 T_DKIM_INVALID DKIM-Signature header exists but is not valid X-Headers-End: 1VeL1z-000688-IZ Cc: Bitcoin-development@lists.sourceforge.net Subject: Re: [Bitcoin-development] we can all relax now 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: Thu, 07 Nov 2013 08:33:38 -0000 --001a11c1bce0a0e62e04ea91c4ae Content-Type: text/plain; charset=ISO-8859-1 I wonder if you need to take into consideration the fact that there might be another "bad" pool (in the 1-Q part of the network) running the same strategy and also holding on to two blocks of their own? Once they find their third block before you do, then your 2 blocks lead is gone instantly. -- Jannes Faber Elevate BV t: +31 20 636 9977 m: +31 6 5342 9669 j.faber@elevate.nl On 7 November 2013 04:44, Peter Todd wrote: > On Wed, Nov 06, 2013 at 01:06:47PM -0500, Christophe Biocca wrote: > > I might try building this sometime soon. I think it may also serve an > > educational purpose when trying to understand the whole network's > behaviour. > > > > What level of accuracy are we looking for though? Obviously we need to > > fully emulate the steps of the network protocol, and we need to be able > to > > specify time taken for transmission/processing for each node. Do we care > > about the actual contents of the messages (to be able to simulate double > > spend attempts, invalid transactions and blocks, SPV node communication), > > and their validation (actual signatures and proof of work)? > > > > I imagine the latter is pretty useless, beyond specifying that the > > signature/proof of work is valid/invalid. > > > > If we could build up a set of experiments we'd like to run on it, it > would > > help clarify what's needed. > > > > Off the top of my head: > > > > - Peter Todd's miner strategy of sending blocks to only 51% of the > > hashpower. > > Speaking of, I hadn't gotten around to doing up the math behind that > strategy properly; turns out 51% I was overly optimistic and the actual > threshold is 29.3% > > Suppose I find a block. I have Q hashing power, and the rest of the > network 1-Q. Should I tell the rest of the network, or withhold that > block and hope I find a second one? > > Now in a purely inflation subsidy environment, where I don't care about > the other miners success, of course I should publish. However, if my > goals are to find *more* blocks than the other miners for whatever > reason, maybe because transaction fees matter or I'm trying to get > nLockTime'd announce/commit fee sacrifices, it gets more complicated. > > > There are three possible outcomes: > > 1) I find the next block, probability Q > 2) They find the next block, probability 1-Q > 2.1) I find the next block, probability Q, or (1-Q)*Q in total. > 2.2) They find the next block, probability (1-Q)^2 in total. > > Note how only in the last option do I lose. So how much hashing power do > I need before it is just as likely that the other miners will find two > blocks before I find either one block, or two blocks? Easy enough: > > Q + (1-Q)*Q = (1-Q)^2 -> Q^2 - Q + 1/2 -> Q = (1 - \sqrt(2))/2 > > Q ~= 29.2% > > So basically, if I'm trying to beat other miners, once I have >29.3% of > the hashing power I have no incentive to publish the blocks I mine! > > But hang on, does it matter if I'm the one who actually has that hashing > power? What if I just make sure that only >29.3% of the hashing power > has that block? If my goal is to make sure that someone does useless > work, and/or they are working on a lower height block than me, then no, > I don't care, which means my original "send blocks to >51% of the > hashing power" analysis was actually wrong, and the strategy is even > more crazy: "send blocks to >29.3% of the hashing power" (!) > > > Lets suppose I know that I'm two blocks ahead: > > 1) I find the next block: Q (3:0) > 2) They find the next block: (1-Q) (2:1) > 2.1) I find the next block: (1-Q)*Q (3:1) > 2.2) They find the next block: (1-Q)^2 (2:2) > 2.2.1) I find the next block: (1-Q)^2 * Q (3:2) > 2.2.2) They find the next block: (1-Q)^3 (2:3) > > At what hashing power should I release my blocks? So remember, I win > this round on outcomes 1, 2.1, 2.2.1 and they only win on 2.2.2: > > Q + (1-Q)*Q + (1-Q)^2*Q = (1-Q)^3 -> Q = 1 - 2^-3 > > Q ~= 20.6% > > Interesting... so as I get further ahead, or to be exact the group of > miners who have a given block gets further ahead, I need less hashing > power for my incentives to be to *not* publish the block I just found. > Conversely this means I should try to make my blocks propagate to less > of the hashing power, by whatever means necessary. > > Now remember, none of the above strategy requires me to have a special > low-latency network or anything fancy. I don't even have to have a lot > of hashing power - the strategy still works if I'm, say, a 5% pool. It > just means I don't have the incentives people thought I did to propagate > my blocks widely. > > The other nasty thing about this, is suppose I'm a miner and recently > got a block from another miner: should I forward that block, or not > bother? Well, it depends: if I have no idea how much of the hashing > power has that block, I should forward the block. But again, if my goal > is to be most likely to get the next block, I should only forward in > such a way that >30% of the hashing power has the block. > > This means that if I have some information about what % already has that > block, I have less incentive to forward! For instance, suppose that > every major miner has been publishing their node addresses in their > blocks - I'll have a pretty good idea of who probably has that most > recent block, so I can easily make a well-optimized decision not to > forward. Similarly because the 30% hashing power figure is the > *integral* of time * hashes/second, if miners are forwarding > near-target-headers, I might as well wait a few seconds and see if I see > any near-target-headers; if I do for this block then I have evidence > that hashing power does have it, and I shouldn't forward. > > > So yeah, we're fucked and have got to fix this awful incentive structure > somehow before the inflation subsidy gets any smaller. Also, raising the > blocksize, especially by just removing the limit, is utter madness given > it can be used to slow down block propagation selectively, so the > hashing power that gets a given block is limited repeatably to the same > group. > > > P.S: If any large pools want to try this stuff out, give me a shout. You > have my PGP key - confidentiality assured. > > P.P.S: If you're mining on a pool with more than, like, 1% hashing > power, do the math on varience... Seriously, stop it and go mine on a > smaller pool, or better yet, p2pool. > > -- > 'peter'[:-1]@petertodd.org > 00000000000000078b970f5134bae96da021744f80e04aa9dc2e2d2c2bcb07c2 > > > ------------------------------------------------------------------------------ > November Webinars for C, C++, Fortran Developers > Accelerate application performance with scalable programming models. > Explore > techniques for threading, error checking, porting, and tuning. Get the most > from the latest Intel processors and coprocessors. See abstracts and > register > http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > --001a11c1bce0a0e62e04ea91c4ae Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
I wonder if you need to take into consideration the f= act that there might be another "bad" pool (in the 1-Q part of th= e network) running the same strategy and also holding on to two blocks of t= heir own? Once they find their third block before you do, then your 2 block= s lead is gone instantly.


--
Jannes Faber
Elevate BV

t: = +31 20 636 9977
m: +31 6 5342 9669
j.fab= er@elevate.nl


On 7 November 2013 04:44, Peter Todd <= pete@petertodd.org> wrote:
On Wed, Nov 06, 2013 at 01:06:47PM -0500, Christophe Bioc= ca wrote:
> I might try building this sometime soon. I think it may also serve an<= br> > educational purpose when trying to understand the whole network's = behaviour.
>
> What level of accuracy are we looking for though? Obviously we need to=
> fully emulate the steps of the network protocol, and we need to be abl= e to
> specify time taken for transmission/processing for each node. Do we ca= re
> about the actual contents of the messages (to be able to simulate doub= le
> spend attempts, invalid transactions and blocks, SPV node communicatio= n),
> and their validation (actual signatures and proof of work)?
>
> I imagine the latter is pretty useless, beyond specifying that the
> signature/proof of work is valid/invalid.
>
> If we could build up a set of experiments we'd like to run on it, = it would
> help clarify what's needed.
>
> Off the top of my head:
>
> - Peter Todd's miner strategy of sending blocks to only 51% of the=
> hashpower.

Speaking of, I hadn't gotten around to doing up the math behind t= hat
strategy properly; turns out 51% I was overly optimistic and the actual
threshold is 29.3%

Suppose I find a block. I have Q hashing power, and the rest of the
network 1-Q. Should I tell the rest of the network, or withhold that
block and hope I find a second one?

Now in a purely inflation subsidy environment, where I don't care about=
the other miners success, of course I should publish. However, if my
goals are to find *more* blocks than the other miners for whatever
reason, maybe because transaction fees matter or I'm trying to get
nLockTime'd announce/commit fee sacrifices, it gets more complicated.

There are three possible outcomes:

1) I find the next block, probability Q
2) They find the next block, probability 1-Q
2.1) I find the next block, probability Q, or (1-Q)*Q in total.
2.2) They find the next block, probability (1-Q)^2 in total.

Note how only in the last option do I lose. So how much hashing power do I need before it is just as likely that the other miners will find two
blocks before I find either one block, or two blocks? Easy enough:

Q + (1-Q)*Q =3D (1-Q)^2 -> Q^2 - Q + 1/2 -> Q =3D (1 - \sqrt(2))/2
Q ~=3D 29.2%

So basically, if I'm trying to beat other miners, once I have >29.3%= of
the hashing power I have no incentive to publish the blocks I mine!

But hang on, does it matter if I'm the one who actually has that hashin= g
power? What if I just make sure that only >29.3% of the hashing power has that block? If my goal is to make sure that someone does useless
work, and/or they are working on a lower height block than me, then no,
I don't care, which means my original "send blocks to >51% of t= he
hashing power" analysis was actually wrong, and the strategy is even more crazy: "send blocks to >29.3% of the hashing power" (!)

Lets suppose I know that I'm two blocks ahead:

1) I find the next block: Q =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(3:0) 2) They find the next block: (1-Q) =A0 =A0 =A0 =A0 =A0 =A0 (2:1)
2.1) I find the next block: (1-Q)*Q =A0 =A0 =A0 =A0 =A0 =A0(3:1)
2.2) They find the next block: (1-Q)^2 =A0 =A0 =A0 =A0 (2:2)
2.2.1) I find the next block: (1-Q)^2 * Q =A0 =A0 =A0(3:2)
2.2.2) They find the next block: (1-Q)^3 =A0 =A0 =A0 (2:3)

At what hashing power should I release my blocks? So remember, I win
this round on outcomes 1, 2.1, 2.2.1 and they only win on 2.2.2:

Q + (1-Q)*Q + (1-Q)^2*Q =3D (1-Q)^3 -> Q =3D 1 - 2^-3

Q ~=3D 20.6%

Interesting... so as I get further ahead, or to be exact the group of
miners who have a given block gets further ahead, I need less hashing
power for my incentives to be to *not* publish the block I just found.
Conversely this means I should try to make my blocks propagate to less
of the hashing power, by whatever means necessary.

Now remember, none of the above strategy requires me to have a special
low-latency network or anything fancy. I don't even have to have a lot<= br> of hashing power - the strategy still works if I'm, say, a 5% pool. It<= br> just means I don't have the incentives people thought I did to propagat= e
my blocks widely.

The other nasty thing about this, is suppose I'm a miner and recently got a block from another miner: should I forward that block, or not
bother? Well, it depends: if I have no idea how much of the hashing
power has that block, I should forward the block. But again, if my goal
is to be most likely to get the next block, I should only forward in
such a way that >30% of the hashing power has the block.

This means that if I have some information about what % already has that block, I have less incentive to forward! For instance, suppose that
every major miner has been publishing their node addresses in their
blocks - I'll have a pretty good idea of who probably has that most
recent block, so I can easily make a well-optimized decision not to
forward. Similarly because the 30% hashing power figure is the
*integral* of time * hashes/second, if miners are forwarding
near-target-headers, I might as well wait a few seconds and see if I see any near-target-headers; if I do for this block then I have evidence
that hashing power does have it, and I shouldn't forward.


So yeah, we're fucked and have got to fix this awful incentive structur= e
somehow before the inflation subsidy gets any smaller. Also, raising the blocksize, especially by just removing the limit, is utter madness given it can be used to slow down block propagation selectively, so the
hashing power that gets a given block is limited repeatably to the same
group.


P.S: If any large pools want to try this stuff out, give me a shout. You have my PGP key - confidentiality assured.

P.P.S: If you're mining on a pool with more than, like, 1% hashing
power, do the math on varience... Seriously, stop it and go mine on a
smaller pool, or better yet, p2pool.

--
'peter'[:-1]@pet= ertodd.org
00000000000000078b970f5134bae96da021744f80e04aa9dc2e2d2c2bcb07c2

---------------------------------------------------------= ---------------------
November Webinars for C, C++, Fortran Developers
Accelerate application performance with scalable programming models. Explor= e
techniques for threading, error checking, porting, and tuning. Get the most=
from the latest Intel processors and coprocessors. See abstracts and regist= er
http://pubads.g.doubleclick.net/gam= pad/clk?id=3D60136231&iu=3D/4140/ostg.clktrk
___________________= ____________________________
Bitcoin-development mailing list
Bitcoin-develo= pment@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment


--001a11c1bce0a0e62e04ea91c4ae--