Apply suggestions from code review
Also refines the edge case condition, which reduces two of the test
graphs by one node in a way that I missed previously.
MODIFY
WalletWasabi.Tests/UnitTests/WabiSabi/Client/CredentialDependencyTests.cs
WalletWasabi.Tests/UnitTests/WabiSabi/Client/CredentialDependencyTests.cs
@@ -200,7 +200,7 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData("1,0 1,0 1,0", "3,0", 5)]
[InlineData("3,0", "1,0 1,0 1,0", 5)]
[InlineData("1,5 1,5 1,5", "3,1", 5)]
- [InlineData("3,5", "1,1 1,1 1,1", 6)] // TODO 5?
+ [InlineData("3,5", "1,1 1,1 1,1", 6)] // Can be improved to 5
[InlineData("3,5", "1,1 1,1", 4)]
[InlineData("4,0", "1,0 1,0 1,0 1,0", 7)]
[InlineData("10,0", "1,0 1,0", 4)]
@@ -209,10 +209,10 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData("10,0", "1,0 1,0 1,0 1,0 1,0", 10)]
[InlineData("10,0", "1,0 1,0 1,0 1,0 1,0 1,0", 12)]
[InlineData("10,0", "1,0 1,0 1,0 1,0 1,0 1,0 1,0 1,0 1,0 1,0", 19)]
- [InlineData("3,0 3,0", "2,0 2,0 2,0", 6)] // not 5 because of insufficient zero creds
+ [InlineData("3,0 3,0", "2,0 2,0 2,0", 5)]
[InlineData("5,0 1,0", "2,0 2,0 2,0", 6)]
[InlineData("2,0 2,0", "3,0", 3)]
- [InlineData("3,0 3,0", "2,0 2,0 1,0", 7)] // not 6 because of uneven amount requiring extra reissuance
+ [InlineData("3,0 3,0", "2,0 2,0 1,0", 6)]
[InlineData("8,0 1,0", "3,0 3,0 3,0", 6)]
[InlineData("8,0 2,0", "3,0 3,0 3,0", 6)]
[InlineData("8,3 1,0", "3,1 3,1 3,1", 6)]
@@ -232,7 +232,7 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData("2,6 2,6", "1,3 1,3 1,3 1,3", 6)]
[InlineData("2,6 2,6", "1,1 1,1 1,1 1,1", 8)]
[InlineData("3,6 1,6", "4,1", 3)]
- [InlineData("3,6 1,6", "2,1 1,1 1,1", 6)] // TODO 5
+ [InlineData("3,6 1,6", "2,1 1,1 1,1", 6)] // Can be improved to 5
[InlineData("3,6 1,6 1,6 1,6", "2,1 2,1 1,1", 7)]
[InlineData("3,6 1,6 1,6 1,6", "2,1 2,1 1,1 1,1", 8)]
[InlineData("3,6 1,6 1,6 1,6", "2,1 2,1 2,1", 7)]
@@ -271,7 +271,8 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
AssertResolvedGraphInvariants(g, inputValues, outputValues);
Assert.Equal(finalVertexCount, g.Vertices.Count);
- // TODO when sum is even, reverse
+ // TODO when sum(in) == sum(out) for all credential types, also
+ // verify the reverse graph can be resolved.
await SimulateAsyncRequests(g);
}
@@ -323,7 +324,8 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
}
}
- // TODO opportunistic draining of vsize credentials - add InlineData param for max depth?
+ // TODO add InlineData param for max depth?
+
// TODO assert max depth < ceil(log count)?
}

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialDependency.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialDependency.cs
namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
- // make private inner class of Graph class?
public class CredentialDependency
{
public CredentialDependency(RequestNode from, RequestNode to, CredentialType credentialType, ulong value)

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialEdgeSet.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialEdgeSet.cs
@@ -20,9 +20,9 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
public int InDegree(RequestNode node) => InEdges(node).Count;
- public int OutDegree(RequestNode node) => OutEdges(node).Where(x => x.Value != 0).Count();
+ public int OutDegree(RequestNode node) => OutEdges(node).Count(x => x.Value != 0);
- public int ZeroOnlyOutDegree(RequestNode node) => OutEdges(node).Where(x => x.Value == 0).Count();
+ public int ZeroOnlyOutDegree(RequestNode node) => OutEdges(node).Count(x => x.Value == 0);
public int RemainingInDegree(RequestNode node) => node.MaxInDegree - InDegree(node);
@@ -36,9 +36,6 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
var edge = new CredentialDependency(from, to, CredentialType, value);
- var predecessors = InEdges(edge.To);
- var successors = OutEdges(edge.From);
-
// Maintain degree invariant (subset of K-regular graph, sort of)
if (RemainingInDegree(edge.To) == 0)
{
@@ -51,6 +48,20 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
throw new InvalidOperationException("Can't add more than k non-zero out edges per node.");
}
+ else if (RemainingOutDegree(edge.From) == 1)
+ {
+ // This is the final out edge for the node edge.From
+ if (Balance(edge.From) - (long)edge.Value > 0)
+ {
+ throw new InvalidOperationException($"Can't add final out edge without discharging positive value (edge value {edge.Value} but node balance is {Balance(edge.From)}).");
+ }
+
+ // If it's the final edge overall for that node, the final balance must be 0
+ if (RemainingInDegree(edge.From) == 0 && Balance(edge.From) - (long)edge.Value != 0)
+ {
+ throw new InvalidOperationException("Can't add final in edge without discharging negative value completely.");
+ }
+ }
}
else
{
@@ -87,23 +98,9 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
}
}
- if (value > 0)
- {
- if (RemainingOutDegree(edge.From) == 1)
- {
- // This is the final out edge for the node edge.From
- if (Balance(edge.From) - (long)edge.Value > 0)
- {
- throw new InvalidOperationException($"Can't add final out edge without discharging positive value (edge value {edge.Value} but node balance is {Balance(edge.From)}).");
- }
- // If it's the final edge overall for that node, the final balance must be 0
- if (RemainingInDegree(edge.From) == 0 && Balance(edge.From) - (long)edge.Value != 0)
- {
- throw new InvalidOperationException("Can't add final in edge without discharging negative value completely.");
- }
- }
- }
+ var predecessors = InEdges(edge.To);
+ var successors = OutEdges(edge.From);
return this with
{

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/DependencyGraph.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/DependencyGraph.cs
@@ -9,15 +9,18 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
public const int K = ProtocolConstants.CredentialNumber;
- public static ImmutableArray<CredentialType> CredentialTypes { get; } = ImmutableArray.Create<CredentialType>(CredentialType.Amount, CredentialType.Vsize);
+ public static IEnumerable<CredentialType> CredentialTypes { get; } = Enum.GetValues<CredentialType>();
- public ImmutableList<RequestNode> Vertices { get; private set; } = ImmutableList<RequestNode>.Empty;
+ public ImmutableList<RequestNode> Vertices { get; init; } = ImmutableList<RequestNode>.Empty;
- public ImmutableList<RequestNode> Inputs { get; private set; } = ImmutableList<RequestNode>.Empty;
+ // The input nodes, in the order they were added
+ public ImmutableList<RequestNode> Inputs { get; init; } = ImmutableList<RequestNode>.Empty;
- public ImmutableList<RequestNode> Outputs { get; private set; } = ImmutableList<RequestNode>.Empty;
+ // The output nodes, in the order they were added
+ public ImmutableList<RequestNode> Outputs { get; init; } = ImmutableList<RequestNode>.Empty;
- public ImmutableList<RequestNode> Reissuances { get; private set; } = ImmutableList<RequestNode>.Empty; // TODO sort
+ // The reissuance nodes, unsorted
+ public ImmutableList<RequestNode> Reissuances { get; init; } = ImmutableList<RequestNode>.Empty;
// Internal properties used to keep track of effective values and edges
public ImmutableSortedDictionary<CredentialType, CredentialEdgeSet> edgeSets { get; init; } = ImmutableSortedDictionary<CredentialType, CredentialEdgeSet>.Empty
@@ -42,23 +45,20 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
/// and may contain additional nodes if reissuance requests are
/// required.</remarks>
public static DependencyGraph ResolveCredentialDependencies(IEnumerable<IEnumerable<ulong>> inputValues, IEnumerable<IEnumerable<ulong>> outputValues)
- {
- return FromValues(inputValues, outputValues).ResolveCredentials();
- }
+ => FromValues(inputValues, outputValues).ResolveCredentials();
public static DependencyGraph FromValues(IEnumerable<IEnumerable<ulong>> inputValues, IEnumerable<IEnumerable<ulong>> outputValues)
{
- if (Enumerable.Concat(inputValues, outputValues).Any(x => x.Count() != CredentialTypes.Length))
+ if (Enumerable.Concat(inputValues, outputValues).Any(x => x.Count() != CredentialTypes.Count()))
{
- throw new ArgumentException($"Number of credential values must be {CredentialTypes.Length}");
+ throw new ArgumentException($"Number of credential values must be {CredentialTypes.Count()}");
}
foreach (var credentialType in CredentialTypes)
{
- // no Sum(Func<ulong, ulong>)) variant
- long credentialValue(IEnumerable<ulong> x) => (long)x.Skip((int)credentialType).First();
+ long credentialTypeValue(IEnumerable<ulong> x) => (long)x.ElementAt((int)credentialType);
- if (inputValues.Sum(credentialValue) < outputValues.Sum(credentialValue))
+ if (inputValues.Sum(credentialTypeValue) < outputValues.Sum(credentialTypeValue))
{
throw new ArgumentException("Overall balance must not be negative.");
}
@@ -105,9 +105,8 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
private (DependencyGraph, RequestNode) AddReissuance()
{
- // TODO insert into reissuance requests property
var node = new RequestNode(Enumerable.Repeat(0L, K), inDegree: K, outDegree: K, zeroOnlyOutDegree: K * (K - 1));
- return ((this with { Reissuances = Reissuances.Add(node) }).AddNode(node), node); // TODO keep sorted by topological order?
+ return ((this with { Reissuances = Reissuances.Add(node) }).AddNode(node), node);
}
/// <summary>Resolve edges for all credential types</summary>
@@ -188,6 +187,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
var edgeSet = g.edgeSets[credentialType];
+ var positive = g.Vertices.Where(v => edgeSet.Balance(v) > 0);
var negative = g.Vertices.Where(v => edgeSet.Balance(v) < 0);
if (!negative.Any())
@@ -195,8 +195,6 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
return g;
}
- var positive = g.Vertices.Where(v => edgeSet.Balance(v) > 0);
-
(var largestMagnitudeNode, var smallMagnitudeNodes, var fanIn) = edgeSet.MatchNodesToDischarge(positive, negative);
var maxCount = (fanIn ? edgeSet.RemainingInDegree(largestMagnitudeNode) : edgeSet.RemainingOutDegree(largestMagnitudeNode));
@@ -217,8 +215,6 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
(g, largestMagnitudeNode) = g.AggregateIntoReissuanceNode(new RequestNode[] { largestMagnitudeNode }, credentialType);
}
- var preReduceSmallNodes = smallMagnitudeNodes;
-
// Reduce the number of small magnitude nodes to the number of edges
// available for use in the largest magnitude node
(g, smallMagnitudeNodes) = g.ReduceNodes(smallMagnitudeNodes, maxCount, credentialType);
@@ -234,7 +230,8 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
var edgeSet = edgeSets[credentialType];
- IEnumerable<RequestNode> negative = Vertices.Where(v => edgeSet.Balance(v) < 0).OrderBy(v => edgeSet.Balance(v));
+ // Evaluate the linq query eagerly since edgeSet is reassigned
+ IEnumerable<RequestNode> negative = Vertices.Where(v => edgeSet.Balance(v) < 0).OrderBy(v => edgeSet.Balance(v)).ToImmutableArray();
if (!negative.Any())
{
@@ -243,45 +240,28 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
var g = this;
- // First special case, handle uniform input values (should be the
- // case for vbyte credentials) more efficiently, by spreading the
- // negative nodes evenly.
-
// Unconstrained nodes have a remaining out degree greater than 1,
// so they can produce arbitary value outputs (final edge must leave
// balance = 0).
// The remaining outdegree > 1 condition is equivalent to == K for
// K=2, so that also implies the positive valued nodes haven't been
- // used for this credential type yet (TODO affinity/avoid crossing?).
- var unconstrainedPositive = Vertices.Where(v => edgeSet.Balance(v) > 0 && edgeSet.RemainingOutDegree(v) > 1).OrderByDescending(v => edgeSet.Balance(v));
+ // used for this credential type yet.
+ var unconstrainedPositive = Vertices.Where(v => edgeSet.Balance(v) > 0 && edgeSet.RemainingOutDegree(v) > 1).OrderByDescending(v => edgeSet.Balance(v)).ToImmutableArray();
+
+ // First special case, if the unconstrained inputs have uniform values (should be the
+ // common case for vbyte credentials)...
if (unconstrainedPositive.Select(v => edgeSet.Balance(v)).Distinct().Count() == 1)
{
- if (edgeSet.Balance(negative.First()) * -1 * (negative.Count() / unconstrainedPositive.Count()) < edgeSet.Balance(unconstrainedPositive.First()))
+ // And if the total amount of the uniform unconstrained nodes is
+ // larger than the negative nodes, with room to spare
+ if (unconstrainedPositive.Count() * edgeSet.Balance(unconstrainedPositive.First()) > -1 * negative.Count() * edgeSet.Balance(negative.First()))
{
- // TODO shuffle? not clear if it will benefit or reduce
- // privacy, need to study it in more detail. The adverserial
- // setting that should be considered is one where the
- // coordinator can delay information and request processing
- // and perform an arbitrary number of blameless round
- // failures while attempting to detect correlations between
- // the timings of the registrations of a single user. Random
- // delays should add noise to this and ideally all clients
- // should aim to have the same fixed baseline delay for
- // their output registrations (something that should almost
- // always be a few times longer than the expected RTT), then
- // output registrations should mostly follow reissuances and
- // be difficult to tell apart based on timing, which should
- // render the ordering irrelevant.
-
+ // Aggregate the negative nodes if they are more numerous.
+ // Reducing to `unconstrainedPositive.Count()` (which can be
+ // significantly larger than K) creates a more balanced
+ // structure for the next special case, or later iterations.
if (negative.Count() > unconstrainedPositive.Count())
{
- // TODO consolidate only lowest depth at each iteration
- // (negative height, i.e. max of distance to terminal output
- // nodes derived from the vertex, 0 for such nodes) nodes
- // first. By only consolidating nodes with the lowest
- // depth a balanced structure will be ensured regardless
- // of prior reissuances potentially creating deeper
- // nodes.
(g, negative) = g.ReduceNodes(negative, unconstrainedPositive.Count(), credentialType);
}
}
@@ -289,9 +269,10 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
edgeSet = g.edgeSets[credentialType];
- // Second special case, more general to the previous one, when for each
- // negative node there is a satisfactory unconstrained positive node
- // (not necessarily all of equal value), discharge via a 1:1 correspondence
+ // Second special case, more general than the previous one.
+ // If negative nodes are all strictly smaller than the corresponding
+ // positive nodes (not necessarily of uniform value), discharge them
+ // in a 1:1 correspondence.
if (negative.Count() <= unconstrainedPositive.Count() && Enumerable.Zip(unconstrainedPositive, negative).All(p => edgeSet.Balance(p.First) + edgeSet.Balance(p.Second) >= 0))
{
g = Enumerable.Zip(unconstrainedPositive, negative).Aggregate(g, (g, p) => g.DrainTerminal(p.First, new RequestNode[] { p.Second }, credentialType));
@@ -309,14 +290,21 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
return (this, nodes);
}
+
// Replace up to k nodes, possibly the entire queue, with a
// single reissuance node which combines their values. The total
// number of items might be less than K but still larger than
// maxCount.
var take = Math.Min(K, nodes.Count());
+
+ // TODO order nodes by depth/height, so that this will produce a
+ // balanced structure. Currently nodes are just merged into a binary
+ // tree in the order given by the enumerable, but this can create an
+ // imbalance if a small magnitude node is a reissuance node left
+ // over from a previous iteration.
(var g, var reissuance) = AggregateIntoReissuanceNode(nodes.Take(take), credentialType);
- var reduced = nodes.Skip(take).Append(reissuance).ToImmutableArray(); // keep enumerable expr size bounded by evaluating eagerly
- return g.ReduceNodes(reduced, maxCount, credentialType);
+
+ return g.ReduceNodes(nodes.Skip(take).Append(reissuance), maxCount, credentialType);
}
private (DependencyGraph, RequestNode) AggregateIntoReissuanceNode(IEnumerable<RequestNode> nodes, CredentialType credentialType)
@@ -350,7 +338,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
// dependencies between different requests, weight credentials
// should often be easily satisfiable with parallel edges to the
// amount credential edges.
- if (CredentialTypes.Contains(credentialType + 1))
+ if (CredentialType.IsDefined(credentialType + 1))
{
// TODO Limit up to a certain height in the graph, no more than
// the initial value, this can sometimes create a deeper graph
@@ -374,14 +362,13 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
private DependencyGraph ResolveZeroCredentials(CredentialType credentialType)
{
- // TODO improve affinity/reduce crossings:
- // resolve 0 credentials in 3 depth first passes, always discharging
- // from remaining in = 0, available zero > 1 nodes.
- // each pass should be iterated several times until reaching a fixed
- // point (no more progress).
- // - discharge only to AvailableZeroOutDegree > 1 nodes (should be 1 per)
- // - discharge to direct descendents even if a net reduction in zero creds
- // - discharge all remaining in degree >1 nodes by topological order
+ // TODO Build edges in parallel to existing ones to reduce
+ // dependencies per request.
+ // This can be done in 3 depth first passes, which all consume nodes
+ // whose remaining in degree is 0 and available zero degree is >0.
+ // - discharge only to AvailableZeroOutDegree >0 nodes (should be at most one such node per donor node)
+ // - discharge to direct descendents even if a net reduction in zero creds because of available zero out degree of 0
+ // - discharge all remaining in degree >0 nodes by topological order
var edgeSet = edgeSets[credentialType];
var unresolvedNodes = Vertices.Where(v => edgeSet.RemainingInDegree(v) > 0 && edgeSet.AvailableZeroOutDegree(v) > 0).OrderByDescending(v => edgeSet.AvailableZeroOutDegree(v));
@@ -396,9 +383,6 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
var providers = Vertices.Where(v => edgeSet.RemainingInDegree(v) == 0 && edgeSet.AvailableZeroOutDegree(v) > 0)
.SelectMany(v => Enumerable.Repeat(v, edgeSet.AvailableZeroOutDegree(v)));
- // TODO discharge iteratively by topological layer, each time applying different filters?
- // intersect with successor set of providers of lower credential type edge set for better affinity?
-
var reduced = unresolvedNodes.SelectMany(v => Enumerable.Repeat(v, edgeSet.RemainingInDegree(v)))
.Zip(providers, (t, f) => new { From = f, To = t })
.Aggregate(this, (g, p) => g.AddZeroCredential(p.From, p.To, credentialType));

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/RequestNode.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/RequestNode.cs
@@ -4,7 +4,6 @@ using WalletWasabi.Helpers;
namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
- // make private inner class of Graph?
public class RequestNode
{
public RequestNode(IEnumerable<long> values, int inDegree, int outDegree, int zeroOnlyOutDegree)
@@ -17,7 +16,6 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
public ImmutableArray<long> Values { get; }
- // TODO ImmutableArray<int> (uint?)
public int MaxInDegree { get; }
public int MaxOutDegree { get; }

Apply suggestions from code review

Also refines the edge case condition, which reduces two of the test
graphs by one node in a way that I missed previously.

Co-authored-by: Lucas Ontivero <lucasontivero@gmail.com>