1 // /// \file HashChain.d 2 module tagion.hashchain.HashChain; 3 4 import std.range : empty; 5 import std.range.primitives : back, popBack; 6 import tagion.basic.Types : Buffer; 7 import tagion.crypto.Types : Fingerprint; 8 import tagion.hashchain.HashChainBlock : HashChainBlock; 9 import tagion.hashchain.HashChainStorage : HashChainStorage; 10 import tagion.hibon.HiBONRecord : isHiBONRecord; 11 import tagion.utils.Miscellaneous : decode; 12 13 /** @brief File contains class HashChain 14 */ 15 16 /** 17 * \class HashChain 18 * Class stores dynamic info and handles local files of hash chain 19 */ 20 @safe class HashChain(Block : HashChainBlock) if (isHiBONRecord!Block) { 21 /** Handler of chain blocks storage */ 22 protected HashChainStorage!Block _storage; 23 24 /** Last block in chain */ 25 protected Block _last_block; 26 27 /** Ctor initializes database and reads existing data. 28 * @param folder_path - path to folder with chain files 29 */ 30 this(ref HashChainStorage!Block storage) { 31 this._storage = storage; 32 this._last_block = findLastBlock(); 33 } 34 35 /** Method that finds the last block in chain 36 * \return last block or null if it haven't found 37 */ 38 final protected Block findLastBlock() { 39 auto hashes = _storage.getHashes; 40 41 // Table for searching where 42 // key: fingerprints of blocks 43 // value: previous hashes of this blocks 44 Fingerprint[Fingerprint] link_table; 45 foreach (hash; hashes) { 46 link_table[hash] = _storage.read(hash).getPrevious; 47 } 48 49 foreach (fingerprint; link_table.keys) { 50 bool is_last_block = true; 51 52 // Search through all previous hashes for fixed fingerprint 53 foreach (previous; link_table.values) { 54 // Last block can't be previous for another block 55 if (fingerprint == previous) { 56 is_last_block = false; 57 break; 58 } 59 } 60 61 if (is_last_block) { 62 return _storage.read(fingerprint); 63 } 64 } 65 66 return null; 67 } 68 69 /** Get last block 70 * \return last block in chain 71 */ 72 const(Block) getLastBlock() const pure nothrow @nogc { 73 return _last_block; 74 } 75 76 /** Adds given block to the end of chain 77 * @param block - block to append to chain 78 */ 79 void append(Block block) 80 in { 81 assert(block !is null); 82 if (_last_block is null) { 83 assert(block.isRoot); 84 } 85 else { 86 assert(block.getPrevious == _last_block.getHash); 87 } 88 } 89 do { 90 _storage.write(block); 91 _last_block = block; 92 } 93 94 /** Method that checks validity of chain 95 * \return true is chain is valid, false - otherwise 96 */ 97 bool isValidChain() { 98 try { 99 auto blocks_count = _storage.getHashes.length; 100 if (blocks_count == 0) { 101 // Empty chain 102 return true; 103 } 104 105 auto first_block = _storage.find((block) => block.isRoot); 106 if (first_block is null || _last_block is null) { 107 // Non-empty chain is invalid 108 return false; 109 } 110 111 // Iterate from the last to the first block 112 auto current_block = _last_block; 113 foreach (i; 1 .. blocks_count) { 114 auto block = _storage.read(current_block.getPrevious); 115 if (block is null) { 116 return false; 117 } 118 current_block = block; 119 } 120 121 // If reached block is first block - chain is valid 122 return current_block.toDoc.serialize == first_block.toDoc.serialize; 123 } 124 catch (Exception e) { 125 // Any other scenario - chain is invalid 126 return false; 127 } 128 } 129 130 void replay(void delegate(Block) @safe action) { 131 // Replay from beginning with no condition 132 replayFrom(action, (block) => (false)); 133 } 134 135 void replayFrom(void delegate(Block) @safe action, bool delegate(Block) @safe condition) { 136 // If we start from found block (not next after it) we possible can duplicate records 137 138 Fingerprint[] hash_stack; 139 140 // Go through hash chain until condition is triggered 141 auto current_block = _last_block; 142 143 while (current_block !is null && !condition(current_block)) { 144 hash_stack ~= current_block.getHash; 145 current_block = storage.read(current_block.getPrevious); 146 } 147 148 // Apply action in LIFO order 149 while (!hash_stack.empty) { 150 auto block = storage.read(hash_stack.back); 151 assert(block !is null); 152 153 action(block); 154 155 hash_stack.popBack; 156 } 157 } 158 159 final HashChainStorage!Block storage() { 160 return _storage; 161 } 162 } 163 164 version (unittest) { 165 import tagion.crypto.SecureInterfaceNet : HashNet; 166 import tagion.hibon.HiBONRecord : HiBONRecord, exclude, label, recordType; 167 168 @safe class DummyBlock : HashChainBlock { 169 @exclude Fingerprint hash; 170 @label("prev") Fingerprint previous; 171 @label("dummy") int dummy; 172 173 mixin HiBONRecord!( 174 q{ 175 private this( 176 Fingerprint previous, 177 const(HashNet) net, 178 int dummy = 0) 179 { 180 this.previous = previous; 181 this.dummy = dummy; 182 183 this.hash = net.calcHash(toDoc); 184 } 185 186 private this( 187 const(Document) doc, 188 const(HashNet) net) 189 { 190 this(doc); 191 this.hash = net.calcHash(toDoc); 192 } 193 }); 194 195 Fingerprint getHash() const { 196 return hash; 197 } 198 199 Fingerprint getPrevious() const { 200 return previous; 201 } 202 } 203 } 204 205 unittest { 206 import std.file : rmdirRecurse; 207 import std.path : extension, stripExtension; 208 import std.range.primitives : back; 209 import tagion.basic.Types : Buffer, FileExtension; 210 import tagion.basic.basic : tempfile; 211 import tagion.communication.HiRPC : HiRPC; 212 import tagion.crypto.SecureNet : StdHashNet; 213 import tagion.dart.Recorder : RecordFactory; 214 import tagion.hashchain.HashChainFileStorage; 215 216 HashNet net = new StdHashNet; 217 218 const empty_hash = Fingerprint.init; 219 const temp_folder = tempfile ~ "/"; 220 221 alias Storage = HashChainStorage!DummyBlock; 222 alias StorageImpl = HashChainFileStorage!DummyBlock; 223 alias ChainImpl = HashChain!DummyBlock; 224 225 /// HashChain_empty_folder 226 { 227 Storage storage = new StorageImpl(temp_folder, net); 228 auto chain = new ChainImpl(storage); 229 230 assert(chain.getLastBlock is null); 231 assert(chain.isValidChain); 232 233 rmdirRecurse(temp_folder); 234 } 235 236 /// HashChain_single_block 237 { 238 Storage storage = new StorageImpl(temp_folder, net); 239 auto chain = new ChainImpl(storage); 240 241 auto block0 = new DummyBlock(empty_hash, net); 242 chain.append(block0); 243 244 assert(chain.getLastBlock.toDoc.serialize == block0.toDoc.serialize); 245 assert(chain.isValidChain); 246 247 // Amount of blocks 248 assert(chain.storage.getHashes.length == 1); 249 250 // Find block with given hash 251 auto found_block = chain.storage.find((b) => (b.getHash == block0.getHash)); 252 assert(found_block !is null && found_block.toDoc.serialize == block0.toDoc.serialize); 253 254 rmdirRecurse(temp_folder); 255 } 256 257 /// HashChain_many_blocks 258 { 259 Storage storage = new StorageImpl(temp_folder, net); 260 auto chain = new ChainImpl(storage); 261 262 auto block0 = new DummyBlock(Fingerprint.init, net); 263 chain.append(block0); 264 auto block1 = new DummyBlock(chain.getLastBlock.getHash, net); 265 chain.append(block1); 266 auto block2 = new DummyBlock(chain.getLastBlock.getHash, net); 267 chain.append(block2); 268 269 assert(chain.getLastBlock.toDoc.serialize == block2.toDoc.serialize); 270 assert(chain.isValidChain); 271 272 // Amount of blocks 273 assert(chain.storage.getHashes.length == 3); 274 275 // Find root block 276 auto found_block = chain.storage.find((b) => b.isRoot); 277 assert(found_block !is null && found_block.toDoc.serialize == block0.toDoc.serialize); 278 279 rmdirRecurse(temp_folder); 280 } 281 282 /// HashChain_replay 283 { 284 Storage storage = new StorageImpl(temp_folder, net); 285 auto chain = new ChainImpl(storage); 286 287 auto block0 = new DummyBlock(Fingerprint.init, net); 288 chain.append(block0); 289 auto block1 = new DummyBlock(chain.getLastBlock.getHash, net); 290 chain.append(block1); 291 auto block2 = new DummyBlock(chain.getLastBlock.getHash, net); 292 chain.append(block2); 293 294 assert(chain.isValidChain); 295 296 Fingerprint[] hashes; 297 298 chain.replay((DummyBlock b) @safe { hashes ~= b.getHash; }); 299 300 assert(hashes.length == 3); 301 assert(hashes[0] == block0.getHash); 302 assert(hashes[1] == block1.getHash); 303 assert(hashes[2] == block2.getHash); 304 305 rmdirRecurse(temp_folder); 306 } 307 308 /// HashChain_replayFrom 309 { 310 Storage storage = new StorageImpl(temp_folder, net); 311 auto chain = new ChainImpl(storage); 312 313 enum blocks_count = 10; 314 DummyBlock[] blocks; 315 316 // Add blocks 317 foreach (i; 0 .. blocks_count) { 318 auto last_block = chain.getLastBlock; 319 320 blocks ~= new DummyBlock(last_block is null ? Fingerprint.init : last_block.getHash, net); 321 322 chain.append(blocks.back); 323 } 324 assert(chain.isValidChain); 325 326 enum some_block_index = 2; 327 Fingerprint[] hashes; 328 329 // Replay from block with specified index 330 chain.replayFrom((DummyBlock b) @safe { hashes ~= b.getHash; }, (b) => b.getHash == blocks[some_block_index] 331 .getHash); 332 333 // Check array with hashes 334 assert(hashes.length == blocks_count - some_block_index - 1); 335 foreach (i, hash; hashes) { 336 assert(hashes[i] == blocks[i + some_block_index + 1].getHash); 337 } 338 339 rmdirRecurse(temp_folder); 340 } 341 }