Address by address
MODIFY
WalletWasabi.Bench/ExtPubKeyExplorer.cs
WalletWasabi.Bench/ExtPubKeyExplorer.cs
@@ -14,9 +14,6 @@ namespace WalletWasabi.Benck
[RPlotExporter, RankColumn]
public class SearchingUnusedAddresses
{
- [Params(21)]
- public int ChunkSize;
-
private List<FilterModel> _filters;
[GlobalSetup]
@@ -31,10 +28,9 @@ namespace WalletWasabi.Benck
[Benchmark]
public void FindFirstUnusedKey()
{
- var extPubKey = ExtPubKey.Parse("tpubDHATEWfRGN6UyE9TMGASsojBxrvWsaDc6zuVDiiAspjJrHsUUuR7eV7KyFM8RYtAqHnTjqBd7BigU4qy1CeAdkHw3Y4ocmT63DUsKVEwgWu");
- var explorer = new ExtPubKeyExplorer(extPubKey, _filters, ChunkSize);
- var index = explorer.GetIndexFirstUnusedKey();
- Console.WriteLine($"first index: m/84'/0'/0'/0/{index}");
+ var extPubKey = ExtPubKey.Parse("tpubDESeudcLbEHBoH8iw6mL284PXoe2TVmGa3MdQ2gSAkkMj9d1P88LB8wEbVYpigwzurDmDSRsGMKkUsH6vx1anBDCMRzha4YucJfCvEy6z6B");
+ var explorer = new ExtPubKeyExplorer(extPubKey, _filters);
+ var index = explorer.UnusedKeys().First();
}
}
}
\ No newline at end of file

MODIFY
WalletWasabi.Tests/ExtPubKeyExplorerTests.cs
WalletWasabi.Tests/ExtPubKeyExplorerTests.cs
@@ -21,7 +21,7 @@ namespace WalletWasabi.Tests
var mnemonic = new Mnemonic("abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about");
_extKey = mnemonic.DeriveExtKey();
- _extPubKey = _extKey.Derive(new KeyPath("m/84'/0'/0'/1")).Neuter();
+ _extPubKey = _extKey.Derive(new KeyPath("m/84'/0'/0'/1/0")).Neuter();
}
[Fact]
@@ -33,8 +33,8 @@ namespace WalletWasabi.Tests
var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
- var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
- Assert.Equal(0, unusedKeyIndex);
+ var unusedKeyIndex = explorer.UnusedKeys().First();
+ Assert.Equal(DerivateScript(0u), unusedKeyIndex);
}
[Fact]
@@ -47,8 +47,8 @@ namespace WalletWasabi.Tests
var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
- var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
- Assert.Equal(20, unusedKeyIndex);
+ var unusedKeyIndex = explorer.UnusedKeys().First();
+ Assert.Equal(DerivateScript(20u), unusedKeyIndex);
}
[Fact]
@@ -61,8 +61,8 @@ namespace WalletWasabi.Tests
var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
- var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
- Assert.Equal(999, unusedKeyIndex);
+ var unusedKeyIndex = explorer.UnusedKeys().First();
+ Assert.Equal(DerivateScript(999), unusedKeyIndex);
}
[Fact]
@@ -77,8 +77,8 @@ namespace WalletWasabi.Tests
var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
- var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
- Assert.Equal(30, unusedKeyIndex);
+ var unusedKeyIndex = explorer.UnusedKeys().First();
+ Assert.Equal(DerivateScript(30), unusedKeyIndex);
}
[Fact]
@@ -93,8 +93,8 @@ namespace WalletWasabi.Tests
var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
- var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
- Assert.Equal(1_000, unusedKeyIndex);
+ var unusedKeyIndex = explorer.UnusedKeys().First();
+ Assert.Equal(DerivateScript(1_000), unusedKeyIndex);
}
[Fact]
@@ -104,8 +104,8 @@ namespace WalletWasabi.Tests
var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
- var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
- Assert.Equal(25_000, unusedKeyIndex);
+ var unusedKeyIndex = explorer.UnusedKeys().First();
+ Assert.Equal(DerivateScript(25_000), unusedKeyIndex);
}
[Fact]
@@ -117,8 +117,8 @@ namespace WalletWasabi.Tests
filters.Add(FilterModel.FromStream(file, 0));
var extPubKey = ExtPubKey.Parse("tpubDESeudcLbEHBoH8iw6mL284PXoe2TVmGa3MdQ2gSAkkMj9d1P88LB8wEbVYpigwzurDmDSRsGMKkUsH6vx1anBDCMRzha4YucJfCvEy6z6B");
- var explorer = new ExtPubKeyExplorer(extPubKey, filters, 3);
- var index = explorer.GetIndexFirstUnusedKey();
+ var explorer = new ExtPubKeyExplorer(extPubKey, filters);
+ var index = explorer.UnusedKeys().First();
Console.WriteLine($"first index: m/84'/0'/0'/0/{index}");
// Review: The Wallet file indicates that the first Locked index is 48, however increasing the chunkSize makes the
// method to return wrong index.
@@ -154,5 +154,10 @@ namespace WalletWasabi.Tests
}
return scripts;
}
+
+ private IEnumerable<byte> DerivateScript(uint index)
+ {
+ return _extPubKey.Derive(index).PubKey.WitHash.ScriptPubKey.ToCompressedBytes();
+ }
}
}
\ No newline at end of file

MODIFY
WalletWasabi/Services/ExtPubKeyExplorer.cs
WalletWasabi/Services/ExtPubKeyExplorer.cs
@@ -12,26 +12,12 @@ namespace WalletWasabi.Services
{
private readonly FilterModel[] _filters;
- // Indicates how many scripts to try each time. The default value is 21
- public const int DefaultChunkSize = 21;
- private const int BufferCount = 10;
private ExtPubKey _extPubKey;
- private ArraySegment<byte[]>[] _buffers = new ArraySegment<byte[]>[BufferCount];
- private int _curBufferIndex = 0;
private IEnumerator<byte[]> _generator;
- private int _chunkSize;
public ExtPubKeyExplorer(ExtPubKey extPubKey, IEnumerable<FilterModel> filters)
- : this(extPubKey, filters, DefaultChunkSize)
- {}
-
- public ExtPubKeyExplorer(ExtPubKey extPubKey, IEnumerable<FilterModel> filters, int chunkSize)
{
_extPubKey = extPubKey;
- _chunkSize = chunkSize;
- var mainBuffer = new byte[BufferCount * _chunkSize][];
- for(var i=0; i < BufferCount; i++)
- _buffers[i] = new ArraySegment<byte[]>(mainBuffer, i * _chunkSize, _chunkSize);
_generator = DerivateNext().GetEnumerator();
_filters = filters.Where(x=>x.Filter != null).ToArray();
@@ -39,81 +25,29 @@ namespace WalletWasabi.Services
throw new ArgumentException(nameof(filters), "There is not filter to match.");
}
- private (int, ArraySegment<byte[]>) FindLastMatchingChunk()
+ public IEnumerable<byte[]> UnusedKeys()
{
- var offset = 0;
- var lastOffset = 0;
- var scriptChunk = GetChunkOfScripts();
- var lastMatchingChunk = scriptChunk;
while(true)
{
- if(!Match(scriptChunk))
- return (lastOffset, lastMatchingChunk);
-
- lastMatchingChunk = scriptChunk;
- lastOffset = offset;
- offset += _chunkSize;
- scriptChunk = GetChunkOfScripts();
- }
- }
-
- public int GetIndexFirstUnusedKey()
- {
- var (absoluteOffset, lastMatchingCunck) = FindLastMatchingChunk();
-
- var arr = lastMatchingCunck.Array;
- var begin= lastMatchingCunck.Offset;
- var size = lastMatchingCunck.Count;
-
- while(size > 0)
- {
- var mid = (size+1) / 2;
- var rest = size-mid;
-
- var lh = new ArraySegment<byte[]>(arr, begin, mid);
- var rh = new ArraySegment<byte[]>(arr, begin + mid, rest);
-
- if(!Match(lh)) break;
- var frh = (rest > 0) ? Match(rh) : true;
-
- if(frh)
- {
- begin += mid;
- size = rest;
- }
- else
- {
- size = mid;
- }
+ _generator.MoveNext();
+ var cur = _generator.Current;
+ if(!Match(cur))
+ yield return cur;
}
-
- return absoluteOffset + (begin - lastMatchingCunck.Offset);
}
- private bool Match(ArraySegment<byte[]> chunk)
+ private bool Match(byte[] script)
{
var used = false;
foreach (var filterModel in _filters)
{
- used = filterModel.Filter.MatchAny(chunk, filterModel.FilterKey);
+ used = filterModel.Filter.Match(script, filterModel.FilterKey);
if (used)
return true;
}
return false;
}
- private ArraySegment<byte[]> GetChunkOfScripts()
- {
- var buffer = _buffers[_curBufferIndex % BufferCount];
- for(var i=0; i<_chunkSize; i++)
- {
- _generator.MoveNext();
- buffer[i] = _generator.Current;
- }
- _curBufferIndex++;
- return buffer;
- }
-
private IEnumerable<byte[]> DerivateNext()
{
var i = 0u;

Address by address