ADR 028: Public Key Addresses

​

变更记录

• 2020/08/18：初始版本
• 2021/01/15：分析与算法更新

​

状态

​

摘要

​

背景

​

问题

​

初始提案

我在构建 weave 时花了不少时间思考这个问题……另一个 cosmos Sdk。 基本思路是，我将一个条件定义为一种类型，并将其格式化为人类可读字符串，再附加一些二进制数据。这个条件会被哈希为一个 Address（同样是 20 字节）。使用这个前缀后，就不可能针对带有不同条件的给定地址找到原像（例如 ed25519 与 secp256k1）。 这里有更深入的说明 Link 代码在这里，主要看顶部处理条件的部分。Link

是的，据我所知，只要原像是唯一且不可塑的，20 字节应当具备抗碰撞性。2^160 的空间中，大约在 2^80 个元素附近才会开始较大概率出现碰撞（生日悖论）。如果你想为数据库中某个已有元素找到碰撞，复杂度仍然是 2^160。只有当所有这些元素都写入状态时，才会出现 2^80 的情况。 你举的一个好例子是：某段公钥字节同时是 codec 支持的两种算法下的有效公钥。这意味着如果其中任意一种被攻破，即使账户原本由更安全的变体保护，你仍然可以攻破这些账户。只有在原像中没有携带可区分的类型信息（也就是哈希为地址之前）时，才会出现这个问题。 如果 20 字节空间在安全性上确实存在问题，我希望听到相关论证，因为我也愿意在 weave 中增加地址长度。我只是参考了 cosmos、ethereum 和 bitcoin 都使用 20 字节，觉得应该足够了。再加上上面的论证，让我倾向于认为它是安全的。不过我还没有做更深入的分析。

​

评审与讨论

• 哈希函数的选择。
• 将前缀移到哈希函数之外：keyTypePrefix + sha256(keybytes)[:20] [post-hash-prefix-proposal]。
• 使用双重哈希：sha256(keyTypePrefix + sha256(keybytes)[:20])。
• 将 keybytes 哈希切片从 20 字节增加到 32 或 40 字节。我们的结论是，由优良哈希函数生成的 32 字节在未来仍然是安全的。

​

需求

• 支持当前正在使用的工具，我们不希望破坏现有生态，也不希望引入过长的适配周期。参考：Link
• 尽量保持地址长度较小，因为地址在状态中被广泛使用，既可能是键的一部分，也可能是对象值的一部分。

​

范围

​

决策

1. 简单账户：由常规公钥表示（例如：secp256k1、sr25519）
2. 朴素多签：由其他可寻址对象组成的账户（例如：朴素多签）
3. 带有原生地址键的组合账户（例如：bls、group 模块账户）
4. 模块账户：基本上指任何不能签名交易、且由模块内部管理的账户

​

旧版公钥地址保持不变

• secp256k1：ripemd160(sha256(pk_bytes))[:20]
• 旧版 amino 多签：sha256(aminoCdc.Marshal(pk))[:20]

​

哈希函数选择

​

基础地址

const A_LEN = 32

func Hash(typ string, key []byte) []byte {
    return hash(hash(typ) + key)[:A_LEN]
}

• BLS：address.Hash("bls", pubkey)

​

组合地址

// We don't need a PubKey interface - we need anything which is addressable.
type Addressable interface {
    Address() []byte
}

func Composed(typ string, subaccounts []Addressable) []byte {
    addresses = map(subaccounts, \a -> LengthPrefix(a.Address()))

addresses = sort(addresses)

return address.Hash(typ, addresses[0] + ... + addresses[n])
}

​

多签地址

package cosmos.crypto.multisig;

message PubKey {
  uint32 threshold = 1;
  repeated google.protobuf.Any pubkeys = 2;
}

func (multisig PubKey)

Address() {
	// first gather all nested pub keys
	var keys []address.Addressable  // cryptotypes.PubKey implements Addressable
    for _, _key := range multisig.Pubkeys {
    keys = append(keys, key.GetCachedValue().(cryptotypes.PubKey))
}

	// form the type from the message name (cosmos.crypto.multisig.PubKey)

and the threshold joined together
    prefix := fmt.Sprintf("%s/%d", proto.MessageName(multisig), multisig.Threshold)

	// use the Composed function defined above
	return address.Composed(prefix, keys)
}

​

派生地址

func Derive(address, derivationKey []byte) []byte {
    return Hash(addres, derivationKey)
}

​

模块账户地址

address.Module(moduleName, key)

groupPolicyAddresses := []byte{1
}

address.Module(moduleName, groupPolicyAddresses, policyID)

func Module(moduleName string, derivationKeys ...[]byte) []byte{
    if len(derivationKeys) == 0 {
    return authtypes.NewModuleAddress(modulenName)  // legacy case
}
    submoduleAddress := Hash("module", []byte(moduleName) + 0 + key)

return fold((a, k) => Derive(a, k), subsubKeys, submoduleAddress)
}

btcPool := address.Module("lending", btc.Address()
})

btcAtomAMM := address.Module("amm", btc.Address() + atom.Address()
})

smartContractAddr = Module("mySmartContractVM", smartContractsNamespace, smartContractKey
})

// which equals to:
smartContractAddr = Derived(
    Module("mySmartContractVM", smartContractsNamespace), 
    []{
    smartContractKey
})

​

模式类型

package cosmos.crypto.sr25519;

message PubKey {
	bytes key = 1;
}

​

影响

​

向后兼容性

​

正面影响

• 为新的公钥、复杂账户和模块生成地址的简单算法
• 该算法推广了原生组合键
• 提高了地址的安全性和抗冲突能力
• 该方法可扩展到未来的使用场景，只要使用的其他地址类型不与此处规定的地址长度（20 或 32 字节）冲突即可。
• 支持新的账户类型。

​

负面影响

• 地址本身不传达密钥类型，而带前缀的方法本可以做到这一点
• 地址长度增加了 60%，会占用更多存储空间
• 需要重构 KVStore 的 store key，以支持变长地址

​

中性影响

• 使用 protobuf 消息名作为密钥类型前缀

​

进一步讨论

​

附录：咨询会议

• 我们不需要第二原像抗性
• 为了抗冲突，我们需要 32 字节的地址空间
• 当攻击者能够控制某个带地址对象的输入时，就会面临生日攻击问题
• 对于哈希而言，智能合约存在一个问题
• 可以利用 sha2 挖矿来破坏地址原像

• 任何能攻破 blake3 的攻击也会攻破 blake2
• Alan 对当前 blake 哈希算法的安全性分析相当有信心。它曾是决赛入围方案，作者在安全分析领域也很知名。

• Alan 建议对前缀进行哈希：address(pub_key) = hash(hash(key_type) + pub_key)[:32]，主要优点是：
  • 我们可以自由使用任意长度的前缀名称
  • 仍然不会有冲突风险
  • switch tables
• 关于 penalization 的讨论 -> 关于在哈希后添加前缀
• Aaron 询问了哈希后前缀（address(pub_key) = key_type + hash(pub_key)）及其差异。Alan 指出，这种方法的地址空间更长，强度也更高。

• 使用相同算法合并树状地址是可行的

• 我们需要为模块地址设置一个原像前缀，以将其保持在 32 字节空间内：hash(hash('module') + module_key)
• Aaron 的观察：我们本来就需要处理变长问题（以避免破坏 secp256k1 密钥）。

• Posseidon / Rescue
• 问题：风险要大得多，因为我们对算术结构的密码分析技术和历史了解不多。这仍然是一个新的方向，也是活跃研究领域。

• Alan 的建议：Falcon，速度 / 大小比非常好。
• Aaron：我们应该考虑这个吗？ Alan：根据早期推测，这种技术将在 2050 年具备攻破 EC 密码学的能力。但这其中存在很大的不确定性。不过在递归 / 链接 / 模拟方面正在出现一些突破，可能会加快这一进展。

