Tolerate zero scalar gracefully.
MODIFY
WalletWasabi.Tests/UnitTests/Crypto/ZeroKnowledge/ZkExponentTests.cs
WalletWasabi.Tests/UnitTests/Crypto/ZeroKnowledge/ZkExponentTests.cs
using NBitcoin.Secp256k1;
using System;
using System.Collections.Generic;
+using System.Linq;
using System.Text;
using WalletWasabi.Crypto;
using WalletWasabi.Crypto.Randomness;
@@ -11,7 +12,35 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
{
public class ZkExponentTests
{
- public static readonly Scalar LargestScalarOverflow = new Scalar(uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue);
+ public static readonly Scalar ScalarLargestOverflow = new Scalar(uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue, uint.MaxValue);
+ public static readonly Scalar ScalarN = EC.N;
+ public static readonly Scalar ScalarEcnPlusOne = EC.N + Scalar.One;
+ public static readonly Scalar ScalarEcnMinusOne = EC.N + Scalar.One.Negate(); // Largest non-overflown scalar.
+ public static readonly Scalar ScalarLarge = new Scalar(int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue);
+ public static readonly Scalar ScalarZero = Scalar.Zero;
+ public static readonly Scalar ScalarOne = Scalar.One;
+ public static readonly Scalar ScalarTwo = new Scalar(2);
+ public static readonly Scalar ScalarThree = new Scalar(3);
+ public static readonly Scalar ScalarEcnc = EC.NC;
+
+ public static IEnumerable<Scalar> GetScalars(Func<Scalar, bool> predicate)
+ {
+ var scalars = new List<Scalar>
+ {
+ ScalarLargestOverflow,
+ ScalarN,
+ ScalarEcnPlusOne,
+ ScalarEcnMinusOne,
+ ScalarLarge,
+ ScalarZero,
+ ScalarOne,
+ ScalarTwo,
+ ScalarThree,
+ ScalarEcnc
+ };
+
+ return scalars.Where(predicate);
+ }
[Theory]
[InlineData(1)]
@@ -21,17 +50,29 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
[InlineData(short.MaxValue)]
[InlineData(int.MaxValue)]
[InlineData(uint.MaxValue)]
- public void VerifySimpleProof(uint scalarSeed)
+ public void End2EndVerifiesSimpleProof(uint scalarSeed)
{
var exponent = new Scalar(scalarSeed);
- var gen = new Scalar(2) * GroupElement.G;
- var p = exponent * gen;
- var proof = ZkProver.CreateProof(exponent, p, gen);
- Assert.True(ZkVerifier.Verify(proof, p, gen));
+ var generator = GroupElement.G;
+ var publicPoint = exponent * generator;
+ var proof = ZkProver.CreateProof(exponent, publicPoint, generator);
+ Assert.True(ZkVerifier.Verify(proof, publicPoint, generator));
+ }
+
+ [Fact]
+ public void End2EndVerifiesExponents()
+ {
+ foreach (var exponent in GetScalars(x => !x.IsOverflow && !x.IsZero))
+ {
+ var generator = GroupElement.G;
+ var publicPoint = exponent * generator;
+ var proof = ZkProver.CreateProof(exponent, publicPoint, generator);
+ Assert.True(ZkVerifier.Verify(proof, publicPoint, generator));
+ }
}
[Fact]
- public void VerifiesFalse()
+ public void VerifiesToFalse()
{
// Even if the challenge is correct, because the public input in the hash is right,
// if the final response is not valid wrt the verification equation,
@@ -160,7 +201,7 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
// Exponent cannot overflow.
Assert.ThrowsAny<ArgumentException>(() => ZkProver.CreateProof(EC.N, EC.N * GroupElement.G, GroupElement.G));
- Assert.ThrowsAny<ArgumentException>(() => ZkProver.CreateProof(LargestScalarOverflow, LargestScalarOverflow * GroupElement.G, GroupElement.G));
+ Assert.ThrowsAny<ArgumentException>(() => ZkProver.CreateProof(ScalarLargestOverflow, ScalarLargestOverflow * GroupElement.G, GroupElement.G));
}
[Fact]
@@ -179,5 +220,28 @@ namespace WalletWasabi.Tests.UnitTests.Crypto.ZeroKnowledge
// Public point should not be equal to the random point of the proof.
Assert.ThrowsAny<InvalidOperationException>(() => ZkVerifier.Verify(proof, GroupElement.G, GroupElement.Ga));
}
+
+ [Fact]
+ public void RandomOverflow()
+ {
+ var mockRandom = new MockRandom();
+ foreach (var scalar in GetScalars(x => x.IsOverflow))
+ {
+ mockRandom.GetScalarResults.Add(scalar);
+
+ Assert.ThrowsAny<InvalidOperationException>(() => ZkProver.CreateProof(Scalar.One, Scalar.One * GroupElement.G, GroupElement.G, mockRandom));
+ }
+ }
+
+ [Fact]
+ public void RandomZero()
+ {
+ var mockRandom = new MockRandom();
+ mockRandom.GetScalarResults.Add(Scalar.Zero);
+ // Don't tolerate if the second zero scalar random is received.
+ mockRandom.GetScalarResults.Add(Scalar.Zero);
+
+ Assert.ThrowsAny<InvalidOperationException>(() => ZkProver.CreateProof(Scalar.One, Scalar.One * GroupElement.G, GroupElement.G, mockRandom));
+ }
}
}

MODIFY
WalletWasabi/Crypto/Randomness/MockRandom.cs
WalletWasabi/Crypto/Randomness/MockRandom.cs
@@ -9,6 +9,7 @@ namespace WalletWasabi.Crypto.Randomness
public class MockRandom : WasabiRandom
{
public List<byte[]> GetBytesResults { get; } = new List<byte[]>();
+ public List<Scalar> GetScalarResults { get; } = new List<Scalar>();
public override void GetBytes(byte[] output)
{
@@ -28,5 +29,19 @@ namespace WalletWasabi.Crypto.Randomness
{
throw new NotImplementedException();
}
+
+ public override Scalar GetScalar()
+ {
+ if (GetScalarResults.Any())
+ {
+ var first = GetScalarResults.First();
+ GetScalarResults.RemoveFirst();
+ return first;
+ }
+ else
+ {
+ return base.GetScalar();
+ }
+ }
}
}

MODIFY
WalletWasabi/Crypto/Randomness/WasabiRandom.cs
WalletWasabi/Crypto/Randomness/WasabiRandom.cs
@@ -36,7 +36,7 @@ namespace WalletWasabi.Crypto.Randomness
return random;
}
- public Scalar GetScalar()
+ public virtual Scalar GetScalar()
{
Scalar randomScalar;
int overflow;

MODIFY
WalletWasabi/Crypto/ZeroKnowledge/ZkProver.cs
WalletWasabi/Crypto/ZeroKnowledge/ZkProver.cs
@@ -9,7 +9,7 @@ namespace WalletWasabi.Crypto.ZeroKnowledge
{
public static class ZkProver
{
- public static ZkExponentProof CreateProof(Scalar exponent, GroupElement publicPoint, GroupElement generator)
+ public static ZkExponentProof CreateProof(Scalar exponent, GroupElement publicPoint, GroupElement generator, WasabiRandom? random = null)
{
Guard.False($"{nameof(exponent)}.{nameof(exponent.IsOverflow)}", exponent.IsOverflow);
Guard.False($"{nameof(exponent)}.{nameof(exponent.IsZero)}", exponent.IsZero);
@@ -20,12 +20,7 @@ namespace WalletWasabi.Crypto.ZeroKnowledge
throw new InvalidOperationException($"{nameof(publicPoint)} != {nameof(exponent)} * {nameof(generator)}");
}
- using var secureRandom = new SecureRandom();
- Scalar randomScalar = Scalar.Zero;
- while (randomScalar == Scalar.Zero)
- {
- randomScalar = secureRandom.GetScalar();
- }
+ var randomScalar = GetNonZeroRandomScalar(random);
var randomPoint = randomScalar * generator;
var challenge = ZkChallenge.Build(publicPoint, randomPoint);
@@ -33,5 +28,53 @@ namespace WalletWasabi.Crypto.ZeroKnowledge
return new ZkExponentProof(randomPoint, response);
}
+
+ private static Scalar GetNonZeroRandomScalar(WasabiRandom? random = null)
+ {
+ var disposeRandom = false;
+ if (random is null)
+ {
+ disposeRandom = true;
+ random = new SecureRandom();
+ }
+
+ try
+ {
+ Scalar randomScalar = Scalar.Zero;
+ var gotZero = false;
+
+ while (randomScalar == Scalar.Zero)
+ {
+ randomScalar = random.GetScalar();
+
+ // We can tolerate zero scalar only once.
+ // Its probability is null to get it even once, but getting it twice is a catastrophe.
+ if (randomScalar == Scalar.Zero)
+ {
+ if (gotZero)
+ {
+ throw new InvalidOperationException("Something is wrong with the random generation. It should not return zero scalar twice in a row.");
+ }
+ else
+ {
+ gotZero = true;
+ }
+ }
+ }
+
+ if (randomScalar.IsOverflow)
+ {
+ throw new InvalidOperationException("Something is wrong with the random generation. It should not return overflown scalar.");
+ }
+ return randomScalar;
+ }
+ finally
+ {
+ if (disposeRandom)
+ {
+ (random as IDisposable)?.Dispose();
+ }
+ }
+ }
}
}

Tolerate zero scalar gracefully.