new SigmaProofOr(challengeSpace, param, copies)
Let R be an NP relation for which there is a Sigma
proof (P, V), let c > 0 be an integer, and define the NP relation
R(c) to consist of all pairs of the form (x, (w, i)) such that
(x[i], w) is contained in R for some 0 <= i < c. This class gives a
Sigma proof for R(c) provided that:
- The challenge space of V is a finite additive group, i.e., challenges implement add() and sub() for addition and subtraction, and toByteTree().
- The challenge is uniquely determined by the proof commitment and the reply. It may suffice that it is infeasible to find two distinct challenges that give accepting transcripts, but great care is needed.
Parameters:
Name | Type | Description |
---|---|---|
challengeSpace |
Space of challenges. This must implement a method toElement() that converts a byte tree to a challenge. | |
param |
Array of proofs in which case the second parameter must not be used, or a single sigma proof in which case the second parameter must be a positive integer. | |
copies |
Number of copies in case the first parameter is a single sigma proof. |
- Source:
Extends
Methods
byteTreeToCommitment(byteTree)
Converts a byte tree to a commitment.
Parameters:
Name | Type | Description |
---|---|---|
byteTree |
Byte tree representation of a commitment. |
- Inherited From:
- Source:
Returns:
Commitment.
byteTreeToReply(byteTree)
Converts a byte tree to a reply.
Parameters:
Name | Type | Description |
---|---|---|
byteTree |
Byte tree representation of a reply. |
- Overrides:
- Source:
Returns:
Reply.
challenge(first, second)
Computes the challenge of the verifier using either a
source of randomness or by applying the Fiat-Shamir heuristic to a
byte tree using a given hash function.
Parameters:
Name | Type | Description |
---|---|---|
first |
Source of randomness, or data to be hashed. | |
second |
Statistical distance from the uniform distribution assuming a perfect random source, or a hash function used to implement the Fiat-Shamir heuristic. |
- Inherited From:
- Source:
Returns:
Challenge of the verifier.
check(instance, commitment, challenge, witness, reply)
Computes the verdict of the verifier on a transcript.
Parameters:
Name | Type | Description |
---|---|---|
instance |
Instance. | |
commitment |
Commitment. | |
challenge |
Challenge of the prover. | |
witness |
Witness. | |
reply |
Reply. |
- Overrides:
- Source:
Returns:
Verdict of the verifier as a boolean.
commit(precomputed, instance, witness, randomSource, statDist)
Computes a pair of updated pre-computed values and a
commitment.
Parameters:
Name | Type | Description |
---|---|---|
precomputed |
Pre-computed values. | |
instance |
Instance. | |
witness |
Witness. | |
randomSource |
Source of randomness. | |
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Overrides:
- Source:
Returns:
Pair of updated pre-computed values and a commitment.
commitmentToByteTree(commitment)
Converts a commitment to a byte tree.
Parameters:
Name | Type | Description |
---|---|---|
commitment |
Commitment. |
- Inherited From:
- Source:
Returns:
Byte tree representation of the commitment.
completeProof(precomputed, label, instance, witness, hashfunction, randomSource, statDist)
Completes a proof using pre-computed values.
Parameters:
Name | Type | Description |
---|---|---|
precomputed |
Pre-computed values. | |
label |
Label as an array of bytes or byte tree. | |
instance |
Instance. | |
witness |
Witness of instance belonging to the right language. | |
hashfunction |
Hash function used to implement the random oracle. | |
randomSource |
Source of randomness. | |
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Inherited From:
- Source:
Returns:
Proof in the form of a byte array.
instanceToByteTree(instance)
Converts an instance to a byte tree.
Parameters:
Name | Type | Description |
---|---|---|
instance |
Instance. |
- Inherited From:
- Source:
Returns:
Byte tree representation of the instance.
precompute(randomSource, statDist)
Performs pre-computation.
Parameters:
Name | Type | Description |
---|---|---|
randomSource |
Source of randomness. | |
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Inherited From:
- Source:
Returns:
Pre-computed values.
precomputeRequiresInstance()
Indicates if pre-computation requires the
instance. This allows choosing the right pre-computation function.
- Overrides:
- Source:
Returns:
True or false depending on if pre-computation requires the
instance or not.
precomputeWithInstance(instance, randomSource, statDist)
Performs pre-computation when the instance is needed.
Parameters:
Name | Type | Description |
---|---|---|
instance |
Instance. | |
randomSource |
Source of randomness. | |
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Overrides:
- Source:
Returns:
Pre-computed values.
prove(label, instance, witness, hashfunction, randomSource, statDist)
Computes a proof.
Parameters:
Name | Type | Description |
---|---|---|
label |
Label as an array of bytes or byte tree. | |
instance |
Instance. | |
witness |
Witness of instance belonging to the right language. | |
hashfunction |
Hash function used to implement the random oracle. | |
randomSource |
Source of randomness. | |
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Inherited From:
- Source:
Returns:
Proof in the form of a byte array.
randomnessByteLength(statDist)
Number of bytes or randomness needed to compute a proof.
Parameters:
Name | Type | Description |
---|---|---|
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Inherited From:
- Source:
Returns:
Number of bytes needed to compute a proof.
reply(precomputed, witness, challenge, randomness)
Computes the reply of the prover.
Parameters:
Name | Type | Description |
---|---|---|
precomputed |
Pre-computed values needed to compute the reply. | |
witness |
Witness. | |
challenge |
Challenge of the verifier. | |
randomness |
Randomness used to form the commitment. |
- Overrides:
- Source:
Returns:
Reply of the prover.
replyToByteTree(reply)
Converts a reply to a byte tree.
Parameters:
Name | Type | Description |
---|---|---|
reply |
Reply. |
- Overrides:
- Source:
Returns:
Byte tree representation of the reply.
simulate(instance, challenge, randomSource, statDist)
Simulates a commitment and reply for the given
challenge.
Parameters:
Name | Type | Description |
---|---|---|
instance |
Instance. | |
challenge |
Challenge of the verifier. | |
randomSource |
Source of randomness. | |
statDist |
Statistical distance from the uniform distribution assuming a perfect random source. |
- Overrides:
- Source:
Returns:
Pair of a commitment and reply.
verify(label, instance, hashfunction, proof)
Verifies a proof. This is meant to be used for
debugging, so the granularity in error handling is rudimentary.
Parameters:
Name | Type | Description |
---|---|---|
label |
Label as an array of bytes or byte tree. | |
instance |
Instance. | |
hashfunction |
Hash function used to implement the random oracle. | |
proof |
Candidate proof in the form of a byte array. |
- Inherited From:
- Source:
Returns:
True or false depending on if the candidate proof is valid
or not.