New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement selective disclosure #406

Open
nathan-at-least opened this Issue Nov 3, 2015 · 70 comments

Comments

@nathan-at-least
Contributor

nathan-at-least commented Nov 3, 2015

Editorial note 2016-12-02: We've switched from selective transparency to selective disclosure which we believe is clearer and focuses on the user's choice and action.

I'm not sure we already have a ticket for selective transparency, even though we've been discussing it for about a year. Here's a ticket specifically for this feature, which looks something like every zc address also comes with an "auditing" key which allows reading all sent/received transaction amounts, but not spending for that address.

crosslinks:

  • Here's a mention of it in the use case brainstorm ticket: #72 (comment)
  • we also have notes from the January hackfest somewhere. Paging @daira.

Also, this sounds very similar to a Monero feature:

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Dec 3, 2015

Contributor

Assigning to me to add the notes from the hackfest.

Contributor

daira commented Dec 3, 2015

Assigning to me to add the notes from the hackfest.

@daira daira self-assigned this Dec 3, 2015

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jan 21, 2016

Contributor

Here's a link to the notes from the hackfest:

Contributor

daira commented Jan 21, 2016

Here's a link to the notes from the hackfest:

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jan 21, 2016

Contributor

Selective transparency in the receive direction (i.e. giving an auditor the ability to audit --but not spend-- the coins you receive) does not require any extra keys or protocol changes. (Adding lsk_enc/lpk_enc is orthogonal to this.)

Contributor

daira commented Jan 21, 2016

Selective transparency in the receive direction (i.e. giving an auditor the ability to audit --but not spend-- the coins you receive) does not require any extra keys or protocol changes. (Adding lsk_enc/lpk_enc is orthogonal to this.)

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jan 21, 2016

Contributor

Selective transparency in the send direction requires extra key pairs (one for each subset of information that can be selectively revealed) to encrypt sent coins to the auditor. Note that the auditor can verify (per transaction) that the information they decrypt is correct once given the private key, because they can recompute from it the coin commitments cmnew1,2. This does not require a circuit change. However it is not possible with the protocol described in the meeting notes to publically verify in advance that these ciphertexts are valid.

Contributor

daira commented Jan 21, 2016

Selective transparency in the send direction requires extra key pairs (one for each subset of information that can be selectively revealed) to encrypt sent coins to the auditor. Note that the auditor can verify (per transaction) that the information they decrypt is correct once given the private key, because they can recompute from it the coin commitments cmnew1,2. This does not require a circuit change. However it is not possible with the protocol described in the meeting notes to publically verify in advance that these ciphertexts are valid.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jan 21, 2016

Contributor

I wrote:

However it is not possible with the protocol described in the meeting notes to publically verify in advance that these ciphertexts are valid.

That might not actually be a useful or enforceable property: even if you prove publically that there exist a decryption key or keys that would validly decrypt the information encrypted to the auditing key(s), those decryption keys could have been immediately destroyed.

Contributor

daira commented Jan 21, 2016

I wrote:

However it is not possible with the protocol described in the meeting notes to publically verify in advance that these ciphertexts are valid.

That might not actually be a useful or enforceable property: even if you prove publically that there exist a decryption key or keys that would validly decrypt the information encrypted to the auditing key(s), those decryption keys could have been immediately destroyed.

@nathan-at-least nathan-at-least added this to the Feb 15 milestone Feb 1, 2016

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Feb 9, 2016

Contributor

I wrote:

Selective transparency in the send direction requires extra key pairs (one for each subset of information that can be selectively revealed) to encrypt sent coins to the auditor. Note that the auditor can verify (per transaction) that the information they decrypt is correct once given the private key, because they can recompute from it the coin commitments cmnew1,2.

