Use SipHash-2-4 for various non-cryptographic hashes by sipa · Pull Request #8020 · bitcoin/bitcoin

sipa · 2016-05-06T20:01:10Z

Use SipHash-2-4 for:

CCoinsViewCache hashmap (instead of a custom Lookup3/XOR scheme)
CTxMempool::mapTx txid index (converting from an ordered map)
Address relay peer selection (instead of SHA256)

Computing a hash for a txid using this takes around 52 CPU cycles in benchmarks (the Lookup3/XOR based mechanism used for CCoinsViewCache took 31 cycles). I think that's negligible still, while using a much more standard construct designed for such purposes.

gmaxwell · 2016-05-06T20:24:47Z

Concept ACK.

pstratem · 2016-05-06T21:11:40Z

Concept ACK
ad00e3af31df0655c1cdc95b8d29dcc1ec413e5b

kazcw · 2016-05-07T01:06:25Z

What if pnode is 32-bit?

Nice catch. I've replaced it by using pnode->id.

laanwj · 2016-05-07T08:27:43Z

Concept ACK
Python took the same step for 3.4 to convert their hash algorithms to SipHash, and they have similar motivations of mitigating collision attacks, so we're in good company: https://www.python.org/dev/peps/pep-0456/

sipa · 2016-05-08T23:13:44Z

Here is a comment about using SipHash-1-3 instead of SipHash-2-4: rust-lang/rust#29754 (comment)

It would be approximately twice as fast for hashing txids, and the distinguisher mentioned in that comment is not relevant for data that is a multiple of 8 bytes (which is the case for us), as 8 bytes of padding are added in that case. Opinions?

laanwj · 2016-05-09T10:39:05Z

Siphash 2-4 seems to be the defacto 'safe' choice. Siphash 1-3 happens to be secure for our use case right now, but that sounds a tad brittle: as if a small change in our use case, or a small advancement in cryptoanalysis of the function, could mean that the known weakness does suddenly affect us?

Not sure how much hashing the txids is a bottleneck in the whole scheme of things around CCoinsCache, it's only 32 bytes after all. Conservatively I'd say only consider 'downgrading' if performance is seriously affected by going from 29 cycles to 49 cycles.

On the other hand it's pretty nice if using a hash with better security properties could be faster than the Lookup3/XOR scheme, so I see the attraction in that.

sipa · 2016-05-09T17:28:29Z

Did some better benchmarks:

Current Lookup3-based approach: 31 cycles
SipHash-2-4: 52 cycles
SipHash-1-3: 32 cycles

dcousens · 2016-05-11T03:14:40Z

Ha, I thought SipHash was something home grown by @sipa... TIL.
LGTM, for the record, do we have a comparison with cycle counts of the other hash functions? (SHA1 say?)

sipa · 2016-05-11T04:14:53Z

@dcousens Based on numbers I get from #8039:

SHA1: 577 cycles (1 block, 64 bytes)
SHA256: 1504 cycles (1 block, 64 bytes)
SHA512: 1988 cycles (1 block, 128 bytes)
RIPEMD160: 751 cycles (1 block, 64 bytes)

dcousens · 2016-05-11T04:25:37Z

Thanks @sipa 👍

TheBlueMatt · 2016-05-15T23:37:15Z

It'd be nice to not break aliasing rules here? Shouldnt the compiler optimize out a manual-shift-or?

sipa · 2016-05-16T22:38:08Z

Going to stick to SipHash-2-4 for now. We can always switch to something else later.

Ready for merge, I think.

pstratem · 2016-05-17T04:49:47Z

utACK 658c6481616f12a3466d1ddeb23eb91788ab2e66

gmaxwell · 2016-05-17T07:46:18Z

ACK

TheBlueMatt · 2016-05-17T17:31:47Z

This is ~1.7x slower than the Lookup3-of-Xor-with-salt construct we were using before, but it is a primitive designed for exactly this.

