RE: ERS - using hash tree?

["Tobias Gondrom" <tgondrom@xxxxxxxxxxxx>]

Hello Jesus, 

1. 
> Then, what is the meaning of building the hash tree if you really
> after of building it you canīt add or remove any data object?.

Yes, after you completed the hashtree and protect it with a timestamp you can not add further nodes. (Comment: Typical ERS-systems build one hashtree per day for all documents that were archived during that day and sign the hashtree every evening with a timestamp.)


2. Arity (number of branches at each node) of the hashtree: 
Actually the arity of the hash tree is not restricted by the ERS standard and can be decided by the implementer. 
Several performance and efficiency tests I have seen, have shown that typically a tertiary (or binary) hashtree offers the highest efficiency and performance when handling larger numbers of documents. 

E.g. hashtree for about 2000 documents
With tertiary: 
2187 nodes on the lowest level
729 nodes on 2nd level
243 nodes on 3rd level
81 nodes on 4th level
27 nodes on 5th level
9 nodes on 6th level
3 nodes on 7th level
And the timestamp at the top. 

That way the reduced ERS for one specific document is a lot smaller as it does not need to contain all 2000 nodes of all neighbours, but a lot less.

Plus other operational parameters have also been more efficient. 
(Typically I would recommend a tertiary tree.)

But if you like you can also use a tree with arity n, e.g. n=1000 or n=1.000.000. 

Hope this helps, Tobias




> -----Original Message-----
> From: owner-ietf-ltans@xxxxxxxxxxxx [mailto:owner-ietf-ltans@xxxxxxxxxxxx]
> On Behalf Of Jesus Maria Mendez Perez
> Sent: Thursday, November 22, 2007 6:48 PM
> To: ietf-ltans@xxxxxxx
> Subject: ERS - using hash tree?
> 
> 
> Hello,
> 
> Iīm Jesus and I donīt understand some aspects about using the
> hash-tree to preserving data objects.
> 
> According to ERS if you have 4 data objects the working will be the next
> one:
> 
> 			------		------		------		---
> ---
> 			| d1 |        | d2 |	      | d3 |	     | d4 |
> 			------		------		------		---
> ---
> 			   |		    |		    |		    |
> 			   |		    |		    |		    |
> 			------		------		------		---
> ---
> 			| h1 |        | h2 |	      | h3 |	     | h4 |
> 			------		------		------		---
> ---
> 			    |	            |		   |		    |
> 				 |       |			|      |
> 				    |				   |
> 				--------			------
> 				| h12 |			     | h34 |
> 				--------			------
> 				    |			           |
> 				          |		    |
> 				    		    |
> 						-----------
> 						| h1234 |
> 						-----------
> 		   				     |
> 						--------------
> 						| TSh1234 |
> 				  		--------------
> 
> where "d" are the data objects and "h" are the hash of the data
> objects and "TS" is the timestamp.
> 
> In this case youīll have to do 7 hashes and the additional timestamping.
> 
> Then, what is the meaning of building the hash tree if you really
> after of building it you canīt add or remove any data object?.
> 
> You can simply add the 4 hashes of the 4 data objects and do the finish
> hash.
> Then weīll have to do 5 hashes and the additonal timestamping versus 7
> hashes we had before.
> 
> 			------		------		------		---
> ---
> 			| d1 |        | d2 |	     | d3 |         | d4 |
> 			------		------		------		---
> ---
> 			   |		    |		    |		    |
> 			   |		    |		    |		    |
> 			------		------		------		---
> ---
> 			| h1 |   +   | h2 |   +	   | h3 |   +	  | h4 |
> 			------		------		------		---
> ---
> 			       |           |		   |		  |
> 				    |        |            |           |
> 					|	|       |	  |
> 					-------------------------
> 					| 	h1234         |
> 					-------------------------
> 						    |
> 					----------------------------
> 					|        TSh1234      |
> 					---------------------------
> 
> I dont know if we could do it this last way or if i donīt understand
> the processing of Generation and Verification at all..
> 
> Thanks.