Skip to content
This repository has been archived by the owner on Oct 31, 2023. It is now read-only.

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

Closed
arielgabizon opened this issue Aug 6, 2019 · 3 comments
Assignees

Comments

@arielgabizon
Copy link

arielgabizon commented Aug 6, 2019

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
Copy link
Contributor

nicola commented Aug 8, 2019

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?)

@nicola nicola changed the title Does malleability need to be addressed? Should we switch to an SE-SNARK? MALLSNARK: Does malleability need to be addressed? Should we switch to an SE-SNARK? Aug 8, 2019
@arielgabizon
Copy link
Author

arielgabizon commented Aug 9, 2019

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
Copy link
Contributor

nicola commented Aug 20, 2019

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

@nicola nicola closed this as completed Aug 20, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants