Botan 2.19.1
Crypto and TLS for C&
Public Types | Public Member Functions | List of all members
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, output_cb_t output_cb) const
 
void encode (const uint8_t input[], size_t size, output_cb_t output_cb) const
 
void encode_shares (const std::vector< const uint8_t * > &shares, size_t share_size, 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 33 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 405 of file zfec.cpp.

405 :
406 m_K(K), m_N(N), m_enc_matrix(N * K)
407 {
408 if(m_K == 0 || m_N == 0 || m_K > 256 || m_N > 256 || m_K > N)
409 throw Invalid_Argument("ZFEC: violated 1 <= K <= N <= 256");
410
411 std::vector<uint8_t> temp_matrix(m_N * m_K);
412
413 /*
414 * quick code to build systematic matrix: invert the top
415 * K*K Vandermonde matrix, multiply right the bottom n-K rows
416 * by the inverse, and construct the identity matrix at the top.
417 */
418 create_inverted_vdm(&temp_matrix[0], m_K);
419
420 for(size_t i = m_K*m_K; i != temp_matrix.size(); ++i)
421 temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];
422
423 /*
424 * the upper part of the encoding matrix is I
425 */
426 for(size_t i = 0; i != m_K; ++i)
427 m_enc_matrix[i*(m_K+1)] = 1;
428
429 /*
430 * computes C = AB where A is n*K, B is K*m, C is n*m
431 */
432 for(size_t row = m_K; row != m_N; ++row)
433 {
434 for(size_t col = 0; col != m_K; ++col)
435 {
436 uint8_t acc = 0;
437 for(size_t i = 0; i != m_K; i++)
438 {
439 const uint8_t row_v = temp_matrix[row * m_K + i];
440 const uint8_t row_c = temp_matrix[col + m_K * i];
441 acc ^= GF_MUL_TABLE(row_v)[row_c];
442 }
443 m_enc_matrix[row * m_K + col] = acc;
444 }
445 }
446 }

Member Function Documentation

◆ decode_shares()

void Botan::ZFEC::decode_shares ( const std::map< size_t, const uint8_t * > &  shares,
size_t  share_size,
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 500 of file zfec.cpp.

504 {
505 /*
506 Todo:
507 If shares.size() < K:
508 signal decoding error for missing shares < K
509 emit existing shares < K
510 (ie, partial recovery if possible)
511 Assert share_size % K == 0
512 */
513
514 if(shares.size() < m_K)
515 throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");
516
517 std::vector<uint8_t> decoding_matrix(m_K * m_K);
518 std::vector<size_t> indexes(m_K);
519 std::vector<const uint8_t*> sharesv(m_K);
520
521 auto shares_b_iter = shares.begin();
522 auto shares_e_iter = shares.rbegin();
523
524 bool missing_primary_share = false;
525
526 for(size_t i = 0; i != m_K; ++i)
527 {
528 size_t share_id = 0;
529 const uint8_t* share_data = nullptr;
530
531 if(shares_b_iter->first == i)
532 {
533 share_id = shares_b_iter->first;
534 share_data = shares_b_iter->second;
535 ++shares_b_iter;
536 }
537 else
538 {
539 // if share i not found, use the unused one closest to n
540 share_id = shares_e_iter->first;
541 share_data = shares_e_iter->second;
542 ++shares_e_iter;
543 missing_primary_share = true;
544 }
545
546 if(share_id >= m_N)
547 throw Decoding_Error("ZFEC: invalid share id detected during decode");
548
549 /*
550 This is a systematic code (encoding matrix includes K*K identity
551 matrix), so shares less than K are copies of the input data,
552 can output_cb directly. Also we know the encoding matrix in those rows
553 contains I, so we can set the single bit directly without copying
554 the entire row
555 */
556 if(share_id < m_K)
557 {
558 decoding_matrix[i*(m_K+1)] = 1;
559 output_cb(share_id, share_data, share_size);
560 }
561 else // will decode after inverting matrix
562 {
563 std::memcpy(&decoding_matrix[i*m_K], &m_enc_matrix[share_id*m_K], m_K);
564 }
565
566 sharesv[i] = share_data;
567 indexes[i] = share_id;
568 }
569
570 // If we had the original data shares then no need to perform
571 // a matrix inversion, return immediately.
572 if(!missing_primary_share)
573 {
574 for(size_t i = 0; i != indexes.size(); ++i)
575 {
576 BOTAN_ASSERT_NOMSG(indexes[i] < m_K);
577 }
578 return;
579 }
580
581 invert_matrix(&decoding_matrix[0], m_K);
582
583 for(size_t i = 0; i != indexes.size(); ++i)
584 {
585 if(indexes[i] >= m_K)
586 {
587 std::vector<uint8_t> buf(share_size);
588 for(size_t col = 0; col != m_K; ++col)
589 {
590 addmul(&buf[0], sharesv[col], decoding_matrix[i*m_K + col], share_size);
591 }
592 output_cb(i, &buf[0], share_size);
593 }
594 }
595 }
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68

References BOTAN_ASSERT_NOMSG.

◆ encode()

void Botan::ZFEC::encode ( const uint8_t  input[],
size_t  size,
output_cb_t  output_cb 
) const
Parameters
inputthe data to FEC
sizethe length in bytes of input
output_cbthe output callback

Definition at line 451 of file zfec.cpp.

455 {
456 if(size % m_K != 0)
457 throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");
458
459 const size_t share_size = size / m_K;
460
461 std::vector<const uint8_t*> shares;
462 for(size_t i = 0; i != m_K; ++i)
463 shares.push_back(input + i*share_size);
464
465 this->encode_shares(shares, share_size, output_cb);
466 }
void encode_shares(const std::vector< const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
Definition: zfec.cpp:468

References encode_shares().

◆ encode_shares()

void Botan::ZFEC::encode_shares ( const std::vector< const uint8_t * > &  shares,
size_t  share_size,
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 468 of file zfec.cpp.

473 {
474 if(shares.size() != m_K)
475 throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
476
477 // The initial shares are just the original input shares
478 for(size_t i = 0; i != m_K; ++i)
479 output_cb(i, shares[i], share_size);
480
481 std::vector<uint8_t> fec_buf(share_size);
482
483 for(size_t i = m_K; i != m_N; ++i)
484 {
485 clear_mem(fec_buf.data(), fec_buf.size());
486
487 for(size_t j = 0; j != m_K; ++j)
488 {
489 addmul(&fec_buf[0], shares[j],
490 m_enc_matrix[i*m_K+j], share_size);
491 }
492
493 output_cb(i, &fec_buf[0], fec_buf.size());
494 }
495 }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115

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 597 of file zfec.cpp.

598 {
599#if defined(BOTAN_HAS_ZFEC_VPERM)
600 if(CPUID::has_vperm())
601 {
602 return "vperm";
603 }
604#endif
605
606#if defined(BOTAN_HAS_ZFEC_SSE2)
607 if(CPUID::has_sse2())
608 {
609 return "sse2";
610 }
611#endif
612
613 return "base";
614 }
static bool has_vperm()
Definition: cpuid.h:362

References Botan::CPUID::has_vperm().

◆ recovery_threshold()

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

Definition at line 42 of file zfec.h.

42{ return m_K; }

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