[WIP] respond with a single vector per system of equations
The previous implementation incorrectly generated a vector of response scalars
for each equation, based on a whole matrix of secret nonces.
This meant that witness terms could actually vary from equation to equation,
and that proofs sizes were quadratic instead of linear.
MODIFY
WalletWasabi.Tests/UnitTests/Crypto/ZeroKnowledge/LinearRelationTests.cs
WalletWasabi.Tests/UnitTests/Crypto/ZeroKnowledge/LinearRelationTests.cs
@@ -102,13 +102,14 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
// Create transcripts using a witness to the relation
var knowledge = new Knowledge(statement, new ScalarVector(x));
- var allSecretNonces = new[] { new ScalarVector(new Scalar(7)), new ScalarVector(new Scalar(11)) };
- var publicNonces = new GroupElementVector(statement.Equations.Zip(allSecretNonces, (equation, secretNonces) => secretNonces * equation.Generators));
- var allResponses = knowledge.RespondToChallenge(challenge, allSecretNonces);
- Assert.True(statement.CheckVerificationEquation(publicNonces, challenge, allResponses));
+ var secretNonces = new ScalarVector(new Scalar(7));
+ var publicNonces = new GroupElementVector(statement.Equations.Select(equation => secretNonces * equation.Generators));
+ var responses = knowledge.RespondToChallenge(challenge, secretNonces);
+ Assert.Single(responses);
+ Assert.True(statement.CheckVerificationEquation(publicNonces, challenge, responses));
// Ensure that verifier rejects invalid transcripts
- Assert.False(statement.CheckVerificationEquation(publicNonces, new Scalar(17), allResponses));
+ Assert.False(statement.CheckVerificationEquation(publicNonces, new Scalar(17), responses));
}
[Fact]

MODIFY
WalletWasabi/Crypto/ZeroKnowledge/LinearRelation/Knowledge.cs
WalletWasabi/Crypto/ZeroKnowledge/LinearRelation/Knowledge.cs
@@ -26,12 +26,12 @@ namespace WalletWasabi.Crypto.ZeroKnowledge.LinearRelation
public Statement Statement { get; }
public ScalarVector Witness { get; }
- public IEnumerable<ScalarVector> RespondToChallenge(Scalar challenge, IEnumerable<ScalarVector> allSecretNonces)
+ public ScalarVector RespondToChallenge(Scalar challenge, ScalarVector secretNonces)
{
// allSecretNonces should have the same dimension as the equation matrix
- Statement.Equations.CheckDimensions(allSecretNonces);
+ // Statement.Equations.CheckDimensions(allSecretNonces);
- return Statement.Equations.Zip(allSecretNonces, (equation, secretNonces) => equation.Respond(Witness, secretNonces, challenge));
+ return Statement.Equations.First().Respond(Witness, secretNonces, challenge); // FIXME refactor
}
}
}

MODIFY
WalletWasabi/Crypto/ZeroKnowledge/LinearRelation/Statement.cs
WalletWasabi/Crypto/ZeroKnowledge/LinearRelation/Statement.cs
@@ -39,14 +39,14 @@ namespace WalletWasabi.Crypto.ZeroKnowledge.LinearRelation
public Knowledge ToKnowledge(ScalarVector witness) =>
new Knowledge(this, witness);
- public bool CheckVerificationEquation(GroupElementVector publicNonces, Scalar challenge, IEnumerable<ScalarVector> allResponses)
+ public bool CheckVerificationEquation(GroupElementVector publicNonces, Scalar challenge, ScalarVector responses)
{
// The responses matrix should match the generators in the equations and
// there should be once nonce per equation.
Guard.True(nameof(publicNonces), Equations.Count() == publicNonces.Count());
- Equations.CheckDimensions(allResponses);
+ // Equations.CheckDimensions(allResponses);
- return Equations.Zip(publicNonces, allResponses, (equation, r, s) => equation.Verify(r, challenge, s)).All(x => x);
+ return Equations.Zip(publicNonces, (equation, r) => equation.Verify(r, challenge, responses)).All(x => x);
}
}
}

MODIFY
WalletWasabi/Crypto/ZeroKnowledge/NonInteractive/FiatShamirTransform/Prover.cs
WalletWasabi/Crypto/ZeroKnowledge/NonInteractive/FiatShamirTransform/Prover.cs
@@ -39,24 +39,18 @@ namespace WalletWasabi.Crypto.ZeroKnowledge.NonInteractive.FiatShamirTransform
// different challenges which would leak the witness, these are generated
// as synthetic nonces that also depend on the witness data.
var secretNonceProvider = transcript.CreateSyntheticSecretNonceProvider(Knowledge.Witness, random);
-
- // Actually generate all of the required nonces and save them in an array
- // because if the enumerable is evaluated several times the results will
- // be different.
- // Note, ToArray() is needed to make sure that secretNonces is captured
- // once and shared between the phases.
- var equations = Knowledge.Statement.Equations;
- var secretNonces = secretNonceProvider.Sequence.Take(equations.Count()).ToArray();
+ var secretNonces = secretNonceProvider.Sequence.First(); // FIXME refactor GetVector()
// The prover then commits to these, adding the corresponding public
// points to the transcript.
- var publicNonces = new GroupElementVector(equations.Zip(secretNonces, (equation, pointSecretNonces) => pointSecretNonces * equation.Generators));
+ var equations = Knowledge.Statement.Equations;
+ var publicNonces = new GroupElementVector(equations.Select(equation => secretNonces * equation.Generators));
transcript.CommitPublicNonces(publicNonces);
return () => Respond(transcript, publicNonces, secretNonces);
}
- private Proof Respond(Transcript transcript, GroupElementVector nonces, IEnumerable<ScalarVector> secretNonces)
+ private Proof Respond(Transcript transcript, GroupElementVector nonces, ScalarVector secretNonces)
{
// With the public nonces committed to the transcript the prover can then
// derive a challenge that depend on the transcript state without needing

MODIFY
WalletWasabi/Crypto/ZeroKnowledge/NonInteractive/Proof.cs
WalletWasabi/Crypto/ZeroKnowledge/NonInteractive/Proof.cs
@@ -6,23 +6,16 @@ namespace WalletWasabi.Crypto.ZeroKnowledge.NonInteractive
{
public class Proof
{
- public Proof(GroupElementVector publicNonces, IEnumerable<ScalarVector> allResponses)
+ public Proof(GroupElementVector publicNonces, ScalarVector responses)
{
CryptoGuard.NotNullOrInfinity(nameof(publicNonces), publicNonces);
- Guard.NotNullOrEmpty(nameof(allResponses), allResponses);
-
- // Ensure allResponses isn't jagged
- var n = allResponses.First().Count();
- Guard.True(nameof(allResponses), allResponses.All(responses => Guard.NotNullOrEmpty(nameof(responses), responses).Count() == n));
-
- // Ensure there is a vector of response scalars for each public nonce
- Guard.True(nameof(allResponses), allResponses.Count() == publicNonces.Count());
+ Guard.NotNullOrEmpty(nameof(responses), responses);
PublicNonces = publicNonces;
- Responses = allResponses;
+ Responses = responses;
}
public GroupElementVector PublicNonces { get; }
- public IEnumerable<ScalarVector> Responses { get; }
+ public ScalarVector Responses { get; }
}
}

[WIP] respond with a single vector per system of equations

The previous implementation incorrectly generated a vector of response scalars
for each equation, based on a whole matrix of secret nonces.

This meant that witness terms could actually vary from equation to equation,
and that proofs sizes were quadratic instead of linear.