Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 12:26:30PM +0100, Mike Hearn wrote:
 W.R.T. this paper and the oft-discussed miner backbone,
 
   http://arxiv.org/pdf/1311.0243v1.pdf
 
 I'm wondering about an alternative protocol change that perhaps has less
 subtle implications than their suggested change. Rather than address the
 problem by assuming the network is full of sybil nodes and changing the
 rules for selecting the chain to build on, how about if we wrote code to
 automatically build a miner backbone by having IP addresses of nodes
 embedded into coinbases, then having any bitcoind that is creating work
 automatically connect to IPs that appeared in enough recent blocks?

I proposed this as a means of giving a mechanism for wallets to get
non-sybilled peers as well.

 This would have the effect of automatically linking all the major pools
 together, with no administration overhead.
 
 For bonus points, the IPs could be IPv6 and then the trick we use to pack
 hidden services into IPv6 address space would allow nodes to be reached via
 Tor. This might be useful in the case of pools that don't to reveal the
 location of their bitcoin node[s], like for anti-DoS reasons.
 
 It feels like this should be achievable with a few days of solid coding and
 a couple of new command line flags, and the impact is much easier to reason
 about than a fundamental rule change like the one proposed by the paper.

Doing so encourages pools to only bother connecting to other pools,
which is a strong centralizing force. But given the nasty incentives
present anyway - it's in your advantage to distribute your blocks to no
more than a majority of hashing power if you can do so consistently -
I'm unconvinced that this won't happen anyway.

