templates package

Module containing the templates for the sigma-protocol zero-knowledge proofs.

class templates.BaseSigmaProtocol(homomorphism, image_to_prove, commitment, response, hash_algorithm)

Bases: Generic[InputElementT, HomomorphismOutputT, ChallengeT, ResponseT, HomomorphismT]

Abstract class defining the methods provided by a sigma protocol.

__init__(homomorphism, image_to_prove, commitment, response, hash_algorithm)

Create a Sigma Protocol instantiation. The instantiation contains all elements needed for verification. To generate a proof of knowledge see the method generate_proof.

Parameters:

• homomorphism (TypeVar(HomomorphismT, bound= Homomorphism[Any, Any, Any])) – Homomorphism which is used for the evaluation.

• image_to_prove (TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)) – The image created by applying the homomorphism on the secret input.

• commitment (TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)) – Evaluation of $psi(r)$, where $r$ is the random input used during proof generation.

• response (TypeVar(ResponseT, bound= HomomorphismInput[Any])) – The response $z$.

• hash_algorithm (str) – The hash algorithm used to generate the challenge from the hashlib library.

property commitment: HomomorphismOutputT

The commitment from the prover to a random vector $r$. The commitment is represented as

variable $A$ in the basic sigma protocol.

Returns:

Evaluation of $psi(r)$, where $r$ is the random input used during proof generation.

property hash_algorithm: str

Hash algorithm used for the Fiat-Shamir transformation. The Fiat-Shamir transformation makes the proof non-interactive.

The choice of the hash algorithm determines the number of bytes, which are available to generate a challenge.

Returns:

A string with the name of the hash algorithm

property homomorphism: HomomorphismT

The homomorphism function used in this sigma protocol

Returns:

Homomorphism corresponding to this sigma protocol

property image_to_prove: HomomorphismOutputT

Evaluation of the input by the homomorphism. This evaluation results in the input $P$ for the sigma protocol.

Returns:

A homomorphism output representing $psi(x)$, where x is the input vector and $psi$ the homomorphism.

property response: ResponseT

Response of the prover, which is used to verify the proof of knowledge. This corresponds to the variable $z$ of the sigma protocol. The evaluation of $z$ by the homomorphism is used to verify the proof of knowledge.

In the basic sigma protocol the response corresponds to $z= r + cx$, where $r$ is a vector of random elements, $c$ is the challenge from the verifier and $x$ is the input vector.

Returns:

A list of input elements representing the response of the prover.

verify()

Validate the sigma protocol and determine whether the verifier is convinced of the proof of knowledge.

Return type:

bool

Returns:

True if the verifier is convinced otherwise False

class templates.CompressedSigmaProtocol(homomorphism, image_to_prove, response, commitment, transcript, hash_algorithm)

Bases: Generic[InputElementT, HomomorphismOutputT, ChallengeT], BaseSigmaProtocol[InputElementT, HomomorphismOutputT, ChallengeT, CompressibleHomomorphismInput[InputElementT], CompressibleHomomorphism[InputElementT, HomomorphismOutputT, ChallengeT]]

Sigma protocol which has been compressed. A compressed sigma protocol can be created by applying the compression mechanism to the sigma-protocol.

__init__(homomorphism, image_to_prove, response, commitment, transcript, hash_algorithm)

Initialization function for a compressed sigma protocol. To create a compressed sigma- protocol use the compress function from the compression mechanism.

Parameters:

• homomorphism (CompressibleHomomorphism[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True)]) – The compressible homomorphism used by the sigma protocol.

• image_to_prove (TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)) – image generated by applying the homomorphism to the secret input

• response (CompressibleHomomorphismInput[TypeVar(InputElementT)]) – a compressed response

• commitment (TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)) – the initial commitment from the sigma protocol

• transcript (list[tuple[TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)]]) – the transcript of $A_i$ and $B_i$

• hash_algorithm (str) – the hash algorithm used to generate the challenges

property transcript: list[tuple[HomomorphismOutputT, HomomorphismOutputT]]

Transcript of the tuple consisting of the $A_i$ and $B_i$ elements. The elements are used during the verification to generate the corresponding challenges and to verify the result.

Returns:

A list of tuples corresponding to the $A$’s and $B$’s.

verify()

Validate the sigma protocol and determine whether the verifier is convinced of the proof of knowledge.

Return type:

bool

Returns:

True if the verifier is convinced otherwise False

class templates.CompressibleHomomorphism(*args, **kwargs)

Bases: Homomorphism[InputElementT, HomomorphismOutputT, ChallengeT], Protocol[InputElementT, HomomorphismOutputT, ChallengeT]

An abstract class which extends the Homomorphism-class with functions. The additional functions enable the compression mechanism to compress the sigma protocol.

__add__(other)

Add two homomorphisms mapping from the same groups $mathbb{G}^n$ and $mathbb{H}$ to generate a new homomorphism.

Parameters:

other (object) – the homomorphism to add

Return type:

Self

Returns:

The new homomorphism also mapping from $mathbb{G}^n$ to $mathbb{H}$.

__mul__(other)

Multiply the homomorphism by the challenge.

Parameters:

other (object) – the challenge to multiply by.

Return type:

Self

Returns:

A new homomorphism mapping from the same groups.

split_in_half()

Split the homomorphism into two new homomorphisms where the input size is of length $n/2$. The homomorphisms are split into a left and right half and map from the same groups.

Return type:

tuple[Self, Self]

Returns:

Tuple of two homomorphisms with input size of $n/2$, with the left half being the first element and the right half being the second element of the tuple.

class templates.Homomorphism(*args, **kwargs)

Bases: Protocol[InputElementT, HomomorphismOutputT, ChallengeT]

The homomorphism class is a class consisting of abstract methods. The class must be able to take in a vector of length $n$ and evaluate to an output. The size of $n$ is determined by a local property called expected_input_size.

The homomorphism class is also known as the function $psi$ in literature.

The homomorphism assumes you can multiply the InputElement and HomomorphismOutput by the Challenge and that InputElement objects can be added together.

challenge_from_bytes(hash_bytes)

Create a challenge from the bytes that are received. The bytes must create a consistent way of generating the challenge.

Parameters:

hash_bytes (bytes) – the bytes to generate the challenge from

Return type:

TypeVar(ChallengeT, covariant=True)

Returns:

a Challenge object derived from the bytes

evaluate(homomorphism_input)

Apply the homomorphism to the input.

Parameters:

homomorphism_input (HomomorphismInput[TypeVar(InputElementT)]) – The input vector and any additional information necessary

Return type:

TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)

Returns:

The output of the homomorphism applied to the input

property input_size: int

The length of the vector that can be processed by the homomorphism.

Returns:

integer indicating the length of the excepted vector input

output_to_bytes(output)

Transform the homomorphism output to a representation in bytes.

Parameters:

output (TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)) – The output to transform

Return type:

bytes

Returns:

bytes representing the homomorphism output

random_input()

Generate a vector of length $n$ consisting of random input elements.

Return type:

HomomorphismInput[TypeVar(InputElementT)]

Returns:

List of $n$ random input elements

class templates.StandardSigmaProtocol(homomorphism, image_to_prove, commitment, response, hash_algorithm)

Bases: Generic[InputElementT, HomomorphismOutputT, ChallengeT], BaseSigmaProtocol[InputElementT, HomomorphismOutputT, ChallengeT, HomomorphismInput[InputElementT], Homomorphism[InputElementT, HomomorphismOutputT, ChallengeT]]

Sigma protocol which consists of three steps. The sigma protocol enables the user to generate a proof of knowledge and verify it. The proof of knowledge is over a vector of InputElement’s.

classmethod generate_proof(homomorphism, private_input, hash_function)

Generate a zero-knowledge proof for the provided input and the homomorphism.

Parameters:

• homomorphism (Homomorphism[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True)]) – The homomorphism used during the sigma protocol

• private_input (HomomorphismInput[TypeVar(InputElementT)]) – The input for which a proof is generated

• hash_function (str) – The hash function name from hashlib used to create the challenge

Return type:

Self

Returns:

