coin_join_perfection.mzn

% each participant (a and b) has a utxo set. We model each as an array of ints
array[int] of int: a_inputs = [ 200, 12300, 5000, 100, 20, 5000, 230, 23, 23000];
array[int] of int: b_inputs = [ 1050, 100, 100, 100, 100, 2000, 2834];


% the amount of satoshis of fees we need to pay to create a 2-output transaction (with no inputs)
% we have a min and max, because it helps a lot in creating a transaction.
int: minTransactionFeeConstOverhead = 10; 
int: maxTransactionFeeConstOverhead = 20;

% and there's also a certain amount of extra fees we want to pay additional input
int: transactionFeeMinPerInputFee = 2;
int: transactionFeeMaxPerInputFee = 3;


array[1..length(a_inputs)] of var bool: a_selected;
array[1..length(b_inputs)] of var bool: b_selected;


var int: a_selected_amount = sum(i in 1..length(a_inputs))(a_inputs[i] * bool2int(a_selected[i]));
var int: b_selected_amount = sum(i in 1..length(b_inputs))(b_inputs[i] * bool2int(b_selected[i]));


var int: a_selected_count = sum(i in 1..length(a_inputs))(bool2int(a_selected[i]));
var int: b_selected_count = sum(i in 1..length(b_inputs))(bool2int(b_selected[i]));


var int: total_selected_count = a_selected_count + b_selected_count;

% how much we're each participant is getting out
var int: a_output_amount;
var int: b_output_amount;


% how much each participant is paying in tx fees
var int: a_fee = a_selected_amount - a_output_amount;
var int: b_fee = b_selected_amount - b_output_amount;

var int: total_fee = a_fee + b_fee;

% the entire transaction must pay enough fees
constraint total_fee >= minTransactionFeeConstOverhead + transactionFeeMinPerInputFee*total_selected_count; % must pay enough tx fees
constraint total_fee <= maxTransactionFeeConstOverhead + transactionFeeMaxPerInputFee*total_selected_count; % dont pay enough tx fees


% a user must at least pay for their own inputs
var int: a_min_fee = transactionFeeMinPerInputFee * a_selected_count;
var int: b_min_fee = transactionFeeMinPerInputFee * b_selected_count;


% no user can get a free ride:
constraint a_fee >= a_min_fee;
constraint b_fee >= b_min_fee;

% and pay less than a "full" transaction that if they made it themselves
var int: a_max_fee = maxTransactionFeeConstOverhead + transactionFeeMaxPerInputFee * a_selected_count;
var int: b_max_fee = maxTransactionFeeConstOverhead + transactionFeeMaxPerInputFee * b_selected_count;


constraint a_fee <= a_max_fee;
constraint b_fee <= b_max_fee;


% no point creating a transaction unless both A and B have contributed inputs
constraint a_selected_count > 0;
constraint b_selected_count > 0;




% This is just to constrain a...



array[1..length(a_inputs), 1..length(a_inputs)] of var bool: a_working_memory_a;
array[1..length(a_inputs), 1..length(b_inputs)] of var bool: a_working_memory_b;


constraint forall(a in 1..length(a_inputs)) (
       a_selected[a] = a_working_memory_a[a, a]
);


constraint  forall(a in 1..length(a_inputs)) (
  forall(i in 1..length(a_inputs))(a_selected[i] >= a_working_memory_a[a, i]) /\
  forall(i in 1..length(b_inputs))(b_selected[i] >= a_working_memory_b[a, i])
);



constraint  forall(a in 1..length(a_inputs)) (
    sum(i in 1..length(a_inputs)) (a_inputs[i]*bool2int(a_working_memory_a[a, i])) +
              sum(i in 1..length(b_inputs)) (b_inputs[i]*bool2int(a_working_memory_b[a, i]))
              >= b_output_amount + b_min_fee
);
  

constraint  forall(a in 1..length(a_inputs)) (
         sum(i in 1..length(a_inputs)) (a_inputs[i]*bool2int(a_working_memory_a[a, i])) +
              sum(i in 1..length(b_inputs)) (b_inputs[i]*bool2int(a_working_memory_b[a, i]))
              <= b_output_amount + b_max_fee
);

                                  
% omg copy and paste alert! (now for b's)


array[1..length(b_inputs), 1..length(a_inputs)] of var bool: b_working_memory_a;
array[1..length(b_inputs), 1..length(b_inputs)] of var bool: b_working_memory_b;


constraint forall(b in 1..length(b_inputs)) (
       b_selected[b] = b_working_memory_b[b, b]
);


constraint  forall(b in 1..length(b_inputs)) (
  forall(i in 1..length(a_inputs))(a_selected[i] >= b_working_memory_a[b, i]) /\
  forall(i in 1..length(b_inputs))(b_selected[i] >= b_working_memory_b[b, i])
);


constraint  forall(b in 1..length(b_inputs)) (
    sum(i in 1..length(a_inputs)) (a_inputs[i]*bool2int(b_working_memory_a[b, i])) +
    sum(i in 1..length(b_inputs)) (b_inputs[i]*bool2int(b_working_memory_b[b, i]))
    >= a_output_amount + a_min_fee
);
  

constraint  forall(b in 1..length(b_inputs)) (
    sum(i in 1..length(a_inputs)) (a_inputs[i]*bool2int(b_working_memory_a[b, i])) +
    sum(i in 1..length(b_inputs)) (b_inputs[i]*bool2int(b_working_memory_b[b, i]))
    <= a_output_amount + a_max_fee
);


solve maximize total_selected_count;

description.md

CoinJoin Jigsaw

A "CoinJoin Jigsaw" is send-to-self coinjoin transaction in which every input is ambiguously associated with an output (i.e. every transaction input must belong to at least one subset of every output amount).

For simplicity I've used minizinc to model this. To make it clean, I decided to model as two users (affectionately called 'A' and 'B') who trust a common party to orchestrate the CoinJoin Jigsaw for them. A and B don't trust each other, so they want to get all their money atomically in this one transaction. We also want the "CoinJoin Jigsaw" to have exactly 2 outputs. One for A, and one for B. That way at first approximation it looks like a pretty standard bitcoin payment. (Of course the problem is substantially easier to solve if we allow A and B to have N outputs, but that creates an ugly transaction).

We also need to make sure that both A and B are paying a fee proportional to the amount of inputs they added, and the total transaction fee is satisfactory.

So I've modelled it as A and B provide their utxo to the orchestrater. The orchestrater will pick the largest subset of A's and B's utxo and such that satisfies our CoinJoin Jigsaw properties.