Data Availability with Validity Proofs
Intro
Basin is still in its research phase, and we're exploring various data availability approaches, including XOR-based (and related) schemes for erasure encoding. In this architecture, the validators create an auxiliary data structure with a dual purpose. It can be used to repair data in case of data loss or data withholding attacks and to ensure that the validators are not deleting the old data they are supposed to store.
One common consideration in DA systems is to make the "data storage" requirement optional. This would enable light nodes to validate that no data was lost without downloading all the data. This guarantee is typically provided using data availability sampling and fraud proofs. However, fraud proofs introduce a "challenge" window, which deters the system's finality. Fraud proofs are also tricky to implement and test.
Validity Proofs for DA
An alternative to DAS and fraud proofs is to validate erasure encoding itself using SNARKs. This idea first surfaced in the Celestia forum last year.
If you created a way to generate a zk proof of correct erasure coding, then light nodes would not have to wait for a fraud proof window after sampling each block to consider it final. Second, we wouldn't need bad encoding fraud proofs (BEFPs) which require the light node to download an entire row or column of the block data. Third, this unlocks the possibility of having consensus nodes vote on blocks without downloading all the data.
originally published on the Textile blog (July 2024): https://blog.textile.io/weeknotes-xor-da-basin-server#h-data-availability-with-validity-proofs