Botan::ZFEC Class Reference

#include <zfec.h>

Public Types
typedef std::function< void(size_t, const uint8_t[], size_t)>	output_cb_t

Public Member Functions
void	decode_shares (const std::map< size_t, const uint8_t * > &shares, size_t share_size, const output_cb_t &output_cb) const
void	encode (const uint8_t input[], size_t size, const output_cb_t &output_cb) const
void	encode_shares (const std::vector< const uint8_t * > &shares, size_t share_size, const output_cb_t &output_cb) const
size_t	generated_shares () const
std::string	provider () const
size_t	recovery_threshold () const
	ZFEC (size_t K, size_t N)

Detailed Description

A forward error correction code compatible with the zfec library (https://github.com/tahoe-lafs/zfec)

This algorithm is not constant time and is likely susceptible to side channels. Do not use this class to encode information that should be kept secret. (If nothing else, because the first K shares are simply the original input!)

Definition at line 30 of file zfec.h.

Member Typedef Documentation

output_cb_t

typedef std::function<void(size_t, const uint8_t[], size_t)> Botan::ZFEC::output_cb_t

Callback invoked with each produced share

Receives the share index, a pointer to the share contents, and the length of the share in bytes.

Definition at line 38 of file zfec.h.

Constructor & Destructor Documentation

ZFEC()

Botan::ZFEC::ZFEC	(	size_t	K,
		size_t	N )

FEC constructor

Parameters

K	the number of shares needed for recovery
N	the number of shares generated

Definition at line 359 of file zfec.cpp.

                             : m_K(K), m_N(N), m_enc_matrix(N * K) {
   if(m_K == 0 || m_N == 0 || m_K >= 256 || m_N >= 256 || m_K > N) {
      throw Invalid_Argument("ZFEC: violated 1 <= K <= N < 256");
   }
 
   std::vector<uint8_t> temp_matrix(m_N * m_K);
 
   /*
   * quick code to build systematic matrix: invert the top
   * K*K Vandermonde matrix, multiply right the bottom n-K rows
   * by the inverse, and construct the identity matrix at the top.
   */
   create_inverted_vdm(temp_matrix.data(), m_K);
 
   for(size_t i = m_K * m_K; i != temp_matrix.size(); ++i) {
      temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];
   }
 
   /*
   * the upper part of the encoding matrix is I
   */
   for(size_t i = 0; i != m_K; ++i) {
      m_enc_matrix[i * (m_K + 1)] = 1;
   }
 
   /*
   * computes C = AB where A is n*K, B is K*m, C is n*m
   */
   for(size_t row = m_K; row != m_N; ++row) {
      for(size_t col = 0; col != m_K; ++col) {
         uint8_t acc = 0;
         for(size_t i = 0; i != m_K; i++) {
            const uint8_t row_v = temp_matrix[row * m_K + i];
            const uint8_t row_c = temp_matrix[col + m_K * i];
            acc ^= GF_MUL_TABLE(row_v)[row_c];
         }
         m_enc_matrix[row * m_K + col] = acc;
      }
   }
}

Member Function Documentation

decode_shares()

void Botan::ZFEC::decode_shares	(	const std::map< size_t, const uint8_t * > &	shares,
		size_t	share_size,
		const output_cb_t &	output_cb ) const

Recover the original data from K shares

Parameters

shares	map of share id to share contents
share_size	size in bytes of each share
output_cb	the output callback

