Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
furszy merged 5 commits into from
Aug 3, 2020
Merged

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

furszy merged 5 commits into from
Aug 3, 2020

Conversation

@random-zebra
Copy link

@random-zebra random-zebra commented Jul 28, 2020

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.

@random-zebra random-zebra added this to the 5.0.0 milestone Jul 28, 2020
@random-zebra random-zebra self-assigned this Jul 28, 2020
@random-zebra random-zebra mentioned this pull request Jul 29, 2020
Merged
1 task
sipa and others added 5 commits July 30, 2020 00:54
@sipa @random-zebra
Add SipHash-2-4 primitives to hash
b2e5c4a
@random-zebra
[Core] implement GetUint64 on uint256
15ee581 
Needed while we transition to base_blob
@random-zebra
Use SipHash-2-4 for CCoinsCache index
7e636b2 
>>> backports bitcoin/bitcoin@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.
@sipa @random-zebra
Switch CTxMempool::mapTx to use a hash index for txids
cf27341
@sipa @random-zebra
Use SipHash-2-4 for address relay selection
cbdd0e1
Fuzzbawls
Fuzzbawls approved these changes Aug 2, 2020
View reviewed changes
Copy link
Collaborator

@Fuzzbawls Fuzzbawls left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK cbdd0e1

@random-zebra random-zebra requested a review from furszy August 2, 2020 12:22
furszy
furszy approved these changes Aug 2, 2020
View reviewed changes
Copy link

@furszy furszy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK cbdd0e1

@furszy furszy merged commit 6881e10 into PIVX-Project:master Aug 3, 2020
furszy added a commit that referenced this pull request Aug 5, 2020
@furszy
Merge #1771: [Core] Use SipHash for node eviction
bda654c 
f980d43 Implement SipHash in Python (Pieter Wuille)
042d691 test: Add more test vectors for siphash (Wladimir J. van der Laan)
ba049bf Use C++11 thread-safe static initializers (Pieter Wuille)
0f4290f Use 64-bit SipHash of netgroups in eviction (Pieter Wuille)
d81973a Support SipHash with arbitrary byte writes (Pieter Wuille)
03dba42 Avoid recalculating vchKeyedNetGroup in eviction logic. (Patrick Strateman)

Pull request description:

  Builds on top of
  - [x] #1768

  Use SipHash for node eviction and add more test vectors for siphash
  (backports bitcoin#8173)

ACKs for top commit:
  furszy:
    Looking good, utACK f980d43
  Fuzzbawls:
    utACK f980d43

Tree-SHA512: 8e71322113b32a43e205a1e6dcd3b6a2b466da0f07ac59cc20856792fccb740a21edfc0f3791ddb73457676e8aa29979e155954a50361e519b7757b3aa4f007e
@random-zebra random-zebra modified the milestones: 5.0.0, 4.3.0 Sep 10, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Fuzzbawls Fuzzbawls Fuzzbawls approved these changes

+1 more reviewer

@furszy furszy furszy approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@random-zebra random-zebra

Labels

Upstream UTXO DBs and Indexes

Projects

None yet

Milestone

4.3.0

Development

Successfully merging this pull request may close these issues.

4 participants

@random-zebra @furszy @Fuzzbawls @sipa