|
| 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