From mboxrd@z Thu Jan 1 00:00:00 1970
Received: from pigeon.gentoo.org ([69.77.167.62] helo=lists.gentoo.org)
by finch.gentoo.org with esmtp (Exim 4.60)
(envelope-from <gentoo-dev+bounces-34213-garchives=archives.gentoo.org@lists.gentoo.org>)
id 1LW8CB-00016Z-Bq
for garchives@archives.gentoo.org; Sun, 08 Feb 2009 11:51:31 +0000
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
by pigeon.gentoo.org (Postfix) with SMTP id 484B0E03C4;
Sun, 8 Feb 2009 11:51:29 +0000 (UTC)
Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183])
by pigeon.gentoo.org (Postfix) with ESMTP id 08873E03C4
for <gentoo-dev@lists.gentoo.org>; Sun, 8 Feb 2009 11:51:29 +0000 (UTC)
Received: from [192.168.0.100] (173-224.1-85.cust.bluewin.ch [85.1.224.173])
(using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits))
(No client certificate requested)
by smtp.gentoo.org (Postfix) with ESMTP id F0F3664DB1
for <gentoo-dev@lists.gentoo.org>; Sun, 8 Feb 2009 11:51:27 +0000 (UTC)
Subject: Re: [gentoo-dev] [RFC] DIGESTS metadata variable for cache
validation
From: Tiziano =?ISO-8859-1?Q?M=FCller?= <dev-zero@gentoo.org>
To: gentoo-dev@lists.gentoo.org
In-Reply-To: <498E9EFE.2030807@gentoo.org>
References: <498758E6.5080609@gentoo.org>
<1234045916.24784.1373.camel@localhost> <498E17E6.8060407@gentoo.org>
<1234080464.24784.2517.camel@localhost> <498E9EFE.2030807@gentoo.org>
Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="=-rh4pJE916EWHtVuRTUOt"
Organization: Gentoo
Date: Sun, 08 Feb 2009 12:51:19 +0100
Message-Id: <1234093879.24784.2819.camel@localhost>
Precedence: bulk
List-Post: <mailto:gentoo-dev@lists.gentoo.org>
List-Help: <mailto:gentoo-dev+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-dev+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-dev+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-dev.gentoo.org>
X-BeenThere: gentoo-dev@lists.gentoo.org
Reply-to: gentoo-dev@lists.gentoo.org
Mime-Version: 1.0
X-Mailer: Evolution 2.24.4
X-Archives-Salt: 8de916d4-e844-4da0-97df-b3670c79908c
X-Archives-Hash: 556234ed32fd2e46ba39700ed6e7cb0f
--=-rh4pJE916EWHtVuRTUOt
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Am Sonntag, den 08.02.2009, 00:59 -0800 schrieb Zac Medico:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>=20
> Tiziano M=C3=BCller wrote:
> > Am Samstag, den 07.02.2009, 15:23 -0800 schrieb Zac Medico:
> >> -----BEGIN PGP SIGNED MESSAGE-----
> >> Hash: SHA1
> >>
> >> Tiziano M=C3=BCller wrote:
> >>> Am Montag, den 02.02.2009, 12:34 -0800 schrieb Zac Medico:
> >>>> For the digest format, I suggest that we use the leftmost 10
> >>>> hexadecimal digits of the SHA-1 digest. The rationale for limiting
> >>>> it to 10 digits (out of 40) is to save space. Due to the avalanche
> >>>> effect [2], 10 digits should be sufficient to ensure that problems
> >>>> resulting from hash collisions are extremely unlikely.
> >>> I'd recommend to prefix the digest with a "{TYPE}" (like for hashed
> >>> passwords) to be able to change the digest algorithm as needed
> >>> (especially in regards to the current SHA successor competition).
> >>> This allows a future package manager which might use SHA-3 for hashin=
g
> >>> (once it's released) to still check old digests. Furthermore it would
> >>> allow for easier transition and only needs a definition of allowed
> >>> hashes instead of a specific one.
> >> I like that idea. That way it's not necessary to bump the EAPI in
> >> order to change the hash function. So, a typical DIGESTS value might
> >> look like this:
You still have to bump the EAPI in case you want to use a new hash not
already available now (like SHA-3). The advantage of noting the used
hash is that new PMs can handle old metadata cache.
> >>
> >> SHA1 02021be38b a28b191904 3992945426 6ec21b29a3
> >=20
> > Sleeping over it again I don't think that truncating a hash is a good
> > idea (truncating it from 40 to 10 digits makes the possibility of
> > collisions much much higher).
>=20
> The probability of collision is much higher, but it's still
> relatively small. Given the "avalanche effect" that is typical of
> cryptographic hash functions, it's extremely unlikely that collision
> will occur in such a way that it will cause a problem for cache
> validation.
The "avalanche effect" as I understood it is required for a hash
function to avoid simple calculations of collisions (what the diffusion
is for crypto algorithms). So, small changes should affect as many
numbers in the hash as possible. But you don't have only small changes
here in case somebody patches an eclass, so, the only thing which counts
is the probability of a collision.
>=20
> > But if you want to go this way, I'd say you should use something like
> > SHA1t (t for truncated) to make sure we can use full hashes once we fee=
l
> > it's appropriate.
>=20
> We could, but I think SHA1 would also be fine since one can infer
> from the length of the string that it's been truncated.
No, guessing is a bad thing here because it could be truncated because
of faulty metadata. But the main motivation is that if you write SHA1
everyone reading it expects it to be a full SHA1 hash, which it isn't.
But if your target is to reduce the size of the metadata cache, why
store the hashes of the eclasses in the ebuild's metadata and not in a
seperate dir? They have to be the same for every ebuild, don't they?
In case you have an average number of eclasses which is bigger than 4,
you can even store the full hash with less space used than with
truncated hashes for all eclasses.
--=20
=EF=BB=BF-------------------------------------------------------
Tiziano M=C3=BCller
Gentoo Linux Developer, Council Member
Areas of responsibility:
Samba, PostgreSQL, CPP, Python, sysadmin
E-Mail : dev-zero@gentoo.org
GnuPG FP : F327 283A E769 2E36 18D5 4DE2 1B05 6A63 AE9C 1E30
--=-rh4pJE916EWHtVuRTUOt
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Dies ist ein digital signierter Nachrichtenteil
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
iEYEABECAAYFAkmOxzcACgkQGwVqY66cHjA8xQCePnWiG88uOFVEzWOW4ht9QerT
TncAn2NUujQHtS1j7dZsL5mn2jknCy/I
=N1Ar
-----END PGP SIGNATURE-----
--=-rh4pJE916EWHtVuRTUOt--