Replace with more efficient function
MODIFY
WalletWasabi.Tests/ExtPubKeyExplorerTests.cs
WalletWasabi.Tests/ExtPubKeyExplorerTests.cs
@@ -31,81 +31,73 @@ namespace WalletWasabi.Tests
FilterModel.FromHeightlessLine("000000000000de90e633e1b1330859842795d39018d033044e8b003e8cbf58e4:050a2f58828c9820642769ae320a40", 0)
};
- var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
+ var unusedKeyIndex = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, _extPubKey.GetWif(Network.Main), filters).First().ScriptPubKey.ToCompressedBytes();
- var unusedKeyIndex = explorer.UnusedKeys().First();
- Assert.Equal(DerivateScript(0u), unusedKeyIndex);
+ Assert.Equal(DerivateScript(true, 0), unusedKeyIndex);
}
[Fact]
public void ShouldFindUnsedKeyFirstChunk()
{
var filters = new[]{
- CreateFiltersWith(GetScripts(0, 10)),
- CreateFiltersWith(GetScripts(10, 10))
+ CreateFiltersWith(GetScripts(false, 0, 10)),
+ CreateFiltersWith(GetScripts(false, 10, 10))
};
- var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
+ var unusedKeyIndex = ExtPubKeyExplorer.GetUnusedBech32Keys(1, false, _extPubKey.GetWif(Network.Main), filters).First().ScriptPubKey.ToCompressedBytes();
- var unusedKeyIndex = explorer.UnusedKeys().First();
- Assert.Equal(DerivateScript(20u), unusedKeyIndex);
+ Assert.Equal(DerivateScript(false, 20), unusedKeyIndex);
}
[Fact]
public void ShouldFindUnsedKeyAtTheEndOfFirstChunk()
{
var filters = new[]{
- CreateFiltersWith(GetScripts(0, 500)),
- CreateFiltersWith(GetScripts(500, 499))
+ CreateFiltersWith(GetScripts(true, 0, 500)),
+ CreateFiltersWith(GetScripts(true, 500, 499))
};
- var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
-
- var unusedKeyIndex = explorer.UnusedKeys().First();
- Assert.Equal(DerivateScript(999), unusedKeyIndex);
+ var unusedKeyIndex = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, _extPubKey.GetWif(Network.Main), filters).First().ScriptPubKey.ToCompressedBytes();
+ Assert.Equal(DerivateScript(true, 999), unusedKeyIndex);
}
[Fact]
public void ShouldFindUnsedKeyAnywhereFirstChunk()
{
var filters = new[]{
- CreateFiltersWith(GetScripts(0, 1)),
- CreateFiltersWith(GetScripts(0, 2)),
- CreateFiltersWith(GetScripts(0, 27)),
- CreateFiltersWith(GetScripts(27, 3)),
+ CreateFiltersWith(GetScripts(true, 0, 1)),
+ CreateFiltersWith(GetScripts(true, 0, 2)),
+ CreateFiltersWith(GetScripts(true, 0, 27)),
+ CreateFiltersWith(GetScripts(true, 27, 3)),
};
- var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
+ var unusedKeyIndex = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, _extPubKey.GetWif(Network.Main), filters).First().ScriptPubKey.ToCompressedBytes();
- var unusedKeyIndex = explorer.UnusedKeys().First();
- Assert.Equal(DerivateScript(30), unusedKeyIndex);
+ Assert.Equal(DerivateScript(true, 30), unusedKeyIndex);
}
[Fact]
public void ShouldFindUnsedKeySecondChunk()
{
var filters = new[]{
- CreateFiltersWith(GetScripts( 0, 250)),
- CreateFiltersWith(GetScripts(250, 250)),
- CreateFiltersWith(GetScripts(500, 250)),
- CreateFiltersWith(GetScripts(750, 250))
+ CreateFiltersWith(GetScripts(true, 0, 250)),
+ CreateFiltersWith(GetScripts(true, 250, 250)),
+ CreateFiltersWith(GetScripts(true, 500, 250)),
+ CreateFiltersWith(GetScripts(true, 750, 250))
};
- var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
+ var unusedKeyIndex = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, _extPubKey.GetWif(Network.Main), filters).First().ScriptPubKey.ToCompressedBytes();
- var unusedKeyIndex = explorer.UnusedKeys().First();
- Assert.Equal(DerivateScript(1_000), unusedKeyIndex);
+ Assert.Equal(DerivateScript(true, 1_000), unusedKeyIndex);
}
[Fact]
public void ShouldFindUnsedKeyFarFarAway()
{
- var filters = Enumerable.Range(0, 100).Select(x => CreateFiltersWith(GetScripts(x * 250, 250))).ToArray();
-
- var explorer = new ExtPubKeyExplorer(_extPubKey, filters);
+ var filters = Enumerable.Range(0, 100).Select(x => CreateFiltersWith(GetScripts(true, x * 250, 250))).ToArray();
- var unusedKeyIndex = explorer.UnusedKeys().First();
- Assert.Equal(DerivateScript(25_000), unusedKeyIndex);
+ var unusedKeyIndex = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, _extPubKey.GetWif(Network.Main), filters).First().ScriptPubKey.ToCompressedBytes();
+ Assert.Equal(DerivateScript(true, 25_000), unusedKeyIndex);
}
private FilterModel CreateFiltersWith(IEnumerable<byte[]> scripts)
@@ -127,21 +119,23 @@ namespace WalletWasabi.Tests
};
}
- private byte[][] GetScripts(int offset, int count)
+ private byte[][] GetScripts(bool isInternal, int offset, int count)
{
+ var change = isInternal ? 1 : 0;
var scripts = new byte[count][];
for (var i = 0; i < count; i++)
{
- var pubKey = _extPubKey.Derive((uint)(offset + i)).PubKey;
+ var pubKey = _extPubKey.Derive(change, false).Derive(offset + i, false).PubKey;
var bytes = pubKey.WitHash.ScriptPubKey.ToCompressedBytes();
scripts[i] = bytes;
}
return scripts;
}
- private IEnumerable<byte> DerivateScript(uint index)
+ private IEnumerable<byte> DerivateScript(bool isInternal, int index)
{
- return _extPubKey.Derive(index).PubKey.WitHash.ScriptPubKey.ToCompressedBytes();
+ var change = isInternal ? 1 : 0;
+ return _extPubKey.Derive(change, false).Derive(index, false).PubKey.WitHash.ScriptPubKey.ToCompressedBytes();
}
}
}

