---
# System prepended metadata

title: Kerl Encoding Options
tags: [discussion]

---

---
title: Kerl Encoding Options
tags: discussion
---

# Kerl Encoding Options

There are essentially three different options how to encode (ternary) data consisting of one or more Kerl hashes:

1. Convert the entire input using the t5b1 encoding.
1. Remove each 243rd trit from the input (always zero) and then convert the result using the t5b1 encoding.
1. Convert each 243-trit hash segment of the input to 48-bytes by applying the `convertToBytes` step as described in the [Kerl spec](https://github.com/iotaledger/kerl/blob/master/IOTA-Kerl-spec.md#trits---bytes-encoding).

### First option
The first encoding is the most straightforward, but it also results in the largest signatures with ⌈n · 27 · 243 / 5⌉ bytes for n hashes. This encoding is malleable since each 243rd trit will be ignored. In order to prevent this malleability, the node implementations must verify that
- each 243rd trit is always 0 and 
- that the correct zero-padding has been applied to the end to reach a multiple of 5.
These checks complicate the decoding, but are necessary, especially, since an incorrect validation could result in a security issue.

#### Pros
- Easiest to implement; all building blocks are already available in the libraries

#### Cons
- Least efficient encoding
- It includes a lot of redundant zeros that must be checked to prevent malleability

## Second option
The second encoding is very similar to the first, but the signatures are shorter with ⌈n · 27 · 242 / 5⌉ bytes for n hashes. It also simplifies the validation, as the 243rd trit will always be zero by definition. However, the zero-padding still needs to be verified. Furthermore, the encoding/decoding is complicated as the 243rd trits needs to be added or removed, respectively, in a separate step. 

#### Pros
- Easy to implement
- Significantly shorter than option one
- Less malleability options than one 

#### Cons
- More complicated to implement that option one as it includes one additional step in which the entire input needs to be copied to add/remove the zeroes.
- Slower than option one
- No space benefit compared to option one for a single hash.

## Third option
The third option is the most compact and probably the most performant encoding. It results in n · 27 · 48 bytes. To prevent malleability, the validation must include a check, whether the last trit in each 48-byte segment is not set, i.e. whether the corresponding signed 384-bit integer is in <big>[</big>-⌊3<sup>242</sup> / 2⌋, ⌊3<sup>242</sup> / 2⌋<big>]</big>. After this validation check, the segments could then be directly absorbed by Keccak-384 instead of requiring an additional ternary-binary conversion. Also, the encoded 48-byte segments can be computed directly from the Keccak-384 hash by adding or subtracting, respectively, 3<sup>242</sup> from its 48 bytes without any ternary conversion.

#### Pros
- Most compact encoding possible. (Saves about 50 bytes for sec=3 and a few hundred bytes for long multisig.)
- Even a single hash can be encoded in 48 bytes! This would even benefit the Bech32 address encoding as it would allow for longer hrp like `iota`.
- When correctly implemented, the most performant encoding 

#### Cons
- Requires many changes to existing Kerl implementations
- The validity check includes big integer arithmetic.
- Most complicated option.

