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

ZIP: Delegated Proving T (DPT) Protocol #104

Closed
nathan-at-least opened this Issue Feb 6, 2017 · 10 comments

Comments

Projects
None yet
4 participants
@nathan-at-least

nathan-at-least commented Feb 6, 2017

Use Case

Roughly, there is a light wallet, a proving service, and some way to interact with the blockchain.

Concrete Cases

a. JAXX-like: light wallet is written in JS and may not have sufficient RAM for proving. It relies on a third party service for learning about UTXOs, block headers, relaying transactions. It uses a public proving service.
b. HSM + Proving Cluster: Same enterprise operates HSM and proving cluster, but the proving cluster cannot meet some security requirements. HSM can execute light wallet logic.
c. Hardware Wallets, desktop or website prover: Similar to case b in that the light wallet logic may live on an embedded device. May be like case b if prover is on a local desktop, may be like a if prover is a web service.

Note for a or c where there is a web service, it may or may not charge a fee for the service. Protocols should accommodate that if possible.

Two Protocol Categories

(Note: Let's exclude DPZ category from the topical meeting until the DPT case is well covered.)

a. Delegated Proving T (DPT) - a light wallet sends from t-addr to z-addr via proving service.
b. Delegated Proving Z (DPZ) - a light wallet sends from z-addr to z-addr via proving service.

Overlap:

  • Both T & Z variants prevent the proving service from absconding w/ funds.
  • Both sacrifice privacy to proving service. (Is this true for DPZ?)

Differences:

  • DPT does not bestow any privacy benefit against blockchain observers, whereas DPZ does.
  • DPZ allows light wallet to receive funds at a z-addr.

DPT-a Sketch

Assume light wallet has full blockchain view, but not the proving service.

#. light wallet hands proving service everything necessary to generate a proof sending from t-addr (controlled by light wallet) to z-addr, including:

  • all of the public and private inputs to the circuit (rt, nf^old_*, a_pk, v, r, phi, hSig, etc.)
  • the output note pre-image (excluding memo field) which encodes the correct value transfer to the correct recipient z-addr,
  • the vpub_in amount,

#. proving service generates proof, hands back to light wallet.
#. light wallet verifies the output commitment is derived from the note pre-image it requested.
#. [Optional?] light wallet verifies the zkSNARK.
#. light wallet constructs a CTransaction with sufficient funds to pay the vpub_in.
#. light wallet submits to network.

Questions

  • Is the list in step 1 sufficient info?

  • If the proving service is truly unaware of the blockchain how badly could malicious clients abuse it?

  • If the proving service is connected to the blockchain, it could require the wallet sends UTXOs to prove that it's request is goodish (including the fee), but how could it deal with double-spends or other mischief?

  • Implementation Roadmap:

    • Since this is a single request and response, I imagine an HTTP binding would be sensible, especially for web-wallets. Is it?
    • What's the best target for a MVP version of the client and server?
    • Can we provide minimal proving service functionality as a zcashd rpc call, then write a Proof-of-Concept web server in python?
    • Or is it better to write a stand-alone daemon w/ a totally new interface? (It seems to depend heavily on if the proving service needs to be blockchain-aware.)
    • Can we create a JS library that is the core of the light wallet side for a Proof-of-Concept?
    • Can we start a ZIP that specifies a specific HTTP-based protocol binding?
@arielgabizon

This comment has been minimized.

Show comment
Hide comment
@arielgabizon

arielgabizon Feb 7, 2017

Contributor

CTransaction = Complete Transaction?
The one time ecdsa key is want corresponds to joinsplitPubKey in the spec?

Contributor

arielgabizon commented Feb 7, 2017

CTransaction = Complete Transaction?
The one time ecdsa key is want corresponds to joinsplitPubKey in the spec?

@arielgabizon

This comment has been minimized.

Show comment
Hide comment
@arielgabizon

arielgabizon Feb 7, 2017

Contributor

Notes from discussion:
DPZ can work for addresses containing only a single note,
by revealing you secret key to delegated prover.
Prover doesn't need memo field.
Should we give Prover as much data as possible -i.e. also rho, and r of note,
or, as little, i.e. just a_pk
Can the prover do anthing bad if they choose rho,r?
Seems not much..except weaken privacy on blockchain, by choosing low entropy r,
or low entropy anchor.
Seems better sender chooses everything - anchor,r,rho..
Should there be a fee to the delegated prover?
Should it be part of this transaction? Using a second z-output of the joinsplit?

Can give prover H_sig directly so it won't need randomseed and joinsplitpubkey..
so maybe joinSplitPubKey doesn't need to be sent to Prover?

If we do it in a way that we're giving the prover all data of dummy notes, including a_sk the same code could be used for the DPZ (assuming sender trusts Prover with his a_sk,e.g. when it's address containing only this note)

Should there be separate binaries for the client/server? Should it be part of zcashd?
Separate binary seems easier to integrate.

Give prover less data using circuit change?
Seems with two commitment layers as in ZeroCash can avoid giving them a_pk of new note
Engineering wise -
RPC with single request? TLS?
ZMQ?
Retain openssl as dependency?
Daira trusts TLS and CurveCP.
BoringSSL from Google?
Json RPC seems easier.
Reuse stuff from Zcash RPC protocol?
Seem orthogonal questions to protocol design.

Questions about boundaries..

Contributor

arielgabizon commented Feb 7, 2017

Notes from discussion:
DPZ can work for addresses containing only a single note,
by revealing you secret key to delegated prover.
Prover doesn't need memo field.
Should we give Prover as much data as possible -i.e. also rho, and r of note,
or, as little, i.e. just a_pk
Can the prover do anthing bad if they choose rho,r?
Seems not much..except weaken privacy on blockchain, by choosing low entropy r,
or low entropy anchor.
Seems better sender chooses everything - anchor,r,rho..
Should there be a fee to the delegated prover?
Should it be part of this transaction? Using a second z-output of the joinsplit?

Can give prover H_sig directly so it won't need randomseed and joinsplitpubkey..
so maybe joinSplitPubKey doesn't need to be sent to Prover?

If we do it in a way that we're giving the prover all data of dummy notes, including a_sk the same code could be used for the DPZ (assuming sender trusts Prover with his a_sk,e.g. when it's address containing only this note)

Should there be separate binaries for the client/server? Should it be part of zcashd?
Separate binary seems easier to integrate.

Give prover less data using circuit change?
Seems with two commitment layers as in ZeroCash can avoid giving them a_pk of new note
Engineering wise -
RPC with single request? TLS?
ZMQ?
Retain openssl as dependency?
Daira trusts TLS and CurveCP.
BoringSSL from Google?
Json RPC seems easier.
Reuse stuff from Zcash RPC protocol?
Seem orthogonal questions to protocol design.

Questions about boundaries..

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Feb 20, 2017

@arielgabizon

CTransaction = Complete Transaction?

I often refer to the C++ class called CTransaction when I mean just 'transactions'. This is an old habit back in the day when JoinSplits were called PourTransaction which was incredibly confusing since these two entities lived at different layers in the protocol and one is embedded in the other.

nathan-at-least commented Feb 20, 2017

@arielgabizon

CTransaction = Complete Transaction?

I often refer to the C++ class called CTransaction when I mean just 'transactions'. This is an old habit back in the day when JoinSplits were called PourTransaction which was incredibly confusing since these two entities lived at different layers in the protocol and one is embedded in the other.

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Feb 22, 2017

Contributor

In zcash/zcash#1113 (comment) I have listed what zcash/zcash#2120 currently sends over the wire for proving. The information set is sufficient for both DPT, and DPZ where the prover is given the spending key. More importantly, it ensures that the proving service does not select any of the random values (for either regular Note components or dummy Note values), so they have zero ability to influence the resulting transaction other than providing an invalid proof (per the discussion in the topical meeting).

Specification side-notes:

  • Whatever we send over the wire should be versioned, so we can change the format later (e.g for better DPZ or new requirements after a circuit change).
  • I used ZMQ instead of JSON-RPC in zcash/zcash#2120 because it was far simpler to prototype (the JSON-RPC server is not currently modular enough to use outside of zcashd).
Contributor

str4d commented Feb 22, 2017

In zcash/zcash#1113 (comment) I have listed what zcash/zcash#2120 currently sends over the wire for proving. The information set is sufficient for both DPT, and DPZ where the prover is given the spending key. More importantly, it ensures that the proving service does not select any of the random values (for either regular Note components or dummy Note values), so they have zero ability to influence the resulting transaction other than providing an invalid proof (per the discussion in the topical meeting).

Specification side-notes:

  • Whatever we send over the wire should be versioned, so we can change the format later (e.g for better DPZ or new requirements after a circuit change).
  • I used ZMQ instead of JSON-RPC in zcash/zcash#2120 because it was far simpler to prototype (the JSON-RPC server is not currently modular enough to use outside of zcashd).
@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Feb 22, 2017

Contributor

@nathan-at-least re: your original DPT sketch:

  1. light wallet hands proving service everything necessary to generate a proof sending from t-addr (controlled by light wallet) to z-addr, including:
  • all of the public and private inputs to the circuit (rt, nf^old_*, a_pk, v, r, phi, hSig, etc.)
  • the output note pre-image (excluding memo field) which encodes the correct value transfer to the correct recipient z-addr,
  • the vpub_in amount,
  1. proving service generates proof, hands back to light wallet.
  2. light wallet verifies the output commitment is derived from the note pre-image it requested.

I am confused about point 3. If the light wallet hands the proving service everything necessary to generate a proof, it can already derive the output commitment. More specifically, I don't see a way to validate the server's response other than verifying the proof. If the client sends insufficient information such that it requires the server to choose values and compute commitments, then the server can return those values and the client can verify that the commitment provided by the server is equal to what they calculate with the server's randomness and their own note pre-images. However, that doesn't constrain the proof on-the-wire - IIUC, given a commitment and a proof, there is no way to validate that the proof took that commitment as input without actually validating the proof, which could contain random data for all we know.

Contributor

str4d commented Feb 22, 2017

@nathan-at-least re: your original DPT sketch:

  1. light wallet hands proving service everything necessary to generate a proof sending from t-addr (controlled by light wallet) to z-addr, including:
  • all of the public and private inputs to the circuit (rt, nf^old_*, a_pk, v, r, phi, hSig, etc.)
  • the output note pre-image (excluding memo field) which encodes the correct value transfer to the correct recipient z-addr,
  • the vpub_in amount,
  1. proving service generates proof, hands back to light wallet.
  2. light wallet verifies the output commitment is derived from the note pre-image it requested.

I am confused about point 3. If the light wallet hands the proving service everything necessary to generate a proof, it can already derive the output commitment. More specifically, I don't see a way to validate the server's response other than verifying the proof. If the client sends insufficient information such that it requires the server to choose values and compute commitments, then the server can return those values and the client can verify that the commitment provided by the server is equal to what they calculate with the server's randomness and their own note pre-images. However, that doesn't constrain the proof on-the-wire - IIUC, given a commitment and a proof, there is no way to validate that the proof took that commitment as input without actually validating the proof, which could contain random data for all we know.

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Feb 23, 2017

Contributor

Comment from @ebfull in dev chat:

one thing i need to mention is that this would be the first time that our protocol involves serialization of IncrementalWitness
serialization of IncrementalWitness is not fully specified nor have i verified that it is protected against malleability
typically the structure is kept local to our client

Contributor

str4d commented Feb 23, 2017

Comment from @ebfull in dev chat:

one thing i need to mention is that this would be the first time that our protocol involves serialization of IncrementalWitness
serialization of IncrementalWitness is not fully specified nor have i verified that it is protected against malleability
typically the structure is kept local to our client

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Feb 24, 2017

Contributor

More ZIP-relevant design discussion: zcash/zcash#1113 (comment)

Contributor

str4d commented Feb 24, 2017

More ZIP-relevant design discussion: zcash/zcash#1113 (comment)

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Feb 24, 2017

Contributor

One takeaway of the above discussion is that the API should enable sending multiple requests for proofs at once to the proving service. In particular, it is doable and desirable to be able to send most or all JSProofWitnesss for a chained JoinSplit at once:

  • The transaction's entire vjoinsplit can be filled out without proofs, because chained JoinSplit roots only require knowing the commitments.
  • The proving service may want to enforce that it is paid at the start of a chain.

