Skip to content
This repository has been archived by the owner on Jun 6, 2024. It is now read-only.

zkvm: support short encoding for scalars and integers #483

Open
oleganza opened this issue Jul 29, 2020 · 0 comments
Open

zkvm: support short encoding for scalars and integers #483

oleganza opened this issue Jul 29, 2020 · 0 comments

Comments

@oleganza
Copy link
Contributor

oleganza commented Jul 29, 2020

Problem

Currently const instruction expects a 32-byte canonically-encoded ristretto255 Scalar. This is suboptimal when we want to store small-range parameters such as timestamps (8 bytes) and sequence numbers (<4 bytes).

Proposal

Encode scalars with top all-zero bytes trimmed. To prevent malleability, require that encoding for all scalars.

  1. When encoding a scalar in a program: encode the scalar in a 32-byte string, trim all-zero bytes from the end of the string and write it to the program,
  2. When reading a scalar, check that top byte is not zero, then pad 32-byte array with zeroes before decoding it and checking if it's canonical.

Under this encoding:

  • number 0 is encoded as an empty string,
  • 1..255 as [01]..[ff],
  • 256..65535 as [00 01]..[ff ff] and so on.

Alternative

We could introduce a separate type "integer", that has fixed-length 8-byte encoding. This is still not optimal for small integers, and introduces an extra type and requires additional rules of conversion to scalars, and a separate instruction to read it.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant