Add LinearRelation.{Statement,Knowledge} classes
These classes implement the generalized linear relation Sigma protocol, proving
knowledge of a witness that satisfies a system of equations (implemented by the
internal Equation class).
MODIFY
WalletWasabi.Tests/UnitTests/Crypto/ZeroKnowledge/LinearRelationTests.cs
WalletWasabi.Tests/UnitTests/Crypto/ZeroKnowledge/LinearRelationTests.cs
using NBitcoin.Secp256k1;
+using System;
using System.Linq;
using WalletWasabi.Crypto;
using WalletWasabi.Crypto.Groups;
@@ -7,7 +8,7 @@ using Xunit;
namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
{
- public class EquationTest
+ public class LinearRelationTests
{
[Theory]
[InlineData(0, 0)]
@@ -23,22 +24,22 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
[InlineData(uint.MaxValue, uint.MaxValue)]
public void VerifyResponsesAndSimulations(uint scalarSeed1, uint scalarSeed2)
{
- var witness = new ScalarVector(new[] { new Scalar(scalarSeed1), new Scalar(scalarSeed2) });
- var generators = new GroupElementVector(new[] { Generators.G, Generators.Ga });
+ var witness = new ScalarVector(new Scalar(scalarSeed1), new Scalar(scalarSeed2));
+ var generators = new GroupElementVector(Generators.G, Generators.Ga);
var publicPoint = witness * generators;
- var eqn = new Equation(publicPoint, generators);
+ var equation = new Equation(publicPoint, generators);
// First, demonstrate proving knowledge with the witness
- var secretNonces = new ScalarVector(new[] { new Scalar(23), new Scalar(42) });
+ var secretNonces = new ScalarVector(new Scalar(23), new Scalar(42));
var publicNonce = Enumerable.Zip(secretNonces, generators, (s, g) => s * g).Sum();
var challenge = new Scalar(101);
- var response = eqn.Respond(witness, secretNonces, challenge);
- Assert.True(eqn.Verify(publicNonce, challenge, response));
+ var response = equation.Respond(witness, secretNonces, challenge);
+ Assert.True(equation.Verify(publicNonce, challenge, response));
// Even without a witness, simulated proofs with the same response should still verify
- var simulatedNonce = eqn.Simulate(challenge, response);
- Assert.True(eqn.Verify(simulatedNonce, challenge, response));
+ var simulatedNonce = equation.Simulate(challenge, response);
+ Assert.True(equation.Verify(simulatedNonce, challenge, response));
// And the simulated prover commitment should be the same as the real one
// even if its discrete log w.r.t. the generators is not known
@@ -47,17 +48,17 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
// With a different challenge the nonce should be different
// unless the secret is 0, due to the absorption property
var otherChallenge = new Scalar(103);
- var otherSimulatedNonce = eqn.Simulate(otherChallenge, response);
- Assert.True(eqn.Verify(otherSimulatedNonce, otherChallenge, response));
+ var otherSimulatedNonce = equation.Simulate(otherChallenge, response);
+ Assert.True(equation.Verify(otherSimulatedNonce, otherChallenge, response));
if (scalarSeed1 != 0 && scalarSeed2 != 0)
{
Assert.True(otherSimulatedNonce != publicNonce);
}
// And with a different response the verifier should still accept
- var otherResponse = new ScalarVector(new[] { new Scalar(2), new Scalar(3) });
- var thirdSimulatedNonce = eqn.Simulate(challenge, otherResponse);
- Assert.True(eqn.Verify(thirdSimulatedNonce, challenge, otherResponse));
+ var otherResponse = new ScalarVector(new Scalar(2), new Scalar(3));
+ var thirdSimulatedNonce = equation.Simulate(challenge, otherResponse);
+ Assert.True(equation.Verify(thirdSimulatedNonce, challenge, otherResponse));
Assert.True(thirdSimulatedNonce != otherSimulatedNonce);
Assert.True(thirdSimulatedNonce != publicNonce);
@@ -65,8 +66,8 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
// an exception for when the public input is the point at infinity
if (scalarSeed1 != 0 && scalarSeed2 != 0)
{
- Assert.False(eqn.Verify(simulatedNonce, otherChallenge, response));
- Assert.False(eqn.Verify(publicNonce, otherChallenge, response));
+ Assert.False(equation.Verify(simulatedNonce, otherChallenge, response));
+ Assert.False(equation.Verify(publicNonce, otherChallenge, response));
}
}
@@ -75,29 +76,29 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
{
// Sometimes an equation uses the point at infinity as a generator,
// effectively canceling out the corresponding component of the witness
- var generators = new GroupElementVector(new[] { Generators.G, GroupElement.Infinity });
+ var generators = new GroupElementVector(Generators.G, GroupElement.Infinity);
var publicPoint = new Scalar(42) * Generators.G;
- var eqn = new Equation(publicPoint, generators);
+ var equation = new Equation(publicPoint, generators);
- var witness1 = new ScalarVector(new[] { new Scalar(42), new Scalar(23) });
- var witness2 = new ScalarVector(new[] { new Scalar(42), new Scalar(100) });
+ var witness1 = new ScalarVector(new Scalar(42), new Scalar(23));
+ var witness2 = new ScalarVector(new Scalar(42), new Scalar(100));
// Generate a single nonce to be shared by both proofs.
// note that in normal circumstances this is catastrophic because nonce
// reuse with different challenges allows recovery of the witness.
// in this case this is intentional, so that the test can compare the
// responses which would otherwise be different.
- var secretNonces = new ScalarVector(new[] { new Scalar(7), new Scalar(11) });
+ var secretNonces = new ScalarVector(new Scalar(7), new Scalar(11));
var publicNonce = Enumerable.Zip(secretNonces, generators, (s, g) => s * g).Sum();
var challenge = new Scalar(13);
// Derive two responses with the two different witnesses for the same
// point, and ensure that both are valid, implying that the second
// component in the witness is ignored.
- var response1 = eqn.Respond(witness1, secretNonces, challenge);
- Assert.True(eqn.Verify(publicNonce, challenge, response1));
- var response2 = eqn.Respond(witness2, secretNonces, challenge);
- Assert.True(eqn.Verify(publicNonce, challenge, response2));
+ var response1 = equation.Respond(witness1, secretNonces, challenge);
+ Assert.True(equation.Verify(publicNonce, challenge, response1));
+ var response2 = equation.Respond(witness2, secretNonces, challenge);
+ Assert.True(equation.Verify(publicNonce, challenge, response2));
// With different witnesses the responses should be different even if the
// nonces are the same, but since the first part of the witness is the
@@ -105,5 +106,89 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
Assert.False(response1 == response2);
Assert.True(response1.First() == response2.First());
}
+
+ [Fact]
+ public void StatementAndKnowledge()
+ {
+ var x = new Scalar(42);
+ var a = x * Generators.Gg;
+ var b = x * Generators.Gh;
+
+ // Discrete log equality (Chaum-Pedersen proof)
+ var statement = new Statement(new[]
+ {
+ new Equation(a, new GroupElementVector(Generators.Gg)),
+ new Equation(b, new GroupElementVector(Generators.Gh)),
+ });
+
+ // Check that simulation produces valid transcripts
+ var challenge = new Scalar(13);
+ var simulatedResponses = new[]
+ {
+ new ScalarVector(Scalar.One),
+ new ScalarVector(Scalar.One),
+ };
+
+ var simulatedPublicNonces = statement.SimulatePublicNonces(challenge, simulatedResponses);
+ Assert.True(statement.CheckVerificationEquation(simulatedPublicNonces, challenge, simulatedResponses));
+
+ // 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));
+
+ // Ensure that verifier rejects invalid transcripts
+ Assert.False(statement.CheckVerificationEquation(publicNonces, new Scalar(17), allResponses));
+ Assert.False(statement.CheckVerificationEquation(simulatedPublicNonces, challenge, allResponses));
+ Assert.False(statement.CheckVerificationEquation(publicNonces, challenge, simulatedResponses));
+ }
+
+ [Fact]
+ public void StatementThrows()
+ {
+ // Jagged equation matrices are not allowed
+ Assert.ThrowsAny<ArgumentException>(() => new Statement(new[]
+ {
+ new Equation(GroupElement.Infinity, new GroupElementVector(Generators.Gg, Generators.Gh)),
+ new Equation(GroupElement.Infinity, new GroupElementVector(Generators.G)),
+ }));
+
+ // Null generators are not allowed
+ Assert.ThrowsAny<ArgumentException>(() => new Statement(new[]
+ {
+ new Equation(GroupElement.Infinity, new GroupElementVector(Generators.Gg, Generators.Gh)),
+ new Equation(GroupElement.Infinity, new GroupElementVector(Generators.G, null!)),
+ }));
+ }
+
+ [Fact]
+ public void KnowledgeThrows()
+ {
+ var x = new Scalar(42);
+ var a = x * Generators.Gg;
+ var b = x * Generators.Gh;
+
+ var statement = new Statement(new[]
+ {
+ new Equation(a, new GroupElementVector(Generators.Gg)),
+ new Equation(b, new GroupElementVector(Generators.Gh)),
+ });
+
+ // Wrong size for witness
+ Assert.ThrowsAny<ArgumentException>(() => new Knowledge(statement, new ScalarVector(Scalar.Zero, Scalar.Zero)));
+
+ // Incorrect witness
+ Assert.ThrowsAny<ArgumentException>(() => new Knowledge(statement, new ScalarVector(Scalar.One)));
+
+ // Incorrect statement generators (effectively incorrect witness)
+ var badStatement = new Statement(new[]
+ {
+ new Equation(a, new GroupElementVector(Generators.Gh)),
+ new Equation(b, new GroupElementVector(Generators.Gg)),
+ });
+ Assert.ThrowsAny<ArgumentException>(() => new Knowledge(badStatement, new ScalarVector(Scalar.One)));
+ }
}
}

