Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove point serialization method from the public verkle API #86

Open
kevaundray opened this issue Feb 17, 2024 · 0 comments
Open

Remove point serialization method from the public verkle API #86

kevaundray opened this issue Feb 17, 2024 · 0 comments

Comments

@kevaundray
Copy link
Contributor

TLDR

Currently, we expose two methods which are different internally, but to consumers of the verkle cryptography and even further downstream users, they serve the same purpose.

Problem

There are two ways to convert a point into 32 bytes

The cryptography library provides a Point datastructure. This has a method which allows a point to be serialized into 32 bytes. This method is exposed to the downstream verkle users. In go-ipa, this is the .Bytes method. In the rust library, this is serialize_compressed.

The Point data structure has another method which allows you to convert a Point into a Scalar/Field data structure. The Scalar/Field data structure can be serialized into 32 bytes.

So far we have two ways to go from a Point to a 32 byte array:

  • Serialize a Point into 32 bytes
  • Convert a Point into a Scalar and serialize the Scalar into 32 bytes.

Are there any important differences between these two methods?

The second one(mapToField) was initially thought to be more SNARK friendly. This has not been formally verified, though its for the most part irrelevant for this issue.

The first was thought to be more CPU friendly -- you can roughly see this because the SNARK friendly version uses an inversion which is cheap in a SNARK (number of constraints), but outside of a SNARK field inversions are not cheap.

For all intents and purposes, they provide the same functionality to downstream users.

New Abstraction

The main issue currently is that both methods are exposed in the verkle API and in some places the usage is arbitrary. Here is the new abstraction that the solution will propose:

  • Proofs will use the CPU friendly version
  • All other trie related algorithms will use the SNARK friendly version.

Since proofs are seen as an opaque slice, the usage of the SNARK friendly version can be removed from the public API.

Solution

The solution is to remove the CPU friendly version from the verkle API.

  • In go-ipa, this means that only go-ipa will ever called .Bytes on points. go-verkle and go-ethereum will use MapToScalarField and serialize the scalar to bytes if it needs a 32 byte array.

  • In rust-verkle, this means removing deprecated_serialize_commitment from the ffi_interface for downstream js and java.

    • js will need to modify pedersen_hash/get_tree_key_hash to now use map_to_scalar_field too

### Disadvantages

pedersen_hash/get_tree_key will likely become somewhat slower since we are using the SNARK friendly version which includes an inversion.

This seems like an okay tradeoff because:

  • You only need to call it once -- For the same address and tree_index get_tree_key_for_version/balance/etc can cache the result
  • It may be possible to batch the inversion similar to what already happens inside of the verkle algorithm
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant