ARC-0045: a dedicated Bytes type for snarkVM

[ljedrz]

Introduction

In order to be able to support objects like proofs and hashes in programs, we first need to have the plumbing necessary to represent them. The purpose of this ARC is to introduce a new snarkVM type that can facilitate this.

Goals

• the ability to contain sequences of arbitrary bytes of different lengths
• a convenient representation for objects like hashes

Considerations

1. Preexisting types

• String - its set of features (support for a wide range of Unicode characters, UTF-8 validation) is much greater, making it inherently less efficient than what is needed to just encode arbitrary bytes
• Array - its representation in programs is suitable to contain relatively small numbers of entries, but using it for objects like proofs would make it bloated and unreadable; it is also not ergonomic for handling hashes

2. Encoded size

• while the most basic way to encode bytes is hexadecimal, its efficiency is only 50%, meaning it results in double the number of input bytes when encoded; this would make it more costly to use in programs, especially considering potential large inputs
• on the other hand, more efficient encodings could potentially be confusing when used with e.g. hashes
• since the encoding doesn't affect the internal representation, different kinds could be supported depending on the use case; this would require e.g. a prefix or suffix that would indicate the type of encoding used

3. Overall capacity

• the Literal "supertype" has an upper size limit of u16::MAX (65535) bytes, meaning the same would apply to the newly proposed type
• the encoded size is the one where this limit would apply, meaning that e.g. with the hex encoding, the maximum number of raw bytes would be 32767, and with base64 it would be ~43689
• larger sets of bytes would need to be chunked and packed into e.g. a struct

4. Internal representation

• the initial draft PR uses a plain Vec<u8> internally, which has several benefits:
  • relatively simple to implement and easy to maintain
  • support for different numbers of bytes without padding or terminators
  • compatible with various use cases, potentially with no need for any conversion
  • very efficient to read and write
• a different representation could be considered if additional functionalities are desirable

5. The circuit-side counterpart

• all console types have a circuit equivalent, and while the initial implementation can target just the console for easier discussion and reviewing, a follow-up circuit-side implementation needs to be kept in mind
• while the internal representation can be different, the set of features should not diverge

References

• a snarkVM draft PR containing an initial console-side implementation
• an ARC related to hash portability