First non-optimized version
ADD
IndexMain.bin
IndexMain.bin
Binary files /dev/null and b/IndexMain.bin differ

MODIFY
WalletWasabi.Bench/ExtPubKeyExplorer.cs
WalletWasabi.Bench/ExtPubKeyExplorer.cs
@@ -6,6 +6,7 @@ using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using WalletWasabi.Services;
using WalletWasabi.Backend.Models;
+using System.IO;
namespace WalletWasabi.Benck
{
@@ -13,70 +14,25 @@ namespace WalletWasabi.Benck
[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;
+ private List<FilterModel> _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()
- };
- }
+ _filters = new List<FilterModel>(500_000);
+ using(var file = File.OpenRead("IndexTestNet.bin"))
+ while(file.Position < file.Length)
+ _filters.Add(FilterModel.FromStream(file, 0));
}
[Benchmark]
- public BitcoinWitPubKeyAddress[] FindFirstUnusedKey()
+ public void FindFirstUnusedKey()
{
- var result = ExtPubKeyExplorer.GetUnusedBech32Keys(1, true, new BitcoinExtPubKey(_extPubKey, Network.Main), _filters);
- return result?.ToArray();
+ var extPubKey = ExtPubKey.Parse("tpubD6NzVbkrYhZ4YcNe2sjvpcdPzEgZuXQyWSnVjxmYQLCXAce7UKVtbftWaUGyCKrdXMy2uWy7DcTqMTXJWmgFJZd2T1BzHRPm7cHvzBTmeed");
+ var scriptProvider = new ScriptPubKeyProvider(extPubKey);
+ var explorer = new ExtPubKeyExplorer(scriptProvider, _filters);
+ var index = explorer.GetIndexFirstUnusedKey();
+ Console.WriteLine($"first index: m/84'/0'/0'/0/{index}");
}
}
}
\ No newline at end of file

ADD
WalletWasabi.Tests/ExtPubKeyExplorerTests.cs
+using System;
+using System.Linq;
+using System.Collections.Generic;
+using Xunit;
+using NBitcoin;
+using WalletWasabi.Services;
+using WalletWasabi.Backend.Models;
+using System.IO;
+
+namespace WalletWasabi.Tests
+{
+ public class ExtPubKeyExplorerTests
+ {
+ private ExtKey _extKey;
+ private ScriptPubKeyProvider _scriptProvider;
+ private Random _random;
+
+ public ExtPubKeyExplorerTests()
+ {
+ _random = new Random(Seed:6439);
+
+ var mnemonic = new Mnemonic("abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about");
+ _extKey = mnemonic.DeriveExtKey();
+ }
+
+ [Fact]
+ public void ShouldFindNeverUsedKey()
+ {
+ var extPubKey = _extKey.Derive(new KeyPath("m/84'/0'/1")).Neuter();
+ var scriptProvider = new ScriptPubKeyProvider(extPubKey);
+ var filters = new[] {
+ FilterModel.FromHeightlessLine("000000000000de90e633e1b1330859842795d39018d033044e8b003e8cbf58e4:050a2f58828c9820642769ae320a40", 0)
+ };
+
+ var explorer = new ExtPubKeyExplorer(scriptProvider, filters);
+
+ var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
+ Assert.Equal(0, unusedKeyIndex);
+ }
+
+ [Fact]
+ public void ShouldFindUnsedKeyFirstChunk()
+ {
+ var extPubKey = _extKey.Derive(new KeyPath("m/84'/0'/1")).Neuter();
+ var scriptProvider = new ScriptPubKeyProvider(extPubKey);
+ var filters = new []{
+ CreateFiltersWith(scriptProvider.GetScripts(0, 10)),
+ CreateFiltersWith(scriptProvider.GetScripts(10, 10))
+ };
+
+ var explorer = new ExtPubKeyExplorer(scriptProvider, filters);
+
+ var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
+ Assert.Equal(20, unusedKeyIndex);
+ }
+
+ [Fact]
+ public void ShouldFindUnsedKeyAtTheEndOfFirstChunk()
+ {
+ var extPubKey = _extKey.Derive(new KeyPath("m/84'/0'/1")).Neuter();
+ var scriptProvider = new ScriptPubKeyProvider(extPubKey);
+ var filters = new []{
+ CreateFiltersWith(scriptProvider.GetScripts(0, 500)),
+ CreateFiltersWith(scriptProvider.GetScripts(500, 499))
+ };
+
+ var explorer = new ExtPubKeyExplorer(scriptProvider, filters);
+
+ var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
+ Assert.Equal(999, unusedKeyIndex);
+ }
+
+ [Fact]
+ public void ShouldFindUnsedKeySecondChunk()
+ {
+ var extPubKey = _extKey.Derive(new KeyPath("m/84'/0'/1")).Neuter();
+ var scriptProvider = new ScriptPubKeyProvider(extPubKey);
+ var filters = new []{
+ CreateFiltersWith(scriptProvider.GetScripts( 0, 250)),
+ CreateFiltersWith(scriptProvider.GetScripts(250, 250)),
+ CreateFiltersWith(scriptProvider.GetScripts(500, 250)),
+ CreateFiltersWith(scriptProvider.GetScripts(750, 250))
+ };
+
+ var explorer = new ExtPubKeyExplorer(scriptProvider, filters);
+
+ var unusedKeyIndex = explorer.GetIndexFirstUnusedKey();
+ Assert.Equal(1_000, unusedKeyIndex);
+ }
+
+ [Fact]
+ public void RealWorldCase()
+ {
+ var filters = new List<FilterModel>(500_000);
+ using(var file = File.OpenRead("/home/lontivero/GitHub/WalletWasabi/WalletWasabi.Bench/IndexTestNet.bin"))
+ while(file.Position < file.Length)
+ filters.Add(FilterModel.FromStream(file, 0));
+
+ var extPubKey = ExtPubKey.Parse("tpubD6NzVbkrYhZ4YcNe2sjvpcdPzEgZuXQyWSnVjxmYQLCXAce7UKVtbftWaUGyCKrdXMy2uWy7DcTqMTXJWmgFJZd2T1BzHRPm7cHvzBTmeed");
+ var scriptProvider = new ScriptPubKeyProvider(extPubKey);
+ var explorer = new ExtPubKeyExplorer(scriptProvider, filters);
+ var index = explorer.GetIndexFirstUnusedKey();
+ Console.WriteLine($"first index: m/84'/0'/0'/0/{index}");
+ }
+
+
+ private FilterModel CreateFiltersWith(IEnumerable<byte[]> scripts)
+ {
+ var keyBuffer = new byte[32];
+ _random.NextBytes(keyBuffer);
+ var blockHash = new uint256(keyBuffer);
+
+ var builder = new GolombRiceFilterBuilder()
+ .SetKey(blockHash)
+ .SetP(20);
+
+ builder.AddEntries(scripts);
+ return new FilterModel{
+ BlockHeight = 0,
+ BlockHash = new uint256(blockHash),
+ Filter = builder.Build()
+ };
+ }
+ }
+}
\ No newline at end of file

MODIFY
WalletWasabi/Services/ExtPubKeyExplorer.cs
WalletWasabi/Services/ExtPubKeyExplorer.cs
@@ -8,63 +8,126 @@ using WalletWasabi.Backend.Models;
namespace WalletWasabi.Services
{
- public static class ExtPubKeyExplorer
+ public class ScriptPubKeyProvider
{
- public static IEnumerable<BitcoinWitPubKeyAddress> GetUnusedBech32Keys(int count, bool isInternal, BitcoinExtPubKey bitcoinExtPubKey, IEnumerable<FilterModel> filters)
+ public const int ChunkSize = 1_000;
+ private const int ChunkCount = 3;
+ private const int DefaultBufferSize = ChunkCount * ChunkSize;
+ private ExtPubKey _extPubKey;
+ private byte[][] _buffer;
+ private int _availableScriptCount = 0;
+ private IEnumerator<byte[]> _generator;
+
+ public int ScriptBufferSize => _buffer.Length;
+
+ public ScriptPubKeyProvider(ExtPubKey extPubKey)
{
- var change = isInternal ? 1u : 0u;
- var filterArray = filters.ToArray();
+ _extPubKey = extPubKey;
+ _buffer = new byte[DefaultBufferSize][];
+ _generator = GenerateNext().GetEnumerator();
+ }
- const int MaxScanDepth = 1_000;
- var path = new KeyPath($"{change}/0");
- var scripts = new byte[MaxScanDepth][];
- for(var i=0; i<MaxScanDepth; i++)
+ public ArraySegment<byte[]> GetScripts(int offset, int count=100)
{
- var pubKey = bitcoinExtPubKey.ExtPubKey.Derive(change).PubKey;
+ if(count > ChunkSize)
+ throw new ArgumentNullException(nameof(count));
+
+ offset %= DefaultBufferSize;
+ _availableScriptCount %= DefaultBufferSize;
+ if(offset + count > DefaultBufferSize)
+ throw new ArgumentNullException(nameof(count));
+
+ while(offset + count > _availableScriptCount)
+ {
+ _generator.MoveNext();
+ _buffer[_availableScriptCount++] = _generator.Current;
+ }
+ return new ArraySegment<byte[]>(_buffer, offset, count);
+ }
+
+ private IEnumerable<byte[]> GenerateNext()
+ {
+ var i = 0u;
+ while(true)
+ {
+ var pubKey = _extPubKey.Derive(i++).PubKey;
var bytes = pubKey.WitHash.ScriptPubKey.ToCompressedBytes();
- scripts[i] = bytes;
+ yield return bytes;
+ }
+ }
}
- var found = -1;
- var begin=0;
- var size = MaxScanDepth-1;
- while(found>-1 && size > 0)
+ public class ExtPubKeyExplorer
{
- var mid = size / 2;
- var lh = new ArraySegment<byte[]>(scripts, begin, mid);
- var rh = new ArraySegment<byte[]>(scripts, begin + mid, mid);
+ private readonly ScriptPubKeyProvider _scriptProvider;
+ private readonly FilterModel[] _filters;
- var flh = false;
- var frh = false;
- foreach (var filterModel in filterArray.Where(x=>x.Filter != null))
+ public ExtPubKeyExplorer(ScriptPubKeyProvider scriptProvider, IEnumerable<FilterModel> filters)
{
- flh = filterModel.Filter.MatchAny(lh, filterModel.FilterKey);
- if (flh) break;
+ _scriptProvider = scriptProvider;
+ _filters = filters.Where(x=>x.Filter != null).ToArray();
+ if(_filters.Length == 0)
+ throw new ArgumentException(nameof(filters), "There is not filter to match.");
}
- if(!flh)
+
+ private (int, ArraySegment<byte[]>) FindLastMatchingChunk()
+ {
+ var offset = 0;
+ var lastOffset = 0;
+ var scriptChunk = _scriptProvider.GetScripts(offset, 1_000);
+ var lastMatchingChunk = scriptChunk;
+ while(true)
{
- return scripts.Skip(begin).Take(count)
- .Select(x=>new Script(x).WitHash.GetAddress(bitcoinExtPubKey.Network))
- .Cast<BitcoinWitPubKeyAddress>();
+ foreach (var filterModel in _filters)
+ {
+ var matching = filterModel.Filter.MatchAny(scriptChunk, filterModel.FilterKey);
+ if(!matching)
+ return (lastOffset, lastMatchingChunk);
+ }
+ lastMatchingChunk = scriptChunk;
+ lastOffset = offset;
+ offset += 1_000;
+ scriptChunk = _scriptProvider.GetScripts(offset, 1_000);
+ }
}
- foreach (var filterModel in filterArray.Where(x=>x.Filter != null))
+ public int GetIndexFirstUnusedKey()
{
- frh = filterModel.Filter.MatchAny(rh, filterModel.FilterKey);
- if (frh) break;
- }
+ var (absoluteOffset, lastMatchingCunck) = FindLastMatchingChunk();
+
+ var begin= lastMatchingCunck.Offset;
+ var size = lastMatchingCunck.Count;
+
+ while(size > 0)
+ {
+ var mid = (size+1) / 2;
+ var lh = _scriptProvider.GetScripts(begin, mid);
- if(flh && !frh)
+ var flh = true;
+ var frh = true;
+ foreach (var filterModel in _filters)
{
- size /= 2;
+ flh = filterModel.Filter.MatchAny(lh, filterModel.FilterKey);
+ if (flh) break;
}
- else if( flh && frh)
+ if(!flh) break;
+
+ if(size-mid > 0)
+ {
+ var rh = _scriptProvider.GetScripts(begin + mid, size-mid);
+ foreach (var filterModel in _filters)
{
- begin = mid;
+ frh = filterModel.Filter.MatchAny(rh, filterModel.FilterKey);
+ if (frh) break;
}
}
- return null;
+ if( flh && frh) begin += mid;
+ size = mid;
+ }
+
+ var relativeOffset = begin + (((begin % ScriptPubKeyProvider.ChunkSize) != 0) ? 1 : 0);
+ return absoluteOffset + relativeOffset;
}
}
}

First non-optimized version