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

Support Overwinter and Sapling in Riemann #19

Open
prestwich opened this Issue May 11, 2018 · 34 comments

Comments

Projects
None yet
6 participants
@prestwich

prestwich commented May 11, 2018

Motivation and overview

Riemann is a library for transaction constructions on Bitcoin-based blockchains. It accepts human-readable inputs and serializes transactions from them. Currently, we support with over 20 live networks as well as dozens of testnets. All the tools already support Sprout transactions to and from t-addresses. Shielded tx support is not currently planned.

Riemann leverages the shared history of all Bitcoin-based chains. The vast majority of serialization logic is handled by a shared core. The Overwinter and Sapling network upgrades will cause the transaction serialization format to diverge significantly from standard Bitcoin transactions. Transaction expiry and other will prevent us from using the shared core. New data structures will need to be created to reflect the new Overwinter serialization formats.

Technical approach

We'll create and implement new objects that handle serialization, sighash, and other specific features for Overwinter and Sapling.

An example of the approach can be found in the Decred-specific data structures here.

Once those are completed, we work them into the tx_builder logic and other simplified interfaces.

Team background and qualifications

Team:
Summa
James Prestwich, founder @ Summa former COO @ Storj
Rachel Rybarcyzk, blockchain engineer @ Summa

Qualification:
We wrote Riemann. It works in production already.

Evaluation plan

We are successful when we have full test coverage and can reliably create consensus-correct transactions on Overwinter and Sapling mainnets using Riemann. We will deliver a sample application that does so.

Security considerations

We do not handle private keys, and we do not touch shielded transactions. Every piece of data that Riemann processes is intended to be broadcast on the network. Riemann is a developer tool, not an application. It's difficult to see privacy or security implications in our work.

Schedule

  • We hope to support Overwinter before its launch.
  • Timing of support for Sapling is contingent on finalization of its spec.
  • Based on experience implementing Decred, we expect it to take about 40 hours per new transaction format.

Budget and justification

We expect to spend about 80 hours total. My hourly rate is $300. Rachel's is $200.

40 hours * $200 + 40 hours * $300 = $20,000

Email address(es) for direct contact

james@summa.one

@tromer

This comment has been minimized.

Collaborator

tromer commented May 25, 2018

@prestwich, what's your rationale for excluding shielded transactions? Are there circumstances under which they can be supported?

Note that the plan (on the scale of years) is to deprecate and ultimately eliminate transparent transactions, in favor of a fully shielded blockchain + selective disclosure features.

@tromer tromer added the misc label May 25, 2018

@prestwich

This comment has been minimized.

prestwich commented May 25, 2018

@tromer I have a branch started for encoding Zcash's version 2 transactions. I haven't prioritized it because I don't know of any tools for generating JoinSplit descriptors (besides zcashd). Which is to say, I can't figure out to whom it would be useful.

Riemann is purely for syntactic manipulation. It doesn't handle keys or secrets at all. Future companion tools will (once I get familiar with the python bindings for libsecp256k1). My intention is to create a companion tool for creating JoinSplit descriptors via pulling out and writing Python bindings for parts of the zcashd codebase. Unfortunately, this is probably about as far off as a version of Zcash without transparent transactions.

@tromer

This comment has been minimized.

Collaborator

tromer commented May 25, 2018

@jasondavies, any thoughts on the above in light of your work on the Alternative Fully-Verifying Node in Rust?

@tromer

This comment has been minimized.

Collaborator

tromer commented May 25, 2018

Can you say more about typical use cases and prominent users of Riemann?

This will also inform the above discussion on whom shielded support would be useful for.

@prestwich

This comment has been minimized.

prestwich commented May 25, 2018

I'd like to support version 2 formatting. My main question is "how will people generate JoinSplits?" Until there's a reliable way to do that, I can't really support private transactions. In the next month or two I'll probably implement version 2 tx parsing that blackboxes JoinSplits, so that we can inspect those transactions easy.

Typical usecases:

  • Application-specific transactions (HTLCs, custom msigs, etc.)
  • Multi-asset applications
  • Quick prototyping of complex transactions

Significant users:

  • Summa
  • An upcoming unified wallet for 20 assets
  • An upcoming cross-chain swap tool
@tromer

This comment has been minimized.

Collaborator

tromer commented May 30, 2018

Point taken about generating shielded transactions.

However, how about payment disclosures?

Also, how about v4 (Sapling) transactions, as introduced in zcashd v1.1.1?

Note that concerns have been raised in the review committee about about the budget. While your hourly rate is not unheard of in per-hour contracted work, most proposers quoted much more modest rates for their development work.

@prestwich

