Add zkp in neo

[doubiliu]

Summary or problem description
Zero-knowledge proof is currently one of the most popular technologies in blockchain technology. In this issue, I want to integrate this technology into neo, so that applications such as anonymous currency and 2-layer networks can be further developed.
There are multiple schemes for zero-knowledge proof, and there are multiple implementations for each scheme. The solution I explained is the PGRH13 implementation of zk-snark, and the groth16 implementation will be explained later.

zk-snark:Zero-knowledge succint non-interactive arguments of knowledge (zk-snark) is one of various zero-knowledge proof systems. It is a zero-knowledge proof based on polynomial construction.

• zero knowledge - zero knowledge proof
• succinct - the proof is succinct and can be verified easily.
• non-interactivity - the prover just provides a string, which will then be placed on the blockchain for public verification.
• arguments - the proving process is computationally soundness. The prover cannot fake the proof within a reasonable time.
• of knowledge - It is impossible for a prover to construct a valid zero-knowledge proof without knowing the specific proof (witness).

PGRH13: An implementation of zk-snark
Groth16: An implementation of zk-snark, which saves more space than the PGRH13 solution

Do you have any solution you want to propose?

Modification in neo:
Add new interoperability methods

zk protocol：
Suppose the prover needs to prove to the verifier that he knows some secret data

The above process may be too abstract, then I will make a detailed derivation.Welcome to discuss and point out the errors.

First, we limit the secret data to some special data, and then generalize it to the general form.
Then，suppose A claims to know a secret polynomial of degree d (B knows the secret polynomial, or only the calculation results of the polynomial at some particular points), how can verifier B verify that A knows the secret polynomial?

• Option 1: A directly announces all the coefficients of the secret polynomial (knowing a polynomial is equivalent to knowing all the polynomial coefficients)
• Option 2: Design a proving protocol

Proving protocol V1.0
Verification steps:

1. B randomly selects a point x and record the calculation result f(x) of the polynomial corresponding to x
2. B sends x to A
3. A calculates the corresponding polynomial result f`(x) and sends it to B
4. B checks that f`(x) = f(x), If so, it proves that A knows the secret polynomial; otherwise A doesn't know.
   Some known issues:

