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

Alternative Fully-Verifying Node in Rust #32

Open
jasondavies opened this Issue Sep 15, 2017 · 43 comments

Comments

Projects
None yet
9 participants
@jasondavies

jasondavies commented Sep 15, 2017

[Edit: after feedback and some last-minute changes, I initially submitted a proposal that focused on optimising zk-SNARK verification; and later made another submission that more closely follows my original plan of a full alternative implementation in Rust.]

Motivation and overview

The primary aim is to provide an alternative fully-validating implementation for network robustness: supposing some strange implementation error is found in the Zcash reference client, having alternative implementations that do not have this error would help keep the network running if the error was to be exploited, and would help detection of any error in the case where the network stays up but the main chain was determined to be invalid by the alternative implementation.

In addition, using Rust, a memory-safe language, improves security by eliminating particular types of bugs. Adding wallet and proving functionality in the future would make this a fully-functioning client.

Technical approach

I propose porting an existing Rust-based Bitcoin client, parity-bitcoin to support full validation of the Zcash blockchain. I have already written a Rust-based verifier for Zcash zk-SNARK proofs, so it should be easy to include this. I think full proving support and porting wallet functionality are both out of scope for this proposal.

Background and qualifications

MA (Cantab) CompSci, Univ. of Cambridge, contributor to various open-source projects including Apache CouchDB and D3.js.

I've been following Zcash since its inception and have made some minor contributions so far:

Evaluation plan

If successful, the alternative implementation should have the ability to fully validate transactions on the Zcash network and relay valid transactions to other nodes.

Schedule

The following milestones are anticipated:

  • Ensure that Zcash blocks can be parsed and validated, but excluding shielded transactions; all changes to the consensus protocol relative to Bitcoin need to be supported e.g. difficulty algorithm changes, mining reward schedule. I anticipate this will be around 50% of the work.
  • Validate shielded transactions using zcash-sprout-verifier. This requires implementing various Zcash-specific things such as the incremental merkle tree etc. and should be around 50% of the work.

Security considerations

Since the intention is to use this for validation only, security considerations are not as important per se as they do not impact wallets directly, and other nodes on the network will validate any transactions that this implementation will relay. In the future, the code would need to be extensively reviewed if wallet/proving functionality was to be added.

Budget and justification

I estimate around $45k would be sufficient to support the development work. Note that I have submitted a separate proposal, #29, so if both are accepted this might affect turnaround time slightly, but I expect this to take 2-3 months.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Sep 16, 2017

Collaborator

What are your thoughts on having such verifying nodes running continuously and providing real-time alerts on anomalies? Can you commit to running one yourself, say for 12 months?

Collaborator

tromer commented Sep 16, 2017

What are your thoughts on having such verifying nodes running continuously and providing real-time alerts on anomalies? Can you commit to running one yourself, say for 12 months?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Sep 16, 2017

Good idea. I would be happy to commit to running a fully-verifying node myself for 12 months. The latest verification status could be viewed on a website. Perhaps anomaly alerts could also be tweeted automatically?

jasondavies commented Sep 16, 2017

Good idea. I would be happy to commit to running a fully-verifying node myself for 12 months. The latest verification status could be viewed on a website. Perhaps anomaly alerts could also be tweeted automatically?

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Sep 17, 2017

Collaborator

Might this Rust code be useful for some in-browser functionality (say, via emscripten)?

Collaborator

tromer commented Sep 17, 2017

Might this Rust code be useful for some in-browser functionality (say, via emscripten)?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Sep 17, 2017

Yes, Rust can already be compiled to WebAssembly or asm.js via emscripten, and there is also an ongoing effort to do this without requiring emscripten by using the LLVM wasm backend directly, which could be useful for minimally-sized, reusable components.

I think validating transactions in-browser should be quite feasible, which might be useful for various applications such as SPV clients. You would still need some way to query the nullifier set and commitment tree in order to validate shielded transactions though, and browser storage limitations would make this non-trivial.

jasondavies commented Sep 17, 2017

Yes, Rust can already be compiled to WebAssembly or asm.js via emscripten, and there is also an ongoing effort to do this without requiring emscripten by using the LLVM wasm backend directly, which could be useful for minimally-sized, reusable components.

I think validating transactions in-browser should be quite feasible, which might be useful for various applications such as SPV clients. You would still need some way to query the nullifier set and commitment tree in order to validate shielded transactions though, and browser storage limitations would make this non-trivial.

@zmanian

This comment has been minimized.

Show comment
Hide comment
@zmanian

zmanian Sep 17, 2017

Have you done much experimentation with partity-bitcoin on the mainnet? Is it relatively stable while syncing the Bitcoin blockchain?

I haven't heard from too much people who have been running their node day to day.

zmanian commented Sep 17, 2017

Have you done much experimentation with partity-bitcoin on the mainnet? Is it relatively stable while syncing the Bitcoin blockchain?

I haven't heard from too much people who have been running their node day to day.

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Sep 17, 2017

Have you done much experimentation with parity-bitcoin on the mainnet? Is it relatively stable while syncing the Bitcoin blockchain?

I'm running a node now and synchronising from scratch with Bitcoin mainnet to see how it goes (~10% of blocks downloaded so far). I like the fact that parity-bitcoin is modular, and my hope is that this alternative fully-validating node for Zcash can be simpler than parity-bitcoin (at least initially) by removing unnecessary modules and code that would otherwise be required for RPC and wallet functionality.

jasondavies commented Sep 17, 2017

Have you done much experimentation with parity-bitcoin on the mainnet? Is it relatively stable while syncing the Bitcoin blockchain?

I'm running a node now and synchronising from scratch with Bitcoin mainnet to see how it goes (~10% of blocks downloaded so far). I like the fact that parity-bitcoin is modular, and my hope is that this alternative fully-validating node for Zcash can be simpler than parity-bitcoin (at least initially) by removing unnecessary modules and code that would otherwise be required for RPC and wallet functionality.

@zookozcash

This comment has been minimized.

Show comment
Hide comment
@zookozcash

zookozcash Sep 19, 2017

How's parity-bitcoin's test coverage?

zookozcash commented Sep 19, 2017

How's parity-bitcoin's test coverage?

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Sep 26, 2017

From a comment above @jasondavies says he hopes this project would be simpler by

removing unnecessary modules and code that would otherwise be required for RPC and wallet functionality.

However, when I look at the RPC interface specification I don't see any wallet functionality, such as address generation, transferring funds, etc…

If there's already no wallet functionality, this proposal is simpler. However, I advocate keeping the existing documented RPC interface and avoiding regressions against it. That interface makes a good building block for wallets, exchanges, block explorers, etc… to be built on top of this node, while keeping the feature scope of the node simple.

Also, it would help to know if excluding wallet functionality is the plan of upstream developers. If so, it would make tracking this new port against upstream simpler.

@jasondavies, have you interacted with the parity-bitcoin developers? Do you know their roadmap and/or feature scope?

nathan-at-least commented Sep 26, 2017

From a comment above @jasondavies says he hopes this project would be simpler by

removing unnecessary modules and code that would otherwise be required for RPC and wallet functionality.

However, when I look at the RPC interface specification I don't see any wallet functionality, such as address generation, transferring funds, etc…

If there's already no wallet functionality, this proposal is simpler. However, I advocate keeping the existing documented RPC interface and avoiding regressions against it. That interface makes a good building block for wallets, exchanges, block explorers, etc… to be built on top of this node, while keeping the feature scope of the node simple.

Also, it would help to know if excluding wallet functionality is the plan of upstream developers. If so, it would make tracking this new port against upstream simpler.

@jasondavies, have you interacted with the parity-bitcoin developers? Do you know their roadmap and/or feature scope?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Sep 28, 2017

How's parity-bitcoin's test coverage?

Unfortunately I'm encountering some difficulty actually computing coverage statistics (for some reason kcov isn't playing nicely with Rust binaries). Overall, it looks like there are a few hundred tests. In terms of quality and coverage, however, this is not really clear and I'm guessing it could probably be improved (based on a cursory glance).

jasondavies commented Sep 28, 2017

How's parity-bitcoin's test coverage?

Unfortunately I'm encountering some difficulty actually computing coverage statistics (for some reason kcov isn't playing nicely with Rust binaries). Overall, it looks like there are a few hundred tests. In terms of quality and coverage, however, this is not really clear and I'm guessing it could probably be improved (based on a cursory glance).

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Sep 28, 2017

However, when I look at the RPC interface specification I don't see any wallet functionality, such as address generation, transferring funds, etc…

You're absolutely right, there is no wallet functionality in parity-bitcoin at the moment.

If there's already no wallet functionality, this proposal is simpler. However, I advocate keeping the existing documented RPC interface and avoiding regressions against it. That interface makes a good building block for wallets, exchanges, block explorers, etc… to be built on top of this node, while keeping the feature scope of the node simple.

OK, that does make sense. I was attempting to limit the scope of the proposal somewhat, but I suppose maintaining the RPC interface is not going to be too difficult.

Also, it would help to know if excluding wallet functionality is the plan of upstream developers. If so, it would make tracking this new port against upstream simpler.

I've opened an issue to ask about this: paritytech/parity-bitcoin#404.

jasondavies commented Sep 28, 2017

However, when I look at the RPC interface specification I don't see any wallet functionality, such as address generation, transferring funds, etc…

You're absolutely right, there is no wallet functionality in parity-bitcoin at the moment.

If there's already no wallet functionality, this proposal is simpler. However, I advocate keeping the existing documented RPC interface and avoiding regressions against it. That interface makes a good building block for wallets, exchanges, block explorers, etc… to be built on top of this node, while keeping the feature scope of the node simple.

OK, that does make sense. I was attempting to limit the scope of the proposal somewhat, but I suppose maintaining the RPC interface is not going to be too difficult.

Also, it would help to know if excluding wallet functionality is the plan of upstream developers. If so, it would make tracking this new port against upstream simpler.

I've opened an issue to ask about this: paritytech/parity-bitcoin#404.

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Sep 28, 2017

This discussion about consensus compatibility is also somewhat relevant: paritytech/parity-bitcoin#404.

To alleviate the concerns raised about consensus compatibility when using different implementations, I would suggest:

  • This alternative, pure-Rust, fully-verifying node should initially be used in an experimental fashion to detect network issues and improve the robustness of the network rather than being advertised as a complete replacement. In other words, users should be warned about the risks of using an alternative implementation.
  • In the cases where users may require a complete replacement e.g. exchanges etc., we could alleviate the consensus compatibility concern by optionally running both a pure-Rust consensus library and the standard libzcashconsensus library. However, I would prefer this as a "nice-to-have" feature in order to keep this proposal limited in scope.

Of course, my hope is that the Zcash reference client will eventually have a pure-Rust consensus library that everyone can use, but before that happens, it's important to ensure the risks of multiple implementations are understood and handled properly.

jasondavies commented Sep 28, 2017

This discussion about consensus compatibility is also somewhat relevant: paritytech/parity-bitcoin#404.

To alleviate the concerns raised about consensus compatibility when using different implementations, I would suggest:

  • This alternative, pure-Rust, fully-verifying node should initially be used in an experimental fashion to detect network issues and improve the robustness of the network rather than being advertised as a complete replacement. In other words, users should be warned about the risks of using an alternative implementation.
  • In the cases where users may require a complete replacement e.g. exchanges etc., we could alleviate the consensus compatibility concern by optionally running both a pure-Rust consensus library and the standard libzcashconsensus library. However, I would prefer this as a "nice-to-have" feature in order to keep this proposal limited in scope.

Of course, my hope is that the Zcash reference client will eventually have a pure-Rust consensus library that everyone can use, but before that happens, it's important to ensure the risks of multiple implementations are understood and handled properly.

@acityinohio

This comment has been minimized.

Show comment
Hide comment
@acityinohio

acityinohio Oct 4, 2017

Collaborator

Every informal proposal has multiple reviews by the review committee. The reviews are being collected and discussed in a private google doc (the 5 reviewers all have edit access to it, no one else can view it). By way of early, informal feedback, the reviewers have made a list of projects that they consider leading candidates for grant funding.

In that vein, your project was selected as one of the leading candidates, and the review committee encourages you to submit a full proposal by October 6th and looks forward to reviewing it.

Collaborator

acityinohio commented Oct 4, 2017

Every informal proposal has multiple reviews by the review committee. The reviews are being collected and discussed in a private google doc (the 5 reviewers all have edit access to it, no one else can view it). By way of early, informal feedback, the reviewers have made a list of projects that they consider leading candidates for grant funding.

In that vein, your project was selected as one of the leading candidates, and the review committee encourages you to submit a full proposal by October 6th and looks forward to reviewing it.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 5, 2017

Collaborator

@jasondavies The tentative $45k budget is a large fraction of the total funds available for the 2017 Q4 Grants round, and this affects the probability of funding the proposal.

Is it feasible to break the work into two stages, allowing the committee to fund only the first stage in the current Grants round, and hopefully fund the second stage in the next Grants round? If so, please include both stages in your proposal, but demarcate their schedule and budget. The first stage should still be meaningful and useful by itself.

Also, can you clarify your position on open-source distribution of the code?

Collaborator

tromer commented Oct 5, 2017

@jasondavies The tentative $45k budget is a large fraction of the total funds available for the 2017 Q4 Grants round, and this affects the probability of funding the proposal.

Is it feasible to break the work into two stages, allowing the committee to fund only the first stage in the current Grants round, and hopefully fund the second stage in the next Grants round? If so, please include both stages in your proposal, but demarcate their schedule and budget. The first stage should still be meaningful and useful by itself.

Also, can you clarify your position on open-source distribution of the code?

@acityinohio

This comment has been minimized.

Show comment
Hide comment
@acityinohio

acityinohio Oct 6, 2017

Collaborator

As you may have seen in the other issue @jasondavies, but just in case you didn't: just a reminder that the submission deadline is October 6th! Please endeavor to have a final proposal submitted by then, as an attachment to this issue (and yes, it can be October 6th anywhere in the world).

Collaborator

acityinohio commented Oct 6, 2017

As you may have seen in the other issue @jasondavies, but just in case you didn't: just a reminder that the submission deadline is October 6th! Please endeavor to have a final proposal submitted by then, as an attachment to this issue (and yes, it can be October 6th anywhere in the world).

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 6, 2017

To be honest, after further discussion with Sean, I'm now less convinced about building on top of parity-bitcoin. As nice as it seems to have a pre-existing implementation to build on, I think the test coverage could be much improved, and I'm not sure the abstractions are exactly how I would approach things. It also took a long time to sync with Bitcoin mainnet (much longer than Bitcoin Core), which indicates to me that it might need more work than I realised to bring it up to scratch.

Perhaps the scope of this proposal should be restricted to expand on my existing zcash-sprout-verifier (optimisations, etc.) and implement all Zcash-specific ancillary data structures (such as incremental merkle tree and nullifier set) in Rust. I envisage the following:

  • Implement optimisations for zcash-sprout-verifier. The current version uses a naive implementation for easy comparison with the basic algorithm, but various optimisations (e.g. pre-computation) are used in libsnark which can be re-implemented in Rust.
  • Implement BN254 in pairing to take advantage of the new API and performance improvements. This includes porting all tests over from bn.
  • Implement Zcash-specific (relating to zk-SNARKs) code in Rust. Primarily this would be the incremental merkle tree and nullifier set. In order to limit scope for this grant round, I would assume correctness of the Bitcoin-derived validation of blocks and transactions as done by the C++ client (e.g. UTXO references etc.), with validation of joinsplits and anchors done in Rust.

