Ethereum KZG / EIP4844 followup

[mratsim]

Following #239, here are the missing parts to fully provide EIP4844

• public API for
  • compute_kzg_proof
  • compute_blob_kzg_proof
  • verify_kzg_proof
  • verify_blob_kzg_proof
• Batch verification via
  • verify_kzg_proof_batch
  • verify_blob_kzg_proof_batch
• End-to-end test from the EF on all those primitives
• Parallelization

Implementation note

For KZG multiproofs, the spec is

def verify_kzg_proof_batch(commitments: Sequence[KZGCommitment],
                           zs: Sequence[BLSFieldElement],
                           ys: Sequence[BLSFieldElement],
                           proofs: Sequence[KZGProof]) -> bool:
    """
    Verify multiple KZG proofs efficiently.
    """

    assert len(commitments) == len(zs) == len(ys) == len(proofs)

    # Compute a random challenge. Note that it does not have to be computed from a hash,
    # r just has to be random.
    degree_poly = int.to_bytes(FIELD_ELEMENTS_PER_BLOB, 8, ENDIANNESS)
    num_commitments = int.to_bytes(len(commitments), 8, ENDIANNESS)
    data = RANDOM_CHALLENGE_KZG_BATCH_DOMAIN + degree_poly + num_commitments

    # Append all inputs to the transcript before we hash
    for commitment, z, y, proof in zip(commitments, zs, ys, proofs):
        data += commitment \
            + int.to_bytes(z, BYTES_PER_FIELD_ELEMENT, ENDIANNESS) \
            + int.to_bytes(y, BYTES_PER_FIELD_ELEMENT, ENDIANNESS) \
            + proof

    r = hash_to_bls_field(data)
    r_powers = compute_powers(r, len(commitments))

    ...

r just needs to be data that is NOT under the control of an attacker. Hashing the proposed way is a deterministic solution to the problem, the more efficient solution is using a CSPRNG (cryptographically secure pseudo random number generator). Requires #212.

[mratsim]

Also disambiguate properly between "flat" batch openings: https://discord.com/channels/595666850260713488/694537838691352576/1104864474109841449 and KZG-verkle-tree batch opening https://discord.com/channels/595666850260713488/694537838691352576/1104887185234210817

[mratsim]

Parallelization implemented in #279