最小化密钥库rollup方案规范

针对 Vitalik 的 密钥库专用最小化 Rollup 的规范。

简介

随着账户抽象的兴起，用户将开始在多个链上使用智能合约钱包（SCW）。这带来了一个挑战：如何保持他们在各个链上的钱包同步？特别是，如果用户在一个 L2 上更改了他们的签名密钥，该更改如何传播到其他链？

这些问题和一些解决方案在 Vitalik 的 关于钱包和其他用例的跨 L2 读取的深入探讨 帖子中进行了讨论。

需求

我们首先描述所需的功能集。一个解决方案应该为 SCW 实现以下功能：

• 新钱包在所有链上立即可用：无需等待状态同步或链间消息。
• 使用此钱包的交易费用在 L2 上是合理的。
• 更新你的签名者的成本是合理的（1 美元可能可以接受，但不能 > 10 美元）。
• 签名者更新在合理的时间内传播到所有链（理想情况下是几分钟，最多 1 小时）。
• 钱包实现可以为签名验证和签名者更改定义自定义逻辑。示例：
  • 具有单个签名者的 secp256r1 密码钥匙钱包
  • 具有 m of n 阈值要求的 secp256k1 多重签名钱包
  • BLS 或 EdDSA 签名验证

解决方案

我们创建一个新的最小密钥库 Rollup（MKSR），它是一个Based Rollup，将其 Merkle 树状态根存储在 L1 上。它是更深入探讨文章中概述的 ZK-SNARK 证明解决方案的实现。

如果用户想要更改他们的 SCW 签名者，他们可以提交一个 SNARK，证明他们有权访问他们 SCW 的当前签名者。用户可以选择将此证明提交到单独的 MKSR mempool，或者直接提交到 L1，这提供了一种强制包含机制。这些证明在电路中进行验证，以节省恢复操作的 Gas 成本。

要从使用此 Rollup 的 SCW 发送交易，用户可以生成 Merkle 证明的 SNARK，以在任何可以访问存储在 L1 上的 MKSR 状态根的链上证明他们的 SCW 的当前签名者。

虽然我们主要设计此方案来解决跨链密钥库状态的问题，但它可用于存储任何目的的配置。它只是一个无需许可的可证明的多链 KV 存储。

设计

Rollup 状态

Rollup 的状态存储为 BN254 Poseidon 索引 Merkle 树（IMT），深度为 64。树中的每个键值对都编码了用户当前的 SCW 配置（例如，签名者 + 阈值）。

钱包创建

用户创建一个 ZK 电路（参见 Account 电路），该电路定义了验证和更新其签名者的逻辑。该电路使用 BLS12-377 上的 PLONK 进行编译，以生成一个证明密钥和验证密钥（original_vk）。或者，用户可以从实现不同逻辑的预编译电路列表中进行选择（例如，ECDSA 签名检查或基本哈希密码检查等）。

然后，用户定义一个 256 字节的数组（original_data），其中包含 SCW 签名者配置。在最简单的情况下，这可能包含一个 secp256k1 公钥，或者包含多个带有附加的多重签名阈值规则的公钥。

用户的 key 定义为：

key = poseidon_bn254(keccak256(original_vk) >> 8, keccak256(original_data) >> 8)

此 key 是用于 IMT 排除/包含证明的密钥。

keccak256 哈希右移 8 位，以确保它们适合字段元素（理论上可以移动 3，但 8 通过坚持字节边界使电路中的 Keccak 稍微简单一些）。这也在下面的其他 keccak256 哈希实例中完成。

该电路必须接受 10 个公共输入：data 的 256 字节的 9 个字段元素（前 8 个包含 31 字节的块，最后一个包含最后的 8 个字节）和一个额外的 newKey 元素。该电路可以选择针对 data + newKey 进行验证； 例如，它可以检查是否提供了 newKey 的有效 ECDSA 签名。

为了为不同的电路生成恒定大小的验证密钥和证明，预计这些电路将只有 3 个承诺。

钱包中 key 的用法

用户创建一个 SCW，该 SCW 将其 key 硬编码为不可变值。为了验证 key 的当前状态，SCW 签名验证逻辑可以执行以下操作（在上面提到的简单 ECDSA 情况下）：

• 需要一个 signature、publicKey 和 stateProof 作为输入
• 使用 publicKey 的私钥验证 signature 是否对预期数据（例如，userOpHash）进行签名
• 使用 BN254 PLONK 证明验证传递的 publicKey 是否是 IMT 中为 SCW 中硬编码的 key 提供的当前 value，进行 IMT 排除/包含的验证（参见 State 电路）。

为了使钱包能够立即使用而无需等待密钥库传播，用户可以提供排除证明，证明 IMT 中不存在其 key。如果他们过去执行过恢复，他们将必须提供包含证明，证明密钥中的当前 value 与他们传递的 publicKey 匹配（编码在哈希到存储在 IMT 中的 newKey 值的 data 变量中）。

通过 Rollup 恢复

要更改 SCW 签名者（又名“恢复”），用户可以将以下数据提交到 MKSR Rollup：

• uint256 key：用户的原始密钥，由 poseidon_bn254(keccak256(original_vk) >> 8, keccak256(original_data) >> 8) 计算
• uint256 newKey：新密钥，由 poseidon_bn254(keccak256(new_vk) >> 8, keccak256(new_data) >> 8) 计算
• uint256 currentVkHash：IMT 中编码的 vk 的当前值，如果未对此 key 执行恢复，则为 original_vk（vk 必须已经通过上面的 submitVk 提交）
• bytes currentData：IMT 中编码的 data 的当前值，如果未对该 key 执行恢复，则为 original_data（可以是前缀 3）
• bytes proof：一个针对 currentVk 验证的证明，当传入 currentData + newKey >> 2 作为公共输入时

稍后，证明者会将此交易包含在一个区块中，其中包括将 key / newKey 元组提交给 KeyStore 合约，以及新的 IMT 根和状态更改证明。

通过 L1 恢复

或者，用户可以将 MKSR 交易直接提交到 L1 上的 KeyStore 合约。

每个验证密钥 vk 必须在可用于 L1 恢复之前在 KeyStore 合约中“注册”。这节省了恢复路径上的 calldata 成本，因为多个用户可以为流行的账户电路共享相同的 vk。要注册 vk，用户可以调用 KeyStore.submitVk 函数，该函数将对 vk 进行 keccak256 哈希，右移 8，并将其存储在 mapping(uint256 => bool) 存储变量中。

为了执行恢复，用户将与上面相同的字段集提交到 L1 上的 KeyStore 合约。 KeyStore 合约计算将连接的这些输入进行 keccak256 哈希，并在前面加上之前的哈希：

currentDataHash = uint256(keccak256(currentData)) >> 8;
txHash = uint256(keccak256(abi.encodePacked(
    txHash, originalKey, newKey, currentVkHash, currentDataHash, proof
))) >> 8;

这充当强制包含/反审查机制。在证明区块时，KeyStore 合约使用 txHash 作为证明验证的公共输入。证明者必须在电路中执行相同的哈希，因此证明了每个交易都以相同的顺序包含在内。这使得 Rollup 成为一个Based Rollup。

合约

赤裸的 KeyStore 合约：

contract KeyStore {
    struct OffchainTransaction {
        uint256 originalKey;
        uint256 newKey;
    }

    uint256 public root;

    mapping(uint256 => bool) public knownVk;
    uint256 public txHash;
    uint256 public pendingTxHash;

    IVerifier public immutable blockVerifier;

    function submitVk(bytes calldata vk) external {
        uint256 h = uint256(keccak256(vk)) >> 8;
        require(!knownVk[h], "vk already known");
        knownVk[h] = true;
    }

    function recover(
        uint256 originalKey,
        uint256 newKey,
        uint256 currentVkHash,
        bytes calldata currentData,
        bytes calldata proof
    ) external {
        require(knownVk[currentVkHash], "vk not known");

        bytes memory currentDataFull = new bytes(256);
        for (uint256 i = 0; i < currentData.length; i++) {
            currentDataFull[i] = currentData[i];
        }

        uint256 currentDataHash = uint256(keccak256(currentDataFull)) >> 8;
        pendingTxHash = uint256(keccak256(abi.encodePacked(pendingTxHash, originalKey, newKey, currentVkHash, currentDataHash, proof))) >> 8;
    }

    function prove(uint256 newRoot, OffchainTransaction[] calldata offchainTxs, bytes calldata proof) external {
        uint256 allTxsHash = pendingTxHash;
        for (uint256 i = 0; i < offchainTxs.length; i++) {
            allTxsHash = uint256(keccak256(abi.encodePacked(allTxsHash, offchainTxs[i].originalKey, offchainTxs[i].newKey))) >> 8;
        }

        uint256[] memory public_inputs = new uint256[](3);
        public_inputs[0] = root;
        public_inputs[1] = newRoot;
        public_inputs[2] = allTxsHash;
        require(blockVerifier.Verify(proof, public_inputs), "proof is invalid");

        root = newRoot;
        txHash = pendingTxHash;
    }
}

此合约被有意简化；实际上，将会有某种形式的每个区块的 pendingTxHash，以避免通过在证明生成期间提交另一笔交易来对证明者进行恶意攻击（参见下面的Rollup 区块证明）。

电路

我们使用 BN254 进行在 EVM 上执行的任何证明验证，因为自 EIP-196 以来，以太坊支持对此曲线的有效验证。

我们使用 BW6-761，因为它与 BLS12-377 形成 2 链，从而可以有效地在 BW6-761 中验证 BLS12-377 证明。

我们早期探索的更简单的设计没有使用递归，而是依靠用户将 BN254 证明直接提交给 L1 以进行恢复。但是，由于恢复的高额费用（2kb 的 calldata 和 350k 的 gas 来验证 PLONK 证明），我们认为这是一个不可行的情况。

此设计涉及 5 个电路；每个用户的帐户有 2 个（State，Account），以及专门用于密钥库的 3 个（Hash，Batch，Update）。

State 电路

SCW 使用的每个帐户电路，用于验证 IMT 中的密钥排除或键值包含。这用于每个 SCW 交易，与恢复分开。此电路仅由 SCW 使用，而不由密钥库使用，因此可以由 SCW 构建器自定义。通常，期望是接受 SCW key、密钥库的 IMT root 和 keccak256(currentData) >> 8 作为公共输入，并针对 root 执行 key IMT 验证。这使用 BN254 曲线，以便在以太坊上进行廉价验证。

曲线

BN254

公共输入

私有输入

伪代码

inclusion = lowKey == originalKey
currentKey = poseidonBN254(currentVkHash, currentDataHash)

if inclusion:
    assert(currentKey == currentValue)
else:
    assert(currentKey == originalKey)

imtVerify(
    root=root,
    size=size,
    key=originalKey,
    value=currentValue,
    index=index,
    nextKey=nextKey,
    lowKey=lowKey,
    siblings=siblings,
    inclusion=inclusion
)

Account 电路

用于验证用户提供的密钥库更新证明的每帐户电路。可以由用户自定义，并且需要接受 9 个字段元素（表示 data）和一个表示 newKey 的字段元素作为公共输入。使用 BLS12-377 曲线。在下面的 Batch 电路中进行验证。此电路的验证密钥是用户的 vk 值。

曲线

BLS12-377

公共输入

私有输入（secp256k1 签名帐户的示例）

伪代码

publicKey = currentData[0:3]
verifySignature(
    public=publicKey,
    msg=newKey,
    sig=[signatureR,signatureS]
)

Hash 电路

此电路负责通过证明数据的 keccak256 哈希与 txHash 输入匹配来确保证明者提供的交易数据正确。还验证 currentVk 和 currentData 的 keccak256 哈希。公共输入是来自 Batch 电路的输入数据的 BW6-761 Poseidon 哈希。使用 BLS12-377 曲线。