However, note that this only works for verifying the coin recipient address and value. The auditor cannot verify the memo field. Also the sender is only identified by virtue of being associated with the view key. (It isn't yet clear whether there will be any verifiable cryptographic binding between a view key and the corresponding public address.) We could make the memo field verifiable by committing to a hash of it in the coin commitment — this assumes that the auditor trusts the recipient's verification of this hash, since valid encryption is not checked by the circuit.

Contributor

daira commented Feb 9, 2016

I wrote:

Selective transparency in the send direction requires extra key pairs (one for each subset of information that can be selectively revealed) to encrypt sent coins to the auditor. Note that the auditor can verify (per transaction) that the information they decrypt is correct once given the private key, because they can recompute from it the coin commitments cmnew1,2.

However, note that this only works for verifying the coin recipient address and value. The auditor cannot verify the memo field. Also the sender is only identified by virtue of being associated with the view key. (It isn't yet clear whether there will be any verifiable cryptographic binding between a view key and the corresponding public address.) We could make the memo field verifiable by committing to a hash of it in the coin commitment — this assumes that the auditor trusts the recipient's verification of this hash, since valid encryption is not checked by the circuit.

@daira daira modified the milestones: Trafford spec and stuff, Feb 15 Feb 9, 2016

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Feb 9, 2016

Contributor

The implementation of this may or may not interact with #716.

Contributor

nathan-at-least commented Feb 9, 2016

The implementation of this may or may not interact with #716.

@zookozcash

This comment has been minimized.

Show comment
Hide comment
@ebfull

This comment has been minimized.

Show comment
Hide comment
@ebfull

ebfull Feb 10, 2016

Contributor

@daira Do you think there is a way to avoid increasing transaction size while committing to the memo field? Perhaps a clever use of hi? (Or changing the structure of the Coin commitment.)

Contributor

ebfull commented Feb 10, 2016

@daira Do you think there is a way to avoid increasing transaction size while committing to the memo field? Perhaps a clever use of hi? (Or changing the structure of the Coin commitment.)

@defuse

This comment has been minimized.

Show comment
Hide comment
@defuse

defuse Feb 11, 2016

Contributor

We need to decide on a formal definition of "selective transparency" that would be on par with the definitions of "ledger indistinguishability", "transaction non-malleability", and "balance" from the Zerocash paper. The Zerocash protocol wasn't designed with selective transparency and so any claim about what one can know having just skenc (or its equivalent in our new protocol) will need to be proven.

Contributor

defuse commented Feb 11, 2016

We need to decide on a formal definition of "selective transparency" that would be on par with the definitions of "ledger indistinguishability", "transaction non-malleability", and "balance" from the Zerocash paper. The Zerocash protocol wasn't designed with selective transparency and so any claim about what one can know having just skenc (or its equivalent in our new protocol) will need to be proven.

@defuse

This comment has been minimized.

Show comment
Hide comment
@defuse

defuse Feb 11, 2016

Contributor

In the last selective transparency meeting, we noticed (thanks to @daira) that transactions can be hidden from someone with the viewkey. Proof: When Alice sends money to Bob, they can agree that Alice won't send Ci but rather Ci ⊕K where K is some key Alice and Bob share. This will cause step 3.b.i of "Receive" in Figure 2 for the viewkey holder to fail. So the holder of Bob's viewkey will not see the transaction, but Bob can, by undoing the ⊕K before trial-decrypting.

(edit: We already knew this before that meeting, but it only just bubbled up to the surface in an important way.)

Contributor

defuse commented Feb 11, 2016

In the last selective transparency meeting, we noticed (thanks to @daira) that transactions can be hidden from someone with the viewkey. Proof: When Alice sends money to Bob, they can agree that Alice won't send Ci but rather Ci ⊕K where K is some key Alice and Bob share. This will cause step 3.b.i of "Receive" in Figure 2 for the viewkey holder to fail. So the holder of Bob's viewkey will not see the transaction, but Bob can, by undoing the ⊕K before trial-decrypting.

(edit: We already knew this before that meeting, but it only just bubbled up to the surface in an important way.)

@defuse

This comment has been minimized.

Show comment
Hide comment
@defuse

defuse Feb 11, 2016

Contributor

There's an another potential problem, which is a sort of "converse" to the one in the previous comment. The problem in the previous comment lets you hide real transactions from the viewkey holder. This second problem might let you show transactions to the viewkey holder that haven't really happened.

To carry out the "receive" operation in Figure 2 of the paper, ask is required in step 3.b.ii.second-bullet-point. A viewkey holder who doesn't know ask therefore can't actually complete the entire "receive" and therefore can't be sure that the holder of ask can spend the value the viewkey holder observed them to receive.

This raises questions:

  • If an organization puts up a donation address, and that organization has to pay taxes on donations, could I unfairly inflate their tax bill by sending them value the tax auditor would see, but they could never spend?
  • Can I do the same thing as above, but somehow make it so that I (the attacker) can spend those coins, instead of the coins getting destroyed? Could I make it look like I donated all my income to charity, but really I still have all of those coins?
Contributor

defuse commented Feb 11, 2016

There's an another potential problem, which is a sort of "converse" to the one in the previous comment. The problem in the previous comment lets you hide real transactions from the viewkey holder. This second problem might let you show transactions to the viewkey holder that haven't really happened.

To carry out the "receive" operation in Figure 2 of the paper, ask is required in step 3.b.ii.second-bullet-point. A viewkey holder who doesn't know ask therefore can't actually complete the entire "receive" and therefore can't be sure that the holder of ask can spend the value the viewkey holder observed them to receive.

This raises questions:

  • If an organization puts up a donation address, and that organization has to pay taxes on donations, could I unfairly inflate their tax bill by sending them value the tax auditor would see, but they could never spend?
  • Can I do the same thing as above, but somehow make it so that I (the attacker) can spend those coins, instead of the coins getting destroyed? Could I make it look like I donated all my income to charity, but really I still have all of those coins?
@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Mar 25, 2016

Contributor

The next step is for the spec to describe the more limited form of viewing key, for incoming transactions. (The crypto is already there; it just isn't described as such.)

Contributor

daira commented Mar 25, 2016

The next step is for the spec to describe the more limited form of viewing key, for incoming transactions. (The crypto is already there; it just isn't described as such.)

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira May 23, 2016

Contributor

See zcash/zips#50 for a security flaw in the original viewing key proposal, if we reinstate that at some point. (It persisted to a version of the spec after viewing keys were removed, and then was fixed.)

Contributor

daira commented May 23, 2016

See zcash/zips#50 for a security flaw in the original viewing key proposal, if we reinstate that at some point. (It persisted to a version of the spec after viewing keys were removed, and then was fixed.)

@daira daira removed this from the Trafford spec and stuff milestone Sep 30, 2016

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 24, 2016

Contributor

What's the current status of selective transparency?

We have explicit viewing keys in the protocol spec, code and database, which seem to provide receiver-side-per-account selective transparency. "Concepts in Zcash" (https://github.com/zcash/zcash/wiki/Concepts-in-Zcash) states so too.

However, it seems we don't have an RPC interface for passing them around and using them.

We also don't have a precise statement (let alone proof) of the soundness and completeness of using these keys, in light of the discussion in this issue and zcash/zips#50 .

Is this just a matter of documentation and adding RPC calls, or are there essential open issues?

Contributor

tromer commented Oct 24, 2016

What's the current status of selective transparency?

We have explicit viewing keys in the protocol spec, code and database, which seem to provide receiver-side-per-account selective transparency. "Concepts in Zcash" (https://github.com/zcash/zcash/wiki/Concepts-in-Zcash) states so too.

However, it seems we don't have an RPC interface for passing them around and using them.

We also don't have a precise statement (let alone proof) of the soundness and completeness of using these keys, in light of the discussion in this issue and zcash/zips#50 .

Is this just a matter of documentation and adding RPC calls, or are there essential open issues?

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Nov 10, 2016

Contributor

Related to zcash/zips#93 ("Independent ephemeral keys").

Contributor

tromer commented Nov 10, 2016

Related to zcash/zips#93 ("Independent ephemeral keys").

@zookozcash

This comment has been minimized.

Show comment
Hide comment
@zookozcash

zookozcash Nov 12, 2016

Here are some very interesting details on Monero's features. It says Monero has three different kinds of view keys: http://monero.stackexchange.com/questions/2566/selective-transparency-in-monero-vs-zcash

zookozcash commented Nov 12, 2016

Here are some very interesting details on Monero's features. It says Monero has three different kinds of view keys: http://monero.stackexchange.com/questions/2566/selective-transparency-in-monero-vs-zcash

@str4d str4d changed the title from Implement selective transparency to Implement selective disclosure Dec 2, 2016

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Dec 7, 2016

Contributor

I haven't caught up on backlog on this ticket yet. I wanted to make sure we're considering "the lowest hanging fruit" implementation of this which is to allow nodes to opt-in to persistently saving one-time encryption keys (either as recipient or sender) for each transaction.

Note: This would be at the cost of forward security (which requires both sides of a transaction to forget the one-time encryption key), but I feel that's ok as long as its communicated very clearly to users who make an explicit opt-in choice.

Contributor

nathan-at-least commented Dec 7, 2016

I haven't caught up on backlog on this ticket yet. I wanted to make sure we're considering "the lowest hanging fruit" implementation of this which is to allow nodes to opt-in to persistently saving one-time encryption keys (either as recipient or sender) for each transaction.

Note: This would be at the cost of forward security (which requires both sides of a transaction to forget the one-time encryption key), but I feel that's ok as long as its communicated very clearly to users who make an explicit opt-in choice.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jan 7, 2017

Contributor

A correction to @nathan-at-least's last comment: only the sender has an ephemeral key that is normally forgotten. The receiver's key is part of the address, pkenc. (The encryption is half-ephemeral, half-static Diffie-Hellman.)

Contributor

daira commented Jan 7, 2017

A correction to @nathan-at-least's last comment: only the sender has an ephemeral key that is normally forgotten. The receiver's key is part of the address, pkenc. (The encryption is half-ephemeral, half-static Diffie-Hellman.)

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Jan 7, 2017

Contributor

Another use case is when a user wants to prove that his z-address did not receive a transaction with certain properties (amount, sender address, blockheight range), e.g., during a dispute about whether a contract was fulfilled.

To prove this claim, this (non)recipient can reveal his all-incoming-transactions view key to the other party/arbitrator/judge, who can then scan the blockchain to verify the claim of non-receipt. However, this discloses too much unrelated information.

Disturbingly, because the above possibility exists, an arbitrator/judge may require that the (non)recepient does this to support his claim.

So, it would be nice to have a way to create a zero-knowledge proof (or conduct an interactive proof) of non-receipt of a transaction with specific attributes by a specific z-address.

Contributor

tromer commented Jan 7, 2017

Another use case is when a user wants to prove that his z-address did not receive a transaction with certain properties (amount, sender address, blockheight range), e.g., during a dispute about whether a contract was fulfilled.

To prove this claim, this (non)recipient can reveal his all-incoming-transactions view key to the other party/arbitrator/judge, who can then scan the blockchain to verify the claim of non-receipt. However, this discloses too much unrelated information.

Disturbingly, because the above possibility exists, an arbitrator/judge may require that the (non)recepient does this to support his claim.

So, it would be nice to have a way to create a zero-knowledge proof (or conduct an interactive proof) of non-receipt of a transaction with specific attributes by a specific z-address.

@zmanian

This comment has been minimized.

Show comment
Hide comment
@zmanian

zmanian Jan 9, 2017

I don't think #1997 and #1996 fully depend on this issue.

To the wallet, it isn't practically much different from having an encrypted spending key.

zmanian commented Jan 9, 2017

I don't think #1997 and #1996 fully depend on this issue.

To the wallet, it isn't practically much different from having an encrypted spending key.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jan 9, 2017

Contributor

#1997 and zcash/zips#101 (moved from #1996) indeed don't depend on this issue; they only depend on the existing Zcash 1.0 protocol support for incoming viewing keys.

Contributor

daira commented Jan 9, 2017

#1997 and zcash/zips#101 (moved from #1996) indeed don't depend on this issue; they only depend on the existing Zcash 1.0 protocol support for incoming viewing keys.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Jan 9, 2017

Contributor

We do not have a precise statement, let alone proof, of the soundness and completeness properties of these viewing keys (in light of the discussion above and zcash/zips#50).

Also, we have not established terminology for the various different keys involved in different forms of selective disclosure.

Yes, the "viewing keys" defined in the spec will probably turn out (as intended) to be what's needed for some form of selective disclosure; but they are currently a half-baked concept and it is premature to expose them to users.

Contributor

tromer commented Jan 9, 2017

We do not have a precise statement, let alone proof, of the soundness and completeness properties of these viewing keys (in light of the discussion above and zcash/zips#50).

Also, we have not established terminology for the various different keys involved in different forms of selective disclosure.

Yes, the "viewing keys" defined in the spec will probably turn out (as intended) to be what's needed for some form of selective disclosure; but they are currently a half-baked concept and it is premature to expose them to users.

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Apr 18, 2017

Contributor

I need to recalculate the cost when combined with #647 (and maybe #2277).

Contributor

daira commented Apr 18, 2017

I need to recalculate the cost when combined with #647 (and maybe #2277).

@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Jun 1, 2017

Contributor

I wrote on Rocket Chat:

So, although I'm a huge fan of selective [disclosure], note that a major goal for Sapling is to greatly improve proving performance. If we add outgoing viewing keys with circuit-enforced completeness (i.e. the holder of an outgoing viewing key is assured that they have all the disclosures for outgoing transfers from a given address), then that's quite expensive in terms of circuit cost, relative to the cost of the rest of the new faster circuit. (Basically ChaCha20 has similar performance in the circuit to SHA-256 when encrypting/hashing the same amount of data, and the main performance benefit of Sapling comes from avoiding SHA-256.)

Unless, that is, we also switch from ChaCha20 to a circuit-efficient cipher, e.g. MiMC, for the note encryption.

[or a discrete-log-based symmetric cipher, if that would be less expensive than ChaCha20]

(The Poly1305 authentication is already circuit-efficient.) This is feasible, but I'm inclined to think that it blows the complexity/security analysis budget for Sapling.

Another alternative is to add outgoing viewing keys without circuit-enforced completeness for Sapling, and then maybe add that enforcement (possibly with a change to the note encryption to make it more efficient) in a later circuit change. But there was some pushback in previous engineering and selective-disclosure topical meetings against the idea of adding outgoing viewing keys with weaker completeness properties, on the grounds that users could think they provide the stronger property (and then adding that property later would require them to reason about whether it is achieved depending on what version of viewing key they have).

And that was why I haven't pressed for outgoing viewing keys in Sapling. (I think @nathan and I discussed this reasoning in a triage or roadmapping meeting but it hasn't come up in wider meetings, so I should put it on the #406 ticket.)

It also depends to some extent on how conservative we want to be with the crypto primitives used in Sapling. If we end up using Pedersen-based hashes and commitments (the more conservative option), then that's consistent with leaving the note encryption as it is, and either omitting outgoing viewing keys or using the weaker variant. If we end up using MiMC-based hashes and (possibly) commitments, then that's consistent with also changing the note encryption to MiMC because we'd already be relying on it.

If MiMC had more third-party cryptanalytic attention, I'd be more confident about switching to it, although maybe still not in Sapling. (Cryptanalysts: go break reduced-round MiMC, please!)

Contributor

daira commented Jun 1, 2017

I wrote on Rocket Chat:

So, although I'm a huge fan of selective [disclosure], note that a major goal for Sapling is to greatly improve proving performance. If we add outgoing viewing keys with circuit-enforced completeness (i.e. the holder of an outgoing viewing key is assured that they have all the disclosures for outgoing transfers from a given address), then that's quite expensive in terms of circuit cost, relative to the cost of the rest of the new faster circuit. (Basically ChaCha20 has similar performance in the circuit to SHA-256 when encrypting/hashing the same amount of data, and the main performance benefit of Sapling comes from avoiding SHA-256.)

Unless, that is, we also switch from ChaCha20 to a circuit-efficient cipher, e.g. MiMC, for the note encryption.

[or a discrete-log-based symmetric cipher, if that would be less expensive than ChaCha20]

(The Poly1305 authentication is already circuit-efficient.) This is feasible, but I'm inclined to think that it blows the complexity/security analysis budget for Sapling.

Another alternative is to add outgoing viewing keys without circuit-enforced completeness for Sapling, and then maybe add that enforcement (possibly with a change to the note encryption to make it more efficient) in a later circuit change. But there was some pushback in previous engineering and selective-disclosure topical meetings against the idea of adding outgoing viewing keys with weaker completeness properties, on the grounds that users could think they provide the stronger property (and then adding that property later would require them to reason about whether it is achieved depending on what version of viewing key they have).

And that was why I haven't pressed for outgoing viewing keys in Sapling. (I think @nathan and I discussed this reasoning in a triage or roadmapping meeting but it hasn't come up in wider meetings, so I should put it on the #406 ticket.)

It also depends to some extent on how conservative we want to be with the crypto primitives used in Sapling. If we end up using Pedersen-based hashes and commitments (the more conservative option), then that's consistent with leaving the note encryption as it is, and either omitting outgoing viewing keys or using the weaker variant. If we end up using MiMC-based hashes and (possibly) commitments, then that's consistent with also changing the note encryption to MiMC because we'd already be relying on it.

If MiMC had more third-party cryptanalytic attention, I'd be more confident about switching to it, although maybe still not in Sapling. (Cryptanalysts: go break reduced-round MiMC, please!)

@ebfull

This comment has been minimized.

Show comment
Hide comment
@ebfull

ebfull Feb 16, 2018

Contributor

I think @tromer was totally right to say viewing keys should not have been exposed to users, especially with Sapling changing their capabilities before we even had a chance to fully document what the guarantees of Sprout were.

Contributor

ebfull commented Feb 16, 2018

I think @tromer was totally right to say viewing keys should not have been exposed to users, especially with Sapling changing their capabilities before we even had a chance to fully document what the guarantees of Sprout were.

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