Struct SubsetSum 

pub struct SubsetSum { /* private fields */ }

“Subset Sum” is the following “knowledge” problem:

• Given a list of non-negative integers and a target value, do you know a sublist which sums exactly to the target value?

The circuit has the full list and the target value as public inputs, and the selected sublist as a private input. It checks that that the sublist sums to the target value.

Implementations

impl SubsetSum

pub fn construct_circuit(builder: &mut CircuitBuilder, len: usize) -> Self

This constructs the circuit in builder and stores some of the wires in a SubsetSum struct, which is then returned. The wires are stored so that they can be populated with values later.

pub fn populate_problem( &self, filler: &mut WitnessFiller<'_>, values: &[u64], target: u64, )

This populates the public wires which define the subset sum problem.

• values is the list of integers available
• target is the target value that a sublist should sum to

pub fn populate_solution( &self, filler: &mut WitnessFiller<'_>, selection: &[bool], )

This populates the private wires which select a sublist which is claimed to sum to the target value.

• selection should have the same length as the original list, and should contain true for every number that should be included in the sublist