Enforce range proof constraints in dependency graph
MODIFY
WalletWasabi.Tests/UnitTests/WabiSabi/Client/CredentialDependencyTests.cs
WalletWasabi.Tests/UnitTests/WabiSabi/Client/CredentialDependencyTests.cs
@@ -4,6 +4,7 @@ using System.Collections.Immutable;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
+using WalletWasabi.WabiSabi;
using WalletWasabi.WabiSabi.Client.CredentialDependencies;
using Xunit;
@@ -253,6 +254,8 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData("21,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1", "11,5 10,5 10,5 10,6", 42)]
[InlineData("21,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1", "10,5 10,5 10,5 10,6", 43)]
[InlineData("21,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1", "10,5 10,5 10,5 10,5", 42)]
+ [InlineData("1,255 1,255 1,255 1,255", "4,1", 7)]
+ [InlineData("13,255 1,255 1,255 1,255 1,255 1,255", "3,255 3,255 3,255 3,255 3,255 3,255", 17)]
public async void ResolveCredentialDependenciesAsync(string inputs, string outputs, int finalVertexCount)
{
// blackbox tests (apart from finalVertexCount, which leaks
@@ -287,6 +290,10 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
var balance = graph.Balance(node, credentialType);
Assert.True(balance >= 0);
+ if (credentialType == CredentialType.Vsize)
+ {
+ Assert.InRange(balance, 0, ProtocolConstants.MaxVsizeCredentialValue);
+ }
Assert.Equal(0, node.MaxInDegree);
Assert.Equal(node.MaxInDegree, graph.InDegree(node, credentialType));
@@ -315,6 +322,10 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
var balance = graph.Balance(node, credentialType);
Assert.True(balance >= 0);
+ if (credentialType == CredentialType.Vsize)
+ {
+ Assert.InRange(balance, 0, ProtocolConstants.MaxVsizeCredentialValue);
+ }
Assert.Equal(DependencyGraph.K, node.MaxInDegree);
Assert.Equal(node.MaxInDegree, graph.InDegree(node, credentialType));
@@ -324,6 +335,12 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
}
}
+ // Ensure that vsize credentials do not exceed the range proof width
+ foreach (var edge in graph.EdgeSets[CredentialType.Vsize].Successors.Values.SelectMany(x => x))
+ {
+ Assert.InRange<ulong>(edge.Value, 0, ProtocolConstants.MaxVsizeCredentialValue);
+ }
+
// TODO add InlineData param for max depth?
// TODO assert max depth < ceil(log count)?

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialEdgeSet.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialEdgeSet.cs
@@ -8,6 +8,9 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
public record CredentialEdgeSet
{
public CredentialType CredentialType { get; init; }
+
+ public long MaxCredentialValue { get; init; }
+
public ImmutableDictionary<RequestNode, ImmutableHashSet<CredentialDependency>> Predecessors { get; init; } = ImmutableDictionary.Create<RequestNode, ImmutableHashSet<CredentialDependency>>();
public ImmutableDictionary<RequestNode, ImmutableHashSet<CredentialDependency>> Successors { get; init; } = ImmutableDictionary.Create<RequestNode, ImmutableHashSet<CredentialDependency>>();
public ImmutableDictionary<RequestNode, long> EdgeBalances { get; init; } = ImmutableDictionary.Create<RequestNode, long>();
@@ -167,17 +170,37 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
// Drain values into a reissuance request (towards the center of the graph).
public CredentialEdgeSet DrainReissuance(RequestNode reissuance, IEnumerable<RequestNode> nodes)
- // The amount for the edge is always determined by the dicharged
+ // The amount for the edge is always determined by the discharged
// nodes' values, since we only add reissuance nodes to reduce the
// number of charged nodes overall.
=> nodes.Aggregate(this, (edgeSet, node) => edgeSet.DrainReissuance(reissuance, node));
private CredentialEdgeSet DrainReissuance(RequestNode reissuance, RequestNode node)
- => Balance(node) switch
{
- > 0 and long value => AddEdge(node, reissuance, (ulong)value),
- < 0 and long value => AddEdge(reissuance, node, (ulong)(-1 * value)).AddZeroEdges(reissuance, node),
+ var value = Balance(node);
+ if (Math.Abs(Balance(reissuance) + value) > MaxCredentialValue)
+ {
+ // Avoid creating graphs that cannot be executed due to range
+ // proof constraints. Technically up to K * MaxCredentialValue
+ // is possible, but being stricter keeps it simple by avoiding
+ // edge cases, and is likely to be good enough in practice as
+ // this only really applies to vsize credentials and those
+ // should almost always have a significant surplus, so this
+ // should result in few strictly unnecessary reissuance
+ // requests overall.
+ return this;
+ }
+ else if ( value > 0 )
+ {
+ return AddEdge(node, reissuance, (ulong)value);
+ }
+ else if (value < 0 )
+ {
+ return AddEdge(reissuance, node, (ulong)(-1 * value)).AddZeroEdges(reissuance, node);
+ }
+ else if (InDegree(reissuance) == 0)
+ {
// Due to opportunistic draining of lower priority credential
// types when defining a reissuance node for higher priority
// ones, the amount is not guaranteed to be zero, avoid adding
@@ -185,8 +208,11 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
// Always satisfiy zero credential from new reissuance nodes
// (it's guaranteed to be possible) to avoid crossing edges,
// even if there's no balance to discharge.
- _ => (InDegree(reissuance) == 0 ? AddZeroEdges(reissuance, node) : this),
- };
+ return AddZeroEdges(reissuance, node);
+ } else {
+ return this;
+ }
+ }
public CredentialEdgeSet AddZeroEdges(RequestNode src, RequestNode dst)
=> RemainingInDegree(dst) switch

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/DependencyGraph.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/DependencyGraph.cs
@@ -24,8 +24,8 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
// Internal properties used to keep track of effective values and edges
public ImmutableSortedDictionary<CredentialType, CredentialEdgeSet> EdgeSets { get; init; } = ImmutableSortedDictionary<CredentialType, CredentialEdgeSet>.Empty
- .Add(CredentialType.Amount, new() { CredentialType = CredentialType.Amount })
- .Add(CredentialType.Vsize, new() { CredentialType = CredentialType.Vsize });
+ .Add(CredentialType.Amount, new() { CredentialType = CredentialType.Amount, MaxCredentialValue = ProtocolConstants.MaxAmountPerAlice })
+ .Add(CredentialType.Vsize, new() { CredentialType = CredentialType.Vsize, MaxCredentialValue = ProtocolConstants.MaxVsizeCredentialValue });
public long Balance(RequestNode node, CredentialType credentialType) => EdgeSets[credentialType].Balance(node);

MODIFY
WalletWasabi/WabiSabi/ProtocolContants.cs
WalletWasabi/WabiSabi/ProtocolContants.cs
@@ -4,6 +4,7 @@ namespace WalletWasabi.WabiSabi
{
public const int CredentialNumber = 2;
public const long MaxAmountPerAlice = 4_300_000_000_000L;
+ public const long MaxVsizeCredentialValue = 255;
public const string WabiSabiProtocolIdentifier = "WabiSabi_v1.0";
public const string DomainStrobeSeparator = "domain-separator";

Enforce range proof constraints in dependency graph