A sigma protocol which can be verified.

Raises:

ValueError – When the input length vector is not equal to the expected input size

verify()

Validate the sigma protocol and determine whether the verifier is convinced of the proof of knowledge.

Return type:

bool

Returns:

True if the verifier is convinced otherwise False

templates.compression(sigma_protocol)

Compress a sigma protocol by using the folding technique described in the dissertation mentioned in the README.md

Parameters:

sigma_protocol (BaseSigmaProtocol[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True), TypeVar(ResponseT, bound= HomomorphismInput[Any]), TypeVar(HomomorphismT, bound= Homomorphism[Any, Any, Any])]) – the sigma protocol which will be compressed

Return type:

CompressedSigmaProtocol[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True)]

Returns:

A compressed sigma protocol

Raises:

• TypeError – When the homomorphism of the sigma protocol is not compressible

• TypeError – When the homomorphism input of the sigma protocol is not compressible

• ValueError – When the homomorphism is already as small as possible

templates.create_challenge(hash_function_name, create_bytes_from, homomorphism)

Create a challenge from homomorphism output using the hash function. The challenge is used in the sigma-protocol to make it non-interactive.

Parameters:

• hash_function_name (str) – Name of hash function in the hashlib library

• create_bytes_from (Union[TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), Iterable[TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition)]]) – homomorphism output(s) from which the challenge is made

• homomorphism (Homomorphism[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True)]) – the corresponding homomorphism which creates a challenge from bytes

Return type:

TypeVar(ChallengeT, covariant=True)

Returns:

A challenge derived from the bytes of the hash function applied to the homomorphism output(s).

templates.full_compression(sigma_protocol)

Compress a sigma protocol until it can not be compressed any further.

Parameters:

sigma_protocol (BaseSigmaProtocol[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True), TypeVar(ResponseT, bound= HomomorphismInput[Any]), TypeVar(HomomorphismT, bound= Homomorphism[Any, Any, Any])]) – the sigma protocol which will be compressed

Return type:

CompressedSigmaProtocol[TypeVar(InputElementT), TypeVar(HomomorphismOutputT, bound= SupportsMultiplicationAndAddition), TypeVar(ChallengeT, covariant=True)]

Returns:

A compressed sigma protocol if the protocol could be compressed otherwise the sigma protocol itself

Raises:

• TypeError – When the homomorphism of the sigma protocol is not compressible

• TypeError – When the homomorphism input of the sigma protocol is not compressible

• ValueError – When the homomorphism is already as small as possible

Submodules

• templates.compression_mechanism module
  • compression()
  • full_compression()
• templates.homomorphism module
  • CompressibleHomomorphism
    • CompressibleHomomorphism.__add__()
    • CompressibleHomomorphism.__mul__()
    • CompressibleHomomorphism.split_in_half()
  • CompressibleHomomorphismInput
    • CompressibleHomomorphismInput.split_in_half()
  • Homomorphism
    • Homomorphism.challenge_from_bytes()
    • Homomorphism.evaluate()
    • Homomorphism.input_size
    • Homomorphism.output_to_bytes()
    • Homomorphism.random_input()
  • HomomorphismInput
    • HomomorphismInput.input_vector
  • SupportsMultiplicationAndAddition
    • SupportsMultiplicationAndAddition.__add__()
    • SupportsMultiplicationAndAddition.__mul__()
• templates.sigma_protocol module
  • BaseSigmaProtocol
    • BaseSigmaProtocol.__init__()
    • BaseSigmaProtocol.commitment
    • BaseSigmaProtocol.hash_algorithm
    • BaseSigmaProtocol.homomorphism
    • BaseSigmaProtocol.image_to_prove
    • BaseSigmaProtocol.response
    • BaseSigmaProtocol.verify()
  • CompressedSigmaProtocol
    • CompressedSigmaProtocol.__init__()
    • CompressedSigmaProtocol.transcript
    • CompressedSigmaProtocol.verify()
  • StandardSigmaProtocol
    • StandardSigmaProtocol.generate_proof()
    • StandardSigmaProtocol.verify()
  • create_challenge()