Repository: btcpayserver/btcpayserver (csharp)

Issue:
[Bug]: Gateway Timeout (504) on Invoice Creation because Mempool.space is down
### What is your BTCPay version?

 © BTCPay Server v1.12.3+f23078df1 

### How did you deploy BTCPay Server?

I enabeld the BTC onchain store wallet (which I had prior disabled because of high fees) and then created an invoice in my store. This loaded until it hit a nginx proxy timeout which resulted in this message:

![grafik](https://github.com/btcpayserver/btcpayserver/assets/1374810/eba81f5c-05f6-4bd8-ada7-0f5df6b580b4)


### What happened?

504 Gateway Timeout

It seems that this problem coexists with a downtime of the mempool.space website.
This shouldn't happen as we have a fallback with the internal BTC node.

### How did you encounter this bug?

see above

### Relevant log output

```shell
none
```


### What browser do you use?

Firefox

### Additional information

none

### Are you sure this is a bug report?

- [X] I confirm this is a bug report

Pull request:
The fee provider ended up glued with a hardcoded factory. This PR:
* removes this glue and uses the DI to register fee provider for a network. (allows plugins to add their own fee providers, for any network
* Add a 10 second timeout to mempoolspace fee fetching as they are slow at times (many reports of downtime issues within past 24 hours)
Fixes #5641.

Patch:
diff --git a/BTCPayServer/Services/Fees/MempoolSpaceFeeProvider.cs b/BTCPayServer/Services/Fees/MempoolSpaceFeeProvider.cs
index 85cd5d5821..90e53db9fb 100644
--- a/BTCPayServer/Services/Fees/MempoolSpaceFeeProvider.cs
+++ b/BTCPayServer/Services/Fees/MempoolSpaceFeeProvider.cs
@@ -3,21 +3,26 @@
 using System.Collections.Generic;
 using System.Linq;
 using System.Net.Http;
+using System.Runtime.InteropServices;
+using System.Text.RegularExpressions;
 using System.Threading;
 using System.Threading.Tasks;
 using AngleSharp.Dom;
+using ExchangeSharp;
 using Microsoft.Extensions.Caching.Memory;
 using NBitcoin;
+using Org.BouncyCastle.Asn1.X509;
+using YamlDotNet.Core.Tokens;
 
 namespace BTCPayServer.Services.Fees;
 
 public class MempoolSpaceFeeProvider(
-    IMemoryCache MemoryCache,
-    string CacheKey,
-    IHttpClientFactory HttpClientFactory,
-    bool Testnet) : IFeeProvider
+    IMemoryCache memoryCache,
+    string cacheKey,
+    IHttpClientFactory httpClientFactory,
+    bool testnet) : IFeeProvider
 {
-    private readonly string ExplorerLink = Testnet switch
+    private string ExplorerLink = testnet switch
     {
         true => "https://mempool.space/testnet/api/v1/fees/recommended",
         false => "https://mempool.space/api/v1/fees/recommended"
@@ -27,50 +32,87 @@ public async Task<FeeRate> GetFeeRateAsync(int blockTarget = 20)
     {
         var result = await GetFeeRatesAsync();
 
-        return result.TryGetValue(blockTarget, out var feeRate)
-            ? feeRate
-            :
-            //try get the closest one
-            result[result.Keys.MinBy(key => Math.Abs(key - blockTarget))];
+        return InterpolateOrBound(result, blockTarget);
+            
+    }
+    
+    internal static FeeRate InterpolateOrBound(BlockFeeRate[] ordered, int target)
+    {
+        (BlockFeeRate lb, BlockFeeRate hb) = (ordered[0], ordered[^1]);
+        target = Math.Clamp(target, lb.Blocks, hb.Blocks);
+        for (int i = 0; i < ordered.Length; i++)
+        {
+            if (ordered[i].Blocks > lb.Blocks && ordered[i].Blocks <= target)
+                lb = ordered[i];
+            if (ordered[i].Blocks < hb.Blocks && ordered[i].Blocks >= target)
+                hb = ordered[i];
+        }
+        if (hb.Blocks == lb.Blocks)
+            return hb.FeeRate;
+        var a = (decimal)(target - lb.Blocks) / (decimal)(hb.Blocks - lb.Blocks);
+        return new FeeRate((1 - a) * lb.FeeRate.SatoshiPerByte + a * hb.FeeRate.SatoshiPerByte);
     }
 
-    public Task<Dictionary<int, FeeRate>> GetFeeRatesAsync()
+    internal async Task<BlockFeeRate[]> GetFeeRatesAsync()
     {
-        return MemoryCache.GetOrCreateAsync(CacheKey, async entry =>
+        try
         {
-            entry.AbsoluteExpirationRelativeToNow = TimeSpan.FromMinutes(5);
-            var client = HttpClientFactory.CreateClient(nameof(MempoolSpaceFeeProvider));
-            using var result = await client.GetAsync(ExplorerLink);
-            result.EnsureSuccessStatusCode();
-            var recommendedFees = await result.Content.ReadAsAsync<Dictionary<string, decimal>>();
-            var feesByBlockTarget = new Dictionary<int, FeeRate>();
-            foreach ((var feeId, decimal value) in recommendedFees)
+            return  (await  memoryCache.GetOrCreateAsync(cacheKey, async entry =>
             {
-                var target = feeId switch
-                {
-                    "fastestFee" => 1,
-                    "halfHourFee" => 3,
-                    "hourFee" => 6,
-                    "economyFee" when recommendedFees.TryGetValue("minimumFee", out var minFee) && minFee == value => 144,
-                    "economyFee" => 72,
-                    "minimumFee" => 144,
-                    _ => -1
-                };
-                feesByBlockTarget.TryAdd(target, new FeeRate(RandomizeByPercentage(value, 10)));
-            }
-            return feesByBlockTarget;
-        })!;
+                entry.AbsoluteExpirationRelativeToNow = TimeSpan.FromMinutes(5);
+                return await GetFeeRatesCore();
+            }))!;
+        }
+        catch (Exception)
+        {
+            memoryCache.Remove(cacheKey);
+            throw;
+        }
+    }
+    internal record BlockFeeRate(int Blocks, FeeRate FeeRate);
+    async Task<BlockFeeRate[]> GetFeeRatesCore()
+    {
+        var client = httpClientFactory.CreateClient(nameof(MempoolSpaceFeeProvider));
+        using var cts = new CancellationTokenSource(TimeSpan.FromSeconds(10));
+        using var result = await client.GetAsync(ExplorerLink, cts.Token);
+        result.EnsureSuccessStatusCode();
+        var recommendedFees = await result.Content.ReadAsAsync<Dictionary<string, decimal>>();
+        var r = new List<BlockFeeRate>();
+        foreach ((var feeId, decimal value) in recommendedFees)
+        {
+            var target = feeId switch
+            {
+                "fastestFee" => 1,
+                "halfHourFee" => 3,
+                "hourFee" => 6,
+                "economyFee" when recommendedFees.TryGetValue("minimumFee", out var minFee) && minFee == value => 144,
+                "economyFee" => 72,
+                "minimumFee" => 144,
+                _ => -1
+            };
+            r.Add(new(target, new FeeRate(value)));
+        }
+        var ordered = r.OrderBy(k => k.Blocks).ToArray();
+        for (var i = 0; i < ordered.Length; i++)
+        {
+            // Randomize a bit
+            ordered[i] = ordered[i] with { FeeRate = new FeeRate(RandomizeByPercentage(ordered[i].FeeRate.SatoshiPerByte, 10m)) };
+            if (i > 0) // Make sure feerate always increase
+                ordered[i] = ordered[i] with { FeeRate = FeeRate.Max(ordered[i - 1].FeeRate, ordered[i].FeeRate) };
+        }
+        return ordered;
     }
     
-    static decimal RandomizeByPercentage(decimal value, int percentage)
+    internal static decimal RandomizeByPercentage(decimal value, decimal percentage)
     {
-        decimal range = value * percentage / 100m;
-        var res = value + range * (Random.Shared.NextDouble() < 0.5 ? -1 : 1);
-
+        if (value is 1)
+            return 1;
+        decimal range = (value * percentage) / 100m;
+        var res = value + (range * 2.0m) * ((decimal)(Random.Shared.NextDouble() - 0.5));
         return res switch
         {
             < 1m => 1m,
-            > 850m => 2000m,
+            > 2000m => 2000m,
             _ => res
         };
     }


Test patch:
diff --git a/BTCPayServer.Tests/FastTests.cs b/BTCPayServer.Tests/FastTests.cs
index 9ec8fb8621..cbe84c61db 100644
--- a/BTCPayServer.Tests/FastTests.cs
+++ b/BTCPayServer.Tests/FastTests.cs
@@ -28,6 +28,7 @@
 using BTCPayServer.Rating;
 using BTCPayServer.Services;
 using BTCPayServer.Services.Apps;
+using BTCPayServer.Services.Fees;
 using BTCPayServer.Services.Invoices;
 using BTCPayServer.Services.Labels;
 using BTCPayServer.Services.Rates;
@@ -159,6 +160,38 @@ public void CanParseDecimals()
             Assert.Equal("Test", data.FromAsset);
         }
 
