LogoLogo
  • WELCOME TO ALEPH ZERO
  • EXPLORE
    • About Aleph Zero
    • AlephBFT Consensus
    • The Economy of Aleph Zero
    • Where to Buy AZERO
    • Decentralized Governance on Aleph Zero
    • Ecosystem
    • Aleph Zero Foundation Treasury Management
    • Community
    • Glossary
    • Audit & Research Papers
  • USE
    • Wallets
    • Explorer
    • Ledger
    • Telegram Notifications
    • Aleph Zero Signer
      • General introduction
      • What does Signer do?
      • What are Sub-accounts and Sub-account paths?
      • Why is it critical to store your Secret Phrase in a safe place?
      • How to forget and restore accounts?
      • What are Networks?
      • What are Trusted apps?
    • Dashboard
      • Dashboard basics
      • Overview
    • Stake
      • Staking Basics
      • Staking Menu Overview
      • How to Start Staking with the Aleph Zero Dashboard
      • How to Start Staking With the Developer Wallet
      • How to start staking using Ledger hardware wallet
      • How to Change Nominations
      • How to Stop Staking
      • Staking Rewards
      • Validators
      • Commission and Foundation Nodes
      • Proxy Accounts
    • Validate
      • Validating Overview
      • Hardware requirements
      • Running an Aleph Node on Testnet
        • Downloading and running the node
        • Verifying your setup
        • Customizing your setup
        • Building and running from source [advanced]
          • Building from source
          • Set environment variables
          • Download DB snapshot
          • Running the binary
        • Appendix: Ports, addresses, validators, and archivists
      • Running an Aleph Node on Mainnet
        • Running the node
        • Building and running from source [advanced]
      • Setting your identity
      • Making the node validate
      • Securing your validator
      • Troubleshooting
      • Elections and Rewards Math
      • Testnet Validator Airdrop
      • Foundation Nomination Program
    • Using the EVM-layer
    • Governance
      • Token
      • Multisig Accounts
  • BUILD
    • Aleph Zero smart contracts basics
      • Setting up a Testnet account
      • Installing required tools
      • Creating your first contract
      • Deploying your contract to Aleph Zero Testnet
      • Extending your contract
    • Cross contract calls
      • Using references
      • Using dynamic calls
    • Migrating from Solidity
    • Writing e2e tests with ink-wrapper
    • Aleph Zero Signer integration
    • Front-end app: smart contract interaction
    • Security Course by Kudelski Security
      • ink! Developers Security Guideline
      • Lesson 1 - Getting started with ink!
      • Lesson 2 - Threat Assessment
      • Lesson 3 - Integer Overflow
      • Lesson 4 - Signed-integer
      • Lesson 5 - Role-Based Access Control
      • Lesson 6 - Address Validation
      • Lesson 7 - Smart Contract Control
    • Development on EVM-layer
  • PROTOCOL DETAILS
    • Shielder
      • Overview
      • Design against Bad Actors
      • Preliminaries - ZK-relations
      • Notes and Accounts
      • ZK-ID and Registrars
      • Anonymity Revokers
      • PoW Anonymity Revoking
      • Relayers
      • Deterministic Secret Management
      • SNARK-friendly Symmetric Encryption
      • SNARK-friendly Asymmetric Encryption
      • Cryptography
      • Token shortlist
      • User Wallet
      • Versioning
      • PoC
      • Version 0.1.0
      • Version 0.2.0
    • Common DEX
      • Common Whitepaper - Differences
      • Dutch Auctions
  • FAQ
  • Tutorials
    • Withdrawing coins from exchanges
      • How to withdraw your AZERO coins from KuCoin
      • How to withdraw your AZERO coins from MEXC Global
      • How to withdraw your AZERO coins from HTX
  • Setting up or restoring a wallet
    • How to set up or recover your AZERO account using Aleph Zero Signer
    • How to set up or recover your AZERO account using the official mainnet web wallet
    • How to set up or recover your AZERO account using Nova Wallet
    • How to set up or recover your AZERO account using SubWallet
    • How to set up or recover your AZERO account using Talisman
  • Staking
    • How to stake via a direct nomination using the Aleph Zero Dashboard
    • How to stake via a nomination pool using the Aleph Zero Dashboard
    • How to destroy a nomination pool via the Aleph Zero Dashboard
Powered by GitBook
On this page
  • ZK-relations
  • Mathematical description of R

Was this helpful?

  1. PROTOCOL DETAILS
  2. Shielder

Preliminaries - ZK-relations

PreviousDesign against Bad ActorsNextNotes and Accounts

Last updated 8 months ago

Was this helpful?

In the course of this documentation we often describe certain relations that are then proved using ZK-SNARKs. The purpose of this section is to explain how each such a description is structured and what each part of the description means.

