randomize or sort the order of input and output notes #778

Closed
daira opened this Issue Mar 14, 2016 · 13 comments

Comments

@daira
Contributor

daira commented Mar 14, 2016

For input notes, this could help to mitigate #679. For output notes, it mitigates potential information leaks to the note recipient (or viewing key holder): if a wallet is implemented in such a way that the ordering of notes depends on private information (such as the relative value of the notes) then that information could be leaked.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Mar 21, 2016

Contributor

We think that the higher-level payment interface should do this, but that the "raw" RPC interface cannot feasibly do so. Since the higher-level interface is not in 1.0, neither is this ticket.

[Edit: this is now part of the Payment API feature, which is provisionally in 1.0.]

Contributor

daira commented Mar 21, 2016

We think that the higher-level payment interface should do this, but that the "raw" RPC interface cannot feasibly do so. Since the higher-level interface is not in 1.0, neither is this ticket.

[Edit: this is now part of the Payment API feature, which is provisionally in 1.0.]

@daira daira changed the title from randomize the order of input and output coins to randomize the order of input and output notes Mar 29, 2016

@daira daira added this to the Payment API Code Freeze milestone Apr 4, 2016

@daira daira changed the title from randomize the order of input and output notes to randomize or sort the order of input and output notes Apr 4, 2016

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Apr 4, 2016

Contributor

Sorting the output notes by their commitments, and the input notes by their nullifiers, would suffice to block the information leak.

Contributor

daira commented Apr 4, 2016

Sorting the output notes by their commitments, and the input notes by their nullifiers, would suffice to block the information leak.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jul 6, 2016

Contributor

@ebfull points out that the computation of a commitment (specifically PRFρφ(i, hSig) ) depends on its index. Therefore the outputs cannot simply be sorted after computing the commitments, since changing their order would invalidate them.

This leaves two options:

  1. If the output commitments are not sorted, pick new r values until they are sorted.
  2. Randomize the order of outputs, don't sort them.

I think option 2 is simpler. (If we do option 2 for outputs then we should also randomize the order of inputs, since the benefit of determinism has already been lost in that case.)

Contributor

daira commented Jul 6, 2016

@ebfull points out that the computation of a commitment (specifically PRFρφ(i, hSig) ) depends on its index. Therefore the outputs cannot simply be sorted after computing the commitments, since changing their order would invalidate them.

This leaves two options:

  1. If the output commitments are not sorted, pick new r values until they are sorted.
  2. Randomize the order of outputs, don't sort them.

I think option 2 is simpler. (If we do option 2 for outputs then we should also randomize the order of inputs, since the benefit of determinism has already been lost in that case.)

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jul 6, 2016

Contributor

To clarify, the order of outputs would be randomized before computing the commitments, so that their order isn't correlated with wallet behaviour. Randomizing their order after computing the commitments would run into the same problem.

Contributor

daira commented Jul 6, 2016

To clarify, the order of outputs would be randomized before computing the commitments, so that their order isn't correlated with wallet behaviour. Randomizing their order after computing the commitments would run into the same problem.

@defuse

This comment has been minimized.

Show comment
Hide comment
@defuse

defuse Jul 26, 2016

Contributor

+1 on randomizing the order of both the inputs and the outputs.

Contributor

defuse commented Jul 26, 2016

+1 on randomizing the order of both the inputs and the outputs.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Aug 15, 2016

Contributor

I need to specify this as well.

Contributor

daira commented Aug 15, 2016

I need to specify this as well.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Aug 18, 2016

Contributor

Given that we're doing randomization rather than sorting, this is not a consensus change, so I'm bumping it to beta1.

Contributor

daira commented Aug 18, 2016

Given that we're doing randomization rather than sorting, this is not a consensus change, so I'm bumping it to beta1.

@daira daira modified the milestones: Beta 1 - audit mitigations, other linux support, user bugfixes, z9 Release - RPC, Testing improvements Aug 18, 2016

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Aug 26, 2016

Contributor

This could be done in several locations:

  • JoinSplit::prove() - this would cover all potential uses in one place, but has the unfortunate side-effect that the order of the prove() outputs (nullifiers, commitments etc) would not correspond to the order provided by the caller (unless we made the inputs and outputs non-const, and modified them for the caller).
  • JSDescription() - limits the effect to transactions, and still has the above issue
  • In the RPC code (#1200) - essentially requires us to implement randomisation anywhere we start creating a JoinSplit, but has the advantage that we know that the ordering of the JSDescription properties corresponds to the inputs and outputs we provided.
Contributor

str4d commented Aug 26, 2016

This could be done in several locations:

  • JoinSplit::prove() - this would cover all potential uses in one place, but has the unfortunate side-effect that the order of the prove() outputs (nullifiers, commitments etc) would not correspond to the order provided by the caller (unless we made the inputs and outputs non-const, and modified them for the caller).
  • JSDescription() - limits the effect to transactions, and still has the above issue
  • In the RPC code (#1200) - essentially requires us to implement randomisation anywhere we start creating a JoinSplit, but has the advantage that we know that the ordering of the JSDescription properties corresponds to the inputs and outputs we provided.
@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Aug 26, 2016

Contributor

We should implement another layer over JSDescription and have the RPC code use it, IMHO. How much this layer handles is up for discussion.

Contributor

daira commented Aug 26, 2016

We should implement another layer over JSDescription and have the RPC code use it, IMHO. How much this layer handles is up for discussion.

@ebfull ebfull modified the milestones: Beta 1 - complete RPC, Beta 2 - audit mitigations and critical bug fixes Sep 7, 2016

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Sep 14, 2016

Contributor

BTW- I consider this a low priority (in comparison to other beta2 goals). The one case I have thought of that makes me hesitate to kick it to post-1.0 is if the non-random order leak compromises a user's activity in the early days before we release a randomized version.

Let's work on this PR later in the Beta 2 process.

Contributor

nathan-at-least commented Sep 14, 2016

BTW- I consider this a low priority (in comparison to other beta2 goals). The one case I have thought of that makes me hesitate to kick it to post-1.0 is if the non-random order leak compromises a user's activity in the early days before we release a randomized version.

Let's work on this PR later in the Beta 2 process.

@ebfull ebfull removed their assignment Sep 22, 2016

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Sep 29, 2016

Contributor

IIRC @ebfull was going to work on this as part of @bitcartel's RPC work, but I'm not sure if it has happened in any of the open PRs (and @ebfull has had his head in other critical work). Could I get a status update please? I can add this to my list of things to knock out over the weekend if necessary.

Contributor

str4d commented Sep 29, 2016

IIRC @ebfull was going to work on this as part of @bitcartel's RPC work, but I'm not sure if it has happened in any of the open PRs (and @ebfull has had his head in other critical work). Could I get a status update please? I can add this to my list of things to knock out over the weekend if necessary.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Sep 29, 2016

Contributor

Let's add a RandomizedJSDescription that just does this, and have the RPC use it in place of JSDescription.

Contributor

daira commented Sep 29, 2016

Let's add a RandomizedJSDescription that just does this, and have the RPC use it in place of JSDescription.

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Oct 17, 2016

Contributor

@daira and I paired on a function that would permute an array in a way that could be tracked by the caller. Next I will pair with @bitcartel to integrate the new JSDescription::Randomized() into the RPC code, and to update the corresponding tests to ensure that the resulting mappings are a valid permutation.

Contributor

str4d commented Oct 17, 2016

@daira and I paired on a function that would permute an array in a way that could be tracked by the caller. Next I will pair with @bitcartel to integrate the new JSDescription::Randomized() into the RPC code, and to update the corresponding tests to ensure that the resulting mappings are a valid permutation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment