Binary Application Record Encoding (BARE)

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

1.2. Use-cases

The goals of a concise, binary, strongly-typed, and broadly-compatible structured message encoding format support a broad number of use-cases. Examples include:¶

• Self-describing authentication tokens for web services¶
• Opaque messages for transmitting arbitrary state between unrelated internet services¶
• A representation for packets in an internet protocol¶
• A structured data format for encrypted or signed application messages¶
• A structured data format for storing data in persistent storage¶

The conciseness of a BARE-encoded message enables representing structured data under strict limitations on message length in a large variety of contexts. The simple binary format may also be easily paired with additional tools, such as plain-text encodings, compression, or cryptography algorithms, as demanded by the application's needs, without increasing the complexity of the message encoding. A BARE message has a comparable size and entropy to the underlying state it represents.¶

The BARE schema language also provides a means of describing the format of BARE messages without implementation-specific details. This encourages applications that utilize BARE to describe their state in a manner that other programmers can easily utilize for application interoperation. The conservative set of primitives offered by BARE aids in making such new implementations easy to write.¶

2.1. Primitive Types

Primitive types represent exactly one value.¶

uint

A variable-length unsigned integer encoded using the Unsigned Little Endian Base 128 (ULEB128). Every octet of the encoded value has the most-significant bit set, except for the last octet. The remaining bits are the zero-extended integer value in 7-bit groups, the least-significant group first.¶

The encoder MUST encode uint using the minimum necessary number of octets, and the decoder SHOULD raise an error if it encounters the opposite.¶

The maximum precision of such a number is 64-bits. The maximum length of an encoded uint is therefore 10 octets.¶

Numbers that require all ten octets will have 6 bits in the final octet that do not have meaning, between the least- and most-significant bits. The implementation MUST set these to zero.¶

int

A signed integer with variable-length encoding. Signed integers are represented as uint using a "zig-zag" encoding: positive values x are written as 2x + 0, negative values as -2x - 1. Another way of looking at it is that negative numbers are complemented, and whether to complement is encoded in bit 0.¶

The encoder MUST encode int using the minimum necessary number of octets, and the decoder SHOULD raise an error if it encounters the opposite.¶

The maximum precision of such a number is 64-bits. The maximum length of an encoded int is therefore 10 octets.¶

Numbers that require all ten octets will have 6 bits in the final octet that do not have meaning, between the least- and most-significant bits. The implementation MUST set these to zero.¶

u8, u16, u32, u64

Unsigned integers of a fixed precision, respectively 8, 16, 32, and 64 bits. They are encoded in little-endian (least significant octet first).¶

i8, i16, i32, i64

Signed integers of a fixed precision, respectively 8, 16, 32, and 64 bits. They are encoded in little-endian (least significant octet first), with two's complement notation.¶

f32, f64

Floating-point numbers represented with the IEEE 754 [IEEE.754.1985] binary32 and binary64 floating point number formats.¶

bool

A boolean value, either true or false, encoded as a u8 type with a value of one or zero, respectively representing true or false.¶

If a value other than one or zero is found in the u8 representation of the bool, the message is considered invalid, and the decoder SHOULD raise an error if it encounters such a value.¶

str

A string of text. The length of the text in octets is encoded first as a uint, followed by the text data represented with the UTF-8 encoding [RFC3629].¶

If the data is found to contain invalid UTF-8 sequences, it is considered invalid, and the decoder SHOULD raise an error if it encounters such a value.¶

data

Arbitrary data of a variable length. The length (in octets) is encoded first as a uint, followed by the data itself encoded literally.¶

data[length]

Arbitrary data of a fixed "length", e.g. data[16]. The length (in octets) is not encoded into the message. The data is encoded literally in the message.¶

void

A type with zero length. It is not encoded into BARE messages.¶

enum

An unsigned integer value from a set of named values agreed upon in advance, encoded with the uint type.¶

An enum whose uint value is not a member of the values agreed upon in advance is considered invalid, and the decoder SHOULD raise an error if it encounters such a value.¶

Note that this makes the enum type unsuitable for representing several enum values that have been combined with a bitwise OR operation.¶

Using uint for enum value makes it possible to encode named values with different number of octets. Constant-length enum can be achieved when all the enum values are encoded by uints with the same number of octets.¶

2.2. Aggregate Types

Aggregate types may store zero or more primitive or aggregate values.¶

optional<type>

A value of "type" that may or may not be present, e.g. optional<u32>. Represented as either a u8 with a value of zero, indicating that the optional value is unset; or a u8 with a value of one, followed by the encoded data of the optional type.¶

An optional value whose initial u8 is set to a number other than zero or one is considered invalid, and the decoder SHOULD raise an error if it encounters such a value.¶

list<type>

A variable-length list of "type" values, e.g. list<str>. The length of the list (number of values) is encoded as a uint, followed by the encoded values of each member of the list concatenated.¶

list<type>[length]

A list of "length" values of "type", e.g. list<uint>[10]. The length is not encoded into the message. The encoded values of each member of the list are concatenated to form the encoded list.¶

map<type A><type B>

A mapping of "type B" values keyed by "type A" values, e.g. map<u32><str>. The encoded representation of a map begins with the number of key/value pairs encoded as a uint, followed by the encoded key/value pairs concatenated. Each key/value pair is encoded as the encoded key concatenated with the encoded value.¶

A message with repeated keys is considered invalid, and the decoder SHOULD raise an error if it encounters such a value.¶

union

A tagged union whose value may be one of any type from a set of types agreed upon in advance. Every type in the set is assigned a numeric identifier. The value is encoded as the selected type's identifier represented with the uint encoding, followed by the encoded value of that type.¶

A union with a tag value that does not have a corresponding type assigned is considered invalid, and the decoder SHOULD raise an error if it encounters such a value.¶

struct

A set of values of arbitrary types concatenated in an order agreed upon in advance. Each value is called "field", and the field has a name and type.¶

2.3. User-Defined Types

A user-defined type gives a name to another type. This creates a distinct type whose representation is equivalent to the named type. An arbitrary number of user-defined types may be used for the same underlying type; each is distinct from the other.¶

2.4. Invariants

The following invariants are specified:¶

• Any type that is ultimately a void type (either directly or via a user-defined type) MUST NOT be used as an optional type, list value, map key, map value, or struct field type. Void types may only be used as members of the set of types in a tagged union.¶
• Enums MUST have at least one named value, and each named value of an enum MUST be unique.¶
• The lengths of fixed-length data and fixed-length list types MUST be at least one and MUST NOT be longer than 18,446,744,073,709,551,615 octets (the maximum value of a u64).¶
• Any map key type (directly or via a user-defined type) MUST be of a primitive type that is not f32, f64, data, data[length], or void.¶
• Unions MUST have at least one type, and each type of a union MUST be unique.¶
• Structs MUST have at least one field, and each field of a struct MUST have a unique name.¶
• Any user-defined type MUST be defined before used. Any user-defined type MUST NOT be defined recursively (directly or indirectly).¶

B.2. Encoded Messages

Some basic example messages in hexadecimal are provided for the schema specified in Appendix B.1.¶

A "Person" value of type "Customer" with the following values:¶

name

James Smith¶

email

jsmith@example.org¶

address

123 Main St; Philadelphia; PA; United States¶

orders (1)

orderId: 4242424242; quantity: 5¶

metadata

(unset)¶

Encoded BARE message:¶

00 0b 4a 61 6d 65 73 20 53 6d 69 74 68 12 6a 73
6d 69 74 68 40 65 78 61 6d 70 6c 65 2e 6f 72 67
0b 31 32 33 20 4d 61 69 6e 20 53 74 0c 50 68 69
6c 61 64 65 6c 70 68 69 61 02 50 41 0d 55 6e 69
74 65 64 20 53 74 61 74 65 73 01 b2 41 de fc 00
00 00 00 05 00 00 00 00

Encoded BARE message, but characters of strings are decoded:¶

00 0b  J  a  m  e  s     S  m  i  t  h 12  j  s
 m  i  t  h  @  e  x  a  m  p  l  e  .  o  r  g
0b  1  2  3     M  a  i  n     S  t 0c  P  h  i
 l  a  d  e  l  p  h  i  a 02  P  A 0d  U  n  i
 t  e  d     S  t  a  t  e  s 01 b2 41 de fc 00
00 00 00 05 00 00 00 00

A "Person" value of type "Employee" with the following values:¶

name

Tiffany Doe¶

email

tiffanyd@acme.corp¶

address

123 Main St; Philadelphia; PA; United States¶

department

ADMINISTRATION¶

hireDate

2020-06-21T21:18:05Z¶

publicKey

(unset)¶

metadata

(unset)¶

Encoded BARE message:¶

01 0b 54 69 66 66 61 6e 79 20 44 6f 65 12 74 69
66 66 61 6e 79 64 40 61 63 6d 65 2e 63 6f 72 70
0b 31 32 33 20 4d 61 69 6e 20 53 74 0c 50 68 69
6c 61 64 65 6c 70 68 69 61 02 50 41 0d 55 6e 69
74 65 64 20 53 74 61 74 65 73 01 14 32 30 32 30
2d 30 36 2d 32 31 54 32 31 3a 31 38 3a 30 35 5a
00 00

Encoded BARE message, but characters of strings are decoded:¶

01 0b  T  i  f  f  a  n  y     D  o  e 12  t  i
 f  f  a  n  y  d  @  a  c  m  e  .  c  o  r  p
0b  1  2  3     M  a  i  n     S  t 0c  P  h  i
 l  a  d  e  l  p  h  i  a 02  P  A 0d  U  n  i
 t  e  d     S  t  a  t  e  s 01 14  2  0  2  0
 -  0  6  -  2  1  T  2  1  :  1  8  :  0  5  Z
00 00

A "Person" value of type "TerminatedEmployee".¶

Encoded BARE message:¶

02

C.1. Simple Hierarchical Data

Recursive data types are forbidden in BARE. The following examples show how linked list and binary tree, widely used recursive data types, can be encoded in BARE messages.¶

As BARE supports variable-length lists, encoding of linked list is straightforward.¶

type Element struct {
  str: what
}

type LinkedList list<Element>

A binary tree can be encoded to BARE's variable-length list with 2x + 1 and 2x + 2 indexing.¶

type Node optional<struct {
  str: what
}>

type BinaryTree list<Node>

C.2. JSON Schema

Sometimes it is needed to deal with generic format of data. When the use-case for recursive types is encountered, each element to encode needs to be identified.¶

type ElementId uint

type False void
type True void
type Null void

type Object map<str><ElementId>
type Array list<ElementId>

type Element union {
  | False
  | True
  | Null
  | f64
  | str
  | Object
  | Array
}

type JSONDocument list<Element>

C.3. Graph

It is not possible to encode pointers in BARE. However, an arbitrary graph can be encoded in the lists of nodes and connections.¶

type NodeId uint

type Node struct {
  what: str
}

type Connection struct {
  from: NodeId
  to: NodeId
  why: str
}

type Graph struct {
  nodes: map<NodeId><Node>
  edges: list<Connection>
}