New post.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
rustyrussell · Oct 30, 2014 · 03e9d19 · 03e9d19
1 parent be563b9
commit 03e9d19
Showing 1 changed file with 71 additions and 0 deletions.
diff --git a/_posts/2014-10-30-More-Regular-Block-Times.md b/_posts/2014-10-30-More-Regular-Block-Times.md
@@ -0,0 +1,71 @@
+---
+layout: post
+commentIssueId: 36
+---
+One problem with bitcoin blocks is the irregular timing between them.
+If you're waiting for inclusion in a block to make double-spending
+more difficult, the formula you need to know is is 1-e^(-(T/600)):
+this says the probability that a block has been found at time T
+seconds.  At T=600 (ie. 10 minutes) it's 63%: in fact most blocks are
+found in under 7 minutes, but there's a long tail.  14% of the time
+you're still waiting after 20 minutes, and 5% of the time you're
+waiting over 30 minutes with no confirmation, and 1% are over 46
+minutes.
+
+10 minutes is a long time already so this doesn't usually hurt
+bitcoin, but for shorter block times (for pettycoin, substitute
+minutes below for seconds) it can undermine the aim of making payment
+usable for casual purchases.
+
+One obvious idea to trim this tail is to allow weaker blocks if some
+time has passed, say, twice the target block time (which should happen
+14% of the time).  But this doesn't quite have the desired effect,
+because miners will store such lower-target blocks when they find
+them, whereas normal blocks enter the blockchain immediately.
+
+Imagine block 100 is produced at midday.  Miner Jill finds an easy
+block 101 at 12:05 and sends it out.  At 12:20, no normal block has
+been found, so nodes accept Jill's block.  But this means that
+transactions broadcast at 12:06 are still waiting, so the fast block
+time doesn't help them.
+
+I hacked up a quick simulator, and simulating 1000 blocks demonstrates
+this: the 99-of-transactions% case withdrops to around 30 minutes
+(from 46 minutes), but we can do better.  We could simply allow easy
+blocks after 10 minutes rather than twenty, but there's another way.
+
+There's usually more than one easy block found before the 20 minute
+mark (we'd expect 4).  Among those, we actually want the last one, not
+the first, since it will include the most transactions.  But naively
+accepting the last or the one with most transactions would mean
+everyone would keep trying to mine a replacement for the last easy
+block, instead of mining on top of that for the next block.
+
+Fortunately, we know what transactions were pending at the 20 minute
+mark (at least for us; there are delays across the network).  We can
+use this to judge easy blocks: pick the one most similar to these
+"expected" transactions.
+
+Unfortunately this opens the door to miners gaming the system.  Jill
+creates a heap of her own self-to-self transactions, and includes them
+in the block she's solving.  If she solves it, publish the block like
+normal.  If she gets an easy solution, she would wait until just
+before the 20 minute mark and she knows her easy block has a chance.
+Then she publishes all those self-to-self transactions; any other
+miner won't have included those transactions, and her block will look
+really good by our heuristic.
+
+Thus I suggest judging an easy block by summing the transaction fees
+of transactions which match our "expected" ones.  There's now a real
+risk for a miner publishing self-to-self transactions with fees, since
+another miner may include these transactions in their own competing
+block, and gain the fees.
+
+Such an algorithm means that 1% case is around 22 minutes; it's pretty
+close to the aim of ensuring 20 minute upper limit on transaction
+processing.
+
+Side note: the technique used to adjust difficulty every 2016 would
+have to be changed a little.  The simplest way is to adjust difficulty
+after each 2016-blocks-worth of work, counting easy blocks as 1/4.
+This might be up to 3/4 of a block out, but that's acceptable error.