In terms of budget, I might suggest reducing the budget to $15k for this first phase (timeline 1-2 months). I think implementing optimisations will be about 20% of the budget, BN254 in pairing around 40%, and the remaining 40% for Rust versions of Zcash-specific parts of block/tx validation.

I have other ideas to move towards a full alternative node implementation that I could propose in the next grant round, but I need to think about them a bit more so I won't include them in this proposal.

Open source: "permissive" license (MIT or similar).

jasondavies commented Oct 6, 2017

To be honest, after further discussion with Sean, I'm now less convinced about building on top of parity-bitcoin. As nice as it seems to have a pre-existing implementation to build on, I think the test coverage could be much improved, and I'm not sure the abstractions are exactly how I would approach things. It also took a long time to sync with Bitcoin mainnet (much longer than Bitcoin Core), which indicates to me that it might need more work than I realised to bring it up to scratch.

Perhaps the scope of this proposal should be restricted to expand on my existing zcash-sprout-verifier (optimisations, etc.) and implement all Zcash-specific ancillary data structures (such as incremental merkle tree and nullifier set) in Rust. I envisage the following:

  • Implement optimisations for zcash-sprout-verifier. The current version uses a naive implementation for easy comparison with the basic algorithm, but various optimisations (e.g. pre-computation) are used in libsnark which can be re-implemented in Rust.
  • Implement BN254 in pairing to take advantage of the new API and performance improvements. This includes porting all tests over from bn.
  • Implement Zcash-specific (relating to zk-SNARKs) code in Rust. Primarily this would be the incremental merkle tree and nullifier set. In order to limit scope for this grant round, I would assume correctness of the Bitcoin-derived validation of blocks and transactions as done by the C++ client (e.g. UTXO references etc.), with validation of joinsplits and anchors done in Rust.

In terms of budget, I might suggest reducing the budget to $15k for this first phase (timeline 1-2 months). I think implementing optimisations will be about 20% of the budget, BN254 in pairing around 40%, and the remaining 40% for Rust versions of Zcash-specific parts of block/tx validation.

I have other ideas to move towards a full alternative node implementation that I could propose in the next grant round, but I need to think about them a bit more so I won't include them in this proposal.

Open source: "permissive" license (MIT or similar).

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies commented Oct 6, 2017

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 6, 2017

Collaborator

In general, I would prioritize functionality and robustness over optimization, at this point. (Unless optimization would make some qualitative difference, like crossing the threshold to being useful on phones, or some such.)

With this new approach, what does the Rust code plug into? Without parity-bitcoin integration, where does it even get its view of the blockchain and parsing of transactions?

Collaborator

tromer commented Oct 6, 2017

In general, I would prioritize functionality and robustness over optimization, at this point. (Unless optimization would make some qualitative difference, like crossing the threshold to being useful on phones, or some such.)

With this new approach, what does the Rust code plug into? Without parity-bitcoin integration, where does it even get its view of the blockchain and parsing of transactions?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 6, 2017

With this new approach, what does the Rust code plug into? Without parity-bitcoin integration, where does it even get its view of the blockchain and parsing of transactions?

I'm expecting that it would plug into the existing C++ Zcash client.

jasondavies commented Oct 6, 2017

With this new approach, what does the Rust code plug into? Without parity-bitcoin integration, where does it even get its view of the blockchain and parsing of transactions?

I'm expecting that it would plug into the existing C++ Zcash client.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 6, 2017

Collaborator

So basically you're proposing a Rust implementation of the functionality in https://github.com/zcash/zcash/tree/master/src/zcash (or the original https://github.com/Zerocash/libzerocash it's based on)?

Collaborator

tromer commented Oct 6, 2017

So basically you're proposing a Rust implementation of the functionality in https://github.com/zcash/zcash/tree/master/src/zcash (or the original https://github.com/Zerocash/libzerocash it's based on)?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 6, 2017

So basically you're proposing a Rust implementation of the functionality in https://github.com/zcash/zcash/tree/master/src/zcash (or the original https://github.com/Zerocash/libzerocash it's based on)?

Yes, but I'm limiting the scope to validation only, so I wouldn't need to implement a prover for this proposal. This work should make it easier to implement a prover, though.

jasondavies commented Oct 6, 2017

So basically you're proposing a Rust implementation of the functionality in https://github.com/zcash/zcash/tree/master/src/zcash (or the original https://github.com/Zerocash/libzerocash it's based on)?

Yes, but I'm limiting the scope to validation only, so I wouldn't need to implement a prover for this proposal. This work should make it easier to implement a prover, though.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 6, 2017

Collaborator