The maximal benefit would be if two sets of addresses were published:
public and private. The issue with publishing addresses is DoS attacks,
but publishing Tor addresses doesn't stop attacks. What would discourage
attacks however would be to encrypt that data such that only the
creators of specific prior blocks could decrypt it. This limits the
audience to those with incentives not to commit a DoS attack. (DoS
attack the IP, and you'll no longer get preferential peering)

Say what you want about centralization, but for the pools involved it's
a good idea.


On a technical level, the coinbase is limited in size, and people use it
for other purposes, so lets define a standard where this data is stored
in an OP_RETURN txout of the form:

OP_RETURN key value key value ...

Multiple values with the same key should be allowed. This data should be
placed in the last txout so that SPV nodes can eventually be given it
with a SHA256 midstate.

-- 
'peter'[:-1]@petertodd.org
00080e395c361bdf9db583d5f4c0e144f476c229285b15eae59c


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Mike Hearn
On Mon, Nov 4, 2013 at 12:53 PM, Peter Todd p...@petertodd.org wrote:

 I proposed this as a means of giving a mechanism for wallets to get
 non-sybilled peers as well.


Ah yes, good point.


 Doing so encourages pools to only bother connecting to other pools,
 which is a strong centralizing force.


They could already create such a setup, but we don't observe it in practice.


 On a technical level, the coinbase is limited in size, and people use it
 for other purposes, so lets define a standard 


Given that IP address data is inherently transient, perhaps a better
solution is to define a short hash in the coinbase that commits to extra
data that is relayed along with block data (e.g. appended to the block
message). It can then be stored temporarily in the block db and erased
after some time, like a few months. It would therefore not really be a part
of the chain, but could be extended as we see fit with any other
semi-transient data required. A new getextra message would let nodes
query for it.

The hash can be short because it doesn't have to survive brute forcing
attacks longer than the expected validity period of the transient data
anyway. 80 bits would probably be overkill.
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 01:03:50PM +0100, Mike Hearn wrote:
 
  The suggested change is actually very simple (minutes of coding) and
  elegant and addresses precisely the identified problem.
 
 
 Disagree. Unless I'm misunderstanding what they propose, their suggested
 change would mean anyone could broadcast a newly discovered block at any
 point and have a 50% chance of being the winner. That is a fundamental
 change to the dynamics of how Bitcoin works that would require careful
 thought and study.

It's worth pointing out that my previous post on this list for
near-block broadcasts - where blocks that almost but not quite met the
proof-of-work threshold are also broadcast so that propagation of
transactions can be proven - also naturally leads to their proposed
solution. Any miner who sees a near-block-broadcast extending a chain
fork that they aren't mining on would naturally see that as evidence
that the other side has more hashing power, and thus it's in their
interest to mine it rather than the side they are mining.


You know, the whole paper follows the same logic as the point I made
months ago in how if there is no explicit blocksize limit miners have
incentives to make their blocks large enough that they only propagate to
just over 50% of the hashing power, thus causing their competitors to
waste effort.  They analyze the situation in terms of a sybil attack,
where I proposed a more fundemental mechanism to achieve the same goal
based on simple physics.

-- 
'peter'[:-1]@petertodd.org
000719f061e0fa83343ddbe80d2b6a1fefc84691ffe8652385e0


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Michael Gronager
We propose a simple, backwards-compatible change to the Bitcoin
protocol to address this problem and raise the threshold. Specifically,
when a miner learns of competing branches of the same length, it should
propagate all of them, and choose which one to mine on uniformly at random.

So only in the case of two competing chains... The Selfish Miner today
has an advantage knowing which chain the other will work on, and by
simply choosing the other they get their advantage making it likely that
it is the other that will waste their effort. By using the random scheme
this advantage is gone.

Note again that it is only in the case of two competing chains, which
will happen on average every 60 blocks. So it is only roughly once every
60 block that you change from choosing one chain to doing a 50% random.

A rough calculation on earnings will be that you loose roughly 1/(2*60)
~ 1% of your blocks using this scheme. But at the same time you make it
harder for such an attack to happen. (This number might be slightly
higher, as working in parallel on both chains will make the two chains
last longer, so agree that we need a bit more analysis...)

I also agree that it is a kind of a Sybil attack, but I think we should
accept the risk of a Sybil attack but of course minimize it, rather than
introducing various social network (ip addresses) solutions, which in
one way or the other always have some central auth / oracle assumption.



On 4/11/13, 13:03 , Mike Hearn wrote:
 The suggested change is actually very simple (minutes of coding) and
 elegant and addresses precisely the identified problem.
 
 
 Disagree. Unless I'm misunderstanding what they propose, their suggested
 change would mean anyone could broadcast a newly discovered block at any
 point and have a 50% chance of being the winner. That is a fundamental
 change to the dynamics of how Bitcoin works that would require careful
 thought and study.
 
 Also, their solution doesn't really address the problem they bring up,
 it just changes the size of the threshold required. 
 
 Fundamentally, their attack is a sybil attack. It doesn't work if they
 can't delay or block a pools competitors because mostly their block will
 come in second place and they'll lose the race. Thus the solution should
 be a solution to sybil attacks.


--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 12:26:30PM +0100, Mike Hearn wrote:
 W.R.T. this paper and the oft-discussed miner backbone,
 
   http://arxiv.org/pdf/1311.0243v1.pdf
 
 I'm wondering about an alternative protocol change that perhaps has less
 subtle implications than their suggested change. Rather than address the
 problem by assuming the network is full of sybil nodes and changing the
 rules for selecting the chain to build on, how about if we wrote code to
 automatically build a miner backbone by having IP addresses of nodes
 embedded into coinbases, then having any bitcoind that is creating work
 automatically connect to IPs that appeared in enough recent blocks?
 
 It feels like this should be achievable with a few days of solid coding and
 a couple of new command line flags, and the impact is much easier to reason
 about than a fundamental rule change like the one proposed by the paper.

Actually on further reflection this idea will make the attack described
in the paper easier to carry out, rather than harder.

I think where you're misunderstanding originates is the description of
this attack as requiring a sybil attack on the network - you see this
underlying sybil as one of numerical advantage, when it's actually one
of *informational* advantage.

Remember that the selfish miner strategy outlined in the paper is
essentially a way to use knowledge of what blocks miners will be mining
on, from the first seen rule, and the ability to broadcast blocks you
have mined more widely than other miners. That knowledge and ability is
then used in conjunction with a small lead (obtainable by chance) to
outpace the rest of the network.

By making all miners easily identifiable you make gaining that
informational and broadcast capability easier to obtain rather than
harder. The attacker now only needs to connect to every identified miner
with especially fast nodes. With judicious use of DoS attacks and low
latency they can still gain the informational and broadcast upper hand
over other miners and carry out the attack.

Where the paper goes wrong is they don't recognize the fundemental
nature of the strategy being based on an informational advantage. Their
pick a random side of the fork strategy may work to some extent, but
it's incomplete and isn't necessarily rational for the miners
individually.

The correct, and rational, approach for a miner is to always mine to
extend the block that the majority of hashing power is trying to extend.
The current relay rules don't give you that information at all, but they
can if we do two things:

1) Relay all blocks that meet the PoW target. (as suggested in the
   paper)

2) Relay block headers that nearly meet the PoW target.

Mining strategy is now to mine to extend the first block you see, on the
assumption that the earlier one probably propagated to a large portion
of the total hashing power. But as you receive near-blocks that are
under the PoW target, use them to estimate the hashing power on each
fork, and if it looks like you are not on the majority side, switch.

This very effectively defeats the paper's selfish-miner strategy, as all
miners will very quickly be mining on the block that truly has the
majority of hashing power trying to extend it. This is also a better
overall outcome, because it puts the 51% attack threshhold back at 51%

-- 
'peter'[:-1]@petertodd.org
0004ee9bb13b022c412d75692b5e85454013c53f89e5d6fa8c69


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Pieter Wuille
On Mon, Nov 4, 2013 at 3:26 PM, Peter Todd p...@petertodd.org wrote:
 The correct, and rational, approach for a miner is to always mine to
 extend the block that the majority of hashing power is trying to extend.
 The current relay rules don't give you that information at all, but they
 can if we do two things:

 1) Relay all blocks that meet the PoW target. (as suggested in the
paper)

 2) Relay block headers that nearly meet the PoW target.

 Mining strategy is now to mine to extend the first block you see, on the
 assumption that the earlier one probably propagated to a large portion
 of the total hashing power. But as you receive near-blocks that are
 under the PoW target, use them to estimate the hashing power on each
 fork, and if it looks like you are not on the majority side, switch.

Doesn't that mean that by selective blocking these near-PoW headers,
you can bias peers into preferring to mine on those with near-PoW
headers, turning the attack around? Of course, because of their size,
headers are likely much harder to slow down (in propagation speed)
than full blocks...

-- 
Pieter

--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 03:34:35PM +0100, Pieter Wuille wrote:
  Mining strategy is now to mine to extend the first block you see, on the
  assumption that the earlier one probably propagated to a large portion
  of the total hashing power. But as you receive near-blocks that are
  under the PoW target, use them to estimate the hashing power on each
  fork, and if it looks like you are not on the majority side, switch.
 
 Doesn't that mean that by selective blocking these near-PoW headers,
 you can bias peers into preferring to mine on those with near-PoW
 headers, turning the attack around? Of course, because of their size,
 headers are likely much harder to slow down (in propagation speed)
 than full blocks...

Remember that the attack described in the paper *doesn't* depend on the
ability to selectively block or even just slow down anything - it works
even on a unlimited bandwidth jam-free network so long as latency is
non-zero.

As for other possible attacks, if you can selectively block or slow down
certain near-target headers you haven't achieved anything novel. Why not
use that ability to block or slow down blocks themselves? Even if you
did block some PoW headers for whatever reason the original purpose of
broadcasting them - getting all hashing power to work to extend the same
block - is still achieved.

-- 
'peter'[:-1]@petertodd.org
0001d7eb7fceb2e27f3dd1eb5f516464a6b6874fdf6debbd0227


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Mike Hearn
On Mon, Nov 4, 2013 at 3:26 PM, Peter Todd p...@petertodd.org wrote:

 The attacker now only needs to connect to every identified miner
 with especially fast nodes. With judicious use of DoS attacks and low
 latency .


So you're back to a complicated sybil attack. I don't follow your thought
process here - I didn't say anything about numerical advantage. The attack
outlined in the paper *requires* you to be able to race the rest of the
network and win some non-trivial fraction of the time. If you can't do that
then all it means is that when you try to release a private block to
compete with the other found block, you're quite likely to lose and you
sacrifice the block rewards by doing so.


 The correct, and rational, approach for a miner is to always mine to
 extend the block that the majority of hashing power is trying to extend.


There's no stable way to know that. The whole purpose of the block chain to
establish the majority. I think your near-miss headers solution is
circular/unstable for that reason, it's essentially a recursive solution.


 Mining strategy is now to mine to extend the first block you see, on the
 assumption that the earlier one probably propagated to a large portion
 of the total hashing power. But as you receive near-blocks that are
 under the PoW target, use them to estimate the hashing power on each
 fork, and if it looks like you are not on the majority side, switch.


But you can't reliably estimate that. You can't even reliably estimate the
speed of the overall network especially not on a short term basis like a
block interval.
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 10:25:19AM -0500, Ittay wrote:
 Peter - how can you guarantee that the majority mines on the non-selfish
 block?

Feedback basically. So suppose the hashing power is split exactly 50:50,
with half the hashing power hearing about one block first, and half the
other. Also suppose the near-target threshold is 1/64th, that is a block
header that means a target with difficulty 1/64th of the actual
difficulty will be broadcast around the network by nodes. With a 10
minute block interval, near-target block headers will be found on
average every 9.4 seconds.

Eventually one of the two halves will find a near-target PoW solution,
and the corresponding block-header will be broadcast on the network. Now
if you are a miner, and you receive such a PoW solution, that's evidence
that whatever block that block header built on has more hashing power
than other competing blocks. Thus you would be rational to switch, and
start mining to extend that block if you aren't already. Once miners
start doing that, very soon another near-block solution will be
generated, giving even more certainty about what block the majority are
mining on.

Of course, it may be the case that competing near-block headers are
found, but no matter: as long as miners switch to the block with the
most hashing power, this forms a feedback effect that quickly brings
everyone to consensus. With everyone mining to extend the same block,
there's nothing the selfish miner can do; there's no disagreement to
exploit.

-- 
'peter'[:-1]@petertodd.org
000771e068338fef7e2285b8a6db582e37473f42b76573677adf


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Gregory Maxwell
On Mon, Nov 4, 2013 at 3:58 AM, Michael Gronager grona...@ceptacle.com wrote:
 The suggested change is actually very simple (minutes of coding) and
 elegant and addresses precisely the identified problem. It is actually a
 mental shortcut in the assumption of how probability works when mining a
 chain. The paper simply corrects this error - nice work!

This isn't so.  Their solution creates a weaker form of the
vulnerability at all times, not just when the attacker has a
informational/positional advantage.

Normally delaying your blocks is negative expectation because you will
get orphaned by blocks that are announced before you most of the time
because miners extend the first seen. However, if you can position
yourself all over the network you can condition your announcements on
other blocks being announced and still win the race even if you
delayed.

Eliminating the first seen rule means that a miner with enough
hashpower (including the largest pools existing today) could execute
this attack without positioning themselves all over the network, the
improvement is that a low hashrate attacker couldn't do as well, even
with positioning themselves all over the network.  I don't think this
can be described as simply corrects the error.  The largest pool
would gain an advantage in delaying their blocks and would receive a
superliner share of mining income from doing so, something they can't
simply do today without attacking the network.

At the moment I believe we can improve the situation with propagation
advantage without the other changes, so we should do that first while
thinking carefully about this.

Simply relaying late blocks might be fine, if anything it would at
least make it easier to keep reliable orphan stats... though I'm
concerned with the bandwidth overhead and risk of flooding if its not
implemented carefully.

--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
(not sure if you meant this to go to the list, my apologies if not)

