Re: [Bitcoin-development] Cut-through propagation of blocks

2014-05-24 Thread Jonathan Levin
I have done some work on incentives arising from block propagation times and it 
turns out that Bitcoin is already quite good at establishing the primacy of 
blocks by time despite what people think. Part of the reason for this is the 
way that partitions on the network evolve as a block is propagated. Typically 
at the moment, blocks reach over 50% of the network in 5 seconds. Reach being 
defined as a node receiving and validating a block. If we make an assumption 
that the hashing power of the network is uniformly distributed over the nodes 
(I know it is not a good assumption but can discuss it off the list). Then 50% 
of the hashing power are already building a block that builds on top of the 
block that is already circulating. The probability that there is a collision on 
the network therefore falls fast and then the probability that the miner who 
propagated the first block wins given a collision occurs is rising. I think 
that block propagation times might actually be a bigger issue for miners who 
are less well connected to the network in the sense that they spend more time 
mining redundant problems and during that time may find blocks to compete with 
blocks that are already spreading throughout the network.

I have a paper that models this more formally and has some numerical 
simulations but cannot publish it on the internet at present (University 
Regulations) but I am happy to share a version privately if anyone is 
interested.

Best,

Jonathan

--
Jonathan Levin
Co-Founder Coinometrics
http://www.coinometrics.com/
Postgraduate Economist | St Antony's College | Oxford University
@jony_levin
@Coinometrics




--
Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos.
Get unparalleled scalability from the best Selenium testing platform available
Simple to use. Nothing to install. Get started now for free.
http://p.sf.net/sfu/SauceLabs___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Economics of information propagation

2014-04-21 Thread Jonathan Levin
Thank you for your thoughts. 

 The earlier, larger block A will only become stale if *two* blocks are
 found in the extra time it takes for block A to propagate the network.
 That is a substantially different risk, and probably a negligible
 concern to most miners.

I really like Mark’s suggestion but one concern is that it might tip the needle 
too far. Currently, there is a private cost to include more transactions, which 
might be too high, but limit the amount of negative externalities that this 
creates on other miners. If I am able to create blocks that are very likely to 
be on the main chain with the maximum number of transactions then this makes 
imposing negative externalities on other miners less costly. Other nodes that 
are closely connected to me would experience a positive externality through 
this as well. Would have do some more thinking here but it seems that there is 
a balance to strike.

 If anything, looks like a threat to the current situation with huge
 mining subsidies coming from the seigniorage, not a problem that you
 would have when the the seigniorage is gone.

The incentives remain so long as the ratio of the seignorage revenues to 
transaction fees remain very high. Even though the dollar price does not change 
that relationship it does mean that Bitcoin becomes more expensive in USD terms 
as the USD price of Bitcoin rises.

 I think the most important part is that nodes can reliably decide on
 first received, regardless of how they subsequently act on it. 

If we want to limit the amount of network time spent on redundant problems it 
would be best for miners to act on this information? What is the benefit of 
serialisation? Is it that the miner would consider it more likely to make it 
into the main chain rather than the block that came second?

 But I don't see how miners mining headers first would result in empty
 blocks either.

I guess it is due to the fact that this is the only way a miner can be certain 
that none of the transactions have been spent already resulting in an orphan 
block.

On 21 Apr 2014, at 17:00, Mark Friedenbach m...@monetize.io wrote:

 That wasn't what I was saying. Right now the primacy of a block is
 determined by the time at which the `block` message is received, which
 is delays due to both the time it takes to transmit the block data and
 the time it takes to validate. Headers-first, on the other hand, has the
 option of basing primacy on the time the block header is received, which
 is O(1) time to transmit and to SPV-validate. Mining on that block
 doesn't actually commence until the full block is received and validated.
 
 To see how this works, take an example: two blocks with a common parent
 are found relatively close to each other, block A and block B. A is
 found first but is a large block with the maximum block size and many
 slow scripts. B is found a few seconds later and is an empty block. In
 the current regime it is entirely possible that block B, the later but
 smaller block, would get received and processed first by more mining
 peers than the larger block A, exactly as described in Jonathan Levin's
 email.
 
 With headers-first, however, the cost of propagation of the block header
 is the same and we should expect block A to win out over block B nearly
 every time. Miners will continue working on the old, known valid parent
 block until the contents of block A are received and processed. So the
 smaller block B is still found, and since it's data moves across the
 network faster, miners even briefly mine on block B. But as soon as they
 receive and process the contents of block A, they switch to that.
 
 The earlier, larger block A will only become stale if *two* blocks are
 found in the extra time it takes for block A to propagate the network.
 That is a substantially different risk, and probably a negligible
 concern to most miners.
 
 On 04/20/2014 09:06 PM, Peter Todd wrote:
 That is mistaken: you can't mine on top of just a block header,
 leaving small miners disadvantaged as they are earning no profit
 while they wait for the information to validate the block and update
 their UTXO sets. This results in the same problem as before, as the
 large pools who mine most blocks can validate either instantly - the
 self-mine case - or more quickly than the smaller miners.
 
 Of course, in reality smaller miners can just mine on top of block
 headers and include no transactions and do no validation, but that is
 extremely harmful to the security of Bitcoin.



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
Start Your Social Network Today - Download eXo Platform
Build your Enterprise Intranet with eXo Platform Software
Java Based Open Source Intranet - Social, Extensible, Cloud Ready
Get Started Now And Turn Your Intranet Into A Collaboration Platform

[Bitcoin-development] Economics of information propagation

2014-04-20 Thread Jonathan Levin
Hi all,

I am a post-graduate economist writing a paper on the incentives of mining. 
Even though this issue has been debated in the forums, I think it is important 
to get a sense of the magnitude of the incentives at play and determine what 
implications this has for the transaction fee market.

As it has been pointed out before the marginal cost for miners does not stem 
from the private cost of the miner validating the signature and including it in 
the list of transactions in the block but rather the increased probability that 
the block will be orphaned as a result of slower propagation. Gavin did some 
back of the envelope worst case calculations but these overstated the effect of 
propagation delay. The reason being the 80ms additional time to reach 50% of 
the network is spread throughout the time that it takes to reach 50% of the 
network. During this time miners are notified about the block and treat it as 
the longest chain and hence are no longer mining with the aim to produce a 
competing block. 

I am looking to calculate the change in the curvature of the probability mass 
function that a block hears about my block in any given second as a function of 
the block size. Although there is likely to be significant noise here, there 
seems to be some stable linear relationships with the time that it takes to 
reach different quartiles. Has anyone done this? I have used some empirical 
data that I am happy to share but ideally I would like analytical solutions.

Following Peter Todd, I also find the concerning result that propagation delays 
results in increasing returns to higher shares of the hashing power. Indeed it 
may well be in the interest of large pools to publish large blocks to increase 
propagation delays on the network which would increase orphan rates 
particularly for small miners and miners that have not invested in sufficient 
bandwidth / connectivity. If a small miner hears about a block after 4.5 
seconds on average there is a 0.7% chance that there is already a block in 
circulation.  Large miners can increase the time that it takes for small miners 
to hear about blocks by increasing the size of their blocks. For example if the 
time that it takes for a small miner to hear about the block goes to 12 seconds 
there is a 2 percent chance there is already a block in circulation for the 
small miner. There is also a 1.2% chance that there will be a competing block 
published after a small miner propagates in the time that it gets to full 
propagation. Am I getting this right that the probability of a miner’s block 
being orphaned is comprised of the probability that the miner was not the first 
to find a valid block and the probability that given they are first, someone 
else in the absence of hearing about it finds a competing valid block. 

One question is: Are orphans probabilistic and only resolved after hearing 
about a new block that lengthens the chain or is there a way to know in 
advance? Is it frowned upon to mine on top of a block that you have just found 
even though it is very likely going to end up an orphan?

Would be happy to share the draft form of the paper and receive any feedback.

Finally, at coinometrics we are working on a modified client to capture 
information on network propagation and would invite any suggestions of any 
other useful statistics that would be useful in the development of software. 

Best,

Jonathan










On 21 Apr 2014, at 01:16, bitcoin-development-requ...@lists.sourceforge.net 
bitcoin-development-requ...@lists.sourceforge.net wrote:

 Send Bitcoin-development mailing list submissions to
   bitcoin-development@lists.sourceforge.net
 
 To subscribe or unsubscribe via the World Wide Web, visit
   https://lists.sourceforge.net/lists/listinfo/bitcoin-development
 or, via email, send a message with subject or body 'help' to
   bitcoin-development-requ...@lists.sourceforge.net
 
 You can reach the person managing the list at
   bitcoin-development-ow...@lists.sourceforge.net
 
 When replying, please edit your Subject line so it is more specific
 than Re: Contents of Bitcoin-development digest...
 
 
 Today's Topics:
 
   1. Re: bits: Unit of account (Oliver Egginger)
   2. Re: bits: Unit of account (Christophe Biocca)
   3. Re: bits: Unit of account (Gmail)
   4. Re: bits: Unit of account (Mike Caldwell)
   5. Re: bits: Unit of account (Justin A)
 
 
 --
 
 Message: 1
 Date: Sun, 20 Apr 2014 20:43:24 +0200
 From: Oliver Egginger bitc...@olivere.de
 Subject: Re: [Bitcoin-development] bits: Unit of account
 To: Bitcoin Development bitcoin-development@lists.sourceforge.net
 Message-ID: 5354154c.1080...@olivere.de
 Content-Type: text/plain; charset=ISO-8859-1
 
 Hello,
 
 just my two 'cents':
 
 Terms arises by itself. Just as most people speak of coins when they
 mean bitcoins. I do not see that bitcoin is currently in common use
 except for speculation.