ADD
WalletWasabi/Crypto/ZeroKnowledge/LinearRelation/Knowledge.cs
+using NBitcoin.Secp256k1;
+using System.Collections.Generic;
+using System.Linq;
+using WalletWasabi.Helpers;
+
+namespace WalletWasabi.Crypto.ZeroKnowledge.LinearRelation
+{
+ public class Knowledge
+ {
+ public Knowledge(Statement statement, ScalarVector witness)
+ {
+ Guard.NotNull(nameof(statement), statement);
+ Guard.NotNullOrEmpty(nameof(witness), witness);
+ Guard.True($"{nameof(witness)} size does not match {nameof(statement)}.{nameof(statement.Equations)}", witness.Count() == statement.Equations.First().Generators.Count());
+
+ // don't try to prove something which isn't true
+ foreach (var equation in statement.Equations)
+ {
+ Guard.True($"{nameof(witness)} is incorrect with respect to {nameof(equation)}.{nameof(equation.PublicPoint)}", equation.PublicPoint == witness * equation.Generators);
+ }
+
+ Statement = statement;
+ Witness = witness;
+ }
+
+ public Statement Statement { get; }
+ public ScalarVector Witness { get; }
+
+ public IEnumerable<ScalarVector> RespondToChallenge(Scalar challenge, IEnumerable<ScalarVector> allSecretNonces)
+ {
+ // allSecretNonces should have the same dimension as the equation matrix
+ Guard.NotNullOrEmpty(nameof(allSecretNonces), allSecretNonces);
+ var n = Statement.Equations.First().Generators.Count();
+ Guard.True(nameof(allSecretNonces), allSecretNonces.All(x => x.Count() == n));
+
+ return Statement.Equations.Zip(allSecretNonces, (equation, secretNonces) => equation.Respond(Witness, secretNonces, challenge));
+ }
+ }
+}

