Struct r1cs::GadgetBuilder

pub struct GadgetBuilder<F: Field> { /* fields omitted */ }

Methods

impl<F: Field> GadgetBuilder<F>

pub fn binary_sum(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BinaryExpression<F>

Add two binary expressions in a widening manner. The result will be one bit longer than the longer of the two inputs.

pub fn binary_sum_ignoring_overflow(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BinaryExpression<F>

Add two binary expressions, ignoring any overflow.

pub fn binary_sum_asserting_no_overflow(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BinaryExpression<F>

Add two binary expressions while asserting that overflow does not occur.

pub fn binary_summation(
    &mut self,
    terms: &[BinaryExpression<F>]
) -> BinaryExpression<F>

Add an arbitrary number of binary expressions. The result will be at least one bit longer than the longest input.

pub fn binary_summation_ignoring_overflow(
    &mut self,
    terms: &[BinaryExpression<F>]
) -> BinaryExpression<F>

Add an arbitrary number of binary expressions, ignoring any overflow.

pub fn binary_summation_asserting_no_overflow(
    &mut self,
    terms: &[BinaryExpression<F>]
) -> BinaryExpression<F>

Add an arbitrary number of binary expressions, asserting that overflow does not occur.

pub fn binary_assert_zero(&mut self, x: &BinaryExpression<F>)

Assert that a binary expression is zero.

impl<F: Field> GadgetBuilder<F>

pub fn bitwise_not(&mut self, x: &BinaryExpression<F>) -> BinaryExpression<F>

The bitwise negation of a binary expression x, a.k.a. ~x.

pub fn bitwise_and(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BinaryExpression<F>

The bitwise conjunction of two binary expressions x and y, a.k.a. x & y.

pub fn bitwise_or(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BinaryExpression<F>

The bitwise disjunction of two binary expressions x and y, a.k.a. x | y.

pub fn bitwise_xor<BE1, BE2>(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BinaryExpression<F>

The bitwise exclusive disjunction of two binary expressions x and y, a.k.a. x ^ y.

pub fn bitwise_rotate_inc_significance(
    &mut self,
    x: &BinaryExpression<F>,
    n: usize
) -> BinaryExpression<F>

Rotate bits in the direction of increasing significance. This is equivalent to "left rotate" in most programming languages.

pub fn bitwise_rotate_dec_significance(
    &mut self,
    x: &BinaryExpression<F>,
    n: usize
) -> BinaryExpression<F>

Rotate bits in the direction of increasing significance. This is equivalent to "right rotate" in most programming languages.

pub fn bitwise_shift_inc_significance(
    &mut self,
    x: &BinaryExpression<F>,
    n: usize
) -> BinaryExpression<F>

Shift bits in the direction of increasing significance, discarding bits on the most significant end and inserting zeros on the least significant end. This is equivalent to "left shift" in most programming languages.

pub fn bitwise_shift_dec_significance(
    &mut self,
    x: &BinaryExpression<F>,
    n: usize
) -> BinaryExpression<F>

Shift bits in the direction of decreasing significance, discarding bits on the least significant end and inserting zeros on the most significant end. This is equivalent to "right shift" in most programming languages.

impl<F: Field> GadgetBuilder<F>

pub fn not(&mut self, x: &BooleanExpression<F>) -> BooleanExpression<F>

The negation of a boolean value.

pub fn and(
    &mut self,
    x: &BooleanExpression<F>,
    y: &BooleanExpression<F>
) -> BooleanExpression<F>

The conjunction of two boolean values.

pub fn or(
    &mut self,
    x: &BooleanExpression<F>,
    y: &BooleanExpression<F>
) -> BooleanExpression<F>

The disjunction of two boolean values.

pub fn xor(
    &mut self,
    x: &BooleanExpression<F>,
    y: &BooleanExpression<F>
) -> BooleanExpression<F>

The exclusive disjunction of two boolean values.

impl<F: Field> GadgetBuilder<F>

pub fn assert_lt(&mut self, x: &Expression<F>, y: &Expression<F>)

Assert that x < y.

pub fn assert_le(&mut self, x: &Expression<F>, y: &Expression<F>)

Assert that x <= y.

pub fn assert_gt(&mut self, x: &Expression<F>, y: &Expression<F>)

Assert that x > y.

pub fn assert_ge(&mut self, x: &Expression<F>, y: &Expression<F>)

Assert that x >= y.

pub fn assert_lt_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
)

Assert that x < y.

pub fn assert_le_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
)

Assert that x <= y.

pub fn assert_gt_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
)

Assert that x > y.

pub fn assert_ge_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
)

Assert that x >= y.

pub fn lt(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> BooleanExpression<F>

Returns x < y.

pub fn le(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> BooleanExpression<F>

Returns x <= y.

pub fn gt(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> BooleanExpression<F>

Returns x > y.

pub fn ge(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> BooleanExpression<F>

Returns x >= y.

pub fn lt_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BooleanExpression<F>

Returns x < y.

pub fn le_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BooleanExpression<F>

Returns x <= y.

pub fn gt_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BooleanExpression<F>

Returns x > y.

pub fn ge_binary(
    &mut self,
    x: &BinaryExpression<F>,
    y: &BinaryExpression<F>
) -> BooleanExpression<F>

Returns x >= y.

impl<F: Field> GadgetBuilder<F>

pub fn product(&mut self, x: &Expression<F>, y: &Expression<F>) -> Expression<F>

The product of two Expressions x and y, i.e. x * y.

pub fn exponentiation(
    &mut self,
    x: &Expression<F>,
    p: &Element<F>
) -> Expression<F>

x^p for a constant p.

pub fn inverse(&mut self, x: &Expression<F>) -> Expression<F>

Returns 1 / x, assuming x is non-zero. If x is zero, the gadget will not be satisfiable.

pub fn inverse_or_zero(&mut self, x: &Expression<F>) -> Expression<F>

Like inverse, except that zero is mapped to itself rather than being prohibited.

pub fn quotient(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> Expression<F>

Returns x / y, assuming y is non-zero. If y is zero, the gadget will not be satisfiable.

pub fn quotient_unsafe(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> Expression<F>

Returns x / y, assuming y is non-zero. This is equivalent to quotient except that it allows 0 / 0. This method will panic if it encounters 0 / 0, but a malicious prover would be able to supply an arbitrary quotient.

This method uses a single constraint, whereas quotient uses two, so this method may be preferable in cases where 0 / 0 cannot possibly arise.

pub fn modulus(&mut self, x: &Expression<F>, y: &Expression<F>) -> Expression<F>

Returns x mod y, assuming y is non-zero. If y is zero, the gadget will not be satisfiable.

pub fn divides(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> BooleanExpression<F>

Returns whether x divides y, i.e. x | y.

impl<F: Field> GadgetBuilder<F>

A utility for building Gadgets. See the readme for examples.

pub fn new() -> Self

Creates a new GadgetBuilder, starting with no constraints or generators.

pub fn wire(&mut self) -> Wire

Add a wire to the gadget. It will start with no generator and no associated constraints.

pub fn boolean_wire(&mut self) -> BooleanWire

Add a wire to the gadget, whose value is constrained to equal 0 or 1.

pub fn wires(&mut self, n: usize) -> Vec<Wire>

Add n wires to the gadget. They will start with no generator and no associated constraints.

pub fn binary_wire(&mut self, n: usize) -> BinaryWire

Add a binary wire comprised of n bits to the gadget.

pub fn generator<T>(&mut self, dependencies: Vec<Wire>, generate: T) where
    T: Fn(&mut WireValues<F>) + 'static, 

Add a generator function for setting certain wire values.

pub fn equal(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>
) -> BooleanExpression<F>

x == y

pub fn zero(&mut self, x: &Expression<F>) -> BooleanExpression<F>

x == 0

pub fn nonzero(&mut self, x: &Expression<F>) -> BooleanExpression<F>

x != 0

pub fn selection(
    &mut self,
    c: &BooleanExpression<F>,
    x: &Expression<F>,
    y: &Expression<F>
) -> Expression<F>

if c { x } else { y }. Assumes c is binary.

pub fn assert_product(
    &mut self,
    x: &Expression<F>,
    y: &Expression<F>,
    z: &Expression<F>
)

Assert that x * y = z;

pub fn assert_boolean(&mut self, x: &Expression<F>) -> BooleanExpression<F>

Assert that the given quantity is in [0, 1], and return it as a BooleanExpression.

pub fn assert_equal(&mut self, x: &Expression<F>, y: &Expression<F>)

Assert that x == y.

pub fn assert_nonequal(&mut self, x: &Expression<F>, y: &Expression<F>)

Assert that x != y.

pub fn assert_zero(&mut self, x: &Expression<F>)

Assert that x == 0.

pub fn assert_nonzero(&mut self, x: &Expression<F>)

Assert that x != 0.

pub fn assert_true(&mut self, x: &BooleanExpression<F>)

Assert that x == 1.

pub fn assert_false(&mut self, x: &BooleanExpression<F>)

Assert that x == 0.

pub fn build(self) -> Gadget<F>

Builds the gadget.

impl<F: Field> GadgetBuilder<F>

pub fn merkle_tree_root<CF>(
    &mut self,
    leaf: &Expression<F>,
    path: &MerklePath<F>,
    compress: &CF
) -> Expression<F> where
    CF: CompressionFunction<F>, 

Compute a Merkle root given a leaf value and its Merkle path.

pub fn assert_merkle_tree_membership<E1, E2, MP, CF>(
    &mut self,
    leaf: &Expression<F>,
    purported_root: &Expression<F>,
    path: &MerklePath<F>,
    compress: &CF
) where
    CF: CompressionFunction<F>, 

impl<F: Field> GadgetBuilder<F>

pub fn random_access(
    &mut self,
    items: &[Expression<F>],
    index: &Expression<F>
) -> Expression<F>

Access the ith element of items, where i may be a dynamic expression. Assumes i < items.len().

Note that this gadget returns 0 if the index is out of range. If you want to prohibit out-of-range indices, you can do so with a separate call to assert_lt.

impl<F: Field> GadgetBuilder<F>

pub fn sort_ascending(&mut self, inputs: &[Expression<F>]) -> Vec<Expression<F>>

Sorts field elements in ascending order.

pub fn sort_descending(
    &mut self,
    inputs: &[Expression<F>]
) -> Vec<Expression<F>>

Sorts field elements in descending order.

impl<F: Field> GadgetBuilder<F>

pub fn split(&mut self, x: &Expression<F>) -> BinaryExpression<F>

Split an arbitrary field element x into its canonical binary representation.

pub fn split_allowing_ambiguity(
    &mut self,
    x: &Expression<F>
) -> BinaryExpression<F>

Split an arbitrary field element x into a binary representation. Unlike split, this method permits two distinct binary decompositions: the canonical one, and another representation where the weighted sum of bits overflows the field size. This minimizes constraints, but the ambiguity can be a security problem depending on the context. If in doubt, use split instead.

pub fn split_bounded(
    &mut self,
    x: &Expression<F>,
    bits: usize
) -> BinaryExpression<F>

Split x into bits bit wires. This method assumes x < 2^bits < |F|. Note that only one binary representation is possible here, since bits bits is not enough to overflow the field size.

impl<F: Field> GadgetBuilder<F>

pub fn assert_permutation(&mut self, a: &[Expression<F>], b: &[Expression<F>])

Assert that two lists of expressions evaluate to permutations of one another.

This is currently implemented using an AS-Waksman permutation network, although that could change in the future. See "On Arbitrary Waksman Networks and their Vulnerability".