[apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tiancheng Xie <no...@github.com>]

Significant progress has been made during recent years due to the development of blockchain. However, these cryptography protocols are hard to implement correctly and even more hard to parallelize. A lot of them can be efficiently parallelized, and I will list some of them later. It shares a  data-parallel nature with deep learning tasks.

Existing new papers are doing the experiment in single-thread mode, and claiming that it's parallelizable like [Ligero](https://acmccs.github.io/papers/p2087-amesA.pdf), [Libra](https://eprint.iacr.org/2019/317). I am an author of Libra (not the facebook libra), and I tried to implement a parallelized one. There are several reasons for not presenting the parallelized program in our paper:

- The zero-knowledge community usually doesn't do the parallelized implementation, and it's considered unfair to do this. If we can make an easy tool to parallelize it, it will gradually become a standard way for the community, and no fairness problem.
- It's tricky to deal with cache misses. It will be nice to have an automatic tool to balance the parallelism and cache misses, and even deliver GPU&ASIC implementations.

# Example applications
## Merkle tree
Merkle tree enables Alice to commit their secret data and Bob can verify the membership of that secret data. Alice cannot modify the secret data after the commitment is made. 

It builds a binary tree, where leaves are the data itself, and for every parent node, it hashes the child node and stores the hash value. Alice will output the root node as the commitment. Any data modify will change the root completely, so it will preserve the data integrity. The structure enables Bob to ask Alice what's the value is at a specific leaf node, then Alice can provide the whole tree path from that leaf node to the root. Bob can verify the integrity of data by doing hash. And checking the hash result is identical to the root.

Such structure is parallelizable, we can parallel evaluate hashes for each node. And we can finish the commitment generation in only O(log n) rounds.

## Polynomial commitment
Polynomial commitment enables Alice to commit to a polynomial F(x). After she committed the polynomial, she cannot change the polynomial, otherwise, the change will be detected in verification phase.

The verification phase(or opening phase), will open the commitment to a specific point z, and it will return the polynomial value F(z) as well as a proof for the validity of the value (say the value is actually derived from the polynomial that is committed before).

This can be implemented by a combination of NTTs (FFT in finite fields) and some other minor parts. So it can be parallelized efficiently like FFT.

## Zero-knowledge proofs

It's a bit hard to explain, but it can be constructed from polynomial commitments. Industrial level implementations actually do parallelization but it's great if we can make a tool for such tasks.

# Major Todos (for now)
## Implement a demo project (Proof of Concept)
I could help to implement our zero-knowledge proofs protocol using TVM, and hopefully, we can take advantage of the data parallelism. In my own implementation, I tried to hand-code the AVX2 codes and some assembly codes to make it faster which look very old-school.

This implementation will include implementing all primitives that I mentioned in the previous section and we do have a C++ implementation as a reference. I could DIY it and submit the code later. Most likely, I will use the Python interface.

## A clear developer guide for Rust programmers
It's better to have a Rust tutorial because many security companies prefer to use rust in sake of security of the code. For now, as I noticed, we only have a great tutorial for python.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Junru Shao <no...@github.com>]

Hi Tiancheng,

It would be super excited and great impact if TVM is enabled to express crypto protocols and primitives. While I think the RFC does a perfect job in enumerating all the tasks from the crypto side, would you mind talking about something on the compiler side? For example, it would be great for the community to know how many of those primitives can be expressed as intrinsic (links will be helpful), and whether others could be abstracted as op.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-558749080

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tiancheng Xie <no...@github.com>]

> Shall the `basic primitives` implemented in the runtime? Or it could be designed with either hybrid script or ir_builder, I mean the primitives could be generated.

I would prefer "intrinsic"

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-558285868

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tiancheng Xie <no...@github.com>]

Some story
When I was writing Libra and it’s followup, @merrymercy come and asks “why are you implementing this with a handwritten AVX2 code? It’s already the year 9012! Try tvm instead.”

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-557700093

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tianqi Chen <no...@github.com>]

Closed #4403.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#event-3568430785

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tianqi Chen <no...@github.com>]

closing for now due to inactive status, feel free to reopen

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-661492467

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tiancheng Xie <no...@github.com>]

> Interesting, cc @nhynes regarding rust interface.



-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-557739982

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tiancheng Xie <no...@github.com>]

Reopened #4403.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#event-2824935991

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Nick Hynes <no...@github.com>]

> rust interface

The rust interface is currently only that of a TVM runtime, but that's sufficient since the kernels are already memory safe. For maximum safety (but slightly less flexibility from dynamic linking), one would use the [non-bindings] runtime in `rust/runtime`. At least until TVM exposes a C FFI to the compiler internals, developers will necessarily have a polyglot workflow.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-557739011

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Tiancheng Xie <no...@github.com>]

Closed #4403.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#event-2824935908

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[masahi <no...@github.com>]

Interesting, cc @nhynes regarding rust interface.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-557733313

Re: [apache/incubator-tvm] [RFC][Cryptography] Modernize the cryptography implementation (#4403)

[Liangfu Chen <no...@github.com>]

Shall the `basic primitives` implemented in the runtime? Or it could be designed with either hybrid script or ir_builder, I mean the primitives could be generated.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4403#issuecomment-557970826