Zokyo Auditing Tutorials
  • 🔐Zokyo Auditing Tutorials
  • 📚Tutorials
    • 🏃Tutorial 1: Front-Running
      • 🚀Prerequisites
      • 📘Understanding Front-Running
      • 👓Examples
      • ⚒️Mitigation Steps
      • 🏦Resource Bank to more front running examples
      • 🤝Front-Running Conclusion
    • 🧱Tutorial 2: Unsafe Casting
      • 🚀Prerequisites
      • 📘Understanding Casting
      • 👓Examples
      • 🤝Unsafe Casting Conclusion
    • 👍Tutorial 3: Approvals and Safe Approvals
      • 🚀Prerequisites
      • 📘Understanding Approvals
      • 👓Vulnerability Examples
        • 🔁ERC20 Approval Reset Requirement
        • 😴Ignoring Return Values from ERC20 approve() Function: Potential Miscount of Successful Approvals
        • 🚫Improper use of Open Zeppelins safeApprove() for Non-zero Allowance Increments
        • 🥾Omitted Approval for Contract Interactions Within a Protocol
        • 🤦‍♂️Failing to Reset Token Approvals in Case of Failed Transactions or other actions
        • 💭Miscellaneous
        • ERC20 Approve Race Condition Vulnerability
      • ⚒️Spot the Vulnerability
      • 🤝Approvals and Safe Approvals Conclusion
    • ⛓️Tutorial 4: Block.chainid, DOMAIN_SEPARATOR and EIP-2612 permit
      • 🚀Prerequisites
      • 📘Understanding Block.chainid and DOMAIN_SEPARATOR
      • 👓Examples
      • ⚒️General Mitigation Steps
      • 🤝Tutorial 4 Conclusion
  • 💰Tutorial 5: Fee-On-Transfer Tokens
    • 🚀Prerequisites
    • 📘Understanding Fee-On-Transfer
    • 👓Examples
    • 📘Links to more fee-on-transfer vulnerability examples
    • 🤝Fee-On-Transfer Tokens: Conclusion
  • 🌴Tutorial 6: Merkle Trees
    • 🚀Prerequisites
    • 📘Understanding Merkle Trees
    • 🔎Verification within a Merkle Tree:
    • 📜Merkle Proofs Within Smart Contracts
    • 🖋️Merkle Proof Solidity Implementation
    • 🛑Vulnerabilities When Using Merkle Trees
    • 💀Example Vulnerabilities
    • 🧠Exercise
    • 🤝Merkle Trees Conclusion
  • 🌳Tutorial 7: Merkle-Patricia Trees
    • 🚀Prerequisites
    • 📘Understanding Merkle-Patricia Trees
    • 📕Understanding Merkle-Patrica Trees pt.2
    • 🔎Verification within a Merkle-Patricia Tree
    • 🛑Vulnerabilities When Using Merkle-Patricia Trees
    • 💀Example Vulnerability
    • 🤝Merkle-Patricia Trees: Conclusion
  • 🔁Tutorial 8: Reentrancy
    • 🚀Prerequisites
    • 📘Understanding Reentrancy
    • ⚒️Mitigation
    • 💀The DAO Hack: An In-depth Examination
    • 👓Examples
    • 🏦Resource Bank To More Reentrancy Examples
    • 🤝Conclusion: Reflecting on the Reentrancy Vulnerability
  • 🔂Tutorial 9: Read-Only Reentrancy
    • 🚀Prerequisites
    • 📘Understanding Read-Only Reentrancy
    • 🔨Mitigating Read-Only Reentrancy
    • 👓Real World Examples
    • 🏦Resource Bank To More Reentrancy Examples
    • 🤝Read-Only Reentrancy: Conclusion
  • 🚆Tutorial 10: ERC20 transfer() and safeTransfer()
    • 🚀Prerequisites
    • 📘Understanding ERC20 transfer() and safeTransfer()
    • 👓Examples
    • 🤝Conclusion
  • 📞Tutorial 11: Low level .call(), .transfer() and .send()
    • 🚀Prerequisites
    • 📘Understanding .call, .transfer, and .send
    • 🛑Understanding the Vulnerabilities of .transfer and .send
    • 👓Examples
    • 🤝Low level .call(), .transfer() and .send() conclusion
  • ☎️Tutorial 12: Delegatecall Vulnerabilities in Precompiled Contracts
    • 🚀Prerequisites
    • 📳Understanding Delegatecall
    • ⛰️EVM, L2s, Bridges, and the Quest for Scalability
    • 🏗️Understanding Precompiles in the Ethereum Virtual Machine (EVM)
    • 💻Custom Precompiles
    • 💀Potential Vulnerabilities in EVM Implementations: Overlooked DelegateCall in Precompiled Contracts
    • 👓Real World Examples
    • 🤝Delegatecall and Precompiles: Conclusion
  • 🌊Tutorial 13: Liquid Staking
    • 🚀Prerequisites
    • 📘Understanding Liquid Staking
    • 💀Understanding Liquid Staking Vulnerabilities
    • 🛑Example Vulnerability
    • 🐜Example Vulnerability 2
    • 🕷️Example Vulnerability 3
    • 🤝Liquid Staking: Conclusion
  • 🚿Tutorial 14: Slippage
    • 🚀Prerequisites
    • 📘Understanding Slippage in Automated Market Makers (AMMs)
    • 💀Understanding the "Lack of Slippage Check" Vulnerability in Automated Market Makers (AMMs) and DEXs
    • 😡On-Chain Slippage Calculations Vulnerability
    • 📛0 slippage tolerance vulnerability
    • 👓Real World Examples
    • 🏦Resource bank to more slippage vulnerabilities
    • 🤝Slippage Conclusion
  • 📉Tutorial 15: Oracles
    • 🚀Prerequisites
    • 📘Understanding Oracles
    • 📈Types of price feeds
    • 😡Flash Loans
    • 💀Understanding Oracle Vulnerabilities
      • ⛓️The Danger of Single Oracle Dependence
      • ⬇️Using Deprecated Functions
      • ❌Lack of return data validation
      • 🕐Inconsistent or Absent Price Data Fetching/Updating Intervals
    • 🔫Decentralized Exchange (DEX) Price Oracles Vulnerabilities
    • 🛑Found Vulnerabilities In Oracle Implementations
      • ⚖️Newly Registered Assets Skew Consultation Results
      • ⚡Flash-Loan Oracle Manipulations
      • ⛓️Relying Only On Chainlink: PriceOracle Does Not Filter Price Feed Outliers
      • ✍️Not Validating Return Data e.g Chainlink: (lastestRoundData)
      • 🗯️Chainlink: Using latestAnswer instead of latestRoundData
      • 😭Reliance On Fetching Oracle Functionality
      • 🎱Wrong Assumption of 18 decimals
      • 🧀Stale Prices
      • 0️⃣Oracle Price Returning 0
      • 🛶TWAP Oracles
      • 😖Wrong Token Order In Return Value
      • 🏗️miscellaneous
    • 🤝Oracles: Conclusion
  • 🧠Tutorial 16: Zero Knowledge (ZK)
    • 🚀Prerequisites
    • 📚Theory
      • 🔌Circom
      • 💻Computation
      • 🛤️Arithmetic Circuits
      • 🚧Rank-1 Constraint System (R1CS)
      • ➗Quadratic Arithmetic Program
      • ✏️Linear Interactive Proof
      • ✨ZK-Snarks
    • 🤓Definitions and Essentials
      • 🔑Key
      • 😎Scalar Field Order
      • 🌳Incremental Merkle Tree
      • ✒️ECDSA signature
      • 📨Non-Interactive Proofs
      • 🏝️Fiat-Shamir transformation (or Fiat-Shamir heuristic)
      • 🪶Pedersen commitment
    • 💀Common Vulnerabilities in ZK Code
      • ⛓️Under-constrained Circuits
      • ❗Nondeterministic Circuits
      • 🌊Arithmetic Over/Under Flows
      • 🍂Mismatching Bit Lengths
      • 🌪️Unused Public Inputs Optimized Out
      • 🥶Frozen Heart: Forging of Zero Knowledge Proofs
      • 🚰Trusted Setup Leak
      • ⛔Assigned but not Constrained
    • 🐛Bugs In The Wild
      • 🌳Dark Forest v0.3: Missing Bit Length Check
      • 🔢BigInt: Missing Bit Length Check
      • 🚓Circom-Pairing: Missing Output Check Constraint
      • 🏹Semaphore: Missing Smart Contract Range Check
      • 🔫Zk-Kit: Missing Smart Contract Range Check
      • 🤖Aztec 2.0: Missing Bit Length Check / Nondeterministic Nullifier
      • ⏸️Aztec Plonk Verifier: 0 Bug
      • 🪂0xPARC StealthDrop: Nondeterministic Nullifier
      • 😨a16z ZkDrops: Missing Nullifier Range Check
      • 🤫MACI 1.0: Under-constrained Circuit
      • ❄️Bulletproofs Paper: Frozen Heart
      • 🏔️PlonK: Frozen Heart
      • 💤Zcash: Trusted Setup Leak
      • 🚨14. MiMC Hash: Assigned but not Constrained
      • 🚔PSE & Scroll zkEVM: Missing Overflow Constraint
      • ➡️PSE & Scroll zkEVM: Missing Constraint
      • 🤨Dusk Network: Missing Blinding Factors
      • 🌃EY Nightfall: Missing Nullifier Range Check
      • 🎆Summa: Unconstrained Constants Assignemnt
      • 📌Polygon zkEVM: Missing Remainder Constraint
    • 💿ZK Security Resources
  • 🤝Tutorial 17 DEX's (Decentralized Exchanges)
    • 🚀Prerequisites
    • 📚Understanding Decentralized Exchanges
    • 💀Common Vulnerabilities in DEX Code
      • 🔎The "Lack of Slippage Check" Vulnerability in Automated Market Makers (AMMs) a
      • 😡On-Chain Slippage Calculations Vulnerability
      • 📛Slippage tolerance vulnerability
      • 😵How Pool Implementation Mismatches Pose a Security Risk to Decentralized Exchanges (DEXs)
      • 🏊‍♂️Vulnerabilities in Initial Pool Creation - Liquidity Manipulation Attacks
      • 🛑Vulnerabilities In Oracle Implementations
        • ⚖️Newly Registered Assets Skew Consultation Results
        • ⚡Flash-Loan Oracle Manipulations
        • ⛓️Relying Only On Chainlink: PriceOracle Does Not Filter Price Feed Outliers
        • ✍️Not Validating Return Data e.g Chainlink: (lastestRoundData)
        • 🗯️Chainlink: Using latestAnswer instead of latestRoundData
        • 😭Reliance On Fetching Oracle Functionality
        • 🎱Wrong Assumption of 18 decimals
        • 🧀Stale Prices
        • 0️⃣Oracle Price Returning 0
        • 🛶TWAP Oracles
        • 😖Wrong Token Order In Return Value
        • 🏗️miscellaneous
      • 🥶Minting and Burning Liquidity Pool Tokens
      • 🎫Missing Checks
      • 🔞18 Decimal Assumption
        • 📌Understanding ERC20 Decimals
        • 💀Examples Of Vulnerabilities To Do With Assuming 18 Decimals
      • 🛣️Incorrect Swap Path
      • The Importance of Deadline Checks in Swaps
    • 🤝Conclusion
  • 🤖Tutorial 18: Proxies
    • 🚀Prerequisites
    • 📥Ethereum Storage and Memory
    • 📲Ethereum Calls and Delegate Calls
    • 💪Upgradability Patterns in Ethereum: Enhancing Smart Contracts Over Time
    • 🔝Proxy Upgrade Pattern in Ethereum
    • 🌀Exploring the Landscape of Ethereum Proxies
      • 🪞Transparent Proxies
      • ⬆️UUPS Proxies
      • 💡Beacon Proxies
      • 💎Diamond Proxies
  • 🔞Tutorial 19: 18 Decimal Assumption
    • 🚀Prerequisites
    • 📌Understanding ERC20 Decimals
    • 💀Examples Of Vulnerabilities To Do With Assuming 18 Decimals
    • 🤝Conclusion
  • ➗Tutorial 20: Arithmetic
    • 🚀Prerequisites
    • 🕳️Arithmetic pitfall 1: Division by 0
    • 🔪Arithmetic pitfall 2: Precision Loss Due To Rounding
    • 🥸Arithmetic pitfall 3: Erroneous Calculations
    • 🤝Conclusion
  • 🔁Tutorial 21: Unbounded Loops
    • 🚀Prerequisites
    • ⛽Gas Limit Vulnerability
    • 📨Transaction Failures Within Loops
    • 🤝Conclusion
  • 📔Tutorial 22: `isContract`
    • 🚀Prerequisites
    • 💀Understanding the 'isContract()` vulnerability
    • 🤝Conclusion
  • 💵Tutorial 23: Staking
    • 🚀Prerequisites
    • 💀First Depositor Inflation Attack in Staking Contracts
    • 🌪️Front-Running Rebase Attack (Stepwise Jump in Rewards)
    • ♨️Rugability of a Poorly Implemented recoverERC20 Function in Staking Contracts
    • 😠General Considerations for ERC777 Reentrancy Vulnerabilities
    • 🥏Vulnerability: _lpToken and Reward Token Confusion in Staking Contracts
    • 🌊Slippage Checks
    • 🌽The Harvest Functionality in Vaults: Issues and Best Practices
  • ⛓️Tutorial 24: Chain Re-org Vulnerability
    • 🚀Prerequisites
    • ♻️Chain Reorganization (Re-org) Vulnerability
    • 🧑‍⚖️Chain Re-org Vulnerability in Governance Voting Mechanisms
  • 🌉Tutorial 25: Cross Chain Bridges Vulnerabilities
    • 🚀Prerequisites
    • ♻️ERC777 Bridge Vulnerability: Reentrancy Attack in Token Accounting
      • 🛑Vulnerability: Withdrawals Can Be Locked Forever If Recipient Is a Contract
    • 👛The Dangers of Not Using SafeERC20 for Token Transfers
    • Uninitialized Variable Vulnerability in Upgradeable Smart Contracts
    • Unsafe External Calls and Their Vulnerabilities
    • Signature Replay Attacks in Cross-Chain Protocols
  • 🚰Tutorial 26: Integer Underflow and Overflow Vulnerabilities in Solidity (Before 0.8.0)
    • 🚀Prerequisites
    • 💀Understanding Integer Underflow and Overflow Vulnerabilities
    • 🤝Conclusion
  • 🥏Tutorial 27: OpenZeppelin Vulnerabilities
    • 🚀Prerequisites
    • 🛣️A Guide on Vulnerability Awareness and Management
      • 🤝Conclusion
  • 🖊️Tutorial 28: Signature Vulnerabilities / Replays
    • 🚀Prerequisites
    • 🔏Reusing EIP-712 Signatures in Private Sales
    • 🔁Replay Attacks on Failed Transactions
    • 📃Improper Token Validation in Permit Signature
  • 🤝Tutorial 29: Solmate Vulnerabilities
    • 🔏Lack of Code Size Check in Token Transfer Functions in Solmate
  • 🧱Tutorial 30: Inconsistent block lengths across chains
    • 🕛Incorrect Assumptions about Block Number in Multi-Chain Deployments
  • 💉Tutorial 31: NFT JSON and XSS injection
    • 📜Vulnerability: JSON Injection in tokenURI Functions
    • 📍Cross-Site Scripting (XSS) Vulnerability via SVG Construction in Smart Contracts
  • 🍃Tutorial 32: Merkle Leafs
    • 🖥️Misuse of Merkle Leaf Nodes
  • 0️Tutorial 33: Layer 0
    • 📩Lack of Force Resume in LayerZero Integrations
    • ⛽LayerZero-Specific Vulnerabilities in Airdropped Gas and Failure Handling
    • 🔓Understanding the Vulnerability of Blocking LayerZero Channels
    • 🖊️Copy of Understanding the Vulnerability of Blocking LayerZero Channels
  • ♻️Tutorial 34: Forgetting to Update the Global State in Smart Contracts
  • ‼️Tutorial 35: Wrong Function Signature
  • 🛑Tutorial 36: Handling Edge Cases of Banned Addresses in DeFi
  • Tutorial 37: initializer and onlyInitializing
  • ➗Tutorial 38: Eigen Layer
    • 📩Denial of Service in NodeDelegator Due to EigenLayer's maxPerDeposit Check
    • 📈Incorrect Share Issuance Due to Strategy Updates in EigenLayer Integrations
    • 🔁nonReentrant Vulnerability in EigenLayer Withdrawals
  • ⚫Tutorial 39: Wormhole
    • 📩Proposal Execution Failure Due to Guardian Set Change
  • 💼Tutorial 40: Uniswap V3
    • 📩Understanding and Mitigating Partial Swaps in Uniswap V3
    • 🌊Underflow Vulnerability in Uniswap V3 Position Fee Growth Calculations
    • ➗Handling Decimal Discrepancies in Uniswap V3 Price Calculations
  • 🔢Tutorial 41: Multiple Token Addresses in Proxied Tokens
    • 🔓Understanding Vulnerabilities Arising from Tokens with Multiple Entry Points
  • 🤖Tutorial 42: abiDecoder v2
    • 🥥Vulnerabilities from Manipulated Token Interactions Using ABI Decoding
  • ❓Tutorial 43: On-Chain Randomness
    • Vulnerabilities in On-Chain Randomness and How It Can Be Exploited
  • 😖Tutorial 44: Weird ERC20 Tokens
    • Weird Token List
  • 🔨Tutorial 45: Hardcoded stable coin values
  • ❤️Tutorial 46: The Risks of Chainlink Heartbeat Discrepancies in Smart Contracts
  • 👣Tutorial 47: The Risk of Forgetting a Withdrawal Mechanism in Smart Contracts
  • 💻Tutorial 48: Governance and Voting
    • Flash Loan Voting Exploit
    • Exploiting Self-Delegation
    • 💰Missing payable Keyword in Governance Execute Function
    • 👊Voting Multiple Times by Shifting Delegation
    • 🏑Missing Duplicate Veto Check
  • 📕Tutorial 49: Not Conforming To EIP standards
    • 💎Understanding EIP-2981: NFT Royalty Standard
    • 👍Improper Implementation of EIP-2612 Permit Standard
    • 🔁Vulnerabilities of Missing EIP-155 Replay Attack Protection
    • ➡️Vulnerabilities Due to Missing EIP-1967 in Proxy Contracts
    • 🔓Vulnerability of Design Preventing EIP-165 Extensibility
    • 🎟️The Dangers of Not Properly Implementing ERC-4626 in Yield Vaults
    • 🔁EIP-712 Implementation and Replay Attacks
  • ⏳Tutorial 50: Vesting
    • 🚔Vulnerability of Allowing Unauthorized Withdrawals in Vesting Contracts
    • 👊Vulnerability of Unbounded Timelock Loops in Vesting Contracts
    • ⬆️Vulnerability of Incorrect Linear Vesting Calculations
    • ⛳Missing hasStarted Modifier
    • 🔓Vulnerability in Bond Depositor's Vesting Period Reset
  • ⛽Tutorial 51: Ethereum's 63/64 Gas Rule
    • 🛢️Abusing Ethereum's 63/64 Gas Rule to Manipulate Contract Behavior
  • 📩Tutorial 52: NPM Dependency Confusion and Unclaimed Packages
    • 💎Exploiting Unclaimed NPM Packages and Scopes
  • 🎈Tutorial 53: Airdrops
    • 🛄Claiming on Behalf of Other Users
    • 🧲Repeated Airdrop Claims Vulnerability
    • 🍃Airdrop Vulnerability – Merkle Leaves and Parent Node Hash Collisions
  • 🎯Tutorial 54: Precision
    • 🎁Vulnerabilities Due to Insufficient Precision in Reward Calculations
    • Min-Shares: Fixed Minimum Share Values for Tokens with Low Decimal Precision
    • Vulnerability Due to Incorrect Rounding When the Numerator is Not a Multiple of the Denominator
    • Vulnerability from Small Deposits Being Rounded Down to Zero Shares in Smart Contracts
    • Precision Loss During Withdrawals from Vaults Can Block Token Transfers Due to Value < Amount
    • 18 Decimal Assumption Scaling: Loss of Precision in Asset Conversion Due to Incorrect Scaling
  • Tutorial 55: AssetIn == AssetOut, FromToken == ToToken
    • 🖼️Vulnerability: Missing fromToken != toToken Check
  • 🚿Tutorial 56: Vulnerabilities Related to LP Tokens Being the Same as Reward Tokens
    • 🖼️Vulnerabilities Caused by LP Tokens Being the Same as Reward Tokens
  • Tutorial 57: Unsanitized SWAP Paths and Arbitrary Contract Call Vulnerabilities
    • 📲Arbitrary Contract Calls from Unsanitized Paths
  • Tutorial 58: The Risk of Infinite Approvals and Arbitrary Contract Calls
    • 🪣Exploiting Infinite Approvals and Arbitrary Contract Calls
  • Tutorial 59: Low-Level Calls in Solidity Returning True for Non-Existent Contracts
    • Low-Level Calls Returning True for Non-Existent Contracts
  • 0️⃣Tutorial 60: The Impact of PUSH0 and the Shanghai Hardfork on Cross-Chain Deployments > 0.8.20
    • PUSH0 and Cross-Chain Compatibility Challenges
  • 🐍Tutorial 61: Vyper Vulnerable Versions
    • Vyper and the EVM
  • ⌨️Tutorial 62: Typos in Smart Contracts — The Silent Threat Leading to Interface Mismatch
    • Vyper and the EVM
  • ☁️Tutorial 63: Balance Check Using ==
    • The Vulnerability: == Balance Check
  • 💍Tutorial 64: Equal Royalties for Unequal NFTs
    • Understanding the Problem: Equal Royalties for Unequal NFTs
  • 🖼️Tutorial 65: ERC721 and NFTs
    • The Risk of Using transferFrom Instead of safeTransferFrom in ERC721 Projects
    • ❄️Why _safeMint Should Be Used Instead of _mint in ERC721 Projects
    • The Importance of Validating Token Types in Smart Contracts
    • 📬Implementing ERC721TokenReceiver to Handle ERC721 Safe Transfers
    • NFT Implementation Deviating from ERC721 Standard in Transfer Functions
    • NFT Approval Persistence after Transfer
    • 🎮Gameable NFT Launches through Pseudo-Randomness
    • 2️⃣Protecting Buyers from Losing Funds Due to Claimed NFT Rewards on Secondary Markets
    • ♻️Preventing Reentrancy When Using SafeERC721
    • 🖊️Preventing Re-use of EIP-712 Signatures in NFT Private Sales
  • 2️⃣Tutorial 66: Vulnerability Arising from NFTs Supporting Both ERC721 and ERC1155 Standards
  • 📷Tutorial 67: ERC1155 Vulnerabilities
    • ♻️Preventing Reentrancy in OpenZeppelin's SafeERC1155
    • 🛫Vulnerabilities in OpenZeppelin's ERC1155Supply Contract
    • Understanding Incorrect Token Owner Enumeration in ERC1155Enumerable
    • Avoiding Breaking ERC1155 Composability with Improper safeTransferFrom Implementation
    • 💍Ensuring Compatibility with EIP-2981 in ERC1155 Contracts
  • 🪟Informational Vulnerabilities
  • ⛽Gas Efficiency
  • 💻Automation Tools
  • 🔜Out Of Gas (Coming Soon)
  • 🔜DEX Aggregators (Coming Soon)
  • 🔜Bribes (Coming Soon)
  • 🔜Understanding Compiled Bytecode (coming soon)
  • 🔜Deployment Mistakes (coming soon)
  • 🔜Optimistic Roll-ups (coming soon)
  • 🔜Typos (coming soon)
  • 🔜Try-Catch (coming soon)
  • 🔜NFT Market-place (coming soon)
  • 🔜Upgrade-able Contracts (coming soon)
Powered by GitBook
On this page
  1. Tutorial 16: Zero Knowledge (ZK)
  2. Theory

Linear Interactive Proof

PreviousQuadratic Arithmetic ProgramNextZK-Snarks

Last updated 1 year ago

Linear Interactive Proof (LIP) from QAP: Once we have the Quadratic Arithmetic Program (QAP) represented by the equation

A(x)⋅B(x)−C(x)=Zd(x)⋅H(x), the next step in the zk-SNARK process is to transform this into a Linear Interactive Proof (LIP).

A Linear Interactive Proof is an interactive protocol where the verifier sends a random challenge to the prover, and in response, the prover sends back some values. The verifier then checks the validity of the proof using linear combinations of these values. It's called "linear" because the verifier's checks are linear operations on the prover's responses.

Here's a step-by-step process of the transformation:

Variables and Notations:

x: A generic variable that represents the polynomial's input.

s: A specific secret point chosen by the prover, where the polynomial will be evaluated. It's a concrete value in the field, but remains hidden from the verifier.

α: A challenge issued by the verifier to the prover during the interaction. It's used to form linear combinations of the polynomials.

Encoding the Witness:

The prover encodes their secret witness as the values of the polynomials

A(x), B(x), C(x), and H(x) at a secret point s, chosen randomly from the field over which the polynomials are defined.

Verifying Polynomial Evaluation:

At this stage, the prover must convince the verifier that they've correctly evaluated the polynomials

A(s), B(s), C(s), and H(s) without revealing the specific value of s or the polynomial evaluations at s.

Random Challenge:

As part of the interaction, the verifier sends a random value α to the prover. This challenge is not related to

x or s. It's a separate value used to ensure that the prover's responses aren't pre-computed and are based on this specific interaction.

The random challenge α serves an essential purpose in interactive proofs. Let's break down its role step by step:

Purpose of α:

The random challenge is meant to ensure that the prover isn't just providing pre-computed answers, but is actually responding based on the specific interaction and challenge presented by the verifier. This prevents a malicious prover from "faking" knowledge of a solution.

Usage of α in zk-SNARKs:

Given the original relation from the QAP:

A(x)⋅B(x)−C(x)=Z(x)⋅H(x)

The verifier asks the prover to provide a linear combination of the polynomials weighted by α. For example:

P(x)=A(x)+α⋅B(x)+α^2⋅C(x)

The prover will then evaluate this combined polynomial at the secret point s, resulting in P(s), and send this value to the verifier.

Why is this significant?:

By combining the polynomials in this manner, the prover demonstrates knowledge of each individual polynomial's evaluation at s without revealing the evaluations directly. If they didn't know the real evaluations, they wouldn't be able to correctly compute the combined polynomial's value at s.

The verifier, using properties of the QAP and the received combined evaluation, can then check if the prover's response is consistent with the relation. If the prover's response is correct, it indicates that the prover likely knows the correct evaluations A(s), B(s), C(s), and H(s), even though they haven't directly revealed them.

Given our original equation:

A(x)⋅B(x)−C(x)=Zd(x)⋅H(x)

The prover provides evaluations of the polynomials

A(s), B(s), C(s), and H(s) without directly revealing them.

Let's consider the linear combination created using α as the challenge:

P(x)=A(x)+α⋅B(x)+α^2⋅C(x)

The prover evaluates this combined polynomial at the secret point s and sends P(s) as the response.

Now, the verifier's role is to ensure that the given polynomial evaluations satisfy the original equation when combined in a manner dictated by the challenge α.

In the context of zk-SNARKs and the QAP, the key is the polynomial Zd(x). Recall that Zd(x) is the vanishing polynomial, which has roots that correspond to the domain of the original computation. The prover's secret point

s is one of the roots.Because of this, the verifier can utilize the properties of the vanishing polynomial

Zd(x). Specifically, the verifier can create their own version of a combined polynomial, incorporating Zd(x) and the challenge α, and then evaluate this polynomial at s. If the prover's response matches the verifier's expectation (while taking into account the evaluations

A(s), B(s), C(s), and H(s) in some obscured manner), it indicates the prover's claims are consistent with the relation.

A detailed example would require delving into the specific math behind the QAP, its domain, and how the values interplay. However, the high-level idea is that the challenge and the response mechanism ensures a prover who doesn't genuinely "know" the correct polynomial evaluations would have an astronomically small chance of correctly guessing the response for the randomly chosen challenge α.

The inclusion of H(x) in the equation essentially captures the "error" or difference in the evaluations. It represents the difference between the left-hand side and the right-hand side of the equation. So, when the prover provides H(s), they are effectively giving the verifier a way to check the consistency of the equation at the point s.

Knowledge of Zd(x):

Both the prover and verifier are aware of the vanishing polynomial Zd(x) since it is constructed based on the domain D of the system, which is public information. This polynomial is known to evaluate to 0 at specific points determined by D. However, the verifier does not have knowledge of how Zd(x) interacts with

H(x) in the prover's equations unless the prover reveals H(s).

The challenge-response interaction ensures that the prover must genuinely know the polynomials to generate valid responses. Coupled with the verifier's knowledge of certain public parameters and structures (like Zd(x)), it makes it computationally infeasible for a dishonest prover to deceive the verifier.

secret evaluation point

In zk-SNARKs, s (often referred to as the secret evaluation point) is indeed chosen randomly by the prover. The randomness of s ensures several things:

Privacy:

Since s is random, it acts as a one-time mask for the polynomial evaluations, ensuring that the actual evaluations A(s), B(s), C(s), and H(s) don't reveal any useful information about the witness (solution) to the verifier.

Soundness:

By evaluating the polynomials at a random point, the prover prevents the verifier from being able to "guess" or infer the polynomials based on a set of known evaluation points. It's a fundamental property of polynomials that given a polynomial of degree d, if you know its value at d+1 distinct points, you can determine the polynomial completely. By choosing a random s for each proof, the prover avoids giving the verifier enough information across multiple proofs to reconstruct the polynomial.

Zero-Knowledge:

The randomness of s plays a crucial role in ensuring the zero-knowledge property of the zk-SNARK. The verifier never learns s or the direct polynomial evaluations at s, so they gain no knowledge about the witness, other than that the prover possesses a valid one. While the point s is randomly selected for each proof, it remains fixed throughout the interaction between the prover and verifier for that particular proof. This means that the prover uses the same s to evaluate all their polynomials and generate their responses for a given proof session.

The secrecy of s

The secrecy of s (the secret evaluation point) is pivotal for the security and zero-knowledge properties of the protocol. Here are the reasons:

Zero-Knowledge:

One of the central properties of zk-SNARKs (and many other zero-knowledge proofs) is that the verifier learns nothing about the prover's secret witness, other than the fact that it exists. If s were known to the verifier, then the evaluations A(s), B(s), C(s), and H(s) would directly reveal information about the polynomials A(x), B(x), C(x), and H(x), which encode the secret witness. Keeping s secret ensures that the verifier learns nothing about these polynomials or the witness from the evaluations.

