🚧 Stagnant Standards Track: ERC

ERC-3772: 压缩整数

在 uint256 上使用有损压缩来提高 gas 成本，理想情况下可提高高达 4 倍。

Authors	Soham Zemse (@zemse)
Created	2021-08-27
Discussion Link	https://github.com/ethereum/EIPs/issues/3772

摘要
动机
规范
- 压缩
- 解压缩
理由
向后兼容性
参考实现
安全注意事项
版权

摘要

本文档规定将 uint256 压缩为更小的数据结构，如 uint64、uint96、uint128，以优化存储成本。较小的数据结构（表示为 cintx）分为两部分，第一部分存储 significant 位，另一部分存储对 significant 位进行解压缩所需的左 shift 的数量。由于压缩本质上是有损的，即会导致下溢，因此本文档还包括两个解压缩规范。

动机

存储成本高昂，每个存储槽的初始化成本几乎为 0.8 美元，更新成本为 0.2 美元（20 gwei，2000 ETHUSD）。
通常，我们将金额存储在占用整个槽的 uint256 中。
如果是 DAI 值，我们最常使用的范围是 0.001 DAI 到 1T DAI（或 10¹²）。如果是 ETH 值，我们最常使用的范围是 0.000001 ETH 到 1B ETH。同样，任何规模的任何 token 都有一个合理的 10¹⁵ 金额范围，我们关心/使用这些金额。
但是，uint256 类型允许我们表示 $10^-18 到 $10⁵⁸，其中大部分是浪费。用技术术语来说，我们认为大于 $10¹⁵ 且小于 $10^-3 的值的概率分布可以忽略不计（即 P[val > 10¹⁵] ≈ 0 且 P[val < 10^-3] ≈ 0）。
表示 10¹⁵ 个值所需的位数 = log₂(10¹⁵) = 50 位。因此，仅 50 位（而不是 256 位）就足以表示实际的金额范围，从而导致非常小的差异。

规范

在本规范中，用于表示压缩值的结构使用 cintx 表示，其中 x 是整个压缩值占用的位数。在实现层面上，可以使用 uintx 来存储 cintx 值。

压缩

uint256 压缩为 cint64（最高 cint120）

cintx 中最右边或最低有效位的 8 位保留用于存储 shift，其余可用位用于存储从 uintx 中的第一个 1 位开始的有效位。

struct cint64 { uint56 significant; uint8 shift; }

// ...

struct cint120 { uint112 significant; uint8 shift; }

uint256 压缩为 cint128（最高 cint248）

cintx 中最右边或最低有效位的 7 位保留用于存储 shift，其余可用位用于存储从 uintx 中的第一个 1 位开始的有效位。

在以下代码示例中，uint7 仅用于表示目的，但应注意，Solidity 中的 uint 是 8 的倍数。

struct cint128 { uint121 significant; uint7 shift; }

// ...

struct cint248 { uint241 significant; uint7 shift; }

示例：

示例：
uint256 value: 2**100, 二进制表示: 1000000...(一百个零)
cint64 { significant: 10000000...(55 个零), shift: 00101101 (十进制为 45)}

示例：
uint256 value: 2**100-1, 二进制表示: 111111...(一百个一)
cint64 { significant: 11111111...(56 个一), shift: 00101100 (十进制为 44) }

解压缩

定义了两种解压缩方法：一种是普通的 decompress，另一种是 decompressRoundingUp。

library CInt64 {
    // 将 uint256 金额打包到 cint64 中
    function compress(uint256) internal returns (cint64) {}

    // 通过将有效位左移 shift 来解包 cint64
    function decompress(cint64) internal returns (uint256) {}

    // 通过将有效位左移 shift
    // 并在移动位中包含 1 来解包 cint64
    function decompressRoundingUp(cint64) internal returns (uint256) {}
}

普通解压缩

cintx 中的 significant 位被移动到 uint256 空间，并左移 shift 位。

注意：在以下示例中，cint16 用于视觉演示目的。但应注意，它绝对不适合存储金额，因为其有效位容量为 8，而存储金额至少需要 50 位。

示例：
cint16{significant:11010111, shift:00000011}
解压缩后的 uint256: 11010111000 // 左移 3 位

示例：
cint64 { significant: 11111111...(56 个一), shift: 00101100 (十进制为 44) }
解压缩后的 uint256: 1111...(56 个一)0000...(44 个零)

连同向上舍入一起解压缩

cintx 中的 significant 位被移动到 uint256 空间，并左移 shift 位，并且最低有效 shift 位为 1。

示例：
cint16{significant:11011110, shift:00000011}
解压缩后的向上舍入值: 11011110111 // 左移 3 位，并将 0 替换为 1

