Choix des sources d'entrée (Coin Selection Algorithm)

D’après ce que je lis, on a tous implémenté à peu près le même algorithme naïf pour le choix des sources pour générer une transaction : on ajoute la première source de la liste des sources disponibles jusqu’à atteindre le montant. (silkaj, sakia, cesium, gmixer)

Si on fait ça en prenant les sources dans l’ordre donné par BMA, qui semble être les DU par bloc croissant puis les UTXO par ordre alphabétique du hash, l’algorithme consomme d’abord les plus anciens DU, puis les UTXO dans un ordre aléatoire.

On pourrait optimiser l’algo pour un but déterminé, comme réduire la taille des documents transactions, réduire la taille des index de sources, réduire l’âge des sources, avoir plus de grosses ou de petites sources…

L’algo du bitcoin résumé ici semble pas mal. Il faut cependant adapter certaines étapes, car il est optimisé pour réduire le montant total des sources, afin de réduire la taxe à payer, or nous n’avons pas encore ce problème.

Selon vous, quelles devraient être les priorités de cet algo ? Je vais réfléchir à comment minimiser le nombre total d’UTXO en attendant. (ça fait un exercice de maths et d’algo intéressant)

3 J'aimes

Choisir les plus anciennes sources est intéressante, afin d’éviter les risques de perte de TX à cause de fork.

3 J'aimes

Pour l’instant j’ai l’impression que BMA ne permet pas de faire ça facilement, à part pour les DU, du coup il faudra attendre GVA… mais algorithmiquement c’est beaucoup plus simple que de minimiser le nombre de sources.

1 J'aime

my 2c: as a trade off of a larger blockchain to sync but a much smaller state db, perhaps consume all available DU/utxos (not including the last prudent-number of blocks that might rollback) for each new transaction… regularly minimizing each account to the latest change output? (added*: as in a client saying « GVA is some time away from reality… so BMA:/tx/sources/PubKey, you will NOT give me bulky output in the future! »)

what is unseen?

  • maybe not ideal for many tx’s per day (*edited: or unusable for many txs/hr)
  • might require some sync-from-checkpoint down the road, instead of from genesis.
  • generous gift given by node hosters exploited to cost them even more verification resources per tx… to the point they’re no longer « having fun » hosting a duniter node.
  • all that we wont be able to think of.

-Spencer971

If someone generates several txs using this algorithm several times in a row, double spend will surely happen.

So we should add a new priority: make double spend less probable. It can be achieved by inserting some randomness into our algo. (e.g. for the « oldest first » algo, select random sources between all the sources older than some arbitrary threshold)

2 J'aimes

I’ll agree, and add that for blockchain maybe even the original priority. thanks tux!

Spencer971