Soundness:

If s were publicly known, a dishonest prover could craft specific polynomials that evaluate correctly at

s but are incorrect elsewhere. This would enable the prover to potentially convince the verifier of a false statement. By keeping s secret and random, the prover is effectively "boxed in" and cannot specifically craft polynomials just for that s.

Replay Attacks:

If s were publicly known and constant across proofs, a dishonest verifier (or anyone eavesdropping on the protocol) could replay previous proofs or responses from the prover in future sessions to potentially extract information or cause other security issues.

Uniqueness:

A fresh, secret s ensures that every proof is unique, even if the prover is proving the same statement multiple times. This adds an additional layer of privacy and unpredictability to the proof.

In summary, the secrecy of s is not an arbitrary design choice but rather a foundational component to ensure the security, soundness, and zero-knowledge properties of the zk-SNARK protocol.

In essence:

The prover claims: "I know polynomials A(x), B(x), and C(x) that satisfy our equation, and I'll prove it without revealing these polynomials."

The prover does this by sending the evaluations at a secret point s.

The verifier checks these claims using its knowledge of Zd(s).

Multiple Rounds:

Sometimes, multiple rounds of challenges and responses are used to reduce the probability that a cheating prover can guess the correct responses. In each round, a new α is chosen, ensuring the prover isn't just getting "lucky" with their responses.

🧠
📚
✏️
Book an audit with Zokyo