示例：
cint64 { significant: 11111111...(56 个一), shift: 00101100 (十进制为 44) }
解压缩后的 uint256: 1111...(100 个一)

此规范供新的智能合约使用，用于管理其内部状态，以便对它的任何状态更改调用都可以更便宜。智能合约状态上的这些压缩值不应暴露给外部世界（其他智能合约或客户端）。如果需要，智能合约应公开解压缩的值。

理由

significant 位存储在 cintx 的最高有效部分，而 shift 位存储在最低有效部分，以帮助防止明显的开发错误。例如，如果排列方式与指定的相反，则小于 2⁵⁶-1 的数的压缩 cint64 值将是其本身。如果开发人员忘记在使用值之前对其进行解压缩，则如果压缩值与解压缩值相同，则这种情况仍然会通过。
应该注意的是，使用 cint64 不会自动节省 gas。Solidity 编译器需要将更多数据打包到同一存储槽中。
此外，打包和解包也会增加一些小成本。
虽然此设计也可以看作是二进制浮点表示，但是在此 ERC 的范围内不包括在 EVM 上使用浮点数。浮点数的主要目标是能够在可用位数中表示更广泛的范围，而此 ERC 中压缩的目标是尽可能保持精度。因此，它指定使用最小指数/shift 位（即，最高为 uint120 时为 8，最高为 uint248 时为 7）。

// 使用 3 个槽
struct UserData1 {
    uint64 amountCompressed;
    bytes32 hash;
    address beneficiary;
}

// 使用 2 个槽
struct UserData2 {
    uint64 amountCompressed;
    address beneficiary;
    bytes32 hash;
}

向后兼容性

没有已知的向后不兼容问题。

参考实现

在实现层面上，可以直接使用 uint64，也可以使用 0.8.9 中引入的自定义类型。

function compress(uint256 full) public pure returns (uint64 cint) {
    uint8 bits = mostSignificantBitPosition(full);
    if (bits <= 55) {
        cint = uint64(full) << 8;
    } else {
        bits -= 55;
        cint = (uint64(full >> bits) << 8) + bits;
    }
}

function decompress(uint64 cint) public pure returns (uint256 full) {
    uint8 bits = uint8(cint % (1 << 9));
    full = uint256(cint >> 8) << bits;
}

function decompressRoundingUp(uint64 cint) public pure returns (uint256 full) {
    uint8 bits = uint8(cint % (1 << 9));
    full = uint256(cint >> 8) << bits + ((1 << bits) - 1);
}

上面的 gist 具有 library CInt64，其中包含用于 cint64 的压缩、解压缩和算术的演示逻辑。该 gist 还有一个使用该库进行演示的示例合约。

CInt64 格式仅用于存储，而开发人员应使用合适的逻辑（解压缩或 decompressRoundingUp）将其转换为 uint256 形式，以便对其执行任何算术运算。

安全注意事项

讨论了以下安全注意事项：

有损压缩的影响
- cint64 的误差估计
- 处理错误
由于不正确使用 cintx 而导致的精度损失
压缩除货币 uint256 之外的内容。

1. 有损压缩的影响

压缩值时，会导致下溢，即牺牲一些不太重要的位。这导致 cintx 值的解压缩值小于或等于实际的 uint256 值。

uint a = 2**100 - 1; // 二进制格式中的 100 个 1
uint c = a.compress().decompress();

a > c; // true
a - (2**(100 - 56) - 1) == c; // true

// 可视化示例：
// 之前：1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
// 之后：1111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000

cint64 的误差估计

假设我们有一个 2^m 阶的值（小于 2^m 且大于或等于 2^m-1）。

对于所有满足 2^m - 1 - (2^m-56 - 1) <= value <= 2^m - 1 的值，压缩值 cvalue 为 2^m - 1 - (2^m-56 - 1)。

最大误差为 2^m-56 - 1，将其近似为十进制：10^n-17 (log₂(56) 为 17)。这里的 n 是十进制位数 + 1。

例如，将 $1,000,000,000,000（或 1T 或 10¹²）量级的值压缩为 cint64，则最大误差为 10^12+1-17 = $10^-4 = $0.0001。这意味着小数点后 4 位的精度会丢失，或者我们可以说未压缩的值最多小 $0.0001。同样，如果有人将 $1,000,000 存储到 cint64 中，则未压缩的值最多小 $0.0000000001。相比之下，存储成本几乎是初始化 $0.8 和更新 $0.2（20 gwei，2000 ETHUSD）。

处理错误

请注意，压缩会使值略微变小（下溢）。但是我们还有另一个操作也会这样做。在整数数学中，除法是一种有损操作（导致下溢）。例如，