• 假设我们在两种不同用例中，对同一个密钥使用两种不同的地址算法，这样仍然安全吗？Alan：如果我们想隐藏公钥（这不是我们的用例），那安全性会更低，但也有对应的修复方法。

​

参考资料

• 笔记

​

Changelog

• 2020/08/18: Initial version
• 2021/01/15: Analysis and algorithm update

​

Status

​

Abstract

​

Context

​

Problem

​

Initial proposals

I spent quite a bit of time thinking about this issue while building weave… The other cosmos Sdk. Basically I define a condition to be a type and format as human readable string with some binary data appended. This condition is hashed into an Address (again at 20 bytes). The use of this prefix makes it impossible to find a preimage for a given address with a different condition (eg ed25519 vs secp256k1). This is explained in depth here Link And the code is here, look mainly at the top where we process conditions. Link

Yeah, AFAIK, 20 bytes should be collision resistance when the preimages are unique and not malleable. A space of 2^160 would expect some collision to be likely around 2^80 elements (birthday paradox). And if you want to find a collision for some existing element in the database, it is still 2^160. 2^80 only is if all these elements are written to state. The good example you brought up was eg. a public key bytes being a valid public key on two algorithms supported by the codec. Meaning if either was broken, you would break accounts even if they were secured with the safer variant. This is only as the issue when no differentiating type info is present in the preimage (before hashing into an address). I would like to hear an argument if the 20 bytes space is an actual issue for security, as I would be happy to increase my address sizes in weave. I just figured cosmos and ethereum and bitcoin all use 20 bytes, it should be good enough. And the arguments above which made me feel it was secure. But I have not done a deeper analysis.

​

Review and Discussions

• Choice of the hash function.
• Move the prefix out of the hash function: keyTypePrefix + sha256(keybytes)[:20] [post-hash-prefix-proposal].
• Use double hashing: sha256(keyTypePrefix + sha256(keybytes)[:20]).
• Increase to keybytes hash slice from 20 byte to 32 or 40 bytes. We concluded that 32 bytes, produced by a good hash functions is future secure.

​

Requirements

• Support currently used tools - we don’t want to break an ecosystem, or add a long adaptation period. Ref: Link
• Try to keep the address length small - addresses are widely used in state, both as part of a key and object value.

​

Scope

​

Decision

1. simple accounts: represented by a regular public key (ie: secp256k1, sr25519)
2. naive multisig: accounts composed by other addressable objects (ie: naive multisig)
3. composed accounts with a native address key (ie: bls, group module accounts)
4. module accounts: basically any accounts which cannot sign transactions and which are managed internally by modules

​

Legacy Public Key Addresses Don’t Change

• secp256k1: ripemd160(sha256(pk_bytes))[:20]
• legacy amino multisig: sha256(aminoCdc.Marshal(pk))[:20]

​

Hash Function Choice

​

Basic Address

const A_LEN = 32

func Hash(typ string, key []byte) []byte {
    return hash(hash(typ) + key)[:A_LEN]
}

• BLS: address.Hash("bls", pubkey)

​

Composed Addresses

// We don't need a PubKey interface - we need anything which is addressable.
type Addressable interface {
    Address() []byte
}

func Composed(typ string, subaccounts []Addressable) []byte {
    addresses = map(subaccounts, \a -> LengthPrefix(a.Address()))

addresses = sort(addresses)

return address.Hash(typ, addresses[0] + ... + addresses[n])
}

​

Multisig Addresses

package cosmos.crypto.multisig;

message PubKey {
  uint32 threshold = 1;
  repeated google.protobuf.Any pubkeys = 2;
}

func (multisig PubKey)

Address() {
	// first gather all nested pub keys
	var keys []address.Addressable  // cryptotypes.PubKey implements Addressable
    for _, _key := range multisig.Pubkeys {
    keys = append(keys, key.GetCachedValue().(cryptotypes.PubKey))
}

	// form the type from the message name (cosmos.crypto.multisig.PubKey)

and the threshold joined together
    prefix := fmt.Sprintf("%s/%d", proto.MessageName(multisig), multisig.Threshold)

	// use the Composed function defined above
	return address.Composed(prefix, keys)
}

​

Derived Addresses

func Derive(address, derivationKey []byte) []byte {
    return Hash(addres, derivationKey)
}

​

Module Account Addresses

address.Module(moduleName, key)

groupPolicyAddresses := []byte{1
}

address.Module(moduleName, groupPolicyAddresses, policyID)

func Module(moduleName string, derivationKeys ...[]byte) []byte{
    if len(derivationKeys) == 0 {
    return authtypes.NewModuleAddress(modulenName)  // legacy case
}
    submoduleAddress := Hash("module", []byte(moduleName) + 0 + key)

return fold((a, k) => Derive(a, k), subsubKeys, submoduleAddress)
}

btcPool := address.Module("lending", btc.Address()
})

btcAtomAMM := address.Module("amm", btc.Address() + atom.Address()
})

smartContractAddr = Module("mySmartContractVM", smartContractsNamespace, smartContractKey
})

// which equals to:
smartContractAddr = Derived(
    Module("mySmartContractVM", smartContractsNamespace), 
    []{
    smartContractKey
})

​

Schema Types

package cosmos.crypto.sr25519;

message PubKey {
	bytes key = 1;
}

​

Consequences

​

Backwards Compatibility

​

Positive

• a simple algorithm for generating addresses for new public keys, complex accounts and modules
• the algorithm generalizes native composed keys
• increased security and collision resistance of addresses
• the approach is extensible for future use-cases - one can use other address types, as long as they don’t conflict with the address length specified here (20 or 32 bytes).
• support new account types.

​

Negative

• addresses do not communicate key type, a prefixed approach would have done this
• addresses are 60% longer and will consume more storage space
• requires a refactor of KVStore store keys to handle variable length addresses

​

Neutral

• protobuf message names are used as key type prefixes

​

Further Discussions

​

Appendix: Consulting session

• we don’t need 2-preimage resistance
• we need 32bytes address space for collision resistance
• when an attacker can control an input for object with an address then we have a problem with birthday attack
• there is an issue with smart-contracts for hashing
• sha2 mining can be use to breaking address pre-image

• any attack breaking blake3 will break blake2
• Alan is pretty confident about the current security analysis of the blake hash algorithm. It was a finalist, and the author is well known in security analysis.

• Alan recommends to hash the prefix: address(pub_key) = hash(hash(key_type) + pub_key)[:32], main benefits:
  • we are free to user arbitrary long prefix names
  • we still don’t risk collisions
  • switch tables
• discussion about penalization -> about adding prefix post hash
• Aaron asked about post hash prefixes (address(pub_key) = key_type + hash(pub_key)) and differences. Alan noted that this approach has longer address space and it’s stronger.

• merging tree like addresses with same algorithm are fine

• we will need to set a pre-image prefix for module addresse to keept them in 32-byte space: hash(hash('module') + module_key)
• Aaron observation: we already need to deal with variable length (to not break secp256k1 keys).

• Posseidon / Rescue
• Problem: much bigger risk because we don’t know much techniques and history of crypto-analysis of arithmetic constructions. It’s still a new ground and area of active research.

• Alan suggestion: Falcon: speed / size ration - very good.
• Aaron - should we think about it? Alan: based on early extrapolation this thing will get able to break EC cryptography in 2050 . But that’s a lot of uncertainty. But there is magic happening with recurions / linking / simulation and that can speedup the progress.

• Let’s say we use same key and two different address algorithms for 2 different use cases. Is it still safe to use it? Alan: if we want to hide the public key (which is not our use case), then it’s less secure but there are fixes.

​

References

• Notes