TheBlueMatt · 2016-05-17T18:47:24Z

ACK a68ec21

a68ec21 Use SipHash-2-4 for address relay selection (Pieter Wuille) 8cc9cfe Switch CTxMempool::mapTx to use a hash index for txids (Pieter Wuille) 382c871 Use SipHash-2-4 for CCoinsCache index (Pieter Wuille) 0b1295b Add SipHash-2-4 primitives to hash (Pieter Wuille)

rebroad · 2016-08-09T08:58:52Z

I'm trying to work out what problem these siphashes fix. What is the risk that this solves please?

laanwj · 2016-08-13T13:46:11Z

It's fast and cryptographically solid - which reduces DoS risk by attackers remotely predicting the behavior of the hash function.

As I quoted above already, pretty much same rationale as for Python: https://www.python.org/dev/peps/pep-0456/

a68ec21 Use SipHash-2-4 for address relay selection (Pieter Wuille) 8cc9cfe Switch CTxMempool::mapTx to use a hash index for txids (Pieter Wuille) 382c871 Use SipHash-2-4 for CCoinsCache index (Pieter Wuille) 0b1295b Add SipHash-2-4 primitives to hash (Pieter Wuille)

elichai · 2020-01-30T09:17:55Z

Here is a comment about using SipHash-1-3 instead of SipHash-2-4: rust-lang/rust#29754 (comment)

It would be approximately twice as fast for hashing txids, and the distinguisher mentioned in that comment is not relevant for data that is a multiple of 8 bytes (which is the case for us), as 8 bytes of padding are added in that case. Opinions?

For future reference.
Because of all the interesting results @jamesob got from the hashmap modifications, I decided to try benchmarking siphash2-4 vs 1-3 by replacing SaltedOutpointHasher and SaltedTxidHasher with SipHash1-3 and this is the result:

Command: /home/profiler/bitcoin/src/bitcoind -datadir="/home/profiler/.bitcoin" -dbcache=12288 -debug=0 -nodebuglogfile -printtoconsole=0 -reindex-chainstate -stopatheight=600000

Before:

real    119m16.133s
user    137m38.092s
sys     2m30.990s

After:

real    115m6.045s
user    133m53.661s
sys     2m30.177s

Spec: i7-8700 CPU @ 3.20GHz, 32GB RAM, NVMe SSD.

cbdd0e1 Use SipHash-2-4 for address relay selection (Pieter Wuille) cf27341 Switch CTxMempool::mapTx to use a hash index for txids (Pieter Wuille) 7e636b2 Use SipHash-2-4 for CCoinsCache index (random-zebra) 15ee581 [Core] implement GetUint64 on uint256 (random-zebra) b2e5c4a Add SipHash-2-4 primitives to hash (Pieter Wuille) Pull request description: Backports bitcoin#8020 > Use SipHash-2-4 for: > > - CCoinsViewCache hashmap (instead of a custom Lookup3/XOR scheme) > - CTxMempool::mapTx txid index (converting from an ordered map) > - Address relay peer selection (instead of SHA256) > > Computing a hash for a txid using this takes around 52 CPU cycles in benchmarks (the Lookup3/XOR based mechanism used for CCoinsViewCache took 31 cycles). I think that's negligible still, while using a much more standard construct designed for such purposes. ACKs for top commit: Fuzzbawls: ACK cbdd0e1 furszy: ACK cbdd0e1 Tree-SHA512: 223f2f119c94991f1e3594afbacc2dd2476a689b9127860c7e8e244052e5e2cddc486ee44f5345370185f1cd337dfd67c2ec9a44e9dcc8f6cc391a011364ce8f

Backport of bitcoin/bitcoin#8020 Cherry-picked from bitcoin/bitcoin#8020 - cherry-pick bitcoin/bitcoin@a68ec21f7e - conflict with bitcoin/bitcoin@957e5d2 - cherry-pick bitcoin/bitcoin@8cc9cfe160 - cherry-pick bitcoin/bitcoin@382c871d28 - replace CCoinsKeyHasher with SaltedTxidHasher - cherry-pick bitcoin/bitcoin@0b1295b066 - self-conflict with previously-applied bitcoin/bitcoin@b8a657936 (#3180)

kazcw reviewed May 7, 2016
View reviewed changes

sipa force-pushed the siphash branch from ad00e3a to ed52170 Compare May 7, 2016 02:24

laanwj added the UTXO Db and Indexes label May 7, 2016

sipa force-pushed the siphash branch from ed52170 to d92580d Compare May 8, 2016 22:36

TheBlueMatt reviewed May 15, 2016
View reviewed changes

sipa force-pushed the siphash branch from d92580d to 658c648 Compare May 16, 2016 04:47

TheBlueMatt reviewed May 17, 2016
View reviewed changes

sipa added 4 commits May 17, 2016 20:04

Add SipHash-2-4 primitives to hash

0b1295b

Use SipHash-2-4 for CCoinsCache index

382c871

This is ~1.7x slower than the Lookup3-of-Xor-with-salt construct we were using before, but it is a primitive designed for exactly this.

Switch CTxMempool::mapTx to use a hash index for txids

8cc9cfe

Use SipHash-2-4 for address relay selection

a68ec21

sipa force-pushed the siphash branch from 658c648 to a68ec21 Compare May 17, 2016 18:04

TheBlueMatt mentioned this pull request May 18, 2016

Compact Blocks #8068

Merged

laanwj merged commit a68ec21 into bitcoin:master May 18, 2016

defuse mentioned this pull request Aug 16, 2016

Merge upstream anti DoS patches zcash/zcash#1251

Open

sickpig mentioned this pull request Oct 1, 2017

dbcache phase 3 enhancements BitcoinUnlimited/BitcoinUnlimited#785

Merged

dagurval mentioned this pull request Jan 14, 2018

Use SipHash-2-4 for various non-cryptographic hashes bitcoinxt/bitcoinxt#295

Merged

random-zebra mentioned this pull request Jul 28, 2020

[Core] Use SipHash-2-4 for various non-cryptographic hashes PIVX-Project/PIVX#1768

Merged

nuttycom mentioned this pull request Feb 11, 2021

Backport of bitcoin/bitcoin#8020 zcash/zcash#4979

Merged

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

Uh oh!

Conversation

sipa commented May 6, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gmaxwell commented May 6, 2016

Uh oh!

pstratem commented May 6, 2016

Uh oh!

kazcw May 7, 2016

Choose a reason for hiding this comment

Uh oh!

sipa May 7, 2016

Choose a reason for hiding this comment

Uh oh!

laanwj commented May 7, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sipa commented May 8, 2016

Uh oh!

laanwj commented May 9, 2016

Uh oh!

sipa commented May 9, 2016

Uh oh!

dcousens commented May 11, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sipa commented May 11, 2016

Uh oh!

dcousens commented May 11, 2016

Uh oh!

TheBlueMatt May 15, 2016

Choose a reason for hiding this comment

Uh oh!

sipa May 16, 2016

Choose a reason for hiding this comment

Uh oh!

sipa commented May 16, 2016

Uh oh!

pstratem commented May 17, 2016

Uh oh!

gmaxwell commented May 17, 2016

Uh oh!

TheBlueMatt May 17, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa May 17, 2016

Choose a reason for hiding this comment

Uh oh!

TheBlueMatt commented May 17, 2016

Uh oh!

rebroad commented Aug 9, 2016

Uh oh!

laanwj commented Aug 13, 2016

Uh oh!

elichai commented Jan 30, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

sipa commented May 6, 2016 •

edited

Loading

laanwj commented May 7, 2016 •

edited

Loading

dcousens commented May 11, 2016 •

edited

Loading

TheBlueMatt May 17, 2016 •

edited

Loading