MODIFY
WalletWasabi/Services/ExtPubKeyExplorer.cs
WalletWasabi/Services/ExtPubKeyExplorer.cs
@@ -10,56 +10,70 @@ namespace WalletWasabi.Services
{
public class ExtPubKeyExplorer
{
- public ExtPubKey ExtPubKey { get; set; }
-
- public FilterModel[] Filters { get; }
- public IEnumerator<byte[]> Generator { get; set; }
-
/// <summary>
- /// WARNING: ONLY CHECKS CONFIRMED AND BECH32 KEYPATHS
+ /// WARNING: ONLY CHECKS CONFIRMED KEYPATHS
/// </summary>
- public ExtPubKeyExplorer(ExtPubKey extPubKey, IEnumerable<FilterModel> filters)
+ public static IEnumerable<BitcoinWitPubKeyAddress> GetUnusedBech32Keys(int count, bool isInternal, BitcoinExtPubKey bitcoinExtPubKey, IEnumerable<FilterModel> filters)
{
- ExtPubKey = extPubKey;
+ var change = isInternal ? 1 : 0;
+ var filterArray = filters.ToArray();
- Generator = DerivateNext().GetEnumerator();
- Filters = filters.Where(x => x.Filter != null).ToArray();
- if (Filters.Length == 0)
- throw new ArgumentException(nameof(filters), "There is no filter to match.");
+ var startingKey = 0; // Where to start getting keys one by one.
+ int i = 0;
+ while (true)
+ {
+ if (Match(bitcoinExtPubKey, change, i, filterArray, out _))
+ {
+ startingKey = i + 1;
+ if (i == 0)
+ {
+ i = 1;
}
-
- public IEnumerable<byte[]> UnusedKeys()
+ else
{
- while (true)
+ i *= 2;
+ }
+ }
+ else
{
- Generator.MoveNext();
- var cur = Generator.Current;
- if (!Match(cur))
- yield return cur;
+ break;
}
}
- private bool Match(byte[] script)
+ i = startingKey;
+ int returnedNum = 0;
+ while (true)
{
- var used = false;
- foreach (var filterModel in Filters)
+ if (!Match(bitcoinExtPubKey, change, i, filterArray, out PubKey pubKey))
{
- used = filterModel.Filter.Match(script, filterModel.FilterKey);
- if (used)
- return true;
+ yield return pubKey.GetSegwitAddress(bitcoinExtPubKey.Network);
+ returnedNum++;
+ if (returnedNum >= count)
+ {
+ yield break;
+ }
+ }
+
+ i++;
}
- return false;
}
- private IEnumerable<byte[]> DerivateNext()
+ public static bool Match(BitcoinExtPubKey bitcoinExtPubKey, int change, int i, FilterModel[] filterArray, out PubKey pubKey)
{
- var i = 0u;
- while (true)
+ KeyPath path = new KeyPath($"{change}/{i}");
+ pubKey = bitcoinExtPubKey.ExtPubKey.Derive(path).PubKey;
+ byte[] bytes = pubKey.WitHash.ScriptPubKey.ToCompressedBytes();
+
+ foreach (var filterModel in filterArray)
+ {
+ bool? matchFoundNow = filterModel.Filter?.Match(bytes, filterModel.FilterKey);
+ if (matchFoundNow is true)
{
- var pubKey = ExtPubKey.Derive(i++).PubKey;
- var bytes = pubKey.WitHash.ScriptPubKey.ToCompressedBytes();
- yield return bytes;
+ return true;
}
}
+
+ return false;
+ }
}
}

Replace with more efficient function https://github.com/zkSNACKs/WalletWasabi/pull/1192