Speed up JoinSplit proving by running is_satisfied() only if verification fails

[tromer]

Creating a JoinSplit currently spends about 1 second merely doing an is_satisfied() sanity check on the witness.

VTune analysis of CreateJoinSplit:

The implementation of r1cs_constraint_system<FieldT>::is_satisfied() (in libsnark's r1cs.tcc) is single-threaded, and can be easily parallelized to reduce the wallclock time.

Alternatively, the call can be removed, relying just on the eventual verification (when entering the local mempool?) as a sanity check.

[ebfull]

Concept ACK.

I like the approach of removing the call; it is (theoretically) not possible to use the API to construct an invalid proof, and we have tests for all the known cases in which the constraint system would be violated. It's an assertion that is done inside of JoinSplitCircuit::prove() -- feel free to open a PR that removes this call.

[daira]

NACK to removing the call, at least for now. Actually, let's not try to optimise it either until we have fixed the bug(s) mentioned below.

We left this check deliberately to get better diagnostics for cases where the constraint system is not satisfied (and also, to get those diagnostics by an assertion on the node where the actual problem is, not when the proof is verified by other nodes). In fact we only recently improved that error reporting, in #1752, because we have at least one bug that causes is_satisfied to fail (#1668, which had been incorrectly closed). It's too early to remove this just for a 1-second speedup.

[tromer]

Agreed about removing, but why not parallelize?

[ebfull]

I don't personally believe there is much purpose to the assertion anymore.

[daira]

@tromer: because we might accidentally break it, and that's a disruptive thing to do while we still have bugs that fail the check.

@ebfull: I'll be happy to remove it when we're confident that it can't actually fail, but that is not the case now, and the diagnostics produced by #1752 in the meantime could be useful.

[daira]

Oh, I hadn't seen that #1752 is intended to make this check redundant. Hmm. On reflection I still think we should wait until we've resolved #1668.

[ebfull]

We have no reason to believe there are any outstanding bugs with the diagnostics. #1668 was filed before any diagnostics were added. There were bugs in the wallet which would trigger the assertion. In order to find them, we improved the diagnostics and closed that ticket. We eventually did find and fix them.

The assertion, to my knowledge, has not been triggered by users since #1797 was merged.

[tromer]

How about running the SNARK verifier on the proof, locally, while the R1CS is still instantiated, and if that fails, running is_satisfiable()?

Since the SNARK verifier is much faster, that gives the best of both worlds (assuming soundness, and if soundness is violated, then diagnostics of bad witness on honest nodes is the least of our concerns.)

[daira]

I like @tromer's idea.

[daira]

Does anyone have any objection to @tromer's idea? I think it achieves the best of both worlds (performance and good diagnostics). It's also what we recommend doing in https://z.cash/blog/pay-to-sudoku-revisited.html , BTW ("As an additional precaution, verify the proof after you construct it!").

It should be orthogonal to Sapling.

[ebfull]

@daira I don't object.

[daira]

I'll file a PR for this on top of #2243 #2670.

[str4d]

We never found time to do this, and with Sapling activation in three weeks, we won't be using the libsnark prover for much longer (and certainly not by the time the next release happens). So there's no longer a benefit to implementing this (beyond slightly speeding up tests, but we will be migrating those to use hybrid Sprout proofs instead at some point).