ADD
WalletWasabi/Crypto/ZeroKnowledge/LinearRelation/Statement.cs
+using NBitcoin.Secp256k1;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using WalletWasabi.Helpers;
+
+namespace WalletWasabi.Crypto.ZeroKnowledge.LinearRelation
+{
+ public class Statement
+ {
+ public Statement(IEnumerable<Equation> equations)
+ {
+ // The equation matrix should not be jagged
+ Guard.NotNullOrEmpty(nameof(equations), equations);
+ var n = equations.First().Generators.Count();
+ Guard.True(nameof(equations), equations.All(e => e.Generators.Count() == n));
+
+ foreach (var generator in equations.SelectMany(equation => equation.Generators))
+ {
+ Guard.NotNull(nameof(generator), generator);
+ }
+
+ Equations = equations;
+ }
+
+ public IEnumerable<Equation> Equations { get; }
+
+ public bool CheckVerificationEquation(GroupElementVector publicNonces, Scalar challenge, IEnumerable<ScalarVector> allResponses)
+ {
+ // 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());
+ CheckDimesions(allResponses);
+
+ return Equations.Zip(publicNonces, allResponses, (equation, R, s) => equation.Verify(R, challenge, s)).All(x => x);
+ }
+
+ public GroupElementVector SimulatePublicNonces(Scalar challenge, IEnumerable<ScalarVector> allGivenResponses)
+ {
+ // The responses matrix should match the generators in the equations and
+ CheckDimesions(allGivenResponses);
+
+ return new GroupElementVector(Enumerable.Zip(Equations, allGivenResponses, (e, r) => e.Simulate(challenge, r)));
+ }
+
+ private void CheckDimesions(IEnumerable<ScalarVector> allResponses)
+ {
+ if (Equations.Count() != allResponses.Count() ||
+ Enumerable.Zip(Equations, allResponses).Any(x => x.First.Generators.Count() != x.Second.Count()))
+ {
+ throw new ArgumentException("The number of responses and the number of generators in the equations do not match.");
+ }
+ }
+ }
+}

Add LinearRelation.{Statement,Knowledge} classes

These classes implement the generalized linear relation Sigma protocol, proving
knowledge of a witness that satisfies a system of equations (implemented by the
internal Equation class).