Optimize block links

[Gilthoniel]

Currently, a link to a block is signed from the digest of the previous block. This is fine but not optimal because it's the block with the current roster that should sign it so that a chain to a block (the proof of consistency) is shaped with the smallest possible number of blocks. In other words, a proof to a block should look like this:

Genesis[R] --> Block[R'] --> Block[R''] --> Block[R'']

Basically, every block that has a change in the roster is a new checkpoint for the chain. New blocks should always be signed with the most recent roster to prevent a group of malicious nodes to take over the chain (i.e. an old roster with few nodes thus a small failure threshold).

[nkcr]

For a more visual representation, where X denotes a roster change:

Before:
┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐
│ X ├───►│   ├───►│ X ├───►│   ├───►│   ├───►│ X ├───►│   │
└───┘    └───┘    └───┘    └───┘    └───┘    └───┘    └───┘

After:
┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐
│ X │    │   │    │ X │    │   │    │   │    │ X │    │   │
└─┬─┘    └─┬─┘    └─┬─┘    └─┬─┘    └─┬─┘    └─┬─┘    └─┬─┘
  │───────►│        │───────►│        │        ├───────►│
  └────────────────►│────────────────►│        │
                    └─────────────────────────►│

[ineiti]

Hmm - the original Chainiac paper presenting the skipchain idea propose two chains:

• one key chain with updates to the roster
• one data chain with the actual data

Both chains contain not only links from block N to block N+1, but also higher-level skips. So if the client has block 0, and wants to proof that block 400'000 is valid, it has to download only a subset of blocks. Whether there was a roster change or not.

In the cothority-skipchain, the key and data chain have been merged into one chain. So roster changes can happen in any block. But the higher level skips are implemented and allowed a new client to get from block 0 to block 400'000 in about a second by downloading 30 something blocks, IRRC.

So does Dela have anything like skipchains? Are higher-level skips implemented? Because if we have 100 elections with 2000 votes each, it will take a long time for a client to catch up.