Emergent Software - FlyClient Implementation

English Grants
#1

Project

Nervosnetwork/ckb with the consensus changes (implemented as a hard fork upgrade for both Rylai and Nervos Mainnet).

Team

Software company specializing in blockchain and cryptocurrency design. Founded in 2018 and has done work for ETC Labs, as well as non-profit work, and specifically presented FlyClient research at ETC Summit.

Specification Outline

(Full RFC to come as per the stated grant process)

  • Full node consensus changes
    • flyproof generation and validation
    • standalone validation module
    • endpoints for flyproof requests and validation
    • endpoints for transaction merkle proofs
    • endpoints for state merkle proofs
  • Client Side tooling
    • Javascript Validation module (for maximal integrations)
  • Separate RFC writeup for light-client protocol based on FlyClient capabilities (implementation of which would not be included in this project)

Draft of the SoW are written up here

Although some of the above choices are up for debate, it’s advised this be done as a consensus change if that is currently feasible for the Nervos governance system. That would allow for the cleanest implementation, which would be safer, cheaper, and allow for more robust features to be built on top of it later.

The amount of extra data needed for full nodes is just 1 extra hash computation and storage per block currently ~60mb (likely a trivial amount for full nodes).

Uncle validation and reorgs may require special considerations to the data structure, although is not expected to be a significant blocker.

3 Likes
Minimum viable light client via FlyClient-style checkpointing
Open Grant Program Categories and Scope of Work for Applications
#2

Hey @Zachary_Mitton - thanks for your grant submission, the MMR in the block header has been implemented in consensus code previously but was pulled prior to launch because more research is needed before the decision can be made to solidify light client functionality in the node.

Here are the relevant PR’s:


1 Like
#3

Thanks for proposing this! NIPoPoWs such as FlyClient is a key component on our light client roadmap, that makes it a research+engineering hybrid problem. Whether to use FlyClient and how to adopt FlyClient largely depends on how much confidence we have on its design proposal - a hard fork might be the cleanest way to add FlyClient but it’s also possible to do it on application layer.

As the FlyClient in the original paper is designed and only proved secure for Bitcoin, we need to devise a proper variation for CKB before we implement it. I can see some obstacles and I’ll just quote them below:

There’re two problems to solve when we apply FlyClient to CKB:

  1. FlyClient assumes fixed epoch length while NC-Max (the consensus algorithm used in CKB) has variable epoch length;
  2. FlyClient assumes original NC style difficulty adjustment, which depends only on timestamps of the first block of each epoch, while difficulty adjustment in NC-Max depends on the number of uncles in the last epoch.

I think we need to improve the Variable Difficulty MMR design in FlyClient paper to accommodate NC-Max, probably adding more auxiliary fields to MMR interval/leaf nodes. A Merkle proof for uncle inclusion of sampled nodes is not enough, because at epoch transition the verifier needs to verify the difficulty adjustment is correct, which means verifying the number of uncles in the last epoch is correct. So certain epoch information should be encoded in MMR nodes.

FlyClient on CKB is definitely doable. If you could put together a more concrete proposal we’d be happy to discuss and see how can we make it secure and optimal.

So it’s important to have a concrete and convincing design before we go implementing it, which is already on the research team’s plan. For this grant proposal, I think we can either delay the discussion until a design emerges or modify the proposal to include protocol design and make it a milestone if you’re interested.

3 Likes
MAP labs - MAPBridge
Open Grant Program Categories and Scope of Work for Applications
#4

thanks @janx for mirroring the Github comments here.

I am wondering about an alternative way of doing this without encoding the uncle information in the MMR, because NC-Max and NC have the equivalent concept of “total epoch difficulty” (# of blocks * block difficulty target).

In a difficulty transition, an attacker can bias the total epoch difficulty down using bogus timestamps or a lower than actual orphan rate, however a verifier should only be interested in the chain with the highest total epoch difficulty value.

Epoch start/end can be seen as two consecutive MMR leaves with different epoch values. Using the number of blocks between epoch start/end and block difficulty target, a verifier can calculate total epoch difficulty for a completed epoch (by inference they can get the orphan rate used in difficulty adjustment), however I am working through the idea that enough information is available during an epoch for a verifier to identify the chain with highest current total epoch difficulty as well.

blocks2
blocks21178×124 2.34 KB

The orphan rate used in the most recent difficulty transition is provided by provers, the verifier then calculates total epoch difficulty, block difficulty target and number of blocks in the epoch based on this and the timestamps. The verifier should then look for highest total epoch difficulty and can check progression through the epoch.

Because we are only trying to mitigate an attacker lowering total epoch difficulty, is there any issue with the verifier only knowing that a particular epoch has the highest total epoch difficulty (and checking PoW) of all provided chains without having the previous epoch orphan information encoded in the MMR?

#5

We also need to defend against Difficulty Raising Attack as described in “Theoretical Bitcoin Attacks with less than Half of the Computational Power” (btw. the paper also gives a better analysis of block withholding attack than the selfish mining paper imo). In DRA, an adversary keeps trying to raise next epoch difficulty and win the diffculty accumulation game by pure luck. The attack is impractical in Bitcoin and CKB because the adversary cannot raise the difficulty arbitrarily as a difficulty adjustment bound is imposed. So the problem here is how we verify the same constraint in FlyClient.

1 Like