Trait sunscreen_zkp_backend::Gadget

pub trait Gadget: Any + Send + Sync {
    // Required methods
    fn gen_circuit(
        &self,
        gadget_inputs: &[NodeIndex],
        hidden_inputs: &[NodeIndex]
    ) -> Vec<NodeIndex>;
    fn compute_hidden_inputs(
        &self,
        gadget_inputs: &[BigInt]
    ) -> Result<Vec<BigInt>>;
    fn gadget_input_count(&self) -> usize;
    fn hidden_input_count(&self) -> usize;

    // Provided method
    fn debug_name(&self) -> &'static str { ... }
}

In ZKP circuits, it’s often simpler for the prover to provide additional inputs and prove they meet some criteria than to directly compute some quantity. However, something must compute these additional inputs. Rather than delegate this responsibility to the prover’s application, we use Gadgets.

Gadgets bear some resemblance to a function call in programming languages. They take N input values and compute M output values. These outputs get assigned to the additional inputs. In addition to computing these values, the Gadget describes the circuit to prove the hidden inputs satisfy some constraints.

Remarks

Gadget methods seem to accept a superfluous &self argument. This serves to ensure the trait is object-safe. Although legal, implementors generally won’t have data.

The Gadget::gadget_input_count method is not marked as const to maintain object-safety, but implementors should ensure the values these functions return is always the same for a given gadget type.

Example

Suppose we want to decompose a native field element x into 8-bit unsigned binary. Directly computing this with e.g. Lagrange interpolation is cost prohibitive because x lives in a very large field (e.g. Bulletproofs Scalar values are O(2^255)).

We instead ask the prover to simply provide the binary decomposition and prove that it’s correct. To do this, we create a gadget. Its compute_hidden_inputs method directly computes the decomposition with shifting and masking. Then, the gen_circuit method defined a circuit that proves the following:

• Each hidden input is a 0 or 1
• x == 2^7 * b_7 + 2^6 * b_6 … 2^0 * b_0

and outputs (b_0..b_7)

Required Methods

fn gen_circuit( &self, gadget_inputs: &[NodeIndex], hidden_inputs: &[NodeIndex] ) -> Vec<NodeIndex>

Create the subcircuit for this gadget.

• gadget_inputs are the node indices of the gadget inputs.
• hidden_inputs are the nodes of the gadget’s hidden inputs.

Returns the node indices of the gadget outputs.

Remarks

gadget_inputs.len() is guaranteed to equal self.get_gadget_input_count().

hidden_inputs.len() is guaranteed to equal self.get_hidden_input_count()

fn compute_hidden_inputs(&self, gadget_inputs: &[BigInt]) -> Result<Vec<BigInt>>

Compute the values for each of the hidden inputs from the given gadget inputs.

• Remarks

The number of returned hidden input values must equal hidden_input_count.

Implementors should ensure this function runs in constant time.

fn gadget_input_count(&self) -> usize

Returns the expected number of gadget inputs.

fn hidden_input_count(&self) -> usize

Returns the expected number of hidden inputs.

Provided Methods

fn debug_name(&self) -> &'static str

The gadget’s name used to implement Operation’s Debug trait.

Implementors