On Mon, Nov 04, 2013 at 10:50:25AM -0500, Ittay wrote:
 On Mon, Nov 4, 2013 at 10:46 AM, Peter Todd p...@petertodd.org wrote:
 
  On Mon, Nov 04, 2013 at 10:25:19AM -0500, Ittay wrote:
   Peter - how can you guarantee that the majority mines on the non-selfish
   block?
 
  Of course, it may be the case that competing near-block headers are
  found, but no matter: as long as miners switch to the block with the
  most hashing power, this forms a feedback effect that quickly brings
  everyone to consensus. With everyone mining to extend the same block,
  there's nothing the selfish miner can do; there's no disagreement to
  exploit.
 
 
 This is not the exploit! The majority you create might just as well follow
 the previously-private block, so we're back in square one.

Right, but the thing is, if all miners quickly come to consensus and are
all mining on the same block, there's nothing the attacker can exploit
in the first place.

Suppose Alice the attacker is 100 blocks ahead of the main network
somehow. We'll say the other miners are working to extend block n, and
she's in posession of 100 blocks extending that. She also has just under
50% of the hashing power.

Now when the main network finds a block n+1, Alice can do one of two
things: she can publish her own n+1 block, or she can do nothing. If she
does nothing, the main network will find block n+2 faster than she finds
n+101, so eventually she loses. Thus she has to publish.

In your attack she publishes to a subset of nodes strategicly, splitting
the hashing power between nodes working to extend her n+1, and the other
n+1 found. However, with near-target headers, very quickly all hashing
power will come to consensus and all work to extend the same block,
either theirs or Alice's. Given that they have the majority, they will
find another block faster on average than Alice can extend her lead, and
thus eventually Alice will lose.

Now there is still a slight advantage for Alice in that it takes some
time for the whole network to come to consensus, but this is a much
slimmer margin, maybe a few percentage points, so at best Alice might
need, say, 45% of the total hashing power.

