11
$\begingroup$

I have a data set with 300 Million entries and every 5 minutes 4000 random entries in this table change. I need to calculate the merkle root on this data set to validate integrity multiple times every 5 minutes.

Assuming sha224 hashes this would be 8 GB for just the leaf nodes and almost 16 GB of data would have to be processed via sha224 to calculate the root and would take over 5 minutes to calculate. To accelerate the calculation I must cache the tree and make incremental updates.

Is there a any known approach to accelerate incremental updates without requiring 16 GB memory mapped merkle tree?

|improve this question
$\endgroup$
  • $\begingroup$ The key point here is that you're validating integrity - if you'd explain exactly your problem (details concerning the way integrity should be checked) rather than your solution we might be able to help you better. Though I'm not exactly sure whether that revised question would still be fit for crypto.stackexchange.com . $\endgroup$ – orlp Jul 13 '13 at 5:09
  • 2
    $\begingroup$ You can choose until which level you keep the tree. If you keep less of the tree updates become more expensive, but you need less memory. $\endgroup$ – CodesInChaos Jul 13 '13 at 10:02
  • 1
    $\begingroup$ Do you have to keep working with SHA-224? Maybe you could switch to SHA-224/512 which would be the same size but faster on 64 bit machines (which I presume you are using, this doesn't sound like an embedded platform). $\endgroup$ – Maarten Bodewes♦ Jul 13 '13 at 20:52
  • 2
    $\begingroup$ Is it that the updates coming in at a rate of 4000 per 5 minutes, $\hspace{2.56 in}$ or that once each 5 minutes you receive a list of 4000 updates? $\:$ $\endgroup$ – user991 Jul 13 '13 at 21:37
  • 5
    $\begingroup$ Questions about Merkle trees, about cryptographic schemes for protecting integrity, or about performance optimization of cryptographic data structures are all completely on-topic for this site. bytemaster, I'm not sure why you're getting feedback suggesting that your question is out of scope (it isn't; it is perfectly within the scope of this site), but please don't be discouraged: there's nothing wrong with your question. Actually, your question is excellent and just the sort of question I'd love to see more of! $\endgroup$ – D.W. Aug 7 '13 at 4:08
8
$\begingroup$

Yes, you should be able to handle this situation readily. There are many optimizations available.

One key observation is that if you're going to go to disk, then you might as well read lots of data: it takes just as long to read an entire block of data as to read 1 byte. So, I suggest you store the data on disk in 4096-byte blocks, and do a Merkle tree over these blocks. In particular, you will have one leaf per 4096-byte block. Then you can store the Merkle tree in memory.

Second, there's no need to use SHA224. A 160-bit hash is sufficient, so you could use SHA1 (or SHA224/SHA256) truncated to 160 bits. This way, each hash will be 20 bytes long.

How will this perform? Each 4096-byte block on disk can store about 200 hashes. Therefore, you'll have about 1.5 million blocks. Treating the hash of each block as a leaf, we have a Merkle tree with 1.5 million leaves. Such a Merkle tree has 3 million nodes in total, which you can store in memory using just 60 MB of RAM.

Every 5 minutes, 4000 random entries will be modified. This requires you to read 4000 blocks from disk, update them, recompute their hashes, and update the Merkle tree. To read the 4000 blocks, update them, and write them back out to disk will involve reading 16 MB of data and writing 16 MB of data; no problem. Hashing all of this data will take about 40 ms, since you can hash a 4096-byte block in about 10 microseconds. Then, you'll need to update about 8000 nodes in the Merkle tree. This involves computing 8000 hashes on short inputs, which will take about 4 ms, since it takes about 0.5 microseconds per hash of a short input. Overall, the performance impact on your system should be very low. (These numbers are on one particular machine I happened to have laying around, using SHA1. Your numbers may vary by a constant factor, but probably not by an order of magnitude.)

Overall, this solution should perform extremely well, both in memory consumption as well as in CPU usage.

If you want to squeeze out every last byte of RAM, there are other tricks available. You can save up to a factor of 2x in memory usage if you use a tree with a much higher branching factor, rather than a binary tree (though this will cost you a little bit in CPU utilization).

Also, you can safely truncate the size of the hash down to about 80 bits (10 bytes), if you use a UOWHF. One way to do this is to pick a secret 128-bit key $K$, and then the hash of the data $X$ is $H(X || K)$ (i.e., append $K$ to the data before hashing), truncated to 80 bits. The use of the key $K$ (i.e., the use of a UOWHF) eliminates the opportunity for birthday attacks, so in this situation, 80 bits is enough. This can save you another 2x in memory usage.

|improve this answer
$\endgroup$
  • $\begingroup$ Unfortunately, I need the tree to be cryptographically secure and cannot rely on secrets because the tree needs to be publicly verifiable (think bitcoin). Thanks for the info about 80bit hashes in this case, it may be useful other places. $\endgroup$ – bytemaster Aug 10 '13 at 18:31
  • $\begingroup$ As for using larger blocks, in my case the purpose is to provide the lightest weight proof of membership and using 4096 byte blocks would create much larger branch sizes. Though that may be a suitable compromise. $\endgroup$ – bytemaster Aug 10 '13 at 18:37
  • $\begingroup$ @bytemaster, if you like, the 4096-byte block can itself be structured as a Merkle tree. This is roughly equivalent to building a Merkle tree on all the records (each record = a leaf of the big Merkle tree) and only storing the top 20-21 levels of the Merkle tree in RAM, which is also a valid optimization. There are many possible optimizations -- hopefully my answer helps you identify some of the possibilities, so you can choose whichever one is most appropriate for your specific setting. $\endgroup$ – D.W. Aug 10 '13 at 18:55
4
$\begingroup$

Merkle trees allow several time-memory-tradeoffs:

  1. Using larger leaves or store only hashes at a certain level above then leaves. Now you need to hash a bigger leaf for update, but you need to keep fewer intermediate hashes in memory.
  2. Using a higher fanout. With fanout=2 you need to keep 2*n hashes in memory. With fanout=4 you only need 1.33*n hashes. But you need to do more work per-node, so CPU wise it cancels out.
  3. You could drop the tree idea entirely storing only one additional layer with a million entries. That way the hashing cost drops by a factor of 200 compared to a plain sequential hash while taking only 24 MB of additional memory.

You could also optimize the hash. 5 mins for hashing 16 GB is pretty long, even with SHA-224. You should be able to speed it up by a factor of 2 even with a single core. You could also try Blake2s which should be 2-3 times as fast.

I worked on Blake2, so I might be biased

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.