rpc: Shuffle inputs and outputs after joining psbts

achow101 commented at 10:11 pm on July 31, 2019: member

joinpsbts currently just adds the inputs and outputs in the order of that the PSBTs were provided. This makes it extremely easy to identify which outputs belong to which inputs. This PR changes that so that all of the inputs and outputs are shuffled in the joined transaction.

fanquake added the label RPC/REST/ZMQ on Jul 31, 2019

in src/rpc/rawtransaction.cpp:1615 in a114e33645 outdated

1610+    Shuffle(input_indices.begin(), input_indices.end(), FastRandomContext());
1611+    std::vector<int> output_indices(merged_psbt.outputs.size());
1612+    std::iota(output_indices.begin(), output_indices.end(), 0);
1613+    Shuffle(output_indices.begin(), output_indices.end(), FastRandomContext());
1614+
1615+    // Shuffle the inputs

promag commented at 11:05 pm on July 31, 2019:

Unnecessary comment? Or maybe move it to L1607 like Shuffle inputs and outputs of the merged PSBT.

achow101 commented at 7:56 pm on August 1, 2019:

Removed the comment and updated the one above.

promag commented at 11:08 pm on July 31, 2019: member

Concept ACK.

fanquake added the label Privacy on Aug 1, 2019

laanwj commented at 12:47 pm on August 1, 2019: member

Concept ACK, not sure whether there’s reasons someone would want to disable this, but in any case I think privacy-by-default behavior is good

practicalswift commented at 4:44 pm on August 1, 2019: contributor

Concept ACK

achow101 force-pushed on Aug 1, 2019

fanquake commented at 9:37 am on August 14, 2019: member

Concept ACK - Can we get some sort of simple test case to ensure that there’s some shuffling going on.

but in any case I think privacy-by-default behavior is good

Definitely agree.

I guess this should also be backported given the patch is fairly simple and it’s a privacy improvement?

fanquake added the label Needs backport on Aug 14, 2019

fanquake added this to the milestone 0.18.2 on Aug 14, 2019

achow101 commented at 6:31 pm on August 14, 2019: member

I’ve added a test. It runs joinpsbts multiple times and checks whether at least one of the resulting psbts are different.

in test/functional/rpc_psbt.py:378 in 4228d64e2c outdated

369@@ -370,6 +370,13 @@ def test_psbt_input_keys(psbt_input, keys):
370         joined_decoded = self.nodes[0].decodepsbt(joined)
371         assert len(joined_decoded['inputs']) == 4 and len(joined_decoded['outputs']) == 2 and "final_scriptwitness" not in joined_decoded['inputs'][3] and "final_scriptSig" not in joined_decoded['inputs'][3]
372 
373+        # Check that joining shuffles the inputs and outputs
374+        shuffled = False
375+        for i in range(0, 10):
376+            shuffled_joined = self.nodes[0].joinpsbts([psbt, psbt2])
377+            shuffled |= joined != shuffled_joined

promag commented at 10:47 pm on August 14, 2019:

nit, could break if shuffled.

achow101 commented at 0:22 am on August 15, 2019:

Done

in test/functional/rpc_psbt.py:373 in 4228d64e2c outdated

369@@ -370,6 +370,13 @@ def test_psbt_input_keys(psbt_input, keys):
370         joined_decoded = self.nodes[0].decodepsbt(joined)
371         assert len(joined_decoded['inputs']) == 4 and len(joined_decoded['outputs']) == 2 and "final_scriptwitness" not in joined_decoded['inputs'][3] and "final_scriptSig" not in joined_decoded['inputs'][3]
372 
373+        # Check that joining shuffles the inputs and outputs

promag commented at 10:50 pm on August 14, 2019:

nit, could improve comment like “10 attempts should be enough to get a shuffled join”.

achow101 commented at 0:22 am on August 15, 2019:

Done

in src/rpc/rawtransaction.cpp:1611 in 4228d64e2c outdated

1603@@ -1604,8 +1604,28 @@ UniValue joinpsbts(const JSONRPCRequest& request)
1604         merged_psbt.unknown.insert(psbt.unknown.begin(), psbt.unknown.end());
1605     }
1606 
1607+    // Generate list of shuffled indices for shuffling inputs and outputs of the merged PSBT
1608+    std::vector<int> input_indices(merged_psbt.inputs.size());
1609+    std::iota(input_indices.begin(), input_indices.end(), 0);
1610+    Shuffle(input_indices.begin(), input_indices.end(), FastRandomContext());

