Implement Crypto Primitives and Confidential Transfer Pallet

ashWhiteHat · April 11, 2023, 1:09am

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.

github.com/w3f/Grants-Program

Three RFPs for "easy" crypto implementation

opened 07:52PM - 19 Jan 21 UTC

burdges

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.

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.

github.com

KogarashiNetwork/Kogarashi/blob/227477e52867a07c7be98b84787cca0dbdf98c16/pallets/confidential_transfer/src/lib.rs

// Copyright (C) 2023-2024 Inverse (JP) LLC.
// SPDX-License-Identifier: Apache-2.0

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 	http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#![cfg_attr(not(feature = "std"), no_std)]
#![allow(clippy::unused_unit)]

pub use pallet::*;

This file has been truncated. show original

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!

burdges · April 11, 2023, 4:59am

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.

ashWhiteHat · April 11, 2023, 9:03am

Hi @burdges
Thank you for the reply

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

Compatibility with Substrate runtime
Performance optimization
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.

github.com

KogarashiNetwork/Kogarashi/blob/ff5c00469ab11b457ae2642af89979ea335c8748/pallets/encrypted_balance/src/lib.rs#L197


      
                  + Default
                  + Copy
                  + MaybeSerializeDeserialize
                  + Debug
                  + ConfidentialTransferPublicInputs<Self::P>;
          
              /// The overarching event type.
              type Event: From<Event<Self, I>> + IsType<<Self as frame_system::Config>::Event>;
          
              /// The means of storing the balances of an account.
              type AccountStore: StoredMap<Self::AccountId, AccountData<Self::EncryptedBalance>>;
          
              /// Weight information for extrinsics in this pallet.
              type WeightInfo: WeightInfo;
          }
          
          #[pallet::pallet]
          #[pallet::generate_store(pub(super) trait Store)]
          pub struct Pallet<T, I = ()>(PhantomData<(T, I)>);
          
          #[pallet::hooks]

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.

github.com

KogarashiNetwork/Kogarashi/blob/ff5c00469ab11b457ae2642af89979ea335c8748/primitive/kzg/src/fft.rs#L109


      
          pub fn size(&self) -> usize {
              self.n
          }
          
          /// nth unity of root
          pub fn generator(&self) -> F {
              self.twiddle_factors[1]
          }
          
          /// perform discrete fourier transform
          pub fn dft(&self, coeffs: &mut Polynomial<F>) {
              self.prepare_fft(coeffs);
              classic_fft_arithmetic(&mut coeffs.0, self.n, 1, &self.twiddle_factors)
          }
          
          /// perform classic inverse discrete fourier transform
          pub fn idft(&self, coeffs: &mut Polynomial<F>) {
              self.prepare_fft(coeffs);
              classic_fft_arithmetic(&mut coeffs.0, self.n, 1, &self.inv_twiddle_factors);
              coeffs.0.iter_mut().for_each(|coeff| *coeff *= self.n_inv)
          }

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

github.com/KogarashiNetwork/Kogarashi

Optimization

opened 03:42AM - 07 Jan 23 UTC

closed 06:48AM - 05 Nov 23 UTC

ashWhiteHat

performance

# 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.

github.com/zcash/pasta_curves

Reduce code duplication in field implementations

opened 02:23AM - 13 Oct 22 UTC

str4d

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.

github.com/KogarashiNetwork/Kogarashi

Optimization

opened 03:42AM - 07 Jan 23 UTC

closed 06:48AM - 05 Nov 23 UTC

ashWhiteHat

performance

# 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!

Topic		Replies	Views
Improving the substrate/ecosystem vulnerabilities disclosure Tech Talk security	19	1322	April 15, 2024
Hybrid system chains make Polkadot permissionless Tech Talk	15	1207	July 16, 2024
ParityTech update for June 2024 Ecosystem	0	292	July 4, 2024
Polkadot Digest 25 Nov 2022 Digest	0	308	November 25, 2022
Open Discussion Thread: Fall 2022 Roadmap Roundup	18	1149	November 12, 2022

Related topics