Fabcoin Core  0.16.2
P2P Digital Currency
ida.cpp
Go to the documentation of this file.
1 // ida.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "config.h"
5 
6 #include "ida.h"
7 #include "stdcpp.h"
8 #include "algebra.h"
9 #include "gf2_32.h"
10 #include "polynomi.h"
11 #include "polynomi.cpp"
12 
14 const CryptoPP::GF2_32 field;
16 
18 
19 #if (defined(_MSC_VER) && (_MSC_VER < 1400)) && !defined(__MWERKS__)
20  // VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
21  typedef std::reverse_bidirectional_iterator<const byte *, const byte> RevIt;
22 #elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
23  typedef std::reverse_iterator<const byte *, std::random_access_iterator_tag, const byte> RevIt;
24 #else
25  typedef std::reverse_iterator<const byte *> RevIt;
26 #endif
27 
29 {
30  if (!parameters.GetIntValue("RecoveryThreshold", m_threshold))
31  throw InvalidArgument("RawIDA: missing RecoveryThreshold argument");
32 
34  if (m_threshold <= 0)
35  throw InvalidArgument("RawIDA: RecoveryThreshold must be greater than 0");
36 
38  m_channelsReady = 0;
42  m_inputQueues.reserve(m_threshold);
43 
44  m_outputChannelIds.clear();
46  m_outputQueues.clear();
47 
48  word32 outputChannelID;
49  if (parameters.GetValue("OutputChannelID", outputChannelID))
50  AddOutputChannel(outputChannelID);
51  else
52  {
53  int nShares = parameters.GetIntValueWithDefault("NumberOfShares", m_threshold);
54  CRYPTOPP_ASSERT(nShares > 0);
55  if (nShares <= 0) {nShares = m_threshold;}
56  for (unsigned int i=0; i< (unsigned int)(nShares); i++)
58  }
59 }
60 
61 unsigned int RawIDA::InsertInputChannel(word32 channelId)
62 {
64  {
65  if (m_lastMapPosition->first == channelId)
66  goto skipFind;
68  if (m_lastMapPosition != m_inputChannelMap.end() && m_lastMapPosition->first == channelId)
69  goto skipFind;
70  }
71  m_lastMapPosition = m_inputChannelMap.find(channelId);
72 
73 skipFind:
75  {
76  if (m_inputChannelIds.size() == size_t(m_threshold))
77  return m_threshold;
78 
79  m_lastMapPosition = m_inputChannelMap.insert(InputChannelMap::value_type(channelId, (unsigned int)m_inputChannelIds.size())).first;
80  m_inputQueues.push_back(MessageQueue());
81  m_inputChannelIds.push_back(channelId);
82 
83  if (m_inputChannelIds.size() == size_t(m_threshold))
85  }
86  return m_lastMapPosition->second;
87 }
88 
89 unsigned int RawIDA::LookupInputChannel(word32 channelId) const
90 {
91  std::map<word32, unsigned int>::const_iterator it = m_inputChannelMap.find(channelId);
92  if (it == m_inputChannelMap.end())
93  return m_threshold;
94  else
95  return it->second;
96 }
97 
98 void RawIDA::ChannelData(word32 channelId, const byte *inString, size_t length, bool messageEnd)
99 {
100  int i = InsertInputChannel(channelId);
101  if (i < m_threshold)
102  {
103  lword size = m_inputQueues[i].MaxRetrievable();
104  m_inputQueues[i].Put(inString, length);
105  if (size < 4 && size + length >= 4)
106  {
107  m_channelsReady++;
108  if (m_channelsReady == size_t(m_threshold))
110  }
111 
112  if (messageEnd)
113  {
114  m_inputQueues[i].MessageEnd();
115  if (m_inputQueues[i].NumberOfMessages() == 1)
116  {
118  if (m_channelsFinished == size_t(m_threshold))
119  {
120  m_channelsReady = 0;
121  for (i=0; i<m_threshold; i++)
124  }
125  }
126  }
127  }
128 }
129 
131 {
132  int i = LookupInputChannel(channelId);
133  return i < m_threshold ? m_inputQueues[i].MaxRetrievable() : 0;
134 }
135 
136 void RawIDA::ComputeV(unsigned int i)
137 {
138  if (i >= m_v.size())
139  {
140  m_v.resize(i+1);
141  m_outputToInput.resize(i+1);
142  }
143 
145  if (m_outputToInput[i] == size_t(m_threshold) && i * size_t(m_threshold) <= 1000*1000)
146  {
147  m_v[i].resize(m_threshold);
149  }
150 }
151 
153 {
154  m_outputChannelIds.push_back(channelId);
155  m_outputChannelIdStrings.push_back(WordToString(channelId));
156  m_outputQueues.push_back(ByteQueue());
157  if (m_inputChannelIds.size() == size_t(m_threshold))
158  ComputeV((unsigned int)m_outputChannelIds.size() - 1);
159 }
160 
162 {
163  CRYPTOPP_ASSERT(m_inputChannelIds.size() == size_t(m_threshold));
165  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
166  ComputeV(i);
167 }
168 
170 {
171  bool finished = (m_channelsFinished == size_t(m_threshold));
172  unsigned int i;
173 
174  while (finished ? m_channelsReady > 0 : m_channelsReady == size_t(m_threshold))
175  {
176  m_channelsReady = 0;
177  for (i=0; i<size_t(m_threshold); i++)
178  {
179  MessageQueue &queue = m_inputQueues[i];
180  queue.GetWord32(m_y[i]);
181 
182  if (finished)
183  m_channelsReady += queue.AnyRetrievable();
184  else
185  m_channelsReady += queue.NumberOfMessages() > 0 || queue.MaxRetrievable() >= 4;
186  }
187 
188  for (i=0; (unsigned int)i<m_outputChannelIds.size(); i++)
189  {
190  if (m_outputToInput[i] != size_t(m_threshold))
192  else if (m_v[i].size() == size_t(m_threshold))
194  else
195  {
199  }
200  }
201  }
202 
203  if (m_outputChannelIds.size() > 0 && m_outputQueues[0].AnyRetrievable())
205 
206  if (finished)
207  {
209 
210  m_channelsReady = 0;
211  m_channelsFinished = 0;
212  m_v.clear();
213 
214  std::vector<MessageQueue> inputQueues;
215  std::vector<word32> inputChannelIds;
216 
217  inputQueues.swap(m_inputQueues);
218  inputChannelIds.swap(m_inputChannelIds);
219  m_inputChannelMap.clear();
221 
222  for (i=0; i<size_t(m_threshold); i++)
223  {
224  inputQueues[i].GetNextMessage();
225  inputQueues[i].TransferAllTo(*AttachedTransformation(), WordToString(inputChannelIds[i]));
226  }
227  }
228 }
229 
231 {
232  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
234 }
235 
237 {
238  if (GetAutoSignalPropagation() != 0)
239  {
240  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
242  }
243 }
244 
245 // ****************************************************************
246 
248 {
249  m_pad = parameters.GetValueWithDefault("AddPadding", true);
250  m_ida.IsolatedInitialize(parameters);
251 }
252 
253 size_t SecretSharing::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
254 {
255  if (!blocking)
256  throw BlockingInputOnly("SecretSharing");
257 
258  SecByteBlock buf(UnsignedMin(256, length));
259  unsigned int threshold = m_ida.GetThreshold();
260  while (length > 0)
261  {
262  size_t len = STDMIN(length, buf.size());
263  m_ida.ChannelData(0xffffffff, begin, len, false);
264  for (unsigned int i=0; i<threshold-1; i++)
265  {
266  m_rng.GenerateBlock(buf, len);
267  m_ida.ChannelData(i, buf, len, false);
268  }
269  length -= len;
270  begin += len;
271  }
272 
273  if (messageEnd)
274  {
275  m_ida.SetAutoSignalPropagation(messageEnd-1);
276  if (m_pad)
277  {
279  while (m_ida.InputBuffered(0xffffffff) > 0)
281  }
282  m_ida.ChannelData(0xffffffff, NULL, 0, true);
283  for (unsigned int i=0; i<m_ida.GetThreshold()-1; i++)
284  m_ida.ChannelData(i, NULL, 0, true);
285  }
286 
287  return 0;
288 }
289 
291 {
292  m_pad = parameters.GetValueWithDefault("RemovePadding", true);
293  RawIDA::IsolatedInitialize(CombinedNameValuePairs(parameters, MakeParameters("OutputChannelID", (word32)0xffffffff)));
294 }
295 
297 {
298  if (m_pad)
300  else
301  m_outputQueues[0].TransferTo(*AttachedTransformation());
302 }
303 
305 {
306  if (m_pad)
307  {
308  PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
309  m_outputQueues[0].TransferAllTo(paddingRemover);
310  }
311 
312  if (GetAutoSignalPropagation() != 0)
314 }
315 
316 // ****************************************************************
317 
319 {
320  m_nextChannel = 0;
321  m_pad = parameters.GetValueWithDefault("AddPadding", true);
322  m_ida.IsolatedInitialize(parameters);
323 }
324 
325 size_t InformationDispersal::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
326 {
327  if (!blocking)
328  throw BlockingInputOnly("InformationDispersal");
329 
330  while (length--)
331  {
332  m_ida.ChannelData(m_nextChannel, begin, 1, false);
333  begin++;
334  m_nextChannel++;
335  if (m_nextChannel == m_ida.GetThreshold())
336  m_nextChannel = 0;
337  }
338 
339  if (messageEnd)
340  {
341  m_ida.SetAutoSignalPropagation(messageEnd-1);
342  if (m_pad)
344  for (word32 i=0; i<m_ida.GetThreshold(); i++)
345  m_ida.ChannelData(i, NULL, 0, true);
346  }
347 
348  return 0;
349 }
350 
352 {
353  m_pad = parameters.GetValueWithDefault("RemovePadding", true);
354  RawIDA::IsolatedInitialize(parameters);
355 }
356 
358 {
359  while (m_outputQueues[0].AnyRetrievable())
360  {
361  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
363  }
364 
365  if (m_pad)
366  m_queue.TransferTo(*AttachedTransformation(), m_queue.MaxRetrievable()-4*m_threshold);
367  else
368  m_queue.TransferTo(*AttachedTransformation());
369 }
370 
372 {
373  if (m_pad)
374  {
375  PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
376  m_queue.TransferAllTo(paddingRemover);
377  }
378 
379  if (GetAutoSignalPropagation() != 0)
381 }
382 
383 size_t PaddingRemover::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
384 {
385  if (!blocking)
386  throw BlockingInputOnly("PaddingRemover");
387 
388  const byte *const end = begin + length;
389 
390  if (m_possiblePadding)
391  {
392  size_t len = std::find_if(begin, end, std::bind2nd(std::not_equal_to<byte>(), byte(0))) - begin;
393  m_zeroCount += len;
394  begin += len;
395  if (begin == end)
396  return 0;
397 
399  while (m_zeroCount--)
401  AttachedTransformation()->Put(*begin++);
402  m_possiblePadding = false;
403  }
404 
405  const byte *x = std::find_if(RevIt(end), RevIt(begin), std::bind2nd(std::not_equal_to<byte>(), byte(0))).base();
406  if (x != begin && *(x-1) == 1)
407  {
408  AttachedTransformation()->Put(begin, x-begin-1);
409  m_possiblePadding = true;
410  m_zeroCount = end - x;
411  }
412  else
413  AttachedTransformation()->Put(begin, end-begin);
414 
415  if (messageEnd)
416  {
417  m_possiblePadding = false;
418  Output(0, begin, length, messageEnd, blocking);
419  }
420  return 0;
421 }
422 
An invalid argument was detected.
Definition: cryptlib.h:184
virtual bool AnyRetrievable() const
Determines whether bytes are ready for retrieval.
Definition: cryptlib.cpp:504
std::vector< MessageQueue > m_inputQueues
Definition: ida.h:56
uint8_t byte
Definition: Common.h:57
std::vector< word32 > m_outputChannelIds
Definition: ida.h:57
std::vector< word32 > m_outputToInput
Definition: ida.h:57
std::vector< word32 > m_inputChannelIds
Definition: ida.h:57
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:350
Message Queue.
Definition: mqueue.h:14
unsigned int NumberOfMessages() const
Provides the number of meesages processed by this object.
Definition: mqueue.h:48
void FlushOutputQueues()
Definition: ida.cpp:357
void resize(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:705
std::vector< SecBlock< word32 > > m_v
Definition: ida.h:62
#define NAMESPACE_BEGIN(x)
Definition: config.h:200
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:373
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:524
InputChannelMap m_inputChannelMap
Definition: ida.h:54
Library configuration file.
unsigned int InsertInputChannel(word32 channelId)
Definition: ida.cpp:61
std::string WordToString(T value, ByteOrder order=BIG_ENDIAN_ORDER)
Definition: misc.h:2241
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:647
Combines two sets of NameValuePairs.
Definition: algparam.h:135
std::vector< std::string > m_outputChannelIdStrings
Definition: ida.h:58
Classes for performing mathematics over different fields.
lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: mqueue.h:38
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
Definition: ida.cpp:290
concurrent_queue< JitTask > m_queue
Definition: SmartVM.cpp:60
virtual void OutputMessageEnds()
Definition: ida.cpp:236
void AddOutputChannel(word32 channelId)
Definition: ida.cpp:152
std::vector< ByteQueue > m_outputQueues
Definition: ida.h:59
size_t Output(int outputSite, const byte *inString, size_t length, int messageEnd, bool blocking, const std::string &channel=DEFAULT_CHANNEL)
Forward processed data on to attached transformation.
Definition: filters.cpp:127
bool MessageEnd(int propagation=-1, bool blocking=true)
Signals the end of messages to the object.
Definition: cryptlib.h:1434
bool AnyRetrievable() const
Determines whether bytes are ready for retrieval.
Definition: mqueue.h:40
int m_threshold
Definition: ida.h:60
Classes and functions for schemes over GF(2^32)
#define x(i)
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:337
lword TransferTo(BufferedTransformation &target, lword transferMax=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL)
move transferMax bytes of the buffered output to target as input
Definition: cryptlib.h:1654
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: ida.cpp:325
SecBlock< word32 > m_y
Definition: ida.h:63
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1376
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:498
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
Definition: ida.cpp:351
CRYPTOPP_DLL int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:382
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
Definition: filters.cpp:36
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
Definition: ida.cpp:318
unsigned int m_channelsFinished
Definition: ida.h:61
unsigned int m_channelsReady
Definition: ida.h:61
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:512
ANONYMOUS_NAMESPACE_BEGIN const CryptoPP::GF2_32 field
Definition: ida.cpp:14
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: ida.cpp:253
SecBlock< word32 > m_w
Definition: ida.h:63
unsigned int LookupInputChannel(word32 channelId) const
Definition: ida.cpp:89
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:477
#define CRYPTOPP_ASSERT(exp)
Definition: trap.h:92
Classes for polynomial basis and operations.
Redirect input to another BufferedTransformation without owning it.
Definition: filters.h:808
Data structure used to store byte strings.
Definition: queue.h:20
void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n)
Definition: polynomi.cpp:528
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:499
#define ANONYMOUS_NAMESPACE_BEGIN
Definition: config.h:204
Exception thrown by objects that have not implemented nonblocking input processing.
Definition: cryptlib.h:1470
size_t PutWord32(word32 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 32-bit word for processing.
Definition: cryptlib.cpp:719
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
Definition: ida.cpp:28
void PrepareInterpolation()
Definition: ida.cpp:161
size_t GetWord32(word32 &value, ByteOrder order=BIG_ENDIAN_ORDER)
Retrieve a 32-bit word.
Definition: cryptlib.cpp:767
NAMESPACE_END typedef std::reverse_iterator< const byte * > RevIt
Definition: ida.cpp:25
void TransferAllTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL)
Transfer all bytes from this object to another BufferedTransformation.
Definition: cryptlib.h:1763
void ProcessInputQueues()
Definition: ida.cpp:169
virtual unsigned int NumberOfMessages() const
Provides the number of meesages processed by this object.
Definition: cryptlib.cpp:569
InputChannelMap::iterator m_lastMapPosition
Definition: ida.h:55
uint8_t const size_t const size
Definition: sha3.h:20
SecBlock< word32 > m_u
Definition: ida.h:63
int GetAutoSignalPropagation() const
Retrieve automatic signal propagation value.
Definition: simple.h:289
uint8_t byte
Definition: Common.h:10
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:496
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
Definition: ida.cpp:247
#define NAMESPACE_END
Definition: config.h:201
std::vector< char * > parameters
Definition: boostTest.cpp:46
virtual void FlushOutputQueues()
Definition: ida.cpp:230
lword InputBuffered(word32 channelId) const
Definition: ida.cpp:130
void ComputeV(unsigned int)
Definition: ida.cpp:136
word64 lword
Definition: config.h:245
void ChannelData(word32 channelId, const byte *inString, size_t length, bool messageEnd)
Definition: ida.cpp:98
unsigned int word32
Definition: config.h:231
void OutputMessageEnds()
Definition: ida.cpp:371
void OutputMessageEnds()
Definition: ida.cpp:304
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: ida.cpp:383
void FlushOutputQueues()
Definition: ida.cpp:296
void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n)
Definition: polynomi.cpp:515
Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n)
Definition: polynomi.cpp:555
Classes for Rabin&#39;s Information Dispersal and Shamir&#39;s Secret Sharing algorithms. ...
bool ChannelMessageEnd(const std::string &channel, int propagation=-1, bool blocking=true)
Signal the end of a message.
Definition: cryptlib.h:1913
Interface for retrieving values given their names.
Definition: cryptlib.h:279