From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1 ([2001:41d0:2:bcc0::]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id ELR5HKJyX2AqzgAAgWs5BA (envelope-from ) for ; Sat, 27 Mar 2021 19:00:02 +0100 Received: from aspmx1.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1 with LMTPS id IKlSFqJyX2BfcwAAbx9fmQ (envelope-from ) for ; Sat, 27 Mar 2021 18:00:02 +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 17B0120D5B for ; Sat, 27 Mar 2021 19:00:02 +0100 (CET) Received: from localhost ([::1]:53992 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lQDE9-000535-8H for larch@yhetil.org; Sat, 27 Mar 2021 14:00:01 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:57080) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lQCEW-0004BA-0S for guix-devel@gnu.org; Sat, 27 Mar 2021 12:56:20 -0400 Received: from mail1.protonmail.ch ([185.70.40.18]:49130) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lQCET-0006Do-38 for guix-devel@gnu.org; Sat, 27 Mar 2021 12:56:19 -0400 Date: Sat, 27 Mar 2021 16:56:08 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rishi.is; s=protonmail; t=1616864173; bh=um6X8YWW/OfX9wRmYTdh1m8wp3QfQ3uJv1rD9wH39ZY=; h=Date:To:From:Reply-To:Subject:From; b=h0582YADztSz1jBXTIAc58+iBtjZHykXU4hvw5WQNFbnXTB3FCYh8HCsE43nCsUNz k2Z0q6/W2PxCPXN1Kyw6g8XlwZBeIvjiY+IVWp5wziNrA+ua/ll569FtZuHJ1ea+Hl uB/9tTsdT81rpSMIG6up2YSLmGpqSisTkAumPiO8= To: "guix-devel@gnu.org" From: ilmu Subject: Deep vs Shallow trace: Removing the tradeoff? Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Received-SPF: pass client-ip=185.70.40.18; envelope-from=ilmu@rishi.is; helo=mail1.protonmail.ch X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 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, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Sat, 27 Mar 2021 13:59:53 -0400 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: , Reply-To: ilmu 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=1616868002; h=from:from:sender:sender:reply-to: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:list-id:list-help: list-unsubscribe:list-subscribe:list-post:dkim-signature; bh=um6X8YWW/OfX9wRmYTdh1m8wp3QfQ3uJv1rD9wH39ZY=; b=EtRInaCK8AL5r1An/3gR0DBj73MmWPNjJ/Hx3hq55GQxayIaEMglCT/JqxoTHuPzdAphp+ VxIdUuufvCUEFFpU5ZJOOptPYq2iwdetuEbRmt/jqlR5k5yhvAdqylJAskiH9vJ4ci+lbg h2cAIX02oFfdrGWEzqDix8Z++9zN1GrR2v0Zau4HkbU5tvRSHqgSQIuFoo17LrdNwM7cme 7tnGvH8Z7+i7KBJEGcAmmh6SAWYNoeDut+mBT1hj4JhNFo3fqlD96D5RrHi/NpKXRKqM3P ujxzBg/1HvuqrHe1GTdUrnv43HF43aSXPSm8Y+1OEdUfjlZWde99vwY9/nfwNQ== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1616868002; a=rsa-sha256; cv=none; b=jnCw5udCubsg0ZvGYSHThwYGHALOYZcY6VXnGq1RXwX24QEXd552fwJajUlb8fSxWXacQx 87XQzkgtuSkUPOeGheCGJ8agUkoaS04X3vKQ3PKw4As2yVQ0vkveKsgGK+KYDckSQvoFGD 3sR+jNEmDslEbqdl/2h4Kl5x4l9QNZmWuiO9+hGay3t3ZGlu3p7UEgc+s4VXGG7hoUhb2k ZfF1u/CQHpVoJz6SmOQoY6H2DSAWp57fM8RukMw75hNvr7Pu/hXpcDYThPYH+06VF0eDIA SKpAeq0jYD23kucL4zMvhzcc1YFqFhgdGVrTnB7cdt8R4Xw/8l1Ab4QMGN512Q== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=rishi.is header.s=protonmail header.b=h0582YAD; dmarc=pass (policy=none) header.from=rishi.is; 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=rishi.is header.s=protonmail header.b=h0582YAD; dmarc=pass (policy=none) header.from=rishi.is; 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: 17B0120D5B X-Spam-Score: -2.12 X-Migadu-Scanner: scn0.migadu.com X-TUID: 40QIrpdsNT1x Hi, I had this idea while reading about authenticated datastructures, I would b= e very thankful if you could tell me why it doesn't work. Bear in mind the following disclaimer as you read this: My experience with these things is mostly theoretical, I have never used Ba= zel and although I was a user of Nix and am now moving to Guix I have not c= ontributed to nixpkgs and only written simple expressions. Without further ado. The premise I am assuming is the framework introduced in Build Systems a la= Carte. They talk about Bazel and Nix as representatives of two different d= ependency tracing strategies: - Shallow tracing :: You hash immediate dependencies. - Deep tracing :: You hash the whole transitive closure. Now the tradeoff is basically the following: - In Nix when you put a comment in curl you need to rebuild every single pa= ckage 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 alm= ost every package. - In Bazel when you put a comment in curl then the direct dependents need t= o be rebuilt but if they are the same as before after being rebuilt then th= e propagation is killed and nothing else needs to change. However, in Bazel you will need to traverse the whole dependency tree all o= f the time to verify that everything is as it should be. 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 (trans= itive closure is verified to be as it should be). Now if someone puts a com= ment in curl there is a small amount of packages that need to be rebuilt an= d then we redo only the proofs all the way up. This way we save ourselves a= potentially massive amount of compilation. As I said before I do not have much experience with the real implementation= s of these ideas so I am sure this is not as simple as it is in my head. Ho= wever 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 su= ffix for the path of concurrent versions of the same package. This gives a = better UX imho and is probably also easier to extend with more appropriate = authenticated datastructures as they are discovered. I hope I am not a raving madman and that this actually makes at least a sli= ght amount of sense. Very much looking forward to takedowns :) Kind regards, - Ilmu