promag commented at 10:58 pm on August 14, 2019:

Should #include <random.h>

achow101 commented at 0:22 am on August 15, 2019:

Done

promag commented at 10:58 pm on August 14, 2019: member

ACK, but could add a release note regarding the behavior change and also improve help text.

achow101 force-pushed on Aug 15, 2019

achow101 commented at 0:22 am on August 15, 2019: member

Added a release note.

DrahtBot commented at 1:10 am on August 15, 2019: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#16839 (Replace Connman and BanMan globals with Node local by ryanofsky)
#16439 (RPC: support “@height” in place of blockhash for getblock etc by ajtowns)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

luke-jr commented at 0:55 am on August 20, 2019: member

Only bugfixes should be backported, not improvements…

JeremyRubin commented at 1:37 am on August 20, 2019: contributor

Wouldn’t it be better to deterministically sort them?

achow101 commented at 2:33 am on August 20, 2019: member

Wouldn’t it be better to deterministically sort them?

Not at all. That gives a different privacy leak as it will indicate that joinpsbts has been used on that transaction.

JeremyRubin commented at 5:28 pm on August 20, 2019: contributor

Hm gotcha. I was unclear of the status of BIP-69 and related standard adoption efforts for Core

instagibbs commented at 2:47 pm on August 27, 2019: member

Only bugfixes should be backported, not improvements…

Privacy leak is a bug imo. Everywhere else we(should be) shuffle.

in test/functional/rpc_psbt.py:375 in b1d769faf3 outdated

369@@ -370,6 +370,16 @@ def test_psbt_input_keys(psbt_input, keys):
370         joined_decoded = self.nodes[0].decodepsbt(joined)
371         assert len(joined_decoded['inputs']) == 4 and len(joined_decoded['outputs']) == 2 and "final_scriptwitness" not in joined_decoded['inputs'][3] and "final_scriptSig" not in joined_decoded['inputs'][3]
372 
373+        # Check that joining shuffles the inputs and outputs
374+        # 10 attempts should be enough to get a shuffled join
375+        shuffled = False

instagibbs commented at 2:49 pm on August 27, 2019:

I think it’s simpler to just do an infinite loop and break IFF a difference is found, makes it less dependent on number of inputs and lowers false negatives

promag commented at 3:27 pm on August 27, 2019:

Do you mean just replacing the line below with while True:? If you mean to drop shuffled then what would you assert after the loop?

instagibbs commented at 3:34 pm on August 27, 2019:

just saying remove the 10 times limit, maybe makes the logic simpler. hanging with implementation bug is better than false negative imo

promag commented at 3:39 pm on August 27, 2019:

I agree with you but it it isn’t that informative. Suppose it hangs in travis, you would be clueless.

instagibbs commented at 3:45 pm on August 27, 2019:

Wouldn’t be clueless if it printed out what tests are still running, but those PRs have been unable to get merged, sad!

Could just bump it to some fairly ridiculous number that’s unlikely to be hit even if the test itself is modified significantly. I think the easiest case to get a false negative is just two entries, 50/50 chance, so run that 128 times and we’re fine :P

achow101 commented at 9:39 pm on September 4, 2019:

I think 10 is enough for now.

instagibbs commented at 9:15 pm on September 5, 2019:

first test failure you’re getting strung up :P

in src/rpc/rawtransaction.cpp:1610 in 6e7ff4be32 outdated

1604@@ -1604,8 +1605,28 @@ UniValue joinpsbts(const JSONRPCRequest& request)
1605         merged_psbt.unknown.insert(psbt.unknown.begin(), psbt.unknown.end());
1606     }
1607 
1608+    // Generate list of shuffled indices for shuffling inputs and outputs of the merged PSBT
1609+    std::vector<int> input_indices(merged_psbt.inputs.size());
1610+    std::iota(input_indices.begin(), input_indices.end(), 0);

instagibbs commented at 2:54 pm on August 27, 2019:

std::iota

not sure we should be adding IOTA support to Core

(this is a joke)

in src/rpc/rawtransaction.cpp:1608 in 6e7ff4be32 outdated

1604@@ -1604,8 +1605,28 @@ UniValue joinpsbts(const JSONRPCRequest& request)
1605         merged_psbt.unknown.insert(psbt.unknown.begin(), psbt.unknown.end());
1606     }
1607 
1608+    // Generate list of shuffled indices for shuffling inputs and outputs of the merged PSBT

instagibbs commented at 3:02 pm on August 27, 2019:

Forgive me, why are we not just shuffling the vector of inputs and outputs in merged_psbt using Shuffle directly?

achow101 commented at 4:14 pm on August 27, 2019:

There are two input vectors and output vectors. The on in the global tx, and the one in the psbt metadata. Both need to line up, so by shuffling the indicies, each input and output can be lined up with its respective metadata.

instagibbs commented at 4:19 pm on August 27, 2019:

ah! Missed how the actual transaction was being reconstructed, got it.

jonatack commented at 10:42 am on September 4, 2019:

Suggested change for git grepping, mainly the line “// Shuffle input and output indices lists” to have a comment beginning with “Shuffle” like:

0src/wallet/rpcwallet.cpp:913: // Shuffle recipient list
1src/wallet/wallet.cpp:3211: // Shuffle selected coins and fill in final vin

 0    // Generate lists of input and output indices of the merged PSBT
 1    // to be shuffled.
 2    std::vector<int> input_indices(merged_psbt.inputs.size());
 3    std::iota(input_indices.begin(), input_indices.end(), 0);
 4    std::vector<int> output_indices(merged_psbt.outputs.size());
 5    std::iota(output_indices.begin(), output_indices.end(), 0);
 6
 7    // Shuffle input and output indices lists
 8    Shuffle(input_indices.begin(), input_indices.end(), FastRandomContext());
 9    Shuffle(output_indices.begin(), output_indices.end(), FastRandomContext());
10
11    // Generate shuffled_psbt from shuffled indices lists
12    PartiallySignedTransaction shuffled_psbt;

jonatack commented at 11:04 am on September 4, 2019:

Note that the proposed change places the two Shuffle functions together. First generate the lists, then perform the shuffles.

achow101 commented at 9:44 pm on September 4, 2019:

Done

in test/functional/rpc_psbt.py:376 in b1d769faf3 outdated

369@@ -370,6 +370,16 @@ def test_psbt_input_keys(psbt_input, keys):
370         joined_decoded = self.nodes[0].decodepsbt(joined)
371         assert len(joined_decoded['inputs']) == 4 and len(joined_decoded['outputs']) == 2 and "final_scriptwitness" not in joined_decoded['inputs'][3] and "final_scriptSig" not in joined_decoded['inputs'][3]
372 
373+        # Check that joining shuffles the inputs and outputs
374+        # 10 attempts should be enough to get a shuffled join
375+        shuffled = False
376+        for i in range(0, 10):

jonatack commented at 10:32 am on September 4, 2019:

Suggested change:

0-        for i in range(0, 10):
1+        for _ in range(10):

achow101 commented at 9:40 pm on September 4, 2019:

meh. not important enough to change

in test/functional/rpc_psbt.py:373 in b1d769faf3 outdated

369@@ -370,6 +370,16 @@ def test_psbt_input_keys(psbt_input, keys):
370         joined_decoded = self.nodes[0].decodepsbt(joined)
371         assert len(joined_decoded['inputs']) == 4 and len(joined_decoded['outputs']) == 2 and "final_scriptwitness" not in joined_decoded['inputs'][3] and "final_scriptSig" not in joined_decoded['inputs'][3]
372 
373+        # Check that joining shuffles the inputs and outputs

jonatack commented at 10:34 am on September 4, 2019:

Suggested change:

0-        # Check that joining shuffles the inputs and outputs
1-        # 10 attempts should be enough to get a shuffled join
2
3+        # Check that joining shuffles the inputs and outputs.
4+        # Run up to 10 attempts to ensure seeing a shuffled join.

achow101 commented at 9:40 pm on September 4, 2019:

meh. not important enough to change

in doc/release-notes-16512.md:3 in b1d769faf3 outdated

0@@ -0,0 +1,3 @@
1+RPC changes
2+-----------
3+The RPC `joinpsbts` will shuffle the order of the inputs and outputs of the resulting joined psbt.

jonatack commented at 10:54 am on September 4, 2019:

Perhaps provide more context on “why” and what the previous behavior was, like in your PR description.

achow101 commented at 9:44 pm on September 4, 2019:

Done

jonatack commented at 11:01 am on September 4, 2019: member

Concept ACK b1d769faf3bab38c18c7424cfa5f1aeadc832c30. Code review, built, ran tests, verified the added test fails without the change. Code looks correct; a few suggestions follow for your perusal. Is testing joinpsbt inequality in rpc_psbt.py enough? Could the manual copy+shuffling be extracted and covered by unit tests? e.g. as a member function of PartiallySignedTransaction?

nopara73 commented at 2:42 pm on September 4, 2019: none

Concept ACK. Related: https://github.com/bitcoin/bitcoin/issues/12457

Shuffle inputs and outputs after joining psbts 6f405a1d3b

Test that joinpsbts randomly shuffles the inputs c0b5d97103

achow101 force-pushed on Sep 4, 2019

in src/rpc/rawtransaction.cpp:1614 in c0b5d97103

1609+    std::vector<int> input_indices(merged_psbt.inputs.size());
1610+    std::iota(input_indices.begin(), input_indices.end(), 0);
1611+    std::vector<int> output_indices(merged_psbt.outputs.size());
1612+    std::iota(output_indices.begin(), output_indices.end(), 0);
1613+
1614+    // Shuffle input and output indicies lists

jonatack commented at 9:03 pm on September 5, 2019:

nit (if you need to retouch this): s/indicies/indices/

jonatack commented at 4:58 pm on September 17, 2019: member

@achow101 what did you think of this question / suggestion above?

achow101 commented at 5:07 pm on September 17, 2019: member

Is testing joinpsbt inequality in rpc_psbt.py enough?

It should be.

Could the manual copy+shuffling be extracted and covered by unit tests? e.g. as a member function of PartiallySignedTransaction?

Maybe later? I would like this merged for 0.19 so I do want any further changes to this to be minimal.

instagibbs commented at 5:08 pm on September 17, 2019: member

utACK https://github.com/bitcoin/bitcoin/pull/16512/commits/c0b5d9710322a614a50ab5da081558cf6a38ad2a

MarcoFalke removed this from the milestone 0.18.2 on Sep 17, 2019

MarcoFalke added this to the milestone 0.19.0 on Sep 17, 2019

jonatack commented at 5:16 pm on September 17, 2019: member

Could the manual copy+shuffling be extracted and covered by unit tests? e.g. as a member function of PartiallySignedTransaction?

Maybe later? I would like this merged for 0.19 so I do want any further changes to this to be minimal.

Fair enough. I might propose it later.

fanquake renamed this:
~~Shuffle inputs and outputs after joining psbts~~
rpc: Shuffle inputs and outputs after joining psbts
on Sep 18, 2019

jonatack commented at 12:58 pm on September 18, 2019: member

ACK c0b5d9710322a614a50ab5da081558cf6a38ad2a modulo suggestions for later.

laanwj commented at 2:19 pm on September 18, 2019: member

ACK c0b5d9710322a614a50ab5da081558cf6a38ad2a

Agree the shuffling should ideally be factored out to a function, but that can be done in a future PR

laanwj referenced this in commit 72d30d668a on Sep 18, 2019

laanwj merged this on Sep 18, 2019

laanwj closed this on Sep 18, 2019

fanquake referenced this in commit 1c1ad3c7b9 on Sep 19, 2019

fanquake referenced this in commit 21299413bc on Sep 19, 2019

fanquake removed the label Needs backport on Sep 19, 2019

fanquake commented at 1:59 am on September 19, 2019: member

Added for backport in #16617.

MarcoFalke removed this from the milestone 0.19.0 on Sep 23, 2019

MarcoFalke added this to the milestone 0.18.2 on Sep 23, 2019

sidhujag referenced this in commit bd652e07a6 on Sep 23, 2019

fanquake referenced this in commit eb07d22b2d on Sep 23, 2019

fanquake referenced this in commit b12defc3bc on Sep 23, 2019

laanwj referenced this in commit 29d70264fb on Nov 25, 2019

deadalnix referenced this in commit bb01006c69 on Jun 23, 2020

Munkybooty referenced this in commit d0500f33cd on Dec 7, 2021

Munkybooty referenced this in commit 1c4e7aeb6e on Dec 15, 2021

Munkybooty referenced this in commit 4ffd8d893b on Dec 15, 2021

DrahtBot locked this on Dec 16, 2021

rpc: Shuffle inputs and outputs after joining psbts #16512

Conflicts