search

arkworks-rs / groth16

A Rust implementation of the Groth16 zkSNARK
https://www.arkworks.rs
Apache License 2.0
242 stars 97 forks source link

Is inline_all_lcs() a must during proving/setup? #33

Closed brucechin closed 2 years ago

brucechin commented 3 years ago

I recently read the DIZK codebase https://github.com/scipr-lab/dizk, where I did not find the proving process contains things like inline_all_lcs(). Previously I found that the inline_all_lcs() is serially executed and could take up a lot of time in the total proving time. I think that the inline_all_lcs()'s worst-case time complexity could be O(n^2) where n is the number of linear combinations, and this really hurts large circuit performance.

https://github.com/arkworks-rs/snark/blob/e0e29bfcbd88ba703aec58d8561db894f602439d/relations/src/r1cs/constraint_system.rs#L309:12

weikengchen commented 3 years ago

Just looking at the code and found that there is one possibility that that LC map will blow up.

So, one question: in your use case where the LC map becomes huge, are there a lot of matrix operations? I may have an idea how to cut the cost significantly.

weikengchen commented 3 years ago

In most cases inline_all_lcs would be fine, but I agree that there seem some common operations that inline_all_lcs is not doing the right amount of work...

brucechin commented 3 years ago

Sorry about late reply, github does not give me a notification on this thread. Yes, there are a lot of matrix multiplications.

weikengchen commented 2 years ago

I will close this one for now. And we will work on the solution on Sum trait.