zks

package module
v0.0.0-...-1ecdfbc Latest Latest
Warning

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

Go to latest
Published: Feb 26, 2025 License: MIT Imports: 6 Imported by: 0

README

ZKS

We provide an implementation of Zero-Knowledge Sets (ZKS) first introduced by Micali, Rabin, and Kilian [MRK03]. We base our construction off the one described in Mercurial Commitments with Applications to Zero-Knowledge Sets by Chase et al. [CHLMR05].

API

Enum Sets

The data stored in a ZKS must be stored as an enumerated set. That is, items need to be stored in a map that maps integers (up to some max value) to a boolean value indicating set-membership.

For instance one can create a set with maximally 10 values as such:

	values := map[uint64]bool{
		0:  true,
		1:  false,
		2:  false,
		3:  true,
		4:  true,
		5:  true,
		6:  false,
		7:  false,
		8:  false,
		9:  false,
    }

    set := NewEnumSet(values, 10)

One can also create this set dynamically by creating an empty EnumSet and using the Add and Remove functions. The In function answers a set-membership query. If the queried value is not explicitly stored in the map or is beyond the maximum value then false is returned.

ZKS
  • Gen() generates the public parameters for a ZKS (a selection of a verification key and a PRF).
  • Rep(pp,es) takes as input the public parameters and an enumerated set. It outputs the ZKS representation and commitment to this representation.
  • Qry(pp,repr,x) takes as input the public parameters, the ZKS representation, and the element x being queried. It outputs the set-membership response and a proof to this response in a single answer struct.
  • Vfy(pp,com,x,answer) takes as input the public parameters, the commitment to the ZKS representation, the element x being queried, the answer/proof struct to a query on x. It outputs a boolean value indicating if the answer is valid.

Installing and Using

To install the ZKS package:

go get -u github.com/smarky7CD/ZKS

The package can be imported and used as such:

import(
    "fmt"
    "github.com/smarky7cd/ZKS"
)

func ZKSexample() {

	values := map[uint64]bool{
		0:  true,
		1:  false,
		2:  false,
		3:  true,
		4:  true,
		5:  true,
		6:  false,
		7:  false,
		8:  false,
		9:  false,
		10: true,
		11: true,
		12: true,
		13: true,
		14: true,
		15: true,
	}

	set := NewEnumSet(values, 16)

	pp := Gen()

	repr, com := Rep(pp, set)

	for i := uint64(0); i < 16; i++ {
		a := Qry(pp, repr, i)
        fmt.Println("Value ",i, " is: ", a.answer)
		v := Vfy(pp, com, i, a)
		fmt.Println("Answer is verified: ", v)
	}

}

Tests

We provide a number of correctness tests and a comprehensive performance evaluation.

They can be ran by using:

go test -v -timeout 5m

The performance tests will create a .csv file reporting the mean time and the variance for all operations for various set and universe sizes over 10 trials for each parameter set. The performance test may take a bit of time to run.

References

  • [MRK03]: Micali, Silvio, Michael Rabin, and Joe Kilian. "Zero-knowledge sets." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.
  • [CHLMR05]: Chase, Melissa, et al. "Mercurial commitments with applications to zero-knowledge sets." Advances in Cryptology–EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Proceedings 24. Springer Berlin Heidelberg, 2005.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ComputeLayer

func ComputeLayer(pp *PubVerPar, level uint64, prev_layer_nodes map[uint64]*TreeNode) map[uint64]*TreeNode

Computes the non-leaf layers of the tree representation.

func ComputeLeaves

func ComputeLeaves(pp *PubVerPar, es *EnumSet, level uint64) map[uint64]*TreeNode

Computes the leaves of the tree.

func ComputeNearestPowerof2

func ComputeNearestPowerof2(n uint64) uint64

Computes the next highest power of 2 on input n.

func Rep

func Rep(pp *PubVerPar, es *EnumSet) (*Repr, Com)

Input: public parameters (h,ps) and an EnumSet. Return: ZKS representation and a commitment to it.

func VerifyOpen

func VerifyOpen(pp *PubVerPar, com Com, x uint64, answer *Answer) bool

Verifies a hard commitment path.

func VerifyPath

func VerifyPath(pp *PubVerPar, com Com, x uint64, answer *Answer) bool

Verifies an authentication path for element x. Calls either VerifyOpen or VerifyTease.

func VerifyTease

func VerifyTease(com Com, x uint64, answer *Answer) bool

Verifies a soft commitment path.

func Vfy

func Vfy(pp *PubVerPar, com Com, x uint64, answer *Answer) bool

Input: The public parameters (h,ps), a ZKS commitment, an element x that was queried, and the answer/proof struct. Return: True if answer verifies, false otherwise.

Types

type Answer

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

An answer contains the boolean set-membership reply and information used in the proof.

func MemberPath

func MemberPath(tree *Tree, pp *PubVerPar, x uint64) *Answer

Computes an authentication path in the tree for an element in the set.

func NonMemberPath

func NonMemberPath(tree *Tree, pp *PubVerPar, x uint64) *Answer

Computes an authentication path in the tree for an element not in the set.

func Qry

func Qry(pp *PubVerPar, repr *Repr, x uint64) *Answer

Input: The public parameters (h,ps), a ZKS representation, and an element x. Return: Answer struct containing set-membership response and a proof.

type Com

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

A commitment is two points on the EC.

type EnumSet

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

An enumerated set.

Values in the set are integers and the boolean value they map to indicates set membership. True indicates membership and false indicates non-membership. The max value is the maximum value of the set. Any value not explicitly in the set or greater than the maximum value will return false.

func NewEnumSet

func NewEnumSet(set map[uint64]bool, max uint64) *EnumSet

Takes in (a possibly empty) integer to bool map and a maximum value. Returns a new EnumSet structure.

func (*EnumSet) Add

func (es *EnumSet) Add(x uint64)

Add a value x to the EnumSet if it is less than the maximum value.

func (*EnumSet) In

func (es *EnumSet) In(x uint64) bool

Respond true if x is in the Enum Set. Respond false if x is not in the Enum Set.

func (*EnumSet) Remove

func (es *EnumSet) Remove(x uint64)

Remove a value x from the EnumSet if its less than the maximum value.

type Open

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

Information to open a commitment.

type PubVerPar

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

h is the randomly selected point on the EC used for the commitment scheme ps is the randomly selected PRF

func Gen

func Gen() *PubVerPar

Generate h (value used for commitments) and *ps (the PRF).

type Repr

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

A ZKS representation is the tree and the underlying EnumSet.

type Tease

type Tease = ristretto.Scalar

Information to tease a commitment.

type Tree

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

Tree is the internal ZKS representation. root is the commitment to the ZKS. tree is a nested map of nodes -- one map per level. levels is the depth of the tree.

func NewTree

func NewTree(pp *PubVerPar, es *EnumSet) *Tree

Creates a new tree given an EnumSet. Calls ComputeLeaves and ComputeLayers.

func (*Tree) Path

func (tree *Tree) Path(pp *PubVerPar, x uint64, a bool) *Answer

Computes an authentication path for element x. Calls either MemberPath or NonMemberPath.

type TreeNode

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

soft indicates whether the nodes is a hard or soft commitment. c0,c1 is the commitment to the node. r0,r1 random scalars used to (could instead be computed on the fly).

func NewNode

func NewNode(soft bool, c0 ristretto.Point, c1 ristretto.Point, r0 ristretto.Scalar, r1 ristretto.Scalar) *TreeNode

Generate a new tree node

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL