selector

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 8, 2024 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Overview

Package selector provides a lookup table and map, based on linear scan.

The native frontend.API provides 1- and 2-bit lookups through the interface methods Select and Lookup2. This package extends the lookups to arbitrary-sized vectors. The lookups can be performed using the index of the elements (function Mux) or using a key, for which the user needs to provide the slice of keys (function Map).

The implementation uses linear scan over all inputs.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func BinaryMux 

func BinaryMux(api frontend.API, selBits, inputs []frontend.Variable) frontend.Variable

BinaryMux is a 2^k to 1 multiplexer which uses a binary selector. selBits are the selector bits, and the input at the index equal to the binary number represented by the selector bits will be selected. More precisely the output will be: 

inputs[selBits[0]+selBits[1]*(1<<1)+selBits[2]*(1<<2)+...]

len(inputs) must be 2^len(selBits).

func Decoder 

func Decoder(api frontend.API, n int, sel frontend.Variable) []frontend.Variable

Decoder is a decoder with n outputs. It outputs 1 on the wire with index sel, and 0 otherwise. Indices start from zero. In other words: 

if i == sel
    out[i] = 1
else
    out[i] = 0

sel needs to be between 0 and n - 1 (inclusive) otherwise no proof can be generated.

func GetHints 

func GetHints() []solver.Hint

GetHints returns all hint functions used in this package. This method is useful for registering all hints in the solver.

func KeyDecoder 

func KeyDecoder(api frontend.API, queryKey frontend.Variable, keys []frontend.Variable) []frontend.Variable

KeyDecoder is a decoder that associates keys to its output wires. It outputs 1 on the wire that is associated to a key that equals to queryKey. In other words: 

if keys[i] == queryKey
    out[i] = 1
else
    out[i] = 0

If keys has more than one key that equals to queryKey, the output is undefined. However, the output is guaranteed to be zero for the wires that are associated with a key which is not equal to queryKey.

func Map 

func Map(api frontend.API, queryKey frontend.Variable,
	keys []frontend.Variable, values []frontend.Variable) frontend.Variable

Map is a key value associative array: the output will be values[i] such that keys[i] == queryKey. If keys does not contain queryKey, no proofs can be generated. If keys has more than one key that equals to queryKey, the output will be undefined, and the output could be any linear combination of all the corresponding values with that queryKey.

In case keys and values do not have the same length, this function will panic.

Example

ExampleMap gives an example on how to use map selector. 

package main

import (
	"fmt"

	"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/selector"
)

// MapCircuit is a minimal circuit using a selector map.
type MapCircuit struct {
	QueryKey      frontend.Variable
	Keys          [10]frontend.Variable // we use array in witness to allocate sufficiently sized vector
	Values        [10]frontend.Variable // we use array in witness to allocate sufficiently sized vector
	ExpectedValue frontend.Variable
}

// Define defines the arithmetic circuit.
func (c *MapCircuit) Define(api frontend.API) error {
	result := selector.Map(api, c.QueryKey, c.Keys[:], c.Values[:])
	api.AssertIsEqual(result, c.ExpectedValue)
	return nil
}

// ExampleMap gives an example on how to use map selector.
func main() {
	circuit := MapCircuit{}
	witness := MapCircuit{
		QueryKey:      55,
		Keys:          [10]frontend.Variable{0, 11, 22, 33, 44, 55, 66, 77, 88, 99},
		Values:        [10]frontend.Variable{0, 2, 4, 6, 8, 10, 12, 14, 16, 18},
		ExpectedValue: 10, // element in values which corresponds to the position of 55 in keys
	}
	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

func Mux 

func Mux(api frontend.API, sel frontend.Variable, inputs ...frontend.Variable) frontend.Variable

Mux is an n to 1 multiplexer: out = inputs[sel]. In other words, it selects exactly one of its inputs based on sel. The index of inputs starts from zero.

sel needs to be between 0 and n - 1 (inclusive), where n is the number of inputs, otherwise the proof will fail.

Example

ExampleMux gives an example on how to use mux selector. 

package main

import (
	"fmt"

	"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/selector"
)

// MuxCircuit is a minimal circuit using a selector mux.
type MuxCircuit struct {
	Selector frontend.Variable
	In       [10]frontend.Variable // we use array in witness to allocate sufficiently sized vector
	Expected frontend.Variable
}

// Define defines the arithmetic circuit.
func (c *MuxCircuit) Define(api frontend.API) error {
	result := selector.Mux(api, c.Selector, c.In[:]...) // Note Mux takes var-arg input, need to expand the input vector
	api.AssertIsEqual(result, c.Expected)
	return nil
}

// ExampleMux gives an example on how to use mux selector.
func main() {
	circuit := MuxCircuit{}
	witness := MuxCircuit{
		Selector: 5,
		In:       [10]frontend.Variable{0, 2, 4, 6, 8, 10, 12, 14, 16, 18},
		Expected: 10, // 5-th element in vector
	}
	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

func Partition 

func Partition(api frontend.API, pivotPosition frontend.Variable, rightSide bool,
	input []frontend.Variable) (out []frontend.Variable)

Partition selects left or right side of the input array, with respect to the pivotPosition. More precisely when rightSide is false, for each i we have: 

if i < pivotPosition
    out[i] = input[i]
else
    out[i] = 0

and when rightSide is true, for each i we have: 

if i >= pivotPosition
    out[i] = input[i]
else
    out[i] = 0

We must have pivotPosition >= 0 and pivotPosition <= len(input), otherwise a proof cannot be generated.

Example

ExamplePartition gives an example on how to use selector.Partition to make a circuit that accepts a Count and an input array In, and then calculates the sum of first Count numbers of the input array. 

package main

import (
	"fmt"

	"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/selector"
)

// adderCircuit adds first Count number of its input array In.
type adderCircuit struct {
	Count       frontend.Variable
	In          [10]frontend.Variable
	ExpectedSum frontend.Variable
}

// Define defines the arithmetic circuit.
func (c *adderCircuit) Define(api frontend.API) error {
	selectedPart := selector.Partition(api, c.Count, false, c.In[:])
	sum := api.Add(selectedPart[0], selectedPart[1], selectedPart[2:]...)
	api.AssertIsEqual(sum, c.ExpectedSum)
	return nil
}

// ExamplePartition gives an example on how to use selector.Partition to make a circuit that accepts a Count and an
// input array In, and then calculates the sum of first Count numbers of the input array.
func main() {
	circuit := adderCircuit{}
	witness := adderCircuit{
		Count:       6,
		In:          [10]frontend.Variable{0, 2, 4, 6, 8, 10, 12, 14, 16, 18},
		ExpectedSum: 30,
	}
	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

func Slice 

func Slice(api frontend.API, start, end frontend.Variable, input []frontend.Variable) []frontend.Variable

Slice selects a slice of the input array at indices [start, end), and zeroes the array at other indices. More precisely, for each i we have: 

if i >= start and i < end
    out[i] = input[i]
else
    out[i] = 0

We must have start >= 0 and end <= len(input), otherwise a proof cannot be generated.

Types

This section is empty.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.