logderivlookup

Documentation

Overview

Package logderiv implements append-only lookups using log-derivative argument.

The lookup is based on log-derivative argument as described in logderivarg. The lookup table is a matrix where first column is the index and the second column the stored values:

1 x_1
2 x_2
...
n x_n

When performing a query for index i, the prover returns x_i from memory and stores (i, x_i) as a query. During the log-derivative argument building we check that all queried tuples (i, x_i) are included in the table.

The complexity of the lookups is linear in the size of the table and the number of queries (O(n+m)).

Example

package main

import (
	"crypto/rand"
	"fmt"
	"math/big"

	"github.com/airchains-network/gnark/backend/groth16"
	"github.com/airchains-network/gnark/frontend"
	"github.com/airchains-network/gnark/frontend/cs/r1cs"
	"github.com/airchains-network/gnark/std/lookup/logderivlookup"
	"github.com/consensys/gnark-crypto/ecc"
)

type LookupCircuit struct {
	Entries           [1000]frontend.Variable
	Queries, Expected [100]frontend.Variable
}

func (c *LookupCircuit) Define(api frontend.API) error {
	t := logderivlookup.New(api)
	for i := range c.Entries {
		t.Insert(c.Entries[i])
	}
	results := t.Lookup(c.Queries[:]...)
	if len(results) != len(c.Expected) {
		return fmt.Errorf("length mismatch")
	}
	for i := range results {
		api.AssertIsEqual(results[i], c.Expected[i])
	}
	return nil
}

func main() {
	field := ecc.BN254.ScalarField()
	witness := LookupCircuit{}
	bound := big.NewInt(int64(len(witness.Entries)))
	for i := range witness.Entries {
		witness.Entries[i], _ = rand.Int(rand.Reader, field)
	}
	for i := range witness.Queries {
		q, _ := rand.Int(rand.Reader, bound)
		witness.Queries[i] = q
		witness.Expected[i] = new(big.Int).Set(witness.Entries[q.Int64()].(*big.Int))
	}
	ccs, err := frontend.Compile(field, r1cs.NewBuilder, &LookupCircuit{})
	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

Index

• type Table
  • func New(api frontend.API) *Table
  • func (t *Table) Insert(val frontend.Variable) (index int)
  • func (t *Table) Lookup(inds ...frontend.Variable) (vals []frontend.Variable)

Examples

• Package

Types

type Table

type Table struct {
	// contains filtered or unexported fields
}

Table holds all the entries and queries.

func New

func New(api frontend.API) *Table

New returns a new *Table. It additionally defers building the log-derivative argument.

func (*Table) Insert

func (t *Table) Insert(val frontend.Variable) (index int)

Insert inserts variable val into the lookup table and returns its index as a constant. It panics if the table is already committed.

func (*Table) Lookup

func (t *Table) Lookup(inds ...frontend.Variable) (vals []frontend.Variable)

Lookup lookups up values from the lookup tables given by the indices inds. It returns a variable for every index. It panics during compile time when looking up from a committed or empty table. It panics during solving time when the index is out of bounds.