# TNO PET Lab - Zero-Knowledge Proofs (ZKP) - Commitment Schemes - Pedersen
Implementation of the Pedersen commitment scheme.
### PET Lab
The TNO PET Lab consists of generic software components, procedures, and functionalities developed and maintained on a regular basis to facilitate and aid in the development of PET solutions. The lab is a cross-project initiative allowing us to integrate and reuse previously developed PET functionalities to boost the development of new protocols and solutions.
The package `tno.zkp.commitment_schemes.pedersen` is part of the [TNO Python Toolbox](https://github.com/TNO-PET).
_Limitations in (end-)use: the content of this software package may solely be used for applications that comply with international export control laws._
_This implementation of cryptographic software has not been audited. Use at your own risk._
## Documentation
Documentation of the `tno.zkp.commitment_schemes.pedersen` package can be found
[here](https://docs.pet.tno.nl/zkp/commitment_schemes/pedersen/0.2.0).
## Install
Easily install the `tno.zkp.commitment_schemes.pedersen` package using `pip`:
```console
$ python -m pip install tno.zkp.commitment_schemes.pedersen
```
_Note:_ If you are cloning the repository and wish to edit the source code, be
sure to install the package in editable mode:
```console
$ python -m pip install -e 'tno.zkp.commitment_schemes.pedersen'
```
If you wish to run the tests you can use:
```console
$ python -m pip install 'tno.zkp.commitment_schemes.pedersen[tests]'
```
_Note:_ A significant performance improvement can be achieved by installing the GMPY2 library.
```console
$ python -m pip install 'tno.zkp.commitment_schemes.pedersen[gmpy]'
```
## Using the Pedersen Zero Knowledge Proof library
**NOTE:** This library is meant to be used in combination with the zero-knowledge proof (ZKP) template library found [here](https://github.com/TNO-ZKP/templates). Preliminaries on the content can also be found here. The Pedersen library is an instance of a ZKP, which uses the functionality from the template. In that sense, it is interchangable with the modulus linear form described in the template. They are both homomorphisms to be used in sigma protocols, though they have different structure. If anything below is unclear, it is highly recommended to read the preliminaries.
The ZKP library is based on Thomas Attema's dissertation Compressed $\Sigma$-protocol Theory, which can be found [here](https://scholarlypublications.universiteitleiden.nl/handle/1887/3619596). Many concepts are taken from it, and there will be references throughout the code to the dissertation. In this README the crucial concepts from the dissertation needed to use this library will be explained in short. If anything is unclear, feel free to raise an issue at the code repository.
## Commitment schemes
A commitment scheme is a cryptograpic protocol that is used when a party has a value they want to commit to now, but only share later.
A commitment scheme consists of two phases: in the _commit phase_, the prover commits to a chosen value and sends a _commitment_ to the verifier. During the _reveal phase_, the prover sends the original value and the verifier checks that the earlier commitment was indeed correct. One can view the functionality similar to the prover putting the value in a box, locking it and giving it to the verifier, and only later giving the key to the verifier to check.
Commitment schemes can for instance be used to fairly flip a coin over text-only communication, where it can make sure neither party cheats by changing their prediction. It can also be used in more complex applications, such as signature schemes, secret sharing or zero-knowledge proofs.
### The Pedersen commitment scheme
The Pedersen commitment scheme is defined as follows. The prover has a secret value $\mathbf{x} \in \mathbb{G}^n$ and reveal information $u \in \mathbb{G}$. They calculate the commitment $P := \psi_n(u, \mathbf{x})$, where the homomorphism $\psi_n$ is defined as
$$ \psi_n(u, \mathbf{x}) := h^u \cdot g_1^{x_1} g_2^{x_2} \cdots g_n^{x_n} $$
where $h, g_1, g_2, \dots, g_n \in \mathbb{G}$.
Then the prover sends $P$ to the verifier who stores it. Only later, when the prover wants to show that they indeed chose $\mathbf{x}$, they send $\mathbf{x}$ to the verifier, who then checks that $\psi(u, \mathbf{x}) = P$.
## Compressing the homomorphism
Splitting the homomorphism $\psi_n$ and the input $(u, \mathbf{x})$ works similarly to the linear form found in [the templates package](https://ci.tno.nl/gitlab/pet/lab/zkp/python-packages/microlibs/templates/-/tree/master/src/tno/zkp/modulus_linear_form?ref_type=heads), but the reveal information needs to be handled correctly as well. We split the input vector $\mathbf{x}$ as follows
```math
\mathbf{x} = (x_1, x_2, \dots, x_n) \\
\mathbf{x_L} = (x_1, x_2, \dots, x_{n/2}) \\
\mathbf{x_R} = (x_{n/2+1}, x_{n/2+2}, \dots, x_n)
```
and similarly the generators $g_1, g_2, \dots, g_n$ of $\psi(\cdot)$.
We also need to 'split' the reveal information $u$ and the generator $h$, but these are numbers rather than vectors.
It turns out that if we simply copy these values to both halves, the verification fails. So instead, we give the halves new reveal information $u_L$ and $u_R$ respectively, leading to the following
```math
\psi_n(u, \mathbf{x}) := h^u \cdot g_1^{x_1} g_2^{x_2} \cdots g_n^{x_n} \\
\psi_{n/2}^L(u_L, \mathbf{x}_L) := h^{u_L} \cdot g_1^{x_1} g_2^{x_2} \cdots g_{n/2}^{x_{n/2}}
\\
\psi_{n/n}^R(u_R, \mathbf{x}_R) := h^{u_R} \cdot g_{n/2+1}^{x_{n/2+1}} g_{n/2+2}^{x_{n/2+2}} \cdots g_n^{x_n}
```
If we plug general $u_L, u_R$ into the scheme and follow the protocol, at the verification step we get the equation
```math
h^{u_L+cu+c^2u_R} = \left(h^{c+1}\right)^{(u_L+cu_R)} \\
\implies u_L+cu+c^2u_R = u_L+c(u_L+u_R)+c^2u_R \\
\implies u = u_L+u_R
```
Therefore when splitting, we define $u_L:=0, \ u_R:=u$ to ensure correct behavior. This design is followed in the code.
## Creating a Sigma Protocol
To support the creation of a sigma protocol the template classes have been created. The template classes can be split into two categories.
The first category are the classes needed to create a basic sigma protocol. The basic sigma protocol creates a proof of knowledge in a non-interactive way. The `StandardSigmaProtocol` object contains all the information needed for the verification and none of the private information. The object can therefore be shared with the verifier for verification.
The `PedersenVectorCommitmentScheme` is a `Homomorphism` object that can be used with the sigma protocol library.
The easiest way to create a `PedersenVectorCommitmentScheme` is using the `from_security_param`, supplying a key length of 256 bits and generating a vector of length 16 in this case. You can also define the coefficients manually, but you need to supply a large enough safe prime as well.
Generating the proof of knowledge is relatively straight forward. You call the method `generate_proof` with the homomorphism, the secret input and the hash function. The class will handle the process as described in the steps above.
To verify the proof of knowledge you only need to call the `verify` function.
```python
from tno.zkp.commitment_schemes.pedersen import PedersenVectorCommitmentScheme
from tno.zkp.templates.sigma_protocol import StandardSigmaProtocol
homomorphism = PedersenVectorCommitmentScheme.from_security_param(key_length=256, vector_length=16)
secret_input_x = homomorphism.random_input()
proof_of_knowledge = StandardSigmaProtocol.generate_proof(
homomorphism, secret_input_x, "sha256"
)
# proof of knowledge can now be transferred to the verifier
assert proof_of_knowledge.verify()
```
## Compressing a Sigma Protocol
To compress a proof of knowledge there are some requirements on the homomorphism and the input. The requirements are
enforced using the `CompressibleHomomorphism` and the `CompressibleHomomorphismInput` abstract classes.
> Compressing a proof of knowledge makes the verification of the protocol cheaper. The cost savings occur due to a
> compression mechanism. The compression mechanism is described in detail in the dissertation.
The `PedersenVectorCommitmentScheme` class satisfies the requirements. Therefore, we can use the
previous proof of knowledge for compression.
To apply the compression we need to use a compression mechanism. The compression mechanism from the dissertation has
been implemented in the template. To apply it you need to do the following:
```python
from tno.zkp.templates.compression_mechanism import full_compression
# compress the proof of knowledge as much as possible
compressed_protocol = full_compression(proof_of_knowledge)
assert compressed_protocol.verify()
```
The function `full_compression` reduces the ZKP from length $n$ until it can not be compressed anymore, which is a length of 1. The function used for the compression is called `compression` and is available to the user as well. The `compression` function halves the length of the ZKP.
Raw data
{
"_id": null,
"home_page": null,
"name": "tno.zkp.commitment-schemes.pedersen",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": "TNO PET Lab <petlab@tno.nl>",
"keywords": "TNO, ZKP, zero-knowledge proofs",
"author": null,
"author_email": "TNO PET Lab <petlab@tno.nl>",
"download_url": "https://files.pythonhosted.org/packages/ec/7d/75a05323f81d5686683f174fb3a6ef94af624d0f27ca8b0e38cd08a29059/tno_zkp_commitment_schemes_pedersen-0.2.0.tar.gz",
"platform": "any",
"description": "# TNO PET Lab - Zero-Knowledge Proofs (ZKP) - Commitment Schemes - Pedersen\n\nImplementation of the Pedersen commitment scheme.\n\n### PET Lab\n\nThe TNO PET Lab consists of generic software components, procedures, and functionalities developed and maintained on a regular basis to facilitate and aid in the development of PET solutions. The lab is a cross-project initiative allowing us to integrate and reuse previously developed PET functionalities to boost the development of new protocols and solutions.\n\nThe package `tno.zkp.commitment_schemes.pedersen` is part of the [TNO Python Toolbox](https://github.com/TNO-PET).\n\n_Limitations in (end-)use: the content of this software package may solely be used for applications that comply with international export control laws._ \n_This implementation of cryptographic software has not been audited. Use at your own risk._\n\n## Documentation\n\nDocumentation of the `tno.zkp.commitment_schemes.pedersen` package can be found\n[here](https://docs.pet.tno.nl/zkp/commitment_schemes/pedersen/0.2.0).\n\n## Install\n\nEasily install the `tno.zkp.commitment_schemes.pedersen` package using `pip`:\n\n```console\n$ python -m pip install tno.zkp.commitment_schemes.pedersen\n```\n\n_Note:_ If you are cloning the repository and wish to edit the source code, be\nsure to install the package in editable mode:\n\n```console\n$ python -m pip install -e 'tno.zkp.commitment_schemes.pedersen'\n```\n\nIf you wish to run the tests you can use:\n\n```console\n$ python -m pip install 'tno.zkp.commitment_schemes.pedersen[tests]'\n```\n\n_Note:_ A significant performance improvement can be achieved by installing the GMPY2 library.\n\n```console\n$ python -m pip install 'tno.zkp.commitment_schemes.pedersen[gmpy]'\n```\n\n## Using the Pedersen Zero Knowledge Proof library\n\n**NOTE:** This library is meant to be used in combination with the zero-knowledge proof (ZKP) template library found [here](https://github.com/TNO-ZKP/templates). Preliminaries on the content can also be found here. The Pedersen library is an instance of a ZKP, which uses the functionality from the template. In that sense, it is interchangable with the modulus linear form described in the template. They are both homomorphisms to be used in sigma protocols, though they have different structure. If anything below is unclear, it is highly recommended to read the preliminaries.\n\nThe ZKP library is based on Thomas Attema's dissertation Compressed $\\Sigma$-protocol Theory, which can be found [here](https://scholarlypublications.universiteitleiden.nl/handle/1887/3619596). Many concepts are taken from it, and there will be references throughout the code to the dissertation. In this README the crucial concepts from the dissertation needed to use this library will be explained in short. If anything is unclear, feel free to raise an issue at the code repository.\n\n## Commitment schemes\n\nA commitment scheme is a cryptograpic protocol that is used when a party has a value they want to commit to now, but only share later.\nA commitment scheme consists of two phases: in the _commit phase_, the prover commits to a chosen value and sends a _commitment_ to the verifier. During the _reveal phase_, the prover sends the original value and the verifier checks that the earlier commitment was indeed correct. One can view the functionality similar to the prover putting the value in a box, locking it and giving it to the verifier, and only later giving the key to the verifier to check.\nCommitment schemes can for instance be used to fairly flip a coin over text-only communication, where it can make sure neither party cheats by changing their prediction. It can also be used in more complex applications, such as signature schemes, secret sharing or zero-knowledge proofs.\n\n### The Pedersen commitment scheme\n\nThe Pedersen commitment scheme is defined as follows. The prover has a secret value $\\mathbf{x} \\in \\mathbb{G}^n$ and reveal information $u \\in \\mathbb{G}$. They calculate the commitment $P := \\psi_n(u, \\mathbf{x})$, where the homomorphism $\\psi_n$ is defined as\n\n$$ \\psi_n(u, \\mathbf{x}) := h^u \\cdot g_1^{x_1} g_2^{x_2} \\cdots g_n^{x_n} $$\n\nwhere $h, g_1, g_2, \\dots, g_n \\in \\mathbb{G}$.\nThen the prover sends $P$ to the verifier who stores it. Only later, when the prover wants to show that they indeed chose $\\mathbf{x}$, they send $\\mathbf{x}$ to the verifier, who then checks that $\\psi(u, \\mathbf{x}) = P$.\n\n## Compressing the homomorphism\n\nSplitting the homomorphism $\\psi_n$ and the input $(u, \\mathbf{x})$ works similarly to the linear form found in [the templates package](https://ci.tno.nl/gitlab/pet/lab/zkp/python-packages/microlibs/templates/-/tree/master/src/tno/zkp/modulus_linear_form?ref_type=heads), but the reveal information needs to be handled correctly as well. We split the input vector $\\mathbf{x}$ as follows\n\n```math\n\\mathbf{x} = (x_1, x_2, \\dots, x_n) \\\\\n\\mathbf{x_L} = (x_1, x_2, \\dots, x_{n/2}) \\\\\n\\mathbf{x_R} = (x_{n/2+1}, x_{n/2+2}, \\dots, x_n)\n```\n\nand similarly the generators $g_1, g_2, \\dots, g_n$ of $\\psi(\\cdot)$.\nWe also need to 'split' the reveal information $u$ and the generator $h$, but these are numbers rather than vectors.\nIt turns out that if we simply copy these values to both halves, the verification fails. So instead, we give the halves new reveal information $u_L$ and $u_R$ respectively, leading to the following\n\n```math\n \\psi_n(u, \\mathbf{x}) := h^u \\cdot g_1^{x_1} g_2^{x_2} \\cdots g_n^{x_n} \\\\\n \\psi_{n/2}^L(u_L, \\mathbf{x}_L) := h^{u_L} \\cdot g_1^{x_1} g_2^{x_2} \\cdots g_{n/2}^{x_{n/2}}\n \\\\\n \\psi_{n/n}^R(u_R, \\mathbf{x}_R) := h^{u_R} \\cdot g_{n/2+1}^{x_{n/2+1}} g_{n/2+2}^{x_{n/2+2}} \\cdots g_n^{x_n}\n```\n\nIf we plug general $u_L, u_R$ into the scheme and follow the protocol, at the verification step we get the equation\n\n```math\n h^{u_L+cu+c^2u_R} = \\left(h^{c+1}\\right)^{(u_L+cu_R)} \\\\\n \\implies u_L+cu+c^2u_R = u_L+c(u_L+u_R)+c^2u_R \\\\\n \\implies u = u_L+u_R\n```\n\nTherefore when splitting, we define $u_L:=0, \\ u_R:=u$ to ensure correct behavior. This design is followed in the code.\n\n## Creating a Sigma Protocol\n\nTo support the creation of a sigma protocol the template classes have been created. The template classes can be split into two categories.\n\nThe first category are the classes needed to create a basic sigma protocol. The basic sigma protocol creates a proof of knowledge in a non-interactive way. The `StandardSigmaProtocol` object contains all the information needed for the verification and none of the private information. The object can therefore be shared with the verifier for verification.\n\nThe `PedersenVectorCommitmentScheme` is a `Homomorphism` object that can be used with the sigma protocol library.\n\nThe easiest way to create a `PedersenVectorCommitmentScheme` is using the `from_security_param`, supplying a key length of 256 bits and generating a vector of length 16 in this case. You can also define the coefficients manually, but you need to supply a large enough safe prime as well.\n\nGenerating the proof of knowledge is relatively straight forward. You call the method `generate_proof` with the homomorphism, the secret input and the hash function. The class will handle the process as described in the steps above.\n\nTo verify the proof of knowledge you only need to call the `verify` function.\n\n```python\nfrom tno.zkp.commitment_schemes.pedersen import PedersenVectorCommitmentScheme\nfrom tno.zkp.templates.sigma_protocol import StandardSigmaProtocol\n\nhomomorphism = PedersenVectorCommitmentScheme.from_security_param(key_length=256, vector_length=16)\nsecret_input_x = homomorphism.random_input()\n\nproof_of_knowledge = StandardSigmaProtocol.generate_proof(\n homomorphism, secret_input_x, \"sha256\"\n)\n\n# proof of knowledge can now be transferred to the verifier\nassert proof_of_knowledge.verify()\n```\n\n## Compressing a Sigma Protocol\n\nTo compress a proof of knowledge there are some requirements on the homomorphism and the input. The requirements are\nenforced using the `CompressibleHomomorphism` and the `CompressibleHomomorphismInput` abstract classes.\n\n> Compressing a proof of knowledge makes the verification of the protocol cheaper. The cost savings occur due to a\n> compression mechanism. The compression mechanism is described in detail in the dissertation.\n\nThe `PedersenVectorCommitmentScheme` class satisfies the requirements. Therefore, we can use the\nprevious proof of knowledge for compression.\n\nTo apply the compression we need to use a compression mechanism. The compression mechanism from the dissertation has\nbeen implemented in the template. To apply it you need to do the following:\n\n```python\nfrom tno.zkp.templates.compression_mechanism import full_compression\n\n# compress the proof of knowledge as much as possible\ncompressed_protocol = full_compression(proof_of_knowledge)\nassert compressed_protocol.verify()\n```\n\nThe function `full_compression` reduces the ZKP from length $n$ until it can not be compressed anymore, which is a length of 1. The function used for the compression is called `compression` and is available to the user as well. The `compression` function halves the length of the ZKP.\n",
"bugtrack_url": null,
"license": "Apache License, Version 2.0",
"summary": "ZKP Pedersen Commitment Scheme module",
"version": "0.2.0",
"project_urls": {
"Documentation": "https://docs.pet.tno.nl/zkp/commitment_schemes/pedersen/0.2.0",
"Homepage": "https://pet.tno.nl/",
"Source": "https://github.com/TNO-ZKP/commitment_schemes.pedersen"
},
"split_keywords": [
"tno",
" zkp",
" zero-knowledge proofs"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "d9fb8441ada99de53569f8d37d75dabb303ec0356d8527ce608cfacf2c5c2305",
"md5": "80cb51ce10e573f631c8afad71c9ac68",
"sha256": "5a3d6a3ccf150cfb620b4b5570048df1518ad3b70a4ebd666ea3c74cd802e0e2"
},
"downloads": -1,
"filename": "tno.zkp.commitment_schemes.pedersen-0.2.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "80cb51ce10e573f631c8afad71c9ac68",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 21236,
"upload_time": "2024-12-06T10:03:13",
"upload_time_iso_8601": "2024-12-06T10:03:13.195812Z",
"url": "https://files.pythonhosted.org/packages/d9/fb/8441ada99de53569f8d37d75dabb303ec0356d8527ce608cfacf2c5c2305/tno.zkp.commitment_schemes.pedersen-0.2.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "ec7d75a05323f81d5686683f174fb3a6ef94af624d0f27ca8b0e38cd08a29059",
"md5": "ce2eda6f4517e0c023763b0b9582be0f",
"sha256": "e606eb77ad8903826394f0928237928e1a9629549da10075e2fd02deb99b7da1"
},
"downloads": -1,
"filename": "tno_zkp_commitment_schemes_pedersen-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "ce2eda6f4517e0c023763b0b9582be0f",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 25048,
"upload_time": "2024-12-06T10:03:15",
"upload_time_iso_8601": "2024-12-06T10:03:15.602324Z",
"url": "https://files.pythonhosted.org/packages/ec/7d/75a05323f81d5686683f174fb3a6ef94af624d0f27ca8b0e38cd08a29059/tno_zkp_commitment_schemes_pedersen-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-06 10:03:15",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "TNO-ZKP",
"github_project": "commitment_schemes.pedersen",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "tno.zkp.commitment-schemes.pedersen"
}
JSON
