# Implement Crypto Primitives and Confidential Transfer Pallet **URL:** \ **Category:** Ecosystem\ **Tags:** treasury\ **Created:** [April 11, 2023, 1:09am UTC](https://forum.polkadot.network/t/implement-crypto-primitives-and-confidential-transfer-pallet/2569 "2023-04-11T01:09:43Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![ashWhiteHat](https://dub1.discourse-cdn.com/flex005/user_avatar/forum.polkadot.network/ashwhitehat/32/1418_2.png) [@ashWhiteHat](https://forum.polkadot.network/u/ashWhiteHat)\ **Post date:** [April 11, 2023, 1:09am UTC](https://forum.polkadot.network/t/implement-crypto-primitives-and-confidential-transfer-pallet/2569/1 "2023-04-11T01:09:43Z")
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. > > > I think https://github.com/arkworks-rs/curves/issues/17 should be straightforwar…d if you know both the substrate wasm boundary and elliptic curves, but probably nobody knows both. > > \--- > > I think https://github.com/kobigurk/aggregatable-dkg/issues/1 should be easy, but it'd fall more to the original authors, but if someone were interested.. > > \--- > > I implemented deliniearized witness multi-signatures in https://github.com/w3f/schnorrkel/blob/master/src/musig.rs in the commit https://github.com/w3f/schnorrkel/commit/fa6c35f832a4ae6f45e9c8e6858d90d1e2789fc7#diff-6ed16ffe933791b81e8340007a820ced7a47171ced9ce5378262d152951ec20d but at that time I'd no security proof so I kept the code encouraging the three round trip version. > > We now have a security proof in https://eprint.iacr.org/2020/1245 and Isis Lovecruft did a nice implementation of the two round trip version in https://github.com/isislovecruft/frost-dalek/ so we should really rip out my code and replace it with theirs. I could do this but so could many other people. > > A second implementation seems to be progressing in https://github.com/ZcashFoundation/redjubjub but its further from ristretto > > \--- > > I'd suspect generous gitcoin level bounties suffice for the all three of these. > [@ZK Rollups as Parachains](https://forum.polkadot.network/t/zk-rollups-as-parachains/2229/13): > > There is an ongoing effort to have host functions for ZK integration here from @achim I dont know how it will be used though. 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](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](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! ---
**Author:** ![burdges](https://dub1.discourse-cdn.com/flex005/user_avatar/forum.polkadot.network/burdges/32/172_2.png) [@burdges](https://forum.polkadot.network/u/burdges)\ **Post date:** [April 11, 2023, 4:59am UTC](https://forum.polkadot.network/t/implement-crypto-primitives-and-confidential-transfer-pallet/2569/2 "2023-04-11T04:59:24Z")
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. ---
**Author:** ![ashWhiteHat](https://dub1.discourse-cdn.com/flex005/user_avatar/forum.polkadot.network/ashwhitehat/32/1418_2.png) [@ashWhiteHat](https://forum.polkadot.network/u/ashWhiteHat)\ **Post date:** [April 11, 2023, 9:03am UTC](https://forum.polkadot.network/t/implement-crypto-primitives-and-confidential-transfer-pallet/2569/3 "2023-04-11T09:03:34Z")
Hi @burdges Thank you for the reply 😀 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. > **[GitHub - paritytech/arkworks-extensions: Library to integrate...](https://github.com/paritytech/arkworks-extensions)** > > Library to integrate arkworks-rs/algebra into Substrate - GitHub - paritytech/arkworks-extensions: Library to integrate arkworks-rs/algebra into Substrate 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](https://github.com/zkcrypto/jubjub/blob/47dfe5181ccf39166c0c479c35c0644d708f4294/src/lib.rs#L283), Naf representation can reduce n/6 hamming weight where n is bits number of field and also clean the zero [here](https://github.com/zero-network/zero/pull/60/files#diff-42968ca17fb4c150ad3280e899e0917997489b7c14606e100ec0cfd9778f7e5cR81). 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 > > > \# Improve Performance > > \## Benchmark > \[Benchmark\](https://github.com/zero-netwo…rk/zero/actions/runs/3936982113/jobs/6734005537) > \[Benchmark(msm)\](https://github.com/zero-network/zero/actions/runs/3938088853/jobs/6736370375) > > \### Bls12 381 > | \_ | add | sub | double | scalar / mul | square | invert | pow | > |---|---|---|---|---|---|---|---| > g1\_affine |1.3802 µs 1.3856 µs 1.3925 µs|1.3730 µs 1.3738 µs 1.3744 µs|1.0493 µs 1.0498 µs 1.0503 µs|434.38 µs 434.51 µs 434.64 µs|\_|\_|\_| > g1\_projective |1.3702 µs 1.3706 µs 1.3709 µs|1.3729 µs 1.3736 µs 1.3742 µs|1.0494 µs 1.0498 µs 1.0502 µs|427.97 µs 428.12 µs 428.26 µs|\_|\_|\_| > g2\_affine |5.6784 µs 5.6795 µs 5.6805 µs|5.6940 µs 5.6953 µs 5.6963 µs|4.2977 µs 4.2981 µs 4.2985 µs|1.8001 ms 1.8007 ms 1.8012 ms|\_|\_|\_| > g2\_projective |5.6720 µs 5.6751 µs 5.6778 µs|5.6812 µs 5.6857 µs 5.6897 µs|4.2811 µs 4.2859 µs 4.2901 µs|1.7669 ms 1.7688 ms 1.7713 ms|\_|\_|\_| > fr |8.9125 ns 8.9551 ns 9.0299 ns|8.4102 ns 8.4159 ns 8.4214 ns|8.1814 ns 8.1863 ns 8.1911 ns|48.537 ns 48.568 ns 48.599 ns|42.951 ns 42.958 ns 42.965 ns|21.729 µs 21.735 µs 21.740 µs|15.083 µs 15.086 µs 15.088 µs| > fq|15.142 ns 15.155 ns 15.166 ns|12.897 ns 12.907 ns 12.914 ns|13.669 ns 13.681 ns 13.691 ns|93.201 ns 93.223 ns 93.244 ns|92.196 ns 92.204 ns 92.214 ns|55.277 µs 55.282 µs 55.288 µs|\_| > fq2|31.849 ns 31.886 ns 31.933 ns|29.618 ns 29.637 ns 29.658 ns|36.221 ns 36.264 ns 36.302 ns|384.25 ns 385.80 ns 387.77 ns|377.49 ns 377.84 ns 378.21 ns|55.623 µs 55.641 µs 55.656 µs|\_| > fq6|152.50 ns 152.58 ns 152.65 ns|137.74 ns 137.76 ns 137.78 ns|144.41 ns 144.48 ns 144.55 ns|2.7686 µs 2.7725 µs 2.7774 µs|2.1881 µs 2.1896 µs 2.1908 µs|60.240 µs 60.262 µs 60.281 µs|\_| > fq12|359.73 ns 359.96 ns 360.17 ns|329.51 ns 329.66 ns 329.77 ns|384.40 ns 384.75 ns 385.44 ns|8.8706 µs 8.8997 µs 8.9387 µs|6.1294 µs 6.1326 µs 6.1353 µs|70.075 µs 70.126 µs 70.174 µs|\_| > > \### Confidential Transfer > > | \_ | Time | > |---|---| > | setup | 8.4388 s 8.4458 s 8.4534 s | > | gen\_proof | 10.676 s 10.758 s 10.879 s | > | verify\_proof | 13.477 ms 13.557 ms 13.680 ms | > > \### Jubjub > > | \_ | add | sub | double | scalar / mul | square | invert | pow | > |---|---|---|---|---|---|---|---| > |extended|547.36 ns 548.05 ns 548.78 ns|546.90 ns 547.04 ns 547.16 ns|375.16 ns 375.22 ns 375.29 ns|193.98 µs 194.00 µs 194.02 µs|\_|\_|\_| > |fp|8.9547 ns 9.0156 ns 9.0807 ns|8.4317 ns 8.4358 ns 8.4426 ns|8.1919 ns 8.1933 ns 8.1945 ns|48.469 ns 48.482 ns 48.494 ns|42.423 ns 42.428 ns 42.432 ns|18.334 µs 18.336 µs 18.338 µs|14.313 µs 14.314 µs 14.316 µs| > > \### Plonk > \- msm > > | \_ | Time | > |---|---| > | 8 |15.518 ms 15.528 ms 15.541 ms| > | 9 |26.011 ms 26.013 ms 26.015 ms| > | 10 |47.973 ms 47.988 ms 48.015 ms| > | 11 |86.871 ms 86.875 ms 86.880 ms| > | 12 |152.99 ms 152.99 ms 153.00 ms| > | 13 |281.96 ms 282.00 ms 282.05 ms| > | 14 |523.59 ms 523.63 ms 523.69 ms| > | 15 |931.85 ms 931.89 ms 931.93 ms| > | 16 |1.8141 s 1.8142 s 1.8142 s| > | 17 |3.3891 s 3.3892 s 3.3893 s| > | 18 |6.1931 s 6.1937 s 6.1948 s| > > \- pairing > > | \_ | Time | > |---|---| > | tate | 2.9226 ms 2.9228 ms 2.9231 ms | > | final\_exp | 1.8184 ms 1.8187 ms 1.8189 ms | > | miller\_loop | 1.1021 ms 1.1023 ms 1.1025 ms | > | multi\_miller\_loop | 2.4157 ms 2.4163 ms 2.4168 ms | > > \## Todo List > \- \[x\] Curve Scalar NAF https://github.com/zero-network/zero/pull/60 > \- \[x\] Optimize field double and square https://github.com/zero-network/zero/pull/64 > \- \[\] MSM wNAF and pippenger > \- \[x\] Twisted Edwards curve revisit https://github.com/zero-network/zero/pull/68 > \- \[x\] Replace Fft > \- \[x\] Replace Kzg > \- \[\] Jacobian coordinate > \- \[\] Copy and Clone vs Ref > \- \[\] Batch Affine I also think that code duplication and hard to replace with the new algorithm are also bad for optimization as the following issue mentioned. > > > Currently this library has two field implementations, the Pallas field and the V…esta field. They only differ in their prime modulus, and are otherwise almost identically implemented. This makes the library harder to maintain, as every change needs to be duplicated. > > There are several possible approaches we could take to improve the situation: > \- Use a declarative macro. > - We already use a declarative macro for implementing the curves, so it would be in keeping with the rest of the library. > - This has been proposed and implemented here: https://github.com/zcash/pasta\_curves/pull/44/commits/e150cc5670ba3559dd9a89609ffb41495ee560e3 > \- Use a procedural macro, i.e. \`ff\_derive\` > - This is how we originally implemented BLS12-381 in the \`pairing\` crate, but we replaced that with a direct implementation of the field in the \`bls12\_381\` crate, and \`ff\_derive\` hasn't been as effectively maintained since. If we switched to it, the majority of our field maintenance effort could go into \`ff\_derive\` instead of here. > \- Use \[\`crypto-bigint\`\](https://crates.io/crates/crypto-bigint) to implement the internal field details. > - This would reduce the amount of code we need to maintain, which would just be the mapping from a big integer element to a prime field element. > - This would be quite a divergence from previous approaches. I also don't know how feature-complete \`crypto-bigint\` is, though progress is being made. > - If this is a practical and performant approach, we could also combine it with either the declarative macro or \`ff\_derive\` approach to make it easier to maintain as well. 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. > > > \# Improve Performance > > \## Benchmark > \[Benchmark\](https://github.com/zero-netwo…rk/zero/actions/runs/3936982113/jobs/6734005537) > \[Benchmark(msm)\](https://github.com/zero-network/zero/actions/runs/3938088853/jobs/6736370375) > > \### Bls12 381 > | \_ | add | sub | double | scalar / mul | square | invert | pow | > |---|---|---|---|---|---|---|---| > g1\_affine |1.3802 µs 1.3856 µs 1.3925 µs|1.3730 µs 1.3738 µs 1.3744 µs|1.0493 µs 1.0498 µs 1.0503 µs|434.38 µs 434.51 µs 434.64 µs|\_|\_|\_| > g1\_projective |1.3702 µs 1.3706 µs 1.3709 µs|1.3729 µs 1.3736 µs 1.3742 µs|1.0494 µs 1.0498 µs 1.0502 µs|427.97 µs 428.12 µs 428.26 µs|\_|\_|\_| > g2\_affine |5.6784 µs 5.6795 µs 5.6805 µs|5.6940 µs 5.6953 µs 5.6963 µs|4.2977 µs 4.2981 µs 4.2985 µs|1.8001 ms 1.8007 ms 1.8012 ms|\_|\_|\_| > g2\_projective |5.6720 µs 5.6751 µs 5.6778 µs|5.6812 µs 5.6857 µs 5.6897 µs|4.2811 µs 4.2859 µs 4.2901 µs|1.7669 ms 1.7688 ms 1.7713 ms|\_|\_|\_| > fr |8.9125 ns 8.9551 ns 9.0299 ns|8.4102 ns 8.4159 ns 8.4214 ns|8.1814 ns 8.1863 ns 8.1911 ns|48.537 ns 48.568 ns 48.599 ns|42.951 ns 42.958 ns 42.965 ns|21.729 µs 21.735 µs 21.740 µs|15.083 µs 15.086 µs 15.088 µs| > fq|15.142 ns 15.155 ns 15.166 ns|12.897 ns 12.907 ns 12.914 ns|13.669 ns 13.681 ns 13.691 ns|93.201 ns 93.223 ns 93.244 ns|92.196 ns 92.204 ns 92.214 ns|55.277 µs 55.282 µs 55.288 µs|\_| > fq2|31.849 ns 31.886 ns 31.933 ns|29.618 ns 29.637 ns 29.658 ns|36.221 ns 36.264 ns 36.302 ns|384.25 ns 385.80 ns 387.77 ns|377.49 ns 377.84 ns 378.21 ns|55.623 µs 55.641 µs 55.656 µs|\_| > fq6|152.50 ns 152.58 ns 152.65 ns|137.74 ns 137.76 ns 137.78 ns|144.41 ns 144.48 ns 144.55 ns|2.7686 µs 2.7725 µs 2.7774 µs|2.1881 µs 2.1896 µs 2.1908 µs|60.240 µs 60.262 µs 60.281 µs|\_| > fq12|359.73 ns 359.96 ns 360.17 ns|329.51 ns 329.66 ns 329.77 ns|384.40 ns 384.75 ns 385.44 ns|8.8706 µs 8.8997 µs 8.9387 µs|6.1294 µs 6.1326 µs 6.1353 µs|70.075 µs 70.126 µs 70.174 µs|\_| > > \### Confidential Transfer > > | \_ | Time | > |---|---| > | setup | 8.4388 s 8.4458 s 8.4534 s | > | gen\_proof | 10.676 s 10.758 s 10.879 s | > | verify\_proof | 13.477 ms 13.557 ms 13.680 ms | > > \### Jubjub > > | \_ | add | sub | double | scalar / mul | square | invert | pow | > |---|---|---|---|---|---|---|---| > |extended|547.36 ns 548.05 ns 548.78 ns|546.90 ns 547.04 ns 547.16 ns|375.16 ns 375.22 ns 375.29 ns|193.98 µs 194.00 µs 194.02 µs|\_|\_|\_| > |fp|8.9547 ns 9.0156 ns 9.0807 ns|8.4317 ns 8.4358 ns 8.4426 ns|8.1919 ns 8.1933 ns 8.1945 ns|48.469 ns 48.482 ns 48.494 ns|42.423 ns 42.428 ns 42.432 ns|18.334 µs 18.336 µs 18.338 µs|14.313 µs 14.314 µs 14.316 µs| > > \### Plonk > \- msm > > | \_ | Time | > |---|---| > | 8 |15.518 ms 15.528 ms 15.541 ms| > | 9 |26.011 ms 26.013 ms 26.015 ms| > | 10 |47.973 ms 47.988 ms 48.015 ms| > | 11 |86.871 ms 86.875 ms 86.880 ms| > | 12 |152.99 ms 152.99 ms 153.00 ms| > | 13 |281.96 ms 282.00 ms 282.05 ms| > | 14 |523.59 ms 523.63 ms 523.69 ms| > | 15 |931.85 ms 931.89 ms 931.93 ms| > | 16 |1.8141 s 1.8142 s 1.8142 s| > | 17 |3.3891 s 3.3892 s 3.3893 s| > | 18 |6.1931 s 6.1937 s 6.1948 s| > > \- pairing > > | \_ | Time | > |---|---| > | tate | 2.9226 ms 2.9228 ms 2.9231 ms | > | final\_exp | 1.8184 ms 1.8187 ms 1.8189 ms | > | miller\_loop | 1.1021 ms 1.1023 ms 1.1025 ms | > | multi\_miller\_loop | 2.4157 ms 2.4163 ms 2.4168 ms | > > \## Todo List > \- \[x\] Curve Scalar NAF https://github.com/zero-network/zero/pull/60 > \- \[x\] Optimize field double and square https://github.com/zero-network/zero/pull/64 > \- \[\] MSM wNAF and pippenger > \- \[x\] Twisted Edwards curve revisit https://github.com/zero-network/zero/pull/68 > \- \[x\] Replace Fft > \- \[x\] Replace Kzg > \- \[\] Jacobian coordinate > \- \[\] Copy and Clone vs Ref > \- \[\] Batch Affine 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!