search

nimiq / core-rs-albatross

Rust implementation of the Albatross protocol
https://nimiq.com
Other
160 stars 61 forks source link

Possible performance optimizations #356

Closed brunoffranca closed 2 years ago

brunoffranca commented 2 years ago

Here are some possible performance optimizations to Albatross. They might or might not be practical, and might or might not be implemented in the future.

  1. Changing the signature scheme used in the micro blocks. Micro blocks contain two BLS signatures in the MNT6-753 elliptic curve (one for signing the block and the other for the VRF). These are very expensive to create and verify. We can change both to use curve 25519 and drastically improve performance. For signing the block there is the ed25519 scheme and for the VRF there is the VXEdDSA scheme (see https://github.com/w3f/schnorrkel, https://www.signal.org/docs/specifications/xeddsa/#vxeddsa and https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-06). The simplest way to do this is probably to use the validators warm key.
  2. Getting rid of the checkpoint macro blocks. Checkpoint blocks are mostly used for syncing and Albatross can work without them. They do introduce small delays every couple of minutes which hurts the performance a bit. We could maybe use a finality gadget (like GRANDPA, see https://arxiv.org/abs/2007.01560) to helps us with the syncing and get rid of the checkpoint blocks. This has the advantage of reducing the number of micro blocks that a node needs to download when syncing, since the finality gadget will most likely always be only a few micro blocks behind the head of the chain (after all, most validators can probably agree on a block that is 10 confirmations deep, for example). The main problem is the added complexity. We would also need to find a solution for the longer duration between rewards. This was a problem before the introduction of the checkpoint blocks, if a validator misbehaved even a single time it would lose the reward for the entire epoch. [A possible solution is for rewards to be slashed gradually. For example, for each time you get view-changed, you lose 1/10 of your reward.]
  3. Switching the groups for the BLS scheme. The elliptic curve we use for BLS signing has two groups. A big one that needs 285 bytes per point, and a small one that needs 95 bytes per point. Right now, we are using the big group for the public keys and the small one for the signatures. But we could easily switch that around. This would give us public keys that are 95 bytes long and signatures that are 285 bytes long. The performance would be similar (signing would be slower but verifying would be the same). But the space savings would be huge on election blocks (since we need to store the public keys of all validators in the body), potentially up to 97 kB. The impact for the Nano zk proofs would also be substantial, since most of the circuit is spent serializing and hashing the validator's public keys we could see a 3x speed improvement on generating the proofs. The PK Tree root calculation would evidently also see a 3x speed improvement. The main drawback is that the signatures on all the blocks would be 3x bigger. This means an extra 380 bytes on each micro block.
brunoffranca commented 2 years ago

After some research, option 2 seems to not have a significant performance improvement, especially when compared to the implementation effort.