Skip to content

Instantly share code, notes, and snippets.

@justmoon

justmoon/NOTES.md

Last active August 24, 2016 12:20
Show Gist options
  • Save justmoon/f2e34233d49051e1e1014f8cc598b74f to your computer and use it in GitHub Desktop.
Save justmoon/f2e34233d49051e1e1014f8cc598b74f to your computer and use it in GitHub Desktop.
Download ZIP
Notes on ILP binary format
Raw
NOTES.md

Introduction

Here is a quick doc to explain our current thinking about the binary format.

Syntax descriptions are ASN.1 (X.680), all encodings are representations according to Octet Encoding Rules (OER; X.696).

First, let's define some basic types.

GenericTypes

GenericTypes
DEFINITIONS
AUTOMATIC TAGS ::=
BEGIN

-- Small Integers
Int8 ::= INTEGER (-128..127)
UInt8 ::= INTEGER (0..255)

Int16 ::= INTEGER (-32768..32767)
UInt16 ::= INTEGER (0..65535)

Int32 ::= INTEGER (-2147483648..2147483647)
UInt32 ::= INTEGER (0..4294967295)

Int64 ::= INTEGER (-9223372036854775808..9223372036854775807)
UInt64 ::= INTEGER (0..18446744073709551615)

-- Large (Cryptographic) Integers
UInt128 ::= OCTET STRING (SIZE(16))
UInt160 ::= OCTET STRING (SIZE(20))
UInt192 ::= OCTET STRING (SIZE(24))
UInt224 ::= OCTET STRING (SIZE(28))
UInt256 ::= OCTET STRING (SIZE(32))
UInt384 ::= OCTET STRING (SIZE(48))
UInt512 ::= OCTET STRING (SIZE(64))

-- Variable-Length Integers
VarInt ::= INTEGER
VarUInt ::= INTEGER (0..MAX)

-- Variable-Length Data
VarBytes ::= OCTET STRING

END

Most of these are encoded in OER as you would expect. A Uint16 for instance is encoded as two bytes in big-endian order.

Variable-length values (Var*) are encoded using a length-prefix defined in the OER standard. A short, readable explanation can be found here.

InterledgerTypes

Next, let's define some Interledger-specific types.

InterledgerTypes
DEFINITIONS
AUTOMATIC TAGS ::=
BEGIN

IMPORTS
	Int8,
	VarUInt
	FROM GenericTypes
;

-- Readable names for special characters that may appear in ILP addresses
hyphen IA5String ::= "-"
period IA5String ::= "."
underscore IA5String ::= "_"
tilde IA5String ::= "~"

-- A standard interledger address
Address ::= IA5String
	(FROM
		( hyphen
		| period
		| "0".."9"
		| "A".."Z"
		| underscore
		| "a".."z"
		| tilde )
	)

-- --------------------------------------------------------------------------

-- Amounts are provided as base-10 floating point
Amount ::= SEQUENCE {
	exponent Int8,
	mantissa VarUInt
}

-- --------------------------------------------------------------------------

-- GeneralizedTime is a standard ASN.1 time format based on ISO 8601. It was
-- tempting to use the Unix epoch, however unfortunately, standard POSIX
-- time is discontinuous. If we used POSIX time for expiries for example, a
-- transfer might expire and then un-expire when a leap second occurs. Since
-- Interledger protocols depend on causality, we cannot use POSIX time and
-- since we do not wish to create our own time standard, we end up using ISO
-- 8601.
Timestamp ::= GeneralizedTime

END

The Address definition is just a very long-winded way to restrict the character set in pure ASN.1. An Interledger address looks like this:

ilpdemo.red.alice

But we recommend it should always be printed with a prefix of ilp:, e.g. ilp:ilpdemo.red.alice. This allows us to distinguish ILP addresses from domains and countless other period-delimited identifiers. Please keep in mind that despite appearances, ILP addresses are a much closer analog to IP addresses than domain names. They are designed to assist the routing algorithm, but they are not meant to be particularly short, or human-readable. That said, being able to dissect ILP addresses visually without a WHOIS tool will help ILP operators debug problems faster.

InterledgerProtocolHeader

Finally, we're ready to tackle the heart of the Interledger Protocol: The ILP header. This header specifies the destination and amount of a payment and enables us to route and forward it closer to the destination.

InterledgerProtocolHeader
DEFINITIONS
AUTOMATIC TAGS ::=
BEGIN

IMPORTS
	Address,
	Amount
	FROM InterledgerTypes
;

InterledgerProtocolHeader ::= SEQUENCE {
	-- Destination ILP Address
	destinationAccount Address,
	-- Amount which must be received at the destination
	destinationAmount Amount,
	-- Enable ASN.1 Extensibility
	...
}

END

The destination ILP address and the amount together specify the desired outcome that we are asking the connector to help us achieve. Note that the currency is implied - each account is associated with a ledger and each ledger is associated with a currency or other asset type.

Higher-level protocols might inform the sender about the currency code/symbol of the recipient, but for the purposes of the Interledger layer, we do not need to know which currency it is.

The ... indicates that we would like to enable ASN.1's extensibility feature. We will see later what effect this has on the actual binary output.

Here is an example ILP header:

00 11 69 6C 70 64 65 6D 6F 2E 72 65 64 2E 61 6C
69 63 65 00 01 0A

Let's break it down:

00                                  # extensibility byte
11                                  # destinationAccount length (17 characters)
   69 6C 70 64 65 6D 6F 2E          # destinationAccount (as ASCII)
   72 65 64 2E 61 6C 69 63          #   lit. "ilpdemo.red.alice"
   65
00                                  # amount exponent (0)
01                                  # amount mantissa length (1 byte)
   0A                               # amount mantissa (10)

Amounts are always provided as base-10 floating point numbers. This example uses an exponent of zero and a mantissa of 10. (In case of dollars this could be $10.)

The destinationAccount is given as a length-prefixed ASCII string. The length prefix is itself variable-length as defined in OER. It is encoded as a single byte in this case since the length is less than 128. However, the encoding can express lengths up to 2^1017 which is hundreds of orders of magnitude greater than the available memory on Earth. More information about the length determinant is available here or in section 8.6 of X.696.

The character set of ILP addresses is limited to alphanumeric characters (a-zA-Z0-9), hyphen (-), underscore (_), tilde (~) and period (.). The period character has special meaning by convention as the primary address delimiter.

Finally, the first byte in the header is the extensibility byte. It allows extensibility in two ways: optional fields and ASN.1 extensibility.

We can add up to seven optional sections in the header (lower seven bits). Older implementations will ignore the additional sections and we can enforce this though appropriate test vectors.

In addition, if the highest bit is set, compliant implementations will look for a separate extensibility bitmask of variable size which allows further extensibility if needed.

Note that we don't expect to ever have to use the extensibility feature due to the ability to additional headers which we will discuss in the next section.

InterledgerProtocolPacket

Interledger headers are not transmitted by themselves. Instead they are encapsulated in a Interledger Packet. The Interledger Packet can contain an infinite number of headers, though we will likely recommend a limit for the overall size of the packet, which ledgers would enforce.

InterledgerProtocolPacket
DEFINITIONS
AUTOMATIC TAGS ::=
BEGIN

IMPORTS
	UInt16,
	VarBytes
	FROM GenericTypes

	InterledgerProtocolHeader
	FROM InterledgerProtocolHeader

	SourceRoutingHeader
	FROM SourceRoutingHeader

	UserDataHeader
	FROM UserDataHeader

	CustomHeader
	FROM CustomHeader
;

HEADER ::= CLASS
	{
	&typeId UInt16,
	&Type
	}
	WITH SYNTAX {&typeId &Type}

HeaderSet HEADER ::=
	{
	{1 InterledgerProtocolHeader} |
	{128 UserDataHeader} |
	{144 SourceRoutingHeader} |
	{16383 CustomHeader} |
	{32767 CustomHeader} |
	{49151 CustomHeader} |
	{65535 CustomHeader}
	}

InterledgerPacket ::= SEQUENCE {
	header Header
}

Header ::= SEQUENCE {
	headerType HEADER.&typeId ({HeaderSet}),
	header HEADER.&Type ({HeaderSet}{@headerType}),
	ext SEQUENCE {
		nextHeader Header OPTIONAL
	}
}

END

This schema uses some advanced ASN.1 syntax to implement the header type, so we will use an example to break it down.

00 01                               # header type (1 = InterledgerProtocolHeader)
16                                  # header length (22 bytes)
   00 11 69 6C 70 64 65 6D          # header data
   6F 2E 72 65 64 2E 61 6C
   69 63 65 00 01 0A
00                                  # continue byte - 0x00 means this was the
                                    #   last header

We immediately see that this packet contains a header of type 1, which maps to the InterledgerProtocolHeader we discussed in the previous section. Next, we learn the header length - in this case 22 bytes. Next, the actual header data is provided. The example data here comes from the example from the previous section.

Finally, we see a single zero byte. This means that no further headers follow. The other possible value for this byte is 0x80, which means another header follows.

Let's see what that looks like:

00 01                               # header type (1 = InterledgerProtocolHeader)
16                                  # header length (22 bytes)
   00 11 69 6C 70 64 65 6D          # header data
   6F 2E 72 65 64 2E 61 6C
   69 63 65 00 01 0A
80                                  # continue byte - 0x80 means keep going
FF FF                               # header type (65535 = CustomHeader)
2F                                  # header length (48 bytes)
   25 68 74 74 70 73 3A 2F          # header data
   2F 72 69 70 70 6C 65 2E
   63 6F 6D 2F 70 72 6F 74
   6F 63 6F 6C 73 2F 72 70
   73 70 2F 31 2E 30 08 01
   23 45 67 89 AB CD EF
00                                  # continue byte - end of packet

We can see that outer envelope of the new header follows the previous one, but we don't know what this header means yet, because we haven't encountered its type id before (0xFFFF = 65535).

When an Interledger implementation encounters an unknown header type, it must act according to the value of the two most significant bits:

Bits Meaning
00 Drop the payment, reply with an error, issue a refund if possible
01 Drop the payment, reply with an error, do not issue a refund
10 Drop the payment quietly, do not reply
11 Ignore the header, process the payment as if the header wasn't there

In this case the first two bits are 11, which means we could safely ignore this unknown header.

But let's find out what a type 65535 header is in the next section.

CustomHeader

CustomHeader is a special header type which allows vendor-specific extensibility. Here is the format:

CustomHeader
DEFINITIONS
AUTOMATIC TAGS ::=
BEGIN

IMPORTS
	VarBytes
	FROM GenericTypes
;

CustomHeader ::= SEQUENCE {
	typeUri UTF8String,
	value VarBytes
}

END

Once again, it's easier to understand this by example, so let's extract the example from the previous section and take a look:

25                              # typeUri length (37 character)
   68 74 74 70 73 3A 2F 2F      # typeUri (UTF8)
   72 69 70 70 6C 65 2E 63      #   lit. "https://ripple.com/protocols/rpsp/1.0"
   6F 6D 2F 70 72 6F 74 6F
   63 6F 6C 73 2F 72 70 73
   70 2F 31 2E 30
08                              # value length (8 bytes)
   01 23 45 67 89 AB CD EF      # value data

Essentially we are looking at a simple key-value encoding. The key in this case refers to the header format and is a URI to avoid collisions between different vendors. The value is the actual header encoded according to the vendor's specification.

Adding custom headers is the preferred way for third parties to extend the protocol. Official, standard headers will be assigned a type ID and added natively to the protocol.

There are two header types mentioned above which we didn't explain, UserDataHeader and SourceRoutingHeader. These formats are still in development and not yet available for review.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment