Module pwg

This module contains methods to implement the partial witness generation (PWG) of an ACIR program. The goal of ACIR execution is to compute the values of all the ACIR witnesses, or an error if it could not compute them all. A proving system will then be able to use the ACIR circuit and the values of the ACIR witnesses to generate a proof of this execution. The ACIR opcodes are not modified by the execution. Witness generation means getting valid values for the witnesses used by the ACIR opcodes of the program. They are called partial witness because a proving system may create additional witnesses on its own for generating the proof (and a corresponding low-level circuit). The PWG generates values for all the witnesses of the ACIR program, or returns an error if it cannot do it.

Implementation details & examples: It starts by instantiating an ACVM (ACIR Virtual Machine), which executes the given ACIR opcodes in the solve() function.

Parameters: When instantiating the ACVM, it needs to be provided with:

• a backend implementing the BlackBoxFunctionSolver trait. Different implementation can be used depending on the EC used by the underlying proving system.
• opcodes: the ACIR opcodes of the program to solve.
• initial_witness: a mapping of initial witness values representing the inputs of the program. The ACVM will update this map as it solves the opcodes.
• unconstrained_functions: the Brillig bytecode of the unconstrained functions used by the program.
• assertion_payloads: additional information used to provide feedback to the user when an assertion fails.

Returns: ACVMStatus

Each opcode is solved independently. In general we require its inputs to be already known, i.e previously solved, and the output is simply computed from the inputs, and then the output becomes ‘known’ for the subsequent opcodes.

See acir::circuit::Opcode for more details.

Example:

This ACIR program defines the ‘main’ function and indicates it is ‘non-transformed’. Indeed, some ACIR pass can transform the ACIR program in order to apply optimizations, or to make it compatible with a specific proving system. However, ACIR execution is expected to work on any ACIR program (transformed or not). Then we see the parameters of the program as public and private inputs. The initial_witness needs to contain values for these parameters before execution, else the execution will fail. The first ACIR opcodes are RANGE opcodes which ensure the inputs have the expected range (as specified in the Noir source code). Solving this black-box simply means to validate that the values (from initial_witness) are indeed 32 bits for w0, w1, w2, w3, w4 If initial_witness does not have values for w0, w1, w2, w3, w4, or if the values are over 32 bits, the execution will fail. The next opcode is an AssertZero opcode: ASSERT w0 - w1 - w6 = 0, which indicates that w0 - w1 - w6 should be equal to 0. Since we know the values of w0, w1 from initial_witness, we can compute w6 = w0 + w1 so that the AssertZero is satisfied. Solving AssertZero means computing the unknown witness and adding the result to initial_witness, which now contains the value for w6. The next opcode is a Brillig Call where input is w6 and output is w7. From the function id of the opcode, the solver will retrieve the corresponding Brillig bytecode and instantiate a Brillig VM with the value of the input. This value was just computed before. Executing the Brillig VM on this input will give us the output which is the value for w7, that we add to initial_witness. The next opcode is again an AssertZero: w6 * w7 + w8 - 1 = 0, which computes the value of w8. The two next opcodes are AssertZero without any unknown witnesses: w6 * w8 = 0 and w1 * w8 = 0 Solving such opcodes means that we compute w6 * w8 and w1 * w8 using the known values, and check that they evaluate to 0. If not, we would return an error. Finally, the last AssertZero computes w9 which is the last witness. All of the witnesses have now been computed; execution is complete.

Modules

• arithmetic 🔒
• blackbox 🔒
• brillig 🔒
• memory_op 🔒

Structs

• ACVM
• AcirCallWaitInfo
  Encapsulates a request from the ACVM that encounters an ACIR call opcode where the result of the circuit execution has not yet been provided.
• BrilligSolver
  Specific solver for Brillig opcodes It maintains a Brillig VM that can execute the bytecode of the called brillig function
• ForeignCallWaitInfo
  Encapsulates a request from a Brillig VM process that encounters a foreign call opcode where the result of the foreign call has not yet been provided.
• ProfilingSample
• RawAssertionPayload
  A dynamic assertion payload whose data has been resolved. This is instantiated upon hitting an assertion failure.

Enums

• ACVMStatus
• BrilligSolverStatus
• ErrorLocation
  Used by errors to point to a specific opcode as that error’s cause
• OpcodeNotSolvable
• OpcodeResolutionError
• ResolvedAssertionPayload
  Enumeration of possible resolved assertion payloads. This is instantiated upon hitting an assertion failure, and can either be static strings or dynamic payloads.
• StepResult

Functions

• any_witness_from_expression 🔒
• check_bit_size
• get_value
  Returns the concrete value for a particular expression If the value cannot be computed, it returns an ‘OpcodeNotSolvable’ error.
• input_to_value
• insert_value
  Inserts value into the initial witness map under the index witness.
• is_predicate_false 🔒
  Returns Ok(true) if the predicate is zero A predicate is used to indicate whether we should skip a certain operation. If we have a zero predicate it means the operation should be skipped.
• witness_to_value

Type Aliases

• ProfilingSamples