曲线

BLS12-377

公共输入

私有输入（secp256k1 签名帐户的示例）

伪代码

currentVkHash = keccak256(currentVk)
currentDataHash = keccak256(currentData)
onchainTxHash = keccak256(prevTxHash, originalKey, newKey, currentVkHash, currentDataHash, proof)
offchainTxHash = keccak256(prevTxHash, originalKey, newKey)
assert((offchain ? offchainTxHash : onchainTxHash) == nextTxHash)

currentKey = poseidonBN254(currentVkHash, currentDataHash)
stateHash = poseidonBN254(enabled, originalKey, currentKey, newKey, nextTxHash)
actualHash = poseidonBW6761(stateHash, currentVk, currentData, proof)
assert(actualHash == inputHash)

Batch 电路

负责证明一批或一个区块的交易。使用 BW6-761 曲线。公共输入是来自 Update 电路的单个 BN254 Poseidon 哈希。对于密钥库 Rollup 区块中的每个交易，此电路执行两个电路内证明验证：

• Account：确保用户提供了针对交易中提供的 vk、data 和 newKey 值进行验证的证明。
• Hash：确保证明者为每个交易使用正确的值，并防止任何恶意审查。

曲线

BW6-761

公共输入

私有输入（secp256k1 签名帐户的示例）

Transaction 类型：

伪代码

actualHash = poseidonBN254(selector, stateHashes...)
assert(actualHash == stateHash)

selectorBits = toBinary(selector)
for i, tx in txs:
    valid = verifyProof(
        vk=tx.currentVk,
        public=[tx.currentData..., tx.newKey],
        proof=tx.proof
    ) // verifyProof 必须返回 0 或 1
    assert(valid == selector[i])

    stateHash = poseidonBW6761(tx.stateHash, tx.currentVk, tx.currentData, tx.proof)
    valid = verifyHashProof(
        public=[stateHash],
        proof=tx.hashProof
    )
    assert(valid)

Update 电路

该电路负责验证区块中每个交易的 IMT 更新。它还对以下 Batch 电路的证明进行电路内验证。公共输入为 OldRoot、NewRoot 和 TxHash。使用 BN254 曲线，并在以太坊上从 KeyStore 合约进行验证。

曲线

BN254

公共输入

私有输入（secp256k1 签名帐户的示例）

Update 类型：

伪代码

selectorBits = toBinary(selector)
root = oldRoot
stateHashes = [selector]

for i, u in updates:
    update = (u.originalKey == u.lowKey)

    newRoot = imtMutate(
        oldRoot=root,
        key=u.originalKey,
        value=u.newKey,
        nextKey=u.nextKey,
        index=u.index,
        lowKey=u.lowKey,
        lowValue=u.lowValue,
        lowIndex=u.lowIndex,
        siblings=u.siblings,
        lowSiblings=u.lowSiblings,
        oldSiblings=u.oldSiblings,
        exists=exists
    )
    updateValid = u.currentKey == (update ? u.lowValue : u.originalKey)
    root = (updateValid && selector[i]) ? newRoot : root

    stateHashes.push(poseidonBN254(selector[i], u.originalKey, u.currentKey, u.newKey, u.nextTxHash))

valid = verifyBatchProof(
    public=[poseidonBN254(stateHashes...)],
    proof=proof
)
assert(valid)

Rollup 区块证明

prove 方法是无需许可的，任何人都可以提交区块证明（到 Update 电路）以推动 Rollup 前进。

为了计算有效的证明，证明者必须：

• 为提交给 KeyStore.recover 方法的每个交易生成 Hash 证明
• 验证（或不验证）交易中提供的每个证明，并为有效证明生成带有 1 位的 selector，为无效证明生成 0 位
• 使用 Hash 证明和交易证明作为输入，生成 Batch 证明。
• 根据具有有效证明的交易中给出的更新，计算 IMT 的新根。
• 生成一个 Update 证明，并将其提交给 KeyStore.prove 方法。