-- 
'peter'[:-1]@petertodd.org
0004b8381fe97338c8b710cb662160f08e391820f30a375bb9b9


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 11:24:33AM -0500, Ittay wrote:
 Yes - this is for the mailing list.
 
 Regarding the algorithm - as we explain in the paper, as long as the
 attacker is way ahead - the others can mine on whatever they like. Doesn't
 really matter. Once they almost close the gap (and they will, because
 they're the majority), leaving only 1 block lead, the selfish miners
 publish their secret blocks, loose their lead, but win the entire secret
 chain. The honest miners thus loose all the work they did so far. It
 doesn't really matter how the honest miners waste their time.

Yes, they lose their work, but that's irrelevant: what's important is
eventually Alice runs out of secret blocks and then has no advantage
over the other miners.

In your paper Alice created her lead by exploiting the fact that not all
of the hashing power was working to extend the same block due to the
first-wins rule. With my solution that situation doesn't happen in the
first place: forks are resolved quickly because both sides have both
forks, and consensus on which one is the winner is achieved very quickly
by proving which side has the majority of hashing power through
near-target PoW solutions. With the majority of hashing power in
consensus and working to extend the same block there's nothing Alice can
do to get ahead, defeating the attack.

-- 
'peter'[:-1]@petertodd.org
0008adb581077dcfa0bf067a4ee010fbabb92d136292625b2299


signature.asc
Description: Digital signature
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote:
 On Mon, Nov 4, 2013 at 10:25 AM, Ittay ittay.e...@cornell.edu wrote:
 
  As for the rational motivation of the individual miners - that's a good
  point!
  Here is a solution we did not put in the paper due to space constraints
  that should alleviate your concern:
  Instead of locally choosing a block at random, have a deterministic
  pseudo-random mechanism for choosing between competing chains. E.g., take
  the one whose last block hash is smaller. This way all miners choose the
  same chain, and the guarantees of our solution hold.
 
 
 I take that back.

Speaking of, I'm going to take back my solution as well; I misunderstood
your paper.

So here's your argument in a ELI5 nutshell:

Alice is a miner with some amount of hashing power. She has the ability
to detect new blocks on the network extremely effectively for whatever
reason; in short she has unusually good knowledge of the state of the
network. She is also very good at publishing her blocks and getting them
to the majority of hashing power in very little time; she has unusually
good connectivity to all miners. (low-latency and high bandwidth)

She's so good at this that when she finds a new block, she keeps it a
secret! She can get away with this because she knows that the moment Bob
finds a block, she can immediately broadcast it to the rest of the
network before the other block propagates. Instead of building on Bob's
blocks, almost everyone builds on Alice's block, depriving Bob of the
revenue. Gradually Alice gets more and more miners because Bob, and
other pools, don't pay out as much.

You propose a rule where essentially miners extend Bob's block 50% of
the time, and show in your paper how that leads to a scenario where
Alice needs to have at leastr 1/4 of the total hashing power to
succesfully pull this attack off anyway.


What I did succesfully show is that for a short-term rational miner
they're still better off mining to extend the block they hear about
first rather than using your pick-one-at-random rule, because when you
hear about a block is important information about whether or not the
majority is mining on it. This is true even if others are using the
pick-one-at-random rule. (they're better defecting than doing what's
right for the whole network) Even worse is that miners have a rational
incentive to broadcast such near-target headers to try to encourage
other miners to work on the same fork that they are working on. The
near-target idea came about for a totally different reason, so it's
something that might wind up being implemented anyway.

Mike Hearn's idea of making it easy to identify nodes associated with
hashing power is still wrong. Although again, it's something that miners
themselves have rational incentives to do. (you always want to encourage
others to send you their blocks, and you also want to be able to send
your blocks to the majority of hashing power as quickly as possible)

Where the idea goes wrong is it makes it easier for Alice to identify
hashing power, specifically where she needs to send her blocks to
distribute them to the majority as quickly as possible. The second
problem occurs if those nodes also distribute blocks to connecting
peers: this makes it easy for Alice to be sure she'll hear about a new
block as soon as possible by connecting to every one of those peers with
a high-speed, low-latency connection. Bizzarely the idea does work if
the advertised nodes only accept blocks, and never send blocks - instead
miners would *only* send their blocks to other miners who have proven
their hashing power, and do so essentially largest miner to smallest.
Now unless Alice already is a large miner, her strategy can't work.  Of
course this will strongly encourage further centralization of pools. But
it is in the interests of rational miners sadly.

That blocks take a finite amount of time to propagate makes the problem
worse: for Alice to learn that another block has been mined only
requires her to receive the small 80 byte header from a peer; she
doesn't need the whole block. She thus can know the block exists well
before it has a chance to propagate fully. Even if every miner were
directly peered to every other as some suggest, Alice could simply make
smaller blocks, faster propagating than everyone else and use especially
low-latency connections to win the race.

On the other hand, the Bitcoin protocol is currently designed such that
a miner can mine a block without knowing the previous block in full.
Given the large block reward and/or a supply of transactions they knew
no other miner had a rational miner would start trying to extend the
longest chain they know about prior to actually receiving and validating
the full block. Again, when miners start doing this - perhaps out of
desperation due to low revenue - as long as Alice has the lowest latency
network she'll win. (she doesn't even need to have the highest bandwidth
in this case) We can change 

Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Alan Reiner
Sorry guys, I'm a little late to the party here.  I skimmed over the
paper, and appreciated Peter Todd's recap of it.  My first thought was
that this seems profit-neutral at best, when you take into account all
the races you lose by trying to beat the propagation of other miners'
blocks.

So given the assumption that Alice is well-connected as Peter
mentioned, it seems like this is a concern.  But is this a realistic
assumption?  All miners have an incentive to be thoroughly connected to
one another, to make sure they minimize the amount of time they spend
mining on forks and that their blocks win with minimal chance of being
orphaned.  Is it realistic that one miner can somehow monopolize the
good connections when the big miners are already trying to do the same
thing for honest reasons?  If you have a network full of honest miners
and this one selfish-miner, it seems that all the honest miners need to
do is try to establish those connections to each other as well as Alice
does, and Alice will end up orphaning all her profit away.

Furthermore, you can de-incentivize it by simply randomizing the order
of broadcasts.  Although you are maintaining multiple concurrent
connections, the data still exits your network card as a serial stream
of packets, and it seems that if you randomize who gets your new-block
broadcasts first, then it further reduces the Alice's advantage if she's
not guaranteed to be first.   Sure, she can do it sometimes, but it
would seem that even a couple failures to beat the rest of the network
is going to erase most/all of what she gained on the blocks/chains that
she wins.

I liked the statement by Chris WIllmer on the reddit thread:  practice
 theory.  The more we can theorize our way to believing the
conclusions that this is a problem, the more incentive there is for
someone intelligent to actually try it.  It's very possible that the
conditions needed to execute this attack just cannot be attained in
practice. 

-Alan




On 11/04/2013 04:04 PM, Peter Todd wrote:
 On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote:
 On Mon, Nov 4, 2013 at 10:25 AM, Ittay ittay.e...@cornell.edu wrote:

 As for the rational motivation of the individual miners - that's a good
 point!
 Here is a solution we did not put in the paper due to space constraints
 that should alleviate your concern:
 Instead of locally choosing a block at random, have a deterministic
 pseudo-random mechanism for choosing between competing chains. E.g., take
 the one whose last block hash is smaller. This way all miners choose the
 same chain, and the guarantees of our solution hold.

 I take that back.
 Speaking of, I'm going to take back my solution as well; I misunderstood
 your paper.

 So here's your argument in a ELI5 nutshell:

 Alice is a miner with some amount of hashing power. She has the ability
 to detect new blocks on the network extremely effectively for whatever
 reason; in short she has unusually good knowledge of the state of the
 network. She is also very good at publishing her blocks and getting them
 to the majority of hashing power in very little time; she has unusually
 good connectivity to all miners. (low-latency and high bandwidth)

 She's so good at this that when she finds a new block, she keeps it a
 secret! She can get away with this because she knows that the moment Bob
 finds a block, she can immediately broadcast it to the rest of the
 network before the other block propagates. Instead of building on Bob's
 blocks, almost everyone builds on Alice's block, depriving Bob of the
 revenue. Gradually Alice gets more and more miners because Bob, and
 other pools, don't pay out as much.

 You propose a rule where essentially miners extend Bob's block 50% of
 the time, and show in your paper how that leads to a scenario where
 Alice needs to have at leastr 1/4 of the total hashing power to
 succesfully pull this attack off anyway.


 What I did succesfully show is that for a short-term rational miner
 they're still better off mining to extend the block they hear about
 first rather than using your pick-one-at-random rule, because when you
 hear about a block is important information about whether or not the
 majority is mining on it. This is true even if others are using the
 pick-one-at-random rule. (they're better defecting than doing what's
 right for the whole network) Even worse is that miners have a rational
 incentive to broadcast such near-target headers to try to encourage
 other miners to work on the same fork that they are working on. The
 near-target idea came about for a totally different reason, so it's
 something that might wind up being implemented anyway.

 Mike Hearn's idea of making it easy to identify nodes associated with
 hashing power is still wrong. Although again, it's something that miners
 themselves have rational incentives to do. (you always want to encourage
 others to send you their blocks, and you also want to be able to send
 your blocks to the majority of hashing 

Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 04:45:24PM -0500, Alan Reiner wrote:
 So given the assumption that Alice is well-connected as Peter
 mentioned, it seems like this is a concern.  But is this a realistic
 assumption?  All miners have an incentive to be thoroughly connected to
 one another, to make sure they minimize the amount of time they spend
 mining on forks and that their blocks win with minimal chance of being
 orphaned.  Is it realistic that one miner can somehow monopolize the
 good connections when the big miners are already trying to do the same
 thing for honest reasons?  If you have a network full of honest miners
 and this one selfish-miner, it seems that all the honest miners need to
 do is try to establish those connections to each other as well as Alice
 does, and Alice will end up orphaning all her profit away.

Right, but as I said, I think this is likely to become a contest of who
can create the lowest latency mining operation, or to be more precise,
who can get the best ratio of latency per dollar.

Unfortunately even with totally honest mining winning orphan rates is
a function of latency; what this paper has done is mainly show a
remarkably effective way of leveraging low-latency and very good
visibility to the network.

Regardless, globe-spanning low-latency networks cost a lot of money, so
if they are something that makes mining more profitable, for whatever
reason, that's an effect that will incentivise pools to grow larger and
more centralized.

 Furthermore, you can de-incentivize it by simply randomizing the order
 of broadcasts.  Although you are maintaining multiple concurrent
 connections, the data still exits your network card as a serial stream
 of packets, and it seems that if you randomize who gets your new-block
 broadcasts first, then it further reduces the Alice's advantage if she's
 not guaranteed to be first.   Sure, she can do it sometimes, but it
 would seem that even a couple failures to beat the rest of the network
 is going to erase most/all of what she gained on the blocks/chains that
 she wins.

Yeah, there's a lot of possible solutions, but what I'm seeing looking
at them is they all tend to be not economically rational, in the short
term, or even worse, they actually incentivize mining pools to get
larger. For instance anything that tries to prevent Alice from sybiling
the network by forcing nodes to prove they have mining capacity just
means that larger miners will have an advantage over smaller ones in
getting their blocks propagated as fast as possible. Once Alice does
have a reasonable amount of mining capacity, she can still use the
selfish miner attack to grow larger and more profitable.

-- 
'peter'[:-1]@petertodd.org
000aae6d13639c5b4555eeda301ebcbc53f12e8a633e267c8331


signature.asc
Description: Digital signature
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Gustaw Wieczorek
Mike Hearn wrote:

 how about if we wrote code to automatically build a miner backbone

Yeah, let's build a backbone, or a cloud, and then we could have Google run it!

Come on, Mike, your conflict-of-interest as an employee is hanging out in the 
open, flapping in the breeze here...  Don't you think it's a bit obvious for 
somebody in your position to advocate centralization of infrastructure, 
especially when it comes to bitcoin?


On the other hand, I guess your blind trust in IP addresses as a solid 
foundation for security is why you were so shocked when the NSA hacked your 
backbone.
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Peter Todd
On Mon, Nov 04, 2013 at 08:14:37PM -0800, Gustaw Wieczorek wrote:
 Mike Hearn wrote:
 
  how about if we wrote code to automatically build a miner backbone
 
 Yeah, let's build a backbone, or a cloud, and then we could have Google run 
 it!
 
 Come on, Mike, your conflict-of-interest as an employee is hanging out in the 
 open, flapping in the breeze here...  Don't you think it's a bit obvious for 
 somebody in your position to advocate centralization of infrastructure, 
 especially when it comes to bitcoin?
 
 
 On the other hand, I guess your blind trust in IP addresses as a solid 
 foundation for security is why you were so shocked when the NSA hacked your 
 backbone.

Go away.

Mike specifically mentioned the idea of using Tor addresses, which are
authenticated. In addition this mechanism to create a backbone
*automatically* is exactly as decentralized as Bitcoin mining itself is.
It has nothing to do with Google.

I suggested the mechanism myself for slightly different reasons, and if
you know me, you'd know I'm the first to jump on anyone pushing
centralization.

-- 
'peter'[:-1]@petertodd.org
000517064a43348fa39325bdc244ffb1d0da11ab85676d494a85


signature.asc
Description: Digital signature
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Auto-generated miner backbone

2013-11-04 Thread Gregory Maxwell
On Mon, Nov 4, 2013 at 8:39 PM, Peter Todd p...@petertodd.org wrote:
 I suggested the mechanism myself for slightly different reasons, and if
 you know me, you'd know I'm the first to jump on anyone pushing
 centralization.

Likewise, I did too and am also not very tolerant with trusted or
centeralized things in general.

An authenticated miner announced set of nodes is _far_ from a cure
all, as any attack they stop can be recovered by adding and dos
attacks the public miner announced nodes to the attack's
requirements... but we build security with layers.

Bitcoin's security is only improved when we can weave the network
tighter and make partitioning it more difficult.

--
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=60136231iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development