Definition at line 441 of file zfec.cpp.

                                                             {
   /*
   Todo:
   If shares.size() < K:
   signal decoding error for missing shares < K
   emit existing shares < K
   (ie, partial recovery if possible)
   Assert share_size % K == 0
   */
 
   if(shares.size() < m_K) {
      throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");
   }
 
   std::vector<uint8_t> decoding_matrix(m_K * m_K);
   std::vector<size_t> indexes(m_K);
   std::vector<const uint8_t*> sharesv(m_K);
 
   auto shares_b_iter = shares.begin();
   auto shares_e_iter = shares.rbegin();
 
   bool missing_primary_share = false;
 
   for(size_t i = 0; i != m_K; ++i) {
      size_t share_id = 0;
      const uint8_t* share_data = nullptr;
 
      if(shares_b_iter->first == i) {
         share_id = shares_b_iter->first;
         share_data = shares_b_iter->second;
         ++shares_b_iter;
      } else {
         // if share i not found, use the unused one closest to n
         share_id = shares_e_iter->first;
         share_data = shares_e_iter->second;
         ++shares_e_iter;
         missing_primary_share = true;
      }
 
      if(share_id >= m_N) {
         throw Decoding_Error("ZFEC: invalid share id detected during decode");
      }
 
      /*
      This is a systematic code (encoding matrix includes K*K identity
      matrix), so shares less than K are copies of the input data,
      can output_cb directly. Also we know the encoding matrix in those rows
      contains I, so we can set the single bit directly without copying
      the entire row
      */
      if(share_id < m_K) {
         decoding_matrix[i * (m_K + 1)] = 1;
         output_cb(share_id, share_data, share_size);
      } else {
         // will decode after inverting matrix
         std::memcpy(&decoding_matrix[i * m_K], &m_enc_matrix[share_id * m_K], m_K);
      }
 
      sharesv[i] = share_data;
      indexes[i] = share_id;
   }
 
   // If we had the original data shares then no need to perform
   // a matrix inversion, return immediately.
   if(!missing_primary_share) {
      for(const size_t index : indexes) {
         BOTAN_ASSERT_NOMSG(index < m_K);
      }
      return;
   }
 
   invert_matrix(decoding_matrix.data(), m_K);
 
   for(size_t i = 0; i != indexes.size(); ++i) {
      if(indexes[i] >= m_K) {
         std::vector<uint8_t> buf(share_size);
         linear_combination(buf.data(), sharesv.data(), &decoding_matrix[i * m_K], m_K, share_size);
         output_cb(i, buf.data(), share_size);
      }
   }
}

References BOTAN_ASSERT_NOMSG.

Referenced by botan_zfec_decode().

encode()

void Botan::ZFEC::encode	(	const uint8_t	input[],
		size_t	size,
		const output_cb_t &	output_cb ) const

Encode the input into N shares

Parameters

input	the data to FEC
size	the length in bytes of input
output_cb	the output callback

Definition at line 403 of file zfec.cpp.

                                                                                        {
   if(size % m_K != 0) {
      throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");
   }
 
   const size_t share_size = size / m_K;
 
   std::vector<const uint8_t*> shares;
   for(size_t i = 0; i != m_K; ++i) {
      shares.push_back(input + i * share_size);
   }
 
   this->encode_shares(shares, share_size, output_cb);
}

References encode_shares().

Referenced by botan_zfec_encode().

encode_shares()

void Botan::ZFEC::encode_shares	(	const std::vector< const uint8_t * > &	shares,
		size_t	share_size,
		const output_cb_t &	output_cb ) const

Encode K existing shares into N shares

Parameters

shares	exactly K shares of data to FEC
share_size	the length in bytes of each share
output_cb	the output callback

Definition at line 418 of file zfec.cpp.

                                                             {
   if(shares.size() != m_K) {
      throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
   }
 
   // The initial shares are just the original input shares
   for(size_t i = 0; i != m_K; ++i) {
      output_cb(i, shares[i], share_size);
   }
 
   std::vector<uint8_t> fec_buf(share_size);
 
   for(size_t i = m_K; i != m_N; ++i) {
      linear_combination(fec_buf.data(), shares.data(), &m_enc_matrix[i * m_K], m_K, share_size);
      output_cb(i, fec_buf.data(), fec_buf.size());
   }
}

Referenced by encode().

generated_shares()

size_t Botan::ZFEC::generated_shares ( ) const

inline

Return how many shares are generated

Returns

the value of N

Definition at line 57 of file zfec.h.

{ return m_N; }

provider()

std::string Botan::ZFEC::provider

(

)

const

Return the name of the provider implementing this object

Returns

the provider name

Definition at line 525 of file zfec.cpp.

                               {
#if defined(BOTAN_HAS_ZFEC_GFNI)
   if(auto feat = CPUID::check(CPUID::Feature::AVX512, CPUID::Feature::GFNI)) {
      return *feat;
   }
#endif
 
#if defined(BOTAN_HAS_ZFEC_VPERM)
   if(auto feat = CPUID::check(CPUID::Feature::SIMD_4X32)) {
      return *feat;
   }
#endif
 
   return "base";
}

References Botan::CPUFeature::AVX512, Botan::CPUID::check(), Botan::CPUFeature::GFNI, and Botan::CPUFeature::SIMD_4X32.

recovery_threshold()

size_t Botan::ZFEC::recovery_threshold ( ) const

inline

Return how many shares are needed for recovery

Returns

the value of K

Definition at line 51 of file zfec.h.

{ return m_K; }

---

The documentation for this class was generated from the following files:

• src/lib/misc/zfec/zfec.h
• src/lib/misc/zfec/zfec.cpp
• src/lib/misc/zfec/zfec_vperm/zfec_vperm.cpp