| ics | title | stage | required-by | category | kind | author | created | modified |
|---|---|---|---|---|---|---|---|---|
23 |
Vector Commitments |
draft |
2, 24 |
IBC/TAO |
interface |
Christopher Goes <[email protected]> |
2019-04-16 |
2019-08-25 |
A vector commitment is a construction that produces a constant-size, binding commitment to an indexed vector of elements and short membership and/or non-membership proofs for any indices & elements in the vector. This specification enumerates the functions and properties required of commitment constructions used in the IBC protocol. In particular, commitments utilised in IBC are required to be positionally binding: they must be able to prove existence or nonexistence of values at specific positions (indices).
In order to provide a guarantee of a particular state transition having occurred on one chain which can be verified on another chain, IBC requires an efficient cryptographic construction to prove inclusion or non-inclusion of particular values at particular paths in state.
The manager of a vector commitment is the actor with the ability and responsibility to add or remove items from the commitment. Generally this will be the state machine of a blockchain.
The prover is the actor responsible for generating proofs of inclusion or non-inclusion of particular elements. Generally this will be a relayer (see ICS 18).
The verifier is the actor who checks proofs in order to verify that the manager of the commitment did or did not add a particular element. Generally this will be an IBC handler (module implementing IBC) running on another chain.
Commitments are instantiated with particular path and value types, which are assumed to be arbitrary serialisable data.
A negligible function is a function that grows more slowly than the reciprocal of every positive polynomial, as defined here.
This document only defines desired properties, not a concrete implementation — see "Properties" below.
A commitment construction MUST specify the following datatypes, which are otherwise opaque (need not be introspected) but MUST be serialisable:
A CommitmentState is the full state of the commitment, which will be stored by the manager.
type CommitmentState = objectA CommitmentRoot commits to a particular commitment state and should be constant-size.
In certain commitment constructions with constant-size states, CommitmentState and CommitmentRoot may be the same type.
type CommitmentRoot = objectA CommitmentPath is the path used to verify commitment proofs, which can be an arbitrary structured object (defined by a commitment type). It must be computed by applyPrefix (defined below).
type CommitmentPath = objectA CommitmentPrefix defines a store prefix of the commitment proof. It is applied to the path before the path is passed to the proof verification functions.
type CommitmentPrefix = objectThe function applyPrefix constructs a new commitment path from the arguments. It interprets the path argument in the context of the prefix argument.
For two (prefix, path) tuples, applyPrefix(prefix, path) MUST return the same key only if the tuple elements are equal.
applyPrefix MUST be implemented per Path, as Path can have different concrete structures. applyPrefix MAY accept multiple CommitmentPrefix types.
The CommitmentPath returned by applyPrefix does not need to be serialisable (e.g. it might be a list of tree node identifiers), but it does need an equality comparison.
type applyPrefix = (prefix: CommitmentPrefix, path: Path) => CommitmentPathA CommitmentProof demonstrates membership or non-membership for an element or set of elements, verifiable in conjunction with a known commitment root. Proofs should be succinct.
type CommitmentProof = objectA commitment construction MUST provide the following functions, defined over paths as serialisable objects and values as byte arrays:
type Path = string
type Value = []byteThe generate function initialises the state of the commitment from an initial (possibly empty) map of paths to values.
type generate = (initial: Map<Path, Value>) => CommitmentStateThe calculateRoot function calculates a constant-size commitment to the commitment state which can be used to verify proofs.
type calculateRoot = (state: CommitmentState) => CommitmentRootThe set function sets a path to a value in the commitment.
type set = (state: CommitmentState, path: Path, value: Value) => CommitmentStateThe remove function removes a path and associated value from a commitment.
type remove = (state: CommitmentState, path: Path) => CommitmentStateThe createMembershipProof function generates a proof that a particular commitment path has been set to a particular value in a commitment.
type createMembershipProof = (state: CommitmentState, path: CommitmentPath, value: Value) => CommitmentProofThe createNonMembershipProof function generates a proof that a commitment path has not been set to any value in a commitment.
type createNonMembershipProof = (state: CommitmentState, path: CommitmentPath) => CommitmentProofThe verifyMembership function verifies a proof that a path has been set to a particular value in a commitment.
type verifyMembership = (root: CommitmentRoot, proof: CommitmentProof, path: CommitmentPath, value: Value) => booleanThe verifyNonMembership function verifies a proof that a path has not been set to any value in a commitment.
type verifyNonMembership = (root: CommitmentRoot, proof: CommitmentProof, path: CommitmentPath) => booleanA commitment construction MAY provide the following functions:
The batchVerifyMembership function verifies a proof that many paths have been set to specific values in a commitment.
type batchVerifyMembership = (root: CommitmentRoot, proof: CommitmentProof, items: Map<CommitmentPath, Value>) => booleanThe batchVerifyNonMembership function verifies a proof that many paths have not been set to any value in a commitment.
type batchVerifyNonMembership = (root: CommitmentRoot, proof: CommitmentProof, paths: Set<CommitmentPath>) => booleanIf defined, these functions MUST produce the same result as the conjunctive union of verifyMembership and verifyNonMembership respectively (efficiency may vary):
batchVerifyMembership(root, proof, items) ===
all(items.map((item) => verifyMembership(root, proof, item.path, item.value)))batchVerifyNonMembership(root, proof, items) ===
all(items.map((item) => verifyNonMembership(root, proof, item.path)))If batch verification is possible and more efficient than individual verification of one proof per element, a commitment construction SHOULD define batch verification functions.
Commitments MUST be complete, sound, and position binding. These properties are defined with respect to a security parameter k, which MUST be agreed upon by the manager, prover, and verifier (and often will be constant for the commitment algorithm).
Commitment proofs MUST be complete: path => value mappings which have been added to the commitment can always be proved to have been included, and paths which have not been included can always be proved to have been excluded, except with probability negligible in k.
For any prefix prefix and any path path last set to a value value in the commitment acc,
root = getRoot(acc)
proof = createMembershipProof(acc, applyPrefix(prefix, path), value)Probability(verifyMembership(root, proof, applyPrefix(prefix, path), value) === false) negligible in k
For any prefix prefix and any path path not set in the commitment acc, for all values of proof and all values of value,
root = getRoot(acc)
proof = createNonMembershipProof(acc, applyPrefix(prefix, path))Probability(verifyNonMembership(root, proof, applyPrefix(prefix, path)) === false) negligible in k
Commitment proofs MUST be sound: path => value mappings which have not been added to the commitment cannot be proved to have been included, or paths which have been added to the commitment excluded, except with probability negligible in a configurable security parameter k.
For any prefix prefix and any path path last set to a value value in the commitment acc, for all values of proof,
Probability(verifyNonMembership(root, proof, applyPrefix(prefix, path)) === true) negligible in k
For any prefix prefix and any path path not set in the commitment acc, for all values of proof and all values of value,
Probability(verifyMembership(root, proof, applyPrefix(prefix, path), value) === true) negligible in k
Commitment proofs MUST be position binding: a given commitment path can only map to one value, and a commitment proof cannot prove that the same path opens to a different value except with probability negligible in k.
For any prefix prefix and any path path set in the commitment acc, there is one value for which:
root = getRoot(acc)
proof = createMembershipProof(acc, applyPrefix(prefix, path), value)Probability(verifyMembership(root, proof, applyPrefix(prefix, path), value) === false) negligible in k
For all other values otherValue where value !== otherValue, for all values of proof,
Probability(verifyMembership(root, proof, applyPrefix(prefix, path), otherValue) === true) negligible in k
Not applicable.
Commitment algorithms are expected to be fixed. New algorithms can be introduced by versioning connections and channels.
Coming soon.
Coming soon.
Security definitions are mostly sourced from these papers (and simplified somewhat):
- Vector Commitments and their Applications
- Commitments with Applications to Anonymity-Preserving Revocation
- Batching Techniques for Commitments with Applications to IOPs and Stateless Blockchains
Thanks to Dev Ojha for extensive comments on this specification.
Apr 25, 2019 - Draft submitted
All content herein is licensed under Apache 2.0.