Skip to content

Latest commit

 

History

History
294 lines (184 loc) · 9.95 KB

README.md

File metadata and controls

294 lines (184 loc) · 9.95 KB
ics title stage required-by category kind author created modified
23
向量承诺
草案
2, 24
IBC/TAO
接口
Christopher Goes <cwgoes@tendermint.com>
2019-04-16
2019-08-25

概要

向量承诺是一种构造，它对向量中任何索引和元素的成员资格/非成员资格的短证明产生恒定大小的绑定承诺。 本规范列举了 IBC 协议中使用的承诺构造所需的函数和特性。特别是，IBC 中使用的承诺必须具有位置约束力 ：它们必须能够证明在特定位置（索引）的值存在或不存在。

动机

为了提供可以在另一条链上验证的一条链上发生的特定状态转换的保证，IBC 需要一种有效的密码构造来证明在状态的特定路径上包含或不包含特定值。

定义

向量承诺的管理者是具有在承诺中添加或删除条目的能力和责任的参与者。通常，这将是区块链的状态机。

证明者是负责生成包含或不包含特定元素的证明的参与者。通常，这将是一个中继器（请参阅 ICS 18 ）。

验证者是检查证明来验证承诺的管理者是否添加了特定元素的参与者。通常，这将是在另一条链上运行的 IBC 处理程序（实现 IBC 的模块）。

使用特定的路径和值类型实例化承诺，它们的类型假定为任意可序列化的数据。

一个可忽略的函数是一个比每个正多项式的倒数增长更慢的函数，如此处所定义。

所需属性

本文档仅定义所需的属性，而不是具体的实现——请参见下文中的“属性”。

技术规范

下面我们定义一个行为和数据类型的概述。有关数据类型定义，请查看conio/ics23代码库。

数据类型

承诺构造必须指定以下数据类型，这些数据类型可以是不透明的（不需要外部检视），但必须是可序列化的：

承诺状态

CommitmentState是承诺的完整状态，将由管理器存储。

type CommitmentState = object

承诺根

CommitmentRoot确保一个特定的承诺状态，并且应为恒定大小。

在状态大小恒定的某些承诺构造中， CommitmentState和CommitmentRoot可以是同一类型。

type CommitmentRoot = object

承诺路径

CommitmentPath是用于验证承诺证明的路径，该路径可以是任意结构化对象（由承诺类型定义）。它必须由通过applyPrefix （定义如下）计算出来。

type CommitmentPath = object

前缀

CommitmentPrefix定义了承诺证明的存储前缀。它在路径传递给证明验证函数之前应用于路径。

type CommitmentPrefix = object

函数applyPrefix从参数构造一个新的提交路径。它在前缀参数的上下文中解释路径参数。

对于两个(prefix, path)元组， applyPrefix(prefix, path)必须仅在元组元素相等时才返回相同的键。

applyPrefix必须按Path来实现，因为Path可以具有不同的具体结构。 applyPrefix可以接受多种CommitmentPrefix类型。

applyPrefix返回的CommitmentPath不需要是可序列化的（例如，它可能是树节点标识符的列表），但它需要可以被比较是否相等。

type applyPrefix = (prefix: CommitmentPrefix, path: Path) => CommitmentPath

证明

一个CommitmentProof证明一个元素或一组元素的成员资格或非成员资格，可以与已知的承诺根一起验证。证明应是简洁的。

type CommitmentProof = object

所需函数

承诺构造必须提供以下函数，这些函数在路径上定义为可序列化的对象，在值上定义为字节数组：

type Path = string

type Value = []byte

初始化

generate函数从一个路径到值的映射（可能为空）初始化承诺的状态。

type generate = (initial: Map<Path, Value>) => CommitmentState

根计算

calculateRoot函数计算承诺状态的恒定大小的承诺，可用于验证证明。

type calculateRoot = (state: CommitmentState) => CommitmentRoot

添加和删除元素

set函数将承诺中的一个路径设置为值。

type set = (state: CommitmentState, path: Path, value: Value) => CommitmentState

remove函数从承诺中删除路径和其关联值。

type remove = (state: CommitmentState, path: Path) => CommitmentState

证明生成

createMembershipProof函数生成一个证明，证明特定承诺路径已被设置为承诺中的特定值。

type createMembershipProof = (state: CommitmentState, path: CommitmentPath, value: Value) => CommitmentProof

createNonMembershipProof函数生成一个证明，证明承诺路径尚未设置为任何值。

type createNonMembershipProof = (state: CommitmentState, path: CommitmentPath) => CommitmentProof

证明验证

verifyMembership函数验证在承诺中已将路径设置为特定值的证明。

type verifyMembership = (root: CommitmentRoot, proof: CommitmentProof, path: CommitmentPath, value: Value) => boolean

verifyNonMembership函数验证在承诺中尚未将路径设置为任何值的证明。

type verifyNonMembership = (root: CommitmentRoot, proof: CommitmentProof, path: CommitmentPath) => boolean

可选函数

承诺构造可以提供以下函数：

batchVerifyMembership函数验证在承诺中已将多个路径设置为特定值的证明。

type batchVerifyMembership = (root: CommitmentRoot, proof: CommitmentProof, items: Map<CommitmentPath, Value>) => boolean

batchVerifyNonMembership函数可验证证明在承诺中尚未将多个路径设置为任何值的证明。

type batchVerifyNonMembership = (root: CommitmentRoot, proof: CommitmentProof, paths: Set<CommitmentPath>) => boolean

如果定义这些函数，必须和使用verifyMembership和verifyNonMembership联合在一起的结果相同（效率可能有所不同）：

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)))

如果批量验证是可行的并且比单独验证每个元素的证明更有效，则承诺构造应定义批量验证函数。

属性与不变性

承诺必须是完整的，合理的和有位置约束的。这些属性是相对于安全性参数k定义的，此安全性参数必须由管理者，证明者和验证者达成一致（并且对于承诺算法通常是恒定的）。

完整性

承诺证明必须是完整的 ：已添加到承诺中的路径/值映射始终可以被证明已包含在内，未包含的路径始终可以被证明已被排除，除非是k定义的可以忽略的概率。

对于最后一个设置承诺acc中的值value的任何前缀prefix和任何路径path，

root = getRoot(acc)
proof = createMembershipProof(acc, applyPrefix(prefix, path), value)
Probability(verifyMembership(root, proof, applyPrefix(prefix, path), value) === false) negligible in k

对于没有在承诺acc中设置的任何前缀prefix和任何路径path ，对于proof的所有值和value的所有值的

root = getRoot(acc)
proof = createNonMembershipProof(acc, applyPrefix(prefix, path))
Probability(verifyNonMembership(root, proof, applyPrefix(prefix, path)) === false) negligible in k

合理性

承诺证明必须是合理的 ：除非在可配置安全性参数k概率下可以忽略不计，否则不能将未添加到承诺中的路径/值映射证明为已包含，或者将已经添加到承诺中的路径证明为已排除。

对于最后一个设置值value在承诺acc中的任何前缀prefix和任何路径path，对于proof 的所有值，

Probability(verifyNonMembership(root, proof, applyPrefix(prefix, path)) === true) negligible in k

对于没有在承诺acc中设置的任何前缀prefix和任何路径path，对于proof的所有值和value的所有值 ，

Probability(verifyMembership(root, proof, applyPrefix(prefix, path), value) === true) negligible in k

位置绑定

承诺证明必须是有位置约束的 ：给定的承诺路径只能映射到一个值，并且承诺证明不能证明同一路径适用于不同的值，除非在概率k下可以被忽略。

对于在承诺acc设置的任何前缀prefix和任何路径path ，都有一个value ：

root = getRoot(acc)
proof = createMembershipProof(acc, applyPrefix(prefix, path), value)
Probability(verifyMembership(root, proof, applyPrefix(prefix, path), value) === false) negligible in k

对于所有其他值otherValue ，其中value !== otherValue ，对于proof的所有值，

Probability(verifyMembership(root, proof, applyPrefix(prefix, path), otherValue) === true) negligible in k

向后兼容性

不适用。

向前兼容性

承诺算法将是固定的。可以通过对连接和通道进行版本控制来引入新算法。

示例实现

即将到来。

其他实现

即将到来。

历史

安全性定义主要来自以下文章（并进行了一些简化）：

感谢 Dev Ojha 对这个规范的广泛评论。

2019年4月25日-提交的草稿

版权

本规范所有内容均采用 Apache 2.0 许可授权。