Find first unused address with binary search
ADD
WalletWasabi.Bench/ExtPubKeyExplorer.cs
+using System;
+using System.Linq;
+using System.Collections.Generic;
+using NBitcoin;
+using BenchmarkDotNet.Attributes;
+using BenchmarkDotNet.Running;
+using WalletWasabi.Services;
+using WalletWasabi.Backend.Models;
+
+namespace WalletWasabi.Benck
+{
+ [ClrJob(baseline: true), CoreJob]
+ [RPlotExporter, RankColumn]
+ public class SearchingUnusedAddresses
+ {
+ private ExtPubKey _extPubKey;
+ private FilterModel[] _filters;
+
+ [Params(100, 1_000)]
+ public int USED_ADDRS;
+
+ [Params(2_000, 5_000)]
+ public int OUTUPS;
+
+ [Params(20_000)]
+ public int FILTERS;
+
+ [GlobalSetup]
+ public void Setup()
+ {
+ var random = new Random(Seed:145);
+
+ var mnemonic = new Mnemonic("abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about");
+ var extKey = mnemonic.DeriveExtKey();
+ _extPubKey = extKey.Derive(new KeyPath("m/84'/0'/1")).Neuter();
+ var myScripts = new byte[USED_ADDRS][];
+ var keyBuffer = new byte[32];
+ for(var i=0; i<USED_ADDRS; i++)
+ {
+ myScripts[i] = _extPubKey.Derive((uint)i).PubKey.GetSegwitAddress(Network.Main).ScriptPubKey.ToBytes();
+ }
+
+ var lastUsed = 0;
+ _filters = new FilterModel[FILTERS];
+ for(var f=0; f < FILTERS; f++)
+ {
+ random.NextBytes(keyBuffer);
+ var blockHash = new uint256(keyBuffer);
+
+ var builder = new GolombRiceFilterBuilder()
+ .SetKey(blockHash)
+ .SetP(20);
+
+ var itemsInFilter = new List<byte[]>();
+ for (var j = 0; j < OUTUPS; j++)
+ {
+ var data = new byte[random.Next(20, 30)];
+ random.NextBytes(data);
+ itemsInFilter.Add(data);
+ }
+ var doIHaveCoinsInTheBlock = random.Next(0, 99) < 10;
+ if(doIHaveCoinsInTheBlock && lastUsed < USED_ADDRS)
+ {
+ itemsInFilter.Add(myScripts[lastUsed++]);
+ }
+ builder.AddEntries(itemsInFilter);
+ _filters[f] = new FilterModel{
+ BlockHeight = f,
+ BlockHash = new uint256(blockHash),
+ Filter = builder.Build()
+ };
+ }
+ }
+
+ [Benchmark]
+ public BitcoinWitPubKeyAddress[] FindFirstUnusedKey()
+ {
+ var result = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, new BitcoinExtPubKey(_extPubKey, Network.Main), _filters);
+ return result?.ToArray();
+ }
+ }
+}
\ No newline at end of file

ADD
WalletWasabi.Bench/WalletWasabi.Bench.csproj
+<Project Sdk="Microsoft.NET.Sdk">
+
+ <PropertyGroup>
+ <OutputType>Exe</OutputType>
+ <TargetFramework>netcoreapp2.2</TargetFramework>
+ </PropertyGroup>
+
+ <ItemGroup>
+ <PackageReference Include="BenchmarkDotNet" Version="0.11.3" />
+ <PackageReference Include="NBitcoin" Version="4.1.1.82" />
+ </ItemGroup>
+
+ <ItemGroup>
+ <ProjectReference Include="..\WalletWasabi\WalletWasabi.csproj" />
+ </ItemGroup>
+</Project>

MODIFY
WalletWasabi/Services/ExtPubKeyExplorer.cs
WalletWasabi/Services/ExtPubKeyExplorer.cs
@@ -12,65 +12,59 @@ namespace WalletWasabi.Services
{
public static IEnumerable<BitcoinWitPubKeyAddress> GetUnusedBech32Keys(int count, bool isInternal, BitcoinExtPubKey bitcoinExtPubKey, IEnumerable<FilterModel> filters)
{
- var change = isInternal ? 1 : 0;
+ var change = isInternal ? 1u : 0u;
var filterArray = filters.ToArray();
- var startingKey = 0; // Where to start getting keys one by one.
- int i = 0;
- while (true)
+ const int MaxScanDepth = 1_000;
+ var path = new KeyPath($"{change}/0");
+ var scripts = new byte[MaxScanDepth][];
+ for(var i=0; i<MaxScanDepth; i++)
{
- if (Match(bitcoinExtPubKey, change, i, filterArray, out _))
- {
- startingKey = i + 1;
- if (i == 0)
- {
- i = 1;
- }
- else
- {
- i *= 2;
- }
- }
- else
- {
- break;
- }
+ var pubKey = bitcoinExtPubKey.ExtPubKey.Derive(change).PubKey;
+ var bytes = pubKey.WitHash.ScriptPubKey.ToCompressedBytes();
+ scripts[i] = bytes;
}
- i = startingKey;
- int returnedNum = 0;
- while (true)
+ var found = -1;
+ var begin=0;
+ var size = MaxScanDepth-1;
+ while(found>-1 && size > 0)
{
- if (!Match(bitcoinExtPubKey, change, i, filterArray, out PubKey pubKey))
- {
- yield return pubKey.GetSegwitAddress(bitcoinExtPubKey.Network);
- returnedNum++;
- if (returnedNum >= count)
- {
- yield break;
- }
- }
+ var mid = size / 2;
+ var lh = new ArraySegment<byte[]>(scripts, begin, mid);
+ var rh = new ArraySegment<byte[]>(scripts, begin + mid, mid);
- i++;
+ var flh = false;
+ var frh = false;
+ foreach (var filterModel in filterArray.Where(x=>x.Filter != null))
+ {
+ flh = filterModel.Filter.MatchAny(lh, filterModel.FilterKey);
+ if (flh) break;
}
+ if(!flh)
+ {
+ return scripts.Skip(begin).Take(count)
+ .Select(x=>new Script(x).WitHash.GetAddress(bitcoinExtPubKey.Network))
+ .Cast<BitcoinWitPubKeyAddress>();
}
- public static bool Match(BitcoinExtPubKey bitcoinExtPubKey, int change, int i, FilterModel[] filterArray, out PubKey pubKey)
+ foreach (var filterModel in filterArray.Where(x=>x.Filter != null))
{
- KeyPath path = new KeyPath($"{change}/{i}");
- pubKey = bitcoinExtPubKey.ExtPubKey.Derive(path).PubKey;
- byte[] bytes = pubKey.WitHash.ScriptPubKey.ToCompressedBytes();
+ frh = filterModel.Filter.MatchAny(rh, filterModel.FilterKey);
+ if (frh) break;
+ }
- foreach (var filterModel in filterArray)
+ if(flh && !frh)
{
- bool? matchFoundNow = filterModel.Filter?.Match(bytes, filterModel.FilterKey);
- if (matchFoundNow is true)
+ size /= 2;
+ }
+ else if( flh && frh)
{
- return true;
+ begin = mid;
}
}
- return false;
+ return null;
}
}
}

Find first unused address with binary search