Forem: yagnadeepxo

Polynomial Commitment using IPA(Inner Product Argument) explained to beginner.

yagnadeepxo — Wed, 23 Aug 2023 07:20:52 +0000

Introduction

The Inner Product Argument (IPA) is a cryptographic technique used to prove statements about the inner product "z," which is a scalar resulting from the dot product of two vectors "a" and "b" without revealing the actual vectors.

Inner product/dot product is a.b = z

There are different variants of IPA, the main focus of this blog is where the "a" is a secret vector.

IPA for polynomial commitments

Inner product arguments can serve as a valuable tool for polynomial commitments. To provide a brief introduction to polynomial commitment, it involves the prover committing to a polynomial and subsequently proving to the verifier the polynomial's behaviour at various points, all without actually disclosing the polynomial itself.

Now let's say there is a polynomial f with coefficients which can be converted to a vector.

Vector f:

f = (f₀, f₁, ..., fₙ)

Function f(x):

f(x) = f₀ + f₁x + f₂x² + ... + fₙxⁿ

Notice: the inner product.

f(s) = ⟨f, (1, s, s², ..., sⁿ)⟩

Before diving into the main setup, it's essential to grasp the concept of Pedersen commitment.

Pedersen commitment allows us to commit to a value "x" by multiplying it with a point "G," where "G" is a point on an elliptic curve with an unknown discrete log.

The commitment of "x" is represented as "x⋅G" (which means "x" multiplied with point "G").

The Pedersen commitment used in this blog possesses the properties of both binding and non-hiding.

Binding indicates that once a commitment is made to a value, it can't be revealed as a different value.

Non-hiding implies that the value "x" itself isn't hidden; it's just a part of the commitment.

Setup(1st Iteration)

In our protocol, the prover holds a secret vector(polynomial coefficients) a = (a₁, a₂, a₃, a₄), known only to them. The rest of the parameters are shared knowledge:

G = (G₁, G₂, G₃, G₄): A basis used for Pedersen hashing.
A = ⟨a, G⟩: A commitment to vector a.
b = (b₁, b₂, b₃, b₄): Powers of value "s," where b = (1, s, s², s³).
Inner product result z = ⟨a,b⟩

After receiving the proof of opening in the first iteration, the verifier sends a random value x to the prover. This x is then used by the prover in the second iteration to reduce the proof size. The size of the proof is reduced by O(log(n)) in each iteration, where n is the size of the vector.

The problem

Sending large commitment data in every interaction with the verifier can be highly inefficient. The Inner Product Argument (IPA) presents an elegant solution by enabling a prover to commit to a vector, progressively reducing its size through proofs, all while ensuring its connection to the original vector remains validated.

Reduced Problem (2nd Iteration)

a' = x⁻¹(a₁a₂) + x(a₃a₄)
b' = x(b₁b₂) + x⁻¹(b₃b₄)
G' = x(G₁G₂) + x⁻¹(G₃G₄)
⟨a',b'⟩ = z' (reduced problem)

now we need 2 things:

a proof that proving above statement is the same as proving the previous statement ⟨a.b⟩ = z
a way for the verifier to compute z', b' and A'(commitment of a') by themselves.

The Proof

A' = ⟨a',G'⟩
= (x⁻¹a₁ + xa₃)(xG₁ + x⁻¹G₃) + (x⁻¹a₂ + xa₄)(xG₂ + x⁻¹G₄)
= A + x⁻²(a₁G₃ + a₂G₄) + x²(a₃G₁ + a₄G₂)
= A + x⁻²La + x²Ra

So to compute this new commitment, the verifier needs:

A (previous commitment) which they already have
La and Ra, points on the curve
some powers of x

now we also have to calculate z'

z' = ⟨a',b'⟩
= ⟨(x⁻¹a₁ + xa₃, x⁻¹a₂ + xa₄), (xb₁ + x⁻¹b₃, xb₂ + x⁻¹b₄)⟩
=(a₁b₁ + a₂b₂ + a₃b₃ + a₄b₄) + x⁻²(a₁b₃ + a₂b₄)+ x²(a₃b₁ + a₄b₂)
z' = z + x⁻²(Lz) + x²(Rz)

Now the total proof to send to the verifier in the 2nd iteration is

a' (half of a)
La and Ra, points on the curve
Lz and Rz, some scalar values

Summary

The prover's first commitment is to the full secret vector.
To reduce the vector size, the prover splits the vector into two halves.
They create a new commitment to just one half vector.
But this new commitment is not independent - it is computed in a way that cryptographically links it to the previous full commitment.
Specifically, the new commitment includes a randomness term derived from the randomness of the original commitment.
This creates a mathematical dependency between the commitments in the chain.
After log2(n) rounds, the vector size is reduced down to just 1 element.

Stealth in Science: Leveraging Zero-Knowledge Proofs to Safeguard Drug Design Intellectual Property

yagnadeepxo — Sat, 01 Jul 2023 08:25:16 +0000

In this blog, we'll explore how the intellectual property (IP) of drugs is protected while also making sure they are safe for use.

We use a cryptographic protocol called zkSNARK. In case if you aren't aware of it, Intro to ZK

Imagine this scenario: a drug's safety depends on certain secret parameters known only to the designer. However, the designer faces a challenge—they must demonstrate the drug's safety without divulging these confidential details.

vaccines may have specific chemical parameters that need to be considered to ensure human safety. These parameters can include:

Adjuvants:
Aluminum salts (e.g., aluminum hydroxide, aluminum phosphate) used as adjuvants in vaccines typically have a concentration range of 0.2-1.25 milligrams per milliliter (mg/mL) or as per specific regulatory requirements.

Preservatives:
Thimerosal, a mercury-containing compound used as a preservative in some vaccines, has a typical concentration range of 0.01-0.5 milligrams per milliliter (mg/mL) or as per specific regulatory requirements. It's worth noting that thimerosal-free vaccine formulations are also available for most vaccines.

Stabilizers:
The concentration of stabilizers used in vaccines can vary depending on the specific substance. Common stabilizers such as sugars (e.g., sucrose) and proteins (e.g., human serum albumin) can be present in the range of 0.1-5% w/v (weight/volume) or as per specific requirements.

Excipients:
Excipients in vaccines can have various concentration limits depending on their nature and purpose. For example, the concentration of certain excipients like sodium chloride (salt) may range from 0.5-9 milligrams per milliliter (mg/mL), while others may have different limits based on their specific role in the vaccine formulation.

The problem here is while generating cryptographic proofs we cannot give float datatype values to the circuit, because cryptographic circuit uses modular math.
The solution for this is we can convert the float values to integers by multiplying specific scalar value (ex: 100, 1000).

Now let's design the circuit.

The circuit design involves checking the values of the parameters and determining if the values lie within the permitted range. If yes the circuit gives out 1(true), else 0(false),this will be the witness.

pragma circom 2.1.5;
include "../node_modules/circomlib/circuits/comparators.circom";
template VaccineParamsCheck() {
    signal input preservative;
    signal input adjuvant;
    signal input stabilizer;
    signal input excipient;
    signal output isValid;

    signal preservative_valid;
    signal adjuvant_valid;
    signal stabilizer_valid;
    signal excipient_valid;

    component LT1 = LessThan(10);
    component GT1 = GreaterThan(10);

    component LT2 = LessThan(10);
    component GT2 = GreaterThan(10);

    component LT3 = LessThan(12);
    component GT3 = GreaterThan(12);

    component LT4 = LessThan(12);
    component GT4 = GreaterThan(12);

    LT1.in[0] <== preservative;
    LT1.in[1] <== 50;

    GT1.in[0] <== preservative;
    GT1.in[1] <== 1;

    preservative_valid <== LT1.out*GT1.out;

    LT2.in[0] <== adjuvant;
    LT2.in[1] <== 125;

    GT2.in[0] <== adjuvant;
    GT2.in[1] <== 20;

    adjuvant_valid <== LT2.out*GT2.out;

    LT3.in[0] <== stabilizer;
    LT3.in[1] <== 500;

    GT3.in[0] <== stabilizer;
    GT3.in[1] <== 10;

    stabilizer_valid <== LT3.out*GT3.out;

    LT4.in[0] <== excipient;
    LT4.in[1] <== 900;

    GT4.in[0] <== excipient;
    GT4.in[1] <== 50;

    excipient_valid <== LT4.out*GT4.out;

     signal int1 <== preservative_valid*adjuvant_valid;
     signal int2 <== stabilizer_valid*adjuvant_valid;

    isValid <== int1*int2;

}
component main = VaccineParamsCheck();

The provided code represents a vaccine parameter checking mechanism. It ensures that specific parameters of a vaccine, such as preservative, adjuvant, stabilizer, and excipient, fall within acceptable ranges without revealing the actual values. The goal is to verify if the vaccine parameters are safe for human use without disclosing sensitive information.

The code uses templates and components to compare the input values with predefined thresholds. It employs comparators like LessThan and GreaterThan to evaluate if each parameter is within the desired range.The cryptographic circuit can perform checks only in a certian way so the compartor components are used from circomlib

template LessThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;

    component n2b = Num2Bits(n+1);

    n2b.in <== in[0]+ (1<<n) - in[1];

    out <== 1-n2b.out[n];
}

template GreaterThan(n) {
    signal input in[2];
    signal output out;

    component lt = LessThan(n);

    lt.in[0] <== in[1];
    lt.in[1] <== in[0];
    lt.out ==> out;
}

The signals preservative_valid, adjuvant_valid, stabilizer_valid, and excipient_valid indicate whether each respective parameter passes the validity check.

The code also performs logical operations to combine the validity results of different parameters. The signals int1 and int2 represent intermediate checks, and isValid is the final output determining if the combination of parameters meets the safety criteria.

In conclusion, this blog provided an overview of a privacy-preserving mechanism for checking vaccine parameters. By utilizing templates and components, the code allows the verification of essential parameters without disclosing sensitive information. This approach ensures that the vaccine's safety can be determined without revealing the exact values of the parameters.

Tornado Cash Hack: 1M $ vanished ⁉️

yagnadeepxo — Thu, 25 May 2023 11:45:07 +0000

On may 21-2023, attacker deployed malicious code which was able to withdraw 100,000 TORN tokens worth nearly 1M $.
Let's breakdown how the hacker was able to exploit.

The hacker proposed changes to the Tornado cash governance smart contract and provided with a legitimate code which the community accepted. But later the hacker removed the legitimate code and deployed malicious code to the same address which was approved by the community, but the community members were not aware of this code change and the hacker exploited.

Let's understand how the hacker was able to deploy the smart contract to the same address

The hacker created a root contract which deployes a deployer contract with the help of create2 opcode, the opcode is used to determine the address of the smart contract before deploying and the address of this contract is independent of nonce(no. of previous transactions made from the account).

The normal create opcode uses address of the deployer and nonce to create the address of the smart contract

contract_address = sha3(RLP(deployer address, nonce))

Deployer address and nonce is RLP(recursive length prefix) encoded and hashed.Here the contract address is dependent on the nonce, if the nonce is different the contract address is also different

create2 opcode is independent of nonce and uses salt(random hexadecimal) of user choice to compute the contract address.

contract address is calculated as

contract_address = sha3(0xFF, sender, salt, bytecode)

0xFF, a constant that prevents collisions with CREATE.
The sender’s own address.
salt(random value)
bytecode of root contract

so the deployer contract is deployed at 0xABC

after that with the help of the deployer contract the hacker deploys a legitimate governance contract to 0xFFF address using create opcode and now the nonce of the deployer contract is set to 1, because a transaction is made, now the commuunity members approved this contract and its address.

Now hacker deleted the deployer contract and legitimate contract. Later he deployed the deployer contract again with create2 opcode using root contract, so now the nonce of the deployer contract is again set to 0 and deployed at the same address(0xABC).

With the help of the deployer contract the hacker deployed malicious contract to the approved address(0xFFF).

The malicious contract had functionalities where it was able to grant the hacker 1,200,000 votes and got access to the withdraw function of the Tornado cash smart contract and was able to withdraw the funds using delegate call

Delegatecall is a low-level function in Solidity that allows a contract to call another contract's function, but with the context of the original contract. This means that the original contract's storage, msg.sender, and msg.value are used when the called contract is executed.

Let's take an example of how delegate call can be used to withdraw funds from other contract

pragma solidity ^0.8.0;

contract Malicious {
    address payable public contractB;

    constructor(address payable _contractB) {
        contractB = _contractB;
    }

    function withdrawFromContractB() public {
        (bool success, ) = contractB.delegatecall(abi.encodeWithSignature("withdraw()"));
        require(success, "Withdraw failed");
    }
}

The malicious contract has a delegatecall which calls the withdraw function in the Tornado cash governance contract.

pragma solidity ^0.8.0;

contract Governance {
    address public owner;
    uint public balance = 10 ether;

    constructor() {
        owner = msg.sender;
    }

    function withdraw() external {
        require(msg.sender == owner, "Only the owner can withdraw");
        require(balance > 0, "Insufficient balance");

        uint amount = balance;
        balance = 0;
        payable(msg.sender).transfer(amount);
    }
}

The code used here is just for educational purpose.

In conclusion, the recent DeFi hack serves as a stark reminder of the risks and vulnerabilities that exist within the decentralized finance ecosystem. The breach not only resulted in a significant financial loss but also raised concerns about the security of smart contracts and the potential for exploitation.

The Tornado.Cash Revolution: Taking Back Control of Your Financial Privacy

yagnadeepxo — Fri, 05 May 2023 19:23:02 +0000

A lot of buzz is happening around Tornado.Cash after the smart contract of the crypto mixer is blacklisted by the US Authorities.
In this article let's make a technical breakdown of the working of Tornado.Cash.

Tornado.Cash according to the whitepaper:

Tornado.Cash implements an Ethereum zero-knowledge privacy solution: a smart contract that accepts
transactions in Ether (in future also in ERC-20 tokens) so that the amount can be later withdrawn with no reference to the original transaction.

Before understanding what Tornado.Cash is let's first understand what a crypto mixer is.

A crypto mixer is a tool used to make cryptocurrency transactions more anonymous by "mixing" them with other users' cryptocurrency.

Mixing in the context of cryptocurrency refers to the process of combining multiple cryptocurrency transactions into one, in order to obscure the original source and destination of the cryptocurrency.

If you look at the diagram, there are different ethereum addresses that are transferring exactly 1 ETH to the smart contract address of the Tornado.Cash and withdrawer can withdraw the 1 ETH deposited to a new ethereym address so that link between depositer and withdrawer is masked. Since all ethereum deposits are of the same amount, the privacy is even more improved.

This is a very high level overview

Now let's get into Technical details.
This involves 3 steps
1. Deposit Ether(or other ERC-20 token)
2. Mixing and Smart Contract Functionality.
3. Withdraw

DEPOSIT
while depositing the ether to the smart contract, the depositer should generate a secret(r) and a nullifier(k) both re 256 bits long and a commitment(c) is generated by hashing both nullfier and the secret using pedersen hashing algorithm.

c = pedersen(r||k)

Now we have the commitment and 1 ETH and the depositer is ready to send the data and ether to the Tornado.Cash smart contract.
It is advised to use TOR for enhaced privacy.
Deposit is succesfully completed.

Smart Contract Functionality
Smart contract implements a data structure called merkle tree.
If your not familiar with merkle trees then study here.
The height of merkle tree in the smart contract is 20,for now lets keep the height of the tree as 4 so there would be 8 leaves.
and each level of the tree has a level defualt, which are random BigNumbers.

uint256[10] levelDefaults = [
        23183772226880328093887215408966704399401918833188238128725944610428185466379,
        24000819369602093814416139508614852491908395579435466932859056804037806454973,
        90767735163385213280029221395007952082767922246267858237072012090673396196740,
        36838446922933702266161394000006956756061899673576454513992013853093276527813

    ];

Each leaf of the merkle tree would store a single commitment hash which depositer send and a corresponding merkle root is calculated.

The merkle root is calculated using the commitment and the corresponding level defaults by feeding it into MIMC hashing algorithm.

The green coloured nodes are the sister nodes(R) which are emitted by the smart contract after successful deposit to reconstruct the merkle root during the withdraw process.

Once the deposit function is successful the merkle root for the given commitment is marked TRUE.

WITHDRAW

Withdraw can be done by the depositer itself or any other person who has valid proof to prove that there is some ether on the contract associated with that proof.

To withdraw the Ether the withdrawer should send the required proof.

withdrawer needs to first calculate the nullifierHash, which is the pedersen hash of the nullifier(k).

nullifierHash = pedersen(k)

Now the withdrawer has to create a zero-knowlege proof, proving to the smart contract that he owns a certain commitment in the merkle tree without revealing the which commitment it is.
If you are not familiar with zero-knowledge proof check out my profile.

D = (dp, dv) be the ZK-SNARK proving-verifying key pair created using some trusted setup procedure.

ZKProof = groth16(k,s,R,Ri*,A)

K = nullifier
s = secret
R = sister nodes
Ri* = merkle root
A = new withdrwal Address

the withdrawer needs to send the ZKProof, and some public variables( nullifierHash, Ri*, A) to the smart contract for verification.

If the verification is successful the nullifierHash is added to the smart contract mapping and marked true which means the nullifierHash for the corresponding commitment is already spent which prevents double spending.

After successful verification the 1 ETH is transferred to new withdrawl address and some gas fees(f) is deducted.

This is basic understanding of the TornadoCash.

The Beginner's Guide to ZK-Snark: Setting Up Your First Proof System

yagnadeepxo — Wed, 26 Apr 2023 14:39:07 +0000

This Blog will guide you on building your first zero knowledge proof and a verification system to verify it.
If you are not aware of what zero knowledge proofs(zkp) are, then check introduction to zkp.

Aim of this blog is to create a zkp system that allows prover to prove to verifier that he knows a pre-image of a hash wihtout actually revealing the pre-image.

workflow

Note: we are setting up a non interactive proof system.

There are three steps in creating a zkp system:
1) generate the proving and verification key
2) generating the proof
3) verifying the proof

FIRST STEP:
In this step we need a circuit and a secret value(λ).

A circuit in zero-knowledge proof is a program that specifies a calculation to be performed on some data inputs. The circuit is used by the prover to generate a proof that they have correctly performed the calculation, without revealing any information about the data inputs. The verifier can then use the proof to confirm that the computation was performed correctly, without learning anything about the data inputs.

These circuits can be complex made of logic gates like (AND, OR) but fortunately we have a programming language called CIRCOM which is DSL(Domain specific language) used to create aritmetic circuits.More about arithmetic circuits.

let' set up the environment to write the circuit and complete it

Pre-requisites.
1) nodejs
2) circom compiler (follow steps)

After successfully installing the dependencies we need to start a nodejs project.



npm init -y

now you need to install circomlib(v2.0.5) to use certain predefined circuits.



npm install circomlib

Now create a file named circuit.circom and write the following code.



pragma circom 2.0.0;

include "node_modules/circomlib/circuits/pedersen.circom";

template Hasher(){
    signal input secret;
    signal output out;

    component pedersen = Pedersen(1);
    pedersen.in[0] <== secret;
    out <== pedersen.out[0];
}

component main = Hasher();

The program defines a template called "Hasher" which takes an input signal called "secret" and outputs a signal called "out". It uses a component called "Pedersen" which is included from the circomlib library, and sets it up to use 1 input.
The code then connects the "secret" input to the first input of the "Pedersen" component, and the output of the "Pedersen" component to the "out" output of the template.
Finally, the program defines a component called "main" which is an instance of the "Hasher" template.
Overall, this program creates a circuit that takes a secret input, hashes it using the Pedersen hashing function, and outputs the resulting hash.

we need to compile the circuit and get the low level represetation of the circuit.



circom circuit.circom --r1cs --wasm

after compiling we get 2 files(circuit.r1cs, circuit.wasm). r1cs(rank 1 constraint system), In simple terms, it is a way to express any computation as a set of linear equations that satisfy certain constraints. These constraints can be thought of as rules that define the inputs and outputs of the computation. We also get a wasm binary(web assembly).

Now one part of step one is completed i.e we have a circuit and now we need a secret value(λ).
This secret value is generated with the help of a ceremony called as trusted setup.

Trusted setup is a process used in some zero knowledge proof systems to generate the initial proving and verifying keys required for generating and verifying proofs. The purpose of trusted setup is to establish a secure foundation for the system by generating these keys in a way that ensures they are unpredictable and unbiased. This is typically done by having a group of trusted individuals generate the keys together, with each individual contributing a piece of random data. Once all the pieces are combined and processed using cryptographic techniques, the resulting keys can be used to generate and verify proofs without the need for any additional trust assumptions. The goal of trusted setup is to ensure that the system is secure and trustworthy, even if some of the participants in the trusted setup process are malicious.

the file generated during trusted setup process is called a ptau file(powers of tau). We already have a generated ptau file(only for testing purpose).



wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_12.ptau

Now we have the circuit and ptau file to generate the proving and verification keys (zkey file).