This comment has been minimized.

prestwich commented May 31, 2018

Maybe it makes sense to make scope a bit more explicit. We'll support the encoding formats in sections 7.1-7.4 of the current version of the Sapling spec. So transaction versions 2, 3, and 4, as well encoding/decoding, but not validating, JoinSplit, Spend, and Output descriptions.

We can support the payment disclosure encoding described here. We'll probably have a few questions. And like JoinSplits, I don't know of a good tool for creating or verifying the proofs.

For some concrete examples, Riemann will be able to:

  • Parse any transaction on Sprout, Overwinter, and Sapling main or test nets
  • Easily extract arbitrary information. E.g. the zkproof from the third Spend description in a version 4 transaction
  • Verify consensus correctness where possible without access to the chain or zk-proof tools
  • Build any version transaction from human- or machine-readable parameters, provided we already have the necessary JoinSplits, Spends, Output descriptions, etc.
  • Parse and interact with payment disclosures, but not build or verify the relevant proofs.

Re: cost. We'd be turning down other work and taking on long-term maintenance without expectation of future pay. We understand if budget is a limiting factor.

@tromer

This comment has been minimized.

Collaborator

tromer commented May 31, 2018

Proof creation (of JoinSplit, Spend or Output) creation doesn't, currently, have any implementation short of full-blown zcashd, so I agree this would be out of scope for now.

What do you mean by "Verify consensus correctness where possible without access to the chain or zk-proof tools"? Skipping all consensus rules relating to the blockchain state (txo sets, doublespend-checking, difficulty adjustment, etc.)? Skipping almost any consensus rule would permit devastating attacks, so what's the use of checking only some of them?

