User:Gmaxwell/coin selection - Revision history

934: correct typo

2015-08-10T13:16:53Z

correct typo

← Older revision		Revision as of 13:16, 10 August 2015
Line 9:		Line 9:
	The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].		The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].

	An interesting variation of the problem is where you first try to minimize linking transactions from multiple anonymity groups, or where some must be linked minimizing the badness of the linkage. One possible ~~baddness~~ metric is the ration of L2 (or higher) to L1 norm for the resulting group sizes (e.g. more smaller groups is better than fewer bigger groups).		An interesting variation of the problem is where you first try to minimize linking transactions from multiple anonymity groups, or where some must be linked minimizing the badness of the linkage. One possible badness metric is the ration of L2 (or higher) to L1 norm for the resulting group sizes (e.g. more smaller groups is better than fewer bigger groups).

	Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.		Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.

Gmaxwell: example execution

2012-05-28T23:24:54Z

example execution

@@ Line 84: / Line 84: @@
    "aaac"                    100000000         2    50      .      .
    "aaad"                            1         1   100      .      . ;
 </pre>

Gmaxwell: tweaks

2012-05-28T23:15:51Z

tweaks

← Older revision		Revision as of 23:15, 28 May 2012
Line 13:		Line 13:
	Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.		Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.

	A realistic implementation would probably try several techniques ("use a single input exactly", "build transactions with no change", "build transactions with change but no fees") with solvers specialized for each and then choose the 'best', potentially based on user preferences.		A realistic implementation would probably try several techniques ("use a single input exactly", "build transactions with no change", "build transactions with change but no fees") with solvers specialized for each and then choose the 'best', potentially based on user preferences. In cases where the constraints limit the inputs substantially (E.g. 'use a single input exactly') exact solutions are easy.

	==AMPL program==		==AMPL program==

Gmaxwell: on mixing techniques.

2012-05-28T23:14:55Z

on mixing techniques.

← Older revision		Revision as of 23:14, 28 May 2012
Line 12:		Line 12:

	Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.		Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.

			A realistic implementation would probably try several techniques ("use a single input exactly", "build transactions with no change", "build transactions with change but no fees") with solvers specialized for each and then choose the 'best', potentially based on user preferences.

	==AMPL program==		==AMPL program==

Gmaxwell: on linkage.

2012-05-28T23:13:10Z

on linkage.

← Older revision		Revision as of 23:13, 28 May 2012
Line 8:		Line 8:

	The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].		The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].

			An interesting variation of the problem is where you first try to minimize linking transactions from multiple anonymity groups, or where some must be linked minimizing the badness of the linkage. One possible baddness metric is the ration of L2 (or higher) to L1 norm for the resulting group sizes (e.g. more smaller groups is better than fewer bigger groups).

	Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.		Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.

Gmaxwell: /* Example AMPL problem data */ on sizes.

2012-05-28T23:10:53Z

Example AMPL problem data: on sizes.

← Older revision		Revision as of 23:10, 28 May 2012
Line 65:		Line 65:
	===Example AMPL problem data===		===Example AMPL problem data===

	If there are multiple identical inputs they should be only put in once and given a fmax equal to the number of duplicates.		If there are multiple identical inputs they should be only put in once and given a fmax equal to the number of duplicates. The sizes given per input and for the base transaction are just random numbers.

	<pre>		<pre>

Gmaxwell: tweaks

2012-05-28T23:10:05Z

tweaks

← Older revision		Revision as of 23:10, 28 May 2012
Line 9:		Line 9:
	The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].		The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].

	Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections.		Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. While big solver systems are not suitable for integration with Bitcoin (due to code size, licensing, computational complexity, memory usage, etc) they can be used as benchmarks to compare more reasonable implementations.

	==AMPL program==		==AMPL program==

Gmaxwell: tweaks

2012-05-28T23:06:53Z

tweaks

← Older revision		Revision as of 23:06, 28 May 2012
Line 1:		Line 1:
	Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.		Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.

	The reference client uses a heuristic subset-sum knapsack solver to try to minimize transaction size. It is fee blind, though ~~its~~ run multiple times excluding less confirmed coins which may sometimes help avoid fees if there are many larger inputs available and minimizing sizes helps with fees (but does not guarantee low fees). Minimizing the current transaction size also does nothing to reduce the amount of data a pruning bitcoin node needs to keep around, in fact it usually does the opposite.		The reference client uses a heuristic subset-sum knapsack solver to try to minimize transaction size. It is fee blind, though it is run multiple times excluding less confirmed coins which may sometimes help avoid fees if there are many larger inputs available and minimizing sizes helps with fees (but does not guarantee low fees). Minimizing the current transaction size also does nothing to reduce the amount of data a pruning bitcoin node needs to keep around, in fact it usually does the opposite.

	Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.		Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.

Gmaxwell: on why coin selection matters.

2012-05-28T23:06:28Z

on why coin selection matters.

← Older revision		Revision as of 23:06, 28 May 2012
Line 1:		Line 1:
	Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.		Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.

			The reference client uses a heuristic subset-sum knapsack solver to try to minimize transaction size. It is fee blind, though its run multiple times excluding less confirmed coins which may sometimes help avoid fees if there are many larger inputs available and minimizing sizes helps with fees (but does not guarantee low fees). Minimizing the current transaction size also does nothing to reduce the amount of data a pruning bitcoin node needs to keep around, in fact it usually does the opposite.

	Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.		Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.

Gmaxwell: tweaks

2012-05-28T23:03:36Z

tweaks

← Older revision		Revision as of 23:03, 28 May 2012
Line 1:		Line 1:
			Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.

	Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.		Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.

Line 4:		Line 6:

	The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].		The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[http://en.wikipedia.org/wiki/Branch_and_cut].

	~~Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.~~

	Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections.		Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections.