| | | 1 | | using System.Collections.Concurrent; |
| | | 2 | | using System.Diagnostics.CodeAnalysis; |
| | | 3 | | |
| | | 4 | | namespace NLightning.Infrastructure.Repositories.Memory; |
| | | 5 | | |
| | | 6 | | using Domain.Bitcoin.Interfaces; |
| | | 7 | | using Domain.Bitcoin.ValueObjects; |
| | | 8 | | using Domain.Bitcoin.Wallet.Models; |
| | | 9 | | using Domain.Channels.ValueObjects; |
| | | 10 | | using Domain.Money; |
| | | 11 | | |
| | | 12 | | public class UtxoMemoryRepository : IUtxoMemoryRepository |
| | | 13 | | { |
| | 0 | 14 | | private readonly ConcurrentDictionary<(TxId, uint), UtxoModel> _utxoSet = []; |
| | | 15 | | |
| | | 16 | | public void Add(UtxoModel utxoModel) |
| | 0 | 17 | | { |
| | 0 | 18 | | if (!_utxoSet.TryAdd((utxoModel.TxId, utxoModel.Index), utxoModel)) |
| | 0 | 19 | | throw new InvalidOperationException("Cannot add Utxo"); |
| | 0 | 20 | | } |
| | | 21 | | |
| | | 22 | | public void Spend(UtxoModel utxoModel) |
| | 0 | 23 | | { |
| | 0 | 24 | | _utxoSet.TryRemove((utxoModel.TxId, utxoModel.Index), out _); |
| | 0 | 25 | | } |
| | | 26 | | |
| | | 27 | | public bool TryGetUtxo(TxId txId, uint index, [MaybeNullWhen(false)] out UtxoModel utxoModel) |
| | 0 | 28 | | { |
| | 0 | 29 | | return _utxoSet.TryGetValue((txId, index), out utxoModel); |
| | 0 | 30 | | } |
| | | 31 | | |
| | | 32 | | public LightningMoney GetConfirmedBalance(uint currentBlockHeight) |
| | 0 | 33 | | { |
| | 0 | 34 | | return LightningMoney.Satoshis(_utxoSet.Values |
| | 0 | 35 | | .Where(x => x.BlockHeight + 3 <= currentBlockHeight) |
| | 0 | 36 | | .Sum(x => x.Amount.Satoshi)); |
| | 0 | 37 | | } |
| | | 38 | | |
| | | 39 | | public LightningMoney GetUnconfirmedBalance(uint currentBlockHeight) |
| | 0 | 40 | | { |
| | 0 | 41 | | return LightningMoney.Satoshis(_utxoSet.Values |
| | 0 | 42 | | .Where(x => x.BlockHeight + 3 > currentBlockHeight) |
| | 0 | 43 | | .Sum(x => x.Amount.Satoshi)); |
| | 0 | 44 | | } |
| | | 45 | | |
| | | 46 | | public LightningMoney GetLockedBalance() |
| | 0 | 47 | | { |
| | 0 | 48 | | return LightningMoney.Satoshis(_utxoSet.Values |
| | 0 | 49 | | .Where(x => x.LockedToChannelId is not null) |
| | 0 | 50 | | .Sum(x => x.Amount.Satoshi)); |
| | 0 | 51 | | } |
| | | 52 | | |
| | | 53 | | public void Load(List<UtxoModel> utxoSet) |
| | 0 | 54 | | { |
| | 0 | 55 | | foreach (var utxoModel in utxoSet) |
| | 0 | 56 | | _utxoSet.TryAdd((utxoModel.TxId, utxoModel.Index), utxoModel); |
| | 0 | 57 | | } |
| | | 58 | | |
| | | 59 | | public List<UtxoModel> LockUtxosToSpendOnChannel(LightningMoney requestFundingAmount, ChannelId channelId) |
| | 0 | 60 | | { |
| | | 61 | | // Get available UTXOs (not already locked for other channels) |
| | 0 | 62 | | var availableUtxos = _utxoSet.Values |
| | 0 | 63 | | .Where(utxo => utxo.LockedToChannelId is null) |
| | 0 | 64 | | .OrderByDescending(utxo => utxo.Amount.Satoshi) |
| | 0 | 65 | | .ToList(); |
| | | 66 | | |
| | 0 | 67 | | if (availableUtxos.Count == 0) |
| | 0 | 68 | | throw new InvalidOperationException("No available UTXOs"); |
| | | 69 | | |
| | | 70 | | // Try Branch and Bound to find an exact match or minimize inputs |
| | 0 | 71 | | var selectedUtxos = BranchAndBound(availableUtxos, requestFundingAmount); |
| | | 72 | | |
| | 0 | 73 | | if (selectedUtxos == null || selectedUtxos.Count == 0) |
| | 0 | 74 | | throw new InvalidOperationException("Insufficient funds"); |
| | | 75 | | |
| | | 76 | | // Lock the selected UTXOs for this channel |
| | 0 | 77 | | foreach (var selectedUtxo in selectedUtxos) |
| | 0 | 78 | | { |
| | 0 | 79 | | selectedUtxo.LockedToChannelId = channelId; |
| | 0 | 80 | | _utxoSet[(selectedUtxo.TxId, selectedUtxo.Index)] = selectedUtxo; |
| | 0 | 81 | | } |
| | | 82 | | |
| | 0 | 83 | | return selectedUtxos; |
| | 0 | 84 | | } |
| | | 85 | | |
| | | 86 | | public List<UtxoModel> GetLockedUtxosForChannel(ChannelId channelId) |
| | 0 | 87 | | { |
| | 0 | 88 | | return _utxoSet.Values.Where(x => x.LockedToChannelId.HasValue && x.LockedToChannelId.Value.Equals(channelId)) |
| | 0 | 89 | | .ToList(); |
| | 0 | 90 | | } |
| | | 91 | | |
| | | 92 | | public List<UtxoModel> ReturnUtxosNotSpentOnChannel(ChannelId channelId) |
| | 0 | 93 | | { |
| | 0 | 94 | | var utxos = _utxoSet.Values |
| | 0 | 95 | | .Where(x => x.LockedToChannelId.HasValue && x.LockedToChannelId.Value.Equals(channelId)) |
| | 0 | 96 | | .ToList(); |
| | 0 | 97 | | foreach (var utxo in utxos) |
| | 0 | 98 | | { |
| | 0 | 99 | | utxo.LockedToChannelId = null; |
| | 0 | 100 | | _utxoSet[(utxo.TxId, utxo.Index)] = utxo; |
| | 0 | 101 | | } |
| | | 102 | | |
| | 0 | 103 | | return utxos; |
| | 0 | 104 | | } |
| | | 105 | | |
| | | 106 | | public void ConfirmSpendOnChannel(ChannelId channelId) |
| | 0 | 107 | | { |
| | 0 | 108 | | var utxos = _utxoSet.Values.Where(x => x.LockedToChannelId.HasValue && |
| | 0 | 109 | | x.LockedToChannelId.Value.Equals(channelId)); |
| | 0 | 110 | | foreach (var utxo in utxos) |
| | 0 | 111 | | _utxoSet.TryRemove((utxo.TxId, utxo.Index), out _); |
| | 0 | 112 | | } |
| | | 113 | | |
| | | 114 | | public void UpgradeChannelIdOnLockedUtxos(ChannelId oldChannelId, ChannelId newChannelId) |
| | 0 | 115 | | { |
| | 0 | 116 | | var utxos = _utxoSet.Values |
| | 0 | 117 | | .Where(x => x.LockedToChannelId.HasValue && x.LockedToChannelId.Value.Equals(oldChannelId)) |
| | 0 | 118 | | .ToList(); |
| | | 119 | | // If there's no locked utxos, we have a problem |
| | 0 | 120 | | if (utxos.Count == 0) |
| | 0 | 121 | | throw new InvalidOperationException("No available UTXOs"); |
| | | 122 | | |
| | 0 | 123 | | foreach (var utxo in utxos) |
| | 0 | 124 | | { |
| | 0 | 125 | | utxo.LockedToChannelId = newChannelId; |
| | 0 | 126 | | _utxoSet[(utxo.TxId, utxo.Index)] = utxo; |
| | 0 | 127 | | } |
| | 0 | 128 | | } |
| | | 129 | | |
| | | 130 | | private static List<UtxoModel>? BranchAndBound(List<UtxoModel> utxos, LightningMoney targetAmount) |
| | 0 | 131 | | { |
| | | 132 | | const int maxTries = 100_000; |
| | 0 | 133 | | var tries = 0; |
| | | 134 | | |
| | | 135 | | // Best solution found so far |
| | 0 | 136 | | List<UtxoModel>? bestSelection = null; |
| | 0 | 137 | | var bestWaste = long.MaxValue; |
| | | 138 | | |
| | | 139 | | // Current selection being explored |
| | 0 | 140 | | var targetSatoshis = targetAmount.Satoshi; |
| | | 141 | | |
| | | 142 | | // Stack for depth-first search: (index, includeUtxo) |
| | 0 | 143 | | var stack = new Stack<(int index, bool include, List<UtxoModel> selection, long value)>(); |
| | 0 | 144 | | stack.Push((0, true, [], 0)); |
| | 0 | 145 | | stack.Push((0, false, [], 0)); |
| | | 146 | | |
| | 0 | 147 | | while (stack.Count > 0 && tries < maxTries) |
| | 0 | 148 | | { |
| | 0 | 149 | | tries++; |
| | 0 | 150 | | var (index, include, selection, value) = stack.Pop(); |
| | | 151 | | |
| | 0 | 152 | | if (include && index < utxos.Count) |
| | 0 | 153 | | { |
| | 0 | 154 | | selection = new List<UtxoModel>(selection) { utxos[index] }; |
| | 0 | 155 | | value += utxos[index].Amount.Satoshi; |
| | 0 | 156 | | } |
| | | 157 | | |
| | | 158 | | // Check if we found a valid solution |
| | 0 | 159 | | if (value >= targetSatoshis) |
| | 0 | 160 | | { |
| | 0 | 161 | | var waste = value - targetSatoshis; |
| | | 162 | | |
| | | 163 | | // Perfect match (changeless transaction) |
| | 0 | 164 | | if (waste == 0) |
| | 0 | 165 | | return selection; |
| | | 166 | | |
| | | 167 | | // Better solution than the current best |
| | 0 | 168 | | if (waste < bestWaste || |
| | 0 | 169 | | (waste == bestWaste && selection.Count < (bestSelection?.Count ?? int.MaxValue))) |
| | 0 | 170 | | { |
| | 0 | 171 | | bestSelection = new List<UtxoModel>(selection); |
| | 0 | 172 | | bestWaste = waste; |
| | 0 | 173 | | } |
| | | 174 | | |
| | 0 | 175 | | continue; // Prune this branch |
| | | 176 | | } |
| | | 177 | | |
| | | 178 | | // Move to the next UTXO |
| | 0 | 179 | | var nextIndex = index + 1; |
| | 0 | 180 | | if (nextIndex >= utxos.Count) |
| | 0 | 181 | | continue; |
| | | 182 | | |
| | | 183 | | // Calculate upper bound (current value + all remaining UTXOs) |
| | 0 | 184 | | var upperBound = value; |
| | 0 | 185 | | for (var i = nextIndex; i < utxos.Count; i++) |
| | 0 | 186 | | upperBound += utxos[i].Amount.Satoshi; |
| | | 187 | | |
| | | 188 | | // Prune if we can't reach the target even with all remaining UTXOs |
| | 0 | 189 | | if (upperBound < targetSatoshis) |
| | 0 | 190 | | continue; |
| | | 191 | | |
| | | 192 | | // Explore both branches: include and exclude the next UTXO |
| | 0 | 193 | | stack.Push((nextIndex, false, [.. selection], value)); |
| | 0 | 194 | | stack.Push((nextIndex, true, [.. selection], value)); |
| | 0 | 195 | | } |
| | | 196 | | |
| | | 197 | | // If no exact match found, return the best solution or fallback to greedy |
| | | 198 | | // Fallback: simple greedy approach if BnB didn't find a solution |
| | 0 | 199 | | return bestSelection ?? GreedySelection(utxos, targetAmount); |
| | 0 | 200 | | } |
| | | 201 | | |
| | | 202 | | private static List<UtxoModel>? GreedySelection(List<UtxoModel> utxos, LightningMoney targetAmount) |
| | 0 | 203 | | { |
| | 0 | 204 | | var selected = new List<UtxoModel>(); |
| | 0 | 205 | | long currentSum = 0; |
| | 0 | 206 | | var targetSatoshis = targetAmount.Satoshi; |
| | | 207 | | |
| | 0 | 208 | | foreach (var utxo in utxos) |
| | 0 | 209 | | { |
| | 0 | 210 | | selected.Add(utxo); |
| | 0 | 211 | | currentSum += utxo.Amount.Satoshi; |
| | | 212 | | |
| | 0 | 213 | | if (currentSum >= targetSatoshis) |
| | 0 | 214 | | return selected; |
| | 0 | 215 | | } |
| | | 216 | | |
| | 0 | 217 | | return null; // Insufficient funds |
| | 0 | 218 | | } |
| | | 219 | | } |