• There is no guarantee that A uses the secret polynomial to calculate f`(x)
• B and A can solve each other's secret polynomials (i.e. solve algebraic equations)
  ......

Of course, if we understand the properties of some polynomials, the above verification protocol can also be written in another form.

ttps://user-images.githubusercontent.com/42929757/146680024-e95a1b9b-f711-42f3-ba4b-3c0d1c7bbcf5.PNG)

Proving protocol V2.0
Verification steps:

1. B samples a random value r, calculates $$ t=t(r) $$ and gives r to A
2. A calculates $$ h(x)=f(x)/t(x) $$ and evaluates $$ f=f(r) $$ and $$ h=h(r) $$, and sends the resulting values f, h to B
3. B checks that $$ f=th $$, if so those polynomials are equal, proving that A knows the secret polynomial
   Some known issues:

• Because A knows r, he or she can forge h to make f= t⋅h holds
• The degree of A's secret polynomial is uncontrollable
• B and A can solve each other's secret polynomials
  ......

The major issue of above protocol is exposure of the random r and resulting value calculated with r.
Multiple issues can be addressed if there is a block box that could verify f(r)= t(r)⋅h(r) without revealing r and resulting values such as h(r),f(r).Fortunately, we can use the homomorphic properties of the encryption function to achieve.

Proving protocol V3.0

The biggest problem with the above verification protocol is that it cannot guarantee that the prover will construct the polynomial correctly according to the operation rules, so we need to introduce some additional security settings

Proving protocol V4.0 (Blind Evaluation of Polynomials)

Let us temporarily ignore some of the security issues that still exist in the verification protocol, and first extend it to the proof of general calculation problems.
Variables in general calculation problems always have some potential equation relations
Example: suppose A wants to prove to B that he knows c1，c2，c3， (c1⋅c2)⋅(c1+c3)=7, and he needs to keep c1，c2，c3 secret.
(c1⋅c2)⋅(c1+c3)=7 is the equation of c1，c2，c3.
We can use a special representation method R1CS to express these equation relations.

R1CS circuit description: The equation relation corresponds to an arithmetic operation process, which is called arithmetic circuit because of its similarity to logic circuits, and is represented in a special way, called the R1CS circuit description.

The equation is somewhat complicated so we need to simplify it using a specific flattenning method.
Flattening method: That is, adding intermediate variables to reduce dimension of the complex equation relation to the simplest form of constraint.
Example:

In addition, we found that these matrices are transformed by the Lagrangian interpolation theorem. This transformation is called the QAP quadratic arithmetic program.QAP is a program to transform vector verification into polynomial verification, the core of which is the Lagrange interpolation method.

Then we can get:

Universal proving protocol V1.0

At this point, we have been able to prove the general problem, but as mentioned before, the protocol still has some security issues. In order to solve these security issues, we need to introduce some additional settings, which we call the Pinocchio protocol

Universal proving protocol V2.0

The general protocol also has the problem of brute force cracking and the abuse of encryption certification, and random offset needs to be introduced.

Universal proving protocol (final version)



The PDF can be obtained here：
zksnarkissue(en).pdf

Commonly used R1CS circuits
Scope proof
To prove that the value of a private input w is between 0 and 15, construct a constraint as follows：

Purpose: Proof of amount

CRS public string in trusted initial process
All random values generated during the initialization process of the above protocols must be disclosed after being encrypted. The encrypted text is known as the CRS public string, while the original random values, called "toxic waste" must be destroyed as soon as the CRS is created, otherwise it can be used by adversaries to forge proofs.
To ensure that toxic waste is truly removed, multi-party computation (MPC) is required to ensure security.

References

• Why and How zk-SNARK Works: Definitive Explanation

Neo Version

• Neo 3

Where in the software does this update applies to?

• Other:

[doubiliu]

Well, I will explain the Groth16 implementation of zk-snark

[doubiliu]

Groth16

Principle Analysis

Groth16 is one implementation of zk-snark, which is optimized mainly on the basis of PGRH13. It implements the process of proof and verification through 3 points (at least 2 points).

Proof of Completeness

Proof of Security

At this time if the same offset occurs, many new elements will be generated according to the product rule. Since $$[C]_1[\delta]_2$$ is a product of two points, it is impossible for C to reverse operation and make corresponding changes. This makes the range of offset transformation very limited, which can only be multiples of random offsets. Therefore, the attack method is relatively simple, which can be avoided by other means. This attack is known as a processability attack.

The PDF can be obtained here：
groth16 scheme analysis.pdf

References

• Groth16

[doubiliu]

Later I will explain the trusted set-up scheme of Groth16. Related documents will be uploaded as soon as possible

[EdgeDLT]

Really happy to see this direction on Neo @doubiliu! Could you clarify if this is a proposal to use Groth16 for SNARKs on Neo, or if Groth16 is only being used as an example to illustrate the concept?

I ask because I believe it would be more practical to prioritize a universal SNARK proof system (like PLONK or Marlin). For the tradeoff of a somewhat larger proof size, it removes the need for a new trusted setup on every arbitrary circuit. Needing a new ceremony for every contract or update to a contract is very cumbersome and introduces more risks that toxic waste isn't properly dealt with.

I think it would result in a much more developer-friendly solution for those who want to build their own applications using ZKP on Neo.

[doubiliu]

We will first add some interoperability in neo-core to support the groth16 solution, because efficiency and some mature projects can learn from.
We want to develop some applications on neo, such as rollup or neo-cash. On the basis of completing these, we may consider additional support for plonk, sonic and other solutions

[doubiliu]

Different solutions have their advantages and disadvantages, the advantage of groth16 is its size and speed of verification

[doubiliu]

We have prepared a demo.
This is to prove that a&b=0 , a,b is private input

[doubiliu]

using System;
using System.ComponentModel;
using Neo.SmartContract.Framework;
using Neo.SmartContract.Framework.Attributes;
using Neo.SmartContract.Framework.Services;

namespace BLSVerifyDemoContract
{
[DisplayName("BLSVerifyDemoContract")]
[ManifestExtra("Author", "NGD")]
[ManifestExtra("Email", "dev@neo.org")]
[ManifestExtra("Description", "This is a verification demo of zk circuit")]
[ContractPermission("", "")]
public class BLSVerifyDemoContract : SmartContract
{
//These parameters need to be obtained by means of an MPC process

    public static readonly byte[] alphaPoint = { 0, 106, 167, 155, 164, 170, 67, 158, 237, 78, 91, 7, 243, 191, 186, 221, 27, 97, 6, 190, 193, 204, 85, 206, 83, 56, 3, 209, 132, 249, 221, 94, 124, 20, 245, 113, 143, 70, 245, 159, 104, 213, 37, 151, 209, 125, 160, 143, 22, 78, 252, 97, 225, 215, 133, 240, 84, 149, 231, 142, 83, 116, 156, 136, 120, 45, 242, 155, 199, 169, 244, 228, 221, 245, 160, 28, 247, 39, 83, 6, 172, 25, 126, 223, 231, 40, 94, 154, 69, 103, 123, 105, 242, 163, 156, 220 };

    public static readonly byte[] betaPoint = { 3, 91, 30, 20, 61, 202, 142, 33, 164, 33, 215, 106, 219, 39, 136, 96, 112, 254, 117, 55, 156, 44, 55, 125, 240, 63, 166, 206, 157, 17, 201, 11, 33, 172, 226, 58, 254, 202, 46, 128, 2, 179, 227, 37, 230, 127, 121, 118, 6, 59, 84, 145, 104, 196, 68, 37, 209, 54, 86, 148, 155, 251, 36, 110, 127, 190, 205, 52, 100, 136, 226, 196, 249, 172, 122, 215, 230, 42, 92, 175, 190, 120, 19, 80, 56, 148, 236, 157, 108, 74, 45, 29, 157, 243, 96, 94, 17, 16, 242, 165, 56, 132, 223, 128, 0, 35, 238, 8, 138, 176, 102, 236, 242, 177, 252, 151, 152, 94, 230, 130, 111, 185, 250, 195, 15, 125, 31, 128, 3, 102, 181, 56, 19, 195, 121, 224, 82, 228, 3, 41, 31, 122, 220, 133, 18, 212, 95, 194, 201, 185, 75, 111, 233, 98, 80, 47, 9, 191, 178, 119, 49, 238, 30, 235, 217, 40, 8, 199, 253, 123, 8, 85, 78, 100, 32, 111, 185, 57, 197, 240, 76, 6, 252, 16, 114, 82, 90, 163, 240, 146, 4, 2 };

    public static readonly byte[] gamma_inversePoint = { 23, 69, 47, 108, 115, 173, 254, 203, 89, 67, 183, 224, 176, 26, 127, 132, 89, 162, 99, 241, 66, 228, 177, 17, 57, 85, 3, 13, 148, 88, 162, 54, 220, 189, 33, 172, 38, 192, 116, 236, 13, 115, 219, 201, 51, 166, 253, 240, 12, 32, 77, 82, 161, 189, 240, 198, 148, 184, 17, 92, 162, 145, 166, 55, 252, 245, 194, 95, 71, 208, 215, 23, 19, 95, 138, 147, 149, 26, 35, 108, 141, 25, 139, 103, 59, 48, 189, 88, 204, 100, 255, 116, 194, 229, 157, 5, 19, 16, 31, 158, 222, 45, 151, 86, 218, 157, 17, 252, 29, 131, 121, 107, 168, 46, 145, 176, 122, 146, 93, 180, 181, 98, 229, 4, 29, 34, 137, 222, 93, 124, 90, 211, 99, 51, 90, 96, 191, 203, 14, 34, 14, 5, 77, 209, 0, 62, 138, 150, 103, 94, 252, 200, 186, 64, 197, 27, 173, 229, 189, 193, 196, 75, 40, 95, 107, 36, 50, 90, 146, 59, 215, 202, 184, 77, 87, 20, 53, 241, 208, 72, 158, 45, 22, 81, 53, 220, 40, 222, 26, 69, 230, 253 };

    public static readonly byte[] deltaPoint = { 1, 78, 83, 175, 159, 103, 127, 217, 80, 213, 0, 194, 108, 30, 210, 241, 138, 209, 0, 164, 117, 32, 68, 102, 121, 36, 40, 65, 89, 205, 198, 1, 14, 144, 196, 236, 176, 214, 119, 139, 225, 118, 215, 185, 36, 216, 183, 27, 22, 126, 193, 21, 173, 212, 250, 104, 25, 69, 107, 40, 199, 160, 228, 239, 112, 102, 144, 85, 58, 109, 122, 73, 221, 170, 145, 188, 60, 9, 228, 178, 36, 227, 175, 140, 40, 181, 158, 175, 91, 189, 92, 169, 90, 90, 30, 153, 4, 225, 187, 53, 206, 114, 60, 109, 51, 184, 2, 100, 39, 95, 43, 33, 82, 141, 161, 200, 136, 146, 33, 18, 202, 141, 43, 222, 64, 81, 151, 58, 141, 146, 8, 214, 159, 110, 167, 173, 253, 57, 190, 62, 94, 88, 245, 59, 20, 121, 233, 209, 122, 42, 13, 184, 114, 0, 19, 32, 120, 143, 108, 118, 107, 241, 218, 182, 69, 135, 117, 42, 231, 191, 199, 88, 88, 145, 134, 24, 133, 211, 53, 72, 23, 214, 105, 97, 134, 254, 116, 89, 166, 119, 221, 223 };

    public static readonly byte[][] ic  = new byte[][] { new byte[] { 14, 152, 253, 159, 101, 142, 227, 5, 166, 71, 152, 207, 32, 152, 56, 172, 191, 43, 184, 28, 148, 40, 224, 42, 135, 137, 181, 215, 96, 34, 200, 127, 77, 151, 165, 11, 130, 57, 91, 83, 71, 38, 253, 159, 103, 191, 139, 120, 20, 9, 91, 120, 106, 16, 209, 88, 87, 206, 209, 233, 129, 87, 15, 139, 92, 164, 84, 150, 51, 92, 220, 188, 115, 217, 131, 193, 213, 23, 225, 128, 244, 135, 95, 128, 181, 127, 159, 195, 219, 176, 152, 16, 186, 80, 5, 143 }, new byte[] { 17, 158, 199, 19, 137, 211, 161, 248, 118, 149, 250, 145, 46, 221, 160, 86, 40, 165, 110, 198, 160, 203, 188, 84, 210, 83, 159, 176, 113, 111, 10, 235, 192, 243, 242, 110, 188, 210, 98, 199, 74, 66, 118, 251, 3, 188, 58, 84, 23, 55, 88, 168, 37, 240, 121, 248, 22, 139, 165, 151, 47, 163, 72, 114, 80, 152, 28, 160, 76, 58, 252, 162, 110, 107, 202, 173, 57, 219, 79, 119, 196, 249, 84, 215, 233, 11, 59, 50, 204, 23, 149, 64, 88, 135, 163, 190 } };

    /// <summary>
    /// Verify '&' circuit.To verify x1&x2 = 0 or 1
    /// AB=alpha*beta+sum(pub_input[i]*(beta*u_i(x)+alpha*v_i(x)+w_i(x))/gamma)*gamma+C*delta
    /// </summary>
    /// <param name="a">Point A</param>
    /// <param name="b">Point B</param>
    /// <param name="c">Point C</param>
    /// <param name="public_input">Public paramters</param>
    /// <returns>result</returns>
    public static bool Veify(byte[] a, byte[] b, byte[] c, long[] public_input)
    {
        //Equation left1: A*B
        byte[] lt = Crypto.Bls12381Pairing(a, b);
        //Equation right1: alpha*beta
        byte[] rt1 = Crypto.Bls12381Pairing(alphaPoint, betaPoint);
        //Equation right2: sum(pub_input[i]*(beta*u_i(x)+alpha*v_i(x)+w_i(x))/gamma)*gamma
        int inputlen = public_input.Length;
        int iclen = ic.Length;
        if (iclen != inputlen + 1) throw new Exception("error: inputlen or iclen");
        byte[] acc = ic[0];
        for (int i = 0; i < inputlen; i++)
        {
            byte[] temp = Crypto.Bls12381Mul(ic[i + 1], public_input[i]);
            acc = Crypto.Bls12381Add(acc, temp);
        }
        byte[] rt2 = Crypto.Bls12381Pairing(acc, gamma_inversePoint);
        //Equation right3: C*delta
        byte[] rt3 = Crypto.Bls12381Pairing(c, deltaPoint);
        //Check equal
        byte[] t1 = Crypto.Bls12381Add(rt1, rt2);
        byte[] t2 = Crypto.Bls12381Add(t1, rt3);
        return lt==t2;
    }
}

}

[doubiliu]

Use
invoke contracthash veify [{"type":"ByteArray","value":"AlidcPpIlaeMy1LgULIZp1FOhxbDumJyfy9POMZzBNZJq2G7DW8Bt9fHDIBOu3HRB5qyDAIkQur6mtWVSm8eeJNCzho8dx1D3BkHblko//BlNQmNaC2548y7z8uepOZ/"},{"type":"ByteArray","value":"B/byS67ab0A/GySx8Eh5Xic/N7DHpZgbszYDAwmFYbUQ621Sf6lCrmoQR2qDrx6vDZCrLtcVuO5Onw+5sQ0w5zOPy63VmqAB8uMCpHyQx2Knr3pyZokMMFSDAKmeN4DmEQMYuQPZZ6B+c8myrpLHiN0fNp3RAysVZbH0yIWciz5QRa8IeS4TMjMw1ssBYuIfEUVrwHVA60mya0SkxEbujnDnJBQ+LU4WU39nh973t1O5DTuVJJFa/luzV65sl2W3"},{"type":"ByteArray","value":"ANUMljD/MeKGiKKIijEh4oI56dq9Y/p0IVyjdrHYj67d4UlkXlTz5I4o9qLxMK+tCwqbS6ciwx4jjmPgpz+0OzK5t6IViis7ZCEkOoO7Dtzgltvna+cu23BdyK9S5sj2"},{"type":"Array","value":[{"type":"Integer","value":0}]}]

[AnnaShaleva]

@doubiliu, we've successfully adapted new Groth16-related interops and tried to build and run simple Groth16 verifier contract on NeoGo nodes (in the nspcc-dev/neo-go#3043), it works perfectly.

My question is whether MPC ceremony will be organized by the core developers to generate the initial randomness after 3.6.0 release? Or maybe it's the duty of every dApp developer team to run the MPC ceremony for their own dApp?

[EdgeDLT]

My question is whether MPC ceremony will be organized by the core developers to generate the initial randomness after 3.6.0 release? Or maybe it's the duty of every dApp developer team to run the MPC ceremony for their own dApp?

Is Neo going to offer an MPC setup solution?

The way I see it, it should be both. Do an organized event for Powers of Tau to generate the universal* part. Then Neo provides tools for phase 2 setup so that dApp developers can take the responsibility of generating their own circuit-specific reference strings.

^{* up to a constraint limit}

[AnnaShaleva]

Is Neo going to offer an MPC setup solution?

I'm not aware of it, that's why I'm interested in the way how it's planned to be held.

The way I see it, it should be both.

I absolutely agree, there should be two phases to match the standards, but I'm not sure whether some work is being made in this direction and what the real plans are. I'm wondering, who is responsible for the phase 1 organization and who are the participants of the upcoming MPC ceremony.

Then Neo provides tools for phase 2 setup

I saw the phase2 cloned repo with some adjustments (https://github.com/doubiliu/phase2), but there's not a lot of ducumentation and instructions. I know that phase1 and phase2 won't be different for Neo network (comparing to randomness generation ceremonies taken by other projects like Ethereum), but we probably need to provide more clear documentation for Neo community developers to make it easier to build ZKP-related dApps. Maybe I'm just not aware of it and someone can point me to the relevant Neo documentation.

[doubiliu]

Let me explain that mpc has 2 parts, Phase 1 and Phase 2. In the library I provided to you, I have abstracted it into a very convenient interface, and I only used a compatible format for the relevant data format used in Phase 1, so you can directly use
the data generated by eth or by neo itself.Phase 2 data needs to be initiated by the project party itself, but our tools can be integrated. @AnnaShaleva

[doubiliu]

Is Neo going to offer an MPC setup solution?

I'm not aware of it, that's why I'm interested in the way how it's planned to be held.

The way I see it, it should be both.

I absolutely agree, there should be two phases to match the standards, but I'm not sure whether some work is being made in this direction and what the real plans are. I'm wondering, who is responsible for the phase 1 organization and who are the participants of the upcoming MPC ceremony.

Then Neo provides tools for phase 2 setup

I saw the phase2 cloned repo with some adjustments (https://github.com/doubiliu/phase2), but there's not a lot of ducumentation and instructions. I know that phase1 and phase2 won't be different for Neo network (comparing to randomness generation ceremonies taken by other projects like Ethereum), but we probably need to provide more clear documentation for Neo community developers to make it easier to build ZKP-related dApps. Maybe I'm just not aware of it and someone can point me to the relevant Neo documentation.

I have plans to prepare related documents. In fact, I originally planned to release it after the release of neo3.6, because it involves some changes to the compiler. In the library I provided to you, I have provided a minimal MPC process and comments (https://github.com/doubiliu/phase2/blob/dev/src/mpc/mod.rs)

[AnnaShaleva]

@doubiliu, thank you for the reply, I see that the library you've provided can be used by dApp developers to generate circuit-specific randomness. However, let's clarify the last thing:

so you can directly use the data generated by eth

Do you mean that Neo project is not going to organize its own Trusted Setup Ceremony (phase1, Powers of Tau)? Do you mean that as a base for Phase 2 we can use the result of Phase 1 got from Ethereum project?

[doubiliu]

I mean compatible. The data generated in Phase 1 itself is common, and each project can use the same data generated in Phase 1. The only difference may be the size of the circuit to which the data fits. So this is a resource-intensive step, and a repetitive one. We can use already generated data such as zcash to use. Of course, if we don't trust them, we can be generated by neo, and the generated methods exist in the library.