概要
向量承诺是一种构造，它能够对一个带索引的元素向量生成固定大小且具有绑定性的承诺，并为该向量中的任意索引与元素提供简短的成员证明和/或非成员证明。 本规范列举了 IBC 协议中所使用承诺构造必须具备的函数和属性。特别地，IBC 中使用的承诺必须满足位置绑定：它们必须能够证明特定位置（索引）上的值存在或不存在。动机
为了保证某条链上发生的特定状态转换可以在另一条链上被验证，IBC 需要一种高效的密码学构造，用于证明状态中特定路径上的特定值被包含或未被包含。定义
向量承诺的管理者是有能力且有责任向承诺中添加或移除条目的参与方。通常这将是区块链的状态机。 证明者是负责生成特定元素包含或不包含证明的参与方。通常这将是中继者（参见 ICS 18）。 验证者是负责检查证明，以验证承诺管理者是否添加了某个特定元素的参与方。通常这将是在另一条链上运行的 IBC 处理器（实现 IBC 的模块）。 承诺会以特定的路径和值类型进行实例化，这些类型被假定为任意可序列化数据。 可忽略函数是指增长速度慢于任意正多项式倒数的函数，定义见这里。期望属性
本文档只定义期望属性，而不定义具体实现，参见下文“属性”。技术规范
下面我们定义行为与数据类型概览。数据类型定义请参见 cosmos/ics23 仓库。数据类型
一种承诺构造必须指定以下数据类型。这些类型在其他方面是透明的（无需进行内部检查），但必须可序列化：承诺状态
CommitmentState 是承诺的完整状态，由管理者存储。
承诺根
CommitmentRoot 对某个特定承诺状态进行承诺，并且应为固定大小。
在某些状态本身为固定大小的承诺构造中，CommitmentState 和 CommitmentRoot 可以是同一种类型。
承诺路径
CommitmentPath 是用于验证承诺证明的路径，它可以是任意结构化对象（由承诺类型定义）。它必须通过 applyPrefix（定义见下文）计算得到。
前缀
CommitmentPrefix 定义了承诺证明的存储前缀。在路径传入证明验证函数之前，会先将此前缀应用到路径上。
applyPrefix 根据参数构造一个新的承诺路径。它会在前缀参数的上下文中解释路径参数。
对于两个 (prefix, path) 元组，只有当元组元素相等时，applyPrefix(prefix, path) 才能返回相同的键。
applyPrefix 必须按 Path 分别实现，因为 Path 可以有不同的具体结构。applyPrefix 可以接受多种 CommitmentPrefix 类型。
applyPrefix 返回的 CommitmentPath 不一定需要可序列化（例如，它可能是树节点标识符列表），但必须支持相等性比较。
removePrefix 是 applyPrefix 的逆操作，即返回去除存储前缀后的字节串键。
证明
CommitmentProof 用于证明某个元素或一组元素的成员关系或非成员关系，并可结合已知的承诺根进行验证。证明应尽量简洁。
必需函数
一种承诺构造必须提供以下函数，这些函数以可序列化对象形式的路径和字节数组形式的值为定义域：初始化
generate 函数根据路径到值的初始映射（可以为空）初始化承诺状态。
根计算
calculateRoot 函数计算承诺状态的一个固定大小承诺，可用于验证证明。
添加与移除元素
set 函数在承诺中将某一路径设置为某个值。
remove 函数从承诺中移除某一路径及其关联值。
证明生成
createMembershipProof 函数生成一个证明，用于证明某个特定承诺路径在某个承诺中已被设置为某个特定值。
createNonMembershipProof 函数生成一个证明，用于证明某个承诺路径在某个承诺中尚未被设置为任何值。
证明验证
verifyMembership 函数验证一个证明，以确认某一路径在某个承诺中已被设置为某个特定值。
verifyNonMembership 函数验证一个证明，以确认某一路径在某个承诺中尚未被设置为任何值。
可选函数
一种承诺构造可以提供以下函数：batchVerifyMembership 函数验证一个证明，以确认多条路径在某个承诺中已被设置为特定值。
batchVerifyNonMembership 函数验证一个证明，以确认多条路径在某个承诺中尚未被设置为任何值。
verifyMembership 和 verifyNonMembership 的合取并集产生相同结果（效率可能不同）：
属性与不变量
承诺必须满足完备性、健全性和位置绑定性。这些属性是相对于安全参数k 定义的，k 必须由管理者、证明者和验证者达成一致（并且通常会是该承诺算法的常量）。
完备性
承诺证明必须具备完备性：凡是已经加入承诺的路径 => 值映射，总是可以被证明已包含；凡是尚未包含的路径，总是可以被证明已排除，例外情况的概率相对于k 可忽略。
对于任意前缀 prefix，以及承诺 acc 中最后一次被设置为值 value 的任一路径 path，
prefix，以及承诺 acc 中未设置的任一路径 path，对于 proof 的所有取值以及 value 的所有取值，
健全性
承诺证明必须具备健全性：凡是未加入承诺的路径 => 值映射，不能被证明为已包含；凡是已经加入承诺的路径，不能被证明为已排除，例外情况的概率相对于可配置安全参数k 可忽略。
对于任意前缀 prefix，以及承诺 acc 中最后一次被设置为值 value 的任一路径 path，对于 proof 的所有取值，
prefix，以及承诺 acc 中未设置的任一路径 path，对于 proof 的所有取值以及 value 的所有取值，
a 与键 c 的存在，并额外证明这两个键在承诺中彼此相邻，来证明键 b 不存在。
位置绑定性
承诺证明必须具备位置绑定性：给定一个承诺路径只能映射到一个值，并且除非以相对于 k 可忽略的概率，否则承诺证明不能证明同一路径可打开为另一个不同的值。 对于任意前缀prefix，以及承诺 acc 中已设置的任一路径 path，存在唯一一个 value，使得：
otherValue，其中 value !== otherValue，以及 proof 的所有取值，
向后兼容性
不适用。向前兼容性
承诺算法预计是固定的。可以通过对连接和通道进行版本化来引入新算法。示例实现
- 可以在 cosmos/ics23 repository 中找到 ICS 23 的 Go 和 Rust 实现。
历史
安全性定义主要来源于以下论文（并做了适当简化）：- Vector Commitments and their Applications
- Commitments with Applications to Anonymity-Preserving Revocation
- Batching Techniques for Commitments with Applications to IOPs and Stateless Blockchains
版权
本文所有内容均依据 Apache 2.0 许可。Synopsis
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).Motivation
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.Definitions
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.Desired Properties
This document only defines desired properties, not a concrete implementation — see “Properties” below.Technical Specification
Below we define a behaviour and an overview of datatypes. For data type definition look at cosmos/ics23 repository.Datatypes
A commitment construction MUST specify the following datatypes, which are otherwise opaque (need not be introspected) but MUST be serialisable:Commitment State
ACommitmentState is the full state of the commitment, which will be stored by the manager.
Commitment Root
ACommitmentRoot 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.
Commitment Path
ACommitmentPath 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).
Prefix
ACommitmentPrefix defines a store prefix of the commitment proof. It is applied to the path before the path is passed to the proof verification functions.
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.
removePrefix is the inverse operation of applyPrefix, i.e. it returns the bytestring key without the store prefix.
Proof
ACommitmentProof demonstrates membership or non-membership for an element or set of elements, verifiable in conjunction with a known commitment root. Proofs should be succinct.
Required functions
A commitment construction MUST provide the following functions, defined over paths as serialisable objects and values as byte arrays:Initialisation
Thegenerate function initialises the state of the commitment from an initial (possibly empty) map of paths to values.
Root calculation
ThecalculateRoot function calculates a constant-size commitment to the commitment state which can be used to verify proofs.
Adding & removing elements
Theset function sets a path to a value in the commitment.
remove function removes a path and associated value from a commitment.
Proof generation
ThecreateMembershipProof function generates a proof that a particular commitment path has been set to a particular value in a commitment.
createNonMembershipProof function generates a proof that a commitment path has not been set to any value in a commitment.
Proof verification
TheverifyMembership function verifies a proof that a path has been set to a particular value in a commitment.
verifyNonMembership function verifies a proof that a path has not been set to any value in a commitment.
Optional functions
A commitment construction MAY provide the following functions: ThebatchVerifyMembership function verifies a proof that many paths have been set to specific values in a commitment.
batchVerifyNonMembership function verifies a proof that many paths have not been set to any value in a commitment.
verifyMembership and verifyNonMembership respectively (efficiency may vary):
Properties & Invariants
Commitments MUST be complete, sound, and position binding. These properties are defined with respect to a security parameterk, which MUST be agreed upon by the manager, prover, and verifier (and often will be constant for the commitment algorithm).
Completeness
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 ink.
For any prefix prefix and any path path last set to a value value in the commitment acc,
prefix and any path path not set in the commitment acc, for all values of proof and all values of value,
Soundness
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 parameterk.
For any prefix prefix and any path path last set to a value value in the commitment acc, for all values of proof,
prefix and any path path not set in the commitment acc, for all values of proof and all values of value,
b may be proven by showing the existence of key a and key c in addition to proving that these two keys are neighbors in the commitment.
Position binding
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 prefixprefix and any path path set in the commitment acc, there is one value for which:
otherValue where value !== otherValue, for all values of proof,
Backwards Compatibility
Not applicable.Forwards Compatibility
Commitment algorithms are expected to be fixed. New algorithms can be introduced by versioning connections and channels.Example Implementations
- Implementations of ICS 23 in Go and Rust can be found in cosmos/ics23 repository.
History
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