Documentation
¶
Overview ¶
Package cmp provides methods and functions for comparing two numbers.
Index ¶
- func GetHints() []solver.Hint
- func IsLess(api frontend.API, a, b frontend.Variable) frontend.Variable
- func IsLessBinary(api frontend.API, aBits, bBits []frontend.Variable) frontend.Variable
- func IsLessOrEqual(api frontend.API, a, b frontend.Variable) frontend.Variable
- func IsLessOrEqualBinary(api frontend.API, aBits, bBits []frontend.Variable) frontend.Variable
- type BoundedComparator
- func (bc BoundedComparator) AssertIsLess(a, b frontend.Variable)
- func (bc BoundedComparator) AssertIsLessEq(a, b frontend.Variable)
- func (bc BoundedComparator) IsLess(a, b frontend.Variable) frontend.Variable
- func (bc BoundedComparator) IsLessEq(a, b frontend.Variable) frontend.Variable
- func (bc BoundedComparator) Min(a, b frontend.Variable) frontend.Variable
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GetHints ¶
GetHints returns all hint functions used in this package. This method is useful for registering all hints in the solver.
func IsLess ¶
IsLess returns 1 if a < b, and returns 0 if a >= b. a and b should be integers in range [0, P-1], where P is the order of the underlying field used by the proof system.
When inputs are not in range [0, P-1], the remainder of their division by P will be considered for comparison.
func IsLessBinary ¶
IsLessBinary compares two non-negative binary numbers represented by aBits and bBits. It returns 1 if the integer represented by aBits is less than the integer represented by bBits, and returns 0 otherwise.
func IsLessOrEqual ¶
IsLessOrEqual returns 1 if a <= b, and returns 0 if a > b. a and b should be integers in range [0, P-1], where P is the order of the underlying field used by the proof system.
When inputs are not in range [0, P-1], the remainder of their division by P will be considered for comparison.
func IsLessOrEqualBinary ¶
IsLessOrEqualBinary compares two non-negative binary numbers represented by aBits and bBits. It returns 1 if the integer represented by aBits is less than or equal to the integer represented by bBits, and returns 0 otherwise.
Types ¶
type BoundedComparator ¶
type BoundedComparator struct {
// contains filtered or unexported fields
}
BoundedComparator provides comparison methods, with relatively low circuit complexity, for signed comparison of two integers a and b, when an upper bound for their absolute difference (|a - b|) is known. These methods perform only one binary conversion of length: absDiffUppBitLen.
a and b can be any signed integers, as long as their absolute difference respects the specified bound: |a - b| <= absDiffUpp. See NewBoundedComparator, for more information.
func NewBoundedComparator ¶
func NewBoundedComparator(api frontend.API, absDiffUpp *big.Int, allowNonDeterministicBehaviour bool) *BoundedComparator
NewBoundedComparator creates a new BoundedComparator, which provides methods for comparing two numbers a and b.
absDiffUpp is the upper bound of the absolute difference of a and b, such that |a - b| <= absDiffUpp. Notice that |a - b| can be equal to absDiffUpp. absDiffUpp must be a positive number, and P - absDiffUpp - 1 must have a longer binary representation than absDiffUpp, where P is the order of the underlying field. Lower values of absDiffUpp will reduce the number of generated constraints.
This function can detect invalid values of absDiffUpp and panics when the provided value is not positive or is too big.
As long as |a - b| <= absDiffUpp, all the methods of BoundedComparator work correctly.
If |a - b| > absDiffUpp, as long as |a - b| < P - 2^absDiffUpp.BitLen(), either a proof can not be generated or the comparison methods work correctly.
When |a - b| >= P - 2^absDiffUpp.BitLen(), if allowNonDeterministicBehaviour is not set, either a proof can not be generated or the methods wrongly produce reversed results. The exact behaviour depends on the specific method and the value of |a - b|, but it will be always well-defined and deterministic.
If allowNonDeterministicBehaviour is set, when |a - b| >= P - 2^absDiffUpp.BitLen(), the generated constraint system sometimes may have multiple solutions and hence the behaviour of the exported methods of BoundedComparator will be undefined.
func (BoundedComparator) AssertIsLess ¶
func (bc BoundedComparator) AssertIsLess(a, b frontend.Variable)
AssertIsLess defines a set of constraints that can be satisfied only if a < b.
func (BoundedComparator) AssertIsLessEq ¶
func (bc BoundedComparator) AssertIsLessEq(a, b frontend.Variable)
AssertIsLessEq defines a set of constraints that can be satisfied only if a <= b.
func (BoundedComparator) IsLess ¶
func (bc BoundedComparator) IsLess(a, b frontend.Variable) frontend.Variable
IsLess returns 1 if a < b, and returns 0 if a >= b.
Example ¶
package main
import (
"fmt"
"math/big"
"github.com/consensys/gnark-crypto/ecc"
"github.com/consensys/gnark/backend/groth16"
"github.com/consensys/gnark/frontend"
"github.com/consensys/gnark/frontend/cs/r1cs"
"github.com/consensys/gnark/std/math/cmp"
)
// sortCheckerCircuit is a circuit that uses BoundedComparator.IsLess method to
// verify that an input array is sorted. We assume that the input array contains
// 16bit unsigned integers. If the input array is sorted and is ascending,
// SortingErrors will be zero, otherwise it will be nonzero and equal to the
// number of adjacent non-ascending pairs.
type sortCheckerCircuit struct {
UInt16Array [10]frontend.Variable
SortingErrors frontend.Variable
}
// Define defines the arithmetic circuit.
func (c *sortCheckerCircuit) Define(api frontend.API) error {
// constructing a 16bit comparator,
// the maximum possible difference between 16bit numbers is 2^16-1.
cmp16bit := cmp.NewBoundedComparator(api, big.NewInt(1<<16-1), false)
res := frontend.Variable(0)
for i := 0; i < len(c.UInt16Array)-1; i++ {
res = api.Add(res, cmp16bit.IsLess(c.UInt16Array[i+1], c.UInt16Array[i]))
}
api.AssertIsEqual(res, c.SortingErrors)
return nil
}
func main() {
circuit := sortCheckerCircuit{}
witness := sortCheckerCircuit{
UInt16Array: [10]frontend.Variable{0, 11, 22, 22, 33, 44, 55, 66, 77, 65535},
SortingErrors: 0, // is zero when UInt16Array is sorted and ascending.
}
ccs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
if err != nil {
panic(err)
}
pk, vk, err := groth16.Setup(ccs)
if err != nil {
panic(err)
}
secretWitness, err := frontend.NewWitness(&witness, ecc.BN254.ScalarField())
if err != nil {
panic(err)
}
publicWitness, err := secretWitness.Public()
if err != nil {
panic(err)
}
proof, err := groth16.Prove(ccs, pk, secretWitness)
if err != nil {
panic(err)
}
err = groth16.Verify(proof, vk, publicWitness)
if err != nil {
panic(err)
}
fmt.Println("done")
}
Output: done
Source Files