Recursive hashing

[JohnLCaron]

CHVote Algorithm 4.14 hashes each component of an array or matrix separately, and then hashes those together.

"it is important to ensure that collisions can not occur in a trivial manner.
This happens for example when applying the hash algorithm directly to the concatenated
byte arrays. A general approach to circumvent this type of problem is to first apply the hash
algorithm individually to each Bi and then to the concatenation of the obtained hashes"

Currently this is only used in computing the challenge.

ElectionGuard does not use recursive hashing, but it does use Hmac based on SHA-256 instead of plain SHA-256:

val md : Mac = Mac.getInstance("HmacSHA256")

instead of

val digest = MessageDigest.getInstance("SHA-256")

Is that why they dont need recursive hashing?

[JohnLCaron]

1. hashFunction is EG algorithm using HmacSHA256 and byte array concatenation
2. recursive HmacSHA256 Mac
3. recursive SHA-256 MessageDigest, reuse digest
4. recursive SHA-256 MessageDigest, new digest each time
5. recursive SHA3-256 MessageDigest, reuse digest

hashFunction took 28.908095 ms for 1000 nrows, .02891 ms per nrows
recursive HmacSHA256 took 5.351683 ms for 1000 nrows, .005352 ms per nrows
recursive SHA-256  took 1.758207 ms for 1000 nrows, .001758 ms per nrows
recursive SHA-256n took 1.554848 ms for 1000 nrows, .001555 ms per nrows
recursive SHA3-256 took 20.943696 ms for 1000 nrows, .02094 ms per nrows

hashFunction took 32.410175 ms for 34000 nrows, .0009532 ms per nrows
recursive HmacSHA256 took 67.783999 ms for 34000 nrows, .001994 ms per nrows
recursive SHA-256  took 30.244888 ms for 34000 nrows, .0008896 ms per nrows
recursive SHA-256n took 28.702903 ms for 34000 nrows, .0008442 ms per nrows
recursive SHA3-256 took 63.514814 ms for 34000 nrows, .001868 ms per nrows

hashFunction took 475.610809 ms for 1000000 nrows, .0004756 ms per nrows
recursive HmacSHA256 took 1336.082916 ms for 1000000 nrows, .001336 ms per nrows
recursive SHA-256  took 508.45002 ms for 1000000 nrows, .0005085 ms per nrows
recursive SHA-256n took 493.843155 ms for 1000000 nrows, .0004938 ms per nrows
recursive SHA3-256 took 1501.092171 ms for 1000000 nrows, .001501 ms per nrows