search

filecoin-project / research

Home for Filecoin Research
Other
74 stars 10 forks source link

MALLSNARK: Does malleability need to be addressed? Should we switch to an SE-SNARK? #143

Closed arielgabizon closed 5 years ago

arielgabizon commented 5 years ago

tl;dr - my answer to the above questions is no.

The potential problem: Someone submits a PoRep to the network for a certain replica-id You want to conclude it implies they have the replica stored. However, since the Groth-16 SNARK is only knowledge sound and not simulation-extractable, it only implies that the "joint party" consisting of everybody that ever submitted information to the chain jointly has this replica.

Things like this are a huge problem in the Zcash context: You want someone to spend a note only when they themselves know its private key.

The way this can be solved is either with an SE-SNARK like Groth-Maller 17 or Bowe-Gabizon18 (used now by Coda) or - as was done in zcash/zerocash - "baking in" the secret key of the replicator in the statement that needs to be proven, such that only someone knowing this secret key could've made the proof.

However I claim in the Filecoin context it doesn't really matter. We just care that all replicas with verifying PoReps are stored somewhere, we don't care who is storing what part of it.

@nicola

nicola commented 5 years ago

Question: can a miner with a different miner ID generate a proof for some data that someone else is storing? (breaking the space-hardness property of filecoin?)

arielgabizon commented 5 years ago

Question: can a miner with a different miner ID generate a proof for some data that someone else is storing? (breaking the space-hardness property of filecoin?)

If I understand your questions correctly: someone is storing a replica of data D with repID r, can you generate a proof for data D and repID r' different from r, when nobody is storing a replica of D with repID r'

(sidenote:seems cleaner to include comm(D) in the repID and then the repID is unique and binds the data) The answer is no. To make a proof for a certain comm(D) and repID, the replica needs to be stored in the network.

What is true with KS, is that in a sense you can't say the prover is storing the replica himself, but just that it's stored somewhere in the network.

How this manifests formally is that you'll say something like, whenever someone makes a proof there's an extractor that output the replica

but with KS the extractor needs to depend on the state of all participants in the system, and with SE the extractor only needs to depend on the state of the current prover.

So, again, that can be interpreted as saying "we only know the replica is stored, not that the prover stores it by himself"

But I think that's fine cause you still have the guarantee that I get mining power according to how much space is allocated to replicas matching my minerID only

nicola commented 5 years ago

If someone made a proof of a certain replicaId, then this replica must exist on some hard disks.