10000001 / 2 == 5000000 // true

除法运算的结果并不总是精确的，但它小于实际值，在某些情况下如上例所示。但是，大多数工程师尝试通过在最后进行所有除法来减少这种影响。

1001 / 2 * 301 == 150500 // true
1001 * 301 / 2 == 150650 // true

除法运算已在实际中使用，并且已经发生了大量的有损整数除法，导致 DeFi 用户获得的提款金额非常非常少，他们甚至没有注意到。如果小心谨慎，则风险非常小。压缩是相似的，因为它也是除以 2^shift。如果对此也小心谨慎，则可以最大程度地减少影响。

通常，应遵循以下规则：

当智能合约必须将压缩金额转账给用户时，他们应使用向下舍入的值（通过使用 amount.decompress()）。
当智能合约必须从用户那里 transferFrom 压缩金额给自己时，即收取一些账单，他们应该使用向上舍入的值（通过使用 amount.decompressUp()）。

以上确保了智能合约不会因压缩而损失金钱，而是用户收到较少的资金或支付更多的资金。舍入的程度对于用户来说已经足够可以忽略。还要提到的是，这种向上和向下舍入模式在包括 UniswapV3 在内的许多项目中都可以观察到。

2. 由于不正确使用 `cintx` 而导致的精度损失

这是一个开发人员在使用压缩时出错可能成为问题的示例。

通常，用户金额的熵最大为 50，即使用中的 10¹⁵（或 2⁵⁰）个值，这就是为什么我们发现 uint56 足够存储有效位的原因。但是，让我们看一个例子：

uint64 sharesC = // 从存储中读取压缩值；
uint64 price = // CALL;
uint64 amountC = sharesC.cmuldiv(price, PRICE_UNIT);
user.transfer(amountC.uncompress());

上面的代码会导致严重的精度损失。sharesC 的熵为 50，并且 priceC 的熵也为 50。当我们乘以它们时，我们得到一个包含两者熵的值，因此熵为 100。完成乘法后，cmul 压缩该值，这将 amountC 的熵降至 56（因为我们有 uint56 在那里存储有效位）。

为了防止熵/精度下降，我们摆脱了压缩。

uint64 sharesC = shares.compress();
uint64 priceC = price.compress();
uint256 amount = sharesC.uncompress() * price / PRICE_UNIT;
user.transfer(amount);

压缩仅在写入存储时有用，而对它们进行算术运算时应非常小心。

3. 压缩除货币 `uint256` 之外的内容。

压缩整数旨在仅压缩金额。从技术上讲，uint256 可以存储大约 10⁷⁷ 个值，但是这些值中的大多数值都是平坦分布的，即概率为 0 或极小。（用户向合约存入 1000T DAI 或 1T ETH 的概率是多少？在正常情况下它不会发生，除非有人完全可以访问 mint 函数）。只有人们使用的金额才具有非零分布（$0.001 DAI 到 $1T 或 uint256 中的 10¹⁵ 到 10³⁰）。50 位足以表示此信息，只是为了将其四舍五入，我们使用 56 位来提高精度。

使用相同的方法压缩其他具有完全不同概率分布的内容可能会导致问题。如果您不确定 uint256 将要采用的值的分布，最好不要压缩。而且，对于您认为确定要使用压缩的内容，最好多考虑一下压缩是否会导致极端情况（例如，在先前的乘法示例中）。

4. 压缩稳定货币金额与波动货币金额

由于我们有一个可以四处移动的动态 uint8 shift 值。因此，即使您想表示 100 万个 SHIBA INU token 或 0.0002 WBTC（截至撰写本文时均为 10 美元），cint64 也会选择其前 56 个有效位来处理值表示。

如果硬币相对于用户的本地货币极不稳定，则可能会出现问题。想象一下一个非常不可能的情况，硬币上涨了 2⁵⁶ 倍（价格上涨了 10¹⁶ lol）。在这种情况下，uint56 可能不够，因为即使其最低有效位也非常有价值。如果要存储如此疯狂波动的 token，则应存储更多有效位，即使用 cint96 或 cint128。

cint64 具有 56 位用于存储有效位，而实际上仅需要 50 位。因此，还有 6 个额外的位，这意味着如果以 cint64 存储的加密货币的美元价值增加 2⁶ 或 64 倍，那就可以了。如果价值下降，则不是问题。

版权

通过 CC0 放弃版权和相关权利。

Citation

Please cite this document as:

Soham Zemse (@zemse), "ERC-3772: 压缩整数 [DRAFT]," Ethereum Improvement Proposals, no. 3772, August 2021. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-3772.