kzg-sharding
kzg-sharding copied to clipboard
Add a simple corrupted samples/proofs detector
This detector implements a straightforward binary search to find corrupted samples and proofs. It mostly relies on get_aggregated_pairings
method, which is heavily modified from the original verify
method. A few tests are added to verify the results.
The code is not optimized, but it should illustrate the basic idea of locating the corrupted ones as we discussed last week. In the worst case, the code will perform 4n-2 pairings to find all corrupted samples and/or proofs (e.g., in the case that all samples or proofs are corrupted).
A couple of optimizations can be done following this PR:
- The number of pairings may be further reduced to 2n-2 (see notes in the code).
- The linear combinations of elliptic curve points (e.g., proofs/commitments/etc) can be further optimized so that some combinations do not need to be re-calculated.