Skip to content
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Commit 4f05998

Browse files
committedAug 29, 2014
Belated update on what I'm doing.
1 parent d2785a2 commit 4f05998

File tree

1 file changed

+66
-0
lines changed

1 file changed

+66
-0
lines changed
 

‎_posts/2014-08-28-Multiple-prevs.md

+66
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
---
2+
layout: post
3+
---
4+
5+
When I looked at the goals for Alpha02, I realized I'd be breaking the
6+
protocol, so I decided I wanted to do all the breakage at once. The
7+
first change is to include more than one "prev" reference in each block.
8+
9+
Blocks currently look like this:
10+
11+
+-------+----------+
12+
| Stuff | PrevHash |...
13+
+-------+----------+
14+
15+
This is very much modelled on the bitcoin protocol; each block builds
16+
on the previous one. But it's been suggested for bitcoin SPV clients
17+
(Simplified Payment Verification, ie. clients without full knowledge)
18+
that you can skip some blocks but still show that you've done all the
19+
work.
20+
21+
The idea is simple: each block's hash has to be below the target
22+
value. But since blocks are found by trial and error, some blocks
23+
will be _way_ under the target. The statistics are simple: half the
24+
blocks will be twice as "hard" as they need to be, one quarter four
25+
times as hard, etc.
26+
27+
So, if we let a block which is four times as hard point back 4 blocks
28+
(not just 1), we can drop the three intermediate blocks, for some
29+
space savings. Of course, we don't know how "hard" a block is until
30+
we've found it, so every block needs to include every back pointer up
31+
to some limit.
32+
33+
+-------+-----------+-----------+-----------+-----------+
34+
| Stuff | PrevHash1 | PrevHash2 | PrevHash4 | Prevhash8 |...
35+
+-------+-----------+-----------+-----------+-----------+
36+
37+
It's just as much work to fake such a "skippy" chain as it is to fake
38+
the entire chain with single back pointers, so no security is lost.
39+
40+
This is great for pettycoin: we have a _horizon_ past which we don't
41+
care about the block contents, just that they lead to the current
42+
blocks we do care about. This reduces the amount of storage we need
43+
in future, though not by as much as we'd hope (roughly a factor of 10
44+
over keeping every header).
45+
46+
There are some extra tricks we can do; the simplest is to use a merkle
47+
tree to hash the prevhash fields together so when we know which one we
48+
need we can throw away the others (and keep log2(numPrevHash)). We
49+
can also choose which blocks we keep, aiming to reach the shortest
50+
path, rather than simply stepping backwards greedily. In fact, we
51+
could even step *forwards* if it allows us to then skip backwards
52+
further. Dijkstra's algorithm would be of use here, though I haven't
53+
measured how much difference it makes in practice.
54+
55+
The naive back skip list has a fascinating property, in that it
56+
quickly converges on the same blocks. If there's a limit to how far
57+
you can skip back, this implies that everyone will agree on the
58+
skiplist for really old blocks.
59+
60+
This may also turn out to be a boon: I always planned that the
61+
protocol would fold back rewards from blocks in the far future
62+
(eg. 3-5 years) to those in the past. But this would mean that we
63+
can't discard blocks below the horizon for at least that long. Yet
64+
it's just as fair if we call agree on which blocks remain in the
65+
skippy chain, and pile the rewards on to those, rather than every
66+
block.

0 commit comments

Comments
 (0)
Please sign in to comment.