The next logical question is, should the wire format enable encoding of the chaining (to make the proving service's job easier) at the expense of providing more contextual information (that the proving service could figure out on its own eventually anyway)? There are three possible formats for a request:

  • JSProofWitness (one per request)
    • Proving service would need to be stateful to enforce payment by remembering multiple requests (or out-of-band client info)
  • std::vector<JSProofWitness>
    • Proving service no longer requires internal state to check for payment
    • Would require blockchain to figure out JS ordering to check it will get paid
  • std::vector<std::vector<JSProofWitness>>
    • Grouped by transaction (assuming honest client, but proving service can fall back to list form)
    • Proving service can now easily figure out where it is in the chain
    • Can also easily see groupings of transactions
      • Could maybe start requiring additional fees based on transaction layouts?
Contributor

str4d commented Feb 24, 2017

One takeaway of the above discussion is that the API should enable sending multiple requests for proofs at once to the proving service. In particular, it is doable and desirable to be able to send most or all JSProofWitnesss for a chained JoinSplit at once:

  • The transaction's entire vjoinsplit can be filled out without proofs, because chained JoinSplit roots only require knowing the commitments.
  • The proving service may want to enforce that it is paid at the start of a chain.

The next logical question is, should the wire format enable encoding of the chaining (to make the proving service's job easier) at the expense of providing more contextual information (that the proving service could figure out on its own eventually anyway)? There are three possible formats for a request:

  • JSProofWitness (one per request)
    • Proving service would need to be stateful to enforce payment by remembering multiple requests (or out-of-band client info)
  • std::vector<JSProofWitness>
    • Proving service no longer requires internal state to check for payment
    • Would require blockchain to figure out JS ordering to check it will get paid
  • std::vector<std::vector<JSProofWitness>>
    • Grouped by transaction (assuming honest client, but proving service can fall back to list form)
    • Proving service can now easily figure out where it is in the chain
    • Can also easily see groupings of transactions
      • Could maybe start requiring additional fees based on transaction layouts?
@daira

This comment has been minimized.

Show comment
Hide comment
@daira

daira Feb 24, 2017

Contributor

The third form doesn't seem to be necessary, because it can be expressed as multiple messages of the second form. In order to check that it will either get paid or produce proofs that are useless to the client, the proving service only needs to check that all of the anchors in messages of the second form are dependent on the first anchor (and that it is paid by the first JoinSplit). The third form doesn't help it to do that any more easily.

Contributor

daira commented Feb 24, 2017

The third form doesn't seem to be necessary, because it can be expressed as multiple messages of the second form. In order to check that it will either get paid or produce proofs that are useless to the client, the proving service only needs to check that all of the anchors in messages of the second form are dependent on the first anchor (and that it is paid by the first JoinSplit). The third form doesn't help it to do that any more easily.

@str4d

This comment has been minimized.

Show comment
Hide comment
@str4d

str4d Feb 24, 2017

Contributor

There's actually an extra degree of freedom in the second form: the list can either be constrained to be all from the same transaction, or a grab bag of multiple transactions. The third form simply makes this distinction concrete.

What I'm trying to reason about here is whether a client or server might want to request proofs from separate transactions or not, and how the server's desire to enforce payment might restrict that ability. From a ZIP level, we could just say "the wire format is a list of JoinSplit inputs" and leave any higher-level considerations to specific implementations, but is that unambiguous enough? Conversely, if we specify e.g. that all JoinSplits in a request must be chained, is that too restricting?

Contributor

str4d commented Feb 24, 2017

There's actually an extra degree of freedom in the second form: the list can either be constrained to be all from the same transaction, or a grab bag of multiple transactions. The third form simply makes this distinction concrete.

What I'm trying to reason about here is whether a client or server might want to request proofs from separate transactions or not, and how the server's desire to enforce payment might restrict that ability. From a ZIP level, we could just say "the wire format is a list of JoinSplit inputs" and leave any higher-level considerations to specific implementations, but is that unambiguous enough? Conversely, if we specify e.g. that all JoinSplits in a request must be chained, is that too restricting?

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