Skip to content

Latest commit

 

History

History
587 lines (355 loc) · 29.2 KB

chip-0011.md

File metadata and controls

587 lines (355 loc) · 29.2 KB
Raw
CHIP Number 0011
Title BLS/SECP CLVM Operators and SOFTFORK Condition
Description Add CLVM operators to increase signature capabilities; also add a new SOFTFORK condition
Author Cameron Cooper, Arvid Norberg, Dan Perry
Editor Freddie Coleman
Comments-URI https://github.com/Chia-Network/chips/wiki/Comments:CHIP-0011
Status Final
Category Standards Track
Sub-Category Chialisp
Created 2022-12-16
Requires 0012
Replaces None
Superseded-By None

Abstract

This CHIP will add a set of new operators to the CLVM. These operators will enable complex BLS operations, as well as new functionality such as ZK proofs, the ability to calculate a remainder, the ability to calculate a coin ID from its component parts, and the ability to verify secp signatures. Initially, the operators will be accessible from behind the softfork guard. Later, they will become part of the core CLVM.

This CHIP will also add a new SOFTFORK condition, which will become available after the hard fork from CHIP-12 has activated. This fork will also add the ability to create new CLVM conditions with cost, as well as six new AGG_SIG conditions.

Definitions

Throughout this document, we'll use the following terms:

  • Chialisp - The high-level programming language from which Chia coins are constructed
  • CLVM - Chialisp Virtual Machine, where the bytecode from compiled Chialisp is executed. Also commonly refers to the compiled bytecode itself
  • BLS - Boneh–Lynn–Shacham, a digital signature scheme that supports aggregation. Chia has been using BLS keys since before the launch of mainnet
  • secp - A set of elliptic curves from the Standards for Efficient Cryptography
  • G1 - The first group of points on a BLS elliptic curve; where public keys are held
  • G2 - The second group of points on a BLS elliptic curve; where digital signatures are held
  • Gt - The target group of the G1 and G2 points, defined as G1 x G2 → Gt
  • ZK proofs - Zero-knowledge proofs, a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true

Motivation

CLVM currently includes a BLS operator called point_add. This operator is used for G1 addition, and was needed to support synthetic keys. However, CLVM lacks the operators necessary to perform more complex operations, such as signature verification.

This CHIP will add a new set of operators to CLVM in order to utilize the full capabilities of BLS signatures. For example, the new operators will add the ability to verify signatures and to use ZK proofs.

In addition, CLVM currently lacks a way to calculate a coin ID while validating its components. To solve this, a new operator will be added to the CLVM that calculates a coin ID from its parent coin ID, puzzle-hash, and amount. The operator will fail if any of the arguments are invalid.

CLVM also lacks operators for directly calculating a remainder from division, as well as a remainder from division of an exponential operation. To solve this, two new operators will be added.

Finally, CLVM currently lacks the ability to verify secp signatures. To solve this, two new operators will be added to the CLVM, one to verify secp256k1 signatures, and one to verify secp256r1 signatures.

CLVM is an extensible on-chain programming language, so adding new operators is not a large technical challenge.

Backwards Compatibility

A few notes regarding this CHIP's compatibility with the current implementation of CLVM:

  • The CLVM operators to be added are backwards compatible -- any calls that succeed after the CHIP has been implemented also would have succeeded beforehand
  • The CLVM operators to be added are not forward compatible -- some calls that succeed before the CHIP has been implemented will no longer succeed afterward
  • Because of the forward incompatibility of the operators to be added, this CHIP will require a soft fork of Chia's blockchain
  • The operators to be added are unlikely to be contentious. However, as with all forks, there will be a risk of a chain split
  • The soft fork could also fail to be adopted. This might happen if an insufficient number of nodes have upgraded to include the changes introduced by this CHIP prior to the fork's block height

The operators will be introduced in multiple phases:

  • Pre-CHIP: Prior to block 4 510 000, any attempt to call the new operators will result in a successful no-op
  • Soft fork: A soft fork will activate at block 4 510 000. From that block forward, the new operators will exhibit the functionality laid out in this CHIP. They will need to be called with the new syntax of the softfork operator (from inside the softfork guard). This syntax is explained in the Specification section of this CHIP
  • Hard fork: A hard fork will activate at block 5 496 000. This hard fork is a result of CHIP-12, which is otherwise unrelated to this CHIP. From block 5 496 000 forward, the operators introduced in this CHIP may also be called without using the softfork operator (from outside the softfork guard). In other words, the new operators will be added to the core CLVM operator set. (Note that the operators will still be callable from inside the softfork guard if desired)

Rationale

This CHIP's design was primarily chosen for its standardized implementation. It includes consistent methods for adding, subtracting, multiplying and negating BLS points. In keeping with this consistency, this proposal also includes a mapping from point_add to g1_add.

Another aspect of this CHIP's design is its enhanced cross-functionality between multiple BLS groupings. The design includes the ability to pair points from different groupings, as well the ability to add arbitrary data to G1 and G2 points.

Each of the new operators will incur a CLVM cost, as detailed below. If this CHIP is adopted, the new operators will be optional when designing Chia coins.

Specification

BLS Operators

To support the necessary set of available BLS operations within the CLVM, math primitives on G1 and G2 points are required, along with functions for pairing and mapping those points. Therefore, the following operators will be added:

g1_add

Opcode: 29

Functionality: Add two or more G1 points

Note: This operator is already implemented in CLVM as point_add. For consistency and ease of use, a new compiler macro will be created to map point_add to g1_add so either name can be used with full backward compatibility.

Arguments:

  • If zero arguments, the G1 identity will be returned
  • If one argument, the result will be a successful no-op
  • If two or more arguments, each argument must be a G1 point; the result will be the sum of the arguments

Usage: (g1_add point1 point2 … pointn)

CLVM Cost: 101 094 base, 1 343 980 per argument

g1_subtract

Opcode: 49

Functionality: Subtract one or more G1 points from a base G1 point

Arguments:

  • If zero arguments, the G1 identity will be returned
  • If one argument, the result will be a successful no-op
  • If two or more arguments, must include a base G1 point (point1), followed by one or more G1 points to subtract from the base G1 point

Usage: (g1_subtract point1 point2 … pointn)

CLVM Cost: 101 094 base, 1 343 980 per argument

g1_multiply

Opcode: 50

Functionality: Multiply a G1 point by a scalar value

Arguments: A single G1 point (point1) and a single scalar value (scalar)

Usage: (g1_multiply point1 scalar)

CLVM Cost: 705 500 base, 10 per byte in the scalar

g1_negate

Opcode: 51

Functionality: Negate a G1 point

Arguments: A single G1 point

Usage: (g1_negate point1)

CLVM Cost: 916

g2_add

Opcode: 52

Functionality: Add two or more G2 points

Arguments:

  • If zero arguments, the G2 identity will be returned
  • If one argument, the result will be a successful no-op
  • If two or more arguments, each argument must be a G2 point; the result will be the sum of the arguments

Usage: (g2_add point1 point2 … pointn)

CLVM Cost: 80 000 base, 1 950 000 per argument

g2_subtract

Opcode: 53

Functionality: Subtract one or more G2 points from a base G2 point

Arguments:

  • If zero arguments, the G2 identity will be returned
  • If one argument, the result will be a successful no-op
  • If two or more arguments, must include a base G2 point (point1), followed by one or more G2 points to subtract from the base G2 point

Usage: (g2_subtract point1 point2 … pointn)

CLVM Cost: 80 000 base, 1 950 000 per argument

g2_multiply

Opcode: 54

Functionality: Multiply a G2 point by a scalar value

Arguments: A single G2 point (point1) and a single scalar value (scalar)

Usage: (g2_multiply point1 scalar)

CLVM Cost: 2 100 000 base, 5 per byte in the scalar

g2_negate

Opcode: 55

Functionality: Negate a G2 point

Arguments: A single G2 point

Usage: (g2_negate point1)

CLVM Cost: 1204

g1_map

Opcode: 56

Functionality: Map arbitrary data to a G1 point. Hashes the specified message to G1 using SHA-256 and ExpandMsgXmd, with a either the specified DST (Domain Separation Tag), or a default DST

Arguments: The first argument (required) is the data; the second argument (optional) is a custom DST. If the second argument is not used, the default DST of BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_ will be used instead

Usage: (g1_map data dst)

CLVM Cost: 195 000 base, 4 per byte, 4 per DST byte

g2_map

Opcode: 57

Functionality: Map arbitrary data to a G2 point. Hashes the specified message to G2 using SHA-256 and ExpandMsgXmd, with either the specified DST, or a default DST

Arguments: The first argument (required) is the data; the second argument (optional) is a custom DST. If the second argument is not used, the default DST of BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_AUG_ will be used instead

Usage: (g2_map data dst)

CLVM Cost: 815 000 base, 4 per byte, 4 per DST byte

bls_pairing_identity

Opcode: 58

Functionality: Returns nil if the pairing of all G1 and G2 pairs is the (Gt) identity, otherwise raise an exception

Arguments: A list of G1/G2 pairs

Usage: (bls_pairing_identity g1point1 g2point1 g1point2 g2point2 … g1pointn g2pointn)

CLVM Cost: 3 000 000 base, 1 200 000 per G1/G2 pair

bls_verify

Opcode: 59

Functionality: Validates the messages (msg) given their public key (G1) against the signature (G2). Returns nil if the signature is valid, otherwise raise an exception. The validation uses the Augmented scheme, which means the G1 points are prepended to the messages before being hashed to G2 points. The DST is BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_AUG_. The validation includes the pair of the negated G1 generator and the signature in the underlying pairing operation

Arguments: A G2 point followed by a list of G1/msg pairs

Usage: (bls_verify g2point g1point1 msg1 g1point2 msg2 … g1pointn msgn)

CLVM Cost: 3 000 000 base, 1 200 000 per G1/G2 pair, 4 per byte, 4 per DST byte, plus the cost of performing g2_map for each the messages that were signed

Other Operators

In addition, coinid, modpow, and % operators, as well as two secp operators, will be added. The behavior of the softfork operator will also be modified.

coinid

Opcode: 48

Functionality: Given a parent coin ID, puzzle-hash and amount, calculate this coin's ID. Also validates arguments, ensuring hashes are 32 bytes, and amount is in canonical representation and in the range of valid coins. Raises an exception if any of the arguments are invalid

Arguments:

  • parent-id -- The coin ID of this coin's parent coin
  • puzzle-hash -- The puzzle-hash of this coin's puzzle
  • amount -- The value of this coin, in mojos

All three of these arguments are required.

Usage: (coinid parent-id puzzle-hash amount)

CLVM Cost: 800

The calculation for the CLVM cost of coinid is similar to that of sha256:

  • SHA256_BASE_COST = 87
  • SHA256_COST_PER_ARG = 134 (and there are 3 args: parent-id, puzzle-hash, and amount)
  • SHA256_COST_PER_BYTE = 2 (and parent-id and puzzle-hash both are 32 bytes; amount is 8 bytes)
  • Base coinid_cost = SHA256_BASE_COST + SHA256_COST_PER_ARG * 3 + SHA256_COST_PER_BYTE * arg_bytes
  • Base coinid_cost = 87 + (134 * 3) + (2 * (32 + 32 + 8))
  • Base coinid_cost = 633

In addition to this cost, there is a per-byte malloc cost:

  • malloc_cost = 10 per byte allocated to the heap
  • Bytes allocated = 32 (the size of the output is the same for sha256 and coinid)
  • malloc_cost = 320

The theoretical coinid_cost is the sum of the base coinid_cost and the malloc_cost:

  • Theoretical coinid_cost = 633 + 320 = 953

So far this cost is identical to the cost of sha256. However, sha256 is more prone to user error. In order to incentivize the use of coinid we have chosen to discount the cost:

  • coinid_cost = theoretical coinid_cost - discount
  • coinid_cost = 953 - 153
  • coinid_cost = 800

modpow

Opcode: 60

Functionality: Computes (base ^ exponent) % modulus

Arguments: A base value (may be negative), an exponent (may not be negative), and a modulus (may not be 0)

Usage: (modpow base exponent modulus)

CLVM Cost:

  • base -- 17 000 base, 38 per byte
  • exponent -- 3 per square byte
  • modulus -- 21 per square byte

%

Opcode: 61

Functionality: Computes the remainder from numerator divided by denominator

Arguments: A numerator and a denominator, either of which may be negative

Usage: (% numerator denominator)

CLVM Cost: 988 base, 4 per byte (sum of both operands)

Note that the cost for % and / are identical

secp256k1_verify

Opcode: 0x13d61f00

Functionality: Verifies a signature that uses the secp256k1 curve

Arguments:

  • pubkey -- the secp256k1 public key used for signing
  • msg_digest -- the sha256 hash of the message that was signed
  • signature -- the digital signature to verify

Note about msg_digest (the sha256 hash of the message to be signed): this parameter is different from bls_verify, which has hash-to-curve (or g2_map) built-in. It simplifies the cost model, since all parameters are nearly fixed in size.

Usage: (secp256k1_verify pubkey msg_digest signature)

CLVM Cost: 1 300 000

Note that we are intentionally making this operator more expensive than the BLS equivalent in order to encourage the usage of BLS operators.

secp256r1_verify

Opcode: 0x1c3a8f00

Functionality: Verifies a signature that uses the secp256r1 curve

Arguments:

  • pubkey -- the secp256r1 public key used for signing
  • msg_digest -- the sha256 hash of the message that was signed
  • signature -- the digital signature to verify

Note about msg_digest (the sha256 hash of the message to be signed): this parameter is different from bls_verify, which has hash-to-curve (or g2_map) built-in. It simplifies the cost model, since all parameters are nearly fixed in size.

Usage: (secp256r1_verify pubkey msg_digest signature)

CLVM Cost: 1 850 000

softfork usage

As explained in the Backwards compatibility section, starting with block 4 510 000 (inclusive), the operators introduced in this CHIP will be available from inside the softfork guard.

Note that starting from block 5 496 000, the operators in this CHIP will also be available from outside the softfork guard (they will become part of the CLVM in a hard fork). After this point, it will be optional to call the operators from this CHIP from inside the softfork guard.

Also note that the syntax of the softfork operator has been updated. The following rules apply when calling the operators from this CHIP using the updated softfork operator:

  • The operator works like apply (a) but takes two additional parameters, cost and extension
  • The syntax is therefore softfork (<cost> <extension> <quoted-program> <arguments>)
  • The cost parameter is the CLVM cost of executing the quoted-program with the specified arguments. If this cost mismatches the actual cost of executing the program, the softfork operator will raise an exception
  • The extension parameter is an integer indicating the set of extensions available in the softfork guard. This integer must fit in an unsigned 32-bit variable
  • Just like the a operator, the quoted-program parameter is quoted and executed from inside the softfork guard.
  • A client that does not recognize the extension specifier must:
    • In consensus mode, ignore the whole softfork, return null and charge the specified cost
    • In mempool mode, fail the program immediately

Since softfork guards always return null, the only useful outcome of executing one is terminating (i.e. failing) the program or not.

The cost of executing the softfork operator is 140. This counts against the cost specified in its arguments.

An example of using the softfork operator to call the new coinid operator is as follows:

(softfork
  (q . 1265) ; expected cost (including cost of softfork itself)
  (q . 0)    ; extension 0
  (q a       ; defer execution of if-branches
    (i
      (=
        (coinid
          (q . 0x1234500000000000000000000000000000000000000000000000000000000000)
          (q . 0x6789abcdef000000000000000000000000000000000000000000000000000000)
          (q . 123456789)
        )
        (q . 0x69bfe81b052bfc6bd7f3fb9167fec61793175b897c16a35827f947d5cc98e4bc)
      )
      (q . 0)  ; if coin ID matches, return 0
      (q x)    ; if coin ID mismatches, raise
    )
    (q . ())) ; environment to apply
  (q . ()))   ; environment to softfork

Hard Fork Additions

The following condition and optimizations will become available after the hard fork from CHIP-12 has activated.

SOFTFORK

Opcode: 90

Functionality: Allows future conditions with non-zero CLVM costs to be added as soft forks. (This functionality was previously only possible as a hard fork)

Arguments: The cost of the condition (specified in ten-thousands) is required as the first argument, further arguments are unspecified. The reason to scale the cost by 10 000 is to make the argument smaller. For example, a cost of 100 in this condition would equate to an actual cost of 1 million (1 000 000). The cost argument is two bytes, with a maximum size of 65 535 (an actual cost of 655 350 000)

Usage: (90 cost)

CLVM Cost: Varies, specified during the call, can be zero

Unknown Conditions with Cost

Before the SOFTFORK condition is enabled, all new conditions must have zero cost. These conditions must fit in one byte (the conditions are an alias for a u8).

After the SOFTFORK condition has been enabled, it will become possible to add new conditions with costs. These new conditions will be soft forks. The condition codes will each be two bytes (an alias for a u16). This change allows the conditions parser to handle 2-byte conditions. In order to use the new conditions with cost, the 2-byte conditions must use 0x01 as their first byte.

The cost for these conditions is calculated from the function specified in PR #183 of the chia_rs repository. The exact costs calculated from this function are listed in this table.

Two additional things to keep in mind regarding these changes:

  • All existing condition codes will stay the same, as single bytes.
  • Two-byte condition codes that don't have a leading 0x01 (including those that begin with 0x00) will be treated as no-ops.

Additional AGG_SIG conditions

Prior to the hard fork from CHIP-12, the following BLS signature conditions exist:

AGG_SIG_UNSAFE

Opcode: 49

Functionality: Verifies a signature by its public_key and message

Usage: (AGG_SIG_UNSAFE public_key message)

CLVM Cost: 1 200 000

AGG_SIG_ME

Opcode: 50

Functionality: Verifies a signature by its public_key and message, which also includes the coin_id and genesis_id

Usage: (AGG_SIG_ME public_key message)

CLVM Cost: 1 200 000


In order to differentiate between these two signature conditions, the signed message includes a domain string. In the case of AGG_SIG_ME, the domain string is the Chia blockchain's genesis challenge, a static and known identifier. The domain string for AGG_SIG_UNSAFE can be anything except the domain string for AGG_SIG_ME.

AGG_SIG_ME and AGG_SIG_UNSAFE each also include the coin's ID (the sha256 hash of the concatenated parent_id, puzzle_hash, and amount) in the signed message. However, certain primitives (eg payment channels) are easier to implement when validation only requires knowledge of one or two of those values.

Therefore, this CHIP will also add operators with message strings that include all combinations of parent_id, puzzle_hash, and amount. The domain string for each condition needs to be unique, so it will include the opcode for the condition:

domain string = sha256(genesis challenge + opcode)

Therefore, after the activation of the hard fork from CHIP-12, the following new conditions will become available:

AGG_SIG_PARENT

Opcode: 43

Functionality: Verifies a signature by its public_key and message; also includes the domain string sha256(genesis challenge + 43) and the coin's parent_id

Usage: (AGG_SIG_PARENT public_key message)

CLVM Cost: 1 200 000

AGG_SIG_PUZZLE

Opcode: 44

Functionality: Verifies a signature by its public_key and message; also includes the domain string sha256(genesis challenge + 44) and the coin's puzzle_hash

Usage: (AGG_SIG_PUZZLE public_key message)

CLVM Cost: 1 200 000

AGG_SIG_AMOUNT

Opcode: 45

Functionality: Verifies a signature by its public_key and message; also includes the domain string sha256(genesis challenge + 45) and the coin's amount

Usage: (AGG_SIG_AMOUNT public_key message)

CLVM Cost: 1 200 000

AGG_SIG_PUZZLE_AMOUNT

Opcode: 46

Functionality: Verifies a signature by its public_key and message; also includes the domain string sha256(genesis challenge + 46) and the coin's puzzle_hash and amount

Usage: (AGG_SIG_PUZZLE_AMOUNT public_key message)

CLVM Cost: 1 200 000

AGG_SIG_PARENT_AMOUNT

Opcode: 47

Functionality: Verifies a signature by its public_key and message; also includes the domain string sha256(genesis challenge + 47) and the coin's parent_id and amount

Usage: (AGG_SIG_PARENT_AMOUNT public_key message)

CLVM Cost: 1 200 000

AGG_SIG_PARENT_PUZZLE

Opcode: 48

Functionality: Verifies a signature by its public_key and message; also includes the domain string sha256(genesis challenge + 48) and the coin's parent_id and puzzle_hash

Usage: (AGG_SIG_PARENT_PUZZLE public_key message)

CLVM Cost: 1 200 000

Block Generator Optimizations

As part of the block creation process, a CLVM program called the ROM generator is responsible for the following:

  • Calling the block generator, which outputs all spends, puzzles and solutions for that block
  • Running the puzzles with each corresponding solution
  • Computing puzzle hashes, which are later used to find the coins to spend from the coin set

Prior to the hard fork from CHIP-12, the cost of running the ROM generator counts against the per-block cost limit.

After the hard fork has activated, the ROM generator will no longer be charged a cost. Note that the block generator, puzzles, and solutions will continue to incur the same costs as before.

The hard fork will also enable an updated serialization format for CLVM, which will be used for block generators. The generators will memoize the tree hashes of sub-trees, an optimization that allows a more compact representation of repeated sub-trees. Since identical trees have already been deduplicated by the farmer, it will become cheaper to compute the puzzle hashes in the common case where there are repeated puzzles in a block.

Test Cases

The test cases for this CHIP are located in the op-tests folder of the clvm_rs GitHub repository. These tests include:

Reference Implementation

The following pull requests have been merged to the Chia-Network/chia_rs GitHub repository as part of this CHIP:

  • 168 - SOFTFORK condition
  • 170 - assign cost to currently unknown condition codes; takes effect when the ENABLE_SOFTFORK_CONDITION flag is set
  • 181 - update costs of unknown condition codes (two bytes instead of one)
  • 183 - use a function to calculate costs for unknown conditions instead of a table
  • 185 - increase the maximum number of announcements created or asserted from 1000 to 1024
  • 213 - new AGG_SIG_* conditions
  • 273 - softfork and coinid operators
  • 274 - the main patch for this CHIP
  • 287 - changes to the signatures for bls_verify and bls_pairing_identity
  • 288 - updated costs for the BLS operators
  • 290 - bls_verify and bls_pairing_identity must return nil if verification succeeds, and raise if verification fails
  • 303 - secp operators
  • 312 - modpow and mod (%) operators
  • 314 - adjust cost of secp256k1_verify

The following pull requests have been merged to the Chia-Network/chia-blockchain GitHub repository as part of this CHIP:

  • 15299 - soft fork infrastructure
  • 15769 - new AGG_SIG_* conditions
  • 15938 - update soft fork activation height

Security

Chia Network, Inc. has conducted an internal review of the code involved with this CHIP.

Additional Assets

Errata

  • 2023-08-29 -- The AGG_SIG_ME section states that AGG_SIG_ME and AGG_SIG_UNSAFE each include the coin's ID. While this is always true for AGG_SIG_ME, it is not necessarily true for AGG_SIG_UNSAFE, which has no requirement for the coin's ID to be included. However, it may be included if desired.

Copyright

Copyright and related rights waived via CC0.