From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp0 ([2001:41d0:8:6d80::]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id 2JNUIUnTX2C0gwEAgWs5BA (envelope-from ) for ; Sun, 28 Mar 2021 01:52:25 +0100 Received: from aspmx1.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp0 with LMTPS id MAYmHEnTX2BCEgAA1q6Kng (envelope-from ) for ; Sun, 28 Mar 2021 00:52:25 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 0DF182FC14 for ; Sun, 28 Mar 2021 01:52:25 +0100 (CET) Received: from localhost ([::1]:36802 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lQJfD-0006Bd-Dy for larch@yhetil.org; Sat, 27 Mar 2021 20:52:23 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:40328) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lQJeB-0006BK-VY for guix-devel@gnu.org; Sat, 27 Mar 2021 20:51:20 -0400 Received: from lepiller.eu ([2a00:5884:8208::1]:35276) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lQJe8-0002UA-Ai for guix-devel@gnu.org; Sat, 27 Mar 2021 20:51:19 -0400 Received: from lepiller.eu (localhost [127.0.0.1]) by lepiller.eu (OpenSMTPD) with ESMTP id cd9172f3; Sun, 28 Mar 2021 00:51:06 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=lepiller.eu; h=date :in-reply-to:references:mime-version:content-type :content-transfer-encoding:subject:to:from:message-id; s=dkim; bh=RHExSlk8XNcia3qeppcJo7aqtgsM6crIQCNouWimS00=; b=n9uxVFK8m7A2 zFqSyD09eq8/u5Y1/ntK3crcFVbqpa0xRudSZu7MS76MivZH6C3yePT6PQXadRj/ ivcxQMcak8huxzUA0tRdfUscP5fTI9XNKlnLnWDHkHAz9TRkE6WSqkfIcKu+sSqq 2wK6zTb27zy04Ipj6e8IYGfNJwU1Tl+sCGKxwGe65lrmpWSNVadBaWaIBC3gU438 HDYdVi4I7JuNUqro+KSTveKsl0OjVoHcFWEhSE4QfsRzhubMGAfEff6RN30dwvjJ c8M+ZoGCMVC70NTwhrA1CSeKfd+tn8V5bEaNsRlnMa+DnRnJpLS4E5Pl8MAoLtkT sgQqCe0l0w== Received: by lepiller.eu (OpenSMTPD) with ESMTPSA id 26e8ff37 (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256:NO); Sun, 28 Mar 2021 00:51:05 +0000 (UTC) Date: Sat, 27 Mar 2021 20:50:56 -0400 User-Agent: K-9 Mail for Android In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: Deep vs Shallow trace: Removing the tradeoff? To: ilmu ,"guix-devel@gnu.org" From: Julien Lepiller Message-ID: <01A29E7C-0E60-4518-A775-92B6F6A8B816@lepiller.eu> Received-SPF: pass client-ip=2a00:5884:8208::1; envelope-from=julien@lepiller.eu; helo=lepiller.eu X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guix-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-devel-bounces+larch=yhetil.org@gnu.org Sender: "Guix-devel" X-Migadu-Flow: FLOW_IN ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1616892745; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:list-id:list-help: list-unsubscribe:list-subscribe:list-post:dkim-signature; bh=RHExSlk8XNcia3qeppcJo7aqtgsM6crIQCNouWimS00=; b=sXbDB6z3o+WHkRUOR5dGLVo1WHDeGrTTSrYH3+gBt3sAuskeB3N4ijRaoJ/0Gd2NMNSwEq aHdLTDdypZLRYzO/jC9nHlEV/j9ZhbTvrdMVW4D4CrzvkGdx4YuFhiQbprG+1KOP9UxYqp 530Y3Ej4LOMvZHjL4ZOWbJIYUXr6iHDv9/suKXtPN+wSh8eyg549zNMgvgwnAFYp41XBP9 l2bRODQ+6LL4DDU2+Pta0aXRcDXfLDaxvhRC9KQ8u8ixuyh3KIUKlI7x0b2YNUdwaoVO7g 7Q6iT9dfe2M/jss8+26Xt9onqYF3WC3oWR96W9dRoK4wPUFLnXtzs41QkRgmQw== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1616892745; a=rsa-sha256; cv=none; b=eboRgtYdeMa2w2j7yTyqKVAeqkL2HvJ/ZZXQPaG7ku2140zQMT51Km2g85U1HZZprJri6E e6i6UNs2Pe39nis2eBBnKKl7wR8gyfHuBsDS3XuHy+2yUKepIITiU7+It8Fql6frPH6Dsn R0YdH6vLny8mYxGOz4enxWl6p6xmRMbG9PzjJzU7efOCaSlO4UKwUJAhCWwUYhto/VMCyr A7rpHyzGIx0jo9W/z8B8w1Y0oiDKDc8rNttVi0PN5Fcl8PrB2td8LT9phM5/YMcjQb3RRM TQVdIm6bHWLpl7aZVjocmNh4DfPHTewW+6yjbpCxdEsfjESVSNavze9mFPHGmg== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=lepiller.eu header.s=dkim header.b=n9uxVFK8; dmarc=pass (policy=none) header.from=lepiller.eu; spf=pass (aspmx1.migadu.com: domain of guix-devel-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-devel-bounces@gnu.org X-Migadu-Spam-Score: -2.12 Authentication-Results: aspmx1.migadu.com; dkim=pass header.d=lepiller.eu header.s=dkim header.b=n9uxVFK8; dmarc=pass (policy=none) header.from=lepiller.eu; spf=pass (aspmx1.migadu.com: domain of guix-devel-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-devel-bounces@gnu.org X-Migadu-Queue-Id: 0DF182FC14 X-Spam-Score: -2.12 X-Migadu-Scanner: scn0.migadu.com X-TUID: J98MR9a4yRVU Le 27 mars 2021 12:56:08 GMT-04:00, ilmu a =C3=A9crit : >Hi, > >I had this idea while reading about authenticated datastructures, I >would be very thankful if you could tell me why it doesn't work=2E > >Bear in mind the following disclaimer as you read this: > >My experience with these things is mostly theoretical, I have never >used Bazel and although I was a user of Nix and am now moving to Guix I >have not contributed to nixpkgs and only written simple expressions=2E > >Without further ado=2E > > >The premise I am assuming is the framework introduced in Build Systems >a la Carte=2E They talk about Bazel and Nix as representatives of two >different dependency tracing strategies: > >- Shallow tracing :: You hash immediate dependencies=2E >- Deep tracing :: You hash the whole transitive closure=2E > >Now the tradeoff is basically the following: > >- In Nix when you put a comment in curl you need to rebuild every >single package in nixpkgs because they more or less all depend on curl >in one way or another and therefore the curl source is in the >transitive closure for almost every package=2E >- In Bazel when you put a comment in curl then the direct dependents >need to be rebuilt but if they are the same as before after being >rebuilt then the propagation is killed and nothing else needs to >change=2E > >However, in Bazel you will need to traverse the whole dependency tree >all of the time to verify that everything is as it should be=2E What I understand from the above is that their is not so much of a differe= nce between Bazel and Nix/Guix=2E The "shallow" tracing *is* a deep tracing= =2E It just records something different=2E In Nix/Guix, we recursively compute the hash of packages from their inputs= , receipe and other stuff=2E This hash is unrelated to the checksum of the = result and changes as soon as one element changes=2E It essentially records= the whole source dependency graph=2E From=20what you write, Bazel records the checksum of inputs and receipe, so = it essentially encodes the whole binary dependency graph=2E It's not "shall= ow", as a real change down the graph can have repercussions higher up=2E Actually Eelco described something similar for Nix in his thesis, the inte= nsionnal model=2E As you noticed, different receipes or inputs can lead to = the same output (bitwise)=2E The idea is to declare the expected checksum o= f the result, and use this to compute the store item name=2E As long as you= apply changes that do not affect the output, different receipes (updates) = can be used to generate the same item=2E So if you update a package, it mig= ht affect its output checksum, so you need to change it=2E Dependents might= not be affected, in which case you can block update propagation there=2E The question being how to monitor that packages need to be rebuilt or have= the same hash?=20 > > >Now the idea I have is very simple: > >We use recursive zero knowledge proofs with shallow traces, the rzkp >caches the traversal and provides the same guarantee as the deep traces >do (transitive closure is verified to be as it should be)=2E Now if >someone puts a comment in curl there is a small amount of packages that >need to be rebuilt and then we redo only the proofs all the way up=2E >This way we save ourselves a potentially massive amount of compilation=2E I don't really understand why it must be zero-knowledge=2E My understandin= g is that to have a zero-knowledge proof, you first need a proof of the cla= im, then find a clever way to proove you have the proof, without disclosing= it=2E Not sure it's helpful here=2E If you have a proof that you don't nee= d to rebuild, why not share that proof to everyone in the first place? > >As I said before I do not have much experience with the real >implementations of these ideas so I am sure this is not as simple as it >is in my head=2E However the distri experimental operating system (which >implements a similar model to guix and nixos) does not put the hash in >the store path but rather keeps a small metadata file for each path and >then has a natural number suffix for the path of concurrent versions of >the same package=2E This gives a better UX imho and is probably also >easier to extend with more appropriate authenticated datastructures as >they are discovered=2E > > >I hope I am not a raving madman and that this actually makes at least a >slight amount of sense=2E Very much looking forward to takedowns :) > > >Kind regards, >- Ilmu