search

jancarlsson / snarklib

a C++ template library for zero knowledge proofs
Other
49 stars 11 forks source link

Remediate the soundness vulnerability described by Bryan Parno. #3

Open nathan-at-least opened 9 years ago

nathan-at-least commented 9 years ago

The input consistency polynomial defined starting at QAP_query.hpp on Line 45 apparently has the soundness vulnerability issue described in A Note on the Unsoundness of vnTinyRAM's SNARK, Bryan Parno.

libsnark suffered from the same vulnerability, and this commit fixes it.

Note, credit for identifying this vulnerability in snarklib is due to @madars. I'm merely ticketing the issue here for due diligence.

jancarlsson commented 9 years ago

Thank you for submitting the issue. It was very considerate to include a link to the technical report and source code commit. I appreciate it.

I need to read the paper and understand the issue, as well as the fix.

This is highest priority for me, of course, displacing other things.

jancarlsson commented 9 years ago

The input consistency fix is ported over from libsnark. Reproducing the vulnerability in a unit test is not straightforward in practice (as discussed in Bryan Parno's report). That makes sense but leaves me unsettled. I would like to have at least one automated unit test demonstrating the issue with the vulnerable input consistency condition.

daira commented 9 years ago

Do we have a test for this in libsnark? If not then we probably should, and then that could be ported.

jancarlsson commented 9 years ago

I didn't see a test for it. That doesn't mean it is not there. I will take a second look. I'll also read Parno's report again.

What makes testing troublesome, besides cryptography, is that this is a negative case. We wish to reproduce failure in old library code. Then we would like to demonstrate success for the same test case in the new library code which has been fixed. So we need to have a test that can work with old and new code.

At present, snarklib does this. A macro switches between pre-fix and post-fix logic. However, I don't blame the libsnark maintainers for not doing this. The binary format necessarily changed after the fix. The library has been refactored (improved, in my opinion) significantly since just a few months ago. Testing against obsolete versions of the library has to be lower priority than mainline development.

I know. Sorry for going on with too much detail you already know. I'll take a second look and think about it.

daira commented 9 years ago

Perhaps a test that the generated constraints are now linearly independent would be sufficient (for both libsnark and snarklib), even if it didn't demonstrate the old bug.