+        [Fact]
+        public void CanInterpolateOrBound()
+        {
+            var testData = new ((int Blocks, decimal Fee)[] Data, int Target, decimal Expected) []
+            {
+                ([(0, 0m), (10, 100m)], 5, 50m),
+                ([(50, 0m), (100, 100m)], 5, 0.0m),
+                ([(50, 0m), (100, 100m)], 101, 100.0m),
+                ([(50, 100m), (50, 100m)], 101, 100.0m),
+                ([(50, 0m), (100, 100m)], 75, 50m),
+                ([(0, 0m), (50, 50m), (100, 100m)], 75, 75m),
+                ([(0, 0m), (500, 50m), (1000, 100m)], 750, 75m),
+                ([(0, 0m), (500, 50m), (1000, 100m)], 100, 10m),
+                ([(0, 0m), (100, 100m)], 80, 80m),
+                ([(0, 0m), (100, 100m)], 25, 25m),
+            };
+            foreach (var t in testData)
+            {
+                var actual = MempoolSpaceFeeProvider.InterpolateOrBound(t.Data.Select(t => new MempoolSpaceFeeProvider.BlockFeeRate(t.Blocks, new FeeRate(t.Fee))).ToArray(), t.Target);
+                Assert.Equal(new FeeRate(t.Expected), actual);
+            }
+        }
+        [Fact]
+        public void CanRandomizeByPercentage()
+        {
+            var generated = Enumerable.Range(0, 1000).Select(_ => MempoolSpaceFeeProvider.RandomizeByPercentage(100.0m, 10.0m)).ToArray();
+            Assert.Empty(generated.Where(g => g < 90m));
+            Assert.Empty(generated.Where(g => g > 110m));
+            Assert.NotEmpty(generated.Where(g => g < 91m));
+            Assert.NotEmpty(generated.Where(g => g > 109m));
+        }
+
         private void CanParseDecimalsCore(string str, decimal expected)
         {
             var d = JsonConvert.DeserializeObject<LedgerEntryData>(str);
diff --git a/BTCPayServer.Tests/ThirdPartyTests.cs b/BTCPayServer.Tests/ThirdPartyTests.cs
index a98d554355..6d3e5cb3ec 100644
--- a/BTCPayServer.Tests/ThirdPartyTests.cs
+++ b/BTCPayServer.Tests/ThirdPartyTests.cs
@@ -10,6 +10,7 @@
 using BTCPayServer.Controllers;
 using BTCPayServer.Data;
 using BTCPayServer.Models.StoreViewModels;
+using BTCPayServer.Models.WalletViewModels;
 using BTCPayServer.Rating;
 using BTCPayServer.Services.Fees;
 using BTCPayServer.Services.Rates;
@@ -92,7 +93,38 @@ public async Task CanQueryMempoolFeeProvider()
                     isTestnet);
                 var rates = await mempoolSpaceFeeProvider.GetFeeRatesAsync();
                 Assert.NotEmpty(rates);
