search

akosba / jsnark

A Java library for zk-SNARK circuits
MIT License
207 stars 85 forks source link

LongElement multiplication without creating prover witness wires. #18

Closed antonis19 closed 4 years ago

antonis19 commented 4 years ago

Hi,

In this line: https://github.com/akosba/jsnark/blob/master/JsnarkCircuitBuilder/src/circuit/auxiliary/LongElement.java#L238

a witness wire array is created when multiplying a LongElement with another.

This has the effect of creating several secret input variables, which get put together with the real user-provided secret inputs of the circuit.

Is there a way to perform the multiplication without having these generated variables as secret or even public input ?

akosba commented 4 years ago

Hi, These additional witness wires are needed for the O(n) long integer multiplication.  Many implemented functionalities in jsnark rely on adding witnesses. For the above case specifically, an alternative method that does not require adding witnesses would be to compute the multiplication of long integers in the circuit, e.g., using the O(n^2) naive approach or using Karatsuba's O(n^1.58) multiplication if efficiency is desired.