Even though we typically don't reach such low-level details it is important to remember that every single input of a relation is a field element (think of the scalar field of the underlying pairing system, see Cryptography). In the code we denote the type of a scalar field element by Scalar. When designing constraints these low level details often ends up being crucial -- we want our constraints to be representable by small arithmetic circuits of the scalar field (in other words: to be "SNARK-friendly") for them to incur low complexity upon arithmetization. For more background we refer to any of the excellent resources on SNARKs that are available online, such as the MOOC

ZK-relations

We describe relations in boxes with structure as below:

relation R

inputs:
    - x_1
    - x_2
    - ...
    - x_n

witnesses:
    - w_1
    - w_2
    - ...
    - w_m 

constraints:
    1. C_1
    2. C_2
    3. ...
    4. C_r

If you are interested in the precise mathematical description of what this box means, we refer to Mathematical description of R below. If not, we will give some intuitions about what to expect to be listed in the 3 sections of the box:

Inputs

In this section we specify "public inputs" to the relation (we denote the vector of public inputs as x), i.e., inputs that the user does not have to keep secret and which are exposed on-chain. If this was a signature scheme than we would likely expose the public key in this section. Or we could expose an encrypted message in this section, or any piece of data that is necessary to input in the plain. In many cases hashes of some larger structures are exposed as inputs, this has two purposes:

  • Compression: the hash is smaller than the underlying, possibly large structure.

  • Privacy: the underlying data is often hashed with some random salt, in order for this to serve a role of a non-revealing commitment.

Witnesses

This section contains data w that is necessary for the prover to demonstrate that for a given input x the relation R(x) holds. Indeed, in typical implementation of the proving function would look like:

generate_proof(R, x, w)

thus would take as input a description of the relation R (perhaps as an arithmetic circuit), an input vector x and a "witness" w that allows the prover to generate all necessary values on the circuit that are required to generate the proof.

The reader might be tempted to think that w are inputs to the relation -- this intuition, while not wrong, might be confusing at times and lead to misconceptions in notation and in implementation. A better intuition to keep in mind is what's described in Mathematical description of R -- roughly speaking the only inputs to R are x but the remaining ones (that appear in the constraints) -- y can all be efficiently computed given the witness w.

Constraints

Example

relation R

inputs:
    - x_1
    - x_2
    - x_3

witnesses:
    - w_1

constraints:
    1. w_1 * w_1 = y_1
    2. y_1 <= x_1
    3. hash(x_2, y_1) = y_2
    4. hash(y_2) = x_3

Note that in the above:

  • All the variables y_1, y_2 can be computed efficiently given x and w . But without w it would not be possible to compute them.

  • The constraint y_1 <= x_1 is written in a high level language. On a low level to make this constraint representable as an arithmetic circuit new implicit variables must likely be introduced (the binary decomposition of y_1) and many arithmetic constraints, just to emulate this one high level constraint. In this case, the implicit variables don't show up as witnesses, but are still computable from y_1 and x, and thus from w and x.

Mathematical description of R

The constraints together define a binary predicate R(x) on public inputs (see below for technical details). The constraints are typically written as pseudocode in a high-level language but it's important to keep in mind that in the end they are supposed to be written as arithmetic circuits (or using a similar arithmetization). These constraints might often involve explicitly, or implicitly some other variables, not mentioned as inputs and/or witnesses. These should be thought of as bound by an existential quantifier ∃\exists∃.

Mathematically the above box describes a relation R(x)R(x)R(x) with x=(x1,x2,...,xn)x=(x_1, x_2, ..., x_n)x=(x1​,x2​,...,xn​). To define what R RR is, let us denote by y=(y1,...,yn′)y=(y_1, ..., y_{n'})y=(y1​,...,yn′​) the vector of all variables besides xxx that appear in the formulas C1,...,CrC_1, ..., C_rC1​,...,Cr​, thus the formulas are really C1(x,y),C2(x,y),...,Cr(x,y)C_1(x, y), C_2(x, y), ..., C_r(x, y)C1​(x,y),C2​(x,y),...,Cr​(x,y) . Then RRR is defined to be:

R(x)=∃y(C1(x,y)∧C2(x,y)∧…∧Cr(x,y))R(x) = \exists_{y} (C_1(x, y) \wedge C_2(x, y) \wedge \ldots \wedge C_r(x, y))R(x)=∃y​(C1​(x,y)∧C2​(x,y)∧…∧Cr​(x,y))

Note that the witnesses www are not explicitly mentioned in the above. In particular not necessarily y=wy=wy=w -- typically this is not the case, it's only that www is a subset of variables in yyy. But more generally the intuition to keep in mind is that for a fixed x xx given and a "suitable witness" www it is possible to efficiently generate yyy which satisfies the below

C1(x,y)∧…∧Cr(x,y)C_1(x, y) \wedge \ldots \wedge C_r(x, y)C1​(x,y)∧…∧Cr​(x,y)

https://zk-learning.org/