-                await mempoolSpaceFeeProvider.GetFeeRateAsync(20);
+                
+                
+                var recommendedFees =
+                    await Task.WhenAll(new[]
+                        {
+                            TimeSpan.FromMinutes(10.0), TimeSpan.FromMinutes(60.0), TimeSpan.FromHours(6.0),
+                            TimeSpan.FromHours(24.0),
+                        }.Select(async time =>
+                        {
+                            try
+                            {
+                                var result = await mempoolSpaceFeeProvider.GetFeeRateAsync(
+                                    (int)Network.Main.Consensus.GetExpectedBlocksFor(time));
+                                return new WalletSendModel.FeeRateOption()
+                                {
+                                    Target = time,
+                                    FeeRate = result.SatoshiPerByte
+                                };
+                            }
+                            catch (Exception)
+                            {
+                                return null;
+                            }
+                        })
+                        .ToArray());
+                //ENSURE THESE ARE LOGICAL
+                Assert.True(recommendedFees[0].FeeRate >= recommendedFees[1].FeeRate, $"{recommendedFees[0].Target}:{recommendedFees[0].FeeRate} >= {recommendedFees[1].Target}:{recommendedFees[1].FeeRate}");
+                Assert.True(recommendedFees[1].FeeRate >= recommendedFees[2].FeeRate, $"{recommendedFees[1].Target}:{recommendedFees[1].FeeRate} >= {recommendedFees[2].Target}:{recommendedFees[2].FeeRate}");
+                Assert.True(recommendedFees[2].FeeRate >= recommendedFees[3].FeeRate, $"{recommendedFees[2].Target}:{recommendedFees[2].FeeRate} >= {recommendedFees[3].Target}:{recommendedFees[3].FeeRate}");
+                
+                
+                
             }
         }
         [Fact]