Copyright | (c) Leo D 2023 |
---|---|
License | BSD-3-Clause |
Maintainer | leo@apotheca.io |
Stability | experimental |
Portability | POSIX |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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.
Synopsis
- type ZFECShare = (Int, ByteString)
- zfecEncode :: Int -> Int -> ByteString -> IO [ZFECShare]
- zfecDecode :: Int -> Int -> [ZFECShare] -> IO ByteString
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) Source #
is more raw
.
:: 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
:: 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