Source: sync/digest-tree.js

  1. /**
  2. * This class represents the digest tree for chrono-sync2013.
  3. * Copyright (C) 2014-2016 Regents of the University of California.
  4. * @author: Zhehao Wang, based on Jeff T.'s implementation in ndn-cpp
  5. *
  6. * This program is free software: you can redistribute it and/or modify
  7. * it under the terms of the GNU Lesser General Public License as published by
  8. * the Free Software Foundation, either version 3 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU Lesser General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU Lesser General Public License
  17. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  18. * A copy of the GNU Lesser General Public License is in the file COPYING.
  19. */
  20. // Use capitalized Crypto to not clash with the browser's crypto.subtle.
  21. /** @ignore */
  22. var Crypto = require('../crypto.js');
  23. /**
  24. * @constructor
  25. */
  26. var DigestTree = function DigestTree()
  27. {
  28. this.root = "00";
  29. this.digestnode = [];
  30. };
  31. exports.DigestTree = DigestTree;
  32. // The meaning of a session is explained here:
  33. // http://named-data.net/doc/ndn-ccl-api/chrono-sync2013.html
  34. // DigestTree.Node works with seqno_seq and seqno_session, without protobuf definition,
  35. DigestTree.Node = function DigestTreeNode(dataPrefix, seqno_session, seqno_seq)
  36. {
  37. // In this context, this should mean DigestTree.Node instead
  38. this.dataPrefix = dataPrefix;
  39. this.seqno_session = seqno_session;
  40. this.seqno_seq = seqno_seq;
  41. this.recomputeDigest();
  42. };
  43. DigestTree.Node.prototype.getDataPrefix = function()
  44. {
  45. return this.dataPrefix;
  46. };
  47. DigestTree.Node.prototype.getSessionNo = function()
  48. {
  49. return this.seqno_session;
  50. };
  51. DigestTree.Node.prototype.getSequenceNo = function()
  52. {
  53. return this.seqno_seq;
  54. };
  55. DigestTree.Node.prototype.getDigest = function()
  56. {
  57. return this.digest;
  58. };
  59. DigestTree.Node.prototype.setSequenceNo = function(sequenceNo)
  60. {
  61. this.seqno_seq = sequenceNo;
  62. this.recomputeDigest();
  63. };
  64. // Using Node.JS buffer, as documented here http://nodejs.org/api/buffer.html.
  65. DigestTree.Node.prototype.Int32ToBuffer = function(value) {
  66. var result = new Buffer(4);
  67. for (var i = 0; i < 4; i++) {
  68. result[i] = value % 256;
  69. value = Math.floor(value / 256);
  70. }
  71. return result;
  72. }
  73. DigestTree.Node.prototype.recomputeDigest = function()
  74. {
  75. var seqHash = Crypto.createHash('sha256');
  76. seqHash.update(this.Int32ToBuffer(this.seqno_session));
  77. seqHash.update(this.Int32ToBuffer(this.seqno_seq));
  78. var digest_seq = seqHash.digest();
  79. var nameHash = Crypto.createHash('sha256');
  80. nameHash.update(this.dataPrefix);
  81. var digest_name = nameHash.digest();
  82. var hash = Crypto.createHash('sha256');
  83. hash.update(digest_name);
  84. hash.update(digest_seq);
  85. this.digest = hash.digest('hex');
  86. };
  87. // Do the work of string and then sequence number compare
  88. DigestTree.Node.Compare = function(node1, node2)
  89. {
  90. if (node1.dataPrefix != node2.dataPrefix)
  91. return node1.dataPrefix < node2.dataPrefix;
  92. return node1.seqno_session < node2.seqno_session;
  93. };
  94. /**
  95. * Update the digest tree and recompute the root digest. If the combination of dataPrefix
  96. * and sessionNo already exists in the tree then update its sequenceNo (only if the given
  97. * sequenceNo is newer), otherwise add a new node.
  98. * @param {string} The name prefix.
  99. * @param {int} sessionNo The session number.
  100. * @param {int} sequenceNo The sequence number.
  101. * @return True if the digest tree is updated, false if not
  102. */
  103. DigestTree.prototype.update = function(dataPrefix, sessionNo, sequenceNo)
  104. {
  105. var n_index = this.find(dataPrefix, sessionNo);
  106. if (n_index >= 0) {
  107. if (this.digestnode[n_index].getSequenceNo() < sequenceNo)
  108. this.digestnode[n_index].setSequenceNo(sequenceNo);
  109. else
  110. return false;
  111. }
  112. else {
  113. var temp = new DigestTree.Node(dataPrefix, sessionNo, sequenceNo);
  114. this.digestnode.push(temp);
  115. this.digestnode.sort(this.sortNodes);
  116. }
  117. this.recomputeRoot();
  118. return true;
  119. };
  120. // Need to confirm this sort works with the insertion in ndn-cpp.
  121. DigestTree.prototype.sortNodes = function()
  122. {
  123. var temp;
  124. for (var i = this.digestnode.length; i > 0; i--) {
  125. for (var j = 0; j < i - 1; j++) {
  126. if (this.digestnode[j].getDataPrefix() > this.digestnode[j + 1].getDataPrefix()) {
  127. temp = this.digestnode[j];
  128. this.digestnode[j] = this.digestnode[j + 1];
  129. this.digestnode[j + 1] = temp;
  130. }
  131. }
  132. }
  133. };
  134. DigestTree.prototype.sortNodes = function (node1, node2)
  135. {
  136. if (node1.getDataPrefix() == node2.getDataPrefix() &&
  137. node1.getSessionNo() == node2.getSessionNo())
  138. return 0;
  139. if ((node1.getDataPrefix() > node2.getDataPrefix()) ||
  140. ((node1.getDataPrefix() == node2.getDataPrefix()) &&
  141. (node1.getSessionNo() >node2.getSessionNo())))
  142. return 1;
  143. else
  144. return -1;
  145. }
  146. DigestTree.prototype.find = function(dataPrefix, sessionNo)
  147. {
  148. for (var i = 0; i < this.digestnode.length; ++i) {
  149. if (this.digestnode[i].getDataPrefix() == dataPrefix &&
  150. this.digestnode[i].getSessionNo() == sessionNo)
  151. return i;
  152. }
  153. return -1;
  154. };
  155. DigestTree.prototype.size = function()
  156. {
  157. return this.digestnode.size();
  158. };
  159. // Not really used
  160. DigestTree.prototype.get = function(i)
  161. {
  162. return this.digestnode[i];
  163. };
  164. DigestTree.prototype.getRoot = function()
  165. {
  166. return this.root;
  167. };
  168. DigestTree.prototype.recomputeRoot = function()
  169. {
  170. var md = Crypto.createHash('sha256');
  171. // The result of updateHex is related with the sequence of participants,
  172. // I don't think that should be the case.
  173. for (var i = 0; i < this.digestnode.length; i++) {
  174. md.update(new Buffer(this.digestnode[i].digest, 'hex'));
  175. }
  176. this.root = md.digest('hex');
  177. };