Here’s a way you could do non-interactive data availability proofs that also prevents the selective share disclosure attack, using Tor hidden services so that block producers can’t tell which sample requests came from the same users.
Registration
Suppose the user makes s samples per challenge. The user sets up s hidden services, and registers the addresses of these hidden services with different random full nodes in the network. It is important that these registrations aren’t linkable to each other, thus they could be sent over a mix net.
Proof phase
Now, suppose a new block is produced. When a full node receives a new block, it sends to each hidden service that has registered with it the sample in that block corresponding to the index seeded from H(blockHeader||hiddenServiceAddress). Note that hidden service addresses are random strings, and here we assume that blockHeader contains a random nonce that is difficult or expensive to influence by the block producer.
Because the hidden services are anonymous and - if the registration was done correctly - unlinkable with each other - this prevents malicious nodes from fooling individual clients.
This scheme has two advantages over simply sending requests over onion routing:
- You only need to worry about your requests being unlinkable to each other once (in the registration phase), rather than every time a new block comes along.
- Light clients can accept new blocks immediately, rather than having to wait for some delay so that everyone can send their requests at the same time.