Botan 3.14.1
Crypto and TLS for C&
Botan::ZFEC Class Referencefinal

#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
Kthe number of shares needed for recovery
Nthe number of shares generated

Definition at line 356 of file zfec.cpp.

356 : m_K(K), m_N(N) {
357 if(m_K == 0 || m_N == 0 || m_K >= 256 || m_N >= 256 || m_K > N) {
358 throw Invalid_Argument("ZFEC: violated 1 <= K <= N < 256");
359 }
360
361 std::vector<uint8_t> temp_matrix(m_N * m_K);
362
363 /*
364 * quick code to build systematic matrix: invert the top
365 * K*K Vandermonde matrix, multiply right the bottom n-K rows
366 * by the inverse, and construct the identity matrix at the top.
367 */
368 create_inverted_vdm(temp_matrix.data(), m_K);
369
370 for(size_t i = m_K * m_K; i != temp_matrix.size(); ++i) {
371 temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];
372 }
373
374 /*
375 * the upper part of the encoding matrix is I
376 */
377 m_enc_matrix.resize(m_N * m_K);
378 for(size_t i = 0; i != m_K; ++i) {
379 m_enc_matrix[i * (m_K + 1)] = 1;
380 }
381
382 /*
383 * computes C = AB where A is n*K, B is K*m, C is n*m
384 */
385 for(size_t row = m_K; row != m_N; ++row) {
386 for(size_t col = 0; col != m_K; ++col) {
387 uint8_t acc = 0;
388 for(size_t i = 0; i != m_K; i++) {
389 const uint8_t row_v = temp_matrix[row * m_K + i];
390 const uint8_t row_c = temp_matrix[col + m_K * i];
391 acc ^= GF_MUL_TABLE(row_v)[row_c];
392 }
393 m_enc_matrix[row * m_K + col] = acc;
394 }
395 }
396}

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
sharesmap of share id to share contents
share_sizesize in bytes of each share
output_cbthe output callback

Definition at line 439 of file zfec.cpp.

441 {
442 /*
443 Todo:
444 If shares.size() < K:
445 signal decoding error for missing shares < K
446 emit existing shares < K
447 (ie, partial recovery if possible)
448 Assert share_size % K == 0
449 */
450
451 if(shares.size() < m_K) {
452 throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");
453 }
454
455 std::vector<uint8_t> decoding_matrix(m_K * m_K);
456 std::vector<size_t> indexes(m_K);
457 std::vector<const uint8_t*> sharesv(m_K);
458
459 auto shares_b_iter = shares.begin();
460 auto shares_e_iter = shares.rbegin();
461
462 bool missing_primary_share = false;
463
464 for(size_t i = 0; i != m_K; ++i) {
465 size_t share_id = 0;
466 const uint8_t* share_data = nullptr;
467
468 if(shares_b_iter->first == i) {
469 share_id = shares_b_iter->first;
470 share_data = shares_b_iter->second;
471 ++shares_b_iter;
472 } else {
473 // if share i not found, use the unused one closest to n
474 share_id = shares_e_iter->first;
475 share_data = shares_e_iter->second;
476 ++shares_e_iter;
477 missing_primary_share = true;
478 }
479
480 if(share_id >= m_N) {
481 throw Decoding_Error("ZFEC: invalid share id detected during decode");
482 }
483
484 /*
485 This is a systematic code (encoding matrix includes K*K identity
486 matrix), so shares less than K are copies of the input data,
487 can output_cb directly. Also we know the encoding matrix in those rows
488 contains I, so we can set the single bit directly without copying
489 the entire row
490 */
491 if(share_id < m_K) {
492 decoding_matrix[i * (m_K + 1)] = 1;
493 output_cb(share_id, share_data, share_size);
494 } else {
495 // will decode after inverting matrix
496 std::memcpy(&decoding_matrix[i * m_K], &m_enc_matrix[share_id * m_K], m_K);
497 }
498
499 sharesv[i] = share_data;
500 indexes[i] = share_id;
501 }
502
503 // If we had the original data shares then no need to perform
504 // a matrix inversion, return immediately.
505 if(!missing_primary_share) {
506 for(const size_t index : indexes) {
507 BOTAN_ASSERT_NOMSG(index < m_K);
508 }
509 return;
510 }
511
512 invert_matrix(decoding_matrix.data(), m_K);
513
514 for(size_t i = 0; i != indexes.size(); ++i) {
515 if(indexes[i] >= m_K) {
516 std::vector<uint8_t> buf(share_size);
517 linear_combination(buf.data(), sharesv.data(), &decoding_matrix[i * m_K], m_K, share_size);
518 output_cb(i, buf.data(), share_size);
519 }
520 }
521}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82

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
inputthe data to FEC
sizethe length in bytes of input
output_cbthe output callback

Definition at line 401 of file zfec.cpp.

401 {
402 if(size % m_K != 0) {
403 throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");
404 }
405
406 const size_t share_size = size / m_K;
407
408 std::vector<const uint8_t*> shares;
409 for(size_t i = 0; i != m_K; ++i) {
410 shares.push_back(input + i * share_size);
411 }
412
413 this->encode_shares(shares, share_size, output_cb);
414}
void encode_shares(const std::vector< const uint8_t * > &shares, size_t share_size, const output_cb_t &output_cb) const
Definition zfec.cpp:416

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
sharesexactly K shares of data to FEC
share_sizethe length in bytes of each share
output_cbthe output callback

Definition at line 416 of file zfec.cpp.

418 {
419 if(shares.size() != m_K) {
420 throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
421 }
422
423 // The initial shares are just the original input shares
424 for(size_t i = 0; i != m_K; ++i) {
425 output_cb(i, shares[i], share_size);
426 }
427
428 std::vector<uint8_t> fec_buf(share_size);
429
430 for(size_t i = m_K; i != m_N; ++i) {
431 linear_combination(fec_buf.data(), shares.data(), &m_enc_matrix[i * m_K], m_K, share_size);
432 output_cb(i, fec_buf.data(), fec_buf.size());
433 }
434}

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.

57{ 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 523 of file zfec.cpp.

523 {
524#if defined(BOTAN_HAS_ZFEC_GFNI)
526 return *feat;
527 }
528#endif
529
530#if defined(BOTAN_HAS_ZFEC_VPERM)
531 if(auto feat = CPUID::check(CPUID::Feature::SIMD_4X32)) {
532 return *feat;
533 }
534#endif
535
536 return "base";
537}
static std::optional< std::string > check(CPUID::Feature feat)
Definition cpuid.h:66

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.

51{ return m_K; }

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