Categories

Circuit proof

You are here:
< All Topics

A circuit proof is a proof that a computation was performed correctly. The computation is expressed as an arithmetic circuit with multiplication and addition gates. The circuit is parameterized by a large prime p. A multiplication gate takes as input two numbers a, b in the finite field Fp and outputs c = a * b mod p. An addition gate takes as input a, b in Fp and outputs c = a + b mod p. The circuit has n public inputs and outputs and m hidden inputs. The circuit proof ensures that given the public input and outputs the prover knows m hidden inputs such that all multiplication gates are correctly computed.

 

A circuit proof can have several sub-modules, which each represent part of the circuit. A whole circuit can be a combination of these modules along with additional gates.

 

    • Range proof: A range proof can both be used as a separate proof system or as a sub-component of a larger circuit proof. The range proof circuit takes public integer inputs L and H, and a hidden integer input x. The output is 1 if Lx ≤ H and 0 otherwise.

 

    • Permutation proof: A permutation proof is a proof that two lists contain the same elements, i.e. that the lists are permutations of each other. The output list can be a shuffling of the input list or the sorted input list.

 

  • Join-split proof: A join-split proof takes n input pairs each consisting of an asset type and an amount. As an output it has m output pairs. Both the input pairs as well as the output tuples are sorted by asset type. The join-split proof module ensure that for each asset the sum of the output amounts is equal to the sum of the input amounts.

 

    • Combiner gadget: A combiner gadget takes as input two pairs each consisting of an asset type an an amount. If the types agree then the gadget outputs a pair of the type and the sum of the amounts. If not then it returns its input.

 

  • Reading in committed values: Often times it is useful to prove statements about committed values. The Bulletproof proof system enables efficient proofs on committed values without additional overhead. These values are directly fed in as private inputs to the circuit.

 

 

 

Previous Pedersen-ElGamal equality proof
Table of Contents