The circuit writer will go through public inputs and private inputs in the order they're defined in the noname code, then public output.
Usually the public output needs to be placed first in proof system. The kimchi backend handles these things fine, because only the add_public_input creates a gate (and only the creation of gates create a new row in the symbolic witness table). Calling new_internal_var (which add_public_input and add_private input call) does not create a new row in the (symbolic) execution trace / witness table, because we don't know at this point if we are going to using them.
In R1CS it's different, because the constraints are detached from the witness vector. So we do add the cells in the (symbolic) witness vector when we call new_internal_var. We could technically wait to see if they are used in a constraint, but the compiler is supposed to warn the user if it doesn't use a variable, and even if they did that then it should be on them to pay the cost of adding useless variables in their code (but we should still warn them!). So I propose to keep the new_internal_var behavior and to add newly created variable to the witness vector right away.
So the important thing is to make sure we process the public input/output before the private inputs.
BTW, all these names are confusing as hell! The witness_vars map in the kimchi backend is actually just a map of variable to values (i.e. how to compute each variable, even if we never use them). (It could be a vector I think, although if we use deferred operations it might be good to keep it as a map.) But in r1cs we use witness_vars to mean the symbolic witness vector! In kimchi, the symbolic witness table (coz we don't use a vector) is called rows_of_vars! We should probably change all these names...
Note: what is a symbolic witness table or vector? At proving time, we know that the witness vector will look like that: [v0, v6, v7, v10, etc.]. They're just variables at this point, we don't actually know the values because for example v0 will be a public input, v6 will be a private input, v7 will be v6 + 3 * v0, etc.
Basically they are inputs, outputs, or intermediary values of our circuits (so we don't know them yet). That's why we call them symbolic, coz they're not values, they're just symbols at this point. At runtime, then you replace the symbols with the actual values. [v0, v6, v7, v10, etc.] becomes [3, 5, 18, 3, etc.], if v0=3, and v6=5, etc.
So to summarize:
[x] in generate_circuit we'll add backend.init_circuit(&function.sig)?; right before going through the arguments
[x] in kimchi it won't do anything, but in r1cs it should add the constant 1 in witness_vars.
[x] arguments should be sorted so that add_public_input and add_public_output are called BEFORE any add_private_input
[x] this should simplify the serialization towards snarkjs, now that everything is ordered
[x] change name of witness_vars to vars_to_value in kimchi
[x] change name of rows_of_vars to witness_table in kimchi
[x] make sure to update the book which mention these variables
[x] change name of witness_vars to witness_vector in r1cs
The circuit writer will go through public inputs and private inputs in the order they're defined in the noname code, then public output.
Usually the public output needs to be placed first in proof system. The kimchi backend handles these things fine, because only the
add_public_inputcreates a gate (and only the creation of gates create a new row in the symbolic witness table). Callingnew_internal_var(which add_public_input and add_private input call) does not create a new row in the (symbolic) execution trace / witness table, because we don't know at this point if we are going to using them.In R1CS it's different, because the constraints are detached from the witness vector. So we do add the cells in the (symbolic) witness vector when we call
new_internal_var. We could technically wait to see if they are used in a constraint, but the compiler is supposed to warn the user if it doesn't use a variable, and even if they did that then it should be on them to pay the cost of adding useless variables in their code (but we should still warn them!). So I propose to keep the new_internal_var behavior and to add newly created variable to the witness vector right away.So the important thing is to make sure we process the public input/output before the private inputs.
BTW, all these names are confusing as hell! The
witness_varsmap in the kimchi backend is actually just a map of variable to values (i.e. how to compute each variable, even if we never use them). (It could be a vector I think, although if we use deferred operations it might be good to keep it as a map.) But in r1cs we usewitness_varsto mean the symbolic witness vector! In kimchi, the symbolic witness table (coz we don't use a vector) is calledrows_of_vars! We should probably change all these names...Note: what is a symbolic witness table or vector? At proving time, we know that the witness vector will look like that:
[v0, v6, v7, v10, etc.]. They're just variables at this point, we don't actually know the values because for example v0 will be a public input, v6 will be a private input, v7 will be v6 + 3 * v0, etc.Basically they are inputs, outputs, or intermediary values of our circuits (so we don't know them yet). That's why we call them symbolic, coz they're not values, they're just symbols at this point. At runtime, then you replace the symbols with the actual values. [v0, v6, v7, v10, etc.] becomes [3, 5, 18, 3, etc.], if v0=3, and v6=5, etc.
So to summarize:
backend.init_circuit(&function.sig)?;right before going through the arguments1in witness_vars.add_public_inputandadd_public_outputare called BEFORE anyadd_private_inputwitness_varstovars_to_valuein kimchirows_of_varstowitness_tablein kimchiwitness_varstowitness_vectorin r1cs