feat: introduce a security parameter to optimize the proof size with controlled security

[yangby-cryptape]

Issue

The previous method, which is used for estimating the samples count, is too simple.

When the total number of blocks in the region which requires verifying is increased, the security is decreased.

Technical Overview

• Let
  • $m$ denote the total number of blocks which used to prove the chain root is valid.
  • $p$ denote the probability of catching the adversary with a single sample.
  • $p_{m}$ denote the probability of failure, i.e., not catching the optimal adversary after $m$ independent queries.
• So $p_{m} = (1 - p)^{m}$.
• Since $p = \frac{1}{k}$ (ref: theorem 2 in section 5.4 of FlyClient: Super-Light Clients for Cryptocurrencies), if we want $p{m} \le 2^{-\lambda}$, then $m \ge \frac{\lambda}{\log{\frac{1}{2}} {(1 - \frac{1}{k})}}$.

[codecov-commenter]

Codecov Report

Merging #54 (0625396) into develop (ad0fc57) will increase coverage by 0.05%. The diff coverage is 66.66%.

@@             Coverage Diff             @@
##           develop      #54      +/-   ##
===========================================
+ Coverage    33.13%   33.18%   +0.05%     
===========================================
  Files           22       22              
  Lines         3338     3345       +7     
  Branches       461      464       +3     
===========================================
+ Hits          1106     1110       +4     
- Misses        2120     2121       +1     
- Partials       112      114       +2     

Flag	Coverage Δ
unittests	33.18% <66.66%> (+0.05%)	:arrow_up:

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
src/protocols/light_client/sampling.rs	93.93% <66.66%> (-4.37%)	:arrow_down:

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.