before that we need to install snarkjs

snarkJS is a JavaScript library for zk-SNARK proof generation and verification.



npm install snarkjs

After successfully installing the files now we need to generate the keys.



npx snarkjs groth16 setup circuit.r1cs powersOfTau28_hez_final_12.ptau circuit_0000.zkey

Groth16 is a type of zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) proof system used for generating and verifying proofs of computation. It is named after its creator, Jens Groth.

circuit_0000.zkey is a binary file that contains the proving and verification keys.

First step is successfully completed 🎉

SECOND STEP
In this step we need to generate proof.

create an index.js file and run the following code



const snarkjs = require('snarkjs')

async function generateProof(){
const { proof, publicSignals } = await snarkjs.groth16.fullProve(
    { secret: 12345 }, 
    "circuit_js/circuit.wasm", 
    "circuit_0000.zkey");
  console.log(publicSignals);
  console.log(proof);
}

generateProof()

generateProof().then(() => {
    process.exit(0);
});

output should look like this.



[
  '5470837527801859476637479809685048117954687279553045117433714472916822705394'
]
{
  pi_a: [
    '705318533694831637201207114678172400618551110993861322781866568756555043874',
    '11516110700725150090242458771069054303979174691445387001497479659508896518046',
    '5596622138762287749906806880510123588992685037536757227047926354733627986895',
    '1'
  ],
  protocol: 'groth16',
  curve: 'bn128'
}

Proof(π) is successfully generated and now we need to generate the verification key from the proving key(circuit_0000.zkey).

Proving key is like private key and verification key is like public key(In context of assymetric key cryptography)

generate verification key



npx snarkjs zkey export verificationkey circuit_0000.zkey verification_key.json

now we have successfully completed step 2 🎉

STEP 3
Verifying the Proof(π) which is generated in step 2.

Note: We can write code to verify the proof on a normal backend or we can also do on-chain verification with the help of smart contract.

let's create web2 backend verification system first.

create a verify.js file



const snarkjs = require('snarkjs')
const fs = require("fs");

async function verify(){
const { proof, publicSignals } = await snarkjs.groth16.fullProve(
    { secret: 12345 }, 
    "circuit_js/circuit.wasm", 
    "circuit_0000.zkey");


    const vKey = JSON.parse(fs.readFileSync("verification_key.json"));
    const res = await snarkjs.groth16.verify(vKey, publicSignals, proof);
      if (res === true) {
        console.log("Verification OK");
      } else {
        console.log("Invalid proof");
      }
}
verify()

verify().then(() => {
    process.exit(0);
});

output:
Verification OK

Congratulations you have completed all the 3 steps 🎉

For detailed explanation of on-chain verification, check here

Unlocking Zero Knowledge Proofs: From Beginner to Advanced

yagnadeepxo — Sun, 09 Apr 2023 11:40:36 +0000

Zero Knowledge Proof(zkp): Where Proof Meets Privacy, and Trust Meets Efficiency.

Imagine There is a lock, and you want to prove to a verifier that you have the keys to that lock. You ask the verifier to give you the lock and then you go into a dark room where the verifier cannot see what you're doing. Inside the dark room, you use the keys to open the lock, put a ring inside, and then lock it back. Finally, you send the locked lock with the ring inside back to the verifier. This way, the verifier can be sure that you have the keys to that lock, as you were able to open and lock it in the dark room without revealing the keys or the ring to the verifier. This is a simple analogy that illustrates the concept of Zero Knowledge Proofs, where you can prove ownership or knowledge of something without revealing the actual information.

Mathematics behind Interactive zk proof.

The discrete logarithm problem (DLP) is a commonly used mathematical problem in interactive zero-knowledge proofs (ZKPs). Here's a simplified description of how DLP is used in an interactive ZKP:

Statement: The prover wants to prove possession of a secret value x, such that

y = g^x mod p

where g is a known generator of a cyclic group of order p, and y is a known value.

Challenge-Response Phase:

The verifier challenges the prover with a randomly chosen value, typically represented as c.
The prover responds with a new value, typically represented as r, computed using the initial statement, the challenge c, and some random values. The response is computed as

z = (x + cr) mod (p-1).

Verification Phase:

The verifier checks if the response z satisfies the equation

y^c * g^r mod p = g^z mod p.