KeyStore 合约可以通过生成具有不同 TxCount 常量的电路来接受不同大小的区块。请注意，给定交易有效性 selector，当前设计不能在单个区块中包含超过 253 个交易。实际上，我们可能会将此限制为每个区块 128 个交易，以便更容易生成证明。

存在一个竞争条件，即用户可以在证明者证明 Keystore.pendingTxHash 指示的当前交易集时提交交易。我们要么通过将每个未经验证的 txHash 存储在存储中来解决此问题，要么存储每 16 个或 32 个哈希，因此证明者可以证明恒定大小的交易区块而不会受到恶意攻击。在证明提交的成本和保持 IMT 状态根从最近的交易中保持新鲜之间存在权衡。

经济学

WIP

必须有一些激励措施来让证明者为 Rollup 提供证明才能使其正常运行。以下是一些选项：

• 用户需要通过一些 msg.value 作为调用 KeyStore.recover 的一部分来预先支付交易证明的费用。这可以分发给验证者。如果用户的交易是一个更大的批次的一部分，则可以选择用户可以获得退款（因此每次交易的费用更便宜，因为提交证明的费用是恒定的）。
• 密钥库合约可能具有一些 tipping 功能，要求实体通过在合约中存储赏金来激励证明者。
• 某种形式的荷兰反向拍卖可能会起作用，其中证明奖励随着时间的推移而增加，并在提交证明时重置。

可信设置

此提案需要三个可信设置：

• BN254 KZG，用于 Update 电路（约 4500 万个约束）
  • 我们很可能可以在这里重用 Hermez 可信设置
• BW6-671 KZG，用于 Batch 电路（约？约束）
• BLS12-377 KZG，用于 Hash + Account 电路（约 2000 万个约束）

我们需要这些仪式的 Powers of Tau，或者依赖其他人（参见此处链接的一些）。

将密钥库根同步到 L2

目前没有标准化方法来读取 L2 上的 L1 状态。大多数 L2 都有一些引用当前 L1 区块哈希的能力，该哈希可用于使用 Merkle-Patricia-Tree（MPT）证明来证明 KeyStore.root 的当前值。

一些 L2 支持通过“存款”从 L1 向 L2 发送消息。这些机制可用于以无需信任的方式将密钥库根从 L1 同步到 L2。

隐身地址

此 Rollup 可用于 隐身地址，而无需更改协议。我们可以向存储在 SCW 中的 key 添加一个 salt，这样密钥变为：

imt_key = poseidon_bn254(keccak256(original_vk) >> 8, keccak256(original_data) >> 8)
scw_key = poseidon_bn254(salt, imt_key)

然后，State 电路将 salt 作为附加的私有输入，并在电路中执行附加的哈希。

因此，Alice 可以通过生成随机盐来为由 Bob 的密钥控制的 SCW 生成一个反事实地址（只要她知道 Bob 的 imt_key 即可）。

未来的改进

4337 + PLONK 证明保证

目前，对于使用密钥库的钱包的每个 SCW 交易，仍然存在相当大的 Gas 成本。验证 PLONK 证明主要是计算 Gas，这在 L2 上通常很便宜，因为区块低于其目标 Gas（因此基本费用很低）。但是，证明大小约为 1kb，calldata 是 L2 上交易成本的主要部分。 4844 将在此处提供帮助，我们可以为捆绑中的多个密钥库交易进行一些证明聚合。

任何降低 4337 和/或 PLONK 验证成本的协议改进都将进一步降低费用。

Blob DA

目前，所有密钥库 Rollup 交易都作为 calldata 提交给 L1，提交者是用户或证明者。我们可以通过将成批的交易作为 4844 blobs 提交来降低交易成本。但请注意，这将增加每个交易的 IMT 根更新的最终确定时间，因为我们必须等待 blobs 填满才有意义发布和证明它们。

• 原文链接： hackmd.io/@mdehoog/mksr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～