Merge remote-tracking branch 'upstream/master' into trustless-remote-builder-simple

68 files changed, 2675 insertions, 965 deletions

diff --git a/src/libstore/binary-cache-store.cc b/src/libstore/binary-cache-store.cc
index 4f5f8607d..8fce94264 100644
--- a/src/libstore/binary-cache-store.cc
+++ b/src/libstore/binary-cache-store.cc
@@ -52,9 +52,9 @@ void BinaryCacheStore::init()
                     throw Error("binary cache '%s' is for Nix stores with prefix '%s', not '%s'",
                         getUri(), value, storeDir);
             } else if (name == "WantMassQuery") {
-                wantMassQuery.setDefault(value == "1" ? "true" : "false");
+                wantMassQuery.setDefault(value == "1");
             } else if (name == "Priority") {
-                priority.setDefault(fmt("%d", std::stoi(value)));
+                priority.setDefault(std::stoi(value));
             }
         }
     }
@@ -130,17 +130,6 @@ AutoCloseFD openFile(const Path & path)
     return fd;
 }
 
-struct FileSource : FdSource
-{
-    AutoCloseFD fd2;
-
-    FileSource(const Path & path)
-        : fd2(openFile(path))
-    {
-        fd = fd2.get();
-    }
-};
-
 ref<const ValidPathInfo> BinaryCacheStore::addToStoreCommon(
     Source & narSource, RepairFlag repair, CheckSigsFlag checkSigs,
     std::function<ValidPathInfo(HashResult)> mkInfo)
@@ -160,7 +149,7 @@ ref<const ValidPathInfo> BinaryCacheStore::addToStoreCommon(
     {
     FdSink fileSink(fdTemp.get());
     TeeSink teeSinkCompressed { fileSink, fileHashSink };
-    auto compressionSink = makeCompressionSink(compression, teeSinkCompressed);
+    auto compressionSink = makeCompressionSink(compression, teeSinkCompressed, parallelCompression, compressionLevel);
     TeeSink teeSinkUncompressed { *compressionSink, narHashSink };
     TeeSource teeSource { narSource, teeSinkUncompressed };
     narAccessor = makeNarAccessor(teeSource);
@@ -179,6 +168,9 @@ ref<const ValidPathInfo> BinaryCacheStore::addToStoreCommon(
     narInfo->url = "nar/" + narInfo->fileHash->to_string(Base32, false) + ".nar"
         + (compression == "xz" ? ".xz" :
            compression == "bzip2" ? ".bz2" :
+           compression == "zstd" ? ".zst" :
+           compression == "lzip" ? ".lzip" :
+           compression == "lz4" ? ".lz4" :
            compression == "br" ? ".br" :
            "");
 
@@ -447,18 +439,43 @@ StorePath BinaryCacheStore::addTextToStore(const string & name, const string & s
 
 std::optional<const Realisation> BinaryCacheStore::queryRealisation(const DrvOutput & id)
 {
+    if (diskCache) {
+        auto [cacheOutcome, maybeCachedRealisation] =
+            diskCache->lookupRealisation(getUri(), id);
+        switch (cacheOutcome) {
+            case NarInfoDiskCache::oValid:
+                debug("Returning a cached realisation for %s", id.to_string());
+                return *maybeCachedRealisation;
+            case NarInfoDiskCache::oInvalid:
+                debug("Returning a cached missing realisation for %s", id.to_string());
+                return {};
+            case NarInfoDiskCache::oUnknown:
+                break;
+        }
+    }
+
     auto outputInfoFilePath = realisationsPrefix + "/" + id.to_string() + ".doi";
     auto rawOutputInfo = getFile(outputInfoFilePath);
 
     if (rawOutputInfo) {
-        return {Realisation::fromJSON(
-            nlohmann::json::parse(*rawOutputInfo), outputInfoFilePath)};
+        auto realisation = Realisation::fromJSON(
+            nlohmann::json::parse(*rawOutputInfo), outputInfoFilePath);
+
+        if (diskCache)
+            diskCache->upsertRealisation(
+                getUri(), realisation);
+
+        return {realisation};
     } else {
+        if (diskCache)
+            diskCache->upsertAbsentRealisation(getUri(), id);
         return std::nullopt;
     }
 }
 
 void BinaryCacheStore::registerDrvOutput(const Realisation& info) {
+    if (diskCache)
+        diskCache->upsertRealisation(getUri(), info);
     auto filePath = realisationsPrefix + "/" + info.id.to_string() + ".doi";
     upsertFile(filePath, info.toJSON().dump(), "application/json");
 }
diff --git a/src/libstore/binary-cache-store.hh b/src/libstore/binary-cache-store.hh
index c2163166c..723f2e805 100644
--- a/src/libstore/binary-cache-store.hh
+++ b/src/libstore/binary-cache-store.hh
@@ -15,13 +15,17 @@ struct BinaryCacheStoreConfig : virtual StoreConfig
 {
     using StoreConfig::StoreConfig;
 
-    const Setting<std::string> compression{(StoreConfig*) this, "xz", "compression", "NAR compression method ('xz', 'bzip2', or 'none')"};
+    const Setting<std::string> compression{(StoreConfig*) this, "xz", "compression", "NAR compression method ('xz', 'bzip2', 'gzip', 'zstd', or 'none')"};
     const Setting<bool> writeNARListing{(StoreConfig*) this, false, "write-nar-listing", "whether to write a JSON file listing the files in each NAR"};
     const Setting<bool> writeDebugInfo{(StoreConfig*) this, false, "index-debug-info", "whether to index DWARF debug info files by build ID"};
     const Setting<Path> secretKeyFile{(StoreConfig*) this, "", "secret-key", "path to secret key used to sign the binary cache"};
     const Setting<Path> localNarCache{(StoreConfig*) this, "", "local-nar-cache", "path to a local cache of NARs"};
     const Setting<bool> parallelCompression{(StoreConfig*) this, false, "parallel-compression",
-        "enable multi-threading compression, available for xz only currently"};
+        "enable multi-threading compression for NARs, available for xz and zstd only currently"};
+    const Setting<int> compressionLevel{(StoreConfig*) this, -1, "compression-level",
+        "specify 'preset level' of compression to be used with NARs: "
+        "meaning and accepted range of values depends on compression method selected, "
+        "other than -1 which we reserve to indicate Nix defaults should be used"};
 };
 
 class BinaryCacheStore : public virtual BinaryCacheStoreConfig, public virtual Store
@@ -34,7 +38,7 @@ private:
 protected:
 
     // The prefix under which realisation infos will be stored
-    const std::string realisationsPrefix = "/realisations";
+    const std::string realisationsPrefix = "realisations";
 
     BinaryCacheStore(const Params & params);
 
diff --git a/src/libstore/build/derivation-goal.cc b/src/libstore/build/derivation-goal.cc
index c29237f5c..0907120db 100644
--- a/src/libstore/build/derivation-goal.cc
+++ b/src/libstore/build/derivation-goal.cc
@@ -20,6 +20,7 @@
 #include <sys/types.h>
 #include <sys/socket.h>
 #include <sys/un.h>
+#include <sys/wait.h>
 #include <netdb.h>
 #include <fcntl.h>
 #include <termios.h>
@@ -73,7 +74,7 @@ DerivationGoal::DerivationGoal(const StorePath & drvPath,
     state = &DerivationGoal::getDerivation;
     name = fmt(
         "building of '%s' from .drv file",
-        StorePathWithOutputs { drvPath, wantedOutputs }.to_string(worker.store));
+        DerivedPath::Built { drvPath, wantedOutputs }.to_string(worker.store));
     trace("created");
 
     mcExpectedBuilds = std::make_unique<MaintainCount<uint64_t>>(worker.expectedBuilds);
@@ -94,7 +95,7 @@ DerivationGoal::DerivationGoal(const StorePath & drvPath, const BasicDerivation
     state = &DerivationGoal::haveDerivation;
     name = fmt(
         "building of '%s' from in-memory derivation",
-        StorePathWithOutputs { drvPath, drv.outputNames() }.to_string(worker.store));
+        DerivedPath::Built { drvPath, drv.outputNames() }.to_string(worker.store));
     trace("created");
 
     mcExpectedBuilds = std::make_unique<MaintainCount<uint64_t>>(worker.expectedBuilds);
@@ -142,7 +143,6 @@ void DerivationGoal::work()
     (this->*state)();
 }
 
-
 void DerivationGoal::addWantedOutputs(const StringSet & outputs)
 {
     /* If we already want all outputs, there is nothing to do. */
@@ -165,12 +165,12 @@ void DerivationGoal::getDerivation()
     /* The first thing to do is to make sure that the derivation
        exists.  If it doesn't, it may be created through a
        substitute. */
-    if (buildMode == bmNormal && worker.store.isValidPath(drvPath)) {
+    if (buildMode == bmNormal && worker.evalStore.isValidPath(drvPath)) {
         loadDerivation();
         return;
     }
 
-    addWaitee(upcast_goal(worker.makeSubstitutionGoal(drvPath)));
+    addWaitee(upcast_goal(worker.makePathSubstitutionGoal(drvPath)));
 
     state = &DerivationGoal::loadDerivation;
 }
@@ -188,12 +188,12 @@ void DerivationGoal::loadDerivation()
     /* `drvPath' should already be a root, but let's be on the safe
        side: if the user forgot to make it a root, we wouldn't want
        things being garbage collected while we're busy. */
-    worker.store.addTempRoot(drvPath);
+    worker.evalStore.addTempRoot(drvPath);
 
-    assert(worker.store.isValidPath(drvPath));
+    assert(worker.evalStore.isValidPath(drvPath));
 
     /* Get the derivation. */
-    drv = std::make_unique<Derivation>(worker.store.derivationFromPath(drvPath));
+    drv = std::make_unique<Derivation>(worker.evalStore.derivationFromPath(drvPath));
 
     haveDerivation();
 }
@@ -212,8 +212,8 @@ void DerivationGoal::haveDerivation()
         if (i.second.second)
             worker.store.addTempRoot(*i.second.second);
 
-    auto outputHashes = staticOutputHashes(worker.store, *drv);
-    for (auto &[outputName, outputHash] : outputHashes)
+    auto outputHashes = staticOutputHashes(worker.evalStore, *drv);
+    for (auto & [outputName, outputHash] : outputHashes)
       initialOutputs.insert({
             outputName,
             InitialOutput{
@@ -246,17 +246,22 @@ void DerivationGoal::haveDerivation()
        through substitutes.  If that doesn't work, we'll build
        them. */
     if (settings.useSubstitutes && parsedDrv->substitutesAllowed())
-        for (auto & [_, status] : initialOutputs) {
+        for (auto & [outputName, status] : initialOutputs) {
             if (!status.wanted) continue;
-            if (!status.known) {
-                warn("do not know how to query for unknown floating content-addressed derivation output yet");
-                /* Nothing to wait for; tail call */
-                return DerivationGoal::gaveUpOnSubstitution();
-            }
-            addWaitee(upcast_goal(worker.makeSubstitutionGoal(
-                status.known->path,
-                buildMode == bmRepair ? Repair : NoRepair,
-                getDerivationCA(*drv))));
+            if (!status.known)
+                addWaitee(
+                    upcast_goal(
+                        worker.makeDrvOutputSubstitutionGoal(
+                            DrvOutput{status.outputHash, outputName},
+                            buildMode == bmRepair ? Repair : NoRepair
+                        )
+                    )
+                );
+            else
+                addWaitee(upcast_goal(worker.makePathSubstitutionGoal(
+                    status.known->path,
+                    buildMode == bmRepair ? Repair : NoRepair,
+                    getDerivationCA(*drv))));
         }
 
     if (waitees.empty()) /* to prevent hang (no wake-up event) */
@@ -332,12 +337,21 @@ void DerivationGoal::gaveUpOnSubstitution()
         for (auto & i : dynamic_cast<Derivation *>(drv.get())->inputDrvs)
             addWaitee(worker.makeDerivationGoal(i.first, i.second, buildMode == bmRepair ? bmRepair : bmNormal));
 
+    /* Copy the input sources from the eval store to the build
+       store. */
+    if (&worker.evalStore != &worker.store) {
+        RealisedPath::Set inputSrcs;
+        for (auto & i : drv->inputSrcs)
+            inputSrcs.insert(i);
+        copyClosure(worker.evalStore, worker.store, inputSrcs);
+    }
+
     for (auto & i : drv->inputSrcs) {
         if (worker.store.isValidPath(i)) continue;
         if (!settings.useSubstitutes)
             throw Error("dependency '%s' of '%s' does not exist, and substitution is disabled",
                 worker.store.printStorePath(i), worker.store.printStorePath(drvPath));
-        addWaitee(upcast_goal(worker.makeSubstitutionGoal(i)));
+        addWaitee(upcast_goal(worker.makePathSubstitutionGoal(i)));
     }
 
     if (waitees.empty()) /* to prevent hang (no wake-up event) */
@@ -388,7 +402,7 @@ void DerivationGoal::repairClosure()
             worker.store.printStorePath(i), worker.store.printStorePath(drvPath));
         auto drvPath2 = outputsToDrv.find(i);
         if (drvPath2 == outputsToDrv.end())
-            addWaitee(upcast_goal(worker.makeSubstitutionGoal(i, Repair)));
+            addWaitee(upcast_goal(worker.makePathSubstitutionGoal(i, Repair)));
         else
             addWaitee(worker.makeDerivationGoal(drvPath2->second, StringSet(), bmRepair));
     }
@@ -473,8 +487,8 @@ void DerivationGoal::inputsRealised()
             /* Add the relevant output closures of the input derivation
                `i' as input paths.  Only add the closures of output paths
                that are specified as inputs. */
-            assert(worker.store.isValidPath(drvPath));
-            auto outputs = worker.store.queryPartialDerivationOutputMap(depDrvPath);
+            assert(worker.evalStore.isValidPath(drvPath));
+            auto outputs = worker.evalStore.queryPartialDerivationOutputMap(depDrvPath);
             for (auto & j : wantedDepOutputs) {
                 if (outputs.count(j) > 0) {
                     auto optRealizedInput = outputs.at(j);
@@ -539,7 +553,7 @@ void DerivationGoal::tryToBuild()
     PathSet lockFiles;
     /* FIXME: Should lock something like the drv itself so we don't build same
        CA drv concurrently */
-    if (dynamic_cast<LocalStore *>(&worker.store))
+    if (dynamic_cast<LocalStore *>(&worker.store)) {
         /* If we aren't a local store, we might need to use the local store as
            a build remote, but that would cause a deadlock. */
         /* FIXME: Make it so we can use ourselves as a build remote even if we
@@ -547,9 +561,15 @@ void DerivationGoal::tryToBuild()
         /* FIXME: find some way to lock for scheduling for the other stores so
            a forking daemon with --store still won't farm out redundant builds.
            */
-        for (auto & i : drv->outputsAndOptPaths(worker.store))
+        for (auto & i : drv->outputsAndOptPaths(worker.store)) {
             if (i.second.second)
                 lockFiles.insert(worker.store.Store::toRealPath(*i.second.second));
+            else
+                lockFiles.insert(
+                    worker.store.Store::toRealPath(drvPath) + "." + i.first
+                );
+        }
+    }
 
     if (!outputLocks.lockPaths(lockFiles, "", false)) {
         if (!actLock)
@@ -733,6 +753,64 @@ void DerivationGoal::cleanupPostOutputsRegisteredModeNonCheck()
 {
 }
 
+void runPostBuildHook(
+    Store & store,
+    Logger & logger,
+    const StorePath & drvPath,
+    StorePathSet outputPaths
+)
+{
+    auto hook = settings.postBuildHook;
+    if (hook == "")
+        return;
+
+    Activity act(logger, lvlInfo, actPostBuildHook,
+            fmt("running post-build-hook '%s'", settings.postBuildHook),
+            Logger::Fields{store.printStorePath(drvPath)});
+    PushActivity pact(act.id);
+    std::map<std::string, std::string> hookEnvironment = getEnv();
+
+    hookEnvironment.emplace("DRV_PATH", store.printStorePath(drvPath));
+    hookEnvironment.emplace("OUT_PATHS", chomp(concatStringsSep(" ", store.printStorePathSet(outputPaths))));
+    hookEnvironment.emplace("NIX_CONFIG", globalConfig.toKeyValue());
+
+    struct LogSink : Sink {
+        Activity & act;
+        std::string currentLine;
+
+        LogSink(Activity & act) : act(act) { }
+
+        void operator() (std::string_view data) override {
+            for (auto c : data) {
+                if (c == '\n') {
+                    flushLine();
+                } else {
+                    currentLine += c;
+                }
+            }
+        }
+
+        void flushLine() {
+            act.result(resPostBuildLogLine, currentLine);
+            currentLine.clear();
+        }
+
+        ~LogSink() {
+            if (currentLine != "") {
+                currentLine += '\n';
+                flushLine();
+            }
+        }
+    };
+    LogSink sink(act);
+
+    runProgram2({
+        .program = settings.postBuildHook,
+        .environment = hookEnvironment,
+        .standardOut = &sink,
+        .mergeStderrToStdout = true,
+    });
+}
 
 void DerivationGoal::buildDone()
 {
@@ -798,57 +876,15 @@ void DerivationGoal::buildDone()
            being valid. */
         registerOutputs();
 
-        if (settings.postBuildHook != "") {
-            Activity act(*logger, lvlInfo, actPostBuildHook,
-                fmt("running post-build-hook '%s'", settings.postBuildHook),
-                Logger::Fields{worker.store.printStorePath(drvPath)});
-            PushActivity pact(act.id);
-            StorePathSet outputPaths;
-            for (auto i : drv->outputs) {
-                outputPaths.insert(finalOutputs.at(i.first));
-            }
-            std::map<std::string, std::string> hookEnvironment = getEnv();
-
-            hookEnvironment.emplace("DRV_PATH", worker.store.printStorePath(drvPath));
-            hookEnvironment.emplace("OUT_PATHS", chomp(concatStringsSep(" ", worker.store.printStorePathSet(outputPaths))));
-
-            RunOptions opts(settings.postBuildHook, {});
-            opts.environment = hookEnvironment;
-
-            struct LogSink : Sink {
-                Activity & act;
-                std::string currentLine;
-
-                LogSink(Activity & act) : act(act) { }
-
-                void operator() (std::string_view data) override {
-                    for (auto c : data) {
-                        if (c == '\n') {
-                            flushLine();
-                        } else {
-                            currentLine += c;
-                        }
-                    }
-                }
-
-                void flushLine() {
-                    act.result(resPostBuildLogLine, currentLine);
-                    currentLine.clear();
-                }
-
-                ~LogSink() {
-                    if (currentLine != "") {
-                        currentLine += '\n';
-                        flushLine();
-                    }
-                }
-            };
-            LogSink sink(act);
-
-            opts.standardOut = &sink;
-            opts.mergeStderrToStdout = true;
-            runProgram2(opts);
-        }
+        StorePathSet outputPaths;
+        for (auto & [_, path] : finalOutputs)
+            outputPaths.insert(path);
+        runPostBuildHook(
+            worker.store,
+            *logger,
+            drvPath,
+            outputPaths
+        );
 
         if (buildMode == bmCheck) {
             cleanupPostOutputsRegisteredModeCheck();
@@ -904,6 +940,8 @@ void DerivationGoal::resolvedFinished() {
 
     auto resolvedHashes = staticOutputHashes(worker.store, *resolvedDrv);
 
+    StorePathSet outputPaths;
+
     // `wantedOutputs` might be empty, which means “all the outputs”
     auto realWantedOutputs = wantedOutputs;
     if (realWantedOutputs.empty())
@@ -920,7 +958,11 @@ void DerivationGoal::resolvedFinished() {
         if (realisation) {
             auto newRealisation = *realisation;
             newRealisation.id = DrvOutput{initialOutputs.at(wantedOutput).outputHash, wantedOutput};
+            newRealisation.signatures.clear();
+            newRealisation.dependentRealisations = drvOutputReferences(worker.store, *drv, realisation->outPath);
+            signRealisation(newRealisation);
             worker.store.registerDrvOutput(newRealisation);
+            outputPaths.insert(realisation->outPath);
         } else {
             // If we don't have a realisation, then it must mean that something
             // failed when building the resolved drv
@@ -928,6 +970,13 @@ void DerivationGoal::resolvedFinished() {
         }
     }
 
+    runPostBuildHook(
+        worker.store,
+        *logger,
+        drvPath,
+        outputPaths
+    );
+
     // This is potentially a bit fishy in terms of error reporting. Not sure
     // how to do it in a cleaner way
     amDone(nrFailed == 0 ? ecSuccess : ecFailed, ex);
@@ -960,7 +1009,7 @@ HookReply DerivationGoal::tryBuildHook()
                     return readLine(worker.hook->fromHook.readSide.get());
                 } catch (Error & e) {
                     e.addTrace({}, "while reading the response from the build hook");
-                    throw e;
+                    throw;
                 }
             }();
             if (handleJSONLogMessage(s, worker.act, worker.hook->activities, true))
@@ -1006,7 +1055,7 @@ HookReply DerivationGoal::tryBuildHook()
         machineName = readLine(hook->fromHook.readSide.get());
     } catch (Error & e) {
         e.addTrace({}, "while reading the machine name from the build hook");
-        throw e;
+        throw;
     }
 
     /* Tell the hook all the inputs that have to be copied to the
@@ -1040,42 +1089,6 @@ HookReply DerivationGoal::tryBuildHook()
 }
 
 
-StorePathSet DerivationGoal::exportReferences(const StorePathSet & storePaths)
-{
-    StorePathSet paths;
-
-    for (auto & storePath : storePaths) {
-        if (!inputPaths.count(storePath))
-            throw BuildError("cannot export references of path '%s' because it is not in the input closure of the derivation", worker.store.printStorePath(storePath));
-
-        worker.store.computeFSClosure({storePath}, paths);
-    }
-
-    /* If there are derivations in the graph, then include their
-       outputs as well.  This is useful if you want to do things
-       like passing all build-time dependencies of some path to a
-       derivation that builds a NixOS DVD image. */
-    auto paths2 = paths;
-
-    for (auto & j : paths2) {
-        if (j.isDerivation()) {
-            Derivation drv = worker.store.derivationFromPath(j);
-            for (auto & k : drv.outputsAndOptPaths(worker.store)) {
-                if (!k.second.second)
-                    /* FIXME: I am confused why we are calling
-                       `computeFSClosure` on the output path, rather than
-                       derivation itself. That doesn't seem right to me, so I
-                       won't try to implemented this for CA derivations. */
-                    throw UnimplementedError("exportReferences on CA derivations is not yet implemented");
-                worker.store.computeFSClosure(*k.second.second, paths);
-            }
-        }
-    }
-
-    return paths;
-}
-
-
 void DerivationGoal::registerOutputs()
 {
     /* When using a build hook, the build hook can register the output
@@ -1243,9 +1256,12 @@ OutputPathMap DerivationGoal::queryDerivationOutputMap()
 void DerivationGoal::checkPathValidity()
 {
     bool checkHash = buildMode == bmRepair;
+    auto wantedOutputsLeft = wantedOutputs;
     for (auto & i : queryPartialDerivationOutputMap()) {
         InitialOutput & info = initialOutputs.at(i.first);
         info.wanted = wantOutput(i.first, wantedOutputs);
+        if (info.wanted)
+            wantedOutputsLeft.erase(i.first);
         if (i.second) {
             auto outputPath = *i.second;
             info.known = {
@@ -1258,15 +1274,33 @@ void DerivationGoal::checkPathValidity()
             };
         }
         if (settings.isExperimentalFeatureEnabled("ca-derivations")) {
-            if (auto real = worker.store.queryRealisation(
-                    DrvOutput{initialOutputs.at(i.first).outputHash, i.first})) {
+            auto drvOutput = DrvOutput{initialOutputs.at(i.first).outputHash, i.first};
+            if (auto real = worker.store.queryRealisation(drvOutput)) {
                 info.known = {
                     .path = real->outPath,
                     .status = PathStatus::Valid,
                 };
+            } else if (info.known && info.known->status == PathStatus::Valid) {
+                // We know the output because it' a static output of the
+                // derivation, and the output path is valid, but we don't have
+                // its realisation stored (probably because it has been built
+                // without the `ca-derivations` experimental flag)
+                worker.store.registerDrvOutput(
+                    Realisation{
+                        drvOutput,
+                        info.known->path,
+                    }
+                );
             }
         }
     }
+    // If we requested all the outputs via the empty set, we are always fine.
+    // If we requested specific elements, the loop above removes all the valid
+    // ones, so any that are left must be invalid.
+    if (!wantedOutputsLeft.empty())
+        throw Error("derivation '%s' does not have wanted outputs %s",
+            worker.store.printStorePath(drvPath),
+            concatStringsSep(", ", quoteStrings(wantedOutputsLeft)));
 }
 
 
diff --git a/src/libstore/build/derivation-goal.hh b/src/libstore/build/derivation-goal.hh
index c85bcd84f..704b77caf 100644
--- a/src/libstore/build/derivation-goal.hh
+++ b/src/libstore/build/derivation-goal.hh
@@ -180,6 +180,9 @@ struct DerivationGoal : public Goal
     /* Open a log file and a pipe to it. */
     Path openLogFile();
 
+    /* Sign the newly built realisation if the store allows it */
+    virtual void signRealisation(Realisation&) {}
+
     /* Close the log file. */
     void closeLogFile();
 
diff --git a/src/libstore/build/drv-output-substitution-goal.cc b/src/libstore/build/drv-output-substitution-goal.cc
new file mode 100644
index 000000000..be270d079
--- /dev/null
+++ b/src/libstore/build/drv-output-substitution-goal.cc
@@ -0,0 +1,122 @@
+#include "drv-output-substitution-goal.hh"
+#include "worker.hh"
+#include "substitution-goal.hh"
+
+namespace nix {
+
+DrvOutputSubstitutionGoal::DrvOutputSubstitutionGoal(const DrvOutput& id, Worker & worker, RepairFlag repair, std::optional<ContentAddress> ca)
+    : Goal(worker)
+    , id(id)
+{
+    state = &DrvOutputSubstitutionGoal::init;
+    name = fmt("substitution of '%s'", id.to_string());
+    trace("created");
+}
+
+
+void DrvOutputSubstitutionGoal::init()
+{
+    trace("init");
+
+    /* If the derivation already exists, we’re done */
+    if (worker.store.queryRealisation(id)) {
+        amDone(ecSuccess);
+        return;
+    }
+
+    subs = settings.useSubstitutes ? getDefaultSubstituters() : std::list<ref<Store>>();
+    tryNext();
+}
+
+void DrvOutputSubstitutionGoal::tryNext()
+{
+    trace("Trying next substituter");
+
+    if (subs.size() == 0) {
+        /* None left.  Terminate this goal and let someone else deal
+           with it. */
+        debug("drv output '%s' is required, but there is no substituter that can provide it", id.to_string());
+
+        /* Hack: don't indicate failure if there were no substituters.
+           In that case the calling derivation should just do a
+           build. */
+        amDone(substituterFailed ? ecFailed : ecNoSubstituters);
+
+        if (substituterFailed) {
+            worker.failedSubstitutions++;
+            worker.updateProgress();
+        }
+
+        return;
+    }
+
+    auto sub = subs.front();
+    subs.pop_front();
+
+    // FIXME: Make async
+    outputInfo = sub->queryRealisation(id);
+    if (!outputInfo) {
+        tryNext();
+        return;
+    }
+
+    for (const auto & [depId, depPath] : outputInfo->dependentRealisations) {
+        if (depId != id) {
+            if (auto localOutputInfo = worker.store.queryRealisation(depId);
+                localOutputInfo && localOutputInfo->outPath != depPath) {
+                warn(
+                    "substituter '%s' has an incompatible realisation for '%s', ignoring.\n"
+                    "Local:  %s\n"
+                    "Remote: %s",
+                    sub->getUri(),
+                    depId.to_string(),
+                    worker.store.printStorePath(localOutputInfo->outPath),
+                    worker.store.printStorePath(depPath)
+                );
+                tryNext();
+                return;
+            }
+            addWaitee(worker.makeDrvOutputSubstitutionGoal(depId));
+        }
+    }
+
+    addWaitee(worker.makePathSubstitutionGoal(outputInfo->outPath));
+
+    if (waitees.empty()) outPathValid();
+    else state = &DrvOutputSubstitutionGoal::outPathValid;
+}
+
+void DrvOutputSubstitutionGoal::outPathValid()
+{
+    assert(outputInfo);
+    trace("Output path substituted");
+
+    if (nrFailed > 0) {
+        debug("The output path of the derivation output '%s' could not be substituted", id.to_string());
+        amDone(nrNoSubstituters > 0 || nrIncompleteClosure > 0 ? ecIncompleteClosure : ecFailed);
+        return;
+    }
+
+    worker.store.registerDrvOutput(*outputInfo);
+    finished();
+}
+
+void DrvOutputSubstitutionGoal::finished()
+{
+    trace("finished");
+    amDone(ecSuccess);
+}
+
+string DrvOutputSubstitutionGoal::key()
+{
+    /* "a$" ensures substitution goals happen before derivation
+       goals. */
+    return "a$" + std::string(id.to_string());
+}
+
+void DrvOutputSubstitutionGoal::work()
+{
+    (this->*state)();
+}
+
+}
diff --git a/src/libstore/build/drv-output-substitution-goal.hh b/src/libstore/build/drv-output-substitution-goal.hh
new file mode 100644
index 000000000..63ab53d89
--- /dev/null
+++ b/src/libstore/build/drv-output-substitution-goal.hh
@@ -0,0 +1,50 @@
+#pragma once
+
+#include "store-api.hh"
+#include "goal.hh"
+#include "realisation.hh"
+
+namespace nix {
+
+class Worker;
+
+// Substitution of a derivation output.
+// This is done in three steps:
+// 1. Fetch the output info from a substituter
+// 2. Substitute the corresponding output path
+// 3. Register the output info
+class DrvOutputSubstitutionGoal : public Goal {
+private:
+    // The drv output we're trying to substitue
+    DrvOutput id;
+
+    // The realisation corresponding to the given output id.
+    // Will be filled once we can get it.
+    std::optional<Realisation> outputInfo;
+
+    /* The remaining substituters. */
+    std::list<ref<Store>> subs;
+
+    /* Whether a substituter failed. */
+    bool substituterFailed = false;
+
+public:
+    DrvOutputSubstitutionGoal(const DrvOutput& id, Worker & worker, RepairFlag repair = NoRepair, std::optional<ContentAddress> ca = std::nullopt);
+
+    typedef void (DrvOutputSubstitutionGoal::*GoalState)();
+    GoalState state;
+
+    void init();
+    void tryNext();
+    void outPathValid();
+    void finished();
+
+    void timedOut(Error && ex) override { abort(); };
+
+    string key() override;
+
+    void work() override;
+
+};
+
+}
diff --git a/src/libstore/build/entry-points.cc b/src/libstore/build/entry-points.cc
index 01a564aba..2b77e4354 100644
--- a/src/libstore/build/entry-points.cc
+++ b/src/libstore/build/entry-points.cc
@@ -6,16 +6,20 @@
 
 namespace nix {
 
-void Store::buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode)
+void Store::buildPaths(const std::vector<DerivedPath> & reqs, BuildMode buildMode, std::shared_ptr<Store> evalStore)
 {
-    Worker worker(*this);
+    Worker worker(*this, evalStore ? *evalStore : *this);
 
     Goals goals;
-    for (auto & path : drvPaths) {
-        if (path.path.isDerivation())
-            goals.insert(worker.makeDerivationGoal(path.path, path.outputs, buildMode));
-        else
-            goals.insert(worker.makeSubstitutionGoal(path.path, buildMode == bmRepair ? Repair : NoRepair));
+    for (const auto & br : reqs) {
+        std::visit(overloaded {
+            [&](const DerivedPath::Built & bfd) {
+                goals.insert(worker.makeDerivationGoal(bfd.drvPath, bfd.outputs, buildMode));
+            },
+            [&](const DerivedPath::Opaque & bo) {
+                goals.insert(worker.makePathSubstitutionGoal(bo.path, buildMode == bmRepair ? Repair : NoRepair));
+            },
+        }, br.raw());
     }
 
     worker.run(goals);
@@ -31,7 +35,7 @@ void Store::buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, Build
         }
         if (i->exitCode != Goal::ecSuccess) {
             if (auto i2 = dynamic_cast<DerivationGoal *>(i.get())) failed.insert(i2->drvPath);
-            else if (auto i2 = dynamic_cast<SubstitutionGoal *>(i.get())) failed.insert(i2->storePath);
+            else if (auto i2 = dynamic_cast<PathSubstitutionGoal *>(i.get())) failed.insert(i2->storePath);
         }
     }
 
@@ -47,7 +51,7 @@ void Store::buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, Build
 BuildResult Store::buildDerivation(const StorePath & drvPath, const BasicDerivation & drv,
     BuildMode buildMode)
 {
-    Worker worker(*this);
+    Worker worker(*this, *this);
     auto goal = worker.makeBasicDerivationGoal(drvPath, drv, {}, buildMode);
 
     BuildResult result;
@@ -89,8 +93,8 @@ void Store::ensurePath(const StorePath & path)
     /* If the path is already valid, we're done. */
     if (isValidPath(path)) return;
 
-    Worker worker(*this);
-    GoalPtr goal = worker.makeSubstitutionGoal(path);
+    Worker worker(*this, *this);
+    GoalPtr goal = worker.makePathSubstitutionGoal(path);
     Goals goals = {goal};
 
     worker.run(goals);
@@ -107,8 +111,8 @@ void Store::ensurePath(const StorePath & path)
 
 void LocalStore::repairPath(const StorePath & path)
 {
-    Worker worker(*this);
-    GoalPtr goal = worker.makeSubstitutionGoal(path, Repair);
+    Worker worker(*this, *this);
+    GoalPtr goal = worker.makePathSubstitutionGoal(path, Repair);
     Goals goals = {goal};
 
     worker.run(goals);
diff --git a/src/libstore/build/goal.cc b/src/libstore/build/goal.cc
index 2dd7a4d37..7c985128b 100644
--- a/src/libstore/build/goal.cc
+++ b/src/libstore/build/goal.cc
@@ -13,11 +13,9 @@ bool CompareGoalPtrs::operator() (const GoalPtr & a, const GoalPtr & b) const {
 
 void addToWeakGoals(WeakGoals & goals, GoalPtr p)
 {
-    // FIXME: necessary?
-    // FIXME: O(n)
-    for (auto & i : goals)
-        if (i.lock() == p) return;
-    goals.push_back(p);
+    if (goals.find(p) != goals.end())
+        return;
+    goals.insert(p);
 }
 
 
@@ -46,10 +44,7 @@ void Goal::waiteeDone(GoalPtr waitee, ExitCode result)
         /* If we failed and keepGoing is not set, we remove all
            remaining waitees. */
         for (auto & goal : waitees) {
-            WeakGoals waiters2;
-            for (auto & j : goal->waiters)
-                if (j.lock() != shared_from_this()) waiters2.push_back(j);
-            goal->waiters = waiters2;
+            goal->waiters.extract(shared_from_this());
         }
         waitees.clear();
 
@@ -78,6 +73,8 @@ void Goal::amDone(ExitCode result, std::optional<Error> ex)
     }
     waiters.clear();
     worker.removeGoal(shared_from_this());
+
+    cleanup();
 }
 
 
diff --git a/src/libstore/build/goal.hh b/src/libstore/build/goal.hh
index fca4f2d00..192e416d2 100644
--- a/src/libstore/build/goal.hh
+++ b/src/libstore/build/goal.hh
@@ -19,7 +19,7 @@ struct CompareGoalPtrs {
 
 /* Set of goals. */
 typedef set<GoalPtr, CompareGoalPtrs> Goals;
-typedef list<WeakGoalPtr> WeakGoals;
+typedef set<WeakGoalPtr, std::owner_less<WeakGoalPtr>> WeakGoals;
 
 /* A map of paths to goals (and the other way around). */
 typedef std::map<StorePath, WeakGoalPtr> WeakGoalMap;
@@ -100,6 +100,8 @@ struct Goal : public std::enable_shared_from_this<Goal>
     virtual string key() = 0;
 
     void amDone(ExitCode result, std::optional<Error> ex = {});
+
+    virtual void cleanup() { }
 };
 
 void addToWeakGoals(WeakGoals & goals, GoalPtr p);
diff --git a/src/libstore/build/local-derivation-goal.cc b/src/libstore/build/local-derivation-goal.cc
index 90731d98d..8d245f84a 100644
--- a/src/libstore/build/local-derivation-goal.cc
+++ b/src/libstore/build/local-derivation-goal.cc
@@ -17,16 +17,14 @@
 #include <regex>
 #include <queue>
 
-#include <sys/types.h>
-#include <sys/socket.h>
 #include <sys/un.h>
-#include <netdb.h>
 #include <fcntl.h>
 #include <termios.h>
 #include <unistd.h>
 #include <sys/mman.h>
 #include <sys/utsname.h>
 #include <sys/resource.h>
+#include <sys/socket.h>
 
 #if HAVE_STATVFS
 #include <sys/statvfs.h>
@@ -34,7 +32,6 @@
 
 /* Includes required for chroot support. */
 #if __linux__
-#include <sys/socket.h>
 #include <sys/ioctl.h>
 #include <net/if.h>
 #include <netinet/ip.h>
@@ -70,12 +67,14 @@ void handleDiffHook(
     auto diffHook = settings.diffHook;
     if (diffHook != "" && settings.runDiffHook) {
         try {
-            RunOptions diffHookOptions(diffHook,{tryA, tryB, drvPath, tmpDir});
-            diffHookOptions.searchPath = true;
-            diffHookOptions.uid = uid;
-            diffHookOptions.gid = gid;
-            diffHookOptions.chdir = "/";
-            auto diffRes = runProgram(diffHookOptions);
+            auto diffRes = runProgram(RunOptions {
+                .program = diffHook,
+                .searchPath = true,
+                .args = {tryA, tryB, drvPath, tmpDir},
+                .uid = uid,
+                .gid = gid,
+                .chdir = "/"
+            });
             if (!statusOk(diffRes.first))
                 throw ExecError(diffRes.first,
                     "diff-hook program '%1%' %2%",
@@ -153,6 +152,7 @@ void LocalDerivationGoal::killChild()
 void LocalDerivationGoal::tryLocalBuild() {
     unsigned int curBuilds = worker.getNrLocalBuilds();
     if (curBuilds >= settings.maxBuildJobs) {
+        state = &DerivationGoal::tryToBuild;
         worker.waitForBuildSlot(shared_from_this());
         outputLocks.unlock();
         return;
@@ -291,7 +291,7 @@ bool LocalDerivationGoal::cleanupDecideWhetherDiskFull()
         auto & localStore = getLocalStore();
         uint64_t required = 8ULL * 1024 * 1024; // FIXME: make configurable
         struct statvfs st;
-        if (statvfs(localStore.realStoreDir.c_str(), &st) == 0 &&
+        if (statvfs(localStore.realStoreDir.get().c_str(), &st) == 0 &&
             (uint64_t) st.f_bavail * st.f_bsize < required)
             diskFull = true;
         if (statvfs(tmpDir.c_str(), &st) == 0 &&
@@ -343,23 +343,6 @@ int childEntry(void * arg)
 }
 
 
-static std::once_flag dns_resolve_flag;
-
-static void preloadNSS() {
-    /* builtin:fetchurl can trigger a DNS lookup, which with glibc can trigger a dynamic library load of
-       one of the glibc NSS libraries in a sandboxed child, which will fail unless the library's already
-       been loaded in the parent. So we force a lookup of an invalid domain to force the NSS machinery to
-       load its lookup libraries in the parent before any child gets a chance to. */
-    std::call_once(dns_resolve_flag, []() {
-        struct addrinfo *res = NULL;
-
-        if (getaddrinfo("this.pre-initializes.the.dns.resolvers.invalid.", "http", NULL, &res) != 0) {
-            if (res) freeaddrinfo(res);
-        }
-    });
-}
-
-
 static void linkOrCopy(const Path & from, const Path & to)
 {
     if (link(from.c_str(), to.c_str()) == -1) {
@@ -388,9 +371,6 @@ void LocalDerivationGoal::startBuilder()
             settings.thisSystem,
             concatStringsSep<StringSet>(", ", worker.store.systemFeatures));
 
-    if (drv->isBuiltin())
-        preloadNSS();
-
 #if __APPLE__
     additionalSandboxProfile = parsedDrv->getStringAttr("__sandboxProfile").value_or("");
 #endif
@@ -416,7 +396,7 @@ void LocalDerivationGoal::startBuilder()
     }
 
     auto & localStore = getLocalStore();
-    if (localStore.storeDir != localStore.realStoreDir) {
+    if (localStore.storeDir != localStore.realStoreDir.get()) {
         #if __linux__
             useChroot = true;
         #else
@@ -517,7 +497,7 @@ void LocalDerivationGoal::startBuilder()
             /* Write closure info to <fileName>. */
             writeFile(tmpDir + "/" + fileName,
                 worker.store.makeValidityRegistration(
-                    exportReferences({storePath}), false, false));
+                    worker.store.exportReferences({storePath}, inputPaths), false, false));
         }
     }
 
@@ -581,7 +561,9 @@ void LocalDerivationGoal::startBuilder()
                 throw Error("derivation '%s' requested impure path '%s', but it was not in allowed-impure-host-deps",
                     worker.store.printStorePath(drvPath), i);
 
-            dirsInChroot[i] = i;
+            /* Allow files in __impureHostDeps to be missing; e.g.
+               macOS 11+ has no /usr/lib/libSystem*.dylib */
+            dirsInChroot[i] = {i, true};
         }
 
 #if __linux__
@@ -729,6 +711,7 @@ void LocalDerivationGoal::startBuilder()
     if (!builderOut.readSide)
         throw SysError("opening pseudoterminal master");
 
+    // FIXME: not thread-safe, use ptsname_r
     std::string slaveName(ptsname(builderOut.readSide.get()));
 
     if (buildUser) {
@@ -772,7 +755,6 @@ void LocalDerivationGoal::startBuilder()
     result.startTime = time(0);
 
     /* Fork a child to build the package. */
-    ProcessOptions options;
 
 #if __linux__
     if (useChroot) {
@@ -815,8 +797,6 @@ void LocalDerivationGoal::startBuilder()
 
         userNamespaceSync.create();
 
-        options.allowVfork = false;
-
         Path maxUserNamespaces = "/proc/sys/user/max_user_namespaces";
         static bool userNamespacesEnabled =
             pathExists(maxUserNamespaces)
@@ -874,7 +854,7 @@ void LocalDerivationGoal::startBuilder()
             writeFull(builderOut.writeSide.get(),
                 fmt("%d %d\n", usingUserNamespace, child));
             _exit(0);
-        }, options);
+        });
 
         int res = helper.wait();
         if (res != 0 && settings.sandboxFallback) {
@@ -938,10 +918,9 @@ void LocalDerivationGoal::startBuilder()
 #endif
     {
     fallback:
-        options.allowVfork = !buildUser && !drv->isBuiltin();
         pid = startProcess([&]() {
             runChild();
-        }, options);
+        });
     }
 
     /* parent */
@@ -956,9 +935,12 @@ void LocalDerivationGoal::startBuilder()
             try {
                 return readLine(builderOut.readSide.get());
             } catch (Error & e) {
-                e.addTrace({}, "while waiting for the build environment to initialize (previous messages: %s)",
+                auto status = pid.wait();
+                e.addTrace({}, "while waiting for the build environment for '%s' to initialize (%s, previous messages: %s)",
+                    worker.store.printStorePath(drvPath),
+                    statusToString(status),
                     concatStringsSep("|", msgs));
-                throw e;
+                throw;
             }
         }();
         if (string(msg, 0, 1) == "\2") break;
@@ -1081,115 +1063,50 @@ void LocalDerivationGoal::initEnv()
 }
 
 
-static std::regex shVarName("[A-Za-z_][A-Za-z0-9_]*");
-
-
 void LocalDerivationGoal::writeStructuredAttrs()
 {
-    auto structuredAttrs = parsedDrv->getStructuredAttrs();
-    if (!structuredAttrs) return;
-
-    auto json = *structuredAttrs;
-
-    /* Add an "outputs" object containing the output paths. */
-    nlohmann::json outputs;
-    for (auto & i : drv->outputs) {
-        /* The placeholder must have a rewrite, so we use it to cover both the
-           cases where we know or don't know the output path ahead of time. */
-        outputs[i.first] = rewriteStrings(hashPlaceholder(i.first), inputRewrites);
-    }
-    json["outputs"] = outputs;
-
-    /* Handle exportReferencesGraph. */
-    auto e = json.find("exportReferencesGraph");
-    if (e != json.end() && e->is_object()) {
-        for (auto i = e->begin(); i != e->end(); ++i) {
-            std::ostringstream str;
-            {
-                JSONPlaceholder jsonRoot(str, true);
-                StorePathSet storePaths;
-                for (auto & p : *i)
-                    storePaths.insert(worker.store.parseStorePath(p.get<std::string>()));
-                worker.store.pathInfoToJSON(jsonRoot,
-                    exportReferences(storePaths), false, true);
-            }
-            json[i.key()] = nlohmann::json::parse(str.str()); // urgh
+    if (auto structAttrsJson = parsedDrv->prepareStructuredAttrs(worker.store, inputPaths)) {
+        auto json = structAttrsJson.value();
+        nlohmann::json rewritten;
+        for (auto & [i, v] : json["outputs"].get<nlohmann::json::object_t>()) {
+            /* The placeholder must have a rewrite, so we use it to cover both the
+               cases where we know or don't know the output path ahead of time. */
+            rewritten[i] = rewriteStrings(v, inputRewrites);
         }
-    }
-
-    writeFile(tmpDir + "/.attrs.json", rewriteStrings(json.dump(), inputRewrites));
-    chownToBuilder(tmpDir + "/.attrs.json");
-
-    /* As a convenience to bash scripts, write a shell file that
-       maps all attributes that are representable in bash -
-       namely, strings, integers, nulls, Booleans, and arrays and
-       objects consisting entirely of those values. (So nested
-       arrays or objects are not supported.) */
-
-    auto handleSimpleType = [](const nlohmann::json & value) -> std::optional<std::string> {
-        if (value.is_string())
-            return shellEscape(value);
-
-        if (value.is_number()) {
-            auto f = value.get<float>();
-            if (std::ceil(f) == f)
-                return std::to_string(value.get<int>());
-        }
-
-        if (value.is_null())
-            return std::string("''");
-
-        if (value.is_boolean())
-            return value.get<bool>() ? std::string("1") : std::string("");
-
-        return {};
-    };
 
-    std::string jsonSh;
+        json["outputs"] = rewritten;
 
-    for (auto i = json.begin(); i != json.end(); ++i) {
+        auto jsonSh = writeStructuredAttrsShell(json);
 
-        if (!std::regex_match(i.key(), shVarName)) continue;
-
-        auto & value = i.value();
-
-        auto s = handleSimpleType(value);
-        if (s)
-            jsonSh += fmt("declare %s=%s\n", i.key(), *s);
-
-        else if (value.is_array()) {
-            std::string s2;
-            bool good = true;
-
-            for (auto i = value.begin(); i != value.end(); ++i) {
-                auto s3 = handleSimpleType(i.value());
-                if (!s3) { good = false; break; }
-                s2 += *s3; s2 += ' ';
-            }
-
-            if (good)
-                jsonSh += fmt("declare -a %s=(%s)\n", i.key(), s2);
-        }
+        writeFile(tmpDir + "/.attrs.sh", rewriteStrings(jsonSh, inputRewrites));
+        chownToBuilder(tmpDir + "/.attrs.sh");
+        env["NIX_ATTRS_SH_FILE"] = tmpDir + "/.attrs.sh";
+        writeFile(tmpDir + "/.attrs.json", rewriteStrings(json.dump(), inputRewrites));
+        chownToBuilder(tmpDir + "/.attrs.json");
+        env["NIX_ATTRS_JSON_FILE"] = tmpDir + "/.attrs.json";
+    }
+}
 
-        else if (value.is_object()) {
-            std::string s2;
-            bool good = true;
 
-            for (auto i = value.begin(); i != value.end(); ++i) {
-                auto s3 = handleSimpleType(i.value());
-                if (!s3) { good = false; break; }
-                s2 += fmt("[%s]=%s ", shellEscape(i.key()), *s3);
-            }
+static StorePath pathPartOfReq(const DerivedPath & req)
+{
+    return std::visit(overloaded {
+        [&](const DerivedPath::Opaque & bo) {
+            return bo.path;
+        },
+        [&](const DerivedPath::Built & bfd)  {
+            return bfd.drvPath;
+        },
+    }, req.raw());
+}
 
-            if (good)
-                jsonSh += fmt("declare -A %s=(%s)\n", i.key(), s2);
-        }
-    }
 
-    writeFile(tmpDir + "/.attrs.sh", rewriteStrings(jsonSh, inputRewrites));
-    chownToBuilder(tmpDir + "/.attrs.sh");
+bool LocalDerivationGoal::isAllowed(const DerivedPath & req)
+{
+    return this->isAllowed(pathPartOfReq(req));
 }
 
+
 struct RestrictedStoreConfig : virtual LocalFSStoreConfig
 {
     using LocalFSStoreConfig::LocalFSStoreConfig;
@@ -1310,33 +1227,54 @@ struct RestrictedStore : public virtual RestrictedStoreConfig, public virtual Lo
     std::optional<const Realisation> queryRealisation(const DrvOutput & id) override
     // XXX: This should probably be allowed if the realisation corresponds to
     // an allowed derivation
-    { throw Error("queryRealisation"); }
+    {
+        if (!goal.isAllowed(id))
+            throw InvalidPath("cannot query an unknown output id '%s' in recursive Nix", id.to_string());
+        return next->queryRealisation(id);
+    }
 
-    void buildPaths(const std::vector<StorePathWithOutputs> & paths, BuildMode buildMode) override
+    void buildPaths(const std::vector<DerivedPath> & paths, BuildMode buildMode, std::shared_ptr<Store> evalStore) override
     {
+        assert(!evalStore);
+
         if (buildMode != bmNormal) throw Error("unsupported build mode");
 
         StorePathSet newPaths;
+        std::set<Realisation> newRealisations;
 
-        for (auto & path : paths) {
-            if (!goal.isAllowed(path.path))
-                throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
+        for (auto & req : paths) {
+            if (!goal.isAllowed(req))
+                throw InvalidPath("cannot build '%s' in recursive Nix because path is unknown", req.to_string(*next));
         }
 
         next->buildPaths(paths, buildMode);
 
         for (auto & path : paths) {
-            if (!path.path.isDerivation()) continue;
-            auto outputs = next->queryDerivationOutputMap(path.path);
-            for (auto & output : outputs)
-                if (wantOutput(output.first, path.outputs))
-                    newPaths.insert(output.second);
+            auto p =  std::get_if<DerivedPath::Built>(&path);
+            if (!p) continue;
+            auto & bfd = *p;
+            auto drv = readDerivation(bfd.drvPath);
+            auto drvHashes = staticOutputHashes(*this, drv);
+            auto outputs = next->queryDerivationOutputMap(bfd.drvPath);
+            for (auto & [outputName, outputPath] : outputs)
+                if (wantOutput(outputName, bfd.outputs)) {
+                    newPaths.insert(outputPath);
+                    if (settings.isExperimentalFeatureEnabled("ca-derivations")) {
+                        auto thisRealisation = next->queryRealisation(
+                            DrvOutput{drvHashes.at(outputName), outputName}
+                        );
+                        assert(thisRealisation);
+                        newRealisations.insert(*thisRealisation);
+                    }
+                }
         }
 
         StorePathSet closure;
         next->computeFSClosure(newPaths, closure);
         for (auto & path : closure)
             goal.addDependency(path);
+        for (auto & real : Realisation::closure(*next, newRealisations))
+            goal.addedDrvOutputs.insert(real.id);
     }
 
     BuildResult buildDerivation(const StorePath & drvPath, const BasicDerivation & drv,
@@ -1358,7 +1296,7 @@ struct RestrictedStore : public virtual RestrictedStoreConfig, public virtual Lo
     void addSignatures(const StorePath & storePath, const StringSet & sigs) override
     { unsupported("addSignatures"); }
 
-    void queryMissing(const std::vector<StorePathWithOutputs> & targets,
+    void queryMissing(const std::vector<DerivedPath> & targets,
         StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
         uint64_t & downloadSize, uint64_t & narSize) override
     {
@@ -1366,12 +1304,12 @@ struct RestrictedStore : public virtual RestrictedStoreConfig, public virtual Lo
            client about what paths will be built/substituted or are
            already present. Probably not a big deal. */
 
-        std::vector<StorePathWithOutputs> allowed;
-        for (auto & path : targets) {
-            if (goal.isAllowed(path.path))
-                allowed.emplace_back(path);
+        std::vector<DerivedPath> allowed;
+        for (auto & req : targets) {
+            if (goal.isAllowed(req))
+                allowed.emplace_back(req);
             else
-                unknown.insert(path.path);
+                unknown.insert(pathPartOfReq(req));
         }
 
         next->queryMissing(allowed, willBuild, willSubstitute,
@@ -1712,7 +1650,7 @@ void LocalDerivationGoal::runChild()
                 /* N.B. it is realistic that these paths might not exist. It
                    happens when testing Nix building fixed-output derivations
                    within a pure derivation. */
-                for (auto & path : { "/etc/resolv.conf", "/etc/services", "/etc/hosts", "/var/run/nscd/socket" })
+                for (auto & path : { "/etc/resolv.conf", "/etc/services", "/etc/hosts" })
                     if (pathExists(path))
                         ss.push_back(path);
             }
@@ -1894,7 +1832,7 @@ void LocalDerivationGoal::runChild()
         /* Fill in the arguments. */
         Strings args;
 
-        const char *builder = "invalid";
+        std::string builder = "invalid";
 
         if (drv->isBuiltin()) {
             ;
@@ -2020,13 +1958,13 @@ void LocalDerivationGoal::runChild()
                 }
                 args.push_back(drv->builder);
             } else {
-                builder = drv->builder.c_str();
+                builder = drv->builder;
                 args.push_back(std::string(baseNameOf(drv->builder)));
             }
         }
 #else
         else {
-            builder = drv->builder.c_str();
+            builder = drv->builder;
             args.push_back(std::string(baseNameOf(drv->builder)));
         }
 #endif
@@ -2082,9 +2020,9 @@ void LocalDerivationGoal::runChild()
             posix_spawnattr_setbinpref_np(&attrp, 1, &cpu, NULL);
         }
 
-        posix_spawn(NULL, builder, NULL, &attrp, stringsToCharPtrs(args).data(), stringsToCharPtrs(envStrs).data());
+        posix_spawn(NULL, builder.c_str(), NULL, &attrp, stringsToCharPtrs(args).data(), stringsToCharPtrs(envStrs).data());
 #else
-        execve(builder, stringsToCharPtrs(args).data(), stringsToCharPtrs(envStrs).data());
+        execve(builder.c_str(), stringsToCharPtrs(args).data(), stringsToCharPtrs(envStrs).data());
 #endif
 
         throw SysError("executing '%1%'", drv->builder);
@@ -2199,8 +2137,7 @@ void LocalDerivationGoal::registerOutputs()
 
         /* Pass blank Sink as we are not ready to hash data at this stage. */
         NullSink blank;
-        auto references = worker.store.parseStorePathSet(
-            scanForReferences(blank, actualPath, worker.store.printStorePathSet(referenceablePaths)));
+        auto references = scanForReferences(blank, actualPath, referenceablePaths);
 
         outputReferencesIfUnregistered.insert_or_assign(
             outputName,
@@ -2214,8 +2151,8 @@ void LocalDerivationGoal::registerOutputs()
                 /* Since we'll use the already installed versions of these, we
                    can treat them as leaves and ignore any references they
                    have. */
-                [&](AlreadyRegistered _) { return StringSet {}; },
-                [&](PerhapsNeedToRegister refs) {
+                [&](const AlreadyRegistered &) { return StringSet {}; },
+                [&](const PerhapsNeedToRegister & refs) {
                     StringSet referencedOutputs;
                     /* FIXME build inverted map up front so no quadratic waste here */
                     for (auto & r : refs.refs)
@@ -2251,11 +2188,11 @@ void LocalDerivationGoal::registerOutputs()
         };
 
         std::optional<StorePathSet> referencesOpt = std::visit(overloaded {
-            [&](AlreadyRegistered skippedFinalPath) -> std::optional<StorePathSet> {
+            [&](const AlreadyRegistered & skippedFinalPath) -> std::optional<StorePathSet> {
                 finish(skippedFinalPath.path);
                 return std::nullopt;
             },
-            [&](PerhapsNeedToRegister r) -> std::optional<StorePathSet> {
+            [&](const PerhapsNeedToRegister & r) -> std::optional<StorePathSet> {
                 return r.refs;
             },
         }, outputReferencesIfUnregistered.at(outputName));
@@ -2267,7 +2204,7 @@ void LocalDerivationGoal::registerOutputs()
         auto rewriteOutput = [&]() {
             /* Apply hash rewriting if necessary. */
             if (!outputRewrites.empty()) {
-                warn("rewriting hashes in '%1%'; cross fingers", actualPath);
+                debug("rewriting hashes in '%1%'; cross fingers", actualPath);
 
                 /* FIXME: this is in-memory. */
                 StringSink sink;
@@ -2276,10 +2213,6 @@ void LocalDerivationGoal::registerOutputs()
                 sink.s = make_ref<std::string>(rewriteStrings(*sink.s, outputRewrites));
                 StringSource source(*sink.s);
                 restorePath(actualPath, source);
-
-                /* FIXME: set proper permissions in restorePath() so
-                   we don't have to do another traversal. */
-                canonicalisePathMetaData(actualPath, -1, inodesSeen);
             }
         };
 
@@ -2333,32 +2266,19 @@ void LocalDerivationGoal::registerOutputs()
             }
             auto got = caSink.finish().first;
             auto refs = rewriteRefs();
-            HashModuloSink narSink { htSHA256, oldHashPart };
-            dumpPath(actualPath, narSink);
-            auto narHashAndSize = narSink.finish();
-            ValidPathInfo newInfo0 {
-                worker.store.makeFixedOutputPath(
+
+            auto finalPath = worker.store.makeFixedOutputPath(
                     outputHash.method,
                     got,
                     outputPathName(drv->name, outputName),
                     refs.second,
-                    refs.first),
-                narHashAndSize.first,
-            };
-            newInfo0.narSize = narHashAndSize.second;
-            newInfo0.ca = FixedOutputHash {
-                .method = outputHash.method,
-                .hash = got,
-            };
-            newInfo0.references = refs.second;
-            if (refs.first)
-                newInfo0.references.insert(newInfo0.path);
-            if (scratchPath != newInfo0.path) {
+                    refs.first);
+            if (scratchPath != finalPath) {
                 // Also rewrite the output path
                 auto source = sinkToSource([&](Sink & nextSink) {
                     StringSink sink;
                     dumpPath(actualPath, sink);
-                    RewritingSink rsink2(oldHashPart, std::string(newInfo0.path.hashPart()), nextSink);
+                    RewritingSink rsink2(oldHashPart, std::string(finalPath.hashPart()), nextSink);
                     rsink2(*sink.s);
                     rsink2.flush();
                 });
@@ -2368,12 +2288,27 @@ void LocalDerivationGoal::registerOutputs()
                 movePath(tmpPath, actualPath);
             }
 
+            HashResult narHashAndSize = hashPath(htSHA256, actualPath);
+            ValidPathInfo newInfo0 {
+                finalPath,
+                narHashAndSize.first,
+            };
+
+            newInfo0.narSize = narHashAndSize.second;
+            newInfo0.ca = FixedOutputHash {
+                .method = outputHash.method,
+                .hash = got,
+            };
+            newInfo0.references = refs.second;
+            if (refs.first)
+                newInfo0.references.insert(newInfo0.path);
+
             assert(newInfo0.ca);
             return newInfo0;
         };
 
         ValidPathInfo newInfo = std::visit(overloaded {
-            [&](DerivationOutputInputAddressed output) {
+            [&](const DerivationOutputInputAddressed & output) {
                 /* input-addressed case */
                 auto requiredFinalPath = output.path;
                 /* Preemptively add rewrite rule for final hash, as that is
@@ -2392,14 +2327,14 @@ void LocalDerivationGoal::registerOutputs()
                     newInfo0.references.insert(newInfo0.path);
                 return newInfo0;
             },
-            [&](DerivationOutputCAFixed dof) {
+            [&](const DerivationOutputCAFixed & dof) {
                 auto newInfo0 = newInfoFromCA(DerivationOutputCAFloating {
                     .method = dof.hash.method,
                     .hashType = dof.hash.hash.type,
                 });
 
                 /* Check wanted hash */
-                Hash & wanted = dof.hash.hash;
+                const Hash & wanted = dof.hash.hash;
                 assert(newInfo0.ca);
                 auto got = getContentAddressHash(*newInfo0.ca);
                 if (wanted != got) {
@@ -2428,6 +2363,10 @@ void LocalDerivationGoal::registerOutputs()
             },
         }, output.output);
 
+        /* FIXME: set proper permissions in restorePath() so
+            we don't have to do another traversal. */
+        canonicalisePathMetaData(actualPath, -1, inodesSeen);
+
         /* Calculate where we'll move the output files. In the checking case we
            will leave leave them where they are, for now, rather than move to
            their usual "final destination" */
@@ -2437,6 +2376,7 @@ void LocalDerivationGoal::registerOutputs()
            floating CA derivations and hash-mismatching fixed-output
            derivations. */
         PathLocks dynamicOutputLock;
+        dynamicOutputLock.setDeletion(true);
         auto optFixedPath = output.path(worker.store, drv->name, outputName);
         if (!optFixedPath ||
             worker.store.printStorePath(*optFixedPath) != finalDestPath)
@@ -2460,6 +2400,7 @@ void LocalDerivationGoal::registerOutputs()
                 assert(newInfo.ca);
             } else {
                 auto destPath = worker.store.toRealPath(finalDestPath);
+                deletePath(destPath);
                 movePath(actualPath, destPath);
                 actualPath = destPath;
             }
@@ -2529,7 +2470,13 @@ void LocalDerivationGoal::registerOutputs()
         infos.emplace(outputName, std::move(newInfo));
     }
 
-    if (buildMode == bmCheck) return;
+    if (buildMode == bmCheck) {
+        // In case of FOD mismatches on `--check` an error must be thrown as this is also
+        // a source for non-determinism.
+        if (delayedException)
+            std::rethrow_exception(delayedException);
+        return;
+    }
 
     /* Apply output checks. */
     checkOutputs(infos);
@@ -2615,13 +2562,22 @@ void LocalDerivationGoal::registerOutputs()
        but it's fine to do in all cases. */
 
     if (settings.isExperimentalFeatureEnabled("ca-derivations")) {
-        for (auto& [outputName, newInfo] : infos)
-            worker.store.registerDrvOutput(Realisation{
-                .id = DrvOutput{initialOutputs.at(outputName).outputHash, outputName},
-                .outPath = newInfo.path});
+        for (auto& [outputName, newInfo] : infos) {
+            auto thisRealisation = Realisation{
+                .id = DrvOutput{initialOutputs.at(outputName).outputHash,
+                                outputName},
+                .outPath = newInfo.path};
+            signRealisation(thisRealisation);
+            worker.store.registerDrvOutput(thisRealisation);
+        }
     }
 }
 
+void LocalDerivationGoal::signRealisation(Realisation & realisation)
+{
+    getLocalStore().signRealisation(realisation);
+}
+
 
 void LocalDerivationGoal::checkOutputs(const std::map<Path, ValidPathInfo> & outputs)
 {
diff --git a/src/libstore/build/local-derivation-goal.hh b/src/libstore/build/local-derivation-goal.hh
index 4bbf27a1b..088a57209 100644
--- a/src/libstore/build/local-derivation-goal.hh
+++ b/src/libstore/build/local-derivation-goal.hh
@@ -108,6 +108,9 @@ struct LocalDerivationGoal : public DerivationGoal
     /* Paths that were added via recursive Nix calls. */
     StorePathSet addedPaths;
 
+    /* Realisations that were added via recursive Nix calls. */
+    std::set<DrvOutput> addedDrvOutputs;
+
     /* Recursive Nix calls are only allowed to build or realize paths
        in the original input closure or added via a recursive Nix call
        (so e.g. you can't do 'nix-store -r /nix/store/<bla>' where
@@ -116,6 +119,12 @@ struct LocalDerivationGoal : public DerivationGoal
     {
         return inputPaths.count(path) || addedPaths.count(path);
     }
+    bool isAllowed(const DrvOutput & id)
+    {
+        return addedDrvOutputs.count(id);
+    }
+
+    bool isAllowed(const DerivedPath & req);
 
     friend struct RestrictedStore;
 
@@ -161,6 +170,8 @@ struct LocalDerivationGoal : public DerivationGoal
        as valid. */
     void registerOutputs() override;
 
+    void signRealisation(Realisation &) override;
+
     /* Check that an output meets the requirements specified by the
        'outputChecks' attribute (or the legacy
        '{allowed,disallowed}{References,Requisites}' attributes). */
diff --git a/src/libstore/build/substitution-goal.cc b/src/libstore/build/substitution-goal.cc
index c4b0de78d..29a8cfb87 100644
--- a/src/libstore/build/substitution-goal.cc
+++ b/src/libstore/build/substitution-goal.cc
@@ -5,40 +5,32 @@
 
 namespace nix {
 
-SubstitutionGoal::SubstitutionGoal(const StorePath & storePath, Worker & worker, RepairFlag repair, std::optional<ContentAddress> ca)
+PathSubstitutionGoal::PathSubstitutionGoal(const StorePath & storePath, Worker & worker, RepairFlag repair, std::optional<ContentAddress> ca)
     : Goal(worker)
     , storePath(storePath)
     , repair(repair)
     , ca(ca)
 {
-    state = &SubstitutionGoal::init;
+    state = &PathSubstitutionGoal::init;
     name = fmt("substitution of '%s'", worker.store.printStorePath(this->storePath));
     trace("created");
     maintainExpectedSubstitutions = std::make_unique<MaintainCount<uint64_t>>(worker.expectedSubstitutions);
 }
 
 
-SubstitutionGoal::~SubstitutionGoal()
+PathSubstitutionGoal::~PathSubstitutionGoal()
 {
-    try {
-        if (thr.joinable()) {
-            // FIXME: signal worker thread to quit.
-            thr.join();
-            worker.childTerminated(this);
-        }
-    } catch (...) {
-        ignoreException();
-    }
+    cleanup();
 }
 
 
-void SubstitutionGoal::work()
+void PathSubstitutionGoal::work()
 {
     (this->*state)();
 }
 
 
-void SubstitutionGoal::init()
+void PathSubstitutionGoal::init()
 {
     trace("init");
 
@@ -59,10 +51,12 @@ void SubstitutionGoal::init()
 }
 
 
-void SubstitutionGoal::tryNext()
+void PathSubstitutionGoal::tryNext()
 {
     trace("trying next substituter");
 
+    cleanup();
+
     if (subs.size() == 0) {
         /* None left.  Terminate this goal and let someone else deal
            with it. */
@@ -142,7 +136,7 @@ void SubstitutionGoal::tryNext()
     /* Bail out early if this substituter lacks a valid
        signature. LocalStore::addToStore() also checks for this, but
        only after we've downloaded the path. */
-    if (!sub->isTrusted && worker.store.pathInfoIsTrusted(*info))
+    if (!sub->isTrusted && worker.store.pathInfoIsUntrusted(*info))
     {
         warn("substituter '%s' does not have a valid signature for path '%s'",
             sub->getUri(), worker.store.printStorePath(storePath));
@@ -154,16 +148,16 @@ void SubstitutionGoal::tryNext()
        paths referenced by this one. */
     for (auto & i : info->references)
         if (i != storePath) /* ignore self-references */
-            addWaitee(worker.makeSubstitutionGoal(i));
+            addWaitee(worker.makePathSubstitutionGoal(i));
 
     if (waitees.empty()) /* to prevent hang (no wake-up event) */
         referencesValid();
     else
-        state = &SubstitutionGoal::referencesValid;
+        state = &PathSubstitutionGoal::referencesValid;
 }
 
 
-void SubstitutionGoal::referencesValid()
+void PathSubstitutionGoal::referencesValid()
 {
     trace("all references realised");
 
@@ -177,12 +171,12 @@ void SubstitutionGoal::referencesValid()
         if (i != storePath) /* ignore self-references */
             assert(worker.store.isValidPath(i));
 
-    state = &SubstitutionGoal::tryToRun;
+    state = &PathSubstitutionGoal::tryToRun;
     worker.wakeUp(shared_from_this());
 }
 
 
-void SubstitutionGoal::tryToRun()
+void PathSubstitutionGoal::tryToRun()
 {
     trace("trying to run");
 
@@ -205,12 +199,12 @@ void SubstitutionGoal::tryToRun()
     thr = std::thread([this]() {
         try {
             /* Wake up the worker loop when we're done. */
-            Finally updateStats([this]() { outPipe.writeSide = -1; });
+            Finally updateStats([this]() { outPipe.writeSide.close(); });
 
             Activity act(*logger, actSubstitute, Logger::Fields{worker.store.printStorePath(storePath), sub->getUri()});
             PushActivity pact(act.id);
 
-            copyStorePath(ref<Store>(sub), ref<Store>(worker.store.shared_from_this()),
+            copyStorePath(*sub, worker.store,
                 subPath ? *subPath : storePath, repair, sub->isTrusted ? NoCheckSigs : CheckSigs);
 
             promise.set_value();
@@ -221,11 +215,11 @@ void SubstitutionGoal::tryToRun()
 
     worker.childStarted(shared_from_this(), {outPipe.readSide.get()}, true, false);
 
-    state = &SubstitutionGoal::finished;
+    state = &PathSubstitutionGoal::finished;
 }
 
 
-void SubstitutionGoal::finished()
+void PathSubstitutionGoal::finished()
 {
     trace("substitute finished");
 
@@ -249,7 +243,7 @@ void SubstitutionGoal::finished()
         }
 
         /* Try the next substitute. */
-        state = &SubstitutionGoal::tryNext;
+        state = &PathSubstitutionGoal::tryNext;
         worker.wakeUp(shared_from_this());
         return;
     }
@@ -278,14 +272,31 @@ void SubstitutionGoal::finished()
 }
 
 
-void SubstitutionGoal::handleChildOutput(int fd, const string & data)
+void PathSubstitutionGoal::handleChildOutput(int fd, const string & data)
 {
 }
 
 
-void SubstitutionGoal::handleEOF(int fd)
+void PathSubstitutionGoal::handleEOF(int fd)
 {
     if (fd == outPipe.readSide.get()) worker.wakeUp(shared_from_this());
 }
 
+
+void PathSubstitutionGoal::cleanup()
+{
+    try {
+        if (thr.joinable()) {
+            // FIXME: signal worker thread to quit.
+            thr.join();
+            worker.childTerminated(this);
+        }
+
+        outPipe.close();
+    } catch (...) {
+        ignoreException();
+    }
+}
+
+
 }
diff --git a/src/libstore/build/substitution-goal.hh b/src/libstore/build/substitution-goal.hh
index dee2cecbf..70c806d23 100644
--- a/src/libstore/build/substitution-goal.hh
+++ b/src/libstore/build/substitution-goal.hh
@@ -8,13 +8,13 @@ namespace nix {
 
 class Worker;
 
-struct SubstitutionGoal : public Goal
+struct PathSubstitutionGoal : public Goal
 {
     /* The store path that should be realised through a substitute. */
     StorePath storePath;
 
     /* The path the substituter refers to the path as. This will be
-     * different when the stores have different names. */
+       different when the stores have different names. */
     std::optional<StorePath> subPath;
 
     /* The remaining substituters. */
@@ -47,14 +47,15 @@ struct SubstitutionGoal : public Goal
     std::unique_ptr<MaintainCount<uint64_t>> maintainExpectedSubstitutions,
         maintainRunningSubstitutions, maintainExpectedNar, maintainExpectedDownload;
 
-    typedef void (SubstitutionGoal::*GoalState)();
+    typedef void (PathSubstitutionGoal::*GoalState)();
     GoalState state;
 
     /* Content address for recomputing store path */
     std::optional<ContentAddress> ca;
 
-    SubstitutionGoal(const StorePath & storePath, Worker & worker, RepairFlag repair = NoRepair, std::optional<ContentAddress> ca = std::nullopt);
-    ~SubstitutionGoal();
+public:
+    PathSubstitutionGoal(const StorePath & storePath, Worker & worker, RepairFlag repair = NoRepair, std::optional<ContentAddress> ca = std::nullopt);
+    ~PathSubstitutionGoal();
 
     void timedOut(Error && ex) override { abort(); };
 
@@ -78,6 +79,8 @@ struct SubstitutionGoal : public Goal
     /* Callback used by the worker to write to the log. */
     void handleChildOutput(int fd, const string & data) override;
     void handleEOF(int fd) override;
+
+    void cleanup() override;
 };
 
 }
diff --git a/src/libstore/build/worker.cc b/src/libstore/build/worker.cc
index b2223c3b6..55afb5cca 100644
--- a/src/libstore/build/worker.cc
+++ b/src/libstore/build/worker.cc
@@ -1,6 +1,7 @@
 #include "machines.hh"
 #include "worker.hh"
 #include "substitution-goal.hh"
+#include "drv-output-substitution-goal.hh"
 #include "local-derivation-goal.hh"
 #include "hook-instance.hh"
 
@@ -8,11 +9,12 @@
 
 namespace nix {
 
-Worker::Worker(Store & store)
+Worker::Worker(Store & store, Store & evalStore)
     : act(*logger, actRealise)
     , actDerivations(*logger, actBuilds)
     , actSubstitutions(*logger, actCopyPaths)
     , store(store)
+    , evalStore(evalStore)
 {
     /* Debugging: prevent recursive workers. */
     nrLocalBuilds = 0;
@@ -78,20 +80,32 @@ std::shared_ptr<DerivationGoal> Worker::makeBasicDerivationGoal(const StorePath
 }
 
 
-std::shared_ptr<SubstitutionGoal> Worker::makeSubstitutionGoal(const StorePath & path, RepairFlag repair, std::optional<ContentAddress> ca)
+std::shared_ptr<PathSubstitutionGoal> Worker::makePathSubstitutionGoal(const StorePath & path, RepairFlag repair, std::optional<ContentAddress> ca)
 {
-    std::weak_ptr<SubstitutionGoal> & goal_weak = substitutionGoals[path];
+    std::weak_ptr<PathSubstitutionGoal> & goal_weak = substitutionGoals[path];
     auto goal = goal_weak.lock(); // FIXME
     if (!goal) {
-        goal = std::make_shared<SubstitutionGoal>(path, *this, repair, ca);
+        goal = std::make_shared<PathSubstitutionGoal>(path, *this, repair, ca);
         goal_weak = goal;
         wakeUp(goal);
     }
     return goal;
 }
 
-template<typename G>
-static void removeGoal(std::shared_ptr<G> goal, std::map<StorePath, std::weak_ptr<G>> & goalMap)
+std::shared_ptr<DrvOutputSubstitutionGoal> Worker::makeDrvOutputSubstitutionGoal(const DrvOutput& id, RepairFlag repair, std::optional<ContentAddress> ca)
+{
+    std::weak_ptr<DrvOutputSubstitutionGoal> & goal_weak = drvOutputSubstitutionGoals[id];
+    auto goal = goal_weak.lock(); // FIXME
+    if (!goal) {
+        goal = std::make_shared<DrvOutputSubstitutionGoal>(id, *this, repair, ca);
+        goal_weak = goal;
+        wakeUp(goal);
+    }
+    return goal;
+}
+
+template<typename K, typename G>
+static void removeGoal(std::shared_ptr<G> goal, std::map<K, std::weak_ptr<G>> & goalMap)
 {
     /* !!! inefficient */
     for (auto i = goalMap.begin();
@@ -109,10 +123,13 @@ void Worker::removeGoal(GoalPtr goal)
 {
     if (auto drvGoal = std::dynamic_pointer_cast<DerivationGoal>(goal))
         nix::removeGoal(drvGoal, derivationGoals);
-    else if (auto subGoal = std::dynamic_pointer_cast<SubstitutionGoal>(goal))
+    else if (auto subGoal = std::dynamic_pointer_cast<PathSubstitutionGoal>(goal))
         nix::removeGoal(subGoal, substitutionGoals);
+    else if (auto subGoal = std::dynamic_pointer_cast<DrvOutputSubstitutionGoal>(goal))
+        nix::removeGoal(subGoal, drvOutputSubstitutionGoals);
     else
         assert(false);
+
     if (topGoals.find(goal) != topGoals.end()) {
         topGoals.erase(goal);
         /* If a top-level goal failed, then kill all other goals
@@ -211,18 +228,18 @@ void Worker::waitForAWhile(GoalPtr goal)
 
 void Worker::run(const Goals & _topGoals)
 {
-    std::vector<nix::StorePathWithOutputs> topPaths;
+    std::vector<nix::DerivedPath> topPaths;
 
     for (auto & i : _topGoals) {
         topGoals.insert(i);
         if (auto goal = dynamic_cast<DerivationGoal *>(i.get())) {
-            topPaths.push_back({goal->drvPath, goal->wantedOutputs});
-        } else if (auto goal = dynamic_cast<SubstitutionGoal *>(i.get())) {
-            topPaths.push_back({goal->storePath});
+            topPaths.push_back(DerivedPath::Built{goal->drvPath, goal->wantedOutputs});
+        } else if (auto goal = dynamic_cast<PathSubstitutionGoal *>(i.get())) {
+            topPaths.push_back(DerivedPath::Opaque{goal->storePath});
         }
     }
 
-    /* Call queryMissing() efficiently query substitutes. */
+    /* Call queryMissing() to efficiently query substitutes. */
     StorePathSet willBuild, willSubstitute, unknown;
     uint64_t downloadSize, narSize;
     store.queryMissing(topPaths, willBuild, willSubstitute, unknown, downloadSize, narSize);
@@ -471,7 +488,10 @@ void Worker::markContentsGood(const StorePath & path)
 }
 
 
-GoalPtr upcast_goal(std::shared_ptr<SubstitutionGoal> subGoal) {
+GoalPtr upcast_goal(std::shared_ptr<PathSubstitutionGoal> subGoal) {
+    return subGoal;
+}
+GoalPtr upcast_goal(std::shared_ptr<DrvOutputSubstitutionGoal> subGoal) {
     return subGoal;
 }
 
diff --git a/src/libstore/build/worker.hh b/src/libstore/build/worker.hh
index 82e711191..6a3b99c02 100644
--- a/src/libstore/build/worker.hh
+++ b/src/libstore/build/worker.hh
@@ -4,6 +4,7 @@
 #include "lock.hh"
 #include "store-api.hh"
 #include "goal.hh"
+#include "realisation.hh"
 
 #include <future>
 #include <thread>
@@ -12,18 +13,20 @@ namespace nix {
 
 /* Forward definition. */
 struct DerivationGoal;
-struct SubstitutionGoal;
+struct PathSubstitutionGoal;
+class DrvOutputSubstitutionGoal;
 
 /* Workaround for not being able to declare a something like
 
-     class SubstitutionGoal : public Goal;
+     class PathSubstitutionGoal : public Goal;
 
    even when Goal is a complete type.
 
    This is still a static cast. The purpose of exporting it is to define it in
-   a place where `SubstitutionGoal` is concrete, and use it in a place where it
+   a place where `PathSubstitutionGoal` is concrete, and use it in a place where it
    is opaque. */
-GoalPtr upcast_goal(std::shared_ptr<SubstitutionGoal> subGoal);
+GoalPtr upcast_goal(std::shared_ptr<PathSubstitutionGoal> subGoal);
+GoalPtr upcast_goal(std::shared_ptr<DrvOutputSubstitutionGoal> subGoal);
 
 typedef std::chrono::time_point<std::chrono::steady_clock> steady_time_point;
 
@@ -72,7 +75,8 @@ private:
     /* Maps used to prevent multiple instantiations of a goal for the
        same derivation / path. */
     std::map<StorePath, std::weak_ptr<DerivationGoal>> derivationGoals;
-    std::map<StorePath, std::weak_ptr<SubstitutionGoal>> substitutionGoals;
+    std::map<StorePath, std::weak_ptr<PathSubstitutionGoal>> substitutionGoals;
+    std::map<DrvOutput, std::weak_ptr<DrvOutputSubstitutionGoal>> drvOutputSubstitutionGoals;
 
     /* Goals waiting for busy paths to be unlocked. */
     WeakGoals waitingForAnyGoal;
@@ -106,6 +110,7 @@ public:
     bool checkMismatch;
 
     Store & store;
+    Store & evalStore;
 
     std::unique_ptr<HookInstance> hook;
 
@@ -127,7 +132,7 @@ public:
        it answers with "decline-permanently", we don't try again. */
     bool tryBuildHook = true;
 
-    Worker(Store & store);
+    Worker(Store & store, Store & evalStore);
     ~Worker();
 
     /* Make a goal (with caching). */
@@ -146,7 +151,8 @@ public:
         const StringSet & wantedOutputs, BuildMode buildMode = bmNormal);
 
     /* substitution goal */
-    std::shared_ptr<SubstitutionGoal> makeSubstitutionGoal(const StorePath & storePath, RepairFlag repair = NoRepair, std::optional<ContentAddress> ca = std::nullopt);
+    std::shared_ptr<PathSubstitutionGoal> makePathSubstitutionGoal(const StorePath & storePath, RepairFlag repair = NoRepair, std::optional<ContentAddress> ca = std::nullopt);
+    std::shared_ptr<DrvOutputSubstitutionGoal> makeDrvOutputSubstitutionGoal(const DrvOutput & id, RepairFlag repair = NoRepair, std::optional<ContentAddress> ca = std::nullopt);
 
     /* Remove a dead goal. */
     void removeGoal(GoalPtr goal);
diff --git a/src/libstore/ca-specific-schema.sql b/src/libstore/ca-specific-schema.sql
index 93c442826..08af0cc1f 100644
--- a/src/libstore/ca-specific-schema.sql
+++ b/src/libstore/ca-specific-schema.sql
@@ -3,9 +3,19 @@
 -- is enabled
 
 create table if not exists Realisations (
+    id integer primary key autoincrement not null,
     drvPath text not null,
     outputName text not null, -- symbolic output id, usually "out"
     outputPath integer not null,
-    primary key (drvPath, outputName),
+    signatures text, -- space-separated list
     foreign key (outputPath) references ValidPaths(id) on delete cascade
 );
+
+create index if not exists IndexRealisations on Realisations(drvPath, outputName);
+
+create table if not exists RealisationsRefs (
+    referrer integer not null,
+    realisationReference integer,
+    foreign key (referrer) references Realisations(id) on delete cascade,
+    foreign key (realisationReference) references Realisations(id) on delete restrict
+);
diff --git a/src/libstore/content-address.cc b/src/libstore/content-address.cc
index 90a3ad1f5..974d1c471 100644
--- a/src/libstore/content-address.cc
+++ b/src/libstore/content-address.cc
@@ -31,10 +31,10 @@ std::string makeFixedOutputCA(FileIngestionMethod method, const Hash & hash)
 std::string renderContentAddress(ContentAddress ca)
 {
     return std::visit(overloaded {
-        [](TextHash th) {
+        [](TextHash & th) {
             return "text:" + th.hash.to_string(Base32, true);
         },
-        [](FixedOutputHash fsh) {
+        [](FixedOutputHash & fsh) {
             return makeFixedOutputCA(fsh.method, fsh.hash);
         }
     }, ca);
@@ -43,10 +43,10 @@ std::string renderContentAddress(ContentAddress ca)
 std::string renderContentAddressMethod(ContentAddressMethod cam)
 {
     return std::visit(overloaded {
-        [](TextHashMethod &th) {
+        [](TextHashMethod & th) {
             return std::string{"text:"} + printHashType(htSHA256);
         },
-        [](FixedOutputHashMethod &fshm) {
+        [](FixedOutputHashMethod & fshm) {
             return "fixed:" + makeFileIngestionPrefix(fshm.fileIngestionMethod) + printHashType(fshm.hashType);
         }
     }, cam);
@@ -104,12 +104,12 @@ ContentAddress parseContentAddress(std::string_view rawCa) {
 
     return std::visit(
         overloaded {
-            [&](TextHashMethod thm) {
+            [&](TextHashMethod & thm) {
                 return ContentAddress(TextHash {
                     .hash = Hash::parseNonSRIUnprefixed(rest, htSHA256)
                 });
             },
-            [&](FixedOutputHashMethod fohMethod) {
+            [&](FixedOutputHashMethod & fohMethod) {
                 return ContentAddress(FixedOutputHash {
                     .method = fohMethod.fileIngestionMethod,
                     .hash = Hash::parseNonSRIUnprefixed(rest, std::move(fohMethod.hashType)),
@@ -137,10 +137,10 @@ std::string renderContentAddress(std::optional<ContentAddress> ca)
 Hash getContentAddressHash(const ContentAddress & ca)
 {
     return std::visit(overloaded {
-        [](TextHash th) {
+        [](const TextHash & th) {
             return th.hash;
         },
-        [](FixedOutputHash fsh) {
+        [](const FixedOutputHash & fsh) {
             return fsh.hash;
         }
     }, ca);
diff --git a/src/libstore/daemon.cc b/src/libstore/daemon.cc
index 3d754830e..bfcdb8d95 100644
--- a/src/libstore/daemon.cc
+++ b/src/libstore/daemon.cc
@@ -2,6 +2,7 @@
 #include "monitor-fd.hh"
 #include "worker-protocol.hh"
 #include "store-api.hh"
+#include "path-with-outputs.hh"
 #include "finally.hh"
 #include "affinity.hh"
 #include "archive.hh"
@@ -226,6 +227,12 @@ struct ClientSettings
             try {
                 if (name == "ssh-auth-sock") // obsolete
                     ;
+                else if (name == settings.experimentalFeatures.name) {
+                    // We don’t want to forward the experimental features to
+                    // the daemon, as that could cause some pretty weird stuff
+                    if (tokenizeString<Strings>(value) != settings.experimentalFeatures.get())
+                        debug("Ignoring the client-specified experimental features");
+                }
                 else if (trusted
                     || name == settings.buildTimeout.name
                     || name == "connect-timeout"
@@ -242,21 +249,16 @@ struct ClientSettings
     }
 };
 
-static void writeValidPathInfo(
-    ref<Store> store,
-    unsigned int clientVersion,
-    Sink & to,
-    std::shared_ptr<const ValidPathInfo> info)
+static std::vector<DerivedPath> readDerivedPaths(Store & store, unsigned int clientVersion, Source & from)
 {
-    to << (info->deriver ? store->printStorePath(*info->deriver) : "")
-       << info->narHash.to_string(Base16, false);
-    worker_proto::write(*store, to, info->references);
-    to << info->registrationTime << info->narSize;
-    if (GET_PROTOCOL_MINOR(clientVersion) >= 16) {
-        to << info->ultimate
-           << info->sigs
-           << renderContentAddress(info->ca);
+    std::vector<DerivedPath> reqs;
+    if (GET_PROTOCOL_MINOR(clientVersion) >= 30) {
+        reqs = worker_proto::read(store, from, Phantom<std::vector<DerivedPath>> {});
+    } else {
+        for (auto & s : readStrings<Strings>(from))
+            reqs.push_back(parsePathWithOutputs(store, s).toDerivedPath());
     }
+    return reqs;
 }
 
 static void performOp(TunnelLogger * logger, ref<Store> store,
@@ -393,13 +395,13 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
                 FramedSource source(from);
                 // TODO this is essentially RemoteStore::addCAToStore. Move it up to Store.
                 return std::visit(overloaded {
-                    [&](TextHashMethod &_) {
+                    [&](TextHashMethod &) {
                         // We could stream this by changing Store
                         std::string contents = source.drain();
                         auto path = store->addTextToStore(name, contents, refs, repair);
                         return store->queryPathInfo(path);
                     },
-                    [&](FixedOutputHashMethod &fohm) {
+                    [&](FixedOutputHashMethod & fohm) {
                         if (!refs.empty())
                             throw UnimplementedError("cannot yet have refs with flat or nar-hashed data");
                         auto path = store->addToStoreFromDump(source, name, fohm.fileIngestionMethod, fohm.hashType, repair);
@@ -409,9 +411,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
             }();
             logger->stopWork();
 
-            to << store->printStorePath(pathInfo->path);
-            writeValidPathInfo(store, clientVersion, to, pathInfo);
-
+            pathInfo->write(to, *store, GET_PROTOCOL_MINOR(clientVersion));
         } else {
             HashType hashAlgo;
             std::string baseName;
@@ -458,6 +458,21 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         break;
     }
 
+    case wopAddMultipleToStore: {
+        bool repair, dontCheckSigs;
+        from >> repair >> dontCheckSigs;
+        if (!trusted && dontCheckSigs)
+            dontCheckSigs = false;
+
+        logger->startWork();
+        FramedSource source(from);
+        store->addMultipleToStore(source,
+            RepairFlag{repair},
+            dontCheckSigs ? NoCheckSigs : CheckSigs);
+        logger->stopWork();
+        break;
+    }
+
     case wopAddTextToStore: {
         string suffix = readString(from);
         string s = readString(from);
@@ -493,9 +508,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
     }
 
     case wopBuildPaths: {
-        std::vector<StorePathWithOutputs> drvs;
-        for (auto & s : readStrings<Strings>(from))
-            drvs.push_back(store->parsePathWithOutputs(s));
+        auto drvs = readDerivedPaths(*store, clientVersion, from);
         BuildMode mode = bmNormal;
         if (GET_PROTOCOL_MINOR(clientVersion) >= 15) {
             mode = (BuildMode) readInt(from);
@@ -575,7 +588,10 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         auto res = store->buildDerivation(drvPath, drv, buildMode);
         logger->stopWork();
         to << res.status << res.errorMsg;
-        if (GET_PROTOCOL_MINOR(clientVersion) >= 0xc) {
+        if (GET_PROTOCOL_MINOR(clientVersion) >= 29) {
+            to << res.timesBuilt << res.isNonDeterministic << res.startTime << res.stopTime;
+        }
+        if (GET_PROTOCOL_MINOR(clientVersion) >= 28) {
             worker_proto::write(*store, to, res.builtOutputs);
         }
         break;
@@ -756,7 +772,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         if (info) {
             if (GET_PROTOCOL_MINOR(clientVersion) >= 17)
                 to << 1;
-            writeValidPathInfo(store, clientVersion, to, info);
+            info->write(to, *store, GET_PROTOCOL_MINOR(clientVersion), false);
         } else {
             assert(GET_PROTOCOL_MINOR(clientVersion) >= 17);
             to << 0;
@@ -856,9 +872,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
     }
 
     case wopQueryMissing: {
-        std::vector<StorePathWithOutputs> targets;
-        for (auto & s : readStrings<Strings>(from))
-            targets.push_back(store->parsePathWithOutputs(s));
+        auto targets = readDerivedPaths(*store, clientVersion, from);
         logger->startWork();
         StorePathSet willBuild, willSubstitute, unknown;
         uint64_t downloadSize, narSize;
@@ -873,11 +887,15 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
 
     case wopRegisterDrvOutput: {
         logger->startWork();
-        auto outputId = DrvOutput::parse(readString(from));
-        auto outputPath = StorePath(readString(from));
-        auto resolvedDrv = StorePath(readString(from));
-        store->registerDrvOutput(Realisation{
-            .id = outputId, .outPath = outputPath});
+        if (GET_PROTOCOL_MINOR(clientVersion) < 31) {
+            auto outputId = DrvOutput::parse(readString(from));
+            auto outputPath = StorePath(readString(from));
+            store->registerDrvOutput(Realisation{
+                .id = outputId, .outPath = outputPath});
+        } else {
+            auto realisation = worker_proto::read(*store, from, Phantom<Realisation>());
+            store->registerDrvOutput(realisation);
+        }
         logger->stopWork();
         break;
     }
@@ -887,9 +905,15 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         auto outputId = DrvOutput::parse(readString(from));
         auto info = store->queryRealisation(outputId);
         logger->stopWork();
-        std::set<StorePath> outPaths;
-        if (info) outPaths.insert(info->outPath);
-        worker_proto::write(*store, to, outPaths);
+        if (GET_PROTOCOL_MINOR(clientVersion) < 31) {
+            std::set<StorePath> outPaths;
+            if (info) outPaths.insert(info->outPath);
+            worker_proto::write(*store, to, outPaths);
+        } else {
+            std::set<Realisation> realisations;
+            if (info) realisations.insert(*info);
+            worker_proto::write(*store, to, realisations);
+        }
         break;
     }
 
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index fe98182bb..ef8765841 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -10,18 +10,18 @@ namespace nix {
 std::optional<StorePath> DerivationOutput::path(const Store & store, std::string_view drvName, std::string_view outputName) const
 {
     return std::visit(overloaded {
-        [](DerivationOutputInputAddressed doi) -> std::optional<StorePath> {
+        [](const DerivationOutputInputAddressed & doi) -> std::optional<StorePath> {
             return { doi.path };
         },
-        [&](DerivationOutputCAFixed dof) -> std::optional<StorePath> {
+        [&](const DerivationOutputCAFixed & dof) -> std::optional<StorePath> {
             return {
                 dof.path(store, drvName, outputName)
             };
         },
-        [](DerivationOutputCAFloating dof) -> std::optional<StorePath> {
+        [](const DerivationOutputCAFloating & dof) -> std::optional<StorePath> {
             return std::nullopt;
         },
-        [](DerivationOutputDeferred) -> std::optional<StorePath> {
+        [](const DerivationOutputDeferred &) -> std::optional<StorePath> {
             return std::nullopt;
         },
     }, output);
@@ -332,22 +332,22 @@ string Derivation::unparse(const Store & store, bool maskOutputs,
         if (first) first = false; else s += ',';
         s += '('; printUnquotedString(s, i.first);
         std::visit(overloaded {
-            [&](DerivationOutputInputAddressed doi) {
+            [&](const DerivationOutputInputAddressed & doi) {
                 s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(doi.path));
                 s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, "");
             },
-            [&](DerivationOutputCAFixed dof) {
+            [&](const DerivationOutputCAFixed & dof) {
                 s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(dof.path(store, name, i.first)));
                 s += ','; printUnquotedString(s, dof.hash.printMethodAlgo());
                 s += ','; printUnquotedString(s, dof.hash.hash.to_string(Base16, false));
             },
-            [&](DerivationOutputCAFloating dof) {
+            [&](const DerivationOutputCAFloating & dof) {
                 s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
                 s += ','; printUnquotedString(s, "");
             },
-            [&](DerivationOutputDeferred) {
+            [&](const DerivationOutputDeferred &) {
                 s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, "");
@@ -420,13 +420,13 @@ DerivationType BasicDerivation::type() const
     std::optional<HashType> floatingHashType;
     for (auto & i : outputs) {
         std::visit(overloaded {
-            [&](DerivationOutputInputAddressed _) {
+            [&](const DerivationOutputInputAddressed &) {
                inputAddressedOutputs.insert(i.first);
             },
-            [&](DerivationOutputCAFixed _) {
+            [&](const DerivationOutputCAFixed &) {
                 fixedCAOutputs.insert(i.first);
             },
-            [&](DerivationOutputCAFloating dof) {
+            [&](const DerivationOutputCAFloating & dof) {
                 floatingCAOutputs.insert(i.first);
                 if (!floatingHashType) {
                     floatingHashType = dof.hashType;
@@ -435,7 +435,7 @@ DerivationType BasicDerivation::type() const
                         throw Error("All floating outputs must use the same hash type");
                 }
             },
-            [&](DerivationOutputDeferred _) {
+            [&](const DerivationOutputDeferred &) {
                deferredIAOutputs.insert(i.first);
             },
         }, i.second.output);
@@ -538,15 +538,15 @@ DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool m
         const auto & res = pathDerivationModulo(store, i.first);
         std::visit(overloaded {
             // Regular non-CA derivation, replace derivation
-            [&](Hash drvHash) {
+            [&](const Hash & drvHash) {
                 inputs2.insert_or_assign(drvHash.to_string(Base16, false), i.second);
             },
-            [&](DeferredHash deferredHash) {
+            [&](const DeferredHash & deferredHash) {
                 isDeferred = true;
                 inputs2.insert_or_assign(deferredHash.hash.to_string(Base16, false), i.second);
             },
             // CA derivation's output hashes
-            [&](CaOutputHashes outputHashes) {
+            [&](const CaOutputHashes & outputHashes) {
                 std::set<std::string> justOut = { "out" };
                 for (auto & output : i.second) {
                     /* Put each one in with a single "out" output.. */
@@ -568,21 +568,21 @@ DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool m
 }
 
 
-std::map<std::string, Hash> staticOutputHashes(Store& store, const Derivation& drv)
+std::map<std::string, Hash> staticOutputHashes(Store & store, const Derivation & drv)
 {
     std::map<std::string, Hash> res;
     std::visit(overloaded {
-        [&](Hash drvHash) {
+        [&](const Hash & drvHash) {
             for (auto & outputName : drv.outputNames()) {
                 res.insert({outputName, drvHash});
             }
         },
-        [&](DeferredHash deferredHash) {
+        [&](const DeferredHash & deferredHash) {
             for (auto & outputName : drv.outputNames()) {
                 res.insert({outputName, deferredHash.hash});
             }
         },
-        [&](CaOutputHashes outputHashes) {
+        [&](const CaOutputHashes & outputHashes) {
             res = outputHashes;
         },
     }, hashDerivationModulo(store, drv, true));
@@ -590,14 +590,6 @@ std::map<std::string, Hash> staticOutputHashes(Store& store, const Derivation& d
 }
 
 
-std::string StorePathWithOutputs::to_string(const Store & store) const
-{
-    return outputs.empty()
-        ? store.printStorePath(path)
-        : store.printStorePath(path) + "!" + concatStringsSep(",", outputs);
-}
-
-
 bool wantOutput(const string & output, const std::set<string> & wanted)
 {
     return wanted.empty() || wanted.find(output) != wanted.end();
@@ -674,22 +666,22 @@ void writeDerivation(Sink & out, const Store & store, const BasicDerivation & dr
     for (auto & i : drv.outputs) {
         out << i.first;
         std::visit(overloaded {
-            [&](DerivationOutputInputAddressed doi) {
+            [&](const DerivationOutputInputAddressed & doi) {
                 out << store.printStorePath(doi.path)
                     << ""
                     << "";
             },
-            [&](DerivationOutputCAFixed dof) {
+            [&](const DerivationOutputCAFixed & dof) {
                 out << store.printStorePath(dof.path(store, drv.name, i.first))
                     << dof.hash.printMethodAlgo()
                     << dof.hash.hash.to_string(Base16, false);
             },
-            [&](DerivationOutputCAFloating dof) {
+            [&](const DerivationOutputCAFloating & dof) {
                 out << ""
                     << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
                     << "";
             },
-            [&](DerivationOutputDeferred) {
+            [&](const DerivationOutputDeferred &) {
                 out << ""
                     << ""
                     << "";
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 061d70f69..b1cb68194 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -52,7 +52,7 @@ struct DerivationOutput
         DerivationOutputCAFloating,
         DerivationOutputDeferred
     > output;
-    std::optional<HashType> hashAlgoOpt(const Store & store) const;
+
     /* Note, when you use this function you should make sure that you're passing
        the right derivation name. When in doubt, you should use the safer
        interface provided by BasicDerivation::outputsAndOptPaths */
@@ -138,8 +138,8 @@ struct Derivation : BasicDerivation
 
     /* Return the underlying basic derivation but with these changes:
 
-	   1. Input drvs are emptied, but the outputs of them that were used are
-	      added directly to input sources.
+       1. Input drvs are emptied, but the outputs of them that were used are
+          added directly to input sources.
 
        2. Input placeholders are replaced with realized input store paths. */
     std::optional<BasicDerivation> tryResolve(Store & store);
diff --git a/src/libstore/derived-path.cc b/src/libstore/derived-path.cc
new file mode 100644
index 000000000..e55af21e9
--- /dev/null
+++ b/src/libstore/derived-path.cc
@@ -0,0 +1,118 @@
+#include "derived-path.hh"
+#include "store-api.hh"
+
+#include <nlohmann/json.hpp>
+
+namespace nix {
+
+nlohmann::json DerivedPath::Opaque::toJSON(ref<Store> store) const {
+    nlohmann::json res;
+    res["path"] = store->printStorePath(path);
+    return res;
+}
+
+nlohmann::json BuiltPath::Built::toJSON(ref<Store> store) const {
+    nlohmann::json res;
+    res["drvPath"] = store->printStorePath(drvPath);
+    for (const auto& [output, path] : outputs) {
+        res["outputs"][output] = store->printStorePath(path);
+    }
+    return res;
+}
+
+StorePathSet BuiltPath::outPaths() const
+{
+    return std::visit(
+        overloaded{
+            [](const BuiltPath::Opaque & p) { return StorePathSet{p.path}; },
+            [](const BuiltPath::Built & b) {
+                StorePathSet res;
+                for (auto & [_, path] : b.outputs)
+                    res.insert(path);
+                return res;
+            },
+        }, raw()
+    );
+}
+
+nlohmann::json derivedPathsWithHintsToJSON(const BuiltPaths & buildables, ref<Store> store) {
+    auto res = nlohmann::json::array();
+    for (const BuiltPath & buildable : buildables) {
+        std::visit([&res, store](const auto & buildable) {
+            res.push_back(buildable.toJSON(store));
+        }, buildable.raw());
+    }
+    return res;
+}
+
+
+std::string DerivedPath::Opaque::to_string(const Store & store) const {
+    return store.printStorePath(path);
+}
+
+std::string DerivedPath::Built::to_string(const Store & store) const {
+    return store.printStorePath(drvPath)
+        + "!"
+        + (outputs.empty() ? std::string { "*" } : concatStringsSep(",", outputs));
+}
+
+std::string DerivedPath::to_string(const Store & store) const
+{
+    return std::visit(
+        [&](const auto & req) { return req.to_string(store); },
+        this->raw());
+}
+
+
+DerivedPath::Opaque DerivedPath::Opaque::parse(const Store & store, std::string_view s)
+{
+    return {store.parseStorePath(s)};
+}
+
+DerivedPath::Built DerivedPath::Built::parse(const Store & store, std::string_view s)
+{
+    size_t n = s.find("!");
+    assert(n != s.npos);
+    auto drvPath = store.parseStorePath(s.substr(0, n));
+    auto outputsS = s.substr(n + 1);
+    std::set<string> outputs;
+    if (outputsS != "*")
+        outputs = tokenizeString<std::set<string>>(outputsS, ",");
+    return {drvPath, outputs};
+}
+
+DerivedPath DerivedPath::parse(const Store & store, std::string_view s)
+{
+    size_t n = s.find("!");
+    return n == s.npos
+        ? (DerivedPath) DerivedPath::Opaque::parse(store, s)
+        : (DerivedPath) DerivedPath::Built::parse(store, s);
+}
+
+RealisedPath::Set BuiltPath::toRealisedPaths(Store & store) const
+{
+    RealisedPath::Set res;
+    std::visit(
+        overloaded{
+            [&](const BuiltPath::Opaque & p) { res.insert(p.path); },
+            [&](const BuiltPath::Built & p) {
+                auto drvHashes =
+                    staticOutputHashes(store, store.readDerivation(p.drvPath));
+                for (auto& [outputName, outputPath] : p.outputs) {
+                    if (settings.isExperimentalFeatureEnabled(
+                            "ca-derivations")) {
+                        auto thisRealisation = store.queryRealisation(
+                            DrvOutput{drvHashes.at(outputName), outputName});
+                        assert(thisRealisation);  // We’ve built it, so we must h
+                                                  // ve the realisation
+                        res.insert(*thisRealisation);
+                    } else {
+                        res.insert(outputPath);
+                    }
+                }
+            },
+        },
+        raw());
+    return res;
+}
+}
diff --git a/src/libstore/derived-path.hh b/src/libstore/derived-path.hh
new file mode 100644
index 000000000..9d6ace069
--- /dev/null
+++ b/src/libstore/derived-path.hh
@@ -0,0 +1,123 @@
+#pragma once
+
+#include "util.hh"
+#include "path.hh"
+#include "realisation.hh"
+
+#include <optional>
+
+#include <nlohmann/json_fwd.hpp>
+
+namespace nix {
+
+class Store;
+
+/**
+ * An opaque derived path.
+ *
+ * Opaque derived paths are just store paths, and fully evaluated. They
+ * cannot be simplified further. Since they are opaque, they cannot be
+ * built, but they can fetched.
+ */
+struct DerivedPathOpaque {
+    StorePath path;
+
+    nlohmann::json toJSON(ref<Store> store) const;
+    std::string to_string(const Store & store) const;
+    static DerivedPathOpaque parse(const Store & store, std::string_view);
+};
+
+/**
+ * A derived path that is built from a derivation
+ *
+ * Built derived paths are pair of a derivation and some output names.
+ * They are evaluated by building the derivation, and then replacing the
+ * output names with the resulting outputs.
+ *
+ * Note that does mean a derived store paths evaluates to multiple
+ * opaque paths, which is sort of icky as expressions are supposed to
+ * evaluate to single values. Perhaps this should have just a single
+ * output name.
+ */
+struct DerivedPathBuilt {
+    StorePath drvPath;
+    std::set<std::string> outputs;
+
+    std::string to_string(const Store & store) const;
+    static DerivedPathBuilt parse(const Store & store, std::string_view);
+};
+
+using _DerivedPathRaw = std::variant<
+    DerivedPathOpaque,
+    DerivedPathBuilt
+>;
+
+/**
+ * A "derived path" is a very simple sort of expression that evaluates
+ * to (concrete) store path. It is either:
+ *
+ * - opaque, in which case it is just a concrete store path with
+ *   possibly no known derivation
+ *
+ * - built, in which case it is a pair of a derivation path and an
+ *   output name.
+ */
+struct DerivedPath : _DerivedPathRaw {
+    using Raw = _DerivedPathRaw;
+    using Raw::Raw;
+
+    using Opaque = DerivedPathOpaque;
+    using Built = DerivedPathBuilt;
+
+    inline const Raw & raw() const {
+        return static_cast<const Raw &>(*this);
+    }
+
+    std::string to_string(const Store & store) const;
+    static DerivedPath parse(const Store & store, std::string_view);
+};
+
+/**
+ * A built derived path with hints in the form of optional concrete output paths.
+ *
+ * See 'BuiltPath' for more an explanation.
+ */
+struct BuiltPathBuilt {
+    StorePath drvPath;
+    std::map<std::string, StorePath> outputs;
+
+    nlohmann::json toJSON(ref<Store> store) const;
+    static BuiltPathBuilt parse(const Store & store, std::string_view);
+};
+
+using _BuiltPathRaw = std::variant<
+    DerivedPath::Opaque,
+    BuiltPathBuilt
+>;
+
+/**
+ * A built path. Similar to a `DerivedPath`, but enriched with the corresponding
+ * output path(s).
+ */
+struct BuiltPath : _BuiltPathRaw {
+    using Raw = _BuiltPathRaw;
+    using Raw::Raw;
+
+    using Opaque = DerivedPathOpaque;
+    using Built = BuiltPathBuilt;
+
+    inline const Raw & raw() const {
+        return static_cast<const Raw &>(*this);
+    }
+
+    StorePathSet outPaths() const;
+    RealisedPath::Set toRealisedPaths(Store & store) const;
+
+};
+
+typedef std::vector<DerivedPath> DerivedPaths;
+typedef std::vector<BuiltPath> BuiltPaths;
+
+nlohmann::json derivedPathsWithHintsToJSON(const BuiltPaths & buildables, ref<Store> store);
+
+}
diff --git a/src/libstore/dummy-store.cc b/src/libstore/dummy-store.cc
index 8f26af685..36c6e725c 100644
--- a/src/libstore/dummy-store.cc
+++ b/src/libstore/dummy-store.cc
@@ -43,11 +43,6 @@ struct DummyStore : public virtual DummyStoreConfig, public virtual Store
         RepairFlag repair, CheckSigsFlag checkSigs) override
     { unsupported("addToStore"); }
 
-    StorePath addToStore(const string & name, const Path & srcPath,
-        FileIngestionMethod method, HashType hashAlgo,
-        PathFilter & filter, RepairFlag repair) override
-    { unsupported("addToStore"); }
-
     StorePath addTextToStore(const string & name, const string & s,
         const StorePathSet & references, RepairFlag repair) override
     { unsupported("addTextToStore"); }
diff --git a/src/libstore/filetransfer.cc b/src/libstore/filetransfer.cc
index 8ea5cdc9d..37e17b397 100644
--- a/src/libstore/filetransfer.cc
+++ b/src/libstore/filetransfer.cc
@@ -7,7 +7,7 @@
 #include "finally.hh"
 #include "callback.hh"
 
-#ifdef ENABLE_S3
+#if ENABLE_S3
 #include <aws/core/client/ClientConfiguration.h>
 #endif
 
@@ -148,7 +148,7 @@ struct curlFileTransfer : public FileTransfer
         }
 
         LambdaSink finalSink;
-        std::shared_ptr<CompressionSink> decompressionSink;
+        std::shared_ptr<FinishSink> decompressionSink;
         std::optional<StringSink> errorSink;
 
         std::exception_ptr writeException;
@@ -665,7 +665,7 @@ struct curlFileTransfer : public FileTransfer
         writeFull(wakeupPipe.writeSide.get(), " ");
     }
 
-#ifdef ENABLE_S3
+#if ENABLE_S3
     std::tuple<std::string, std::string, Store::Params> parseS3Uri(std::string uri)
     {
         auto [path, params] = splitUriAndParams(uri);
@@ -688,7 +688,7 @@ struct curlFileTransfer : public FileTransfer
         if (hasPrefix(request.uri, "s3://")) {
             // FIXME: do this on a worker thread
             try {
-#ifdef ENABLE_S3
+#if ENABLE_S3
                 auto [bucketName, key, params] = parseS3Uri(request.uri);
 
                 std::string profile = get(params, "profile").value_or("");
@@ -716,15 +716,24 @@ struct curlFileTransfer : public FileTransfer
     }
 };
 
+ref<curlFileTransfer> makeCurlFileTransfer()
+{
+    return make_ref<curlFileTransfer>();
+}
+
 ref<FileTransfer> getFileTransfer()
 {
-    static ref<FileTransfer> fileTransfer = makeFileTransfer();
+    static ref<curlFileTransfer> fileTransfer = makeCurlFileTransfer();
+
+    if (fileTransfer->state_.lock()->quit)
+        fileTransfer = makeCurlFileTransfer();
+
     return fileTransfer;
 }
 
 ref<FileTransfer> makeFileTransfer()
 {
-    return make_ref<curlFileTransfer>();
+    return makeCurlFileTransfer();
 }
 
 std::future<FileTransferResult> FileTransfer::enqueueFileTransfer(const FileTransferRequest & request)
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index bc692ca42..5a62c6529 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -775,7 +775,7 @@ void LocalStore::collectGarbage(const GCOptions & options, GCResults & results)
 
         try {
 
-            AutoCloseDir dir(opendir(realStoreDir.c_str()));
+            AutoCloseDir dir(opendir(realStoreDir.get().c_str()));
             if (!dir) throw SysError("opening directory '%1%'", realStoreDir);
 
             /* Read the store and immediately delete all paths that
@@ -856,7 +856,7 @@ void LocalStore::autoGC(bool sync)
             return std::stoll(readFile(*fakeFreeSpaceFile));
 
         struct statvfs st;
-        if (statvfs(realStoreDir.c_str(), &st))
+        if (statvfs(realStoreDir.get().c_str(), &st))
             throw SysError("getting filesystem info about '%s'", realStoreDir);
 
         return (uint64_t) st.f_bavail * st.f_frsize;
diff --git a/src/libstore/globals.cc b/src/libstore/globals.cc
index 8d44003f4..6934801e3 100644
--- a/src/libstore/globals.cc
+++ b/src/libstore/globals.cc
@@ -81,7 +81,7 @@ void loadConfFile()
 
     /* We only want to send overrides to the daemon, i.e. stuff from
        ~/.nix/nix.conf or the command line. */
-    globalConfig.resetOverriden();
+    globalConfig.resetOverridden();
 
     auto files = settings.nixUserConfFiles;
     for (auto file = files.rbegin(); file != files.rend(); file++) {
@@ -166,7 +166,7 @@ bool Settings::isExperimentalFeatureEnabled(const std::string & name)
 }
 
 MissingExperimentalFeature::MissingExperimentalFeature(std::string feature)
-    : Error("experimental Nix feature '%1%' is disabled; use '--experimental-features %1%' to override", feature)
+    : Error("experimental Nix feature '%1%' is disabled; use '--extra-experimental-features %1%' to override", feature)
     , missingFeature(feature)
     {}
 
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
index a51d9c2f1..8784d5faf 100644
--- a/src/libstore/globals.hh
+++ b/src/libstore/globals.hh
@@ -206,7 +206,10 @@ public:
 
     Setting<std::string> builders{
         this, "@" + nixConfDir + "/machines", "builders",
-        "A semicolon-separated list of build machines, in the format of `nix.machines`."};
+        R"(
+          A semicolon-separated list of build machines.
+          For the exact format and examples, see [the manual chapter on remote builds](../advanced-topics/distributed-builds.md)
+        )"};
 
     Setting<bool> buildersUseSubstitutes{
         this, false, "builders-use-substitutes",
@@ -614,8 +617,10 @@ public:
         Strings{"https://cache.nixos.org/"},
         "substituters",
         R"(
-          A list of URLs of substituters, separated by whitespace. The default
-          is `https://cache.nixos.org`.
+          A list of URLs of substituters, separated by whitespace. Substituters
+          are tried based on their Priority value, which each substituter can set
+          independently. Lower value means higher priority.
+          The default is `https://cache.nixos.org`, with a Priority of 40.
         )",
         {"binary-caches"}};
 
@@ -698,7 +703,7 @@ public:
           send a series of commands to modify various settings to stdout. The
           currently recognized commands are:
 
-            - `extra-sandbox-paths`  
+            - `extra-sandbox-paths`\
               Pass a list of files and directories to be included in the
               sandbox for this build. One entry per line, terminated by an
               empty line. Entries have the same format as `sandbox-paths`.
@@ -951,6 +956,9 @@ public:
           resolves to a different location from that of the build machine. You
           can enable this setting if you are sure you're not going to do that.
         )"};
+
+    Setting<bool> useRegistries{this, true, "use-registries",
+        "Whether to use flake registries to resolve flake references."};
 };
 
 
diff --git a/src/libstore/http-binary-cache-store.cc b/src/libstore/http-binary-cache-store.cc
index 0a3afcd51..605ec4b28 100644
--- a/src/libstore/http-binary-cache-store.cc
+++ b/src/libstore/http-binary-cache-store.cc
@@ -57,8 +57,8 @@ public:
     {
         // FIXME: do this lazily?
         if (auto cacheInfo = diskCache->cacheExists(cacheUri)) {
-            wantMassQuery.setDefault(cacheInfo->wantMassQuery ? "true" : "false");
-            priority.setDefault(fmt("%d", cacheInfo->priority));
+            wantMassQuery.setDefault(cacheInfo->wantMassQuery);
+            priority.setDefault(cacheInfo->priority);
         } else {
             try {
                 BinaryCacheStore::init();
diff --git a/src/libstore/legacy-ssh-store.cc b/src/libstore/legacy-ssh-store.cc
index daf78042f..814960bb5 100644
--- a/src/libstore/legacy-ssh-store.cc
+++ b/src/libstore/legacy-ssh-store.cc
@@ -3,6 +3,7 @@
 #include "remote-store.hh"
 #include "serve-protocol.hh"
 #include "store-api.hh"
+#include "path-with-outputs.hh"
 #include "worker-protocol.hh"
 #include "ssh.hh"
 #include "derivations.hh"
@@ -15,6 +16,7 @@ struct LegacySSHStoreConfig : virtual StoreConfig
     using StoreConfig::StoreConfig;
     const Setting<int> maxConnections{(StoreConfig*) this, 1, "max-connections", "maximum number of concurrent SSH connections"};
     const Setting<Path> sshKey{(StoreConfig*) this, "", "ssh-key", "path to an SSH private key"};
+    const Setting<std::string> sshPublicHostKey{(StoreConfig*) this, "", "base64-ssh-public-host-key", "The public half of the host's SSH key"};
     const Setting<bool> compress{(StoreConfig*) this, false, "compress", "whether to compress the connection"};
     const Setting<Path> remoteProgram{(StoreConfig*) this, "nix-store", "remote-program", "path to the nix-store executable on the remote system"};
     const Setting<std::string> remoteStore{(StoreConfig*) this, "", "remote-store", "URI of the store on the remote system"};
@@ -59,6 +61,7 @@ struct LegacySSHStore : public virtual LegacySSHStoreConfig, public virtual Stor
         , master(
             host,
             sshKey,
+            sshPublicHostKey,
             // Use SSH master only if using more than 1 connection.
             connections->capacity() > 1,
             compress,
@@ -79,9 +82,20 @@ struct LegacySSHStore : public virtual LegacySSHStoreConfig, public virtual Stor
             conn->to << SERVE_MAGIC_1 << SERVE_PROTOCOL_VERSION;
             conn->to.flush();
 
-            unsigned int magic = readInt(conn->from);
-            if (magic != SERVE_MAGIC_2)
-                throw Error("protocol mismatch with 'nix-store --serve' on '%s'", host);
+            StringSink saved;
+            try {
+                TeeSource tee(conn->from, saved);
+                unsigned int magic = readInt(tee);
+                if (magic != SERVE_MAGIC_2)
+                    throw Error("'nix-store --serve' protocol mismatch from '%s'", host);
+            } catch (SerialisationError & e) {
+                /* In case the other side is waiting for our input,
+                   close it. */
+                conn->sshConn->in.close();
+                auto msg = conn->from.drain();
+                throw Error("'nix-store --serve' protocol mismatch from '%s', got '%s'",
+                    host, chomp(*saved.s + msg));
+            }
             conn->remoteVersion = readInt(conn->from);
             if (GET_PROTOCOL_MAJOR(conn->remoteVersion) != 0x200)
                 throw Error("unsupported 'nix-store --serve' protocol version on '%s'", host);
@@ -234,6 +248,10 @@ private:
             conn.to
                 << settings.buildRepeat
                 << settings.enforceDeterminism;
+
+        if (GET_PROTOCOL_MINOR(conn.remoteVersion) >= 7) {
+            conn.to << ((int) settings.keepFailed);
+        }
     }
 
 public:
@@ -264,14 +282,26 @@ public:
         return status;
     }
 
-    void buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode) override
+    void buildPaths(const std::vector<DerivedPath> & drvPaths, BuildMode buildMode, std::shared_ptr<Store> evalStore) override
     {
+        if (evalStore && evalStore.get() != this)
+            throw Error("building on an SSH store is incompatible with '--eval-store'");
+
         auto conn(connections->get());
 
         conn->to << cmdBuildPaths;
         Strings ss;
-        for (auto & p : drvPaths)
-            ss.push_back(p.to_string(*this));
+        for (auto & p : drvPaths) {
+            auto sOrDrvPath = StorePathWithOutputs::tryFromDerivedPath(p);
+            std::visit(overloaded {
+                [&](const StorePathWithOutputs & s) {
+                    ss.push_back(s.to_string(*this));
+                },
+                [&](const StorePath & drvPath) {
+                    throw Error("wanted to fetch '%s' but the legacy ssh protocol doesn't support merely substituting drv files via the build paths command. It would build them instead. Try using ssh-ng://", printStorePath(drvPath));
+                },
+            }, sOrDrvPath);
+        }
         conn->to << ss;
 
         putBuildSettings(*conn);
diff --git a/src/libstore/local-binary-cache-store.cc b/src/libstore/local-binary-cache-store.cc
index a58b7733f..f93111fce 100644
--- a/src/libstore/local-binary-cache-store.cc
+++ b/src/libstore/local-binary-cache-store.cc
@@ -2,6 +2,8 @@
 #include "globals.hh"
 #include "nar-info-disk-cache.hh"
 
+#include <atomic>
+
 namespace nix {
 
 struct LocalBinaryCacheStoreConfig : virtual BinaryCacheStoreConfig
@@ -50,7 +52,8 @@ protected:
         const std::string & mimeType) override
     {
         auto path2 = binaryCacheDir + "/" + path;
-        Path tmp = path2 + ".tmp." + std::to_string(getpid());
+        static std::atomic<int> counter{0};
+        Path tmp = fmt("%s.tmp.%d.%d", path2, getpid(), ++counter);
         AutoDelete del(tmp, false);
         StreamToSourceAdapter source(istream);
         writeFile(tmp, source);
@@ -90,7 +93,7 @@ protected:
 void LocalBinaryCacheStore::init()
 {
     createDirs(binaryCacheDir + "/nar");
-    createDirs(binaryCacheDir + realisationsPrefix);
+    createDirs(binaryCacheDir + "/" + realisationsPrefix);
     if (writeDebugInfo)
         createDirs(binaryCacheDir + "/debuginfo");
     BinaryCacheStore::init();
diff --git a/src/libstore/local-fs-store.hh b/src/libstore/local-fs-store.hh
index 55941b771..f8b19d00d 100644
--- a/src/libstore/local-fs-store.hh
+++ b/src/libstore/local-fs-store.hh
@@ -18,6 +18,9 @@ struct LocalFSStoreConfig : virtual StoreConfig
     const PathSetting logDir{(StoreConfig*) this, false,
         rootDir != "" ? rootDir + "/nix/var/log/nix" : settings.nixLogDir,
         "log", "directory where Nix will store state"};
+    const PathSetting realStoreDir{(StoreConfig*) this, false,
+        rootDir != "" ? rootDir + "/nix/store" : storeDir, "real",
+        "physical path to the Nix store"};
 };
 
 class LocalFSStore : public virtual LocalFSStoreConfig, public virtual Store
@@ -34,7 +37,7 @@ public:
     /* Register a permanent GC root. */
     Path addPermRoot(const StorePath & storePath, const Path & gcRoot);
 
-    virtual Path getRealStoreDir() { return storeDir; }
+    virtual Path getRealStoreDir() { return realStoreDir; }
 
     Path toRealPath(const Path & storePath) override
     {
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index 90fb4a4bd..5b2490472 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -53,12 +53,15 @@ struct LocalStore::State::Stmts {
     SQLiteStmt InvalidatePath;
     SQLiteStmt AddDerivationOutput;
     SQLiteStmt RegisterRealisedOutput;
+    SQLiteStmt UpdateRealisedOutput;
     SQLiteStmt QueryValidDerivers;
     SQLiteStmt QueryDerivationOutputs;
     SQLiteStmt QueryRealisedOutput;
     SQLiteStmt QueryAllRealisedOutputs;
     SQLiteStmt QueryPathFromHashPart;
     SQLiteStmt QueryValidPaths;
+    SQLiteStmt QueryRealisationReferences;
+    SQLiteStmt AddRealisationReference;
 };
 
 int getSchema(Path schemaPath)
@@ -76,7 +79,7 @@ int getSchema(Path schemaPath)
 
 void migrateCASchema(SQLite& db, Path schemaPath, AutoCloseFD& lockFd)
 {
-    const int nixCASchemaVersion = 1;
+    const int nixCASchemaVersion = 2;
     int curCASchema = getSchema(schemaPath);
     if (curCASchema != nixCASchemaVersion) {
         if (curCASchema > nixCASchemaVersion) {
@@ -94,7 +97,39 @@ void migrateCASchema(SQLite& db, Path schemaPath, AutoCloseFD& lockFd)
               #include "ca-specific-schema.sql.gen.hh"
                 ;
             db.exec(schema);
+            curCASchema = nixCASchemaVersion;
         }
+
+        if (curCASchema < 2) {
+            SQLiteTxn txn(db);
+            // Ugly little sql dance to add a new `id` column and make it the primary key
+            db.exec(R"(
+                create table Realisations2 (
+                    id integer primary key autoincrement not null,
+                    drvPath text not null,
+                    outputName text not null, -- symbolic output id, usually "out"
+                    outputPath integer not null,
+                    signatures text, -- space-separated list
+                    foreign key (outputPath) references ValidPaths(id) on delete cascade
+                );
+                insert into Realisations2 (drvPath, outputName, outputPath, signatures)
+                    select drvPath, outputName, outputPath, signatures from Realisations;
+                drop table Realisations;
+                alter table Realisations2 rename to Realisations;
+            )");
+            db.exec(R"(
+                create index if not exists IndexRealisations on Realisations(drvPath, outputName);
+
+                create table if not exists RealisationsRefs (
+                    referrer integer not null,
+                    realisationReference integer,
+                    foreign key (referrer) references Realisations(id) on delete cascade,
+                    foreign key (realisationReference) references Realisations(id) on delete restrict
+                );
+            )");
+            txn.commit();
+        }
+
         writeFile(schemaPath, fmt("%d", nixCASchemaVersion));
         lockFile(lockFd.get(), ltRead, true);
     }
@@ -106,9 +141,6 @@ LocalStore::LocalStore(const Params & params)
     , LocalStoreConfig(params)
     , Store(params)
     , LocalFSStore(params)
-    , realStoreDir_{this, false, rootDir != "" ? rootDir + "/nix/store" : storeDir, "real",
-        "physical path to the Nix store"}
-    , realStoreDir(realStoreDir_)
     , dbDir(stateDir + "/db")
     , linksDir(realStoreDir + "/.links")
     , reservedPath(dbDir + "/reserved")
@@ -153,13 +185,13 @@ LocalStore::LocalStore(const Params & params)
             printError("warning: the group '%1%' specified in 'build-users-group' does not exist", settings.buildUsersGroup);
         else {
             struct stat st;
-            if (stat(realStoreDir.c_str(), &st))
+            if (stat(realStoreDir.get().c_str(), &st))
                 throw SysError("getting attributes of path '%1%'", realStoreDir);
 
             if (st.st_uid != 0 || st.st_gid != gr->gr_gid || (st.st_mode & ~S_IFMT) != perm) {
-                if (chown(realStoreDir.c_str(), 0, gr->gr_gid) == -1)
+                if (chown(realStoreDir.get().c_str(), 0, gr->gr_gid) == -1)
                     throw SysError("changing ownership of path '%1%'", realStoreDir);
-                if (chmod(realStoreDir.c_str(), perm) == -1)
+                if (chmod(realStoreDir.get().c_str(), perm) == -1)
                     throw SysError("changing permissions on path '%1%'", realStoreDir);
             }
         }
@@ -310,13 +342,22 @@ LocalStore::LocalStore(const Params & params)
     if (settings.isExperimentalFeatureEnabled("ca-derivations")) {
         state->stmts->RegisterRealisedOutput.create(state->db,
             R"(
-                insert or replace into Realisations (drvPath, outputName, outputPath)
-                values (?, ?, (select id from ValidPaths where path = ?))
+                insert into Realisations (drvPath, outputName, outputPath, signatures)
+                values (?, ?, (select id from ValidPaths where path = ?), ?)
+                ;
+            )");
+        state->stmts->UpdateRealisedOutput.create(state->db,
+            R"(
+                update Realisations
+                    set signatures = ?
+                where
+                    drvPath = ? and
+                    outputName = ?
                 ;
             )");
         state->stmts->QueryRealisedOutput.create(state->db,
             R"(
-                select Output.path from Realisations
+                select Realisations.id, Output.path, Realisations.signatures from Realisations
                     inner join ValidPaths as Output on Output.id = Realisations.outputPath
                     where drvPath = ? and outputName = ?
                     ;
@@ -328,6 +369,19 @@ LocalStore::LocalStore(const Params & params)
                     where drvPath = ?
                     ;
             )");
+        state->stmts->QueryRealisationReferences.create(state->db,
+            R"(
+                select drvPath, outputName from Realisations
+                    join RealisationsRefs on realisationReference = Realisations.id
+                    where referrer = ?;
+            )");
+        state->stmts->AddRealisationReference.create(state->db,
+            R"(
+                insert or replace into RealisationsRefs (referrer, realisationReference)
+                values (
+                    (select id from Realisations where drvPath = ? and outputName = ?),
+                    (select id from Realisations where drvPath = ? and outputName = ?));
+            )");
     }
 }
 
@@ -437,14 +491,14 @@ void LocalStore::makeStoreWritable()
     if (getuid() != 0) return;
     /* Check if /nix/store is on a read-only mount. */
     struct statvfs stat;
-    if (statvfs(realStoreDir.c_str(), &stat) != 0)
+    if (statvfs(realStoreDir.get().c_str(), &stat) != 0)
         throw SysError("getting info about the Nix store mount point");
 
     if (stat.f_flag & ST_RDONLY) {
         if (unshare(CLONE_NEWNS) == -1)
             throw SysError("setting up a private mount namespace");
 
-        if (mount(0, realStoreDir.c_str(), "none", MS_REMOUNT | MS_BIND, 0) == -1)
+        if (mount(0, realStoreDir.get().c_str(), "none", MS_REMOUNT | MS_BIND, 0) == -1)
             throw SysError("remounting %1% writable", realStoreDir);
     }
 #endif
@@ -627,7 +681,7 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
     std::optional<Hash> h;
     for (auto & i : drv.outputs) {
         std::visit(overloaded {
-            [&](DerivationOutputInputAddressed doia) {
+            [&](const DerivationOutputInputAddressed & doia) {
                 if (!h) {
                     // somewhat expensive so we do lazily
                     auto temp = hashDerivationModulo(*this, drv, true);
@@ -639,30 +693,79 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
                         printStorePath(drvPath), printStorePath(doia.path), printStorePath(recomputed));
                 envHasRightPath(doia.path, i.first);
             },
-            [&](DerivationOutputCAFixed dof) {
+            [&](const DerivationOutputCAFixed & dof) {
                 StorePath path = makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName);
                 envHasRightPath(path, i.first);
             },
-            [&](DerivationOutputCAFloating _) {
+            [&](const DerivationOutputCAFloating &) {
                 /* Nothing to check */
             },
-            [&](DerivationOutputDeferred) {
+            [&](const DerivationOutputDeferred &) {
             },
         }, i.second.output);
     }
 }
 
+void LocalStore::registerDrvOutput(const Realisation & info, CheckSigsFlag checkSigs)
+{
+    settings.requireExperimentalFeature("ca-derivations");
+    if (checkSigs == NoCheckSigs || !realisationIsUntrusted(info))
+        registerDrvOutput(info);
+    else
+        throw Error("cannot register realisation '%s' because it lacks a valid signature", info.outPath.to_string());
+}
 
 void LocalStore::registerDrvOutput(const Realisation & info)
 {
     settings.requireExperimentalFeature("ca-derivations");
-    auto state(_state.lock());
     retrySQLite<void>([&]() {
-        state->stmts->RegisterRealisedOutput.use()
-            (info.id.strHash())
-            (info.id.outputName)
-            (printStorePath(info.outPath))
-            .exec();
+        auto state(_state.lock());
+        if (auto oldR = queryRealisation_(*state, info.id)) {
+            if (info.isCompatibleWith(*oldR)) {
+                auto combinedSignatures = oldR->signatures;
+                combinedSignatures.insert(info.signatures.begin(),
+                    info.signatures.end());
+                state->stmts->UpdateRealisedOutput.use()
+                    (concatStringsSep(" ", combinedSignatures))
+                    (info.id.strHash())
+                    (info.id.outputName)
+                    .exec();
+            } else {
+                throw Error("Trying to register a realisation of '%s', but we already "
+                            "have another one locally.\n"
+                            "Local:  %s\n"
+                            "Remote: %s",
+                    info.id.to_string(),
+                    printStorePath(oldR->outPath),
+                    printStorePath(info.outPath)
+                );
+            }
+        } else {
+            state->stmts->RegisterRealisedOutput.use()
+                (info.id.strHash())
+                (info.id.outputName)
+                (printStorePath(info.outPath))
+                (concatStringsSep(" ", info.signatures))
+                .exec();
+        }
+        for (auto & [outputId, depPath] : info.dependentRealisations) {
+            auto localRealisation = queryRealisationCore_(*state, outputId);
+            if (!localRealisation)
+                throw Error("unable to register the derivation '%s' as it "
+                            "depends on the non existent '%s'",
+                    info.id.to_string(), outputId.to_string());
+            if (localRealisation->second.outPath != depPath)
+                throw Error("unable to register the derivation '%s' as it "
+                            "depends on a realisation of '%s' that doesn’t"
+                            "match what we have locally",
+                    info.id.to_string(), outputId.to_string());
+            state->stmts->AddRealisationReference.use()
+                (info.id.strHash())
+                (info.id.outputName)
+                (outputId.strHash())
+                (outputId.outputName)
+                .exec();
+        }
     });
 }
 
@@ -968,14 +1071,19 @@ StorePathSet LocalStore::querySubstitutablePaths(const StorePathSet & paths)
 }
 
 
+// FIXME: move this, it's not specific to LocalStore.
 void LocalStore::querySubstitutablePathInfos(const StorePathCAMap & paths, SubstitutablePathInfos & infos)
 {
     if (!settings.useSubstitutes) return;
     for (auto & sub : getDefaultSubstituters()) {
         for (auto & path : paths) {
+            if (infos.count(path.first))
+                // Choose first succeeding substituter.
+                continue;
+
             auto subPath(path.first);
 
-            // recompute store path so that we can use a different store root
+            // Recompute store path so that we can use a different store root.
             if (path.second) {
                 subPath = makeFixedOutputPathFromCA(path.first.name(), *path.second);
                 if (sub->storeDir == storeDir)
@@ -1102,15 +1210,20 @@ const PublicKeys & LocalStore::getPublicKeys()
     return *state->publicKeys;
 }
 
-bool LocalStore::pathInfoIsTrusted(const ValidPathInfo & info)
+bool LocalStore::pathInfoIsUntrusted(const ValidPathInfo & info)
 {
     return requireSigs && !info.checkSignatures(*this, getPublicKeys());
 }
 
+bool LocalStore::realisationIsUntrusted(const Realisation & realisation)
+{
+    return requireSigs && !realisation.checkSignatures(getPublicKeys());
+}
+
 void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
     RepairFlag repair, CheckSigsFlag checkSigs)
 {
-    if (checkSigs && pathInfoIsTrusted(info))
+    if (checkSigs && pathInfoIsUntrusted(info))
         throw Error("cannot add path '%s' because it lacks a valid signature", printStorePath(info.path));
 
     addTempRoot(info.path);
@@ -1131,24 +1244,15 @@ void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
 
             deletePath(realPath);
 
-            // text hashing has long been allowed to have non-self-references because it is used for drv files.
-            bool refersToSelf = info.references.count(info.path) > 0;
-            if (info.ca.has_value() && !info.references.empty() && !(std::holds_alternative<TextHash>(*info.ca) && !refersToSelf))
-                settings.requireExperimentalFeature("ca-references");
-
             /* While restoring the path from the NAR, compute the hash
                of the NAR. */
-            std::unique_ptr<AbstractHashSink> hashSink;
-            if (!info.ca.has_value() || !info.references.count(info.path))
-                hashSink = std::make_unique<HashSink>(htSHA256);
-            else
-                hashSink = std::make_unique<HashModuloSink>(htSHA256, std::string(info.path.hashPart()));
+            HashSink hashSink(htSHA256);
 
-            TeeSource wrapperSource { source, *hashSink };
+            TeeSource wrapperSource { source, hashSink };
 
             restorePath(realPath, wrapperSource);
 
-            auto hashResult = hashSink->finish();
+            auto hashResult = hashSink.finish();
 
             if (hashResult.first != info.narHash)
                 throw Error("hash mismatch importing path '%s';\n  specified: %s\n  got:       %s",
@@ -1158,6 +1262,31 @@ void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
                 throw Error("size mismatch importing path '%s';\n  specified: %s\n  got:       %s",
                     printStorePath(info.path), info.narSize, hashResult.second);
 
+            if (info.ca) {
+                if (auto foHash = std::get_if<FixedOutputHash>(&*info.ca)) {
+                    auto actualFoHash = hashCAPath(
+                        foHash->method,
+                        foHash->hash.type,
+                        info.path
+                    );
+                    if (foHash->hash != actualFoHash.hash) {
+                        throw Error("ca hash mismatch importing path '%s';\n  specified: %s\n  got:       %s",
+                            printStorePath(info.path),
+                            foHash->hash.to_string(Base32, true),
+                            actualFoHash.hash.to_string(Base32, true));
+                    }
+                }
+                if (auto textHash = std::get_if<TextHash>(&*info.ca)) {
+                    auto actualTextHash = hashString(htSHA256, readFile(realPath));
+                    if (textHash->hash != actualTextHash) {
+                        throw Error("ca hash mismatch importing path '%s';\n  specified: %s\n  got:       %s",
+                            printStorePath(info.path),
+                            textHash->hash.to_string(Base32, true),
+                            actualTextHash.to_string(Base32, true));
+                    }
+                }
+            }
+
             autoGC();
 
             canonicalisePathMetaData(realPath, -1);
@@ -1426,14 +1555,10 @@ bool LocalStore::verifyStore(bool checkContents, RepairFlag repair)
                 /* Check the content hash (optionally - slow). */
                 printMsg(lvlTalkative, "checking contents of '%s'", printStorePath(i));
 
-                std::unique_ptr<AbstractHashSink> hashSink;
-                if (!info->ca || !info->references.count(info->path))
-                    hashSink = std::make_unique<HashSink>(info->narHash.type);
-                else
-                    hashSink = std::make_unique<HashModuloSink>(info->narHash.type, std::string(info->path.hashPart()));
+                auto hashSink = HashSink(info->narHash.type);
 
-                dumpPath(Store::toRealPath(i), *hashSink);
-                auto current = hashSink->finish();
+                dumpPath(Store::toRealPath(i), hashSink);
+                auto current = hashSink.finish();
 
                 if (info->narHash != nullHash && info->narHash != current.first) {
                     printError("path '%s' was modified! expected hash '%s', got '%s'",
@@ -1612,6 +1737,18 @@ void LocalStore::addSignatures(const StorePath & storePath, const StringSet & si
 }
 
 
+void LocalStore::signRealisation(Realisation & realisation)
+{
+    // FIXME: keep secret keys in memory.
+
+    auto secretKeyFiles = settings.secretKeyFiles;
+
+    for (auto & secretKeyFile : secretKeyFiles.get()) {
+        SecretKey secretKey(readFile(secretKeyFile));
+        realisation.sign(secretKey);
+    }
+}
+
 void LocalStore::signPathInfo(ValidPathInfo & info)
 {
     // FIXME: keep secret keys in memory.
@@ -1639,18 +1776,97 @@ void LocalStore::createUser(const std::string & userName, uid_t userId)
     }
 }
 
-std::optional<const Realisation> LocalStore::queryRealisation(
-    const DrvOutput& id) {
-    typedef std::optional<const Realisation> Ret;
-    return retrySQLite<Ret>([&]() -> Ret {
+std::optional<std::pair<int64_t, Realisation>> LocalStore::queryRealisationCore_(
+        LocalStore::State & state,
+        const DrvOutput & id)
+{
+    auto useQueryRealisedOutput(
+            state.stmts->QueryRealisedOutput.use()
+                (id.strHash())
+                (id.outputName));
+    if (!useQueryRealisedOutput.next())
+        return std::nullopt;
+    auto realisationDbId = useQueryRealisedOutput.getInt(0);
+    auto outputPath = parseStorePath(useQueryRealisedOutput.getStr(1));
+    auto signatures =
+        tokenizeString<StringSet>(useQueryRealisedOutput.getStr(2));
+
+    return {{
+        realisationDbId,
+        Realisation{
+            .id = id,
+            .outPath = outputPath,
+            .signatures = signatures,
+        }
+    }};
+}
+
+std::optional<const Realisation> LocalStore::queryRealisation_(
+            LocalStore::State & state,
+            const DrvOutput & id)
+{
+    auto maybeCore = queryRealisationCore_(state, id);
+    if (!maybeCore)
+        return std::nullopt;
+    auto [realisationDbId, res] = *maybeCore;
+
+    std::map<DrvOutput, StorePath> dependentRealisations;
+    auto useRealisationRefs(
+        state.stmts->QueryRealisationReferences.use()
+            (realisationDbId));
+    while (useRealisationRefs.next()) {
+        auto depId = DrvOutput {
+            Hash::parseAnyPrefixed(useRealisationRefs.getStr(0)),
+            useRealisationRefs.getStr(1),
+        };
+        auto dependentRealisation = queryRealisationCore_(state, depId);
+        assert(dependentRealisation); // Enforced by the db schema
+        auto outputPath = dependentRealisation->second.outPath;
+        dependentRealisations.insert({depId, outputPath});
+    }
+
+    res.dependentRealisations = dependentRealisations;
+
+    return { res };
+}
+
+std::optional<const Realisation>
+LocalStore::queryRealisation(const DrvOutput & id)
+{
+    return retrySQLite<std::optional<const Realisation>>([&]() {
         auto state(_state.lock());
-        auto use(state->stmts->QueryRealisedOutput.use()(id.strHash())(
-            id.outputName));
-        if (!use.next())
-            return std::nullopt;
-        auto outputPath = parseStorePath(use.getStr(0));
-        return Ret{
-            Realisation{.id = id, .outPath = outputPath}};
+        return queryRealisation_(*state, id);
     });
 }
+
+FixedOutputHash LocalStore::hashCAPath(
+    const FileIngestionMethod & method, const HashType & hashType,
+    const StorePath & path)
+{
+    return hashCAPath(method, hashType, Store::toRealPath(path), path.hashPart());
+}
+
+FixedOutputHash LocalStore::hashCAPath(
+    const FileIngestionMethod & method,
+    const HashType & hashType,
+    const Path & path,
+    const std::string_view pathHash
+)
+{
+    HashModuloSink caSink ( hashType, std::string(pathHash) );
+    switch (method) {
+    case FileIngestionMethod::Recursive:
+        dumpPath(path, caSink);
+        break;
+    case FileIngestionMethod::Flat:
+        readFile(path, caSink);
+        break;
+    }
+    auto hash = caSink.finish().first;
+    return FixedOutputHash{
+        .method = method,
+        .hash = hash,
+    };
+}
+
 }  // namespace nix
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 03bb0218d..a01d48c4b 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -83,9 +83,6 @@ private:
 
 public:
 
-    PathSetting realStoreDir_;
-
-    const Path realStoreDir;
     const Path dbDir;
     const Path linksDir;
     const Path reservedPath;
@@ -136,7 +133,8 @@ public:
     void querySubstitutablePathInfos(const StorePathCAMap & paths,
         SubstitutablePathInfos & infos) override;
 
-    bool pathInfoIsTrusted(const ValidPathInfo &) override;
+    bool pathInfoIsUntrusted(const ValidPathInfo &) override;
+    bool realisationIsUntrusted(const Realisation & ) override;
 
     void addToStore(const ValidPathInfo & info, Source & source,
         RepairFlag repair, CheckSigsFlag checkSigs) override;
@@ -202,8 +200,11 @@ public:
     /* Register the store path 'output' as the output named 'outputName' of
        derivation 'deriver'. */
     void registerDrvOutput(const Realisation & info) override;
+    void registerDrvOutput(const Realisation & info, CheckSigsFlag checkSigs) override;
     void cacheDrvOutputMapping(State & state, const uint64_t deriver, const string & outputName, const StorePath & output);
 
+    std::optional<const Realisation> queryRealisation_(State & state, const DrvOutput & id);
+    std::optional<std::pair<int64_t, Realisation>> queryRealisationCore_(State & state, const DrvOutput & id);
     std::optional<const Realisation> queryRealisation(const DrvOutput&) override;
 
 private:
@@ -272,16 +273,30 @@ private:
     bool isValidPath_(State & state, const StorePath & path);
     void queryReferrers(State & state, const StorePath & path, StorePathSet & referrers);
 
-    /* Add signatures to a ValidPathInfo using the secret keys
+    /* Add signatures to a ValidPathInfo or Realisation using the secret keys
        specified by the ‘secret-key-files’ option. */
     void signPathInfo(ValidPathInfo & info);
-
-    Path getRealStoreDir() override { return realStoreDir; }
+    void signRealisation(Realisation &);
 
     void createUser(const std::string & userName, uid_t userId) override;
 
+    // XXX: Make a generic `Store` method
+    FixedOutputHash hashCAPath(
+        const FileIngestionMethod & method,
+        const HashType & hashType,
+        const StorePath & path);
+
+    FixedOutputHash hashCAPath(
+        const FileIngestionMethod & method,
+        const HashType & hashType,
+        const Path & path,
+        const std::string_view pathHash
+    );
+
     friend struct LocalDerivationGoal;
+    friend struct PathSubstitutionGoal;
     friend struct SubstitutionGoal;
+    friend struct DerivationGoal;
 };
 
 
diff --git a/src/libstore/local.mk b/src/libstore/local.mk
index 03c4351ac..b992bcbc0 100644
--- a/src/libstore/local.mk
+++ b/src/libstore/local.mk
@@ -8,12 +8,12 @@ libstore_SOURCES := $(wildcard $(d)/*.cc $(d)/builtins/*.cc $(d)/build/*.cc)
 
 libstore_LIBS = libutil
 
-libstore_LDFLAGS = $(SQLITE3_LIBS) -lbz2 $(LIBCURL_LIBS) $(SODIUM_LIBS) -pthread
-ifneq ($(OS), FreeBSD)
+libstore_LDFLAGS += $(SQLITE3_LIBS) $(LIBCURL_LIBS) $(SODIUM_LIBS) -pthread
+ifdef HOST_LINUX
  libstore_LDFLAGS += -ldl
 endif
 
-ifeq ($(OS), Darwin)
+ifdef HOST_DARWIN
 libstore_FILES = sandbox-defaults.sb sandbox-minimal.sb sandbox-network.sb
 endif
 
@@ -23,12 +23,12 @@ ifeq ($(ENABLE_S3), 1)
 	libstore_LDFLAGS += -laws-cpp-sdk-transfer -laws-cpp-sdk-s3 -laws-cpp-sdk-core
 endif
 
-ifeq ($(OS), SunOS)
+ifdef HOST_SOLARIS
 	libstore_LDFLAGS += -lsocket
 endif
 
 ifeq ($(HAVE_SECCOMP), 1)
-	libstore_LDFLAGS += -lseccomp
+	libstore_LDFLAGS += $(LIBSECCOMP_LIBS)
 endif
 
 libstore_CXXFLAGS += \
@@ -60,7 +60,7 @@ $(d)/build.cc:
 
 clean-files += $(d)/schema.sql.gen.hh $(d)/ca-specific-schema.sql.gen.hh
 
-$(eval $(call install-file-in, $(d)/nix-store.pc, $(prefix)/lib/pkgconfig, 0644))
+$(eval $(call install-file-in, $(d)/nix-store.pc, $(libdir)/pkgconfig, 0644))
 
 $(foreach i, $(wildcard src/libstore/builtins/*.hh), \
   $(eval $(call install-file-in, $(i), $(includedir)/nix/builtins, 0644)))
diff --git a/src/libstore/machines.cc b/src/libstore/machines.cc
index 7db2556f4..9843ccf04 100644
--- a/src/libstore/machines.cc
+++ b/src/libstore/machines.cc
@@ -16,13 +16,18 @@ Machine::Machine(decltype(storeUri) storeUri,
     decltype(mandatoryFeatures) mandatoryFeatures,
     decltype(sshPublicHostKey) sshPublicHostKey) :
     storeUri(
-        // Backwards compatibility: if the URI is a hostname,
-        // prepend ssh://.
+        // Backwards compatibility: if the URI is schemeless, is not a path,
+        // and is not one of the special store connection words, prepend
+        // ssh://.
         storeUri.find("://") != std::string::npos
-        || hasPrefix(storeUri, "local")
-        || hasPrefix(storeUri, "remote")
-        || hasPrefix(storeUri, "auto")
-        || hasPrefix(storeUri, "/")
+        || storeUri.find("/") != std::string::npos
+        || storeUri == "auto"
+        || storeUri == "daemon"
+        || storeUri == "local"
+        || hasPrefix(storeUri, "auto?")
+        || hasPrefix(storeUri, "daemon?")
+        || hasPrefix(storeUri, "local?")
+        || hasPrefix(storeUri, "?")
         ? storeUri
         : "ssh://" + storeUri),
     systemTypes(systemTypes),
@@ -54,9 +59,15 @@ ref<Store> Machine::openStore() const {
     if (hasPrefix(storeUri, "ssh://")) {
         storeParams["max-connections"] = "1";
         storeParams["log-fd"] = "4";
+    }
+
+    if (hasPrefix(storeUri, "ssh://") || hasPrefix(storeUri, "ssh-ng://")) {
         if (sshKey != "")
             storeParams["ssh-key"] = sshKey;
+        if (sshPublicHostKey != "")
+            storeParams["base64-ssh-public-host-key"] = sshPublicHostKey;
     }
+
     {
         auto & fs = storeParams["system-features"];
         auto append = [&](auto feats) {
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index ad4dccef9..f184dd857 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -6,100 +6,73 @@
 #include "thread-pool.hh"
 #include "topo-sort.hh"
 #include "callback.hh"
+#include "closure.hh"
 
 namespace nix {
 
-
 void Store::computeFSClosure(const StorePathSet & startPaths,
     StorePathSet & paths_, bool flipDirection, bool includeOutputs, bool includeDerivers)
 {
-    struct State
-    {
-        size_t pending;
-        StorePathSet & paths;
-        std::exception_ptr exc;
-    };
-
-    Sync<State> state_(State{0, paths_, 0});
-
-    std::function<void(const Path &)> enqueue;
-
-    std::condition_variable done;
-
-    enqueue = [&](const Path & path) -> void {
-        {
-            auto state(state_.lock());
-            if (state->exc) return;
-            if (!state->paths.insert(parseStorePath(path)).second) return;
-            state->pending++;
-        }
-
-        queryPathInfo(parseStorePath(path), {[&, pathS(path)](std::future<ref<const ValidPathInfo>> fut) {
-            // FIXME: calls to isValidPath() should be async
-
-            try {
-                auto info = fut.get();
-
-                auto path = parseStorePath(pathS);
-
-                if (flipDirection) {
-
-                    StorePathSet referrers;
-                    queryReferrers(path, referrers);
-                    for (auto & ref : referrers)
-                        if (ref != path)
-                            enqueue(printStorePath(ref));
-
-                    if (includeOutputs)
-                        for (auto & i : queryValidDerivers(path))
-                            enqueue(printStorePath(i));
-
-                    if (includeDerivers && path.isDerivation())
-                        for (auto & i : queryDerivationOutputs(path))
-                            if (isValidPath(i) && queryPathInfo(i)->deriver == path)
-                                enqueue(printStorePath(i));
-
-                } else {
-
-                    for (auto & ref : info->references)
-                        if (ref != path)
-                            enqueue(printStorePath(ref));
-
-                    if (includeOutputs && path.isDerivation())
-                        for (auto & i : queryDerivationOutputs(path))
-                            if (isValidPath(i)) enqueue(printStorePath(i));
-
-                    if (includeDerivers && info->deriver && isValidPath(*info->deriver))
-                        enqueue(printStorePath(*info->deriver));
-
-                }
-
-                {
-                    auto state(state_.lock());
-                    assert(state->pending);
-                    if (!--state->pending) done.notify_one();
-                }
-
-            } catch (...) {
-                auto state(state_.lock());
-                if (!state->exc) state->exc = std::current_exception();
-                assert(state->pending);
-                if (!--state->pending) done.notify_one();
-            };
-        }});
-    };
-
-    for (auto & startPath : startPaths)
-        enqueue(printStorePath(startPath));
-
-    {
-        auto state(state_.lock());
-        while (state->pending) state.wait(done);
-        if (state->exc) std::rethrow_exception(state->exc);
-    }
+    std::function<std::set<StorePath>(const StorePath & path, std::future<ref<const ValidPathInfo>> &)> queryDeps;
+    if (flipDirection)
+        queryDeps = [&](const StorePath& path,
+                        std::future<ref<const ValidPathInfo>> & fut) {
+            StorePathSet res;
+            StorePathSet referrers;
+            queryReferrers(path, referrers);
+            for (auto& ref : referrers)
+                if (ref != path)
+                    res.insert(ref);
+
+            if (includeOutputs)
+                for (auto& i : queryValidDerivers(path))
+                    res.insert(i);
+
+            if (includeDerivers && path.isDerivation())
+                for (auto& [_, maybeOutPath] : queryPartialDerivationOutputMap(path))
+                    if (maybeOutPath && isValidPath(*maybeOutPath))
+                        res.insert(*maybeOutPath);
+            return res;
+        };
+    else
+        queryDeps = [&](const StorePath& path,
+                        std::future<ref<const ValidPathInfo>> & fut) {
+            StorePathSet res;
+            auto info = fut.get();
+            for (auto& ref : info->references)
+                if (ref != path)
+                    res.insert(ref);
+
+            if (includeOutputs && path.isDerivation())
+                for (auto& [_, maybeOutPath] : queryPartialDerivationOutputMap(path))
+                    if (maybeOutPath && isValidPath(*maybeOutPath))
+                        res.insert(*maybeOutPath);
+
+            if (includeDerivers && info->deriver && isValidPath(*info->deriver))
+                res.insert(*info->deriver);
+            return res;
+        };
+
+    computeClosure<StorePath>(
+        startPaths, paths_,
+        [&](const StorePath& path,
+            std::function<void(std::promise<std::set<StorePath>>&)>
+                processEdges) {
+            std::promise<std::set<StorePath>> promise;
+            std::function<void(std::future<ref<const ValidPathInfo>>)>
+                getDependencies =
+                    [&](std::future<ref<const ValidPathInfo>> fut) {
+                        try {
+                            promise.set_value(queryDeps(path, fut));
+                        } catch (...) {
+                            promise.set_exception(std::current_exception());
+                        }
+                    };
+            queryPathInfo(path, getDependencies);
+            processEdges(promise);
+        });
 }
 
-
 void Store::computeFSClosure(const StorePath & startPath,
     StorePathSet & paths_, bool flipDirection, bool includeOutputs, bool includeDerivers)
 {
@@ -119,7 +92,7 @@ std::optional<ContentAddress> getDerivationCA(const BasicDerivation & drv)
     return std::nullopt;
 }
 
-void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
+void Store::queryMissing(const std::vector<DerivedPath> & targets,
     StorePathSet & willBuild_, StorePathSet & willSubstitute_, StorePathSet & unknown_,
     uint64_t & downloadSize_, uint64_t & narSize_)
 {
@@ -147,7 +120,7 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
 
     Sync<State> state_(State{{}, unknown_, willSubstitute_, willBuild_, downloadSize_, narSize_});
 
-    std::function<void(StorePathWithOutputs)> doPath;
+    std::function<void(DerivedPath)> doPath;
 
     auto mustBuildDrv = [&](const StorePath & drvPath, const Derivation & drv) {
         {
@@ -156,17 +129,14 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
         }
 
         for (auto & i : drv.inputDrvs)
-            pool.enqueue(std::bind(doPath, StorePathWithOutputs { i.first, i.second }));
+            pool.enqueue(std::bind(doPath, DerivedPath::Built { i.first, i.second }));
     };
 
     auto checkOutput = [&](
-        const Path & drvPathS, ref<Derivation> drv, const Path & outPathS, ref<Sync<DrvState>> drvState_)
+        const StorePath & drvPath, ref<Derivation> drv, const StorePath & outPath, ref<Sync<DrvState>> drvState_)
     {
         if (drvState_->lock()->done) return;
 
-        auto drvPath = parseStorePath(drvPathS);
-        auto outPath = parseStorePath(outPathS);
-
         SubstitutablePathInfos infos;
         querySubstitutablePathInfos({{outPath, getDerivationCA(*drv)}}, infos);
 
@@ -182,77 +152,80 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
                 drvState->outPaths.insert(outPath);
                 if (!drvState->left) {
                     for (auto & path : drvState->outPaths)
-                        pool.enqueue(std::bind(doPath, StorePathWithOutputs { path } ));
+                        pool.enqueue(std::bind(doPath, DerivedPath::Opaque { path } ));
                 }
             }
         }
     };
 
-    doPath = [&](const StorePathWithOutputs & path) {
+    doPath = [&](const DerivedPath & req) {
 
         {
             auto state(state_.lock());
-            if (!state->done.insert(path.to_string(*this)).second) return;
+            if (!state->done.insert(req.to_string(*this)).second) return;
         }
 
-        if (path.path.isDerivation()) {
-            if (!isValidPath(path.path)) {
+        std::visit(overloaded {
+          [&](const DerivedPath::Built & bfd) {
+            if (!isValidPath(bfd.drvPath)) {
                 // FIXME: we could try to substitute the derivation.
                 auto state(state_.lock());
-                state->unknown.insert(path.path);
+                state->unknown.insert(bfd.drvPath);
                 return;
             }
 
-            PathSet invalid;
+            StorePathSet invalid;
             /* true for regular derivations, and CA derivations for which we
                have a trust mapping for all wanted outputs. */
             auto knownOutputPaths = true;
-            for (auto & [outputName, pathOpt] : queryPartialDerivationOutputMap(path.path)) {
+            for (auto & [outputName, pathOpt] : queryPartialDerivationOutputMap(bfd.drvPath)) {
                 if (!pathOpt) {
                     knownOutputPaths = false;
                     break;
                 }
-                if (wantOutput(outputName, path.outputs) && !isValidPath(*pathOpt))
-                    invalid.insert(printStorePath(*pathOpt));
+                if (wantOutput(outputName, bfd.outputs) && !isValidPath(*pathOpt))
+                    invalid.insert(*pathOpt);
             }
             if (knownOutputPaths && invalid.empty()) return;
 
-            auto drv = make_ref<Derivation>(derivationFromPath(path.path));
-            ParsedDerivation parsedDrv(StorePath(path.path), *drv);
+            auto drv = make_ref<Derivation>(derivationFromPath(bfd.drvPath));
+            ParsedDerivation parsedDrv(StorePath(bfd.drvPath), *drv);
 
             if (knownOutputPaths && settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
                 auto drvState = make_ref<Sync<DrvState>>(DrvState(invalid.size()));
                 for (auto & output : invalid)
-                    pool.enqueue(std::bind(checkOutput, printStorePath(path.path), drv, output, drvState));
+                    pool.enqueue(std::bind(checkOutput, bfd.drvPath, drv, output, drvState));
             } else
-                mustBuildDrv(path.path, *drv);
+                mustBuildDrv(bfd.drvPath, *drv);
 
-        } else {
+          },
+          [&](const DerivedPath::Opaque & bo) {
 
-            if (isValidPath(path.path)) return;
+            if (isValidPath(bo.path)) return;
 
             SubstitutablePathInfos infos;
-            querySubstitutablePathInfos({{path.path, std::nullopt}}, infos);
+            querySubstitutablePathInfos({{bo.path, std::nullopt}}, infos);
 
             if (infos.empty()) {
                 auto state(state_.lock());
-                state->unknown.insert(path.path);
+                state->unknown.insert(bo.path);
                 return;
             }
 
-            auto info = infos.find(path.path);
+            auto info = infos.find(bo.path);
             assert(info != infos.end());
 
             {
                 auto state(state_.lock());
-                state->willSubstitute.insert(path.path);
+                state->willSubstitute.insert(bo.path);
                 state->downloadSize += info->second.downloadSize;
                 state->narSize += info->second.narSize;
             }
 
             for (auto & ref : info->second.references)
-                pool.enqueue(std::bind(doPath, StorePathWithOutputs { ref }));
-        }
+                pool.enqueue(std::bind(doPath, DerivedPath::Opaque { ref }));
+          },
+        }, req.raw());
     };
 
     for (auto & path : targets)
@@ -281,5 +254,44 @@ StorePaths Store::topoSortPaths(const StorePathSet & paths)
         }});
 }
 
+std::map<DrvOutput, StorePath> drvOutputReferences(
+    const std::set<Realisation> & inputRealisations,
+    const StorePathSet & pathReferences)
+{
+    std::map<DrvOutput, StorePath> res;
+
+    for (const auto & input : inputRealisations) {
+        if (pathReferences.count(input.outPath)) {
+            res.insert({input.id, input.outPath});
+        }
+    }
+
+    return res;
+}
 
+std::map<DrvOutput, StorePath> drvOutputReferences(
+    Store & store,
+    const Derivation & drv,
+    const StorePath & outputPath)
+{
+    std::set<Realisation> inputRealisations;
+
+    for (const auto& [inputDrv, outputNames] : drv.inputDrvs) {
+        auto outputHashes =
+            staticOutputHashes(store, store.readDerivation(inputDrv));
+        for (const auto& outputName : outputNames) {
+            auto thisRealisation = store.queryRealisation(
+                DrvOutput{outputHashes.at(outputName), outputName});
+            if (!thisRealisation)
+                throw Error(
+                    "output '%s' of derivation '%s' isn’t built", outputName,
+                    store.printStorePath(inputDrv));
+            inputRealisations.insert(*thisRealisation);
+        }
+    }
+
+    auto info = store.queryPathInfo(outputPath);
+
+    return drvOutputReferences(Realisation::closure(store, inputRealisations), info->references);
+}
 }
diff --git a/src/libstore/nar-info-disk-cache.cc b/src/libstore/nar-info-disk-cache.cc
index 1d8d2d57e..9dd81ddfb 100644
--- a/src/libstore/nar-info-disk-cache.cc
+++ b/src/libstore/nar-info-disk-cache.cc
@@ -4,6 +4,7 @@
 #include "globals.hh"
 
 #include <sqlite3.h>
+#include <nlohmann/json.hpp>
 
 namespace nix {
 
@@ -38,6 +39,15 @@ create table if not exists NARs (
     foreign key (cache) references BinaryCaches(id) on delete cascade
 );
 
+create table if not exists Realisations (
+    cache integer not null,
+    outputId text not null,
+    content blob, -- Json serialisation of the realisation, or null if the realisation is absent
+    timestamp        integer not null,
+    primary key (cache, outputId),
+    foreign key (cache) references BinaryCaches(id) on delete cascade
+);
+
 create table if not exists LastPurge (
     dummy            text primary key,
     value            integer
@@ -63,7 +73,9 @@ public:
     struct State
     {
         SQLite db;
-        SQLiteStmt insertCache, queryCache, insertNAR, insertMissingNAR, queryNAR, purgeCache;
+        SQLiteStmt insertCache, queryCache, insertNAR, insertMissingNAR,
+            queryNAR, insertRealisation, insertMissingRealisation,
+            queryRealisation, purgeCache;
         std::map<std::string, Cache> caches;
     };
 
@@ -98,6 +110,26 @@ public:
         state->queryNAR.create(state->db,
             "select present, namePart, url, compression, fileHash, fileSize, narHash, narSize, refs, deriver, sigs, ca from NARs where cache = ? and hashPart = ? and ((present = 0 and timestamp > ?) or (present = 1 and timestamp > ?))");
 
+        state->insertRealisation.create(state->db,
+            R"(
+                insert or replace into Realisations(cache, outputId, content, timestamp)
+                    values (?, ?, ?, ?)
+            )");
+
+        state->insertMissingRealisation.create(state->db,
+            R"(
+                insert or replace into Realisations(cache, outputId, timestamp)
+                    values (?, ?, ?)
+            )");
+
+        state->queryRealisation.create(state->db,
+            R"(
+                select content from Realisations
+                    where cache = ? and outputId = ?  and
+                        ((content is null and timestamp > ?) or
+                         (content is not null and timestamp > ?))
+            )");
+
         /* Periodically purge expired entries from the database. */
         retrySQLite<void>([&]() {
             auto now = time(0);
@@ -212,6 +244,38 @@ public:
         });
     }
 
+    std::pair<Outcome, std::shared_ptr<Realisation>> lookupRealisation(
+        const std::string & uri, const DrvOutput & id) override
+    {
+        return retrySQLite<std::pair<Outcome, std::shared_ptr<Realisation>>>(
+            [&]() -> std::pair<Outcome, std::shared_ptr<Realisation>> {
+            auto state(_state.lock());
+
+            auto & cache(getCache(*state, uri));
+
+            auto now = time(0);
+
+            auto queryRealisation(state->queryRealisation.use()
+                (cache.id)
+                (id.to_string())
+                (now - settings.ttlNegativeNarInfoCache)
+                (now - settings.ttlPositiveNarInfoCache));
+
+            if (!queryRealisation.next())
+                return {oUnknown, 0};
+
+            if (queryRealisation.isNull(0))
+                return {oInvalid, 0};
+
+            auto realisation =
+                std::make_shared<Realisation>(Realisation::fromJSON(
+                    nlohmann::json::parse(queryRealisation.getStr(0)),
+                    "Local disk cache"));
+
+            return {oValid, realisation};
+        });
+    }
+
     void upsertNarInfo(
         const std::string & uri, const std::string & hashPart,
         std::shared_ptr<const ValidPathInfo> info) override
@@ -251,6 +315,39 @@ public:
             }
         });
     }
+
+    void upsertRealisation(
+        const std::string & uri,
+        const Realisation & realisation) override
+    {
+        retrySQLite<void>([&]() {
+            auto state(_state.lock());
+
+            auto & cache(getCache(*state, uri));
+
+            state->insertRealisation.use()
+                (cache.id)
+                (realisation.id.to_string())
+                (realisation.toJSON().dump())
+                (time(0)).exec();
+        });
+
+    }
+
+    virtual void upsertAbsentRealisation(
+        const std::string & uri,
+        const DrvOutput & id) override
+    {
+        retrySQLite<void>([&]() {
+            auto state(_state.lock());
+
+            auto & cache(getCache(*state, uri));
+            state->insertMissingRealisation.use()
+                (cache.id)
+                (id.to_string())
+                (time(0)).exec();
+        });
+    }
 };
 
 ref<NarInfoDiskCache> getNarInfoDiskCache()
diff --git a/src/libstore/nar-info-disk-cache.hh b/src/libstore/nar-info-disk-cache.hh
index 04de2c5eb..2dcaa76a4 100644
--- a/src/libstore/nar-info-disk-cache.hh
+++ b/src/libstore/nar-info-disk-cache.hh
@@ -2,6 +2,7 @@
 
 #include "ref.hh"
 #include "nar-info.hh"
+#include "realisation.hh"
 
 namespace nix {
 
@@ -29,6 +30,15 @@ public:
     virtual void upsertNarInfo(
         const std::string & uri, const std::string & hashPart,
         std::shared_ptr<const ValidPathInfo> info) = 0;
+
+    virtual void upsertRealisation(
+        const std::string & uri,
+        const Realisation & realisation) = 0;
+    virtual void upsertAbsentRealisation(
+        const std::string & uri,
+        const DrvOutput & id) = 0;
+    virtual std::pair<Outcome, std::shared_ptr<Realisation>> lookupRealisation(
+        const std::string & uri, const DrvOutput & id) = 0;
 };
 
 /* Return a singleton cache object that can be used concurrently by
diff --git a/src/libstore/optimise-store.cc b/src/libstore/optimise-store.cc
index 78d587139..d95e54af1 100644
--- a/src/libstore/optimise-store.cc
+++ b/src/libstore/optimise-store.cc
@@ -198,7 +198,7 @@ void LocalStore::optimisePath_(Activity * act, OptimiseStats & stats,
     /* Make the containing directory writable, but only if it's not
        the store itself (we don't want or need to mess with its
        permissions). */
-    bool mustToggle = dirOf(path) != realStoreDir;
+    bool mustToggle = dirOf(path) != realStoreDir.get();
     if (mustToggle) makeWritable(dirOf(path));
 
     /* When we're done, make the directory read-only again and reset
diff --git a/src/libstore/parsed-derivations.cc b/src/libstore/parsed-derivations.cc
index c5c3ae3dc..caddba9b1 100644
--- a/src/libstore/parsed-derivations.cc
+++ b/src/libstore/parsed-derivations.cc
@@ -1,6 +1,8 @@
 #include "parsed-derivations.hh"
 
 #include <nlohmann/json.hpp>
+#include <regex>
+#include "json.hh"
 
 namespace nix {
 
@@ -91,6 +93,8 @@ StringSet ParsedDerivation::getRequiredSystemFeatures() const
     StringSet res;
     for (auto & i : getStringsAttr("requiredSystemFeatures").value_or(Strings()))
         res.insert(i);
+    if (!derivationHasKnownOutputPaths(drv.type()))
+        res.insert("ca-derivations");
     return res;
 }
 
@@ -121,4 +125,107 @@ bool ParsedDerivation::substitutesAllowed() const
     return getBoolAttr("allowSubstitutes", true);
 }
 
+static std::regex shVarName("[A-Za-z_][A-Za-z0-9_]*");
+
+std::optional<nlohmann::json> ParsedDerivation::prepareStructuredAttrs(Store & store, const StorePathSet & inputPaths)
+{
+    auto structuredAttrs = getStructuredAttrs();
+    if (!structuredAttrs) return std::nullopt;
+
+    auto json = *structuredAttrs;
+
+    /* Add an "outputs" object containing the output paths. */
+    nlohmann::json outputs;
+    for (auto & i : drv.outputs)
+        outputs[i.first] = hashPlaceholder(i.first);
+    json["outputs"] = outputs;
+
+    /* Handle exportReferencesGraph. */
+    auto e = json.find("exportReferencesGraph");
+    if (e != json.end() && e->is_object()) {
+        for (auto i = e->begin(); i != e->end(); ++i) {
+            std::ostringstream str;
+            {
+                JSONPlaceholder jsonRoot(str, true);
+                StorePathSet storePaths;
+                for (auto & p : *i)
+                    storePaths.insert(store.parseStorePath(p.get<std::string>()));
+                store.pathInfoToJSON(jsonRoot,
+                    store.exportReferences(storePaths, inputPaths), false, true);
+            }
+            json[i.key()] = nlohmann::json::parse(str.str()); // urgh
+        }
+    }
+
+    return json;
+}
+
+/* As a convenience to bash scripts, write a shell file that
+   maps all attributes that are representable in bash -
+   namely, strings, integers, nulls, Booleans, and arrays and
+   objects consisting entirely of those values. (So nested
+   arrays or objects are not supported.) */
+std::string writeStructuredAttrsShell(const nlohmann::json & json)
+{
+
+    auto handleSimpleType = [](const nlohmann::json & value) -> std::optional<std::string> {
+        if (value.is_string())
+            return shellEscape(value);
+
+        if (value.is_number()) {
+            auto f = value.get<float>();
+            if (std::ceil(f) == f)
+                return std::to_string(value.get<int>());
+        }
+
+        if (value.is_null())
+            return std::string("''");
+
+        if (value.is_boolean())
+            return value.get<bool>() ? std::string("1") : std::string("");
+
+        return {};
+    };
+
+    std::string jsonSh;
+
+    for (auto & [key, value] : json.items()) {
+
+        if (!std::regex_match(key, shVarName)) continue;
+
+        auto s = handleSimpleType(value);
+        if (s)
+            jsonSh += fmt("declare %s=%s\n", key, *s);
+
+        else if (value.is_array()) {
+            std::string s2;
+            bool good = true;
+
+            for (auto & value2 : value) {
+                auto s3 = handleSimpleType(value2);
+                if (!s3) { good = false; break; }
+                s2 += *s3; s2 += ' ';
+            }
+
+            if (good)
+                jsonSh += fmt("declare -a %s=(%s)\n", key, s2);
+        }
+
+        else if (value.is_object()) {
+            std::string s2;
+            bool good = true;
+
+            for (auto & [key2, value2] : value.items()) {
+                auto s3 = handleSimpleType(value2);
+                if (!s3) { good = false; break; }
+                s2 += fmt("[%s]=%s ", shellEscape(key2), *s3);
+            }
+
+            if (good)
+                jsonSh += fmt("declare -A %s=(%s)\n", key, s2);
+        }
+    }
+
+    return jsonSh;
+}
 }
diff --git a/src/libstore/parsed-derivations.hh b/src/libstore/parsed-derivations.hh
index c9fbe68c4..effcf099d 100644
--- a/src/libstore/parsed-derivations.hh
+++ b/src/libstore/parsed-derivations.hh
@@ -36,6 +36,10 @@ public:
     bool willBuildLocally(Store & localStore) const;
 
     bool substitutesAllowed() const;
+
+    std::optional<nlohmann::json> prepareStructuredAttrs(Store & store, const StorePathSet & inputPaths);
 };
 
+std::string writeStructuredAttrsShell(const nlohmann::json & json);
+
 }
diff --git a/src/libstore/path-info.cc b/src/libstore/path-info.cc
new file mode 100644
index 000000000..fda55b2b6
--- /dev/null
+++ b/src/libstore/path-info.cc
@@ -0,0 +1,46 @@
+#include "path-info.hh"
+#include "worker-protocol.hh"
+
+namespace nix {
+
+ValidPathInfo ValidPathInfo::read(Source & source, const Store & store, unsigned int format)
+{
+    return read(source, store, format, store.parseStorePath(readString(source)));
+}
+
+ValidPathInfo ValidPathInfo::read(Source & source, const Store & store, unsigned int format, StorePath && path)
+{
+    auto deriver = readString(source);
+    auto narHash = Hash::parseAny(readString(source), htSHA256);
+    ValidPathInfo info(path, narHash);
+    if (deriver != "") info.deriver = store.parseStorePath(deriver);
+    info.references = worker_proto::read(store, source, Phantom<StorePathSet> {});
+    source >> info.registrationTime >> info.narSize;
+    if (format >= 16) {
+        source >> info.ultimate;
+        info.sigs = readStrings<StringSet>(source);
+        info.ca = parseContentAddressOpt(readString(source));
+    }
+    return info;
+}
+
+void ValidPathInfo::write(
+    Sink & sink,
+    const Store & store,
+    unsigned int format,
+    bool includePath) const
+{
+    if (includePath)
+        sink << store.printStorePath(path);
+    sink << (deriver ? store.printStorePath(*deriver) : "")
+         << narHash.to_string(Base16, false);
+    worker_proto::write(store, sink, references);
+    sink << registrationTime << narSize;
+    if (format >= 16) {
+        sink << ultimate
+             << sigs
+             << renderContentAddress(ca);
+    }
+}
+
+}
diff --git a/src/libstore/path-info.hh b/src/libstore/path-info.hh
index de87f8b33..b4b54e593 100644
--- a/src/libstore/path-info.hh
+++ b/src/libstore/path-info.hh
@@ -105,6 +105,11 @@ struct ValidPathInfo
     ValidPathInfo(const StorePath & path, Hash narHash) : path(path), narHash(narHash) { };
 
     virtual ~ValidPathInfo() { }
+
+    static ValidPathInfo read(Source & source, const Store & store, unsigned int format);
+    static ValidPathInfo read(Source & source, const Store & store, unsigned int format, StorePath && path);
+
+    void write(Sink & sink, const Store & store, unsigned int format, bool includePath = true) const;
 };
 
 typedef std::map<StorePath, ValidPathInfo> ValidPathInfos;
diff --git a/src/libstore/path-with-outputs.cc b/src/libstore/path-with-outputs.cc
new file mode 100644
index 000000000..e5a121e00
--- /dev/null
+++ b/src/libstore/path-with-outputs.cc
@@ -0,0 +1,71 @@
+#include "path-with-outputs.hh"
+#include "store-api.hh"
+
+namespace nix {
+
+std::string StorePathWithOutputs::to_string(const Store & store) const
+{
+    return outputs.empty()
+        ? store.printStorePath(path)
+        : store.printStorePath(path) + "!" + concatStringsSep(",", outputs);
+}
+
+
+DerivedPath StorePathWithOutputs::toDerivedPath() const
+{
+    if (!outputs.empty() || path.isDerivation())
+        return DerivedPath::Built { path, outputs };
+    else
+        return DerivedPath::Opaque { path };
+}
+
+
+std::vector<DerivedPath> toDerivedPaths(const std::vector<StorePathWithOutputs> ss)
+{
+	std::vector<DerivedPath> reqs;
+	for (auto & s : ss) reqs.push_back(s.toDerivedPath());
+	return reqs;
+}
+
+
+std::variant<StorePathWithOutputs, StorePath> StorePathWithOutputs::tryFromDerivedPath(const DerivedPath & p)
+{
+    return std::visit(overloaded {
+        [&](const DerivedPath::Opaque & bo) -> std::variant<StorePathWithOutputs, StorePath> {
+            if (bo.path.isDerivation()) {
+                // drv path gets interpreted as "build", not "get drv file itself"
+                return bo.path;
+            }
+            return StorePathWithOutputs { bo.path };
+        },
+        [&](const DerivedPath::Built & bfd) -> std::variant<StorePathWithOutputs, StorePath> {
+            return StorePathWithOutputs { bfd.drvPath, bfd.outputs };
+        },
+    }, p.raw());
+}
+
+
+std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s)
+{
+    size_t n = s.find("!");
+    return n == s.npos
+        ? std::make_pair(s, std::set<string>())
+        : std::make_pair(((std::string_view) s).substr(0, n),
+            tokenizeString<std::set<string>>(((std::string_view) s).substr(n + 1), ","));
+}
+
+
+StorePathWithOutputs parsePathWithOutputs(const Store & store, std::string_view pathWithOutputs)
+{
+    auto [path, outputs] = parsePathWithOutputs(pathWithOutputs);
+    return StorePathWithOutputs { store.parseStorePath(path), std::move(outputs) };
+}
+
+
+StorePathWithOutputs followLinksToStorePathWithOutputs(const Store & store, std::string_view pathWithOutputs)
+{
+    auto [path, outputs] = parsePathWithOutputs(pathWithOutputs);
+    return StorePathWithOutputs { store.followLinksToStorePath(path), std::move(outputs) };
+}
+
+}
diff --git a/src/libstore/path-with-outputs.hh b/src/libstore/path-with-outputs.hh
new file mode 100644
index 000000000..4c4023dcb
--- /dev/null
+++ b/src/libstore/path-with-outputs.hh
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <variant>
+
+#include "path.hh"
+#include "derived-path.hh"
+
+namespace nix {
+
+struct StorePathWithOutputs
+{
+    StorePath path;
+    std::set<std::string> outputs;
+
+    std::string to_string(const Store & store) const;
+
+    DerivedPath toDerivedPath() const;
+
+    static std::variant<StorePathWithOutputs, StorePath> tryFromDerivedPath(const DerivedPath &);
+};
+
+std::vector<DerivedPath> toDerivedPaths(const std::vector<StorePathWithOutputs>);
+
+std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s);
+
+class Store;
+
+/* Split a string specifying a derivation and a set of outputs
+   (/nix/store/hash-foo!out1,out2,...) into the derivation path
+   and the outputs. */
+StorePathWithOutputs parsePathWithOutputs(const Store & store, std::string_view pathWithOutputs);
+
+StorePathWithOutputs followLinksToStorePathWithOutputs(const Store & store, std::string_view pathWithOutputs);
+
+}
diff --git a/src/libstore/path.cc b/src/libstore/path.cc
index dc9dc3897..e642abcd5 100644
--- a/src/libstore/path.cc
+++ b/src/libstore/path.cc
@@ -82,19 +82,4 @@ PathSet Store::printStorePathSet(const StorePathSet & paths) const
     return res;
 }
 
-std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s)
-{
-    size_t n = s.find("!");
-    return n == s.npos
-        ? std::make_pair(s, std::set<string>())
-        : std::make_pair(((std::string_view) s).substr(0, n),
-            tokenizeString<std::set<string>>(((std::string_view) s).substr(n + 1), ","));
-}
-
-StorePathWithOutputs Store::parsePathWithOutputs(const std::string & s)
-{
-    auto [path, outputs] = nix::parsePathWithOutputs(s);
-    return {parseStorePath(path), std::move(outputs)};
-}
-
 }
diff --git a/src/libstore/path.hh b/src/libstore/path.hh
index b03a0f69d..06ba0663b 100644
--- a/src/libstore/path.hh
+++ b/src/libstore/path.hh
@@ -69,16 +69,6 @@ typedef std::map<StorePath, std::optional<ContentAddress>> StorePathCAMap;
 /* Extension of derivations in the Nix store. */
 const std::string drvExtension = ".drv";
 
-struct StorePathWithOutputs
-{
-    StorePath path;
-    std::set<std::string> outputs;
-
-    std::string to_string(const Store & store) const;
-};
-
-std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s);
-
 }
 
 namespace std {
diff --git a/src/libstore/profiles.cc b/src/libstore/profiles.cc
index 5d1723886..73163424c 100644
--- a/src/libstore/profiles.cc
+++ b/src/libstore/profiles.cc
@@ -126,9 +126,9 @@ void deleteGeneration(const Path & profile, GenerationNumber gen)
 static void deleteGeneration2(const Path & profile, GenerationNumber gen, bool dryRun)
 {
     if (dryRun)
-        printInfo(format("would remove generation %1%") % gen);
+        notice("would remove profile version %1%", gen);
     else {
-        printInfo(format("removing generation %1%") % gen);
+        notice("removing profile version %1%", gen);
         deleteGeneration(profile, gen);
     }
 }
@@ -142,7 +142,7 @@ void deleteGenerations(const Path & profile, const std::set<GenerationNumber> &
     auto [gens, curGen] = findGenerations(profile);
 
     if (gensToDelete.count(*curGen))
-        throw Error("cannot delete current generation of profile %1%'", profile);
+        throw Error("cannot delete current version of profile %1%'", profile);
 
     for (auto & i : gens) {
         if (!gensToDelete.count(i.number)) continue;
@@ -211,12 +211,15 @@ void deleteGenerationsOlderThan(const Path & profile, time_t t, bool dryRun)
 
 void deleteGenerationsOlderThan(const Path & profile, const string & timeSpec, bool dryRun)
 {
+    if (timeSpec.empty() || timeSpec[timeSpec.size() - 1] != 'd')
+        throw UsageError("invalid number of days specifier '%1%', expected something like '14d'", timeSpec);
+
     time_t curTime = time(0);
     string strDays = string(timeSpec, 0, timeSpec.size() - 1);
     auto days = string2Int<int>(strDays);
 
     if (!days || *days < 1)
-        throw Error("invalid number of days specifier '%1%'", timeSpec);
+        throw UsageError("invalid number of days specifier '%1%'", timeSpec);
 
     time_t oldTime = curTime - *days * 24 * 3600;
 
@@ -233,6 +236,37 @@ void switchLink(Path link, Path target)
 }
 
 
+void switchGeneration(
+    const Path & profile,
+    std::optional<GenerationNumber> dstGen,
+    bool dryRun)
+{
+    PathLocks lock;
+    lockProfile(lock, profile);
+
+    auto [gens, curGen] = findGenerations(profile);
+
+    std::optional<Generation> dst;
+    for (auto & i : gens)
+        if ((!dstGen && i.number < curGen) ||
+            (dstGen && i.number == *dstGen))
+            dst = i;
+
+    if (!dst) {
+        if (dstGen)
+            throw Error("profile version %1% does not exist", *dstGen);
+        else
+            throw Error("no profile version older than the current (%1%) exists", curGen.value_or(0));
+    }
+
+    notice("switching profile from version %d to %d", curGen.value_or(0), dst->number);
+
+    if (dryRun) return;
+
+    switchLink(profile, dst->path);
+}
+
+
 void lockProfile(PathLocks & lock, const Path & profile)
 {
     lock.lockPaths({profile}, (format("waiting for lock on profile '%1%'") % profile).str());
diff --git a/src/libstore/profiles.hh b/src/libstore/profiles.hh
index be55a65d4..d100c970c 100644
--- a/src/libstore/profiles.hh
+++ b/src/libstore/profiles.hh
@@ -11,7 +11,7 @@ namespace nix {
 class StorePath;
 
 
-typedef unsigned int GenerationNumber;
+typedef uint64_t GenerationNumber;
 
 struct Generation
 {
@@ -46,6 +46,13 @@ void deleteGenerationsOlderThan(const Path & profile, const string & timeSpec, b
 
 void switchLink(Path link, Path target);
 
+/* Roll back a profile to the specified generation, or to the most
+   recent one older than the current. */
+void switchGeneration(
+    const Path & profile,
+    std::optional<GenerationNumber> dstGen,
+    bool dryRun);
+
 /* Ensure exclusive access to a profile.  Any command that modifies
    the profile first acquires this lock. */
 void lockProfile(PathLocks & lock, const Path & profile);
diff --git a/src/libstore/realisation.cc b/src/libstore/realisation.cc
index cd74af4ee..f871e6437 100644
--- a/src/libstore/realisation.cc
+++ b/src/libstore/realisation.cc
@@ -1,5 +1,6 @@
 #include "realisation.hh"
 #include "store-api.hh"
+#include "closure.hh"
 #include <nlohmann/json.hpp>
 
 namespace nix {
@@ -21,35 +22,142 @@ std::string DrvOutput::to_string() const {
     return strHash() + "!" + outputName;
 }
 
+std::set<Realisation> Realisation::closure(Store & store, const std::set<Realisation> & startOutputs)
+{
+    std::set<Realisation> res;
+    Realisation::closure(store, startOutputs, res);
+    return res;
+}
+
+void Realisation::closure(Store & store, const std::set<Realisation> & startOutputs, std::set<Realisation> & res)
+{
+    auto getDeps = [&](const Realisation& current) -> std::set<Realisation> {
+        std::set<Realisation> res;
+        for (auto& [currentDep, _] : current.dependentRealisations) {
+            if (auto currentRealisation = store.queryRealisation(currentDep))
+                res.insert(*currentRealisation);
+            else
+                throw Error(
+                    "Unrealised derivation '%s'", currentDep.to_string());
+        }
+        return res;
+    };
+
+    computeClosure<Realisation>(
+        startOutputs, res,
+        [&](const Realisation& current,
+            std::function<void(std::promise<std::set<Realisation>>&)>
+                processEdges) {
+            std::promise<std::set<Realisation>> promise;
+            try {
+                auto res = getDeps(current);
+                promise.set_value(res);
+            } catch (...) {
+                promise.set_exception(std::current_exception());
+            }
+            return processEdges(promise);
+        });
+}
+
 nlohmann::json Realisation::toJSON() const {
+    auto jsonDependentRealisations = nlohmann::json::object();
+    for (auto & [depId, depOutPath] : dependentRealisations)
+        jsonDependentRealisations.emplace(depId.to_string(), depOutPath.to_string());
     return nlohmann::json{
         {"id", id.to_string()},
         {"outPath", outPath.to_string()},
+        {"signatures", signatures},
+        {"dependentRealisations", jsonDependentRealisations},
     };
 }
 
 Realisation Realisation::fromJSON(
     const nlohmann::json& json,
     const std::string& whence) {
-    auto getField = [&](std::string fieldName) -> std::string {
+    auto getOptionalField = [&](std::string fieldName) -> std::optional<std::string> {
         auto fieldIterator = json.find(fieldName);
         if (fieldIterator == json.end())
+            return std::nullopt;
+        return *fieldIterator;
+    };
+    auto getField = [&](std::string fieldName) -> std::string {
+        if (auto field = getOptionalField(fieldName))
+            return *field;
+        else
             throw Error(
                 "Drv output info file '%1%' is corrupt, missing field %2%",
                 whence, fieldName);
-        return *fieldIterator;
     };
 
+    StringSet signatures;
+    if (auto signaturesIterator = json.find("signatures"); signaturesIterator != json.end())
+        signatures.insert(signaturesIterator->begin(), signaturesIterator->end());
+
+    std::map <DrvOutput, StorePath> dependentRealisations;
+    if (auto jsonDependencies = json.find("dependentRealisations"); jsonDependencies != json.end())
+        for (auto & [jsonDepId, jsonDepOutPath] : jsonDependencies->get<std::map<std::string, std::string>>())
+            dependentRealisations.insert({DrvOutput::parse(jsonDepId), StorePath(jsonDepOutPath)});
+
     return Realisation{
         .id = DrvOutput::parse(getField("id")),
         .outPath = StorePath(getField("outPath")),
+        .signatures = signatures,
+        .dependentRealisations = dependentRealisations,
     };
 }
 
+std::string Realisation::fingerprint() const
+{
+    auto serialized = toJSON();
+    serialized.erase("signatures");
+    return serialized.dump();
+}
+
+void Realisation::sign(const SecretKey & secretKey)
+{
+    signatures.insert(secretKey.signDetached(fingerprint()));
+}
+
+bool Realisation::checkSignature(const PublicKeys & publicKeys, const std::string & sig) const
+{
+    return verifyDetached(fingerprint(), sig, publicKeys);
+}
+
+size_t Realisation::checkSignatures(const PublicKeys & publicKeys) const
+{
+    // FIXME: Maybe we should return `maxSigs` if the realisation corresponds to
+    // an input-addressed one − because in that case the drv is enough to check
+    // it − but we can't know that here.
+
+    size_t good = 0;
+    for (auto & sig : signatures)
+        if (checkSignature(publicKeys, sig))
+            good++;
+    return good;
+}
+
 StorePath RealisedPath::path() const {
     return std::visit([](auto && arg) { return arg.getPath(); }, raw);
 }
 
+bool Realisation::isCompatibleWith(const Realisation & other) const
+{
+    assert (id == other.id);
+    if (outPath == other.outPath) {
+        if (dependentRealisations.empty() != other.dependentRealisations.empty()) {
+            warn(
+                "Encountered a realisation for '%s' with an empty set of "
+                "dependencies. This is likely an artifact from an older Nix. "
+                "I’ll try to fix the realisation if I can",
+                id.to_string());
+            return true;
+        } else if (dependentRealisations == other.dependentRealisations) {
+            return true;
+        }
+    }
+    return false;
+}
+
 void RealisedPath::closure(
     Store& store,
     const RealisedPath::Set& startPaths,
diff --git a/src/libstore/realisation.hh b/src/libstore/realisation.hh
index fc92d3c17..9070a6ee2 100644
--- a/src/libstore/realisation.hh
+++ b/src/libstore/realisation.hh
@@ -3,6 +3,7 @@
 #include "path.hh"
 #include <nlohmann/json_fwd.hpp>
 #include "comparator.hh"
+#include "crypto.hh"
 
 namespace nix {
 
@@ -25,9 +26,29 @@ struct Realisation {
     DrvOutput id;
     StorePath outPath;
 
+    StringSet signatures;
+
+    /**
+     * The realisations that are required for the current one to be valid.
+     *
+     * When importing this realisation, the store will first check that all its
+     * dependencies exist, and map to the correct output path
+     */
+    std::map<DrvOutput, StorePath> dependentRealisations;
+
     nlohmann::json toJSON() const;
     static Realisation fromJSON(const nlohmann::json& json, const std::string& whence);
 
+    std::string fingerprint() const;
+    void sign(const SecretKey &);
+    bool checkSignature(const PublicKeys & publicKeys, const std::string & sig) const;
+    size_t checkSignatures(const PublicKeys & publicKeys) const;
+
+    static std::set<Realisation> closure(Store &, const std::set<Realisation> &);
+    static void closure(Store &, const std::set<Realisation> &, std::set<Realisation> & res);
+
+    bool isCompatibleWith(const Realisation & other) const;
+
     StorePath getPath() const { return outPath; }
 
     GENERATE_CMP(Realisation, me->id, me->outPath);
diff --git a/src/libstore/references.cc b/src/libstore/references.cc
index 39c4970c6..c369b14ac 100644
--- a/src/libstore/references.cc
+++ b/src/libstore/references.cc
@@ -5,27 +5,29 @@
 
 #include <map>
 #include <cstdlib>
+#include <mutex>
 
 
 namespace nix {
 
 
-static unsigned int refLength = 32; /* characters */
+static size_t refLength = 32; /* characters */
 
 
-static void search(const unsigned char * s, size_t len,
-    StringSet & hashes, StringSet & seen)
+static void search(
+    std::string_view s,
+    StringSet & hashes,
+    StringSet & seen)
 {
-    static bool initialised = false;
+    static std::once_flag initialised;
     static bool isBase32[256];
-    if (!initialised) {
+    std::call_once(initialised, [](){
         for (unsigned int i = 0; i < 256; ++i) isBase32[i] = false;
         for (unsigned int i = 0; i < base32Chars.size(); ++i)
             isBase32[(unsigned char) base32Chars[i]] = true;
-        initialised = true;
-    }
+    });
 
-    for (size_t i = 0; i + refLength <= len; ) {
+    for (size_t i = 0; i + refLength <= s.size(); ) {
         int j;
         bool match = true;
         for (j = refLength - 1; j >= 0; --j)
@@ -35,7 +37,7 @@ static void search(const unsigned char * s, size_t len,
                 break;
             }
         if (!match) continue;
-        string ref((const char *) s + i, refLength);
+        std::string ref(s.substr(i, refLength));
         if (hashes.erase(ref)) {
             debug(format("found reference to '%1%' at offset '%2%'")
                   % ref % i);
@@ -46,69 +48,60 @@ static void search(const unsigned char * s, size_t len,
 }
 
 
-struct RefScanSink : Sink
+void RefScanSink::operator () (std::string_view data)
 {
-    StringSet hashes;
-    StringSet seen;
-
-    string tail;
-
-    RefScanSink() { }
-
-    void operator () (std::string_view data) override
-    {
-        /* It's possible that a reference spans the previous and current
-           fragment, so search in the concatenation of the tail of the
-           previous fragment and the start of the current fragment. */
-        string s = tail + std::string(data, 0, refLength);
-        search((const unsigned char *) s.data(), s.size(), hashes, seen);
-
-        search((const unsigned char *) data.data(), data.size(), hashes, seen);
-
-        size_t tailLen = data.size() <= refLength ? data.size() : refLength;
-        tail = std::string(tail, tail.size() < refLength - tailLen ? 0 : tail.size() - (refLength - tailLen));
-        tail.append({data.data() + data.size() - tailLen, tailLen});
-    }
-};
+    /* It's possible that a reference spans the previous and current
+       fragment, so search in the concatenation of the tail of the
+       previous fragment and the start of the current fragment. */
+    auto s = tail;
+    s.append(data.data(), refLength);
+    search(s, hashes, seen);
+
+    search(data, hashes, seen);
+
+    auto tailLen = std::min(data.size(), refLength);
+    auto rest = refLength - tailLen;
+    if (rest < tail.size())
+        tail = tail.substr(tail.size() - rest);
+    tail.append(data.data() + data.size() - tailLen, tailLen);
+}
 
 
-std::pair<PathSet, HashResult> scanForReferences(const string & path,
-    const PathSet & refs)
+std::pair<StorePathSet, HashResult> scanForReferences(
+    const string & path,
+    const StorePathSet & refs)
 {
     HashSink hashSink { htSHA256 };
     auto found = scanForReferences(hashSink, path, refs);
     auto hash = hashSink.finish();
-    return std::pair<PathSet, HashResult>(found, hash);
+    return std::pair<StorePathSet, HashResult>(found, hash);
 }
 
-PathSet scanForReferences(Sink & toTee,
-    const string & path, const PathSet & refs)
+StorePathSet scanForReferences(
+    Sink & toTee,
+    const Path & path,
+    const StorePathSet & refs)
 {
-    RefScanSink refsSink;
-    TeeSink sink { refsSink, toTee };
-    std::map<string, Path> backMap;
+    StringSet hashes;
+    std::map<std::string, StorePath> backMap;
 
     for (auto & i : refs) {
-        auto baseName = std::string(baseNameOf(i));
-        string::size_type pos = baseName.find('-');
-        if (pos == string::npos)
-            throw Error("bad reference '%1%'", i);
-        string s = string(baseName, 0, pos);
-        assert(s.size() == refLength);
-        assert(backMap.find(s) == backMap.end());
-        // parseHash(htSHA256, s);
-        refsSink.hashes.insert(s);
-        backMap[s] = i;
+        std::string hashPart(i.hashPart());
+        auto inserted = backMap.emplace(hashPart, i).second;
+        assert(inserted);
+        hashes.insert(hashPart);
     }
 
     /* Look for the hashes in the NAR dump of the path. */
+    RefScanSink refsSink(std::move(hashes));
+    TeeSink sink { refsSink, toTee };
     dumpPath(path, sink);
 
     /* Map the hashes found back to their store paths. */
-    PathSet found;
-    for (auto & i : refsSink.seen) {
-        std::map<string, Path>::iterator j;
-        if ((j = backMap.find(i)) == backMap.end()) abort();
+    StorePathSet found;
+    for (auto & i : refsSink.getResult()) {
+        auto j = backMap.find(i);
+        assert(j != backMap.end());
         found.insert(j->second);
     }
 
diff --git a/src/libstore/references.hh b/src/libstore/references.hh
index 4f12e6b21..a6119c861 100644
--- a/src/libstore/references.hh
+++ b/src/libstore/references.hh
@@ -1,13 +1,31 @@
 #pragma once
 
-#include "types.hh"
 #include "hash.hh"
+#include "path.hh"
 
 namespace nix {
 
-std::pair<PathSet, HashResult> scanForReferences(const Path & path, const PathSet & refs);
+std::pair<StorePathSet, HashResult> scanForReferences(const Path & path, const StorePathSet & refs);
 
-PathSet scanForReferences(Sink & toTee, const Path & path, const PathSet & refs);
+StorePathSet scanForReferences(Sink & toTee, const Path & path, const StorePathSet & refs);
+
+class RefScanSink : public Sink
+{
+    StringSet hashes;
+    StringSet seen;
+
+    std::string tail;
+
+public:
+
+    RefScanSink(StringSet && hashes) : hashes(hashes)
+    { }
+
+    StringSet & getResult()
+    { return seen; }
+
+    void operator () (std::string_view data) override;
+};
 
 struct RewritingSink : Sink
 {
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 0d884389a..fa5ea8af7 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -1,5 +1,6 @@
 #include "serialise.hh"
 #include "util.hh"
+#include "path-with-outputs.hh"
 #include "remote-fs-accessor.hh"
 #include "remote-store.hh"
 #include "worker-protocol.hh"
@@ -50,6 +51,19 @@ void write(const Store & store, Sink & out, const ContentAddress & ca)
     out << renderContentAddress(ca);
 }
 
+
+DerivedPath read(const Store & store, Source & from, Phantom<DerivedPath> _)
+{
+    auto s = readString(from);
+    return DerivedPath::parse(store, s);
+}
+
+void write(const Store & store, Sink & out, const DerivedPath & req)
+{
+    out << req.to_string(store);
+}
+
+
 Realisation read(const Store & store, Source & from, Phantom<Realisation> _)
 {
     std::string rawInput = readString(from);
@@ -58,13 +72,23 @@ Realisation read(const Store & store, Source & from, Phantom<Realisation> _)
         "remote-protocol"
     );
 }
+
 void write(const Store & store, Sink & out, const Realisation & realisation)
-{ out << realisation.toJSON().dump(); }
+{
+    out << realisation.toJSON().dump();
+}
+
 
 DrvOutput read(const Store & store, Source & from, Phantom<DrvOutput> _)
-{ return DrvOutput::parse(readString(from)); }
+{
+    return DrvOutput::parse(readString(from));
+}
+
 void write(const Store & store, Sink & out, const DrvOutput & drvOutput)
-{ out << drvOutput.to_string(); }
+{
+    out << drvOutput.to_string();
+}
+
 
 std::optional<StorePath> read(const Store & store, Source & from, Phantom<std::optional<StorePath>> _)
 {
@@ -138,8 +162,19 @@ void RemoteStore::initConnection(Connection & conn)
     try {
         conn.to << WORKER_MAGIC_1;
         conn.to.flush();
-        unsigned int magic = readInt(conn.from);
-        if (magic != WORKER_MAGIC_2) throw Error("protocol mismatch");
+        StringSink saved;
+        try {
+            TeeSource tee(conn.from, saved);
+            unsigned int magic = readInt(tee);
+            if (magic != WORKER_MAGIC_2)
+                throw Error("protocol mismatch");
+        } catch (SerialisationError & e) {
+            /* In case the other side is waiting for our input, close
+               it. */
+            conn.closeWrite();
+            auto msg = conn.from.drain();
+            throw Error("protocol mismatch, got '%s'", chomp(*saved.s + msg));
+        }
 
         conn.from >> conn.daemonVersion;
         if (GET_PROTOCOL_MAJOR(conn.daemonVersion) != GET_PROTOCOL_MAJOR(PROTOCOL_VERSION))
@@ -198,6 +233,7 @@ void RemoteStore::setOptions(Connection & conn)
         overrides.erase(settings.buildCores.name);
         overrides.erase(settings.useSubstitutes.name);
         overrides.erase(loggerSettings.showTrace.name);
+        overrides.erase(settings.experimentalFeatures.name);
         conn.to << overrides.size();
         for (auto & i : overrides)
             conn.to << i.first << i.second.value;
@@ -362,23 +398,6 @@ void RemoteStore::querySubstitutablePathInfos(const StorePathCAMap & pathsMap, S
 }
 
 
-ref<const ValidPathInfo> RemoteStore::readValidPathInfo(ConnectionHandle & conn, const StorePath & path)
-{
-    auto deriver = readString(conn->from);
-    auto narHash = Hash::parseAny(readString(conn->from), htSHA256);
-    auto info = make_ref<ValidPathInfo>(path, narHash);
-    if (deriver != "") info->deriver = parseStorePath(deriver);
-    info->references = worker_proto::read(*this, conn->from, Phantom<StorePathSet> {});
-    conn->from >> info->registrationTime >> info->narSize;
-    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 16) {
-        conn->from >> info->ultimate;
-        info->sigs = readStrings<StringSet>(conn->from);
-        info->ca = parseContentAddressOpt(readString(conn->from));
-    }
-    return info;
-}
-
-
 void RemoteStore::queryPathInfoUncached(const StorePath & path,
     Callback<std::shared_ptr<const ValidPathInfo>> callback) noexcept
 {
@@ -399,7 +418,8 @@ void RemoteStore::queryPathInfoUncached(const StorePath & path,
                 bool valid; conn->from >> valid;
                 if (!valid) throw InvalidPath("path '%s' is not valid", printStorePath(path));
             }
-            info = readValidPathInfo(conn, path);
+            info = std::make_shared<ValidPathInfo>(
+                ValidPathInfo::read(conn->from, *this, GET_PROTOCOL_MINOR(conn->daemonVersion), StorePath{path}));
         }
         callback(std::move(info));
     } catch (...) { callback.rethrow(); }
@@ -501,20 +521,20 @@ ref<const ValidPathInfo> RemoteStore::addCAToStore(
             });
         }
 
-        auto path = parseStorePath(readString(conn->from));
-        return readValidPathInfo(conn, path);
+        return make_ref<ValidPathInfo>(
+            ValidPathInfo::read(conn->from, *this, GET_PROTOCOL_MINOR(conn->daemonVersion)));
     }
     else {
         if (repair) throw Error("repairing is not supported when building through the Nix daemon protocol < 1.25");
 
         std::visit(overloaded {
-            [&](TextHashMethod thm) -> void {
+            [&](const TextHashMethod & thm) -> void {
                 std::string s = dump.drain();
                 conn->to << wopAddTextToStore << name << s;
                 worker_proto::write(*this, conn->to, references);
                 conn.processStderr();
             },
-            [&](FixedOutputHashMethod fohm) -> void {
+            [&](const FixedOutputHashMethod & fohm) -> void {
                 conn->to
                     << wopAddToStore
                     << name
@@ -618,6 +638,25 @@ void RemoteStore::addToStore(const ValidPathInfo & info, Source & source,
 }
 
 
+void RemoteStore::addMultipleToStore(
+    Source & source,
+    RepairFlag repair,
+    CheckSigsFlag checkSigs)
+{
+    if (GET_PROTOCOL_MINOR(getConnection()->daemonVersion) >= 32) {
+        auto conn(getConnection());
+        conn->to
+            << wopAddMultipleToStore
+            << repair
+            << !checkSigs;
+        conn.withFramedSink([&](Sink & sink) {
+            source.drainInto(sink);
+        });
+    } else
+        Store::addMultipleToStore(source, repair, checkSigs);
+}
+
+
 StorePath RemoteStore::addTextToStore(const string & name, const string & s,
     const StorePathSet & references, RepairFlag repair)
 {
@@ -629,8 +668,12 @@ void RemoteStore::registerDrvOutput(const Realisation & info)
 {
     auto conn(getConnection());
     conn->to << wopRegisterDrvOutput;
-    conn->to << info.id.to_string();
-    conn->to << std::string(info.outPath.to_string());
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) < 31) {
+        conn->to << info.id.to_string();
+        conn->to << std::string(info.outPath.to_string());
+    } else {
+        worker_proto::write(*this, conn->to, info);
+    }
     conn.processStderr();
 }
 
@@ -640,22 +683,59 @@ std::optional<const Realisation> RemoteStore::queryRealisation(const DrvOutput &
     conn->to << wopQueryRealisation;
     conn->to << id.to_string();
     conn.processStderr();
-    auto outPaths = worker_proto::read(*this, conn->from, Phantom<std::set<StorePath>>{});
-    if (outPaths.empty())
-        return std::nullopt;
-    return {Realisation{.id = id, .outPath = *outPaths.begin()}};
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) < 31) {
+        auto outPaths = worker_proto::read(*this, conn->from, Phantom<std::set<StorePath>>{});
+        if (outPaths.empty())
+            return std::nullopt;
+        return {Realisation{.id = id, .outPath = *outPaths.begin()}};
+    } else {
+        auto realisations = worker_proto::read(*this, conn->from, Phantom<std::set<Realisation>>{});
+        if (realisations.empty())
+            return std::nullopt;
+        return *realisations.begin();
+    }
 }
 
+static void writeDerivedPaths(RemoteStore & store, ConnectionHandle & conn, const std::vector<DerivedPath> & reqs)
+{
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 30) {
+        worker_proto::write(store, conn->to, reqs);
+    } else {
+        Strings ss;
+        for (auto & p : reqs) {
+            auto sOrDrvPath = StorePathWithOutputs::tryFromDerivedPath(p);
+            std::visit(overloaded {
+                [&](const StorePathWithOutputs & s) {
+                    ss.push_back(s.to_string(store));
+                },
+                [&](const StorePath & drvPath) {
+                    throw Error("trying to request '%s', but daemon protocol %d.%d is too old (< 1.29) to request a derivation file",
+                        store.printStorePath(drvPath),
+                        GET_PROTOCOL_MAJOR(conn->daemonVersion),
+                        GET_PROTOCOL_MINOR(conn->daemonVersion));
+                },
+            }, sOrDrvPath);
+        }
+        conn->to << ss;
+    }
+}
 
-void RemoteStore::buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode)
+void RemoteStore::buildPaths(const std::vector<DerivedPath> & drvPaths, BuildMode buildMode, std::shared_ptr<Store> evalStore)
 {
+    if (evalStore && evalStore.get() != this) {
+        /* The remote doesn't have a way to access evalStore, so copy
+           the .drvs. */
+        RealisedPath::Set drvPaths2;
+        for (auto & i : drvPaths)
+            if (auto p = std::get_if<DerivedPath::Built>(&i))
+                drvPaths2.insert(p->drvPath);
+        copyClosure(*evalStore, *this, drvPaths2);
+    }
+
     auto conn(getConnection());
     conn->to << wopBuildPaths;
     assert(GET_PROTOCOL_MINOR(conn->daemonVersion) >= 13);
-    Strings ss;
-    for (auto & p : drvPaths)
-        ss.push_back(p.to_string(*this));
-    conn->to << ss;
+    writeDerivedPaths(*this, conn, drvPaths);
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 15)
         conn->to << buildMode;
     else
@@ -677,10 +757,12 @@ BuildResult RemoteStore::buildDerivation(const StorePath & drvPath, const BasicD
     conn->to << buildMode;
     conn.processStderr();
     BuildResult res;
-    unsigned int status;
-    conn->from >> status >> res.errorMsg;
-    res.status = (BuildResult::Status) status;
-    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 0xc) {
+    res.status = (BuildResult::Status) readInt(conn->from);
+    conn->from >> res.errorMsg;
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 29) {
+        conn->from >> res.timesBuilt >> res.isNonDeterministic >> res.startTime >> res.stopTime;
+    }
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 28) {
         auto builtOutputs = worker_proto::read(*this, conn->from, Phantom<DrvOutputs> {});
         res.builtOutputs = builtOutputs;
     }
@@ -792,7 +874,7 @@ void RemoteStore::addSignatures(const StorePath & storePath, const StringSet & s
 }
 
 
-void RemoteStore::queryMissing(const std::vector<StorePathWithOutputs> & targets,
+void RemoteStore::queryMissing(const std::vector<DerivedPath> & targets,
     StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
     uint64_t & downloadSize, uint64_t & narSize)
 {
@@ -803,10 +885,7 @@ void RemoteStore::queryMissing(const std::vector<StorePathWithOutputs> & targets
             // to prevent a deadlock.
             goto fallback;
         conn->to << wopQueryMissing;
-        Strings ss;
-        for (auto & p : targets)
-            ss.push_back(p.to_string(*this));
-        conn->to << ss;
+        writeDerivedPaths(*this, conn, targets);
         conn.processStderr();
         willBuild = worker_proto::read(*this, conn->from, Phantom<StorePathSet> {});
         willSubstitute = worker_proto::read(*this, conn->from, Phantom<StorePathSet> {});
@@ -947,14 +1026,14 @@ std::exception_ptr RemoteStore::Connection::processStderr(Sink * sink, Source *
     return nullptr;
 }
 
-void ConnectionHandle::withFramedSink(std::function<void(Sink &sink)> fun)
+void ConnectionHandle::withFramedSink(std::function<void(Sink & sink)> fun)
 {
     (*this)->to.flush();
 
     std::exception_ptr ex;
 
-    /* Handle log messages / exceptions from the remote on a
-        separate thread. */
+    /* Handle log messages / exceptions from the remote on a separate
+       thread. */
     std::thread stderrThread([&]()
     {
         try {
@@ -987,7 +1066,6 @@ void ConnectionHandle::withFramedSink(std::function<void(Sink &sink)> fun)
     stderrThread.join();
     if (ex)
         std::rethrow_exception(ex);
-
 }
 
 }
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index b3a9910a3..ac1eaa19e 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -78,6 +78,11 @@ public:
     void addToStore(const ValidPathInfo & info, Source & nar,
         RepairFlag repair, CheckSigsFlag checkSigs) override;
 
+    void addMultipleToStore(
+        Source & source,
+        RepairFlag repair,
+        CheckSigsFlag checkSigs) override;
+
     StorePath addTextToStore(const string & name, const string & s,
         const StorePathSet & references, RepairFlag repair) override;
 
@@ -85,7 +90,7 @@ public:
 
     std::optional<const Realisation> queryRealisation(const DrvOutput &) override;
 
-    void buildPaths(const std::vector<StorePathWithOutputs> & paths, BuildMode buildMode) override;
+    void buildPaths(const std::vector<DerivedPath> & paths, BuildMode buildMode, std::shared_ptr<Store> evalStore) override;
 
     BuildResult buildDerivation(const StorePath & drvPath, const BasicDerivation & drv,
         BuildMode buildMode) override;
@@ -108,7 +113,7 @@ public:
 
     void addSignatures(const StorePath & storePath, const StringSet & sigs) override;
 
-    void queryMissing(const std::vector<StorePathWithOutputs> & targets,
+    void queryMissing(const std::vector<DerivedPath> & targets,
         StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
         uint64_t & downloadSize, uint64_t & narSize) override;
 
@@ -120,7 +125,6 @@ public:
 
     struct Connection
     {
-        AutoCloseFD fd;
         FdSink to;
         FdSource from;
         unsigned int daemonVersion;
@@ -128,6 +132,8 @@ public:
 
         virtual ~Connection();
 
+        virtual void closeWrite() = 0;
+
         std::exception_ptr processStderr(Sink * sink = 0, Source * source = 0, bool flush = true);
     };
 
@@ -151,8 +157,6 @@ protected:
 
     virtual void narFromPath(const StorePath & path, Sink & sink) override;
 
-    ref<const ValidPathInfo> readValidPathInfo(ConnectionHandle & conn, const StorePath & path);
-
 private:
 
     std::atomic_bool failed{false};
diff --git a/src/libstore/s3-binary-cache-store.cc b/src/libstore/s3-binary-cache-store.cc
index 6bfbee044..7accad7f4 100644
--- a/src/libstore/s3-binary-cache-store.cc
+++ b/src/libstore/s3-binary-cache-store.cc
@@ -209,7 +209,7 @@ struct S3BinaryCacheStoreImpl : virtual S3BinaryCacheStoreConfig, public virtual
     S3Helper s3Helper;
 
     S3BinaryCacheStoreImpl(
-        const std::string & scheme,
+        const std::string & uriScheme,
         const std::string & bucketName,
         const Params & params)
         : StoreConfig(params)
@@ -232,8 +232,8 @@ struct S3BinaryCacheStoreImpl : virtual S3BinaryCacheStoreConfig, public virtual
     void init() override
     {
         if (auto cacheInfo = diskCache->cacheExists(getUri())) {
-            wantMassQuery.setDefault(cacheInfo->wantMassQuery ? "true" : "false");
-            priority.setDefault(fmt("%d", cacheInfo->priority));
+            wantMassQuery.setDefault(cacheInfo->wantMassQuery);
+            priority.setDefault(cacheInfo->priority);
         } else {
             BinaryCacheStore::init();
             diskCache->createCache(getUri(), storeDir, wantMassQuery, priority);
diff --git a/src/libstore/sandbox-defaults.sb b/src/libstore/sandbox-defaults.sb
index 351037822..41893e6dd 100644
--- a/src/libstore/sandbox-defaults.sb
+++ b/src/libstore/sandbox-defaults.sb
@@ -32,7 +32,9 @@
        (literal "/tmp") (subpath TMPDIR))
 
 ; Some packages like to read the system version.
-(allow file-read* (literal "/System/Library/CoreServices/SystemVersion.plist"))
+(allow file-read*
+       (literal "/System/Library/CoreServices/SystemVersion.plist")
+       (literal "/System/Library/CoreServices/SystemVersionCompat.plist"))
 
 ; Without this line clang cannot write to /dev/null, breaking some configure tests.
 (allow file-read-metadata (literal "/dev"))
@@ -95,3 +97,7 @@
 ; This is used by /bin/sh on macOS 10.15 and later.
 (allow file*
        (literal "/private/var/select/sh"))
+
+; Allow Rosetta 2 to run x86_64 binaries on aarch64-darwin.
+(allow file-read*
+       (subpath "/Library/Apple/usr/libexec/oah"))
diff --git a/src/libstore/serve-protocol.hh b/src/libstore/serve-protocol.hh
index 0a17387cb..3f76baa82 100644
--- a/src/libstore/serve-protocol.hh
+++ b/src/libstore/serve-protocol.hh
@@ -5,7 +5,7 @@ namespace nix {
 #define SERVE_MAGIC_1 0x390c9deb
 #define SERVE_MAGIC_2 0x5452eecb
 
-#define SERVE_PROTOCOL_VERSION 0x206
+#define SERVE_PROTOCOL_VERSION (2 << 8 | 7)
 #define GET_PROTOCOL_MAJOR(x) ((x) & 0xff00)
 #define GET_PROTOCOL_MINOR(x) ((x) & 0x00ff)
 
diff --git a/src/libstore/ssh-store.cc b/src/libstore/ssh-store.cc
index 17c258201..bb03daef4 100644
--- a/src/libstore/ssh-store.cc
+++ b/src/libstore/ssh-store.cc
@@ -13,6 +13,7 @@ struct SSHStoreConfig : virtual RemoteStoreConfig
     using RemoteStoreConfig::RemoteStoreConfig;
 
     const Setting<Path> sshKey{(StoreConfig*) this, "", "ssh-key", "path to an SSH private key"};
+    const Setting<std::string> sshPublicHostKey{(StoreConfig*) this, "", "base64-ssh-public-host-key", "The public half of the host's SSH key"};
     const Setting<bool> compress{(StoreConfig*) this, false, "compress", "whether to compress the connection"};
     const Setting<Path> remoteProgram{(StoreConfig*) this, "nix-daemon", "remote-program", "path to the nix-daemon executable on the remote system"};
     const Setting<std::string> remoteStore{(StoreConfig*) this, "", "remote-store", "URI of the store on the remote system"};
@@ -34,6 +35,7 @@ public:
         , master(
             host,
             sshKey,
+            sshPublicHostKey,
             // Use SSH master only if using more than 1 connection.
             connections->capacity() > 1,
             compress)
@@ -55,6 +57,11 @@ private:
     struct Connection : RemoteStore::Connection
     {
         std::unique_ptr<SSHMaster::Connection> sshConn;
+
+        void closeWrite() override
+        {
+            sshConn->in.close();
+        }
     };
 
     ref<RemoteStore::Connection> openConnection() override;
diff --git a/src/libstore/ssh.cc b/src/libstore/ssh.cc
index 84548a6e4..93f72675d 100644
--- a/src/libstore/ssh.cc
+++ b/src/libstore/ssh.cc
@@ -2,24 +2,37 @@
 
 namespace nix {
 
-SSHMaster::SSHMaster(const std::string & host, const std::string & keyFile, bool useMaster, bool compress, int logFD)
+SSHMaster::SSHMaster(const std::string & host, const std::string & keyFile, const std::string & sshPublicHostKey, bool useMaster, bool compress, int logFD)
     : host(host)
     , fakeSSH(host == "localhost")
     , keyFile(keyFile)
+    , sshPublicHostKey(sshPublicHostKey)
     , useMaster(useMaster && !fakeSSH)
     , compress(compress)
     , logFD(logFD)
 {
     if (host == "" || hasPrefix(host, "-"))
         throw Error("invalid SSH host name '%s'", host);
+
+    auto state(state_.lock());
+    state->tmpDir = std::make_unique<AutoDelete>(createTempDir("", "nix", true, true, 0700));
 }
 
 void SSHMaster::addCommonSSHOpts(Strings & args)
 {
+    auto state(state_.lock());
+
     for (auto & i : tokenizeString<Strings>(getEnv("NIX_SSHOPTS").value_or("")))
         args.push_back(i);
     if (!keyFile.empty())
         args.insert(args.end(), {"-i", keyFile});
+    if (!sshPublicHostKey.empty()) {
+        Path fileName = (Path) *state->tmpDir + "/host-key";
+        auto p = host.rfind("@");
+        string thost = p != string::npos ? string(host, p + 1) : host;
+        writeFile(fileName, thost + " " + base64Decode(sshPublicHostKey) + "\n");
+        args.insert(args.end(), {"-oUserKnownHostsFile=" + fileName});
+    }
     if (compress)
         args.push_back("-C");
 }
@@ -37,7 +50,7 @@ std::unique_ptr<SSHMaster::Connection> SSHMaster::startCommand(const std::string
     options.dieWithParent = false;
 
     conn->sshPid = startProcess([&]() {
-        restoreSignals();
+        restoreProcessContext();
 
         close(in.writeSide.get());
         close(out.readSide.get());
@@ -87,7 +100,6 @@ Path SSHMaster::startMaster()
 
     if (state->sshMaster != -1) return state->socketPath;
 
-    state->tmpDir = std::make_unique<AutoDelete>(createTempDir("", "nix", true, true, 0700));
 
     state->socketPath = (Path) *state->tmpDir + "/ssh.sock";
 
@@ -98,7 +110,7 @@ Path SSHMaster::startMaster()
     options.dieWithParent = false;
 
     state->sshMaster = startProcess([&]() {
-        restoreSignals();
+        restoreProcessContext();
 
         close(out.readSide.get());
 
diff --git a/src/libstore/ssh.hh b/src/libstore/ssh.hh
index 4f0f0bd29..dabbcedda 100644
--- a/src/libstore/ssh.hh
+++ b/src/libstore/ssh.hh
@@ -12,6 +12,7 @@ private:
     const std::string host;
     bool fakeSSH;
     const std::string keyFile;
+    const std::string sshPublicHostKey;
     const bool useMaster;
     const bool compress;
     const int logFD;
@@ -29,7 +30,7 @@ private:
 
 public:
 
-    SSHMaster(const std::string & host, const std::string & keyFile, bool useMaster, bool compress, int logFD = -1);
+    SSHMaster(const std::string & host, const std::string & keyFile, const std::string & sshPublicHostKey, bool useMaster, bool compress, int logFD = -1);
 
     struct Connection
     {
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index e6a4f33ba..49bc91614 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -9,6 +9,7 @@
 #include "url.hh"
 #include "archive.hh"
 #include "callback.hh"
+#include "remote-store.hh"
 
 #include <regex>
 
@@ -53,13 +54,6 @@ StorePath Store::followLinksToStorePath(std::string_view path) const
 }
 
 
-StorePathWithOutputs Store::followLinksToStorePathWithOutputs(std::string_view path) const
-{
-    auto [path2, outputs] = nix::parsePathWithOutputs(path);
-    return StorePathWithOutputs { followLinksToStorePath(path2), std::move(outputs) };
-}
-
-
 /* Store paths have the following form:
 
    <realized-path> = <store>/<h>-<name>
@@ -205,10 +199,10 @@ StorePath Store::makeFixedOutputPathFromCA(std::string_view name, ContentAddress
 {
     // New template
     return std::visit(overloaded {
-        [&](TextHash th) {
+        [&](const TextHash & th) {
             return makeTextPath(name, th.hash, references);
         },
-        [&](FixedOutputHash fsh) {
+        [&](const FixedOutputHash & fsh) {
             return makeFixedOutputPath(fsh.method, fsh.hash, name, references, hasSelfReference);
         }
     }, ca);
@@ -256,6 +250,20 @@ StorePath Store::addToStore(const string & name, const Path & _srcPath,
 }
 
 
+void Store::addMultipleToStore(
+    Source & source,
+    RepairFlag repair,
+    CheckSigsFlag checkSigs)
+{
+    auto expected = readNum<uint64_t>(source);
+    for (uint64_t i = 0; i < expected; ++i) {
+        auto info = ValidPathInfo::read(source, *this, 16);
+        info.ultimate = false;
+        addToStore(info, source, repair, checkSigs);
+    }
+}
+
+
 /*
 The aim of this function is to compute in one pass the correct ValidPathInfo for
 the files that we are trying to add to the store. To accomplish that in one
@@ -344,6 +352,13 @@ ValidPathInfo Store::addToStoreSlow(std::string_view name, const Path & srcPath,
     return info;
 }
 
+StringSet StoreConfig::getDefaultSystemFeatures()
+{
+    auto res = settings.systemFeatures.get();
+    if (settings.isExperimentalFeatureEnabled("ca-derivations"))
+        res.insert("ca-derivations");
+    return res;
+}
 
 Store::Store(const Params & params)
     : StoreConfig(params)
@@ -536,10 +551,10 @@ void Store::queryPathInfo(const StorePath & storePath,
 
 void Store::substitutePaths(const StorePathSet & paths)
 {
-    std::vector<StorePathWithOutputs> paths2;
+    std::vector<DerivedPath> paths2;
     for (auto & path : paths)
         if (!path.isDerivation())
-            paths2.push_back({path});
+            paths2.push_back(DerivedPath::Opaque{path});
     uint64_t downloadSize, narSize;
     StorePathSet willBuild, willSubstitute, unknown;
     queryMissing(paths2,
@@ -547,8 +562,8 @@ void Store::substitutePaths(const StorePathSet & paths)
 
     if (!willSubstitute.empty())
         try {
-            std::vector<StorePathWithOutputs> subs;
-            for (auto & p : willSubstitute) subs.push_back({p});
+            std::vector<DerivedPath> subs;
+            for (auto & p : willSubstitute) subs.push_back(DerivedPath::Opaque{p});
             buildPaths(subs);
         } catch (Error & e) {
             logWarning(e.info());
@@ -634,6 +649,42 @@ string Store::makeValidityRegistration(const StorePathSet & paths,
 }
 
 
+StorePathSet Store::exportReferences(const StorePathSet & storePaths, const StorePathSet & inputPaths)
+{
+    StorePathSet paths;
+
+    for (auto & storePath : storePaths) {
+        if (!inputPaths.count(storePath))
+            throw BuildError("cannot export references of path '%s' because it is not in the input closure of the derivation", printStorePath(storePath));
+
+        computeFSClosure({storePath}, paths);
+    }
+
+    /* If there are derivations in the graph, then include their
+       outputs as well.  This is useful if you want to do things
+       like passing all build-time dependencies of some path to a
+       derivation that builds a NixOS DVD image. */
+    auto paths2 = paths;
+
+    for (auto & j : paths2) {
+        if (j.isDerivation()) {
+            Derivation drv = derivationFromPath(j);
+            for (auto & k : drv.outputsAndOptPaths(*this)) {
+                if (!k.second.second)
+                    /* FIXME: I am confused why we are calling
+                       `computeFSClosure` on the output path, rather than
+                       derivation itself. That doesn't seem right to me, so I
+                       won't try to implemented this for CA derivations. */
+                    throw UnimplementedError("exportReferences on CA derivations is not yet implemented");
+                computeFSClosure(*k.second.second, paths);
+            }
+        }
+    }
+
+    return paths;
+}
+
+
 void Store::pathInfoToJSON(JSONPlaceholder & jsonOut, const StorePathSet & storePaths,
     bool includeImpureInfo, bool showClosureSize,
     Base hashBase,
@@ -734,30 +785,43 @@ const Store::Stats & Store::getStats()
 }
 
 
-void copyStorePath(ref<Store> srcStore, ref<Store> dstStore,
-    const StorePath & storePath, RepairFlag repair, CheckSigsFlag checkSigs)
+static std::string makeCopyPathMessage(
+    std::string_view srcUri,
+    std::string_view dstUri,
+    std::string_view storePath)
 {
-    auto srcUri = srcStore->getUri();
-    auto dstUri = dstStore->getUri();
+    return srcUri == "local" || srcUri == "daemon"
+        ? fmt("copying path '%s' to '%s'", storePath, dstUri)
+        : dstUri == "local" || dstUri == "daemon"
+        ? fmt("copying path '%s' from '%s'", storePath, srcUri)
+        : fmt("copying path '%s' from '%s' to '%s'", storePath, srcUri, dstUri);
+}
+
 
+void copyStorePath(
+    Store & srcStore,
+    Store & dstStore,
+    const StorePath & storePath,
+    RepairFlag repair,
+    CheckSigsFlag checkSigs)
+{
+    auto srcUri = srcStore.getUri();
+    auto dstUri = dstStore.getUri();
+    auto storePathS = srcStore.printStorePath(storePath);
     Activity act(*logger, lvlInfo, actCopyPath,
-        srcUri == "local" || srcUri == "daemon"
-        ? fmt("copying path '%s' to '%s'", srcStore->printStorePath(storePath), dstUri)
-          : dstUri == "local" || dstUri == "daemon"
-        ? fmt("copying path '%s' from '%s'", srcStore->printStorePath(storePath), srcUri)
-          : fmt("copying path '%s' from '%s' to '%s'", srcStore->printStorePath(storePath), srcUri, dstUri),
-        {srcStore->printStorePath(storePath), srcUri, dstUri});
+        makeCopyPathMessage(srcUri, dstUri, storePathS),
+        {storePathS, srcUri, dstUri});
     PushActivity pact(act.id);
 
-    auto info = srcStore->queryPathInfo(storePath);
+    auto info = srcStore.queryPathInfo(storePath);
 
     uint64_t total = 0;
 
     // recompute store path on the chance dstStore does it differently
     if (info->ca && info->references.empty()) {
         auto info2 = make_ref<ValidPathInfo>(*info);
-        info2->path = dstStore->makeFixedOutputPathFromCA(info->path.name(), *info->ca);
-        if (dstStore->storeDir == srcStore->storeDir)
+        info2->path = dstStore.makeFixedOutputPathFromCA(info->path.name(), *info->ca);
+        if (dstStore.storeDir == srcStore.storeDir)
             assert(info->path == info2->path);
         info = info2;
     }
@@ -774,64 +838,90 @@ void copyStorePath(ref<Store> srcStore, ref<Store> dstStore,
             act.progress(total, info->narSize);
         });
         TeeSink tee { sink, progressSink };
-        srcStore->narFromPath(storePath, tee);
+        srcStore.narFromPath(storePath, tee);
     }, [&]() {
-           throw EndOfFile("NAR for '%s' fetched from '%s' is incomplete", srcStore->printStorePath(storePath), srcStore->getUri());
+           throw EndOfFile("NAR for '%s' fetched from '%s' is incomplete", srcStore.printStorePath(storePath), srcStore.getUri());
     });
 
-    dstStore->addToStore(*info, *source, repair, checkSigs);
+    dstStore.addToStore(*info, *source, repair, checkSigs);
 }
 
 
-void copyStorePathAdapter(ref<Store> srcStore, ref<Store> dstStore,
+void copyStorePathAdapter(Store & srcStore, Store & dstStore,
     const ValidPathInfo & info, RepairFlag repair, CheckSigsFlag checkSigs)
 {
     copyStorePath(srcStore, dstStore, info.path, repair, checkSigs);
 }
 
-void copyOrBuildStorePath(ref<Store> srcStore, ref<Store> dstStore,
+void copyOrBuildStorePath(Store & srcStore, Store & dstStore,
     const ValidPathInfo & info, RepairFlag repair, CheckSigsFlag checkSigs)
 {
     auto storePath = info.path;
-    if (dstStore->isTrusting || info.ca) {
+    if (dstStore.isTrusting || info.ca) {
         copyStorePath(srcStore, dstStore, storePath, repair, checkSigs);
-    } else if (info.deriver && dstStore->storeDir == srcStore->storeDir) {
+    } else if (info.deriver && dstStore.storeDir == srcStore.storeDir) {
         auto drvPath = *info.deriver;
-        auto outputMap = srcStore->queryDerivationOutputMap(drvPath);
+        auto outputMap = srcStore.queryDerivationOutputMap(drvPath);
         auto p = std::find_if(outputMap.begin(), outputMap.end(), [&](auto & i) {
             return i.second == storePath;
         });
         // drv file is always CA
-        srcStore->ensurePath(drvPath);
+        srcStore.ensurePath(drvPath);
         copyStorePath(srcStore, dstStore, drvPath, repair, checkSigs);
-        dstStore->buildPaths({{
-            drvPath,
-            p != outputMap.end() ? StringSet { p->first } : StringSet {},
-        }});
+        dstStore.buildPaths({
+            DerivedPath::Built {
+                .drvPath = drvPath,
+                .outputs = p != outputMap.end() ? StringSet { p->first } : StringSet {},
+            },
+        });
     } else {
-        dstStore->ensurePath(storePath);
+        dstStore.ensurePath(storePath);
     }
 }
 
 
-std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStore, const RealisedPath::Set & paths,
-    RepairFlag repair, CheckSigsFlag checkSigs, SubstituteFlag substitute,
-    std::function<void(ref<Store>, ref<Store>, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl)
+std::map<StorePath, StorePath> copyPaths(
+    Store & srcStore,
+    Store & dstStore,
+    const RealisedPath::Set & paths,
+    RepairFlag repair,
+    CheckSigsFlag checkSigs,
+    SubstituteFlag substitute,
+    std::function<void(Store &, Store &, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl)
 {
     StorePathSet storePaths;
-    std::set<Realisation> realisations;
+    std::set<Realisation> toplevelRealisations;
     for (auto & path : paths) {
         storePaths.insert(path.path());
         if (auto realisation = std::get_if<Realisation>(&path.raw)) {
             settings.requireExperimentalFeature("ca-derivations");
-            realisations.insert(*realisation);
+            toplevelRealisations.insert(*realisation);
         }
     }
     auto pathsMap = copyPaths(srcStore, dstStore, storePaths, repair, checkSigs, substitute, copyStorePathImpl);
+
+    ThreadPool pool;
+
     try {
-        for (auto & realisation : realisations) {
-            dstStore->registerDrvOutput(realisation);
-        }
+        // Copy the realisation closure
+        processGraph<Realisation>(
+            pool, Realisation::closure(srcStore, toplevelRealisations),
+            [&](const Realisation & current) -> std::set<Realisation> {
+                std::set<Realisation> children;
+                for (const auto & [drvOutput, _] : current.dependentRealisations) {
+                    auto currentChild = srcStore.queryRealisation(drvOutput);
+                    if (!currentChild)
+                        throw Error(
+                            "incomplete realisation closure: '%s' is a "
+                            "dependency of '%s' but isn't registered",
+                            drvOutput.to_string(), current.id.to_string());
+                    children.insert(*currentChild);
+                }
+                return children;
+            },
+            [&](const Realisation& current) -> void {
+                dstStore.registerDrvOutput(current, checkSigs);
+            });
     } catch (MissingExperimentalFeature & e) {
         // Don't fail if the remote doesn't support CA derivations is it might
         // not be within our control to change that, and we might still want
@@ -845,11 +935,16 @@ std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStor
     return pathsMap;
 }
 
-std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStore, const StorePathSet & storePaths,
-    RepairFlag repair, CheckSigsFlag checkSigs, SubstituteFlag substitute,
-    std::function<void(ref<Store>, ref<Store>, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl)
+std::map<StorePath, StorePath> copyPaths(
+    Store & srcStore,
+    Store & dstStore,
+    const StorePathSet & storePaths,
+    RepairFlag repair,
+    CheckSigsFlag checkSigs,
+    SubstituteFlag substitute,
+    std::function<void(Store &, Store &, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl)
 {
-    auto valid = dstStore->queryValidPaths(storePaths, substitute);
+    auto valid = dstStore.queryValidPaths(storePaths, substitute);
 
     StorePathSet missing;
     for (auto & path : storePaths)
@@ -859,9 +954,31 @@ std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStor
     for (auto & path : storePaths)
         pathsMap.insert_or_assign(path, path);
 
-
     Activity act(*logger, lvlInfo, actCopyPaths, fmt("copying %d paths", missing.size()));
 
+    auto sorted = srcStore.topoSortPaths(missing);
+    std::reverse(sorted.begin(), sorted.end());
+
+    auto source = sinkToSource([&](Sink & sink) {
+        sink << sorted.size();
+        for (auto & storePath : sorted) {
+            auto srcUri = srcStore.getUri();
+            auto dstUri = dstStore.getUri();
+            auto storePathS = srcStore.printStorePath(storePath);
+            Activity act(*logger, lvlInfo, actCopyPath,
+                makeCopyPathMessage(srcUri, dstUri, storePathS),
+                {storePathS, srcUri, dstUri});
+            PushActivity pact(act.id);
+
+            auto info = srcStore.queryPathInfo(storePath);
+            info->write(sink, srcStore, 16);
+            srcStore.narFromPath(storePath, sink);
+        }
+    });
+
+    dstStore.addMultipleToStore(*source, repair, checkSigs);
+
+    #if 0
     std::atomic<size_t> nrDone{0};
     std::atomic<size_t> nrFailed{0};
     std::atomic<uint64_t> bytesExpected{0};
@@ -877,18 +994,21 @@ std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStor
         StorePathSet(missing.begin(), missing.end()),
 
         [&](const StorePath & storePath) {
-            auto info = srcStore->queryPathInfo(storePath);
+            auto info = srcStore.queryPathInfo(storePath);
             auto storePathForDst = storePath;
             if (info->ca && info->references.empty()) {
-                storePathForDst = dstStore->makeFixedOutputPathFromCA(storePath.name(), *info->ca);
-                if (dstStore->storeDir == srcStore->storeDir)
+                storePathForDst = dstStore.makeFixedOutputPathFromCA(storePath.name(), *info->ca);
+                if (dstStore.storeDir == srcStore.storeDir)
                     assert(storePathForDst == storePath);
                 if (storePathForDst != storePath)
-                    debug("replaced path '%s' to '%s' for substituter '%s'", srcStore->printStorePath(storePath), dstStore->printStorePath(storePathForDst), dstStore->getUri());
+                    debug("replaced path '%s' to '%s' for substituter '%s'",
+                        srcStore.printStorePath(storePath),
+                        dstStore.printStorePath(storePathForDst),
+                        dstStore.getUri());
             }
             pathsMap.insert_or_assign(storePath, storePathForDst);
 
-            if (dstStore->isValidPath(storePath)) {
+            if (dstStore.isValidPath(storePath)) {
                 nrDone++;
                 showProgress();
                 return StorePathSet();
@@ -903,19 +1023,22 @@ std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStor
         [&](const StorePath & storePath) {
             checkInterrupt();
 
-            auto info = srcStore->queryPathInfo(storePath);
+            auto info = srcStore.queryPathInfo(storePath);
 
             auto storePathForDst = storePath;
             if (info->ca && info->references.empty()) {
-                storePathForDst = dstStore->makeFixedOutputPathFromCA(storePath.name(), *info->ca);
-                if (dstStore->storeDir == srcStore->storeDir)
+                storePathForDst = dstStore.makeFixedOutputPathFromCA(storePath.name(), *info->ca);
+                if (dstStore.storeDir == srcStore.storeDir)
                     assert(storePathForDst == storePath);
                 if (storePathForDst != storePath)
-                    debug("replaced path '%s' to '%s' for substituter '%s'", srcStore->printStorePath(storePath), dstStore->printStorePath(storePathForDst), dstStore->getUri());
+                    debug("replaced path '%s' to '%s' for substituter '%s'",
+                        srcStore.printStorePath(storePath),
+                        dstStore.printStorePath(storePathForDst),
+                        dstStore.getUri());
             }
             pathsMap.insert_or_assign(storePath, storePathForDst);
 
-            if (!dstStore->isValidPath(storePathForDst)) {
+            if (!dstStore.isValidPath(storePathForDst)) {
                 MaintainCount<decltype(nrRunning)> mc(nrRunning);
                 showProgress();
                 try {
@@ -924,7 +1047,7 @@ std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStor
                     nrFailed++;
                     if (!settings.keepGoing)
                         throw e;
-                    logger->log(lvlError, fmt("could not copy %s: %s", dstStore->printStorePath(storePath), e.what()));
+                    logger->log(lvlError, fmt("could not copy %s: %s", dstStore.printStorePath(storePath), e.what()));
                     showProgress();
                     return;
                 }
@@ -933,9 +1056,27 @@ std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStor
             nrDone++;
             showProgress();
         });
+    #endif
+
     return pathsMap;
 }
 
+void copyClosure(
+    Store & srcStore,
+    Store & dstStore,
+    const RealisedPath::Set & paths,
+    RepairFlag repair,
+    CheckSigsFlag checkSigs,
+    SubstituteFlag substitute)
+{
+    if (&srcStore == &dstStore) return;
+
+    RealisedPath::Set closure;
+    RealisedPath::closure(srcStore, paths, closure);
+
+    copyPaths(srcStore, dstStore, closure, repair, checkSigs, substitute);
+}
+
 std::optional<ValidPathInfo> decodeValidPathInfo(const Store & store, std::istream & str, std::optional<HashResult> hashGiven)
 {
     std::string path;
@@ -1008,10 +1149,10 @@ bool ValidPathInfo::isContentAddressed(const Store & store) const
     if (! ca) return false;
 
     auto caPath = std::visit(overloaded {
-        [&](TextHash th) {
+        [&](const TextHash & th) {
             return store.makeTextPath(path.name(), th.hash, references);
         },
-        [&](FixedOutputHash fsh) {
+        [&](const FixedOutputHash & fsh) {
             auto refs = references;
             bool hasSelfReference = false;
             if (refs.count(path)) {
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 31466c925..24b9228f9 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -2,6 +2,7 @@
 
 #include "realisation.hh"
 #include "path.hh"
+#include "derived-path.hh"
 #include "hash.hh"
 #include "content-address.hh"
 #include "serialise.hh"
@@ -179,6 +180,8 @@ struct StoreConfig : public Config
 
     StoreConfig() = delete;
 
+    StringSet getDefaultSystemFeatures();
+
     virtual ~StoreConfig() { }
 
     virtual const std::string name() = 0;
@@ -197,7 +200,7 @@ struct StoreConfig : public Config
 
     Setting<bool> wantMassQuery{this, false, "want-mass-query", "whether this substituter can be queried efficiently for path validity"};
 
-    Setting<StringSet> systemFeatures{this, settings.systemFeatures,
+    Setting<StringSet> systemFeatures{this, getDefaultSystemFeatures(),
         "system-features",
         "Optional features that the system this store builds on implements (like \"kvm\")."};
 
@@ -263,11 +266,6 @@ public:
 
     PathSet printStorePathSet(const StorePathSet & path) const;
 
-    /* Split a string specifying a derivation and a set of outputs
-       (/nix/store/hash-foo!out1,out2,...) into the derivation path
-       and the outputs. */
-    StorePathWithOutputs parsePathWithOutputs(const string & s);
-
     /* Display a set of paths in human-readable form (i.e., between quotes
        and separated by commas). */
     std::string showPaths(const StorePathSet & paths);
@@ -291,8 +289,6 @@ public:
        result. */
     StorePath followLinksToStorePath(std::string_view path) const;
 
-    StorePathWithOutputs followLinksToStorePathWithOutputs(std::string_view path) const;
-
     /* Constructs a unique store path name. */
     StorePath makeStorePath(std::string_view type,
         std::string_view hash, std::string_view name) const;
@@ -386,7 +382,12 @@ public:
        we don't really want to add the dependencies listed in a nar info we
        don't trust anyyways.
        */
-    virtual bool pathInfoIsTrusted(const ValidPathInfo &)
+    virtual bool pathInfoIsUntrusted(const ValidPathInfo &)
+    {
+        return true;
+    }
+
+    virtual bool realisationIsUntrusted(const Realisation & )
     {
         return true;
     }
@@ -431,9 +432,10 @@ public:
     virtual StorePathSet querySubstitutablePaths(const StorePathSet & paths) { return {}; };
 
     /* Query substitute info (i.e. references, derivers and download
-       sizes) of a map of paths to their optional ca values. If a path
-       does not have substitute info, it's omitted from the resulting
-       ‘infos’ map. */
+       sizes) of a map of paths to their optional ca values. The info
+       of the first succeeding substituter for each path will be
+       returned. If a path does not have substitute info, it's omitted
+       from the resulting ‘infos’ map. */
     virtual void querySubstitutablePathInfos(const StorePathCAMap & paths,
         SubstitutablePathInfos & infos) { return; };
 
@@ -441,6 +443,12 @@ public:
     virtual void addToStore(const ValidPathInfo & info, Source & narSource,
         RepairFlag repair = NoRepair, CheckSigsFlag checkSigs = CheckSigs) = 0;
 
+    /* Import multiple paths into the store. */
+    virtual void addMultipleToStore(
+        Source & source,
+        RepairFlag repair = NoRepair,
+        CheckSigsFlag checkSigs = CheckSigs);
+
     /* Copy the contents of a path to the store and register the
        validity the resulting path.  The resulting path is returned.
        The function object `filter' can be used to exclude files (see
@@ -482,6 +490,8 @@ public:
      */
     virtual void registerDrvOutput(const Realisation & output)
     { unsupported("registerDrvOutput"); }
+    virtual void registerDrvOutput(const Realisation & output, CheckSigsFlag checkSigs)
+    { return registerDrvOutput(output); }
 
     /* Write a NAR dump of a store path. */
     virtual void narFromPath(const StorePath & path, Sink & sink) = 0;
@@ -495,8 +505,9 @@ public:
        recursively building any sub-derivations. For inputs that are
        not derivations, substitute them. */
     virtual void buildPaths(
-        const std::vector<StorePathWithOutputs> & paths,
-        BuildMode buildMode = bmNormal);
+        const std::vector<DerivedPath> & paths,
+        BuildMode buildMode = bmNormal,
+        std::shared_ptr<Store> evalStore = nullptr);
 
     /* Build a single non-materialized derivation (i.e. not from an
        on-disk .drv file).
@@ -542,7 +553,7 @@ public:
     /* Add a store path as a temporary root of the garbage collector.
        The root disappears as soon as we exit. */
     virtual void addTempRoot(const StorePath & path)
-    { warn("not creating temp root, store doesn't support GC"); }
+    { debug("not creating temporary root, store doesn't support GC"); }
 
     /* Add an indirect root, which is merely a symlink to `path' from
        /nix/var/nix/gcroots/auto/<hash of `path'>.  `path' is supposed
@@ -657,7 +668,7 @@ public:
     /* Given a set of paths that are to be built, return the set of
        derivations that will be built, and the set of output paths
        that will be substituted. */
-    virtual void queryMissing(const std::vector<StorePathWithOutputs> & targets,
+    virtual void queryMissing(const std::vector<DerivedPath> & targets,
         StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
         uint64_t & downloadSize, uint64_t & narSize);
 
@@ -696,6 +707,11 @@ public:
 
     const Stats & getStats();
 
+    /* Computes the full closure of of a set of store-paths for e.g.
+       derivations that need this information for `exportReferencesGraph`.
+     */
+    StorePathSet exportReferences(const StorePathSet & storePaths, const StorePathSet & inputPaths);
+
     /* Return the build log of the specified store path, if available,
        or null otherwise. */
     virtual std::shared_ptr<std::string> getBuildLog(const StorePath & path)
@@ -745,17 +761,21 @@ protected:
 
 
 /* Copy a path from one store to another. */
-void copyStorePath(ref<Store> srcStore, ref<Store> dstStore,
-    const StorePath & storePath, RepairFlag repair = NoRepair, CheckSigsFlag checkSigs = CheckSigs);
+void copyStorePath(
+    Store & srcStore,
+    Store & dstStore,
+    const StorePath & storePath,
+    RepairFlag repair = NoRepair,
+    CheckSigsFlag checkSigs = CheckSigs);
 
 
 /* copyStorePath wrapped to be used with `copyPaths`. */
-void copyStorePathAdapter(ref<Store> srcStore, ref<Store> dstStore,
+void copyStorePathAdapter(Store & srcStore, Store & dstStore,
     const ValidPathInfo & info, RepairFlag repair = NoRepair, CheckSigsFlag checkSigs = CheckSigs);
 
 /* The more liberal alternative to `copyStorePathAdapter`, useful for remote
    stores that do not trust us. */
-void copyOrBuildStorePath(ref<Store> srcStore, ref<Store> dstStore,
+void copyOrBuildStorePath(Store & srcStore, Store & dstStore,
     const ValidPathInfo & info, RepairFlag repair = NoRepair, CheckSigsFlag checkSigs = CheckSigs);
 
 /* Copy store paths from one store to another. The paths may be copied
@@ -770,19 +790,29 @@ void copyOrBuildStorePath(ref<Store> srcStore, ref<Store> dstStore,
    side to build dependencies we don't have permission to copy. This behavior
    isn't just the default that way `nix copy` etc. still can be relied upon to
    not build anything. */
-std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStore,
+std::map<StorePath, StorePath> copyPaths(
+    Store & srcStore, Store & dstStore,
     const RealisedPath::Set &,
     RepairFlag repair = NoRepair,
     CheckSigsFlag checkSigs = CheckSigs,
     SubstituteFlag substitute = NoSubstitute,
-    std::function<void(ref<Store>, ref<Store>, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl = copyStorePathAdapter);
-std::map<StorePath, StorePath> copyPaths(ref<Store> srcStore, ref<Store> dstStore,
-    const StorePathSet& paths,
+    std::function<void(Store &, Store &, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl = copyStorePathAdapter);
+
+std::map<StorePath, StorePath> copyPaths(
+    Store & srcStore, Store & dstStore,
+    const StorePathSet & paths,
     RepairFlag repair = NoRepair,
     CheckSigsFlag checkSigs = CheckSigs,
     SubstituteFlag substitute = NoSubstitute,
-    std::function<void(ref<Store>, ref<Store>, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl = copyStorePathAdapter);
+    std::function<void(Store &, Store &, const ValidPathInfo &, RepairFlag, CheckSigsFlag)> copyStorePathImpl = copyStorePathAdapter);
 
+/* Copy the closure of `paths` from `srcStore` to `dstStore`. */
+void copyClosure(
+    Store & srcStore, Store & dstStore,
+    const RealisedPath::Set & paths,
+    RepairFlag repair = NoRepair,
+    CheckSigsFlag checkSigs = CheckSigs,
+    SubstituteFlag substitute = NoSubstitute);
 
 /* Remove the temporary roots file for this process.  Any temporary
    root becomes garbage after this point unless it has been registered
@@ -882,4 +912,9 @@ std::pair<std::string, Store::Params> splitUriAndParams(const std::string & uri)
 
 std::optional<ContentAddress> getDerivationCA(const BasicDerivation & drv);
 
+std::map<DrvOutput, StorePath> drvOutputReferences(
+    Store & store,
+    const Derivation & drv,
+    const StorePath & outputPath);
+
 }
diff --git a/src/libstore/tests/local.mk b/src/libstore/tests/local.mk
new file mode 100644
index 000000000..f74295d97
--- /dev/null
+++ b/src/libstore/tests/local.mk
@@ -0,0 +1,15 @@
+check: libstore-tests_RUN
+
+programs += libstore-tests
+
+libstore-tests_DIR := $(d)
+
+libstore-tests_INSTALL_DIR :=
+
+libstore-tests_SOURCES := $(wildcard $(d)/*.cc)
+
+libstore-tests_CXXFLAGS += -I src/libstore -I src/libutil
+
+libstore-tests_LIBS = libstore libutil
+
+libstore-tests_LDFLAGS := $(GTEST_LIBS)
diff --git a/src/libstore/tests/references.cc b/src/libstore/tests/references.cc
new file mode 100644
index 000000000..d91d1cedd
--- /dev/null
+++ b/src/libstore/tests/references.cc
@@ -0,0 +1,45 @@
+#include "references.hh"
+
+#include <gtest/gtest.h>
+
+namespace nix {
+
+TEST(references, scan)
+{
+    std::string hash1 = "dc04vv14dak1c1r48qa0m23vr9jy8sm0";
+    std::string hash2 = "zc842j0rz61mjsp3h3wp5ly71ak6qgdn";
+
+    {
+        RefScanSink scanner(StringSet{hash1});
+        auto s = "foobar";
+        scanner(s);
+        ASSERT_EQ(scanner.getResult(), StringSet{});
+    }
+
+    {
+        RefScanSink scanner(StringSet{hash1});
+        auto s = "foobar" + hash1 + "xyzzy";
+        scanner(s);
+        ASSERT_EQ(scanner.getResult(), StringSet{hash1});
+    }
+
+    {
+        RefScanSink scanner(StringSet{hash1, hash2});
+        auto s = "foobar" + hash1 + "xyzzy" + hash2;
+        scanner(((std::string_view) s).substr(0, 10));
+        scanner(((std::string_view) s).substr(10, 5));
+        scanner(((std::string_view) s).substr(15, 5));
+        scanner(((std::string_view) s).substr(20));
+        ASSERT_EQ(scanner.getResult(), StringSet({hash1, hash2}));
+    }
+
+    {
+        RefScanSink scanner(StringSet{hash1, hash2});
+        auto s = "foobar" + hash1 + "xyzzy" + hash2;
+        for (auto & i : s)
+            scanner(std::string(1, i));
+        ASSERT_EQ(scanner.getResult(), StringSet({hash1, hash2}));
+    }
+}
+
+}
diff --git a/src/libstore/uds-remote-store.cc b/src/libstore/uds-remote-store.cc
index cac4fa036..02e81b022 100644
--- a/src/libstore/uds-remote-store.cc
+++ b/src/libstore/uds-remote-store.cc
@@ -45,6 +45,12 @@ std::string UDSRemoteStore::getUri()
 }
 
 
+void UDSRemoteStore::Connection::closeWrite()
+{
+    shutdown(fd.get(), SHUT_WR);
+}
+
+
 ref<RemoteStore::Connection> UDSRemoteStore::openConnection()
 {
     auto conn = make_ref<Connection>();
@@ -59,16 +65,7 @@ ref<RemoteStore::Connection> UDSRemoteStore::openConnection()
         throw SysError("cannot create Unix domain socket");
     closeOnExec(conn->fd.get());
 
-    string socketPath = path ? *path : settings.nixDaemonSocketFile;
-
-    struct sockaddr_un addr;
-    addr.sun_family = AF_UNIX;
-    if (socketPath.size() + 1 >= sizeof(addr.sun_path))
-        throw Error("socket path '%1%' is too long", socketPath);
-    strcpy(addr.sun_path, socketPath.c_str());
-
-    if (::connect(conn->fd.get(), (struct sockaddr *) &addr, sizeof(addr)) == -1)
-        throw SysError("cannot connect to daemon at '%1%'", socketPath);
+    nix::connect(conn->fd.get(), path ? *path : settings.nixDaemonSocketFile);
 
     conn->from.fd = conn->fd.get();
     conn->to.fd = conn->fd.get();
diff --git a/src/libstore/uds-remote-store.hh b/src/libstore/uds-remote-store.hh
index ddc7716cd..f8dfcca70 100644
--- a/src/libstore/uds-remote-store.hh
+++ b/src/libstore/uds-remote-store.hh
@@ -40,6 +40,12 @@ public:
 
 private:
 
+    struct Connection : RemoteStore::Connection
+    {
+        AutoCloseFD fd;
+        void closeWrite() override;
+    };
+
     ref<RemoteStore::Connection> openConnection() override;
     std::optional<std::string> path;
 };
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index 95f08bc9a..93cf546d2 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -9,7 +9,7 @@ namespace nix {
 #define WORKER_MAGIC_1 0x6e697863
 #define WORKER_MAGIC_2 0x6478696f
 
-#define PROTOCOL_VERSION 0x11c
+#define PROTOCOL_VERSION (1 << 8 | 32)
 #define GET_PROTOCOL_MAJOR(x) ((x) & 0xff00)
 #define GET_PROTOCOL_MINOR(x) ((x) & 0x00ff)
 
@@ -55,6 +55,7 @@ typedef enum {
     wopQueryDerivationOutputMap = 41,
     wopRegisterDrvOutput = 42,
     wopQueryRealisation = 43,
+    wopAddMultipleToStore = 44,
 } WorkerOp;
 
 
@@ -86,9 +87,11 @@ namespace worker_proto {
 MAKE_WORKER_PROTO(, std::string);
 MAKE_WORKER_PROTO(, StorePath);
 MAKE_WORKER_PROTO(, ContentAddress);
+MAKE_WORKER_PROTO(, DerivedPath);
 MAKE_WORKER_PROTO(, Realisation);
 MAKE_WORKER_PROTO(, DrvOutput);
 
+MAKE_WORKER_PROTO(template<typename T>, std::vector<T>);
 MAKE_WORKER_PROTO(template<typename T>, std::set<T>);
 
 #define X_ template<typename K, typename V>
@@ -114,6 +117,26 @@ MAKE_WORKER_PROTO(, std::optional<StorePath>);
 MAKE_WORKER_PROTO(, std::optional<ContentAddress>);
 
 template<typename T>
+std::vector<T> read(const Store & store, Source & from, Phantom<std::vector<T>> _)
+{
+    std::vector<T> resSet;
+    auto size = readNum<size_t>(from);
+    while (size--) {
+        resSet.push_back(read(store, from, Phantom<T> {}));
+    }
+    return resSet;
+}
+
+template<typename T>
+void write(const Store & store, Sink & out, const std::vector<T> & resSet)
+{
+    out << resSet.size();
+    for (auto & key : resSet) {
+        write(store, out, key);
+    }
+}
+
+template<typename T>
 std::set<T> read(const Store & store, Source & from, Phantom<std::set<T>> _)
 {
     std::set<T> resSet;