Arbitrary length sha256, 192-bit truncated sha256 (squeeze two to one in a single sha256 block), Hash192 support

[cf]

Changes:

1. Cleaned up the sha256 implementation (block digest -> reusable function, same with constant generation and state)
2. Added support for arbitrary length sha256 (no longer limited to 512 bit inputs as before, see a test with 1600 bit input)
3. Added 192-bit truncated sha256 support (much faster for merkle tree verification 🎉, as we only need one sha256 block per level since (384 (192*2 = left and right hashes) + 12 (padding/bit length info)) < 512
4. Added 192-bit truncated sha256 merkle tree support (both delta and standard) + compute root from leaves (useful for bridging small batches of data to L1 with minimal public input footprint)
5. Added conversion support from HashOutTarget <-> Hash192Target, where each element of the HashOut contains 48 bits of the 192 bit truncated sha256 hash, makes it super easy to integrate L1 event data with existing poseidon merkle tree/storage gadgets.

SHA256/T192 = 2x Speed Up 🎉

two_to_one for sha256 truncated to 192-bits

How to test locally:

cargo test --release --package plonky2_crypto --lib -- hash::sha256_truncated::tests::test_truncated_sha256_two_to_one --exact --nocapture 

Observed results:

running 1 test
two_to_one_truncated_sha256 num_gates=1408, copy_constraints=<private>, quotient_degree_factor=8
two_to_one_truncated_sha256 proved in 129ms
two_to_one_truncated_sha256 proved in 130ms
two_to_one_truncated_sha256 proved in 151ms
two_to_one_truncated_sha256 proved in 140ms
two_to_one_truncated_sha256 proved in 132ms
two_to_one_truncated_sha256 proved in 141ms
two_to_one_truncated_sha256 proved in 176ms
two_to_one_truncated_sha256 proved in 140ms
two_to_one_truncated_sha256 proved in 141ms
two_to_one_truncated_sha256 proved in 139ms
two_to_one_truncated_sha256 proved in 167ms
two_to_one_truncated_sha256 proved in 157ms
test hash::sha256_truncated::tests::test_truncated_sha256_two_to_one ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 52 filtered out; finished in 1.89s

two_to_one for normal sha256

How to test locally:

cargo test --release --package plonky2_crypto --lib -- hash::sha256::tests::test_sha256_two_to_one --exact --nocapture

Observed results:

running 1 test
two_to_one_sha256 num_gates=2813, copy_constraints=<private>, quotient_degree_factor=8
two_to_one_sha256 proved in 253ms
two_to_one_sha256 proved in 270ms
two_to_one_sha256 proved in 314ms
two_to_one_sha256 proved in 268ms
two_to_one_sha256 proved in 273ms
two_to_one_sha256 proved in 272ms
two_to_one_sha256 proved in 273ms
two_to_one_sha256 proved in 255ms
two_to_one_sha256 proved in 261ms
two_to_one_sha256 proved in 262ms
two_to_one_sha256 proved in 290ms
two_to_one_sha256 proved in 274ms
test hash::sha256::tests::test_sha256_two_to_one ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 52 filtered out; finished in 3.51s

So by using 192-bit truncated sha256 we get ~2x speed up + 50% less gates 🎉

SHA-256/T-192 is well understood as far as cryptanalysis goes and should be at least as secure as the underlying proof system as far as collisions go, see NIST.SP.800-208