Ack.
How about adding the verifier side of payment disclosure (zcash/zcash#2036, zcash/zips#119, zcash/zcash#2159)?

Collaborator

tromer commented Oct 6, 2017

Ack.
How about adding the verifier side of payment disclosure (zcash/zcash#2036, zcash/zips#119, zcash/zcash#2159)?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 6, 2017

Good idea. Looks reasonably straightforward.

jasondavies commented Oct 6, 2017

Good idea. Looks reasonably straightforward.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 6, 2017

Collaborator

The new scope sounds good to me. I suggest including selective disclosure but acknowledging, as a risk factor, the dependency on the ZIP being finalized.
Also, don't forget to rename the proposal to reflect the new scope (maybe "Alternative implementation of JoinSplit and payment disclosure verification, written in Rust").

Collaborator

tromer commented Oct 6, 2017

The new scope sounds good to me. I suggest including selective disclosure but acknowledging, as a risk factor, the dependency on the ZIP being finalized.
Also, don't forget to rename the proposal to reflect the new scope (maybe "Alternative implementation of JoinSplit and payment disclosure verification, written in Rust").

@jasondavies jasondavies changed the title from Alternative fully-validating node written in Rust to JoinSplit & Payment Disclosure Verification in Rust Oct 6, 2017

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies commented Oct 6, 2017

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Oct 10, 2017

Hi, I haven't had time to read the new proposal, but I have a few concerns/questions:

Similarity to Zcashd PR 2578:

How is the new proposal different than zcash/zcash#2578 ? If I understand correctly, part of it, integration into zcashd, would overlap a lot, whereas other parts (changing pairing libraries, implementing optimizations, etc…) would be new.

I feel that fully integrating a non-optimized version would be more valuable as a first step, since the primary benefit of adding a new verifier, in my opinion, is extra assurance, not extra performance. In fact, if we have a fully integrated rust verifier in zcashd I would like to enable both verifiers by default for safety. In this case, I'd like to see the optimization work as a second step, and maybe there'd even be three versions of verifier eventually (libsnark-based, rust unoptimized, rust optimized).

Zcashd vs parity-bitcoin:

I'm not familiar with parity-bitcoin. However, I felt the fact that it's a ground-up alternative implementation of Bitcoin to be very valuable. It may have flaws such as poor test coverage, but so does Zcash! I'm not sure about the abstraction differences, though.

I trust @ebfull's engineering design instincts, though, and both goals of a redundant verifier in zcashd or a full-stack alternative implementation are valuable for Zcash. So given that, I would advocate for whichever project has a smaller scope.

nathan-at-least commented Oct 10, 2017

Hi, I haven't had time to read the new proposal, but I have a few concerns/questions:

Similarity to Zcashd PR 2578:

How is the new proposal different than zcash/zcash#2578 ? If I understand correctly, part of it, integration into zcashd, would overlap a lot, whereas other parts (changing pairing libraries, implementing optimizations, etc…) would be new.

I feel that fully integrating a non-optimized version would be more valuable as a first step, since the primary benefit of adding a new verifier, in my opinion, is extra assurance, not extra performance. In fact, if we have a fully integrated rust verifier in zcashd I would like to enable both verifiers by default for safety. In this case, I'd like to see the optimization work as a second step, and maybe there'd even be three versions of verifier eventually (libsnark-based, rust unoptimized, rust optimized).

Zcashd vs parity-bitcoin:

I'm not familiar with parity-bitcoin. However, I felt the fact that it's a ground-up alternative implementation of Bitcoin to be very valuable. It may have flaws such as poor test coverage, but so does Zcash! I'm not sure about the abstraction differences, though.

I trust @ebfull's engineering design instincts, though, and both goals of a redundant verifier in zcashd or a full-stack alternative implementation are valuable for Zcash. So given that, I would advocate for whichever project has a smaller scope.

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 10, 2017

Thanks for the feedback, Nathan!

You're right that the new proposal is to extend my existing work on the Rust proof verifier. Currently, my verifier checks the validity of zk-SNARK proofs, but it doesn't implement any other Zcash-specific parts of the protocol. The new proposal has two main parts: (a) implement more of the Zcash specification in Rust, (b) implement the optimisations that I detailed above.

I realise that in hindsight, perhaps I was too quick to drop parity-bitcoin from the proposal, and the new proposal focuses partly on optimisations, which aren't so much of a priority when the ultimate goal is to have an alternative pure Rust fully-validating node.

With the Foundation's permission (as the deadline has now passed!) I would consider revamping my final submission to reflect the original plan more closely. I'm not really sure there's a way to split the proposal into two phases, though, so I would simply ask for less funding.

jasondavies commented Oct 10, 2017

Thanks for the feedback, Nathan!

You're right that the new proposal is to extend my existing work on the Rust proof verifier. Currently, my verifier checks the validity of zk-SNARK proofs, but it doesn't implement any other Zcash-specific parts of the protocol. The new proposal has two main parts: (a) implement more of the Zcash specification in Rust, (b) implement the optimisations that I detailed above.

I realise that in hindsight, perhaps I was too quick to drop parity-bitcoin from the proposal, and the new proposal focuses partly on optimisations, which aren't so much of a priority when the ultimate goal is to have an alternative pure Rust fully-validating node.

With the Foundation's permission (as the deadline has now passed!) I would consider revamping my final submission to reflect the original plan more closely. I'm not really sure there's a way to split the proposal into two phases, though, so I would simply ask for less funding.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 10, 2017

Collaborator

Is it still expected that integration of the extended Rust the code into zcashd (as a full replacement to the "libzerocash" functionaity except proving, as discussed above) will be much easier than porting+integrating parity-bitcoin? If so, perhaps it still makes sense to start with the former, even if zcashd in this case serves merely as a test harness for the new code.

Collaborator

tromer commented Oct 10, 2017

Is it still expected that integration of the extended Rust the code into zcashd (as a full replacement to the "libzerocash" functionaity except proving, as discussed above) will be much easier than porting+integrating parity-bitcoin? If so, perhaps it still makes sense to start with the former, even if zcashd in this case serves merely as a test harness for the new code.

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 10, 2017

I think that’s broadly correct. I can start by reimplementing libzerocash in Rust, and it can be tested on zcashd via FFI. Later, depending on what is preferred, it can be plugged into parity-bitcoin or an alternative pure Rust P2P client. I think Nathan has persuaded me that porting the relevant parts of parity-bitcoin is still worthwhile though, so perhaps the Foundation/others can comment on whether to prioritise (a) optimising the zk-SNARK verifier; versus (b) porting the relevant parts of parity-bitcoin.

jasondavies commented Oct 10, 2017

I think that’s broadly correct. I can start by reimplementing libzerocash in Rust, and it can be tested on zcashd via FFI. Later, depending on what is preferred, it can be plugged into parity-bitcoin or an alternative pure Rust P2P client. I think Nathan has persuaded me that porting the relevant parts of parity-bitcoin is still worthwhile though, so perhaps the Foundation/others can comment on whether to prioritise (a) optimising the zk-SNARK verifier; versus (b) porting the relevant parts of parity-bitcoin.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 11, 2017

Collaborator

My opinion is that porting parity-bitcoin is far more important than optimizing the verifier.
Let's put it this way. The harshest exercise of the verifier is fetching/reindexing the whole blockchain. How long does that take now compared to total number of JoinSplits x time(zcash-sprout-verifier::verify)?

Collaborator

tromer commented Oct 11, 2017

My opinion is that porting parity-bitcoin is far more important than optimizing the verifier.
Let's put it this way. The harshest exercise of the verifier is fetching/reindexing the whole blockchain. How long does that take now compared to total number of JoinSplits x time(zcash-sprout-verifier::verify)?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 11, 2017

My opinion is that porting parity-bitcoin is far more important than optimizing the verifier. The harshest exercise of the verifier is fetching/reindexing the whole blockchain. How long does that take now compared to total number of JoinSplits x time(zcash-sprout-verifier::verify)?

I agree, from the point of view of having a completely separate validating node implementation being more important. If you look at the performance numbers though, proof verification is still a large proportion of the total validation time compared with verifying transaction signatures, linking UTXOs and parsing the block data.

At the time of writing, 291,413 JoinSplits have been executed on Zcash mainnet. Single-threaded verification of these proofs using libsnark would take at ~3.25h at 40ms per proof verification. That's a best-case number taken from https://speed.z.cash; note that on slower CPUs it can take much longer than this (I measured 80ms+ on a Xeon D-1520 2.4GHz; i.e. ~6.5h in total). Of course, with multiple cores it should be trivial to parallelise, but you can see that optimisation is still quite important, especially as shielded transactions become more widely used. (Of course, it would also take quite some time to fetch the whole blockchain of around 7GB depending on connection speed.) The naive zcash-sprout-verifier implementation currently takes 1.5x the time taken by libsnark.

jasondavies commented Oct 11, 2017

My opinion is that porting parity-bitcoin is far more important than optimizing the verifier. The harshest exercise of the verifier is fetching/reindexing the whole blockchain. How long does that take now compared to total number of JoinSplits x time(zcash-sprout-verifier::verify)?

I agree, from the point of view of having a completely separate validating node implementation being more important. If you look at the performance numbers though, proof verification is still a large proportion of the total validation time compared with verifying transaction signatures, linking UTXOs and parsing the block data.

At the time of writing, 291,413 JoinSplits have been executed on Zcash mainnet. Single-threaded verification of these proofs using libsnark would take at ~3.25h at 40ms per proof verification. That's a best-case number taken from https://speed.z.cash; note that on slower CPUs it can take much longer than this (I measured 80ms+ on a Xeon D-1520 2.4GHz; i.e. ~6.5h in total). Of course, with multiple cores it should be trivial to parallelise, but you can see that optimisation is still quite important, especially as shielded transactions become more widely used. (Of course, it would also take quite some time to fetch the whole blockchain of around 7GB depending on connection speed.) The naive zcash-sprout-verifier implementation currently takes 1.5x the time taken by libsnark.

@nathan-at-least

This comment has been minimized.

Show comment
Hide comment
@nathan-at-least

nathan-at-least Oct 12, 2017

I read the proposal pdf and this thread.

I advocate deferring the optimization goal, either to the end of the project as a separate distinct source code change, or just to exclude it.

My reasoning is as follows:

  • The primary benefit of a second verifier implementation is improved safey and assurance, so simpler, easier to understand code is preferable.
  • If the performance optimizations themselves introduce a verification flaw, and we re-implement the same optimizations in both verifiers, we won't detect that kind of flaw on Zcash.
  • I suspect that verifier speed is only a bottleneck when doing a -reindex operation and for a normal new node to bootstrap the total wall-clock-time bottleneck is downloading the blockchain from the network.

My desired roadmap for incorporating this work into Zcash is to add an opt-in redundant verifier. This assumes the last point is an acceptable performance cost.

Note that even adding a redundant verifier is risky in terms of consensus because old nodes which don't have that will accept hypothetical transactions that pass the old verifier and fail on the new verifier. We may leave the redundant verifier mode as an experimental option for a long time and just use it for safety-monitoring nodes rather than promote end-users to use them because of this.

Finally, I don't have specific understanding of the optimizations, so my thoughts above may not apply. If that's the case I'd love to learn why.

nathan-at-least commented Oct 12, 2017

I read the proposal pdf and this thread.

I advocate deferring the optimization goal, either to the end of the project as a separate distinct source code change, or just to exclude it.

My reasoning is as follows:

  • The primary benefit of a second verifier implementation is improved safey and assurance, so simpler, easier to understand code is preferable.
  • If the performance optimizations themselves introduce a verification flaw, and we re-implement the same optimizations in both verifiers, we won't detect that kind of flaw on Zcash.
  • I suspect that verifier speed is only a bottleneck when doing a -reindex operation and for a normal new node to bootstrap the total wall-clock-time bottleneck is downloading the blockchain from the network.

My desired roadmap for incorporating this work into Zcash is to add an opt-in redundant verifier. This assumes the last point is an acceptable performance cost.

Note that even adding a redundant verifier is risky in terms of consensus because old nodes which don't have that will accept hypothetical transactions that pass the old verifier and fail on the new verifier. We may leave the redundant verifier mode as an experimental option for a long time and just use it for safety-monitoring nodes rather than promote end-users to use them because of this.

Finally, I don't have specific understanding of the optimizations, so my thoughts above may not apply. If that's the case I'd love to learn why.

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 17, 2017

Hi Nathan, thanks very much for the feedback. As I mentioned above, I would happy to revise my submission to reflect the original proposal more closely (based on parity-bitcoin), though as the deadline for final submission has passed, I'll wait for the Foundation to indicate whether they would like me to do this or not. The budget would stay the same, but I would extend parity-bitcoin for a minimal validating-only node rather than focus on optimisations initially.

jasondavies commented Oct 17, 2017

Hi Nathan, thanks very much for the feedback. As I mentioned above, I would happy to revise my submission to reflect the original proposal more closely (based on parity-bitcoin), though as the deadline for final submission has passed, I'll wait for the Foundation to indicate whether they would like me to do this or not. The budget would stay the same, but I would extend parity-bitcoin for a minimal validating-only node rather than focus on optimisations initially.

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 17, 2017

Collaborator

@jasondavies Under the circumstances, I suggest you submit the updated/reverted proposal (as an additional PDF file) and the review committee will discuss this. Please do so ASAP, since the committee meets in a few days.

Collaborator

tromer commented Oct 17, 2017

@jasondavies Under the circumstances, I suggest you submit the updated/reverted proposal (as an additional PDF file) and the review committee will discuss this. Please do so ASAP, since the committee meets in a few days.

@jasondavies jasondavies changed the title from JoinSplit & Payment Disclosure Verification in Rust to Alternative Fully-Verifying Node in Rust Oct 17, 2017

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies commented Oct 17, 2017

Thanks @tromer!

Here it is: 32-1.pdf

@tromer

This comment has been minimized.

Show comment
Hide comment
@tromer

tromer Oct 20, 2017

Collaborator

@jasondavies, to be explicit,@jasondavies, the latest revision does not include payment disclosure, right?

Collaborator

tromer commented Oct 20, 2017

@jasondavies, to be explicit,@jasondavies, the latest revision does not include payment disclosure, right?

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 20, 2017

the latest revision does not include payment disclosure, right?

That's correct. It would be relatively simple to add afterwards though.

jasondavies commented Oct 20, 2017

the latest revision does not include payment disclosure, right?

That's correct. It would be relatively simple to add afterwards though.

@ebfull

This comment has been minimized.

Show comment
Hide comment
@ebfull

ebfull Oct 27, 2017

Personal opinions follow:

I just remembered that parity-bitcoin is GPLv3 licensed. I like their project and wish them luck, but I personally will never contribute to a GPL licensed project. 😸

I am okay with the grant because we'll learn a lot from an alternative implementation regardless of its license. I don't like that there's almost no testing surrounding its networking infrastructure, but maybe that's okay as a starting point. I still think we should do something more directly applicable to Zcash in its current form -- like reimplementing libzcash in Rust.

ebfull commented Oct 27, 2017

Personal opinions follow:

I just remembered that parity-bitcoin is GPLv3 licensed. I like their project and wish them luck, but I personally will never contribute to a GPL licensed project. 😸

I am okay with the grant because we'll learn a lot from an alternative implementation regardless of its license. I don't like that there's almost no testing surrounding its networking infrastructure, but maybe that's okay as a starting point. I still think we should do something more directly applicable to Zcash in its current form -- like reimplementing libzcash in Rust.

@jasondavies

This comment has been minimized.

Show comment
Hide comment
@jasondavies

jasondavies Oct 29, 2017

The GPLv3 license is indeed annoying in this case as it reduces potential for reuse in the Zcash ecosystem. If I understand correctly, as the original author of the new code, I would be free to do the following:

  1. Implement the parity-bitcoin + Zcash project as per my final proposal (the combination would have to be released under GPLv3). We would end up with a usable fully-validating node in Rust for tinkering with.
  2. Reuse non-derivative Zcash-specific code e.g. building on a new base p2p layer, and re-release under any other license that I choose. Effectively, the license is annoying but if we anticipate replacing parity-bitcoin at some point anyway, it shouldn't affect my ability to reuse any non-derivative work in terms of licensing. (I could even start by implementing some parts such as an equivalent to libzcash as a separate library released under a less restrictive license if it makes sense to do so.)

jasondavies commented Oct 29, 2017

The GPLv3 license is indeed annoying in this case as it reduces potential for reuse in the Zcash ecosystem. If I understand correctly, as the original author of the new code, I would be free to do the following:

  1. Implement the parity-bitcoin + Zcash project as per my final proposal (the combination would have to be released under GPLv3). We would end up with a usable fully-validating node in Rust for tinkering with.
  2. Reuse non-derivative Zcash-specific code e.g. building on a new base p2p layer, and re-release under any other license that I choose. Effectively, the license is annoying but if we anticipate replacing parity-bitcoin at some point anyway, it shouldn't affect my ability to reuse any non-derivative work in terms of licensing. (I could even start by implementing some parts such as an equivalent to libzcash as a separate library released under a less restrictive license if it makes sense to do so.)
@ebfull

This comment has been minimized.

Show comment
Hide comment
@ebfull

ebfull Oct 30, 2017

Yup. I would write as much as you can in MIT/Apache 2.0, so we aren't locked into parity-bitcoin's license.

ebfull commented Oct 30, 2017

Yup. I would write as much as you can in MIT/Apache 2.0, so we aren't locked into parity-bitcoin's license.

@acityinohio

This comment has been minimized.

Show comment
Hide comment
@acityinohio

acityinohio Nov 21, 2017

Collaborator

@jasondavies : I'm thrilled to inform you that the Grant Review committee—and the Zcash Foundation board—has tentatively approved your proposal! While the recommendations are already posted, we are planning to make a more public post tomorrow morning (November 21st) Pacific Standard Time.

Next steps: please email me josh [at] z.cash.foundation with an email address suitable as a point of contact. Due to our newfound 501(c)3 status there are additional reporting and compliance burdens that may delay or change disbursements, but we are working through them as fast as we can.

Just in case you didn't see it, please find the committee recommendation for your project below, and congratulations again (twice over!)

Proposes to implement a Zcash node with full verification of all transaction types (though not, yet, the wallet and proving functionality). The starting point is the Parity-Bitcoin reimplementation of a Bitcoin full node; the proposer will port it to Zcash and add the extra functionality needed to verify Zcash transactions - in particular, verification of JoinSplits in shielded transactions, also implemented in Rust.

This will constitute an independent implementation of most of the zcashd node functionality, by a party outside the Zcash Company. Such alternative implementation are crucial for security and decentralization, which are core values for the Zcash Foundation. Moreover, the Rust language seems more suitable than zcashd's C++ for some prospective uses, such as in-browser wallets.

The proposer has been an active contributor to the Zcash community and created a stand-alone zk-SNARK verifier in Rust that can validate Zcash JoinSplit proofs; he thus appears capable of implementing this proposal.

Collaborator

acityinohio commented Nov 21, 2017

@jasondavies : I'm thrilled to inform you that the Grant Review committee—and the Zcash Foundation board—has tentatively approved your proposal! While the recommendations are already posted, we are planning to make a more public post tomorrow morning (November 21st) Pacific Standard Time.

Next steps: please email me josh [at] z.cash.foundation with an email address suitable as a point of contact. Due to our newfound 501(c)3 status there are additional reporting and compliance burdens that may delay or change disbursements, but we are working through them as fast as we can.

Just in case you didn't see it, please find the committee recommendation for your project below, and congratulations again (twice over!)

Proposes to implement a Zcash node with full verification of all transaction types (though not, yet, the wallet and proving functionality). The starting point is the Parity-Bitcoin reimplementation of a Bitcoin full node; the proposer will port it to Zcash and add the extra functionality needed to verify Zcash transactions - in particular, verification of JoinSplits in shielded transactions, also implemented in Rust.

This will constitute an independent implementation of most of the zcashd node functionality, by a party outside the Zcash Company. Such alternative implementation are crucial for security and decentralization, which are core values for the Zcash Foundation. Moreover, the Rust language seems more suitable than zcashd's C++ for some prospective uses, such as in-browser wallets.

The proposer has been an active contributor to the Zcash community and created a stand-alone zk-SNARK verifier in Rust that can validate Zcash JoinSplit proofs; he thus appears capable of implementing this proposal.

@acityinohio acityinohio added the awarded label Nov 21, 2017

@zookozcash

This comment has been minimized.

Show comment
Hide comment
@zookozcash

zookozcash Nov 21, 2017

zookozcash commented Nov 21, 2017

@sonyamann

This comment has been minimized.

Show comment
Hide comment
@sonyamann

sonyamann Jun 20, 2018

Heya @jasondavies! I'm pinging all of the 2017 grant recipients for updates on their projects. Can you either write a paragraph or two here, or alternately email me? sonya@z.cash.foundation

Thank you!

sonyamann commented Jun 20, 2018

Heya @jasondavies! I'm pinging all of the 2017 grant recipients for updates on their projects. Can you either write a paragraph or two here, or alternately email me? sonya@z.cash.foundation

Thank you!

@5chdn

This comment has been minimized.

Show comment
Hide comment
@5chdn

5chdn Jun 21, 2018

Please, also keep parity in the loop! ❤️ CC: afri@parity.io ❤️

5chdn commented Jun 21, 2018

Please, also keep parity in the loop! ❤️ CC: afri@parity.io ❤️

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