celestiaorg / celestiaorg/celestia-node

Update BEFP creation and validation to accomodate more types of validator fraud

Open
#2,377 17 comments 0 reactions 1 assignee Claimed by @vgonkivs View on GitHub
area:fraud pending:close
Dominant language
Go
Stars
996
Forks
1.1k
Avg merge
1d 6h
Merged PRs (30d)
34

Description

Per this [comment](https://github.com/celestiaorg/nmt/issues/97#issuecomment-1430327821) in nmt defining the attack scenario:
> Malicious consensus nodes could produce and commit a block, denoted as B, in which the shares are not ordered lexicographically based on their namespace IDs. A DA (data availability) full node obtains the block header, including the data root denoted as dataRoot, and the underlying shares, and will attempt to construct the block. However, if the node detects that the shares used to construct dataRoot are unordered, it must provide a proof of bad encoding to the light clients. Specifically, it must indicate that there are out-of-order leaves in the tree represented by dataRoot.

per the [LL white paper](https://arxiv.org/pdf/1905.09274.pdf) section 5.2
> An adversarial consensus node may attempt to produce a block that contains a Merkle tree with children
that are not ordered correctly. To prevent this, we can set a condition in nsHash such that there is no valid hash when leftMaxNs ≥ rightMinNs, and thus there would be no valid Merkle root for incorrectly ordered children. Therefore blockValid(hi) would return false in the simplistic and probabilistic validity rules as there is no possible Mi where root(Mi) = mRooti

addionally, 2/3s of the voting power could commit to shares that not sized properly and would result in an inability to decode the row or col.

We need to have a fraud proof that can handle out of order namespaces and arbitary things that would cause the erasure decoding to fail. BEFPs (perhaps need to be renamed after this), can and should handle these types of fraud.

During the reconstruction process, if there are two shares that are out of order, then we should still be able to create an inclusion proof to half of the shares in that row or col using _either_ the row or column roots. If the square is available, then this will always be the case.

For the second new type of fraud, if there is something wrong with the shares that would cause the row or col to not be decodable, then if the shares are committed to (step 1 below), then that means that the BEFP is valid.

To accomodate this, the verification logic must be altered to encode the following logic:

1. Check inclusion: if inclusion fails, proof is invalid
2. Reconstruction of row of col: if fails, **proof is valid**
4. Create merkel root: if creation of root fails, **proof is valid**
5. Compare existing root: if different, the proof is valid

currently, we are not following steps two and three of the validation process:
https://github.com/celestiaorg/celestia-node/blob/6654cdf4994dbd381efd0d6a29688c731177c855/share/eds/byzantine/bad_encoding.go#L162-L184

cc @renaynay @Wondertan please feel free to add issues, edit, or convert this to an EPIC as needed :slightly_smiling_face:

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.