Botan.Low.ZFEC

Forward error correction takes an input and creates multiple “shares”, such that any K of N shares is sufficient to recover the entire original input.

Forward Error Correction

The ZFEC module provides forward error correction compatible with the zfec library.

Note

Specific to the ZFEC format, the first K generated shares are identical to the original input data, followed by N-K shares of error correcting code. This is very different from threshold secret sharing, where having fewer than K shares gives no information about the original input.

Warning

If a corrupted share is provided to the decoding algorithm, the resulting decoding will be invalid. It is recommended to protect shares using a technique such as a MAC or public key signature, if corruption is likely in your application.

Forward error correction takes an input and creates multiple “shares”, such that any K of N shares is sufficient to recover the entire original input.

First, we choose a K value appropriate to our message - the higher K is, the smaller (but more numerous) the resulting shares will be:

k = 7
message = "The length of this message must be divisible by K"

NOTE: ZFEC requires that the input length be exactly divisible by K; if

needed define a padding scheme to pad your input to the necessary size.

We can calculate N = K + R, where R is the number of redundant shares, meaning we can tolerate the loss of up to R shares and still recover the original message.

We want 2 additional shares of redundancy, so we set R and N appropriately:

r = 2
n = k + r -- 7 + 2 = 9

Then, we encode the message into N shares:

shares <- zfecEncode k n message
length shares
-- 9

Then, we can recover the message from any K of N shares:

someShares <- take k <$> shuffle shares
recoveredMessage <- zfecDecode k n someShares
message == recoveredMessage
-- True

ZFEC

type ZFECShare = (Int, ByteString)

is more raw.

zfecEncode

Arguments

:: Int

K: the number of shares needed for recovery

-> Int

N: the number of shares generated

-> ByteString

input: the data to FEC

-> IO [ZFECShare]

Encode some bytes with certain ZFEC parameters.

NOTE: The length in bytes of input must be a multiple of K

zfecDecode

Arguments

:: Int

K: the number of shares needed for recovery

-> Int

N: the total number of shares

-> [ZFECShare]

inputs: K previously encoded shares to decode

-> IO ByteString

outputs: An out parameter pointing to a fully allocated array of size [N][size / K]. For all n in range, an encoded block will be written to the memory starting at outputs[n][0].

Decode some previously encoded shares using certain ZFEC parameters.

NOTE: There must be at least K shares of equal length