# Cesr blogpost draft

### Links
- https://medium.com/happy-blockchains/cesr-one-of-sam-smiths-inventions-is-as-controversial-as-genius-d757f36b88f8
- https://medium.com/happy-blockchains/cesr-proof-signatures-are-the-segwit-of-authentic-data-in-keri-e891c83e070a
- https://hackmd.io/UQaEI0w8Thy_xRF7oYX03Q?view
- https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#section-3.3.2
## Aim
- Process Cesrox documentation into less formal way.
- Provide basic concrete examples of things mentioned in there, that can be followed by hand.
- Find diffrence between actual cesrox encoding (in keriox) and new encoding, and why new is better.

## Plan
1. Introduce domains
2. What is Composability and why it's important
3. What is 24 bits boundary and why it's important
1. How it is related to composability
2. Possible solutions to obey 24 bits boudary
- pre-conv (naive base64 as example)
- post conv (why it's better than pre conv and examples)
4. Example with longer values, for example public key

## Introduction

Cesr provides encoding that joins type, size and value in the compact way that is "self framing". This means that no additional delimiting characters are needed to know where primitive ends. Thanks to that, primitives can be concatenated freely and the resulting stream can be parsed into individual primitives back an forward. What's more, primitives can be represented as text and as bytes, and concatenation in one domain can be "undone" in the second one. This property is called _text-binary concatenation composability_, or shorter **_composability_**.
Joining the two domains and composability enables text redability and bytes compactness in one protocol.

## Representations
Let's introduce domains used by cesr briefly. More details can be found in cesr documentation.
There're basicly three ways of representing cesr primitive: as bytes (B domain), as text (T domain) and as tuple of text code and value bytes (R domain). Cesr provides transformations between each of those domains, denoted as `T(B)`,`T(R)`, `B(T)`, `B(R)`, `R(B)` , `R(T)`.


To fulfill cesr assumptions, composability property mentioned earlier needs to apply to transformations between `T` and `B` (in bouth sides). Raw domain is "easy to think about" and cesr provides transformations from it to either text or bytes. We will deal with all of those transformations later in this post.

## Ok, so what is composability and why to care?

So again, composability is a property of transformation between domains that allows us to use collection of elements from one domain, convert them(all at once) to the second domain, and be able to split them into separate elements in the second domain. Each of splitted element can be then transformed (separatly) into orginal element from first domain.

Let's look at base64 encoding examples to check if this is text-binary concatenation composable.

### Example 1
Lets start with text domain. Get two elements and convert it to bytes. According to [designations from cesr documentation](https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#name-concatenation-composability), we have base 64 encode as `T` transform and base64 decode ad `B` transform, and `t[0] = "AQ"`, `t[1] = "Aw"`, `b[0] = [1]`, `b[1] = [3]`.

Let's decode base64 texts to bytes.


Now let's encode concatenation of those text representations:

As we can see, result bytes aren't the same as concatenation of byte representations of elements. So this transform doesn't meet composability constraints. We can't decompose `[1, 0, 48]` into `[1]` and `[3]`.

### Example 2
Now let's start with bytes domain and encode two elements from bytes domain - `[1]` and `[3]` to text domain with base64 algorithm. So we have `b[0] = [1]`, `b[1] = [3]`, `t[0] = "AQ=="`, `t[1] = "Aw=="`.


We can transform elements back and forth again, and we got the same result.


Now let's transform concatenated text representation to binary and back to text.


Notice that after B-> T conversion, to the end of texts padding characters (=) are added. Thanks to that, we're albe to decompose `[1, 3]` int `[1]` and `[3]`, and composability works for `B` transform.

After transforming concatenation to text again, we are not able to decompose text into separate elements in text domain. It means, that copomosability doesn't apply for `T` conversion, so base64 doesn't satisfy composability.

### Example 3
Let's try to do the same for other input data: `[1, 2, 3]` and `[4, 5, 6]`.

Now, let's transform concatenated text representation to binary, and to text again:

After transforming concatenation through bytes to text again, we got the same result.

### Conclusion
So there exists special cases when composability works for base64 transform. The difrences in those examples arise from input data lengths. In the first example, input data was 2 base64 characters length, so 12 bites. In the second one, input was 1 byte length, so they have 8 bites. In the third one, input data was 3 bytes length, so 24 bites.

For more details check [documentation](https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#name-conversions)

## 24 bits boundary

Base64 encodes 3 bytes into 4 characters. If the algorithm get data which length is shorter than 3 bytes, it complements missing bytes with zeros to have lenght dividable by 6 bits (length of base64 character), and then if outpus string is to short, it appends padding characters to it, to have text length dividable by 4. This padding step makes transformation from bytes to text composable, like in example 2.
If on input we have data that doesn't need any compliments, like in third example, composability works also for `T -> B` transformation. And it doesn't need compliments, if input data has 24 bits length - is an integer multiple of four Base64 characters in text domain (24 bits) or is an integer multiple of three bytes in binary domain (24 bits).
So if we modify a little standard base64 algorithm, we are able to achive composability in both, text and binary domains.

There are at least two ways to make conversions satisfy 24 bits boundary. Complement input data before base64 conversion or after. We'll call those conversions pre-pad and post-pad respectivly. Detailed description can be found in [this chapter](https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#name-code-characters-and-lead-by). We will limit here to an example of conversion one byte value with bouth ways.
On the left hand side there's example of pre-pad conversion, and on the right hand side - basic base64 encoding which uses post-pad conversion.


**Note**: In some cases, text that we get from pre pad conversion is readable for humans. It works for small numbers, their base64 representations are readable. We can compute it quite easly basing on base64 character and it's position:
`"AAD/" -> 0 * 64^3 + 0 * 64^2 + 3*64 + 63 -> 255`
It's not so easy for post-pad converted text.

For CESR the pre-pad conversion was choosen, due to better readability.

## Codes

When we convert value from bytes, to text representation with pre-pad conversion, some prepended bytes are converted to characters that don't inlcude any bits of informations of orginal data. For example, two first characters of `AAD/` from above example. The length of this unused part of primitive depends on the length of encoded value and is discussed in details in [this section](https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#name-text-code-size). Thus we can use them to encode addtional informations.
From the CESR point of view it's important to encoded string/bytes to be self framing. Thanks to that, we can have parsers, that cut proper part of the stream, and decode it later. We will use this unused part of encoded primitive, to code this lengths and also add context to them. And that's what codes will do.

**TODO** about codes and lengths that they provides

Let's look at the [examples](https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#section-3.3.2) closly and encode with CESR two bytes value step by step. According to [master code table](https://weboftrust.github.io/ietf-cesr/draft-ssmith-cesr.html#name-appendix-master-code-table) code `M` encodes short value of length 16 bits. Let's encode `[255, 255]` "by hand". In raw domain representation it will be tuple (`M`, `[255, 255]`) (or (`M`, `ffff`) using hex representation).


**TODO** Example of parsing from text and from binary?
**TODO** What if code is longer than one?