From: Jonathan Nieder <jrnieder@gmail.com> To: Junio C Hamano <gitster@pobox.com> Cc: "Adam Langley" <agl@google.com>, "Johannes Schindelin" <Johannes.Schindelin@gmx.de>, "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>, "brian m. carlson" <sandals@crustytoothpaste.net>, "Jeff King" <peff@peff.net>, "Mike Hommey" <mh@glandium.org>, "Brandon Williams" <bmwill@google.com>, "Linus Torvalds" <torvalds@linux-foundation.org>, "Git Mailing List" <git@vger.kernel.org>, "Stefan Beller" <sbeller@google.com>, "Jonathan Tan" <jonathantanmy@google.com> Subject: Re: Which hash function to use, was Re: RFC: Another proposed hash function transition plan Date: Fri, 16 Jun 2017 14:24:14 -0700 Message-ID: <20170616212414.GC133952@aiede.mtv.corp.google.com> (raw) In-Reply-To: <xmqqr2yjwsb6.fsf@gitster.mtv.corp.google.com> Junio C Hamano wrote: > Junio C Hamano <gitster@pobox.com> writes: >> Adam Langley <agl@google.com> writes: >>> However, as I'm not a git developer, I've no opinion on whether the >>> cost of carrying implementations of these functions is worth the speed >>> vs using SHA-256, which can be assumed to be supported everywhere >>> already. >> >> Thanks. >> >> My impression from this thread is that even though fast may be >> better than slow, ubiquity trumps it for our use case, as long as >> the thing is not absurdly and unusably slow, of course. Which makes >> me lean towards something older/more established like SHA-256, and >> it would be a very nice bonus if it gets hardware acceleration more >> widely than others ;-) > > Ah, I recall one thing that was mentioned but not discussed much in > the thread: possible use of tree-hashing to exploit multiple cores > hashing a large-ish payload. As long as it is OK to pick a sound > tree hash coding on top of any (secure) underlying hash function, > I do not think the use of tree-hashing should not affect which exact > underlying hash function is to be used, and I also am not convinced > if we really want tree hashing (some codepaths that deal with a large > payload wants to stream the data in single pass from head to tail) > in the context of Git, but I am not a crypto person, so ... Tree hashing also affects single-core performance because of the availability of SIMD instructions. That is how software implementations of e.g. blake2bp-256 and SHA-256x16[1] are able to have competitive performance with (slightly better performance than, at least in some cases) hardware implementations of SHA-256. It is also satisfying that we have options like these that are faster than SHA-1. All that said, SHA-256 seems like a fine choice, despite its worse performance. The wide availability of reasonable-quality implementations (e.g. in Java you can use 'MessageDigest.getInstance("SHA-256")') makes it a very tempting one. Part of the reason I suggested previously that it would be helpful to try to benchmark Git with various hash functions (which didn't go over well, for some reason) is that it makes these comparisons more concrete. Without measuring, it is hard to get a sense of the distribution of input sizes and how much practical effect the differences we are talking about have. Thanks, Jonathan [1] https://eprint.iacr.org/2012/476.pdf
next prev parent reply other threads:[~2017-06-16 21:24 UTC|newest] Thread overview: 113+ messages / expand[flat|nested] mbox.gz Atom feed top 2017-03-04 1:12 Jonathan Nieder 2017-03-05 2:35 ` Linus Torvalds 2017-03-06 0:26 ` brian m. carlson 2017-03-06 18:24 ` Brandon Williams 2017-06-15 10:30 ` Which hash function to use, was " Johannes Schindelin 2017-06-15 11:05 ` Mike Hommey 2017-06-15 13:01 ` Jeff King 2017-06-15 16:30 ` Ævar Arnfjörð Bjarmason 2017-06-15 19:34 ` Johannes Schindelin 2017-06-15 21:59 ` Adam Langley 2017-06-15 22:41 ` brian m. carlson 2017-06-15 23:36 ` Ævar Arnfjörð Bjarmason 2017-06-16 0:17 ` brian m. carlson 2017-06-16 6:25 ` Ævar Arnfjörð Bjarmason 2017-06-16 13:24 ` Johannes Schindelin 2017-06-16 17:38 ` Adam Langley 2017-06-16 20:52 ` Junio C Hamano 2017-06-16 21:12 ` Junio C Hamano 2017-06-16 21:24 ` Jonathan Nieder [this message] 2017-06-16 21:39 ` Ævar Arnfjörð Bjarmason 2017-06-16 20:42 ` Jeff King 2017-06-19 9:26 ` Johannes Schindelin 2017-06-15 21:10 ` Mike Hommey 2017-06-16 4:30 ` Jeff King 2017-06-15 17:36 ` Brandon Williams 2017-06-15 19:20 ` Junio C Hamano 2017-06-15 19:13 ` Jonathan Nieder 2017-03-07 0:17 ` RFC v3: " Jonathan Nieder 2017-03-09 19:14 ` Shawn Pearce 2017-03-09 20:24 ` Jonathan Nieder 2017-03-10 19:38 ` Jeff King 2017-03-10 19:55 ` Jonathan Nieder 2017-09-28 4:43 ` [PATCH v4] technical doc: add a design doc for hash function transition Jonathan Nieder 2017-09-29 6:06 ` Junio C Hamano 2017-09-29 8:09 ` Junio C Hamano 2017-09-29 17:34 ` Jonathan Nieder 2017-10-02 8:25 ` Junio C Hamano 2017-10-02 19:41 ` Jason Cooper 2017-10-02 9:02 ` Junio C Hamano 2017-10-02 19:23 ` Jason Cooper 2017-10-03 5:40 ` Junio C Hamano 2017-10-03 13:08 ` Jason Cooper 2017-10-04 1:44 ` Junio C Hamano 2017-09-06 6:28 ` RFC v3: Another proposed hash function transition plan Junio C Hamano 2017-09-08 2:40 ` Junio C Hamano 2017-09-08 3:34 ` Jeff King 2017-09-11 18:59 ` Brandon Williams 2017-09-13 12:05 ` Johannes Schindelin 2017-09-13 13:43 ` demerphq 2017-09-13 22:51 ` Jonathan Nieder 2017-09-14 18:26 ` Johannes Schindelin 2017-09-14 18:40 ` Jonathan Nieder 2017-09-14 22:09 ` Johannes Schindelin 2017-09-13 23:30 ` Linus Torvalds 2017-09-14 18:45 ` Johannes Schindelin 2017-09-18 12:17 ` Gilles Van Assche 2017-09-18 22:16 ` Johannes Schindelin 2017-09-19 16:45 ` Gilles Van Assche 2017-09-29 13:17 ` Johannes Schindelin 2017-09-29 14:54 ` Joan Daemen 2017-09-29 22:33 ` Johannes Schindelin 2017-09-30 22:02 ` Joan Daemen 2017-10-02 14:26 ` Johannes Schindelin 2017-09-18 22:25 ` Jonathan Nieder 2017-09-26 17:05 ` Jason Cooper 2017-09-26 22:11 ` Johannes Schindelin 2017-09-26 22:25 ` [PATCH] technical doc: add a design doc for hash function transition Stefan Beller 2017-09-26 23:38 ` Jonathan Nieder 2017-09-26 23:51 ` RFC v3: Another proposed hash function transition plan Jonathan Nieder 2017-10-02 14:54 ` Jason Cooper 2017-10-02 16:50 ` Brandon Williams 2017-10-02 14:00 ` Jason Cooper 2017-10-02 17:18 ` Linus Torvalds 2017-10-02 19:37 ` Jeff King 2017-09-13 16:30 ` Jonathan Nieder 2017-09-13 21:52 ` Junio C Hamano 2017-09-13 22:07 ` Stefan Beller 2017-09-13 22:18 ` Jonathan Nieder 2017-09-14 2:13 ` Junio C Hamano 2017-09-14 15:23 ` Johannes Schindelin 2017-09-14 15:45 ` demerphq 2017-09-14 22:06 ` Johannes Schindelin 2017-09-13 22:15 ` Junio C Hamano 2017-09-13 22:27 ` Jonathan Nieder 2017-09-14 2:10 ` Junio C Hamano 2017-09-14 12:39 ` Johannes Schindelin 2017-09-14 16:36 ` Brandon Williams 2017-09-14 18:49 ` Jonathan Nieder 2017-09-15 20:42 ` Philip Oakley 2017-03-05 11:02 ` RFC: " David Lang [not found] ` <CA+dhYEXHbQfJ6KUB1tWS9u1MLEOJL81fTYkbxu4XO-i+379LPw@mail.gmail.com> 2017-03-06 9:43 ` Jeff King 2017-03-06 23:40 ` Jonathan Nieder 2017-03-07 0:03 ` Mike Hommey 2017-03-06 8:43 ` Jeff King 2017-03-06 18:39 ` Jonathan Tan 2017-03-06 19:22 ` Linus Torvalds 2017-03-06 19:59 ` Brandon Williams 2017-03-06 21:53 ` Junio C Hamano 2017-03-07 8:59 ` Jeff King 2017-03-06 18:43 ` Junio C Hamano 2017-03-07 18:57 ` Ian Jackson 2017-03-07 19:15 ` Linus Torvalds 2017-03-08 11:20 ` Ian Jackson 2017-03-08 15:37 ` Johannes Schindelin 2017-03-08 15:40 ` Johannes Schindelin 2017-03-20 5:21 ` Use base32? Jason Hennessey 2017-03-20 5:58 ` Michael Steuer 2017-03-20 8:05 ` Jacob Keller 2017-03-21 3:07 ` Michael Steuer 2017-03-13 9:24 ` RFC: Another proposed hash function transition plan The Keccak Team 2017-03-13 17:48 ` Jonathan Nieder 2017-03-13 18:34 ` ankostis 2017-03-17 11:07 ` Johannes Schindelin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style List information: http://vger.kernel.org/majordomo-info.html * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20170616212414.GC133952@aiede.mtv.corp.google.com \ --to=jrnieder@gmail.com \ --cc=Johannes.Schindelin@gmx.de \ --cc=agl@google.com \ --cc=avarab@gmail.com \ --cc=bmwill@google.com \ --cc=git@vger.kernel.org \ --cc=gitster@pobox.com \ --cc=jonathantanmy@google.com \ --cc=mh@glandium.org \ --cc=peff@peff.net \ --cc=sandals@crustytoothpaste.net \ --cc=sbeller@google.com \ --cc=torvalds@linux-foundation.org \ --subject='Re: Which hash function to use, was Re: RFC: Another proposed hash function transition plan' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
git@vger.kernel.org list mirror (unofficial, one of many) This inbox may be cloned and mirrored by anyone: git clone --mirror https://public-inbox.org/git git clone --mirror http://ou63pmih66umazou.onion/git git clone --mirror http://czquwvybam4bgbro.onion/git git clone --mirror http://hjrcffqmbrq6wope.onion/git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V1 git git/ https://public-inbox.org/git \ git@vger.kernel.org public-inbox-index git Example config snippet for mirrors. Newsgroups are available over NNTP: nntp://news.public-inbox.org/inbox.comp.version-control.git nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git nntp://news.gmane.io/gmane.comp.version-control.git note: .onion URLs require Tor: https://www.torproject.org/ code repositories for project(s) associated with this inbox: https://80x24.org/mirrors/git.git AGPL code for this site: git clone https://public-inbox.org/public-inbox.git