nervosnetwork / ckb-light-client

CKB light client reference implementation
MIT License
14 stars 16 forks source link

refactor: check total difficulty with short-circuit #150

Closed yangby-cryptape closed 11 months ago

yangby-cryptape commented 1 year ago

Issue

If there are too many epochs, calculate the upper limit of total difficulty may cause an overflow.

Let $n$ denote the length of epochs which will be synchronized in one message. Let $D{fisrt}$ denote the epoch difficulty of the first block which will be synchronized. Let $D{last}$ denote the epoch difficulty of the last block which will be synchronized. Let $l = \Big \lceil {\log{\tau}{\frac{D{first}}{D{last}}}} \Big \rceil$ denote the length that how many epochs, $D{fisrt}$ can be increased or increased to $D_{last}$.

The upper limit of total difficulty of blocks which will be synchronized is:

$$ D{upper} = D{fisrt} \cdot (\large\sum{i=1}^{\lceil \frac{n+l}{2} \rceil}{\tau^i} + \large\sum{i=1}^{\lceil \frac{n-l}{2} \rceil}{\tau^{\lceil \frac{n+l}{2} \rceil-i}}) $$

If $D_{upper}$ is greater than $2^{256}-1$, the client will be panicked.

Solution

So, we could use a short-circuit algorithm.

Pseudo code to explain the changes:

codecov-commenter commented 1 year ago

Codecov Report

Patch coverage: 100.00% and project coverage change: +0.06% :tada:

Comparison is base (ae04578) 69.80% compared to head (fc5f1b8) 69.86%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## develop #150 +/- ## =========================================== + Coverage 69.80% 69.86% +0.06% =========================================== Files 25 25 Lines 6348 6358 +10 =========================================== + Hits 4431 4442 +11 + Misses 1917 1916 -1 ``` | [Flag](https://app.codecov.io/gh/nervosnetwork/ckb-light-client/pull/150/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nervosnetwork) | Coverage Δ | | |---|---|---| | [unittests](https://app.codecov.io/gh/nervosnetwork/ckb-light-client/pull/150/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nervosnetwork) | `69.86% <100.00%> (+0.06%)` | :arrow_up: | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nervosnetwork#carryforward-flags-in-the-pull-request-comment) to find out more. | [Files Changed](https://app.codecov.io/gh/nervosnetwork/ckb-light-client/pull/150?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nervosnetwork) | Coverage Δ | | |---|---|---| | [...s/light\_client/components/send\_last\_state\_proof.rs](https://app.codecov.io/gh/nervosnetwork/ckb-light-client/pull/150?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nervosnetwork#diff-c3JjL3Byb3RvY29scy9saWdodF9jbGllbnQvY29tcG9uZW50cy9zZW5kX2xhc3Rfc3RhdGVfcHJvb2YucnM=) | `93.16% <100.00%> (+0.09%)` | :arrow_up: | ... and [1 file with indirect coverage changes](https://app.codecov.io/gh/nervosnetwork/ckb-light-client/pull/150/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nervosnetwork)

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.