Implement Crypto Primitives and Confidential Transfer Pallet

Hi there.
We are Kogarashi Network substrate builder program number 5027471872`.
We would like to discuss crypto primitive implementation.

■Background
I think we should implement crypto primitives which are compatible with parity codec and no_std.
Privacy and scaling are blockchain missing pieces and needed to be solved.
Both can be solved by zero-knowledge proof and homomorphic encryption.
However, we don’t have crypto primitives compatible with parity codec and no_std as the following issues say.

We have been working on Web3 Foundation grants related to zero-knowledge proof four times.
Most of our development workload is occupied with making crypto primitives compatible with pallet format.
We already know both Substrate and crypto so we would like to solve this issue.

■Proposal
We experimentally implemented a confidential transfer pallet as follows.

We also implemented crypto primitives as in Jubjub, bls12 381, Kzg, and ElGamal, pairing.
https://github.com/KogarashiNetwork/Kogarashi/tree/master/primitive#primitive

These libraries are original and compatible with Parity Scale codec and no_std.
We would like to export our libraries for community developers.
Our proposal is the following.
https://docs.google.com/document/d/17YSrbILm--lu3lQL8JmJ6Rk-_iu723-_/edit?usp=sharing&ouid=116197126832835062977&rtpof=true&sd=true

We are going refactor and optimize crypto primitives.
It would be nice if we can receive feedback and integrate or delivery our libraries for community developers.
We work on the implementation of the rejubjub signature.

If you give us any feedback, we would be happy to reflect it on our libraries.

I would appreciate it if you give comments and feedback for our proposal.
Please ping me if you have any questions.
Thank you!

I think parity has a partial fork of zcash sapling to use arkworks somewhere, well arkworks itself is already a fork of zcash sapling. I’ve no idea about the code quality. It’ll also be possible to directly fork zcash curve repos to use the hostcalls being added of course. Also some others have works on similar things.

There is a lot of user side overhead in doing confidential tx so how close one sticks to an existing open source ecosystem matters here. I do not however know those ecosystems well enough to comment on what is best.

2 Likes

Hi @burdges
Thank you for the reply :grinning:

To summarize the story, I think there are mainly three reasons we should implement by ourselves.

  1. Compatibility with Substrate runtime
  2. Performance optimization
  3. Catch up latest cryptography

Compatibility with Substrate runtime

I think parity has a partial fork of zcash sapling to use arkworks somewhere

Exactly, I think this is that.

We can use ark-works functionalities through hostcalls.
However, we can’t use ark-works crypto primitives on the runtime pallet because it’s not compatible with parity scale codec and no_std.

There are two reasons why we would like to use crypto primitives on the runtime pallet.
Firstly, we would like to change the runtime storage structure as cryptographic-friendly.
When we implement a confidential transfer pallet, we need to change the balance pallet.
At that moment, we need to use crypto primitives on the runtime pallet as follows.

Secondly, when we implement more complex privacy and scaling functionalities, hostcalls wouldn’t be a best practice.
If we can use crypto primitives on the runtime pallet, the implementation would be far simpler.

Performance optimization

I’ve no idea about the code quality

I think our crypto primitives are the fastest.
I have been working on the optimization of zero knowledge prover time.
I made Zcash halo2 MSM and fft two times faster (MSM and fft are occupied 85% of the prover time).
Zcash halo2 uses my fft algorithm.
I made it even faster.

ark-works uses previous Zcash halo2 algorithms.

NAF optimization is our original optimization.
Comparing with zkcrypto/jubjub representation, Naf representation can reduce n/6 hamming weight where n is bits number of field and also clean the zero here.
Eventually, this reduces n/6 times elliptic curve addition and the sum of 1/2,1/4… geometric series times curve doubling.
I benched it and ensured that it worked

I also think that code duplication and hard to replace with the new algorithm are also bad for optimization as the following issue mentioned.

To avoid these problems, I separated arithmetic and interface implementation.
It’s far easier to replace with the new algorithm and apply for all libraries.

Catch up latest cryptography
zero-knowledge proof can use for privacy and scaling.
However, we haven’t known the best option.
If we implement crypto primitives, we would easily implement Nova, hyper plonk, or whatever we want.
Depending on external libraries may lack flexibility.

There is a lot of user side overhead in doing confidential tx

Exactly.
We benched user side prover time and it took about 9.6249 seconds on the Github Actions environment.

In this proposal, we implement rejubjub so we can delegate safely proof generation.
AWS server is high performance than the Github Actions environment so it won’t matter.

The most significant feature of Polkadot is that we can customize the blockchain runtime.
Ethereum can modify their EVM and it was not designed to process cryptographic scheme.
That’s why it uses plookup table and precompile functions.
In our case, we can change the blockchain runtime structure as latest cryptography-friendly.
I think that’s the best differentiation with other blockchains.

Sorry for the long text.
I think we can make Polkadot crazier.
Thank you!

1 Like