EIP-6800: 使用统一 Verkle 树的以太坊状态

# Bandersnatch 曲线阶数
BANDERSNATCH_MODULUS = \
13108968793781547619861935127046491459309155893440570251786403306729687672801
# 长度为 256 的 Bandersnatch Pedersen 基
PEDERSEN_BASIS = [....]
VERKLE_NODE_WIDTH = len(PEDERSEN_BASIS)

def group_to_scalar_field(point: Point) -> int:
    # 不是抗碰撞的。不是随机预言机。
    # Pedersen 承诺的绑定。
    assert isinstance(point, Point)
    if point == bandersnatch.Z:
        return 0
    else:
        return point.map_to_base_field() % BANDERSNATCH_MODULUS
    
def compute_commitment_root(children: Sequence[int]) -> Point:
    o = bandersnatch.Z
    for generator, child in zip(PEDERSEN_BASIS, children):
        o = bandersnatch.add(o, bandersnatch.mul(generator, child))
    return o

def extension_and_suffix_tree(stem: bytes31, values: Dict[byte, bytes32]) -> int:
    sub_leaves = [0] * 512
    for suffix, value in values.items():
        sub_leaves[2 * suffix] = int.from_bytes(value[:16], 'little') + 2**128
        sub_leaves[2 * suffix + 1] = int.from_bytes(value[16:], 'little')
    C1 = compute_commitment_root(sub_leaves[:256])
    C2 = compute_commitment_root(sub_leaves[256:])
    return compute_commitment_root([1, # 扩展标记
                                    int.from_bytes(stem, "little"),
                                    group_to_scalar_field(C1),
                                    group_to_scalar_field(C2)] +
                                    [0] * 252)

def compute_main_tree_root(data: Dict[bytes32, int],
                           prefix: bytes) -> int:
    # 空子树：0
    if len(data) == 0:
        return 0
    elif len(data) == 1:
        return list(data.values())[0]
    else:
        sub_commitments = [
            compute_main_tree_root({
                    key: value for key, value in data.items() if
                    key[:len(prefix) + 1] == prefix + bytes([i])
                }, prefix + bytes([i]))
            for i in range(VERKLE_NODE_WIDTH)
        ]
        return group_to_scalar_field(compute_commitment_root(sub_commitments))

def compute_verkle_root(data: Dict[bytes32, bytes32]) -> Point:
    stems = set(key[:-1] for key in data.keys())
    data_as_stems = {}
    for stem in stems:
        commitment_data = Dict[byte, bytes32]()
        for i in range(VERKLE_NODE_WIDTH):
            if stem + bytes([i]) in data:
                commitment_data[i] = data[stem + bytes([i])]
        data_as_stems[stem] = extension_and_suffix_tree(stem, commitment_data)
    sub_commitments = [
        compute_main_tree_root({
                key: value for key, value in data.items() if
                key[0] == i
            }, bytes([i]))
        for i in range(VERKLE_NODE_WIDTH)
    ]
    return compute_commitment_root(sub_commitments)

def old_style_address_to_address32(address: Address) -> Address32:
    return b'\x00' * 12 + address

def hash_point_to_bytes(point: Point) -> int:
    return group_to_scalar_field(point).to_bytes(32, 'little')

def pedersen_hash(inp: bytes) -> bytes32:
    assert len(inp) <= 255 * 16
    # 将输入解释为 128 位（16 字节）整数列表
    ext_input = inp + b"\0" * (255 * 16 - len(inp))
    ints = [2 + 256 * len(inp)] + \
           [int.from_bytes(ext_input[16 * i:16 * (i + 1)], 'little') for i in range(255)]
    return compute_commitment_root(ints).hash_point_to_bytes()

def get_tree_key(address: Address32, tree_index: int, sub_index: int):
    # 假设 VERKLE_NODE_WIDTH = 256
    return (
        pedersen_hash(address + tree_index.to_bytes(32, 'little'))[:31] +
        bytes([sub_index])
    )
    
def get_tree_key_for_basic_data(address: Address32):
    return get_tree_key(address, 0, BASIC_DATA_LEAF_KEY)

# EXTCODEHASH 的向后兼容性
def get_tree_key_for_code_hash(address: Address32):
    return get_tree_key(address, 0, CODE_HASH_LEAF_KEY)

def get_tree_key_for_code_chunk(address: Address32, chunk_id: int):
    return get_tree_key(
        address,
        (CODE_OFFSET + chunk_id) // VERKLE_NODE_WIDTH,
        (CODE_OFFSET + chunk_id)  % VERKLE_NODE_WIDTH
    )

PUSH_OFFSET = 95
PUSH1 = PUSH_OFFSET + 1
PUSH32 = PUSH_OFFSET + 32

def chunkify_code(code: bytes) -> Sequence[bytes32]:
    # 填充到 31 字节的倍数
    if len(code) % 31 != 0:
        code += b'\x00' * (31 - (len(code) % 31))
    # 确定在每个字节之后+包括多少个 pushdata
    bytes_to_exec_data = [0] * (len(code) + 32)
    pos = 0
    while pos < len(code):
        if PUSH1 <= code[pos] <= PUSH32:
            pushdata_bytes = code[pos] - PUSH_OFFSET
        else:
            pushdata_bytes = 0
        pos += 1
        for x in range(pushdata_bytes):
            bytes_to_exec_data[pos + x] = pushdata_bytes - x
        pos += pushdata_bytes
    # 输出块
    return [
        bytes([min(bytes_to_exec_data[pos], 31)]) + code[pos: pos+31]
        for pos in range(0, len(code), 31)
    ]

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
        pos = HEADER_STORAGE_OFFSET + storage_key
    else:
        pos = MAIN_STORAGE_OFFSET + storage_key
    return get_tree_key(
        address,
        pos // VERKLE_NODE_WIDTH,
        pos % VERKLE_NODE_WIDTH
    )