Proof verification is much easier, and does have a relatively lightweight implementation (see @jasondavies's Alternative Fully-Verifying Node in Rust. But generally, checking proofs may not really make sense if consensus rules aren't checked (see above) but just trusted to have already been checked.

@jasondavies

This comment has been minimized.

jasondavies commented May 31, 2018

Hi @tromer, I think there is some overlap here with my Rust implementation, since I'm parsing v2/v3 transactions (and v4 will be trivial to add), and validating them. The difference is of course that I'm fully validating (both unshielded and shielded) against downloaded blocks, with all consensus rules.

I'm also including support for payment disclosure stuff separately. Any of these aspects in my Rust code: parsing/serialising transactions, payment disclosures, etc. can be compiled for a WebAssembly target making it easily reusable in Node.js or browser environments as standalone parts that do not require the P2P layer. I suppose at a future date, Riemann could use Python bindings to Rust code (in particular anything zkSNARK-related, both verifying and proving) if that ends up being an easier way to reuse these aspects.

@tromer

This comment has been minimized.

Collaborator

tromer commented May 31, 2018

@jasondavies, to what extend does your code (or easy refactoring thereof) provide a Rust implementation of the same functionality as Riemann, as exemplified above?

@prestwich, see @jasondavies's comment above. What's your perspective on reusing/interfacing with his code, and on what additional functionality and use cases Riemann integration enable beyond the capabilities of @jasondavies's code (or easy variants thereof)?

@jasondavies

This comment has been minimized.

jasondavies commented May 31, 2018

@tromer, it provides the same base functionality as far as I can tell, in terms of serialising/deserialising transactions themselves. Even if there was no Rust implementation, I suppose you could ask the same question: whether it would be easier/preferable to write Python bindings for code extracted from the C++ implementation, instead of replicating the implementation in Python. I do think it will be easier to do this with my Rust code as this is one of the intended use cases.

@prestwich

This comment has been minimized.

prestwich commented May 31, 2018

Skipping almost any consensus rule would permit devastating attacks, so what's the use of checking only some of them?

But generally, checking proofs may not really make sense if consensus rules aren't checked (see above) but just trusted to have already been checked.

Skipping consensus rules permits 0 attacks. One of the great features of Bitcoin transactions is that their internal, syntactic validity is separate from their consensus validity. Syntactic validity is a property of the transaction that we should certainly check. Syntactic validity is more important for app developers and harder to achieve than consensus validity. Riemann is a tool for syntactic construction, so we check syntactic rules.

Two concrete examples:

  • OP_CLTV checks the transaction's nLocktime field, instead of checking the block's height or timestamp.
  • Lightning relies on checking the syntactic correctness of pre-signed transactions, regardless of their consensus validity.

What's your perspective on reusing/interfacing with his code, and on what additional functionality and use cases Riemann integration enable beyond the capabilities of @jasondavies's code (or easy variants thereof)?

Proof verification is much easier, and does have a relatively lightweight implementation (see @jasondavies's Alternative Fully-Verifying Node in Rust.

Riemann's goal is to create a consistent development experience for dozens of chains. Using C++ or Rust bindings for specific chains makes that much more difficult and introduces outside dependencies that most developers won't need. What Riemann can do that @jasondavies can't is give Sapling users access to apps built with BTC, LTC, or Sprout in mind.

As discussed above, checking proofs is valuable even if the consensus rules against double-spending, etc. aren't checked. I would love to implement Python bindings for checking proofs and figure out where they best fit in Riemann. @jasondavies is zcash-sprout-verifier the right repo for it? I'm guessing there will be a sapling version at some point?

@jasondavies

This comment has been minimized.

jasondavies commented May 31, 2018

Yes, that's the proof-of-concept Sprout verifier that I implemented last year, with FFI interface for use with zcashd. My current work on a fully-validating node in Rust is not public yet, but that will hopefully be easier to use, and will also get support for Sapling in the future.

@prestwich

This comment has been minimized.

prestwich commented May 31, 2018

Cool thanks. Time to brush up on Rust bindings 👍

@tromer

This comment has been minimized.

Collaborator

tromer commented Jun 1, 2018

The Zcash Foundation Grant Review committee has reviewed your pre-proposal, including the above discussion, to evaluate its potential and competitiveness relative to other proposals. Every pre-proposal was evaluated by at least 3 (and typically more than 4) committee members .

The committee's opinion is that your pre-proposal is a promising candidate funding in this round, and the committee therefore invites you to submit a full proposal.
Please submit a full proposal by June 15th, following the detailed structure described in the Call for Proposals. We encourage you to submit a draft as early as possible, to allow for community feedback.

@tromer tromer added the invited-full label Jun 1, 2018

@prestwich

This comment has been minimized.

prestwich commented Jun 5, 2018

Great, thank you. We'll try to get a full proposal in this week.

@prestwich

This comment has been minimized.

prestwich commented Jun 9, 2018

Proposal is attached. Compared to the version above, we have expanded scope to include Python bindings for Sprout and Sapling verifiers, and clarified deliverables. Budget is unchanged.

We do intend to support Overwinter before the June 25th launch, and understand that grant decisions will be made after that date. The committee can track implementation progress here. If there are pre-constructed examples of Overwinter or Sapling transactions, I'd appreciate a link so that we can include them in our tests.

Riemann Grant Proposal.pdf

@prestwich

This comment has been minimized.

prestwich commented Jun 11, 2018

Can anyone point me to documentation on the libsnark format for encoding the verification key? I grabbed sprout-verifying.key but don't know how to decode it. The Rust lib ships this off to zcashd, which ships it to libsnark afaict

@tromer

This comment has been minimized.

Collaborator

tromer commented Jun 15, 2018

@prestwich, unfortunately I don't think we've ever explicitly documented the libsnark verification key (or proving key, or proof) serialization formats. Though there is the independent re-implementation by @ebfull + @jasondavies, so the format is indeed deducible from the code as intended. (pinging @madars too)

But actually why do you need it? Aren't you opaquely delegating the handling of the proof (including parsing the format) to external libraries?

@prestwich

This comment has been minimized.

prestwich commented Jun 15, 2018

I would strongly prefer not to ship libsnark or zcashd. I see the whole goal as making a tool with as much independent code as possible.

The Rust verifier expects to be passed the verification key's group elements, the primary input, and the proof group elements. Zcash's proof serialization format is documented in the protocol spec. I have working code to parse the proof format and generate the primary input by parsing the joinsplit.

I had a friend look at the bn crate with me and we reached out to @ebfull about it in #bn on the zcash community chat. We can likely figure out how to decode them from the code. The bytes look like a standard compressed curve point format, so this is probably solvable with some legwork.

That just leaves the verifying key. I can learn libsnark, but it'll take a disproportionate amount of time compared to just asking someone :)

@jasondavies

This comment has been minimized.

jasondavies commented Jun 15, 2018

When I wrote the verifier code, I had the same issue with figuring out how to decode the libsnark-encoded verifying key, so in the end it was simpler to get zcashd to pass it to me!

I think it would be easier to dump out the key in a more convenient encoding and use that instead. It can simply be hard-coded as it is quite short. The transformation (libsnark-encoded verifying key → friendly encoding) should also be simple for anyone to independently check.

I am doing this anyway for my Rust node so I will post the code and key for you when it's ready (shouldn't take long).

@prestwich

This comment has been minimized.

prestwich commented Jun 15, 2018

@jasondavies that sounds perfect. Hard-coded key seems ideal for this.

While you're dumping things, would you mind also dumping a couple primary inputs so that I can use them for tests? I've been using this tx, so the primary input from its JoinSplit would be perfect.

@tromer

This comment has been minimized.

Collaborator

tromer commented Jun 26, 2018

@prestwich, are there any released open-source projects using Riemann?

@prestwich

This comment has been minimized.

prestwich commented Jun 26, 2018

It's a young tool, so I'm not aware of anything significant released yet. Summa will be releasing a lot of code using it in the near future. I'm also starting to give development workshops using it.

@tromer

This comment has been minimized.

Collaborator

tromer commented Jun 26, 2018

@prestwich, what applications that use Riemann, and will thus support Zcash with these extensions, can you commit to releasing within the grant's 6-month time scale? Will they be open source?

@prestwich

This comment has been minimized.

prestwich commented Jul 8, 2018

I don't think that's a reasonable request. We've already expanded scope and talked in-person about lowering budget. At some point the committee needs to weigh the proposal on its own merits.

@tromer

This comment has been minimized.

Collaborator

tromer commented Jul 16, 2018

Thanks @prestwich. We understand your position. But note that committee has deliberated on this at length, and finds it difficult to support development of a software library without clarity on when and whether it will be used by applications (preferably open-source ones).

@prestwich

This comment has been minimized.

prestwich commented Jul 22, 2018

I'm happy to demo the app we've built with it. I expect the code to be public in mid-August, after it's had some usage in the wild

@tromer

This comment has been minimized.

Collaborator

tromer commented Sep 25, 2018

@prestwich, we are about to finalize the grant funding recommendations. Are there any updates in your status or plans that we should be aware of?

@prestwich

This comment has been minimized.

prestwich commented Oct 28, 2018

You can track Sapling support progress here. The branch should be usable for serialization and deserialization as-is, but needs more tests and a zip243 implementation. Will be getting those in over the next day or two

@prestwich

This comment has been minimized.

prestwich commented Oct 30, 2018

Just merged the PR. I've tested with a few mainnet txns, as well as a few of bitgo and zcashco's test vectors. Sapling specific code is at about 95% test coverage. There's a few branches in my zip243 implementation that I haven't found good vectors for yet

We are still interested in making bindings for a proof verifier. Main blocker for sprout was figuring out how to deserialize the libsnark-formatted keyfiles. I assume we'll run into similar problems with the new sapling proofs

@sonyamann

This comment has been minimized.

Collaborator

sonyamann commented Nov 6, 2018

I'm thrilled to inform you that the Grant Review Committee and the Zcash Foundation Board of Directors have approved your proposal, pending a final compliance review. Congratulations, and thank you for the excellent submission!

Next steps: Please email josh@z.cash.foundation from an email address that will be a suitable point of contact going forward. We plan to proceed with disbursements following a final confirmation that your grant is within the strictures of our 501(c)(3) status, and that our payment to you will comply with the relevant United States regulations.

We also wish to remind you of the requirement for monthly progress updates to the Foundation’s general mailing list, as noted in the call for proposals.

Before the end of this week, the Zcash Foundation plans to publish a blog post announcing grant winners to the public at large, including a lightly edited version of the Grant Review Committee’s comments on your project. The verbatim original text of the comments can be found below.

Congratulations again!

Grant Review Committee comments:

James Prestwich and Rachel Rybarcyzk from Summa company are working on a library called Riemann. The library is for constructing transactions on Bitcoin-based blockchains. The team is asking for funding in order to support Overwinter and Sapling.

Developing such library infrastructure is important for facilitating third-party applications. Moreover, this library builds on the third-party Rust reimplementation of parts of the Zcash protocol (ZcashFoundation/GrantProposals-2017Q4#32), and bolstering such independent reimplementations is an important component of the Foundation's decentralization and privacy values.

We thus recommend funding this proposal. Budget was reduced to $10k with the proposer's consent.

@mms710

This comment has been minimized.

mms710 commented Nov 19, 2018

@prestwich i! I'd love to help provide any engineering support you might need from the engineers at Zcash Company. Would you be interested in getting a more regular line of communication set up between you and Zcash Company engineers so you can ask questions or get help? If so, would you be okay using a Rocketchat channel or do you have another preferred method of communication?

@NikVolf

This comment has been minimized.

NikVolf commented Nov 26, 2018

Can anyone point me to documentation on the libsnark format for encoding the verification key? I grabbed sprout-verifying.key but don't know how to decode it. The Rust lib ships this off to zcashd, which ships it to libsnark afaict

have those keys file format ever progressed to a documented state?

Or maybe group elements of those keys at least stated somewhere in docs/tests?

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