Orochi Network

What is Orochi Network?

Orochi Network is a project that utilizes cryptography, especially Zero-Knowledge Proofs (ZKP) to build up an operating system (UnityOS) for the next generation of the internet.

UnityOS manages a pool of computation power. It allows High Performance Decentralized Applications to be hosted and processed without any centralized server. UnityOS runs in a server-less fashion with the underlying technology that can handle almost everything. Hence, the developers only need to focus on designing the logic of their dApps. This layer is built with distributed computing using zkWASM.

The dApps can be implemented by popular programming languages, e.g., C++, Rust, Go, etc, and processed with semi-native performance. Computation power will be allocated dynamically and thus, saves operational costs and computational waste.

Our Vision

At Orochi Network, we believe that Verifiable Computation is a essential cryptographic system to establish Web3 and Decentralized Autonomous Economy. However, in order to reach this stage, there are still a number of major challenges of this industry to overcome.

The limits of computation: EVM cannot guarantee semi-native performance, in addition to the extremely high cost and latency to perform computations. dApps nowadays are unstable, expensive, slow and unfriendly to the mass. In other words, they are currently unusable and we cannot replace an ordinary application by a dApp yet.
Data correctness: There is no way to prove the correctness of data since all data pipelines are stored in a blackbox. We have no idea how data are processed.
Data availability: That smart contract and application executors are isolated from the internet prevents data to be accessible from the run-time environment. One can require a third-party service to feed necessary data. This approach is broken since we cannot verify the data. Moreover, the latency from the third-party services is unacceptable.

What Are We Building Toward To That vision?

zkWASM: An Universal Verifiable WebAssembly Run-time

This is considered to be the core component of Orochi Network that provides semi-native executions and proves the computations in ZKPs. We booted this aspect with zkWASM specifications.

zkDatabase: A Verifiable Database

zkDatabase is a database that utilizes ZKPs to prove the correctness of the data and data processing. As far as we know, every zkApp needs to manage their own on-chain and off-chain state itself. This process is costly and inefficient depending on the complexity of data's structure. We want to provide other teams the most critical component, namely, the database, to build their zkApps.

Orand: A Decentralized Random Number Generator

We are conducting various research attempts around VRF and ECVRF to develop a solution for mass adoption of verifiable randomness. Verifiable randomness must be considered an essential primitive of Web3 gaming.

Orand is implemented as a core library of Orochimaru, a full-node client of Orochi Network.

We are also implementing the on-chain verification allowing the randomness to be verified without any third-party service. The verifier is implemented in Solidity and is EVM-compatible at the moment. In the future, we are planning to support other blockchains that support smart contracts.

Orosign: A Passport of Web3

A highly secured solution based on Multi-Party Computations (MPC) that helps you secure your digital assets and digital identities. The product is available on Apple Store and Google Play.

Orochi ❤️ Open Source

All projects are open-sourced and public. We build everything for common good.

Orand V1

Orand project was built based on Elliptic Curve Verifiable Random Function (ECVRF). It is deterministic, verifiable and secured based on assumptions from elliptic curves. Administrators of Orochi Network are unable to manipulate the results.

To optimize operation costs and improve security we provided following features:

Verifiable: An Orand's epoch can be verified independently outside our system or can be verified by smart contracts.
Hybrid Proof System: Our customers can choose between Fraud Proof or Validity Proof to feed the randomness.
Dual Proof: An ECDSA proof will be combined with an ECVRF proof to secure the feeding process, allowing it to be done by any third party while still guaranteeing the result to be verifiable and immutable.
Batching: We allow you to set the batching limit for one epoch, e.g., we can batch $1000$ randomness for one single epoch which makes the cost be reduced significantly.

Orand V2

Orand V2 will focus on utilizing Multi Party Computation (MPC) to secure the randomness generation, allowing the whole system to act as one random oracle. It makes the process more dispersed. In this stage, we boot up Chaos Theory Alliance to preventing predictability. Everything is built up toward to the vision of Decentralized Random Number Generator. If you believe in the vision of Decentralized Random Number Generator, please send drop us an email to ([email protected]) in order to participate in Chaos Theory Alliance.

Orochi Network SDK

Orochi Network SDK provides client-side tools that allow you to interact with the whole Orochi Network ecosystem. We supported browser and Node.js at the first place.

Installation

You can install Orochi Network sdk by running:

npm install @orochi-network/sdk

Please take note that @orochi-network/sdk requires es2018 to work as expected.

Usage

First you might need to import @orochi-network/sdk to your project

import { orand, IOrandEpoch } from "@orochi-network/sdk";

After you import the sdk, you can use our sdk in your project.

const orandInstance = new orand.Orand({
  url: "https://orand-test-service.orochi.network/",
  user: "YOUR_REGISTERED_USERNAME",
  secretKey: "YOUR_REGISTERED_HMAC_SECRET",
  consumerAddress: "YOUR_APPLICATION_SMART_CONTRACT_ADDRESS",
});

In the example above, we initiated an instance of Orand which provides verifiable randomness based on ECVRF.

To learn more about Orand integration please check next section.

Smart Contract Integration

Your smart contract that consumes Orand's randomness needs the interface of IOrandConsumerV1 to be implemented, which was described below:

// SPDX-License-Identifier: Apache-2.0
pragma solidity ^0.8.0;

error InvalidProvider();

interface IOrandConsumerV1 {
  function consumeRandomness(uint256 randomness) external returns (bool);
}

Dice Game Example

The game is quite easy. You roll the dice and Orand will give you the verifiable randomness so you can calculate the dice number.

// SPDX-License-Identifier: Apache-2.0
pragma solidity ^0.8.0;
import '@openzeppelin/contracts/access/Ownable.sol';
import '../interfaces/IOrandConsumerV1.sol';

error WrongGuessingValue(uint128 guessing);

// Application should be an implement of IOrandConsumerV1 interface
contract ExampleValidityProofDice is IOrandConsumerV1, Ownable {
  // Set new provider
  event SetProvider(address indexed oldProvider, address indexed newProvider);

  // Fulfill awaiting result
  event Fulfill(uint256 indexed gameId, uint256 guessed, uint256 indexed result);

  // New guess from player
  event NewGuess(address indexed player, uint256 indexed gameId, uint128 indexed guessed);

  // Adjust maximum batching
  event AdjustMaximumBatching(uint256 indexed maximum);

  // Game structure
  struct Game {
    uint128 guessed;
    uint128 result;
  }

  // Provider address
  address private orandProviderV1;

  // Game result storage
  mapping(uint256 => Game) private gameResult;

  // Total game
  uint256 private totalGame;

  // Fulfiled randomness
  uint256 private fulfilled;

  // We batching the radomness in one epoch
  uint256 private maximumBatching;

  // Only allow Orand to submit result
  modifier onlyOrandProviderV1() {
    if (msg.sender != orandProviderV1) {
      revert InvalidProvider();
    }
    _;
  }

  // Constructor
  constructor(address provider, uint256 limitBatching) {
    _setProvider(provider);
    _setBatching(limitBatching);
  }

  //=======================[  Internal  ]====================

  // Set provider
  function _setProvider(address provider) internal {
    emit SetProvider(orandProviderV1, provider);
    orandProviderV1 = provider;
  }

  // Set provider
  function _getProvider() internal view returns (address) {
    return orandProviderV1;
  }

  // Set max batching
  function _setBatching(uint256 maximum) internal {
    maximumBatching = maximum;
    emit AdjustMaximumBatching(maximum);
  }

  //=======================[  Owner  ]====================

  // Set provider
  function setProvider(address provider) external onlyOwner returns (bool) {
    _setProvider(provider);
    return true;
  }

  // Set provider
  function setMaximumBatching(uint256 maximum) external onlyOwner returns (bool) {
    _setBatching(maximum);
    return true;
  }

  //=======================[  OrandProviderV1  ]====================

  // Consume the result of Orand V1 with batching feature
  function consumeRandomness(uint256 randomness) external override onlyOrandProviderV1 returns (bool) {
    uint256 filling = fulfilled;
    uint256 processing = totalGame;

    // We keep batching < maximumBatching
    if (processing - filling > maximumBatching) {
      processing = filling + maximumBatching;
    } else {
      processing = totalGame;
    }

    // Starting batching
    for (; filling < processing; filling += 1) {
      gameResult[filling].result = uint128((randomness % 6) + 1);
      randomness = uint256(keccak256(abi.encodePacked(randomness)));
      emit Fulfill(filling, gameResult[filling].guessed, gameResult[filling].result);
    }

    fulfilled = filling - 1;
    return true;
  }

  //=======================[  External  ]====================

  // Player can guessing any number in range of 1-6
  function guessingDiceNumber(uint128 guessing) external returns (bool) {
    // Player only able to guessing between 1-6 since it's dice number
    if (guessing < 1 || guessing > 6) {
      revert WrongGuessingValue(guessing);
    }
    Game memory currentGame = Game({ guessed: guessing, result: 0 });
    gameResult[totalGame] = currentGame;
    emit NewGuess(msg.sender, totalGame, guessing);
    totalGame += 1;
    return true;
  }

  //=======================[  External View  ]====================

  // Get result from smart contract
  function getResult(uint256 gameId) external view returns (Game memory result) {
    return gameResult[gameId];
  }

  function getStateOfGame() external view returns (uint256 fulfill, uint256 total) {
    return (fulfilled, totalGame);
  }
}

In this example, the smart contract ExampleValidityProofDice was deployed at 0xF16F07cfd6e9Ac06925FCf68dD0b450f4131989D

The method consumeRandomness(uint256 randomness) should be restricted to OrandProviderV1. Here is its address on BNB Chain testnet 0x75C0e60Ca5771dd58627ac8c215661d0261D5D76

Orand Code Integration

Randomness Feeding Process

Your application can request the verifiable randomness directly from Orand. Then you can publish the randomness yourself by calling the method publishValidityProof() on smart contract OrandProviderV1. Higher tier of service establishes the ability to submit the randomness from Orand service but the deal will cover the cost for each randomness.

┌───────────┐         ┌─────┐      ┌──────────────┐
│Application│         │Orand│      │Smart Contract│
└─────┬─────┘         └──┬──┘      └──────┬───────┘
      │                  │                │
      │Request Randomness│                │
      │─────────────────>│                │
      │                  │                │
      │                  │Get latest epoch│
      │                  │───────────────>│
      │                  │                │
      │                  │  Latest epoch  │
      │                  │<───────────────│
      │                  │                │
      │   ECVRF Proof    │                │
      │<─────────────────│                │
      │                  │                │
      │            ECVRF Proof            │
      │──────────────────────────────────>│
┌─────┴─────┐         ┌──┴──┐      ┌──────┴───────┐
│Application│         │Orand│      │Smart Contract│
└───────────┘         └─────┘      └──────────────┘

Request Randomness From Orand

import {
  orand,
  IOrandEpoch,
  OrandProviderV1,
  abiOrandProviderV1,
} from "@orochi-network/sdk";
import { ethers } from "ethers";

(async () => {
  // Create an instance of Orand
  const orandInstance = new orand.Orand({
    url: "ORAND_SERVICE_URL",
    user: "ORAND_USER_NAME",
    secretKey: "ORAND_USER_HMAC_SECRET",
    consumerAddress: "ORAND_USER_CONSUMER_ADDRESS",
    chainId: 97,
  });
})();

ORAND_SERVICE_URL: We will provide you the service URL
ORAND_USER_NAME: The username that you registered with Orand service, e.g: "Navi"
ORAND_USER_HMAC_SECRET: The random secret key used to authenticate yourself, for instance, 6b1ab607287f5379db8b70bb7515feaa
ORAND_USER_CONSUMER_ADDRESS: The consumer smart contract address for instance, "0x66681298BBbdf30a0B3Ec98cAbf41AA7669dc201"

Note: ChainId is a predefined value, you can check the chain list here.

Submit The Randomness To Your Smart Contract

// Restore wallet from passphrase and connect it to JSON provider
let wallet = ethers.Wallet.fromPhrase(
  "YOUR_12_WORD_PASSPHRASE",
  new ethers.JsonRpcProvider("https://data-seed-prebsc-1-s1.binance.org:8545")
);

// Get epoch data from Orand
const data: IOrandEpoch = await orandInstance.newPrivateEpoch();

// Create an instance of OrandProviderV1
const orandProviderV1 = (<OrandProviderV1>(
  (<any>(
    new ethers.Contract(
      "0x75C0e60Ca5771dd58627ac8c215661d0261D5D76",
      abiOrandProviderV1
    )
  ))
)).connect(wallet);

// Convert Orand proof to smart contract proof
const [ecdsaProof, epoch] = orandInstance.transformProof(data);
console.log([ecdsaProof, epoch]);

// Publish the proof
await orandProviderV1.publishValidityProof(ecdsaProof, epoch);

Testing result of feeding 10 randomnesses to dice game contract https://testnet.bscscan.com/tx/0x55c21d5c93c7ad314d25d28f49d7c6dc129bbc47a4df1c10b62dcdf579c385f2.

Don't mind to contact us on Telegram if you need support https://t.me/OrochiNetwork.

API Reference

Initial

We assume that you have an initialized instance of Orand.

import { orand } from "@orochi-network/sdk";

const orandInstance = new orand.Orand({
  url: "https://orand-test-service.orochi.network/",
  user: "YOUR_REGISTERED_USERNAME",
  secretKey: "YOUR_REGISTERED_HMAC_SECRET",
  consumerAddress: "YOUR_APPLICATION_SMART_CONTRACT_ADDRESS",
  chaiId: 1,
});

Note:

To prevent replay attack, we're required you to input consumerAddress. It's a smart contract address that will consume the randomness. Each consumerAddress will have different epoch target, you only able to to submit the epoch which has the matched epoch with target epoch on OrandProviderV1 smart contract.

Some results will be returned in BigInt due to new update from ethers.js.

.getPublicEpoch()

await orandInstance.getPublicEpoch(0);

Allowed you to get a list of public epochs at the starting epoch, it will return an array of IOrandEpoch. The result will be limited to 20 records to prevent Denial of Service.

Public epoch has receiverAddress is 0x0000000000000000000000000000000000000000, submitting public epoch to OrandProviderV1 won't have any affect since the consumer address is 0x0000000000000000000000000000000000000000.

Result:

[
  {
    epoch: 0,
    alpha: '195ccc785b997579566fcac4367ee662fffba11f0d7c67d6df4cbbd318251fdd',
    gamma: '59c6bd805ff9b9e21fe7888d1a3a2672e02f950c58814e84d7537ada90c31a7bcf64410d775ec3de37280688c1021a23a32098b590abc3b73f630378fc42c053',
    c: 'b50167c3019820270b3708d3d586d212b4289d9b83d6b0f8350432045b8e9c4d',
    s: 'cc13dc051aeb7cbdcc3bb4e8bfc3e92b1ab254899d503ee20813f7f77c107f7d',
    y: '0a22386520c728455c84b21830ae0a21d56752dd27fe13ae129b0a04f599c0b2',
    witnessAddress: '0c2971ca2f70ca924d3bfb08b94677a6cf9ab068',
    witnessGamma: '8205aee30d8d3c8b9504c467f03b790ec7d7106125e45a8ee9e784f9670341d4429115d24958b64611f17c8d3a748951d27ce2a1c696da80c5edb56c78cf678a',
    witnessHash: '665a9bb45478fa3391bf6308f6752ddc152288d53e4ed393230746ff74504817d71850c87edd776494f053aaf5b3e39e34b5cb05fc468e8d29553faf0e38ea62',
    inverseZ: '60d0c2324755fd8f091c8fa690cd43899c94f0519958f8b85363d804d5f382e2',
    signatureProof: '14d0bdf7f9457321871bc68490d23f04e8d5b394f2b43a7534f2bc01fea694d576ec3c24667d31475cf31747fccc3e79eb70823f852a420dfbf191e3a863b6de1b00000000000000000000000000000000000000000000000000000000000000000a22386520c728455c84b21830ae0a21d56752dd27fe13ae129b0a04f599c0b2',
    createdDate: '2023-03-10 06:40:56'
  },
  {
    epoch: 1,
    alpha: '0a22386520c728455c84b21830ae0a21d56752dd27fe13ae129b0a04f599c0b2',
    gamma: '00e995ee0917b73aea5cbcee6b5583f20e67c80666749359a8c97aa25fea97f88c4fa15d5feffd7815edc9b867c99891f26407cd53c3ad1b20fcb81c913a35a9',
    c: '57f2d6461f1d05f7db5aca504c2b022e23854eeb638a47f56f32ca95730cf17b',
    s: '01b4315ddb662d6bf326b64739777f47dc9a4e1e9362f380a98f9f5a41013951',
    y: '08a5571c2c093c48c16c52dc0ec131a87073a5ff3ae75de354a5f7b66c5b5d8b',
    witnessAddress: 'cab1927ebecfb748f021deed4e0f54acee27dd62',
    witnessGamma: '896da8ba810f6c0412414773fa1012244f3fb0cb086702f78c4420622420ab3f71d7f20e9648c2cce7a65c57ae1f689555d15c357990e639be54a27aaa34e395',
    witnessHash: 'ea1af5c829afdc666c448e1f2aedc4e1fe024bd5a321303cc1f71bacd94558ff23035dbf54c820ec18e6fa371ec96a5f9f0d86493e1a3b08d2be767c3b389c02',
    inverseZ: 'ccc6ef8b4d4deee402c832cc85cc7ff12610dda57aa8a5ced90a05747f240d37',
    signatureProof: '3386c6ba69dd850fa799af07544332f8d45b431ba65f5db34c79345839c921764f89f53a8cb2652920c9495a76804a1b2aa11c01ade58b19c78ae6621f60feaa1b000000000000000000000001000000000000000000000000000000000000000008a5571c2c093c48c16c52dc0ec131a87073a5ff3ae75de354a5f7b66c5b5d8b',
    createdDate: '2023-03-10 06:40:58'
  }
]

.newPrivateEpoch()

await orandInstance.newPrivateEpoch();

Allowed you to generate a new private epoch that related to consumerAddress. The consumerAddress need to be registered on Orand V1 service.

Result:

{
  epoch: 3,
  alpha: 'c9677c0884f380b1facece540fb2674590c6b004207c72d3fa3f99c6699e2401',
  gamma: '8a3059cec8687c2d9d7048098a8484b0ebb8839d6589be070affac5a7763dd8e73a316231302534ea834e897835f610d61bc4dd8a2b75b71be35414b2fb2a2ea',
  c: '9345c77ac9c7c1ba6d084ccf6997e2fcf623dc9cdc72e42a91855b1c8cc1c5fa',
  s: '8457bc202e735627d5a27133744bf3bb0dd72fb5e85ce826d0716c107fd44430',
  y: '147c78180c05d041a9e8b3bb11cf59f1c871019db940532bd38df22f8194f28c',
  witnessAddress: '6dfb0007085713f2621380670e8578eb83df552b',
  witnessGamma: 'a191f86cff2b88e06b38c64e4d2ddfb3c0673b32c7e229bd46f6a2262a962f700765aba72c8d225133874d0f26327a6851a67946b2deb1d7c722d4836d4cd1f4',
  witnessHash: '0142eeaf5d41dad6a3b2f42f0a06ae8b17b47084c78bcd86f44693a264a9defb72a9b3ee2a3466810bb69e6360ca02f16b32f5f241ae7089651bc8f6a1f580c4',
  inverseZ: '77024d6c015a9b0cbe758246843d7d8712115abaac53f761a6e1594d240a8a02',
  signatureProof: '6f7e2c4eef8a3bbc0699971ab2d80693702356f1873d45b20829b50873943e8975f6f978d1daafc10c2c7ecda8bf3dda823485cfa7d17740398852423188f54c1b000000000000000000000003f16f07cfd6e9ac06925fcf68dd0b450f4131989d147c78180c05d041a9e8b3bb11cf59f1c871019db940532bd38df22f8194f28c',
  createdDate: '2023-03-10 06:56:08'
}

.getPrivateEpoch()

await orandInstance.getPrivateEpoch(3);

Allowed you to get a list of private epochs at the starting epoch, it will return an array of IOrandEpoch. The result will be limited to 20 records to prevent Denial of Service. These result will be bounded to receiverAddress.

Result:

[
  {
    epoch: 3,
    alpha: 'c9677c0884f380b1facece540fb2674590c6b004207c72d3fa3f99c6699e2401',
    gamma: '8a3059cec8687c2d9d7048098a8484b0ebb8839d6589be070affac5a7763dd8e73a316231302534ea834e897835f610d61bc4dd8a2b75b71be35414b2fb2a2ea',
    c: '9345c77ac9c7c1ba6d084ccf6997e2fcf623dc9cdc72e42a91855b1c8cc1c5fa',
    s: '8457bc202e735627d5a27133744bf3bb0dd72fb5e85ce826d0716c107fd44430',
    y: '147c78180c05d041a9e8b3bb11cf59f1c871019db940532bd38df22f8194f28c',
    witnessAddress: '6dfb0007085713f2621380670e8578eb83df552b',
    witnessGamma: 'a191f86cff2b88e06b38c64e4d2ddfb3c0673b32c7e229bd46f6a2262a962f700765aba72c8d225133874d0f26327a6851a67946b2deb1d7c722d4836d4cd1f4',
    witnessHash: '0142eeaf5d41dad6a3b2f42f0a06ae8b17b47084c78bcd86f44693a264a9defb72a9b3ee2a3466810bb69e6360ca02f16b32f5f241ae7089651bc8f6a1f580c4',
    inverseZ: '77024d6c015a9b0cbe758246843d7d8712115abaac53f761a6e1594d240a8a02',
    signatureProof: '6f7e2c4eef8a3bbc0699971ab2d80693702356f1873d45b20829b50873943e8975f6f978d1daafc10c2c7ecda8bf3dda823485cfa7d17740398852423188f54c1b000000000000000000000003f16f07cfd6e9ac06925fcf68dd0b450f4131989d147c78180c05d041a9e8b3bb11cf59f1c871019db940532bd38df22f8194f28c',
    createdDate: '2023-03-10 06:56:08'
  }
]

.verifyECDSAProof()

await orandInstance.verifyECDSAProof(epochData);

Allowed you to verify the ECDSA proof of any given epoch.

Result:

{
  signer: '0x7e9e03a453867a7046B0277f6cD72E1B59f67a0e',
  receiverEpoch: 2n,
  receiverAddress: '0xF16F07cfd6e9Ac06925FCf68dD0b450f4131989D',
  y: 91097723859136686723473270573409338368251757405505259439091937259103551628289n
}

signer MUST be equal to await orandInstance.getOperatorAddress() to make sure the ECDSA proof is valid.
receiverEpoch the required epoch number that need to be submit in the next publication.
receiverAddress MUST be equal to predefine receiverAddress in the initial stage
y Result of the current epoch

.getActiveChain()

await orandInstance.getActiveChain();

Allowed you to read the data of current active chain.

Result:

{
  url: 'https://data-seed-prebsc-1-s2.binance.org:8545',
  providerAddress: '0x75C0e60Ca5771dd58627ac8c215661d0261D5D76'
}

url is the JSON-PRC provider, if you don't want you can use another JSON-RPC provider
providerAddress is OrandProviderV1 address on active chain

.getOperatorAddress()

await orandInstance.getOperatorAddress();

Get the operator's address that is going to sign the ECDSA Proof.

Result:

0x7e9e03a453867a7046B0277f6cD72E1B59f67a0e

.getReceiverAlpha()

await orandInstance.getReceiverAlpha(
  "0xf16f07cfd6e9ac06925fcf68dd0b450f4131989d"
);

Get current alpha of receiver, current alpha is previous the result of previous epoch. The next epoch MUST have the same alpha with current receiver's alpha.

Result:

114997148547855332310731174935020155906209462858493962385407246111280193662921n

.getReceiverEpoch()

await orandInstance.getReceiverEpoch(
  "0xf16f07cfd6e9ac06925fcf68dd0b450f4131989d"
);

Get current epoch of receiver, this value will be increased after a new epoch data submit to OrandProviderV1. This value MUST be equal to the epoch number of the submitting epoch.

Result:

1n

.verifyECVRFProof()

await orandInstance.verifyECVRFProof(epochData);

Allowed you to verify the correctness of any epoch, it will return true if the given epoch is valid, otherwise it will return false.

Result:

true

Note: We might provide a new feature to reroll current epoch, in case the result failed to be verified on-chain. This reroll feature only change the witness but the result will be the same.

Verifiable Random Function (VRF)

We present an overview of verifiable random functions (VRF) and describe a construction a VRF based on elliptic curves in [PWHVNRG17].

Informally speaking, a VRF is a function that generates values that looks indistinguishable from random, and these values can be verified if they were computed correctly. Later, we discuss a few cryptographic applications that VRF possibly plays an important building blocks in constructing them.

The chapter is separated into $2$ two major parts. In the first part, we state the formal definition of VRF including its syntax and security properties. Then we talk about the history of VRFs to see its development. In the second major part, we describe the VRF based on elliptic curve and our implementation of the VRF.

Overview of VRF

In this chapter, we present an overview of VRFs. First, we give a short introduction of VRF including its intuition and importance in cryptography. After that, we discuss the formal definition of VRF and its security requirements. Finally, we talk about the history of VRF to see its development.

Introduction

In cryptography, a verifiable random function (VRF) is a public key version of a pseudorandom function. It produces a pseudorandom output and a proof certifying that the output is computed correctly.

A VRF includes a pair of keys, named public and secret keys. The secret key, along with the input is used by the holder to compute the value of a VRF and its proof, while the public key is used by anyone to verify the correctness of the computation.

The issue with traditional pseudorandom functions is that their output cannot be verified without the knowledge of the seed. Thus a malicious adversary can choose an output that benefits him and claim that it is the output of the function. VRF solves this by introducing a public key and a proof that can be verified publicly while the owner can keep secret key to produce numbers indistinguishable from randomly chosen ones.

VRF has applications in various aspects. Among them, in internet security, it is used to provide privacy against offline enumeration (e.g. dictionary attacks) on data stored in a hash-based data structure irtf-vrf15. VRF is also used in lottery systems [MR02] and E-cashes [BCKL09].

VRF Algorithms

Formally, a Verifiable random function consists of three algorithms $ (\mathsf{Gen}, \mathsf{Eval}, \mathsf{Verify})$ where:

$(pk,sk) \leftarrow \mathsf{Gen}(1^{\lambda})$: This algorithm takes as input as a security parameter $ \lambda $ and outputs a key pair $ (pk,sk)$.

$ (Y,\pi) \leftarrow \mathsf{Eval}(X,sk)$: This algorithm takes as input a secret key $sk$ and a value $X$ and outputs a value $Y \in {0,1}^{out(\lambda)} $ and a proof $ \pi $.

$ b \leftarrow \mathsf{Verify}(pk,X,Y,\pi)$: This algorithm takes an input a public key $pk $, a value $X$, a value $Y$, a proof $\pi$ and outputs a bit $b$ that determines whether $Y=\mathsf{Eval}(X,sk)$.

VRF Security Properties

History of Verifiable Random Function

Verifiable Random Function is introduced by Micali, Rabin and Vadhan [MRV99]. They defined a Verifiable Unpredictable Function (VUF) and gave a construction based on the RSA assumption [MRV99], then proved that a VRF can be constructed from a VUF [MRV99].

In 2002, Lysyanskaya [DBLP:conf/crypto/Lysyanskaya02] also followed the same path by constructing a VUF instead VRF. However, Lysyanskaya's VUF is based on Diffie-Hellman assumption instead, and it is the first construction that is based on Diffie-Hellman assumption.

In 2005, Dodis and Yampolsky [DY05] gave a direct and efficient construction using bilinear map, then improved. Later, during the 2010s, many constructions {{#cite HW10,BMR10,Jag15}} also used bilinear map, all of them used non standard assumptions to prove the security of their VRF.

In 2015, Hofheinz and Jager [HJ15] constructed a VRF that is based on a constant-size complexity assumption, namely the $(n-1)$-linear assumption. The $(n-1)$-linear assumption is not easier to break as $n$ grows larger, as opposed to all the assumptions used by previous constructions [Unknown bib ref: HS07].

In 2017, [PWHVNRG17] construct an efficient VRF based on elliptic curve that does not use bilinear map to produce output and verify, instead they only use hash functions and elliptic curve operations. In the other hand, their hash function is viewed as random oracle model in the construction.

In 2019, Nir Bitansky [Bit19] showed that VRF can be constructed from non-interactive witness-indistinguishable proof (NIWI).

In 2020, Esgin et al [EKSSZSC20] was the first to construct a VRF based on lattice based cryptography, which is resistant to attack from quantum computers. Thus, VRF remains as a good candidate for generating randomness in the future.

VRF Based on Elliptic Curves (ECVRF)

In this chapter, we describe a VRF Based on Elliptic Curves in the paper of [PWHVNRG17]. The Internet Research Task Force (IRTF) also describes this VRF in their Internet-Draft irtf-vrf15. The security proof of the VRF is in \cite{PWHVNRG17}, we do not present it here. Then we will present our implementation of the VRF.

Why using ECVRF

There are many VRF constructions, as listed in the history of VRF. However, ECVRF is chosen because its efficient in both proving and verification complexity, and can be make distributed.

For example, in the construction of Hohenberger and Waters [Unknown bib ref: HW10], the proof of the VRF contains $\Theta(\lambda)$ group elements. The number of evaluation steps is $\Theta(\lambda)$, because we need to compute $\Theta(\lambda)$ group elements. Verification require $\Theta(\lambda)$ computations using bilinear map, where $\lambda$ is the security parameter. It is unknown whether this VRF can be made distributed or not.

In the other hand, the proof size and the number of evaluation and verification steps of ECVRF are all constant and can be make distributed, as in the paper of Galindo et al [GLOW20]. The VRF construction of [DY05] also have constant proof size, evaluation and verification steps, and can be make distributed. However, in their paper, they require a cyclic group whose order is a 1000 bit prime, while ECVRF require a cyclic group whose order is a 256 bit prime such that the Decisional Diffie-Hellman (DDH) assumption holds. Hence, we can implement the VRF using Secp256k1, a curve used by Ethereum for creating digital signature. The embeeding degree of Secp256k1 is large, thus the DDH assumption is believed to be true.

Public Parameters

Let $\mathbb{G}$ be a cyclic group of prime order $p$ with generator $g$. Denote $\mathbb{Z}_p$ to be the set of integers modulo $p$. Let $\mathsf{EncodeToCurve}$ be a hash function mapping a bit string to an element in $\mathbb{G}$. Let $\mathsf{ChallengeGeneration}$ be a hash function mapping arbitary input length to a $256$ bit integer.

Note that, in the paper of [PWHVNRG17], the functions $\mathsf{EncodeToCurve}$ and $\mathsf{ChallengeGeneration}$ are modeled as random oracle model. This is used to prove the security of the VRF.

The cofactor parameter mentioned in the irtf draft is set to $1$.

The $\mathsf{Eval}$ function is split into 2 functions: $\mathsf{Prove}$ and $\mathsf{ProofToHash}$. The $\mathsf{Prove}$ function returns the proof of the ECVRF, and the $\mathsf{ProofToHash}$, returns the ECVRF output.

ECVRF Construction

$\mathsf{KeyGen}(1^{k})$: Choose a random secret value $sk \in \mathbb{Z}_p$ and the secret key is set to be $sk $. The public key is $pk=g^{sk}$.

$\mathsf{Prove}(sk,X)$: Given the secret key $sk$ and an input $X$, the proof $\pi$ of ECVRF is computed as follow:

Compute $h=\mathsf{EncodeToCurve}(X,pk)$.
Compute $\gamma=h^{sk}$.
Choose a value $k$ uniformly in $\mathbb{Z}_p$.
Compute $c=\mathsf{ChallengeGeneration}(h,pk,gamma,g^k,h^k)$
Compute $s \equiv k-c.sk \pmod{q}$
The proof $\pi$ of the VRF is computed as $\pi=(\gamma,c,s)$

$\mathsf{ProofToHash}(gamma)$: Given input $\gamma$ that is calculated during the $\mathsf{Prove}$ function, this function returns the output of ECVRF.

Compute $gammastr=\mathsf{PointToString}(\gamma)$
Let $gammastr=PointToString(\gamma)$
Let $suite-string$="0x01"
Let $separator-front$="0x03"
Let $separator-back$="0x00"
Let Y=$\mathsf{keccak}(suite-string || seperator-front || gammastr || seperator-back)$
Return Y

$\mathsf{Verify}(pk,X,Y,\pi)$: Given the public key $pk$, the VRF input $X$, the VRF output $Y$ and its proof $\pi=(\gamma,c,s)$, the verification step proceed as follow:

Check if $\gamma$ and $pk$ is on the curve
Compute $u=pk^cg^s$
Compute $h=\mathsf{EncodeToCurve}(X,pk)$
Compute $v=\gamma^ch^s$
Check if $c=\mathsf{ChallengeGeneration}(h,pk,gamma,g^k,h^k)$. If the check is valid, output $Y=\mathsf{ProofToHash}(\gamma)$, otherwise output $Invalid$.

ECVRF Auxiliary Functions

In this section, we describe the construction of $HashToCurve$ and $HashPoint$ in the Internet-Draft of irtf. More details can be found in irtf-vrf15.

$\mathsf{EncodeToCurve}(X,pk)$: Given two group elements $X, pk \in \mathbb{G}$, the function output a hash value in $\mathbb{Z}_p$ as follow:

Let $ctr=0$
Let $suite-string$="0x01"
Let $seperator-front$="0x01"
Let $seperator-back$="0x00"
Compute $pkstr=\mathsf{PointToString}(pk)$
Define $H$ to be "INVALID"
While $H$ is "INVALID" or $H$ is the identity element of the group:
- Compute $ctrstr=\mathsf{IntToString}(ctr)$
- Compute $hstr=\mathsf{keccak}$$( suite-string || seperator-front || pkstr || X || ctrstr || seperator-back)$
- Compute $H$=$\mathsf{StringToPoint}(hstr)$
- Increment $ctr$ by $1$
Output $H$.

$\mathsf{ChallengeGeneration}(P_1,P_2,...,P_n)$: Given n elements in $\mathbb{G}$, the hash value is computed as follow:

Let $suite-string$="0x01"
Let $seperator-front$="0x02"
Initialize $str=suite-string || seperator-front$
For $i=1,2,...,n$:
- Update $str= str || \mathsf{PointToString}(P_i)$
Let $separator-back$="0x00"
Update $str=str || separator-back$
Update $str=\mathsf{keccak}(str)$
Compute $c=\mathsf{StringToInt}(str)$
Output $c$

The function $\mathsf{PointToString}$ converts a point of an elliptic curve to a string. Many programming supports this function. For example, in python, we can use $str(G)$ to return the string representation of a point$G$.

The function $\mathsf{StringToPoint}$ converts a string to a point of an elliptic curve. It is specified in section 2.3.4 of [SECG1]

ECVRF implementation in Python

The implememtation of the ECVRF in python. The steps and details are written on the comments of the implementation. Below are the global variables. We use the ecdsa library, but the curve curve_256 of the library is replaced with the curve secp256k1. Instead of using SHA256 as in irtf-vrf15, we use the keccak hash function.

G = generator_256
ORDER = G.order()
order_minus_one=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
INFINITY=Point(None,None,None)
suite_string=b"0x01"

ECVRF main functions

The main functions of the ECVRF.

The Key generation function

We create an ECVRF class and use the key generation function as the constructor of the class.

class ECVRF():

    def __init__(self,sk=None):
    if sk==None:
            self.sk = random.randint(0,order_minus_one)
            self.pk = G*self.sk
    else:
        self.sk = sk
        self.pk = G*self.sk

The Prove function

The prove function of the ECVRF. The function closely follow the steps in Section 5.1 of irtf-vrf15

def prove(self, x):
        # the evaluation function, based on the paper [PWHVNRG17]
        # step 1 compute h

        H = ECVRF_encode_to_curve_try_and_increment(self.pk,x,suite_string)

        #step 2 let gamma=h^self.sk

        gamma = H*self.sk

        #step 3 choose a random k

        k = random.randint(0,order_minus_one)

        #step 4 compute c=Hash_point(g,h,g^sk,h^sk,g^k,h^k)

        point_list=[H, self.pk, gamma, G*k, H*k]
        c = ECVRF_challenge_generation(point_list)

        #step 5 compute s=k-c*sk (mod order)
        s = (k - c*sk)% ORDER

        # the proof consists of gamma, c and s
        pi = {'gamma': gamma, 'c': c,  's': s}

        # the output is the keccak hash of gamma
        y=proof_to_hash(gamma)

        return {'output': y, 'proof': pi, 'public key': self.pk}

The ProofToHash function

The prove function of the ECVRF. The function closely follow the steps in Section 5.2 of irtf-vrf15

def proof_to_hash(gamma):

        # the output is the keccak hash of gamma
        hash = keccak.new(digest_bits=256)
        hash.update(b"\x01")
        hash.update(b"\x03")
        hash.update(str(gamma).encode())
        hash.update(b"\x00")
        y = int(hash.hexdigest(), 16)

The Verify function

The verify function of the ECVRF. The function closely follow the steps in Section 5.3 of irtf-vrf15

def verify(self, x, y, pi, pk):
        # this function, given an input x, a value y, a proof pi and 
        # the public key pk,
        # verify if the output y was calculated correctly from x

        gamma = pi['gamma']
        c = pi['c']
        s = pi['s']

        #step 1 compute U=c*pk+G*s

        U = c*pk + G*s

        #step 2 compute V=c*gamma+H*s

        H = ECVRF_encode_to_curve_try_and_increment(pk,x,suite_string)

        #step 3 compute V=c*gamma+h*s

        V = c*gamma + H*s

        #calculate the value Hash_point(G,H,pk,gamma,U,V)

        point_list=[H,pk,gamma,U,V]
        c2 = ECVRF_challenge_generation(point_list)

        #calculate the keccak hash of gamma

        hash = keccak.new(digest_bits=256)
        hash.update(str(gamma).encode())

        #step 4 check if c=Hash_point(g,h,pk,gamma,u,v) and y=keccak(gamma)

        return c == c2 and y == hash_to_proof(gamma)

ECVRF auxiliary functions

The auxiliary functions of the ECVRF.

The HashToCurve function

The HashToCurve of the converts a 256 bit integer into a point of the curve secp256k1. We ignore the cofactor check in irtf-vrf08, since the cofactor value is set to be 1.

def ECVRF_encode_to_curve_try_and_increment(pk, x, suite_string):
    #follow the ecvrf irtf draft

    ctr=0
    pk_string=str(pk).encode()
    one_string=int(0).to_bytes(1,'big')
    zero_string=int(1).to_bytes(1,'big')

    #because the == operation in the elliptic curve class only compare
    #two Points, we cannot use H=="INVALID" (can't compare a Point and a
    # string) but instead use H==INFINITY
    #because if H==INFINITY is also an invalid condition and it does not
    #change anything.

    H=INFINITY
    while  H==INFINITY:
        hash=keccak.new(digest_bits=256)
        ctr_string=str(ctr).encode()
        hash.update(suite_string)
        hash.update(one_string)
        hash.update(pk_string)
        hash.update(str(x).encode())
        hash.update(ctr_string)
        hash.update(zero_string)
        ctr+=1
        hash=hash.digest()
        H=string_to_curve(hash)
    return H

The HashPoint function

The HashPoint function converts a list of point into a 256 bit integer. The function closely follow the steps in Section 5.4.3 of irtf-vrf08

def ECVRF_challenge_generation(point_list):
        # based on the irtf internet draft
        #we use the keccak instead of sha256

        hash = keccak.new(digest_bits=256)
        hash.update(b"\x02")
        for i in point_list:
            hash.update(str(i).encode())
        hash.update(b"\x00")
        return int(hash.hexdigest(), 16) % ORDER

The StringToCurve function

The StringtoCurve converts a string into a point of secp256k1. We only need to implement Step 1, Step 2.2 and Step 2.4.1 in [SECG1], since we use the curve secp256k1.

def string_to_curve(string):
    #specified in 2.3.4 of https://www.secg.org/sec1-v2.pdf
    #since the curve is secp256k1, then q=p is an odd prime
    #we want to implement for secp256k1 therefore we will just implement step 1, 
    # 2.2 and 2.4.1

    #Step 1

    if string==int(2).to_bytes(1,'big'):
        return INFINITY

    #Step 2.2

    x=string_to_field(string)
    if x=="INVALID":
        return INFINITY
    p=secp256k1._CurveFp__p

    #Step 2.4.1
    # let t=x^3+7 (mod p) 

    t=(pow(x,3,p)+secp256k1._CurveFp__a*x+secp256k1._CurveFp__b)%p
    QR=pow(t,(p-1)//2,p)
    if QR==(p-1):
        return INFINITY

    # because p=3 (mod 4), we see that y=t^((p+1)/4)

    beta=pow(t,(p+1)//4,p)
    if beta%2==0:
        return Point(secp256k1,x,beta)
    else:
        return Point(secp256k1,x,p-beta)

The StringToField function

The StringtoCurve converts a string into an element in $\mathcal{Z}_p$, where $p=2^{256}-2^{32}-977$. We only need to implement Step 1 and Step 2.3.6 in [SECG1].

def string_to_field(string): 
    #specified in 2.3.6 of https://www.secg.org/sec1-v2.pdf
    #since i just want to implement for secp256k1, i will just implement step 1
    #in fact, step 1 is just the function string_to_integer in part 2.3.8 of the
    #same paper

    x=0
    for i in range (0,len(string)):
        x+=pow(256,len(string)-1-i)*int(hex(string[i]),16)
    if x<secp256k1._CurveFp__p:
        return x
    return "INVALID"

Distributed Key Generation (DKG)

We give an overview of Distributed Key Generation (DKG) and describe the DKG protocol used in the paper [GJKR99]. This, along with the ECVRF, will be two main components for the Distributed Verifiable Random Function (DVRF) protocol used for generating pseudorandom values. First, we give an overview of DKG. Then, we mention Verifiable Secret Sharing (VSS), the main building block for a DKG protocol. Finally, we describe the DKG protocol of [GJKR99].

Overview to DKG

Distributed key generation is a main component of threshold cryptosystems. It allows $n$ participants to take part and generate a pair of public key and secret key required for the threshold cryptosystem without having to rely on a trusted party (dealer). Each participant in additional receive a partial secret key and a partial public key. While the public key and partial public keys is seen by everyone, the private key is maintained as a (virtual) secret of a $t,n$ secret sharing scheme, where each share is the partial secret key of a participant [GJKR99]. No adversary with limited computational power can learn any information of the secret key unless it control the required amount of participants.

DKG Security Properties

As in [GJKR99], we wish a $(t,n)$ DKG protocol to have the following properties:

Correctness:

There is an efficient algorithm that, given any $t+1$ shares provided by honest parties, output the same unique secret key $sk$.
All honest parties agree on the same value of the public key $pk=g^{sk}$.
$sk$ is uniformly distributed in $\mathbb{Z}_p$.

Secrecy:: For any adversary who controls at most $t$ participants, he cannot learn any additional information except the value $pk=g^{sk}$.

Applications

DKG has been used in numerous aspects:

Threshold Encryption and Signatures: In threshold cryptosytems, one problem arises: single point of failure. If a single participant fails to follow the protocol, then the entire system will abort. When applied as a component of a threshold cryptosystem, $(n,t)$DKG solves this problem by ensuring that any $t+1$ participants who behave honestly will allow the protocol to execute successfully.
Identity based Cryptography (IBC): In IBC, a private-key generator (PKG) is required to generate a secret, called the master key and provide private keys to clients using it. Since he know the private key of the client, he can decrypt the messages of the client. A $(n,t)$ DKG solve this by distributing the PKG into many participants where any adversary who control at most $t$ parties cannot compute the master key, and the client receive his secret key by collecting $t+1$ partial private keys from the participants.
Distriuted Pseudo-random Functions: Pseudo-random Functions (PRF) and Verifiable Random Functions (VRF) is used to produce values that looks indistinguishable from random. Both require a secret key to compute the output. However, the secret key holder can select the value of the secret key to manipulate the output, or share the secret key with others to benefit himself. This can be prevented by applying a $(n,t)$ distributed version of PRF or VRF, thus no adversary can learn or affect the value of the secret key.

In this chapter, we discuss about Verifiable Secret Sharing (VSS), the main building block for a DKG protocol. We state the syntax and security properties of a VSS, then describe the VSS construction due to Pedersen.

Introduction

Secret Sharing was first introducted by Shamir in 1979 [Unknown bib ref: Sha79]. It allows a person to share a secret $s$ among $n$ parties such that any \textit{authorized} subset of parties can use all their shares to reconstruct the secret, while any other (non-authorized) subset learns nothing about the secret from their shares. Shamir proposed a secret sharing scheme in his paper [Unknown bib ref: Sha79]. However, in Shamir's scheme, parties can commit wrong shares, leading the protocol to reconstruct the wrong secret, thus a verification process of the shares is required. To solve this problem, Chor et al. [CGMA85] introduced Verifiable Secret Sharing.

Syntax and Properties

Syntax

A $(t,n)$ Verifiable Secret Sharing consists of two phases: Share and Reconstruct as follow:

Share: The dealer $D$ has a secret value $s$. Initially, there are $n$ parties $P_1, P_2, ..., P_n$. The sharing phase may consist of several rounds of interaction between parties. At the end of the phase, each party $P_i$ holds a share $s_i$ that will be required to reconstruct the secret of the dealer later.

Reconstruct: In this phase, each party $P_i$ publishes its share $s_i$ from the sharing phase. Then, from these shares, a reconstruction function will be applied to output the original secret.

Properties

As in [BKP11], a VSS need to have the following properties:

Correctness: If $D$ is honest, then the reconstruction function outputs $s$ at the end of the Reconstruct phase and all honest parties agree on the value $s$.

Secrecy: If $D$ is honest, then any adversary that control at most $t$ parties does not learn any information about $s$ during the Share phase.

Commitment: If $D$ is dishonest, then at the end of the sharing phase there exists a value $s^* \in \mathbb{F}_p$ such that at the end of the Reconstruct phase all honest parties agree on $s^*$.

Pedersen's Construction

We describe a VSS protocol from Pedersen [Ped91]. This scheme provides perfect information theoretic security against any adversary with unbounded computational power.

Share The dealer chooses two polynomials $p(x)=a_0+a_1x+a_2x^2+...+a_tx^t$ and $p'(x)=b_0+b_1x+b_2x^2+...+b_tx^t$ such that $a_0=s$. Then he compute $s_i=p(i)$ and $s_i'=p'(i)$. The dealer then broadcasts $C_i=g^{s_i}h^{s_i'}$. Then he gives the party $P_i$ the tuple $(s_i,s_i')$. This allows $P_i$ to check if $(s_i,s_i')$ is a valid share by checking that

$$g^{s_{i}}h^{s_{i}'} \stackrel{?}{=} \prod_{k=0}^{t}(C_{k})^{i^k} (*).$$

If a party $P_i$ receives a share that does not satisfy $(*)$, he will complains against the dealer. The dealer must reveal the share $(s_i,s_i')$ that satisfies for each complaining party $P_i$. If any of the revealed shares does not satisfy $(1)$ the equation, the dealer is marked invalid.

Reconstruct Each participant submits $(s_i,s_i')$. Everyone can verify if $P_i$ submitted the correct shares by checking if $1$ is satisfied. If $P_i$ receives more than $t$ complaints, then he is disqualified. Given $t+1$ valid shares, $s_1,s_2,...,s_{t+1}$ from parties $P_{x_1},P_{x_2},...,P_{x_{t+1}}$, the secret $s$ can be computed as: $$s= \sum_{i=0}^{t}s_i \left(\prod_{\substack{j=0 \ j\neq i}}^{t}\dfrac{x_j}{x_j-x_i}\right).$$

The security proof of the protocol can be found in [Ped91].

DKG Construction

In this chapter, we describe the DKG protocol in the paper Gennaro et al [GJKR99]. The protocol can withstand up to $\dfrac{n}{2}$ dishonest participants, where $n$ is the number of participants. Despite the high communication cost, the protocol only need to be executed once in the first round of many threshold cryptosystems.

Why Gennaro et al's Construction?

Despite there are numerous constructions for DKG, namely [GJKR99], there is a reason we choose the DKG protocol of Gennaro et al.

Previously, Pedersen was the first to propose a DKG construction [Ped91a]. However, Gennaro et al. proved that in Pedersen's DKG, an attacker can manipulate the result of the secret key, making it not uniformly distributed [GJKR99].

Canetti et al. [CGJKR99] give a construction of a DKG that is secure against an adaptive adversary. However, his construction has worse performance than Gennaro's, since each participant has to use Pedersen's VSS two times. In addition, no adaptive adversary has been able to successfully attack the construction of Gennato et al.

Numerous attempts have been made to reduce the communication cost for a DKG {{#cite KG09, CS04, CZAPGD20}}. However, all these schemes require a trusted party. This quite contradict the goal of a DKG.

This make the DKG construction of Gennaro et al. remains a simple, efficient and secure DKG protocol.

Gennaro et al's Construction

The DKG protocol consists of two phases, namely, generating and extracting, working as follows:

Public Parameters: Let $p$ be a prime number. Let $G$ be a cyclic group of order $p$ with generators $g$ and $h$. The public parameters of the system are $p,G,g,h$.

Generating: This process works as follows:

Each participant $P_i$ chooses two random polynomials $f_i(z)=a_{i0}+a_{i1}z+...+a_{it}z^t$ and $f_i'(z)=b_{i0}+b_{i1}z+...+b_{it}z^t$ and broadcasts $C_{ij}=g^{a_{ij}}h^{b_{ij}}$ for $j=0,1,...,t$.
The participant $P_i$ then sends $s_{ij}=f_i(j)$ and $s'_{ij}=f_i'(j)$ to $P_j$.
Each participant $P_j$ verifies the shares he received from each $P_i$ by checking whether

$$g^{s_{ij}}h^{s_{ij}'}\stackrel{?}{=} \prod_{k=0}^{t}C_{ik}^{j^k}. (*)$$

If the check fails for some $i$, $P_j$ complains against $P_i$.

Each $P_i$ who receives a complaint from $P_j$ broadcasts $s_{ij}$ and $s_{ij}'$ that satisfy Equation $(*)$.
A participant $P_i$ is disqualified if he receives at least $t+1$ complaints or answers a complaint with value that does not satisfy Equation. Then a set $\mathsf{QUAL}$ of qualified participants is determined.
For each $i$, the secret key $sk_i$ of $P_i$ is equal to $ \sum_{j\in \mathsf{QUAL}} s_{ji}$. For any set $\mathcal{V}$ of at least $t+1$ participants, the secret key $sk$ is equal to $ \sum_{i \in \mathcal{V}} sk_i\cdot\lambda_{i,\mathcal{V}}$.

Extracting: The process works as follows:

Each participant $P_i$ in the set $\mathsf{QUAL}$ publishes $A_{ij}=g^{a_{ij}}$ for $j=0,1,2,\dots,t$.
Each participant $P_j$ verifies $A_{ij}$ for each $i$. Specifically, $P_j$ checks whether $$g^{s_{ij}}\stackrel{?}{=} \prod_{k=0}^{t}A_{ik}^{j^k}.$$ If the check fails for some $i$, $P_j$ complains against $P_i$.
For each $i$ that $P_i$ receives at least one valid complaint, all other parties run Pedersen VSS to reconstruct $f_i(z)$, and restore $s_{i0}$ and $A_{ij}$ for $j=0,1,...,t$. The public key is equal to $pk= \prod_{i \in \mathsf{QUAL}}A_{i0}$
The public key $pk_i$ of $P_i$ is calculated as $pk_i=g^{sk_i}=\prod_{j \in \mathsf{QUAL}}g^{s_{ji}}= \prod_{j \in \mathsf{QUAL}}\prod_{k=0}^{t}A_{jk}^{i^k}$

The security proof of the DKG protocol can be found in [GJKR99].

Isogeny based cryptography

We introduce Isogeny based cryptography, one of the possible candidates for post-quantum cryptography. People may have heard the SIKE protocol have been broken [CD22], but many other isogeny based cryptosystems, such as the CLG hash function [CGL06] and SQISign [Unknown bib ref: SKLPW20] remains secure against the attack on SIDH. We begin with supersingular isogeny graph and its properties, then we describe several isogeny based cryptosystems.

Overview of Supersingular Isogeny Graph

In this chapter, we introduce supersingular isogeny graph and its properties to see why this graph is used in isogeny based cryptography. The vertices of the graph represent the supersingular elliptic curves, and the edges of the graph represent the isogenies between these curves. We will state the definitions of supersingular elliptic curves and isogenies, then describe the structure of the graph and its nice properties in cryptography.

Elliptic Curves

Definition

Let $K$ be a field. An elliptic curve $E$ is a plane curve defined over the field $K$ as follows: $$E(K)=\{y^2=x^3+ax+b : (x,y) \in K^2\} \cup \{\mathcal{O}\}$$ where $(a,b) \in K^2$. The point $\mathcal{O}$ is called the infinity point of the curve. The set $E(K)$ forms an abelian group with identity element $\mathcal{O}$.

In addition, we need the curve to have no cusps, self-intersections, or isolated points. Algebraically, this can be defined by the condition $4a^3+27b^2 \neq 0$ in the field $K$.

The $j-$ invariant of an elliptic curve is defined to be $-1728\frac{4a^3}{4a^3+27b^2}$. Two elliptic curves are isomorphic to each other if and only if they have the same $j-$ invariant value.

The endomorphism ring of $E$ is denoted $End(E)$. The structure of $End(E)$ can be found in Chapter 3.9 of Silverman's book.

For an integer $n$, we define $E[n]=\{(x,y) \in E(K) | n*(x,y)=\mathcal{O}\}$

Over a field $\mathbb{F}_p$, there are two types of curves: Ordinary and Supersingular, based on the set $E[p]$. We are interested in studying Supersingular curves, since the isogeny graph on these curves has nice structure and properties.

Isogenies

Definition

[Was08, Chapter XII.1] Let $E_1:y^2=x^3+a_1x+b_1$ and $E_2:y^2=x^3+a_2x+b_2$ be elliptic curves over a field $K$. An isogeny from $E_1$ to $E_2$ is a nonconstant homorphism $\alpha:E_1 \rightarrow E_2$ that is given by rational functions.

This means $\alpha(P+Q)=\alpha(P)+\alpha(Q)$ for all $P,Q \in E_1$ and there exists rational functions $P, Q$ such that if $\alpha(x_1, y_1)=(P(x_1, y_1),Q(x_1, y_1))$.

In fact, it can be proved that we can write $\alpha$ in the form $\alpha(x_1, y_1)=(p(x_1), y_1q(x_1))$.

If $p(x)=\dfrac{r(x)}{s(x)}$ for polynomials $r$ and $s$ without common roots, define the degree of $\alpha$ to be $Max(deg(r(x)),deg(s(x)))$.

We say an isogeny is seperable if $s(x)$ have no repeated roots.

Example

Consider two curves $E_1:y^2=x^3+x$ and $E_2:y^2=x^3-4x$ over $\mathbb{F}_{11}$. Then the map $$\alpha: E_1 \rightarrow E_2$$ $$(x,y) \mapsto \left(\dfrac{x^2+1}{x},\dfrac{y(x^2-1)}{x}\right)$$ is an isogeny from $E_1$ to $E_2$.

Properties

We mention several important properties of isogenies.

Isogenies are uniquely determined by their kernel: Given an elliptic curve $E$ and a subgroup $L$, there is an unique elliptic curve $E'$ and an isogeny $\alpha: E \rightarrow E'$ such that the kernel of $\alpha$ is $L$.
[Sil09, Chapter III.6, Theorem 6.2] For every isogeny $\alpha: E \rightarrow E'$ of degree $l$, there exists an unique dual isogeny $\hat{\alpha}: E' \rightarrow E$ such that $\alpha \hat{\alpha}= \hat{\alpha} \alpha=l$
[Gha21, Proposition 2.2] (Decomposition of isogenies) Let $\alpha: E \rightarrow E'$ be a seperable isogeny. Then there exists an integer $k$ elliptic curves $E=E_0, E_1,...,E_n=E'$ and isogenies $\beta_i: E_i \rightarrow E_{i+1}$ of prime degree such that $\alpha=\beta_{n-1} \beta_{n-2} ... \beta_{0} [k]$

The edges of Supersingular isogeny graphs are determined by isogenies between the curves, we will talk about it later in the definition of the graph.

Supersingular Elliptic Curves

Definition

Let $p$ is a prime and let $q$ be a power of $p$. Let $E$ be an elliptic curve over $\mathbb{F}_q$. If $E[p]=\mathcal{O}$, then $E$ is a Supersingular elliptic curve, if $E[p]=\mathbb{Z}/p\mathbb{Z}$ then $E$ is an Ordinary elliptic curve.

Example

For $p=3$, the curve $E: y^2=x^3-x$ is supersingular over the field $\bar{F}_3$. Here we see that $[3]*(x,y)=\mathcal{O}$ for $(x,y) \neq \mathcal{O}$ if and only if $3x^4-6x^2-1=0$, but such $x$ does not exist since $\bar{F}_3$ has characteristic $3$. Thus $E[3]=\mathcal{O}$

Properties

Theorem [Sil09, Chapter V.3, Theorem 3.1] These following conditions are equivalent:

$E[p^r]=0$ for all $r \geq 1$.
$End(E)$ is an order in a quaternion algebra.
The map $[p]: E \rightarrow E$ is purely inseperable and $j(E) \in \mathbb{F}_{p^2}$.

As we see, all Supersingular elliptic curves are isomorphic to a curve in $F_{p^2}$, up to isomorphism, therefore the number of these curves are finite. It is natural that we want to count the number of these curves. Fortunately, we have a formula for the number of supersingular elliptic curves, as stated below:

Theorem. [Sil09, Chapter V.4, Theorem 4.1] The number of supersingular elliptic curves up to isomorphism is $\left\lfloor \dfrac{p}{12} \right\rfloor+z$, where

$z=0$ if $p \equiv 1 \pmod{ 12}$
$z=1$ if $p \equiv 5,7 \pmod{ 12}$
$z=2$ if $p \equiv 11 \pmod{ 12}$

In the next chapter, we introduce the graph where the vertices are the Supersingular elliptic curves (up to isomorphism). This graph has several interesting properties that make it a candidate for constructing post quantum cryptosystems.

Supersingular Isogeny Graphs (Pizer Graphs)

Definition

Let $p$ be a prime number. For a prime $l \neq p$, a Supersingluar isogeny graph $\mathcal{G} _l (\mathbb{F} _{p ^2})$ is a graph whose vertices are the j-invariants of supersingular elliptic curves in $\mathbb{F} _{p ^2}$, and such that there is an edge from $j(E _1)$ to $j(E _2)$ if and only if there is an isogeny of degree $l$ from $E_1$ to $E_2$. There can be multiple edges from $j(E_1)$ to $j(E_2)$, the number of such edges is equal to the number of isogenies from $j(E_1)$ to $j(E_2)$.

Since each vertex represents a supersingular elliptic curve, the number of vertices in $\mathcal{G} _l (\mathbb{F} _{p ^2})$ is equal to $\lfloor \frac{p}{12} \rfloor + \epsilon$, where $\epsilon$ is defined in.

For these graph, we require $p \equiv 1 \pmod{ 12} $ so that we can pair an isogeny with its dual to make the graph regular and undirected [Unknown bib ref: Gha21].

Properties

The reason why Supersingular Isogeny Graphs are important lies in the following theorems:

Theorem. [CGL09, Theorem 4.1] For $p \equiv 1 \pmod{ 12} $ and $l \neq p$ , the graph $\mathcal{G} _l(\mathbb{F} _{p^2})$ is connected, and is a $l+1$ regular graph.

Theorem. [CGL09, Theorem 4.2] For $p \equiv 1 \pmod{ 12} $ and $l \neq p$ the graph $\mathcal{G} _l(\mathbb{F} _{p^2})$ are Ramanujan graphs.

We give an overview about Ramanujan graphs. They are optimal expander graph. There are two nice properties of this type of graph. First, relatively short walk on this graph approximate the uniform distribution, which is good for a source of randomness. This can be seen by the following theorem:

Theorem. Let $N_{l,p}$ denote the number of vertices of $\mathcal{G} _l(\mathbb{F} _{p ^2})$ .Fix a supersingular $j_1 \in \mathbb{F} _{p^2}$, and let $j_2$ be the endpoint of a walk of length $e$ orginating at $j_1$. Then for all $j \in \mathbb{F} _{p^2}$:

$$|Pr[j=j_2]-N_{l,p}^{-1}| \leq \left(\dfrac{2\sqrt{l}}{l+1}\right)^e$$

The other nice property of Ramanujan graph is that the path-finding problem is assumed to be hard on this graph, which is good for constructing a cryptographic hash function. Two types of Ramanujan are proposed in [CGL06], LPS Graph and Supersingular Isogeny Graphs. However, the LPS hash function was attacked and broken in 2008 {{#cite TZ08, PLQ08}}, leaving the Supersingular Isonegy Graph as the ruling graph.

The adjacency matrix of $\mathcal{G} _l(\mathbb{F} _{p^2})$ is the Brandt matrix $B(l)$. More informations of the matrix can be found in Voight's book. The matrix allow us to specify all primes $p$ so that the graph does not have short cycles [Unknown bib ref: Gha21], an important property to ensure the hardness of the path-finding problem of the graph ((#cite CGL06)).

Applications of Pizer Graphs

Supersingular Isogeny Graph has applications in both mathematics and cryptography. We list several of their applications below.

In mathematics Supersingular Isogeny Graph is used in the following computational problems:
1. The endomorphism ring computation problem: Given $p$ and a supersingular $j$-invariant $j$, compute the endomorphism ring of $E(j)$ [EHLMP18].
2. The Deuring correspondence problem: Given a maximal order
  $\mathcal{O} \in B_{p,\inf}$, return a supersingular j-invariant such that the endomorphism ring $E(j)$ is isomorphic to $\mathcal{O}$ [EHLMP18].
In cryptography Supersingular Isogeny Graph is used in encryption scheme [MOT20], signature scheme [Unknown bib ref: SKLPW20], hash function [CGL06], verifiable delay function ((#cite LMPS19)). These schemes are secure against the attack on SIKE.

KZG Polynomial Commitment Scheme

KZG polynomial commitment scheme [KZG10] plays an important role in making the polynomial constraints of PlonK's arithmetization become a zkSNARK [GWC19].

In this section, we provide the syntax and security requirements of a polynomial commitment scheme (PCS) in Polynomial Commitment Scheme - Definition. Then, we show some instantiations of the scheme by discussing its technical overview in Technical Overview.

Author(s): khaihanhtang

Polynomial Commitment Scheme - Definition

In this section, we provide the definition of polynomial commitment scheme including syntax and security requirements. Syntax describes how the scheme works through algorithms while security requirements enforce the scheme to satisfy in order to make it secure.

Syntax is presented in Syntax and security requirements are presented in Security Requirements.

Syntax

A polynomial commitment scheme, for polynomials over a field $\mathbb{F}$, is a tuple of $5$ algorithms \[(\mathsf{Setup}, \mathsf{Commit}, \mathsf{VerifyPoly}, \mathsf{CreateWitness}, \mathsf{VerifyEval})\] working as follows:

$\mathsf{Setup}(1^\kappa, t):$ On inputs security parameter $1^\kappa$ and a degree bound $t$, this algorithm returns a commitment key $ck$. The key $ck$ allows to commit any polynomial in $\mathbb{F}[X]$ whose degree is at most $t$.

Above we use the notation $\mathbb{F}[X]$ to denote the field extension of $\mathbb{F}$. For intuition, this field extension contains every polynomial of the form $f(X) = \sum_{j = 0}^{\deg(f)} c_j \cdot X^j$ where $\deg(f)$ is the degree of $f(X)$ and $c_j \in \mathbb{F}$ for all $j \in \{0, \dots, \deg(f)\}$. Hence, with the algorithm $\mathsf{Setup}$ on input $t$, we can assume that it allows to commit to any polynomial $f$ satisfying $\deg(f) \leq t$.

We may have a question about what will happen if we try to use $ck$ to commit to a polynomial whose degree is larger than $t$. In this case, the execution and correctness of the algorithms below or the security of the scheme are not guaranteed.

$\mathsf{Commit}\left(ck, f(X)\right):$ On inputs commitment key $ck$ and polynomial $f(X) \in \mathbb{F}[X]$, this algorithm returns a commitment $c$ and an opening (or decommitment) $d$. We note that $f(X)$ here is recommended to have degree at most $t$ with respect to $ck$ output by $\mathsf{Setup}(1^\kappa, t)$.
$\mathsf{VerifyPoly}(ck, f(X), c, d):$ On inputs commitment key $ck$, polynomial $f(X) \in \mathbb{F}[X]$, commitment $c$ and opening $d$, this algorithm deterministically returns a bit $b \in \{0, 1\}$ to specify whether $c$ is a correct commitment to $f(X)$. If $c$ is such a correct commitment, then $b = 1$. Otherwise, $b = 0$.

At this moment, we may wonder why $\mathsf{Commit}$ does output both $c, d$ and $\mathsf{VerifyPoly}$ does use both $c, d$. In fact, when participating in an interactive protocol, one party may commit to some secret by exposing commitment $c$ to other parties. This commitment $c$ guarantees that the secret behind, namely, polynomial $f(X)$ in this case, is still secret, guaranteed the hiding property to be discussed later.

On the other hand, since we abuse the word commit, it means that the party publishing $c$ has only one opening, namely, $d$, to show that $c$ is a correct commitment to $f(X)$. It is extremely hard for this party to show that $c$ is correct commitment to some other polynomial $f'(X) \not= f(X)$. This is guaranteed by the binding property of the polynomial commitment scheme, to be discussed later.

$\mathsf{CreateWitness}(ck, f(X), i, d):$ On inputs commitment key $ck$, polynomial $f(X)$, index $i$ and opening $d$, this algorithm returns a witness $w_i$ to ensure that $c$, related to opening $d$, is commitment to $f(X)$ whose evaluation at index $i$ is equal to $f(i)$.

Let us explain in detail the use of $\mathsf{CreateWitness}$. Assume that a party published $c$ which is a commitment to $f(X)$. It then publishes a point $(i, v)$ and claims that $f(i) = v$ without exposing $f(X)$. By using the algorithm $\mathsf{VerifyEval}$ defined below, this claim is assured if $f(i)$ is actually equal to $v$. Moreover, for all other indices $i' $ satisfying $i' \not= i$, if $f(i')$ has not been opened before, then $f(i')$ is unknown to any party who does not know $f(X)$.

We also remark that, from basic algebra, if we know evaluations at $\deg(f) + 1$ distinct indices, we can recover the polynomial $f(X)$. Therefore, the above claim assumes that other parties do not know up to $\deg(f) + 1$ distinct evaluations.

$\mathsf{VerifyEval}(ck, c, i, v, w_i):$ On inputs commitment key $ck$, commitment $c$, index $i$, evaluation $v$ and witness $w_i$, this algorithm returns $\{0, 1\}$ deciding whether $c$ is a commitment key $f(X)$ satisfying $f(i) = v$.

Security Requirements

In this section, we briefly discuss the security requirement for polynomial commitment schemes.

A polynomial commitment scheme is said to be secure if it satisfies the following properties:

Correctness. The correctness property says that if the scheme is executed honestly then the verification algorithms, namely, $\mathsf{VerifyPoly}$ and $\mathsf{VerifyEval}$, always returns $1$. In particular, assume that $ck \leftarrow \mathsf{Setup}(1^\kappa, t)$ and $(c, d) \leftarrow \mathsf{Commit}(ck, f(X))$. Then, $\mathsf{VerifyPoly}(ck, f(X), c, d)$ always returns $1$. And, for any $w_i$ output by $\mathsf{CreateWitness}(ck, f(i), i, d)$, algorithm $\mathsf{VerifyEval}(ck, c, i, f(i), w_i)$ always returns $1$.
Polynomial Binding. For a given commitment key $ck$ output by $\mathsf{Setup}(1^\lambda, t)$, this property says that it is hard to output commitment $c$ and two tuples $(f(X), d)$ and $(f'(X), d')$ such that $f(X)$ and $f'(X)$ are distinct and have degrees at most $t$, and $c$ is commitment to both $f(X)$ and $f'(X)$ with respect to openings $d$ and $d'$, respectively. More precisely, it is hard to make $\mathsf{VerifyPoly}(ck, f(X), c, d) = 1$ and $\mathsf{VerifyPoly}(ck, f'(X), c, d') = 1$ if $f(X) \not= f'(X)$, $\deg(f) \leq t$ and $\deg(f') \leq t$.
Evaluation Binding. The evaluation binding property says that a committed polynomial evaluating on an index $i$ cannot produce two different outcomes $v$ and $v'$. More precisely, an adversary cannot provide an index $i$ and $2$ tuples $(v, w_i)$ and $(v', w'_i)$ satisfying $v \not= v'$ such that $\mathsf{VerifyEval}(ck, c, i, v, w_i) = 1$ and $\mathsf{VerifyEval}(ck, c, i, v', w'_i) = 1$.
Hiding. An adversary $\mathcal{A}$ who knows at most $\deg(f)$ evaluations of a committed polynomial $f(X)$ cannot determine any evaluation that it does not know before.

We remind that knowing $\deg(f) + 1$ different evaluations helps to determine polynomial, and hence all other evaluations. Therefore, we use the bound $\deg(f)$ here as a maxmimum number of evaluations that the adversary is allowed to know in order not to correctly obtain the evaluations of all other indices.

Technical Overview

From the syntax of polynomial commitment scheme presented in Polynomial Commitment Scheme - Syntax, a realization, or equivalently, a construction, can be separated into $2$ components:

Commiting polynomial includes the algorithms $\mathsf{Commit}$ and $\mathsf{VerifyPoly}$.
Evaluating polynomial includes the algorithms $\mathsf{CreateWitness}$ and $\mathsf{VerifyEval}$.

Based on those components, we present the high level idea of $2$ constructions, namely, conditional and unconditional, of polynomial commitment scheme separated into $3$ little parts. The first and second parts, to be presented in Commitment to Polynomial Without Hiding Property and Correct Evaluation from the Commitment, respectively, focus on constructing the realization of conditional version. And, in the third part, to be presented in Dealing with Hiding, regarding condition and unconditional hidings, we discuss the modification of conditional version to achieve the unconditional one.

Commitment to Polynomial Without Hiding Property

In the construction of [KZG10], the main idea to commit a polynomial is to evaluate it on a secret index. For example, assume that $f(X) = a_0 + a_1 X + \dots + a_d X^d \in \mathbb{F}[X]$. The secret index can be thought of as some value $x$ that the committer does not know. So, how can committer evaluate $f(x)$ on that secret index without any knowledge about it? In fact, cryptography can magically help you do that. For instance, by putting $1, x, x^2, \dots, x^n $ into the form of powers to some base element $g$, e.g., $g^1, g^x, g^{x^2}, \dots, g^d$, it helps to hide those values $1, x, x^2, \dots, x^d$. Moreover, it alows you to evaluate $g^{f(x)}$ as desired by computing $$ (g^1)^{a_0} \cdot (g^x)^{a_1} \cdot (g^{x^2})^{a_2} \cdot \dots \cdot (g^{x^d})^{a_d} = g^{a_0 + a_1x + \dots a_d x^d} = g^{f(x)}.$$ Thus, $g^{f(x)}$ is computed without any knowledge about $x$. Hence, that is whatever the committer needs to do in the commit step, namely, executing the algorithm $\textsf{Commit}$ to output the commitment $g^{f(x)}$. So the commitment key $ck$ for this algorithm is the hidden indices wrapped under powers of $g$, namely, the set sequence $(g^1, g^{x}, g^{x^2}, \dots, g^{x^d})$. And, therefore, $(g^1, g^{x}, g^{x^2}, \dots, g^{x^d})$ is also the output of the algorithm $\textsf{Setup}$. At this point, we might think about a few things:

How to verify the commitment $c = g^{f(x)}$ by executing $\textsf{VerifyPoly}$.
How to guarantee that the commitment satisfies the polynomial binding property.

For the first question, to verify $c$, the decommitment of the construction is $f(X)$ itself. Committer simply send the entire polynomial $f(X)$ to verifier, namely, by sending coefficients $a_0, \dots, a_d$. Having the polynomial and the commitment key $ck$, the verifier can check easily by repeating steps similar to the algorithm $\textsf{Commit}$.

For the second question, to show the satisfaction of binding property, we can assume that the committer is able to break the binding property by introducing another polynomial $f'(X) = a'_0 + a'_1X + \dots + a'_dX^d$ where $f'(X) \not= f(X)$. So we have $g^{f(x)} = c = g^{f'(x)}$.

Correct Evaluation from the Commitment

Warning. This part explains by the use of algebra. You may skip if you feel it is complicated.

For an index $i$ given to the committer, since committer knows $f(X)$, he can compute $f(i)$ definitely. The $\mathsf{CreateWitness}$ algorithm is constructed based on the fact that $X - i$ divides $f(X) - f(i)$. At this point, there is something difficult to realize here since it regards to the use of algebra. However, we know that $f(i)$ is the output of $f(X)$ on input $i$. Therefore, we see that $i$ is among the roots of $g(X) = f(X) - f(i)$, i.e., $g(i) = 0$ which says that $i$ is a root of $g(X)$. Therefore, $X - i$ divides $f(X) - f(i)$. Hence, to guarantee the evaluation binding property, committer needs to show that $f(X) - f(i)$ is divisible by $X - i$.

Example. Consider polynomial $f(X) = 6X^3 + 25X^2 + 16X + 19$ in $ \mathbb{Z}_{31}$. Let $i = 28$. Then, $f(28) = 151779 = 3$ in $ \mathbb{Z} _{31} $. Hence, $X - 28 = X + 3$ divides $f(X) - 3$. In fact, $$ f(X) - 3 = 6X^3 + 25X^2 + 16X + 16 = (3X + 5)(2X + 30)(X + 3)\text{ in } \mathbb{Z} _{31}.$$ It is obvious that $X + 3$ is a factor of $f(X) - 3$.

Equivalently, we can say that $v = f(i)$ if and only if $X - i$ divides $f(X) - f(i)$.

To show such divisibility holds, we can compute $\psi(X) = \frac{f(X) - v_i}{X - i}$, where $v_i$ is assumed to be $f(i)$, and define witness $w_i = g^{\psi(x)}$ by using $g^1, g^x, \dots, g^{x^d}$ output by the algorithm $\textsf{Setup}$.

At this point, for the verifier to verify, committer needs to show that $\psi(x) \cdot (x - i) + v_i = f(x)$. Let's closely take a look at this formula. We observe the followings:

No one knows $x$. Hence, $\psi(x)$ is not known to anyone.
Committer and verifier know $g^{\psi(x)}$ which is equal to the commitment $c$. Moreover, they also know $g^x, g^i, g^{v_i}$ since $g^x$ belongs to commitment key $ck$, $i$ is public and $v_i$ is publicly claimed by committer.
Verifier can easily compute $g^{x - i} = g^x / g^i$.

Clearly, having $g^{\psi(x)},g^{x - i}, g^{v_i}$ and $g^{f(x)}$, we do not know any efficient way to compute $g^{\psi(x)\cdot (x - i) + v_i}$ since computing $g^{\psi(x)\cdot (x-i)}$ is hard due to Diffie-Hellman assumption.

Using Bilinear Pairing to Handle Correct Multiplications

Recall the bilinear pairing $e : \mathbb{G}\times \mathbb{G} \to \mathbb{G}_T$ where $\mathbb{G}$ and $\mathbb{G}_T$ are some groups of the same cardinality. This bilinear pairing has $2$ properties: bilinearity and non-degeneracy. However, to avoid confusion, we only care about the bilinearity and temporarily skip the notice to non-degeneracy.

Bilinearity. For $g \in \mathbb{G}$ and $g_T \in \mathbb{G}_T$, $e(g^a, g^b) = e(g, g)^{ab}$ for any $a, b \in \mathbb{Z}_p$ where $p=|\mathbb{G}|$.

The validity of the witness can be check easily by using pairing, namely, $$e(w_i, g^x / g^i)\cdot e(g,g)^{v_i} \stackrel{?}{=}e(c, g),$$ where $c$ is the commitment to $f(X)$. If the above identity holds, with non-negligible probability, it says that $v_i = f(i)$.

To show identity implies $v_i = f(i)$ with non-negligible probability, we consider $w_i = g^{\psi(x)} = g^{\frac{f(x) - v_i}{x - i}}$. Hence, $$ \begin{align} e(w_i, g^x / g^i)\cdot e(g, g)^{v_i} &= e\left(g^{\frac{f(x) - v_i}{x - i}}, g^x / g^i\right)\cdot e(g, g)^{v_i}\\ &= e(g, g)^{f(x) - v_i}\cdot e(g, g)^{v_i} = e(g^{f(x)}, g) = e(c, g). \end{align} $$

Notice that, if the person providing $w_i$ and $v_i$ does not know $f(X)$, then we have the following possibilities:

This person correctly guesses $w_i$ and $v_i$. This happens with negligible probability if we assumes that field cardinality, namely, number of elements in field $\mathbb{F}$, is large.
The person incorrectly provides $w_i$ and $v_i$. Specificially, either $v_i$ is not equal to $f(i)$ or $w_i$ is incorrect. Assume that $w_i = g^{h_i}$. This case happens when $x$ is the root of $h_i\cdot (X - i) \cdot v_i = f(X)$. By Schwartz–Zippel lemma, this case also happens with negligible probability if the field cardinality is large and that person does not know $x$, as $x$ at the beginning was assumed to be hidden index.

Dealing with Hiding

In the previous sections, namely, Commitment to Polynomial Without Hiding Property and Correct Evaluation from the Commitment, we discussed the high level idea of the construction of algorithms as well as the polynomial and evaluation binding properties. One remaining thing is the hiding property. In [KZG10], the authors proposed $2$ constructions from discrete logarithm assumption, for conditional hiding, and Pedersen commitment, for unconditional hiding.

Remark. We now make clear the $2$ notions here, namely, conditional hiding and unconditional hiding.

Conditional hiding of a commitment $c$ to a polynomial $f(X)$ is the property protecting the polynomial $f(X)$ from being compromised with a condition that some assumption employed is assumed to be hard. Usually, the hardness of the assumption is against probabilistic polynomial-time adversaries. Here, probabilistic polynomial-time adversaries stand for the machines that attack the scheme with limited amount of time, and this amount of time is upper-bounded by a polynomial on input the security parameter given to the scheme. Probabilistic polynomial time is a notion in the theory of computation. If you would like to know more about the detail, we prefer to check some textbooks. For example, we prefer [Sipser2012-introduction-to-theory-of-computation] in this blog.

On the other hand, unconditional hiding means that we cannot extract any information about the polynomial behind. For example, if $f(X) = a_0 + a_1X + \dots + a_dX^d$ and $r(X) = r_0 + r_1X + \dots + r_dX^d$, given that $r_0, \dots, r_d$ are independently and uniformly sampled from $\mathbb{F}$, then $f(X) + r(X) = (a_0 + r_0) + (a_1 + r_1)X + \dots + (a_d + r_d)X^d$ completely hides $f(X)$ since $a_0 + r_0, a_1 + r_1, \dots, a_d + r_d$ are uniform in $\mathbb{F}$.

Conditional hiding from discrete logarithm assumption

The former, namely, discrete logarithm assumption, guarantees the hiding by its own hardness assumption. In particular, given $g$ and $g^v$ for some secret integer $v$, there is no way to extract any piece of information about $v$ from $g$ and $g^v$ due to hardness of discrete logarithm problem. Therefore, the hiding here is conditional, i.e., discrete logarithm assumption is hard.

Unconditional hiding from Pedersen commitment

The latter, namely, using Pedersen commitment, exploits the use of an additional part to achieve unconditional hiding property, which is secure against powerful adversaries and not limited to PPT ones. Roughly speaking, the external part can be informally thought of as a commitment to a random polynomial with conditional hiding. To perform this, we extend the commitment key $ck$ to contain additional elements $h^1, h^x, \dots, h^{x^d}$ where $h$ is another generator of $\mathbb{G}$ different from $g$. Hence, the commitment key $ck$ now is the tuple $(g^1, \dots, g^{x^d}, h^1, \dots, h^{x^d})$. Therefore, whenever committing to a polynomial $f(X) = a_0 + a_1X + \dots + a_dX^d$, we additionally sample a polynomial $r(X) = r_0 + r_1X + \dots + r_dX^d\in \mathbb{F}[X]$. The sampling process can be conducted easily by sampling each $r_i$ uniformly and independently from $\mathbb{Z}_{|F|} = \{0, \dots, |F| - 1\}$.

The algorithm $\textsf{Commit}$ now can be evaluated by computing $$ c = \prod_{i = 0}^d (g^{x^i})^{a_i} \cdot \prod_{i = 0}^d (h^{x^i})^{r_i} = g^{f(x)}\cdot h^{r(x)}, $$ namely, the original conditional-hiding commitment to $f(X)$ multiplying with the condition-hiding commitment to random polynomial $r(X)$ becomes an unconditional commitment $c$ where auxiliary information $\textsf{aux}$ can be set to be the tuple $(f(X), r(X))$. Hence, now, the adversary knows nothing about the evaluations of any index in $\mathbb{F}$. We can see clearly that the commitment $c$ hides $f(X)$ unconditionally since $r_0$ is chosen uniformly from $\mathbb{Z}_{|\mathbb{F}|}$ and, hence, $(h^{x^0})^{r_0}$ is uniform in $\mathbb{F}$. It also implies that $c$ is uniform in $\mathbb{F}$.

Since $c = g^{f(x)}\cdot h^{r(x)}$, we can say that $c$ is the multiplication of two parts, namely, the message part $g^{f(x)}$ and the randomness part $h^{r(x)}$.

We now discuss how algorithms $\textsf{CreateWitness}$ and $\textsf{VerifyEval}$ work with respect to introductory of the additional part, namely, $h^{r(x)}$.

Creating witness in unconditional hiding mode

For a given index $i$, the witness output by algorithm $\textsf{CreateWitness}$ is also a multiplication of $2$ parts. We simply call the message evaluation and randomness evaluation parts.

The message evaluation part is computed identically to the conditional version of the commitment scheme. That is, we compute the formula $g^{\psi(x)}$ where $\psi(X) = \frac{f(X) - f(i)}{X - i}$.

The randomness evaluation part is also conducted similarly. Notice that, since we employ $r(X)$ as a polynomial of degree $d$, we can compute witness for the correct evaluation on the same index $i$, namely, $r(i)$. This randomness evaluation part is equal to $h^{\varphi(x)}$ where $\varphi(X) = \frac{r(X) - r(i)}{X - i}$.

Remark. As previously said, $x$ is unknown to committer. Therefore, the computation of $g^{\psi(x)}$ and $h^{\varphi(x)}$ must depend on the commitment key $ck$ by employing the elements $g^1, \dots, g^{x^{d - 1}}, h^1, \dots, h^{x^{d - 1}}$. Notice that we do not you $g^{x^d}$ and $h^{x^d}$ since $\psi(X)$ and $\varphi(X)$ are polynomials of degrees at most $d - 1$.

The output of algorithm $\textsf{CreateWitness}$ is then equal to $w_i = (w^\star_i, s_i)$ where $w^\star_i = g^{\psi(x)} \cdot h^{\varphi(x)}$ is the multiplication of message evaluation and randomness evaluation parts and $s_i = r(i)$. Notice that $r(i)$ is attached to witness in order to help the evaluation verification algorithm, to be described below, work.

Verifying correct evaluation in unconditional mode

The evaluation verification algorithm $\textsf{VerifyEval}$ receives as inputs the commitment key $ck = (g^1, \dots, g^{x^d}, h^1, \dots, h^{x^d})$, commitment $c$ to $f(X)$, index $i$, value $v_i \in \mathbb{F}$ assumed to be equal to $f(i)$ and $w_i = (w^\star_i, s_i)$. This algorithm is expected to return $1$ is $v_i$ is equal to $f(i)$ with the use of associated witness $w_i$.

To verify whether $v_i = f(i)$, it is worth to verify both correct computations of $f(i)$ and $r(i)$. More precisely, verifier needs to confirm that $v_i = f(i)$ and $s_i = r(i)$. To this end, again, we imitate the verification process of the conditional hiding case. Hence, we employ again bilinear pairing $e : \mathbb{G}\times \mathbb{G} \to \mathbb{G}_T$ which maps $(g^a, g^b)$ to $e(g, g)^{ab}$. However, there is an obstacle here. Observe that, in this pairing, we use only $1$ generator $g$ while our commitment employs $2$ different generators $g$ and $h$ both generating $G$. In order to enable the bilinear pairing, we enforce $h = g^\gamma$ for some hidden $\gamma$. This enforcement works because $g$ is the generator of $\mathbb{G}$ and $h$ belongs to $\mathbb{G}$. Hence, our commitment $c$ can be alternatively written as $$ c = g^{f(x)}\cdot h^{r(x)} = g^{f(x)}\cdot g^{\gamma \cdot r(x)} = g^{f(x) + \gamma\cdot r(x)} $$ which is a conditional commitment to $f(X) + \gamma\cdot r(X)$ with $\gamma$ unknown to both committer and verifier.

Moreover, the witness $w^\star_i = g^{\psi(x)}\cdot h^{\varphi(x)}$ can also be interpreted as $$ w^\star_i = g^{\psi(x)}\cdot h^{\varphi(x)}=g^{\psi(x)} \cdot g^{\gamma\cdot \varphi(x)} = g^{\psi(x) + \gamma\cdot \varphi(x)} $$ which is also a witness for correct evaluation at index $i$ with respect to polynomial $f(X) + \gamma\cdot r(X)$ whose $\gamma$ is not known to both parties, namely, committer and verifier.

We now observe that $\psi(X) + \gamma\cdot \varphi(X) = \frac{f(X) - f(i)}{X - i} + \gamma\cdot \frac{r(X) - r(i)}{X - i}$. Hence, it is worth to guarantee the following equation holds: $$ \left(\frac{f(X) - f(i)}{X - i} + \gamma\cdot \frac{r(X) - r(i)}{X - i}\right)\cdot\left(X - i\right) - (f(i) + \gamma\cdot r(i)) = f(X) + \gamma \cdot r(X). $$

We now describe the process for verifying the above equation by employing the bilinear pairing function $g : \mathbb{G}\times \mathbb{G} \to \mathbb{G}_T$. Since the above equation has a multiplication, we apply the bilinear pairing by checking $$ e\left(g^{\frac{f(x) - v_i}{x - i} + \gamma\cdot \frac{r(x) - s_i}{x - i}}, g^{x - i}\right)\cdot e\left(g^{-\left(v_i + \gamma\cdot s_i\right)}, g\right) = e\left(g^{f(x) + \gamma\cdot r(x)},g\right) $$ where $x$ and $\gamma$ are unknown to both parties. Since $x$ and $\gamma$ are not known to both parties, it is inconvenient to evaluate the bilinear pairing function. However, since $ck = (g^1, \dots, g^{x^d}, h^1, \dots, h^{x^d})$ and $h = g^\gamma$ are public inputs, we can replace the appearances of $x$ and $\gamma$ in the above equation by those of $ck$ and $h$. The above computation of bilinear pairing hence becomes $$ e\left(w^\star, g^x / g^i\right)\cdot e\left(g^{-v_i}\cdot h^{-s_i}, g\right) = e(c, g) $$ since $c = g^{f(x)}\cdot h^{r(x)} = g^{f(x) + \gamma\cdot r(x)}$.

PlonK

In this chapter, we will present the construction of [GWC19], i.e., permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.

PlonK is a succinct non-interactive zero-knowledge argument (SNARK) system that proves the correct execution of a program, i.e., in this case, an arithmetic circuit with only addition $(+)$ and multiplication $(\cdot)$ operations.

As an overview of the construction, we separate it into $2$ parts. First, we transform the arithmetic circuit into a set of constraints, called arithmetization and represented under some form of polynomials. Then, by applying some proof technique, it compiles the arithmetization into the proof.

Author(s): khaihanhtang

Plonk's Arithmetization

PlonK's arithmetization [GWC19] breaks the circuit into a batch of gates, namely, multiplications, additions, multiplications with constants and additions with constants. For each gate, the operation is transformed into a unified form with respective selectors, uniquely determined by the gate without assigned inputs and output. On the other hand, since breaking circuit into gates introduces the inconsistencies among wires, we additionally apply copy constraints to wires to guarantee that such inconsistencies unavailable.

We describe circuit specification in Circuit Specification. Then, we discuss how to break the circuit into gates and label wires in Breaking Circuit. Then we present unified form of gate constraints in Gate Constraints and handling copy constraints in Copy Constraints.

Circuit Specification

Let $\mathbb{F}$ be a finite field. In this section, we describe the arithmetic circuit whose operations are over $\mathbb{F}$.

Let $\ell_{\mathsf{in}} \in \mathbb{N}$ be the number of input wires of the circuit $\mathcal{C}$. Assume that $\mathcal{C}$ has exactly $n$ gates. Each gate takes at most $2$ wires as inputs and returns $1$ output wires. In particular,

Addition and multiplications gates takes $2$ inputs and return $1$ output.
Gates of additions and multiplications with constants take $1$ input and return $1$ output.

Let's take a look at the following example.

Assume that $f(u, v) = u^2 + 3uv + v + 5$. Then the sequence are arranged in the following constraints, wrapped as below. $$ \begin{cases} z_1 = u \cdot u &\text{(multiplication)},\\ z_2 = u \cdot v &\text{(multiplication)},\\ z_3 = z_2 \cdot 3 &\text{(multiplication with constant)},\\ z_4 = z_1 + z_3 &\text{(addition)},\\ z_5 = z_4 + v &\text{(addition)},\\ z_6 = z_5 + 5 &\text{(addition with constant)}. \end{cases} $$ The input size is $\ell_{\mathsf{in}} = 2$ for variables $u, v$ and the output is $z_6$.

Breaking Circuit

To break the circuit into gates with wires separated, namely, no wire involves to $2$ or more gates, we use a set of labels $\mathcal{I} = \{a_1, \dots, a_n, b_1, \dots, b_n, c_1, \dots, c_n\}$ to denote the wire label of each gate. Let $x : \mathcal{I} \to \mathbb{F}$ be the function mapping wires to their respective wire values. Hence, $x(id)$ represents the value at wire $id \in \mathcal{I}$ For simplicity, we write $x_{id}$, in place of $x(id)$, for any $id \in \mathcal{I}$.

Specifically, for each $i \in \{1, \dots, n\}$, we denote by

$x_{c_i} = x_{a_i}\circ x_{b_i}$ to denote the computation where $\circ$ is either addition or multiplication.
$x_{c_i} = x_{a_i}\circ c$ to denote the computation where $\circ$ is either addition or multiplication with constant and $c$ is the constant.

At this point, we may be curious what value $x_{b_i}$ takes if $\circ$ is operation with constant. In fact, in this case x_{b_i} can be seen as garbage and can take any value from $\mathbb{F}$. This value will affect neither security nor correctness of the system since the constraints in PlonK's arithmetization guarantee that such a compromise will not happen.

Let's take a look at the following example, taken from Circuit Specification.

We have $f(u, v) = u^2 + 3uv + v + 5$ and the constraints below. $$ \begin{cases} z_1 = u \cdot u &\text{(multiplication)},\\ z_2 = u \cdot v &\text{(multiplication)},\\ z_3 = z_2 \cdot 3 &\text{(multiplication with constant)},\\ z_4 = z_1 + z_3 &\text{(addition)},\\ z_5 = z_4 + v &\text{(addition)},\\ z_6 = z_5 + 5 &\text{(addition with constant)}. \end{cases} $$ By breaking circuit, we have the following constraints with respect to the above format, namely, using $\mathcal{I} = \{a_1, \dots, a_6, b_1, \dots, b_6, c_1, \dots, c_6\}$, where $n = 6$, and $x : \mathcal{I}\to \mathbb{F}$. $$ \begin{cases} x_{c_1} = x_{a_1} \cdot x_{b_1},\\ x_{c_2} = x_{a_2} \cdot x_{b_2},\\ x_{c_3} = x_{a_3} \cdot 3,\\ x_{c_4} = x_{a_4} + x_{b_4},\\ x_{c_5} = x_{a_5} + x_{b_5}, \\ x_{c_6} = x_{a_6} + 5 \end{cases}\text{ where } \begin{cases} u = x_{a_1} = x_{a_2} = x_{b_1},\\ v = x_{b_2} = x_{b_5},\\ z_1 = x_{a_4} = x_{c_1},\\ z_2 = x_{a_3} = x_{c_2},\\ z_3 = x_{b_4} = x_{c_3},\\ z_4 = x_{a_5} = x_{c_4},\\ z_5 = x_{a_6} = x_{c_5},\\ z_6 = x_{c_6}.\
\end{cases} $$ Notice that $v_{b_3}$ and $v_{b_6}$ are dismissed. These values can be any elements from \mathbb{F} and do not have any effect to the arithmetization.

For equations in the system guaranteeing the correct computation of the operation, we call them gate constraints.

For equations in the system guaranteeing the equalities, or consistencies, among wires, we call them copy constraints.

We first discuss the transformation of gate constraints into a common unified form with publicly determined selectors in Gate Constraints. Then, we discuss the method for guaranteeing copy constraints in Copy Constraints.

Gate constraints

At this stage, for each $i \in \{1,\dots, n\}$, we need to transform the computation of each gate to a unified form as follows: $$q^O_i \cdot x_{c_i} + q^L_i \cdot x_{a_i} + q^R_i \cdot x_{b_i} + q^M_i \cdot (x_{a_i} \cdot x_{b_i}) + q^C_i = 0$$ where $q_i^O, q_i^L, q_i^R, q_i^M, q_i^C$ are selectors uniquely determined by the corresponding gate. In particular,

For addition gate, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, 1, 1, 0, 0)$ since $(-1) \cdot x_{c_i} + 1 \cdot x_{a_i} + 1 \cdot x_{b_i} + 0 \cdot (x_{a_i} \cdot x_{b_i}) + 0 = 0$ is equivalent to $x_{c_i} = x_{a_i} + x_{b_i}$.
For multiplication gate, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, 0, 0, 1, 0)$ since $(-1) \cdot x_{c_i} + 0 \cdot x_{a_i} + 0 \cdot x_{b_i} + 1 \cdot (x_{a_i} \cdot x_{b_i}) + 0 = 0$ is equivalent to $x_{c_i} = x_{a_i} \cdot x_{b_i}$.
For gate of addition with constant, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, 1, 0, 0, c)$ since $(-1) \cdot x_{c_i} + 1 \cdot x_{a_i} + 0 \cdot x_{b_i} + 0 \cdot (x_{a_i} \cdot x_{b_i}) + c = 0$ is equivalent to $x_{c_i} = x_{a_i} + c$.
For gate of multiplication with constant, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, c, 0, 0, 0)$ since $(-1) \cdot x_{c_i} + c \cdot x_{a_i} + 0 \cdot x_{b_i} + 0 \cdot (x_{a_i} \cdot x_{b_i}) + 0 = 0$ is equivalent to $x_{c_i} = x_{a_i} \cdot c$.

We now take a look at the example achieved above, i.e., $$ \begin{cases} x_{c_1} = x_{a_1} \cdot x_{b_1},\\ x_{c_2} = x_{a_2} \cdot x_{b_2},\\ x_{c_3} = x_{a_3} \cdot 3,\\ x_{c_4} = x_{a_4} + x_{b_4},\\ x_{c_5} = x_{a_5} + x_{b_5}, \\ x_{c_6} = x_{a_6} + 5. \end{cases} $$ In this example, we can transform the above system of equation into the unified form as follows: $$ \begin{cases} (-1) \cdot x_{c_1} + 0 \cdot x_{a_1} + 0 \cdot x_{b_1} + 1 \cdot (x_{a_1} \cdot x_{b_1}) + 0 = 0,\\ (-1) \cdot x_{c_2} + 0 \cdot x_{a_2} + 0 \cdot x_{b_2} + 1 \cdot (x_{a_2} \cdot x_{b_2}) + 0 = 0,\\ (-1) \cdot x_{c_3} + 3 \cdot x_{a_3} + 0 \cdot x_{b_3} + 0 \cdot (x_{a_3} \cdot x_{b_3}) + 0 = 0,\\ (-1) \cdot x_{c_4} + 1 \cdot x_{a_4} + 1 \cdot x_{b_4} + 0 \cdot (x_{a_4} \cdot x_{b_4}) + 0 = 0,\\ (-1) \cdot x_{c_5} + 1 \cdot x_{a_5} + 1 \cdot x_{b_5} + 0 \cdot (x_{a_5} \cdot x_{b_5}) + 0 = 0,\\ (-1) \cdot x_{c_6} + 1 \cdot x_{a_6} + 0 \cdot x_{b_6} + 0 \cdot (x_{a_6} \cdot x_{b_6}) + 5 = 0. \end{cases} $$

Copy Constraints

Recall that gate constraints do not enforce the equalities of wire values making inconsistencies across the circuit. We generalize copy constraints to the following problem.

Let $k \in \{1, \dots, 3n\}$ and $\{i_1, \dots, i_k\} \subseteq \mathcal{I}$ satisfying $i_1 < i_2 < \dots < i_k$. We would like to show that $$ x_{i_1} = x_{i_2} = \dots = x_{i_k}. $$

The technique for proving this problem is tricky. We form the pairs of index-value and make them into a sequence $$ \big((i_1, x_{i_1}), (i_2, x_{i_2}), \dots, (i_k, x_{i_k})\big). $$ It can be observed that if $x_{i_1} = x_{i_2} = \dots = x_{i_k}$, then, if we rotate the indices among the pairs, we achieve a sequence
$$ \big((i_k, x_{i_1}), (i_1, x_{i_2}), \dots, (i_{k - 1}, x_{i_k})\big) $$ that is permutation of the previous sequence. Notice that we just rotated the indices $1$ step to the left and this is the recommended rotation. This fact helps imply the other direction of the fact. For more details, we use the following observation

Observation. $\big((i_1, x_{i_1}), (i_2, x_{i_2}), \dots, (i_k, x_{i_k})\big)$ is a permutation of $\big((i_k, x_{i_1}), (i_1, x_{i_2}), \dots, (i_{k - 1}, x_{i_k})\big)$ if and only if $x_{i_1} = x_{i_2} = \dots = x_{i_k}$.

Proof. The proof is as follows:

"$\Leftarrow$": This direction is straightforward.

"$\Rightarrow$": Since the two sequences are permutation of each other, for $j \in \{1, \dots, k\}$ we consider $(i_j, x_{i_j})$ from the first sequence. It can be seen that $(i_j, x_{i_{(j \mod k) + 1}})$ from the second sequence is the only one that is equal $j \in \{1, \dots, k\}$ since they share the unique prefix $i_j$. Hence, $x_{i_j} = x_{i_{(j \mod k) + 1}}$. Following this argument, we see that $x_{i_1} = x_{i_2}, x_{i_2} = x_{i_3}, \dots, x_{i_{k - 1}} = x_{i_k}, x_{i_k} = x_{i_1}$. Thus, $x_{i_1} = x_{i_2} = \dots = x_{i_k}$.

General paradigm for proving copy constraints of the entire circuit

Recall that $x : \mathcal{I} \to \mathbb{F}$. We can deterministically determine a partition of $\mathcal{I}$ such that $$ \mathcal{I} = \bigcup_{j = 1}^{\ell_{\mathsf{in}} + n} \mathcal{I}_j $$

where $\ell_{\mathsf{in}} + n$ is the number of wires of the original circuits, namely, $\ell_{\mathsf{in}}$ input wires and $n$ output wires of all gates. Hence each subset $\mathcal{I}_j$ is the set of wire labels whose value are all equal to the same wire value of the original circuit. We hence obtain a rotation of indices for each subset $\mathcal{I}_j$. By unifying all those rotations, we achieve a permutation $\sigma : \mathcal{I}\to\mathcal{I}$ such that

$$ \big((a_1, x_{a_1}), \dots, (a_n, x_{a_n}), (b_1, x_{b_1}), \dots, (b_n, x_{b_n}), (c_1, x_{c_1}), \dots, (c_n, x_{c_n})\big) $$

is a permutation of

$$ \big((\sigma(a_1), x_{a_1}), \dots, (\sigma(a_n), x_{a_n}), (\sigma(b_1), x_{b_1}), \dots, (\sigma(b_n), x_{b_n}), (\sigma(c_1), x_{c_1}), \dots, (\sigma(c_n), x_{c_n})\big). $$ Such guaranteed permutation relation implies the consistencies among wires of the circuit.

Recall the example in Breaking Circuit with the following copy constraints. $$ \begin{cases} u = x_{a_1} = x_{a_2} = x_{b_1},\\ v = x_{b_2} = x_{b_5},\\ z_1 = x_{a_4} = x_{c_1},\\ z_2 = x_{a_3} = x_{c_2},\\ z_3 = x_{b_4} = x_{c_3},\\ z_4 = x_{a_5} = x_{c_4},\\ z_5 = x_{a_6} = x_{c_5},\\ z_6 = x_{c_6}.\
\end{cases} $$ We achieve the partition $$ \big\{\{a_1, a_2, b_1\}, \{b_2, b_5\}, \{a_4, c_1\}, \{a_3, c_2\}, \{b_4, c_3\}, \{a_5, c_4\}, \{a_6, c_5\}, \{c_6\}\big\}. $$ We hence can achive the permutation $\sigma: \mathcal{I}\to\mathcal{I}$ as follows: $$ \begin{array}[ccc]\\ \sigma(a_1) = b_1, &\sigma(a_2) = a_1, &\sigma(b_1) = a_2,\\ \sigma(b_2) = b_5, &\sigma(b_5) = b_2,\\ \sigma(a_4) = c_1, &\sigma(c_1) = a_4,\\ \sigma(a_3) = c_2, &\sigma(c_2) = a_3,\\ \sigma(b_4) = c_3, &\sigma(c_3) = b_4,\\ \sigma(a_5) = c_4, &\sigma(c_4) = a_5,\\ \sigma(a_6) = c_5, &\sigma(c_5) = a_6,\\ \sigma(c_6) = c_6. \end{array} $$

Halo 2 for Dummies

Halo 2 is succint non-interactive zero-knowledge argument of knowledge (zkSNARK) library for developing applications with an associated zkSNARK in order to prove their honesty in computing the programs. In this chapter, I present a simple implementation of a program, under the form of a $2$-variable polynomial, by using Halo 2.

Author(s): khaihanhtang

PLONKish Arithemetization

We recommend readers who are not familiar with PlonK's arithmetization to read the article PlonK's Arithmetization. In this chapter, we further discuss a more customized version of PlonK's arithmetization, namely, PLONKish arithmetization. Customization aims to handle more general gates with more complicated structures rather than employing only multiplication, addition, multiplication with constants and addition with constants gates.

PLONKish arithmetization can be pictured as a table of the following types of columns:

Constant columns for putting constants,
Instant columns for putting public inputs,
Advice columns for putting private inputs, literally known as witnesses,
Selector columns for putting selectors.

For simplicity, in this section, we present a transformation from a program, represented by an arithmetic circuit, to the form of PLONKish arithmetization. This transformation can be showed by an example that proves the knowledge of a $2$-variable polynomial specified in A Simple Arithmetic Circuit. Then, we explain the method for transforming this polynomial to the form of PLONKish arithmetization in Transforming to PLONKish Arithmetization and programming in A Simple Halo 2 Program.

A Simple Arithmetic Circuit

Let $\mathbb{F}$ be some finite field. We would like to show in this section the transformation from the program computing polynomial $f(u, v) = u^2 + 3uv + v + 5 $ where $u, v \in \mathbb{F}$. With inputs $u, v \in \mathbb{F}$, the arithmetic circuit for this polynomial is equivalently represented by topologically following the sequence of computations below.

Compute $u^2$.
Compute $uv$.
Compute $3uv$.
Compute $u^2 + 3uv$.
Compute $u^2 + 3uv + v$.
Compute $u^2 + 3uv + v + 5$.

Transforming to PLONKish Arithmetization

To setup the above sequence of computations, in A Simple Arithmetic Circuit, into PLONKish arithmetization, we specify a table to contain all possible variables appeared during the computing the arithmetic circuit for $f(u,v) = u^2 + 3uv + v + 5$. Then, for each row, we setup a the set gates, or equivalently gate constraints, that applies to the row.

Specifying columns

We define the following tuple of columns $$ (\mathsf{advice} _0, \mathsf{advice} _1, \mathsf{advice} _2, \mathsf{constant}, \mathsf{selector} _{\mathsf{add}}, \mathsf{selector} _{\mathsf{mul}}, \mathsf{selector} _{\mathsf{addc}}, \mathsf{selector} _{\mathsf{mulc}}) $$ where

$\mathsf{advice}_0, \mathsf{advice}_1, \mathsf{advice}_2$ are columns containing private inputs, i.e., values belonging to these columns are hidden to any verifier,
$\mathsf{constant}$ is the column containing public constants appearing during the computation,
$\mathsf{selector} _{\mathsf{add}}, \mathsf{selector} _{\mathsf{mul}}, \mathsf{selector} _{\mathsf{addc}}, \mathsf{selector} _{\mathsf{mulc}}$ contain public selectors corresponding to addition, multiplication, addition with constant, multiplication with constant, respectively, gates.

Transforming to Constraints and Meaning of Columns

We now explain the intuition to the above setting of columns. To do this, we need to transform the sequence of computations in A Simple Arithmetic Circuit into $2$ parts, namely, gate constraints (or gate identities) and wire constraints (or wire identities). In particular, we transform $$ \begin{align}
t^{(1)} &= u^2, &t^{(3)} &= t^{(2)} \cdot 3 = 3uv, & t^{(5)} &= t^{(4)} + v = u^2 + 3uv + v,\\ t^{(2)} &= u v, & t^{(4)} &= t^{(1)} + t^{(3)} = u^2 + 3uv, &t^{(6)} &= t^{(5)} + 5 = u^2 + 3uv + v + 5 \end{align} $$ to gate constraints

$$ \begin{align} x ^{(1)} _{c} &= x ^{(1)} _{a} \cdot x ^{(1)} _{b}, & x ^{(3)} _{c} &= x ^{(3)} _{a} \cdot 3, & x ^{(5)} _{c} &= x ^{(5)} _{a} + x ^{(5)} _{b},\\ x ^{(2)} _{c} &= x ^{(2)} _{a} \cdot x ^{(2)} _{b}, & x ^{(4)} _{c} &= x ^{(4)} _{a} + x ^{(4)} _{b}, & x ^{(6)} _{c} &= x ^{(6)} _{a} + 5 \end{align} $$

and wire constraints

$$ \begin{align} u &= x_{a}^{(1)} = x_{a}^{(2)} = x_{b}^{(1)}, &t^{(1)} &= x_{a}^{(4)} = x_{c}^{(1)}, &t^{(3)} &= x_{b}^{(4)} = x_{c}^{(3)}, &t^{(5)} &= x_{a}^{(6)} = x_{c}^{(5)},\\ v &= x_{b}^{(2)} = x_{b}^{(5)}, &t^{(2)} &= x_{a}^{(3)} = x_{c}^{(2)}, &t^{(4)} &= x_{a}^{(5)} = x_{c}^{(4)}, &t^{(6)} &= x_{c}^{(6)}. \end{align} $$

We note that $x_b^{(3)}, x_b^{(6)}$ are not set. To deal with these values, we simple set them to be equal to any random vales, since they do not affect the constraints defined above.

Notice that each equation in gate constrains receives either $2$ secret inputs or $1$ secret input and $1$ constant and returns $1$ secret output. Therefore, we use $2$ columns, namely, $\mathsf{advice}_0$ and $\mathsf{advice}_1$, to contain the secret inputs and $1$ column, namely, $\mathsf{advice}_2$, to contain the secret output. Moreover, we also use the column $\mathsf{constant}$ to contain possible public constants.

The remaining columns, namely, $\mathsf{selector} _{\mathsf{add}}, \mathsf{selector} _{\mathsf{mul}}, \mathsf{selector} _{\mathsf{addc}}, \mathsf{selector} _{\mathsf{mulc}}$, are employed to contain the selectors indicating the required constraints for each row, which corresponds to a constraint in the set of gate constraints specified above. We now clarify the employment of selectors to guarantee the correctness of gate constraints.

Specifying Table Values and Gate Constraints

For each row $i \in \{1, \dots, 6\}$ of the table, we denote by the tuple $$ (x_{a}^{(i)}, x_{b}^{(i)}, x_{c}^{(i)}, c^{(i)}, s_{\mathsf{add}}^{(i)}, s_{\mathsf{mul}}^{(i)}, s_{\mathsf{addc}}^{(i)}, s_{\mathsf{mulc}}^{(i)}) $$ corresponding to the tuple of columns $$ (\mathsf{advice} _0, \mathsf{advice} _1, \mathsf{advice} _2, \mathsf{constant}, \mathsf{selector} _{\mathsf{add}}, \mathsf{selector} _{\mathsf{mul}}, \mathsf{selector} _{\mathsf{addc}}, \mathsf{selector} _{\mathsf{mulc}}) $$ devised above.

For each row $i \in \{1,\dots, 6\}$, we set the following $4$ constraints $$ \begin{align} s_\mathsf{add}^{(i)}\cdot (x_{a}^{(i)} + x_{b}^{(i)} - x_{c}^{(i)}) &= 0, & s_\mathsf{mul}^{(i)}\cdot (x_{a}^{(i)} \cdot x_{b}^{(i)} - x_{c}^{(i)}) &= 0,\\ s_\mathsf{addc}^{(i)}\cdot (x_{a}^{(i)} + c^{(i)} - x_{c}^{(i)}) &= 0, & s_\mathsf{mulc}^{(i)}\cdot (x_{a}^{(i)} \cdot c^{(i)} - x_{c}^{(i)}) &= 0. \end{align} $$

Example. Assume that the $i$-th row corresponds to a multiplication gate. Hence, in this case, we set $(s_{\mathsf{add}}^{(i)}, s_{\mathsf{mul}}^{(i)}, s_{\mathsf{addc}}^{(i)}, s_{\mathsf{mulc}}^{(i)}) = (0, 1, 0, 0)$. We can see that only $s_{\mathsf{mul}}^{(i)} = 1$ while remaining selectors are set to $0$.

Therefore, whatever the values $x_{a}^{(i)}, x_{b}^{(i)}, x_{c}^{(i)}, c^{(i)}$ are set, the results always hold with respect to the gates $s_\mathsf{add}^{(i)}\cdot (x_{a}^{(i)} + x_{b}^{(i)} - x_{c}^{(i)}) = 0, s_\mathsf{addc}^{(i)}\cdot (x_{a}^{(i)} + c^{(i)} - x_{c}^{(i)}) = 0$ and $s_\mathsf{mulc}^{(i)}\cdot (x_{a}^{(i)} \cdot c^{(i)} - x_{c}^{(i)}) = 0$.

However, since $s_{\mathsf{mul}}^{(i)} = 1$, we can see that the gate $s_\mathsf{mul}^{(i)}\cdot (x_{a}^{(i)} \cdot x_{b}^{(i)} - x_{c}^{(i)}) = 0$ must guarantee $x_{a}^{(i)} \cdot x_{b}^{(i)} = x_{c}^{(i)}$.

A Simple Halo 2 Program

Based on the specifications in Transforming to PLONKish Arithmetization, we now show an implementation in Rust for proving knowledge of input of $f(u, v) = u^2 + 3uv + v + 5$ mentioned in A Simple Arithmetic Circuit. The implementation can be found in Example of Halo2-PSE.

The following are a recommended for setting up a Rust implementation for Halo 2.

In Cargo.toml, specify the dependency

#![allow(unused)]
fn main() {
[dependencies]
halo2_proofs = { git = "https://github.com/privacy-scaling-explorations/halo2.git" }
}

In main.rs, we implement step-by-step as follows:

Specify columns by putting all possible columns into a custom struct MyConfig.

#![allow(unused)]
fn main() {
#[derive(Clone, Debug)]
struct MyConfig {
    advice: [Column<Advice>; 3],
    instance: Column<Instance>,
    constant: Column<Fixed>,

    // selectors
    s_add: Selector,
    s_mul: Selector,
    s_add_c: Selector,
    s_mul_c: Selector,
}
}

Define gates based on elements of the above defined struct.

#![allow(unused)]
fn main() {
impl<Field: FieldExt> FChip<Field> {
    fn configure(
        meta: &mut ConstraintSystem<Field>,
        advice: [Column<Advice>; 3],
        instance: Column<Instance>,
        constant: Column<Fixed>,
    ) -> <Self as Chip<Field>>::Config {
        // specify columns used for proving copy constraints
        meta.enable_equality(instance);
        meta.enable_constant(constant);
        for column in &advice {
            meta.enable_equality(*column);
        }

        // extract columns with respect to selectors
        let s_add = meta.selector();
        let s_mul = meta.selector();
        let s_add_c = meta.selector();
        let s_mul_c = meta.selector();

        // define addition gate
        meta.create_gate("add", |meta| {
            let s_add = meta.query_selector(s_add);
            let lhs = meta.query_advice(advice[0], Rotation::cur());
            let rhs = meta.query_advice(advice[1], Rotation::cur());
            let out = meta.query_advice(advice[2], Rotation::cur());
            vec![s_add * (lhs + rhs - out)]
        });

        // define multiplication gate
        meta.create_gate("mul", |meta| {
            let s_mul = meta.query_selector(s_mul);
            let lhs = meta.query_advice(advice[0], Rotation::cur());
            let rhs = meta.query_advice(advice[1], Rotation::cur());
            let out = meta.query_advice(advice[2], Rotation::cur());
            vec![s_mul * (lhs * rhs - out)]
        });

        // define addition with constant gate
        meta.create_gate("add with constant", |meta| {
            let s_add_c = meta.query_selector(s_add_c);
            let lhs = meta.query_advice(advice[0], Rotation::cur());
            let fixed = meta.query_fixed(constant, Rotation::cur());
            let out = meta.query_advice(advice[2], Rotation::cur());
            vec![s_add_c * (lhs + fixed - out)]
        });

        // define multiplication with constant gate
        meta.create_gate("mul with constant", |meta| {
            let s_mul_c = meta.query_selector(s_mul_c);
            let lhs = meta.query_advice(advice[0], Rotation::cur());
            let fixed = meta.query_fixed(constant, Rotation::cur());
            let out = meta.query_advice(advice[2], Rotation::cur());
            vec![s_mul_c * (lhs * fixed - out)]
        });

        MyConfig {
            advice,
            instance,
            constant,
            s_add,
            s_mul,
            s_add_c,
            s_mul_c,
        }
    }
}
}

Put values to the table and define wire constraints.

#![allow(unused)]
fn main() {
impl<Field: FieldExt> Circuit<Field> for MyCircuit<Field> {
    type Config = MyConfig;
    type FloorPlanner = SimpleFloorPlanner;

    fn without_witnesses(&self) -> Self {
        Self::default()
    }

    fn configure(meta: &mut ConstraintSystem<Field>) -> Self::Config {
        let advice = [meta.advice_column(), meta.advice_column(), meta.advice_column()];
        let instance = meta.instance_column();
        let constant = meta.fixed_column();
        FChip::configure(meta, advice, instance, constant)
    }

    fn synthesize(
        &self, config: Self::Config, mut layouter: impl Layouter<Field>
    ) -> Result<(), Error> {
        // handling multiplication region
        let t1 = self.u * self.u;
        let t2 = self.u * self.v;
        let t3 = t2 * Value::known(Field::from(3));

        // define multiplication region
        let (
            (x_a1, x_b1, x_c1),
            (x_a2, x_b2, x_c2),
            (x_a3, x_c3)
        ) = layouter.assign_region(
            || "multiplication region",
            |mut region| {
                // first row
                config.s_mul.enable(&mut region, 0)?;
                let x_a1 = region.assign_advice(|| "x_a1",
                    config.advice[0].clone(), 0, || self.u)?;
                let x_b1 = region.assign_advice(|| "x_b1",
                    config.advice[1].clone(), 0, || self.u)?;
                let x_c1 = region.assign_advice(|| "x_c1",
                    config.advice[2].clone(), 0, || t1)?;

                // second row
                config.s_mul.enable(&mut region, 1)?;
                let x_a2 = region.assign_advice(|| "x_a2",
                    config.advice[0].clone(), 1, || self.u)?;
                let x_b2 = region.assign_advice(|| "x_b2",
                    config.advice[1].clone(), 1, || self.v)?;
                let x_c2 = region.assign_advice(|| "x_c2",
                    config.advice[2].clone(), 1, || t2)?;

                // third row
                config.s_mul_c.enable(&mut region, 2)?;
                let x_a3 = region.assign_advice(|| "x_a3",
                    config.advice[0].clone(), 2, || t2)?;
                region.assign_fixed(|| "constant 3",
                    config.constant.clone(), 2, || Value::known(Field::from(3)))?;
                let x_c3 = region.assign_advice(|| "x_c3",
                    config.advice[2].clone(), 2, || t3)?;

                Ok((
                    (x_a1.cell(), x_b1.cell(), x_c1.cell()),
                    (x_a2.cell(), x_b2.cell(), x_c2.cell()),
                    (x_a3.cell(), x_c3.cell())
                ))
            }
        )?;

        let t4 = t1 + t3;
        let t5 = t4 + self.v;
        let t6 = t5 + Value::known(Field::from(5));

        // define addition region
        let (
            (x_a4, x_b4, x_c4),
            (x_a5, x_b5, x_c5),
            (x_a6, x_c6)
        ) = layouter.assign_region(
            || "addition region",
            |mut region| {
                // first row
                config.s_add.enable(&mut region, 0)?;
                let x_a4 = region.assign_advice(|| "x_a4",
                    config.advice[0].clone(), 0, || t1)?;
                let x_b4 = region.assign_advice(|| "x_b4",
                    config.advice[1].clone(), 0, || t3)?;
                let x_c4 = region.assign_advice(|| "x_c4",
                    config.advice[2].clone(), 0, || t4)?;

                // second row
                config.s_add.enable(&mut region, 1)?;
                let x_a5 = region.assign_advice(|| "x_a5",
                    config.advice[0].clone(), 1, || t4)?;
                let x_b5 = region.assign_advice(|| "x_b5",
                    config.advice[1].clone(), 1, || self.v)?;
                let x_c5 = region.assign_advice(|| "x_c5",
                    config.advice[2].clone(), 1, || t5)?;

                // third row
                config.s_add_c.enable(&mut region, 2)?;
                let x_a6 = region.assign_advice(|| "x_a6",
                    config.advice[0].clone(), 2, || t5)?;
                region.assign_fixed(|| "constant 5",
                    config.constant.clone(), 2, || Value::known(Field::from(5)))?;
                let x_c6 = region.assign_advice(|| "x_c6",
                    config.advice[2].clone(), 2, || t6)?;
                Ok((
                    (x_a4.cell(), x_b4.cell(), x_c4.cell()),
                    (x_a5.cell(), x_b5.cell(), x_c5.cell()),
                    (x_a6.cell(), x_c6.cell())
                ))
            }
        )?;

        // t6 is result, assign instance
        layouter.constrain_instance(x_c6, config.instance, 0)?;

        // enforce copy constraints
        layouter.assign_region(|| "equality",
            |mut region| {
                region.constrain_equal(x_a1, x_a2)?; // namely, x_a1 = x_a2
                region.constrain_equal(x_a2, x_b1)?; // namely, x_a2 = x_b1

                region.constrain_equal(x_b2, x_b5)?; // namely, x_b2 = x_b5

                region.constrain_equal(x_a4, x_c1)?; // namely, x_a4 = x_c1

                region.constrain_equal(x_a3, x_c2)?; // namely, x_a3 = x_c2

                region.constrain_equal(x_b4, x_c3)?; // namely, x_b4 = x_c3

                region.constrain_equal(x_a5, x_c4)?; // namely, x_a5 = x_c4

                region.constrain_equal(x_a6, x_c5)?; // namely, x_a6 = x_c5
                Ok(())
            }
        )?;
        Ok(())
    }
}
}

N/A

Orochi Network's Cookbook