If the equation is satisfied, the verifier is convinced that the prover possesses the knowledge of the secret value x as claimed in the statement.
Iterative Process: If the verifier is not satisfied, the challenge-response phase can be repeated multiple times to increase the security of the proof.

The DLP is used in the challenge-response phase to create a response value that is computationally difficult for anyone else, including the verifier, to compute without knowing the secret value x. The verification phase then checks if the response value satisfies the equation based on the initial statement, challenge, and response. This ensures that the prover possesses the knowledge of the secret value x without revealing it to the verifier, making it a powerful technique for constructing interactive zero-knowledge proofs.

However, this method can be inefficient as it requires multiple interactions between the verifier and the prover. Fortunately, there are more efficient ZKP techniques, such as non-interactive Zero Knowledge Proofs (NIZKPs), where the prover can generate a proof without needing additional interactions with the verifier. This allows for more streamlined and efficient proofs of knowledge while maintaining the confidentiality of sensitive information.

Introduction to zkSNARK(zero knowledge Succinct Non-Interactive Arguments of Knowledge

Interactive ZK proofs are like a conversation, where the prover and verifier exchange information and interact multiple times. Non-interactive ZK proofs are like a monologue, where the prover shares a single proof that the verifier can verify without further interaction.

Asymmetric key cryptography underpins zkSNARK by providing the foundation for generating and verifying proofs. It involves a pair of keys - public and private - used by the prover and verifier to generate and verify SNARK proofs, similar to how digital signatures are used in asymmetric key cryptography for authenticity verification of messages.

Now here is a breakdown of SNARK.

Succinct: The proof generated by SNARK is short and concise, requiring minimal computational resources to verify.

Non-Interactive: The proof can be verified without further interaction with the prover, making it efficient and suitable for various applications.

Argument: The proof is a mathematical argument that attests to the validity of a statement, without revealing any underlying data.

Knowledge: The proof demonstrates that the prover possesses certain information or knowledge, without disclosing the details of that information.

Let's understand the workflow of SNARKS

It consists of 3 algorithms:

1)Generate the proving and verifying keys (Setup)

The Setup algorithm generates two keys: the proving key (“pk”) and verification key (“vk”).

(pk,vk) = setup(circuit(C), secret(λ))

In the context of zkSNARKs, a "circuit" refers to a specific computation that is represented in a formalized way using logical gates, similar to how a digital circuit is represented using gates like AND, OR, and NOT. The circuit defines the behavior of the computation that we want to prove knowledge of without revealing any secrets.

A trusted ceremony is a process in which a group of trusted individuals or entities collaboratively generate the initial parameters for a zkSNARK system in a secure and controlled environment. The parameters generated ("Secret")i n the trusted ceremony are used to create the proving key and verification key, which are used for generating and verifying proofs in zkSNARKs.

*2)Proof Generation (π) *
The prove algorithm is responsible for generating the zero-knowledge proof. It takes as inputs the proving key (“pk”), the private witness “w” and a public value “x” to generate the proof.

Witness "w" is the secret you as a prover know and not reveal it to the verifier and public value "x" is used to verify the proof(π) generated with the witness.

proof = Prove(pk,x,w)

*3)verify *
The verify algorithm takes in the proof, the public value "x" and the verification key(vk) and return true or false.

V(vk, x, π) = true

If the equation is true, then the proof is valid, and the verifier is convinced that the prover possesses the knowledge of the secret witness "w" without revealing it.

This is a very high level overview of zkSNARK.

There are several real-world applications that utilize zkSNARK

Cryptocurrencies: zkSNARKs are used in some blockchain protocols, such as Zcash and Horizen, to provide private and anonymous transactions without revealing the sender, receiver, or transaction amount.

Identity and Access Management: zkSNARKs can be used for secure and privacy-preserving identity verification, authentication, and access control, allowing users to prove their identity without revealing any personal information.

In conclusion, zkSNARKs unlock the power of zero-knowledge proofs, allowing for secure and private interactions in various fields, from cryptocurrencies to supply chain management, healthcare to voting systems, and beyond. With zkSNARKs, secrets can be proven without revealing them, unlocking new possibilities for privacy-enhancing technologies. So, let's embrace the magic of zero-knowledge proofs and step into a world where trust is preserved, privacy is respected, and security is paramount. It's time to unlock the secrets with zkSNARKs and pave the way for a more secure and private future!