Botan 3.8.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 succeptible 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

Definition at line 32 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 358 of file zfec.cpp.

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

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

Definition at line 445 of file zfec.cpp.

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

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

Definition at line 402 of file zfec.cpp.

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

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

Definition at line 417 of file zfec.cpp.

419 {
420 if(shares.size() != m_K) {
421 throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
422 }
423
424 // The initial shares are just the original input shares
425 for(size_t i = 0; i != m_K; ++i) {
426 output_cb(i, shares[i], share_size);
427 }
428
429 std::vector<uint8_t> fec_buf(share_size);
430
431 for(size_t i = m_K; i != m_N; ++i) {
432 clear_mem(fec_buf.data(), fec_buf.size());
433
434 for(size_t j = 0; j != m_K; ++j) {
435 addmul(&fec_buf[0], shares[j], m_enc_matrix[i * m_K + j], share_size);
436 }
437
438 output_cb(i, &fec_buf[0], fec_buf.size());
439 }
440}
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:123

References Botan::clear_mem().

Referenced by encode().

◆ generated_shares()

size_t Botan::ZFEC::generated_shares ( ) const
inline

Definition at line 43 of file zfec.h.

43{ return m_N; }

◆ provider()

std::string Botan::ZFEC::provider ( ) const

Definition at line 531 of file zfec.cpp.

531 {
532#if defined(BOTAN_HAS_ZFEC_VPERM)
533 if(auto feat = CPUID::check(CPUID::Feature::SIMD_4X32)) {
534 return *feat;
535 }
536#endif
537
538#if defined(BOTAN_HAS_ZFEC_SSE2)
539 if(auto feat = CPUID::check(CPUID::Feature::SSE2)) {
540 return *feat;
541 }
542#endif
543
544 return "base";
545}
static std::optional< std::string > check(CPUID::Feature feat)
Definition cpuid.h:67

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

◆ recovery_threshold()

size_t Botan::ZFEC::recovery_threshold ( ) const
inline

Definition at line 41 of file zfec.h.

41{ return m_K; }

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