Merge remote-tracking branch 'upstream/master' into derivation-header-include-order

28 files changed, 938 insertions, 535 deletions

diff --git a/src/libstore/binary-cache-store.cc b/src/libstore/binary-cache-store.cc
index 30150eeba..5433fe50d 100644
--- a/src/libstore/binary-cache-store.cc
+++ b/src/libstore/binary-cache-store.cc
@@ -143,7 +143,7 @@ struct FileSource : FdSource
 void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource,
     RepairFlag repair, CheckSigsFlag checkSigs)
 {
-    assert(info.narHash && info.narSize);
+    assert(info.narSize);
 
     if (!repair && isValidPath(info.path)) {
         // FIXME: copyNAR -> null sink
@@ -153,6 +153,8 @@ void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource
 
     auto [fdTemp, fnTemp] = createTempFile();
 
+    AutoDelete autoDelete(fnTemp);
+
     auto now1 = std::chrono::steady_clock::now();
 
     /* Read the NAR simultaneously into a CompressionSink+FileSink (to
@@ -167,6 +169,7 @@ void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource
     TeeSource teeSource(narSource, *compressionSink);
     narAccessor = makeNarAccessor(teeSource);
     compressionSink->finish();
+    fileSink.flush();
     }
 
     auto now2 = std::chrono::steady_clock::now();
@@ -216,7 +219,7 @@ void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource
             }
         }
 
-        upsertFile(std::string(info.path.to_string()) + ".ls", jsonOut.str(), "application/json");
+        upsertFile(std::string(info.path.hashPart()) + ".ls", jsonOut.str(), "application/json");
     }
 
     /* Optionally maintain an index of DWARF debug info files
@@ -280,7 +283,7 @@ void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource
     if (repair || !fileExists(narInfo->url)) {
         stats.narWrite++;
         upsertFile(narInfo->url,
-            std::make_shared<std::fstream>(fnTemp, std::ios_base::in),
+            std::make_shared<std::fstream>(fnTemp, std::ios_base::in | std::ios_base::binary),
             "application/x-nix-nar");
     } else
         stats.narWriteAverted++;
@@ -309,14 +312,10 @@ void BinaryCacheStore::narFromPath(const StorePath & storePath, Sink & sink)
 {
     auto info = queryPathInfo(storePath).cast<const NarInfo>();
 
-    uint64_t narSize = 0;
-
-    LambdaSink wrapperSink([&](const unsigned char * data, size_t len) {
-        sink(data, len);
-        narSize += len;
-    });
+    LengthSink narSize;
+    TeeSink tee { sink, narSize };
 
-    auto decompressor = makeDecompressionSink(info->compression, wrapperSink);
+    auto decompressor = makeDecompressionSink(info->compression, tee);
 
     try {
         getFile(info->url, *decompressor);
@@ -328,7 +327,7 @@ void BinaryCacheStore::narFromPath(const StorePath & storePath, Sink & sink)
 
     stats.narRead++;
     //stats.narReadCompressedBytes += nar->size(); // FIXME
-    stats.narReadBytes += narSize;
+    stats.narReadBytes += narSize.length;
 }
 
 void BinaryCacheStore::queryPathInfoUncached(const StorePath & storePath,
@@ -382,7 +381,10 @@ StorePath BinaryCacheStore::addToStore(const string & name, const Path & srcPath
         h = hashString(hashAlgo, s);
     }
 
-    ValidPathInfo info(makeFixedOutputPath(method, *h, name));
+    ValidPathInfo info {
+        makeFixedOutputPath(method, *h, name),
+        Hash::dummy, // Will be fixed in addToStore, which recomputes nar hash
+    };
 
     auto source = StringSource { *sink.s };
     addToStore(info, source, repair, CheckSigs);
@@ -393,7 +395,10 @@ StorePath BinaryCacheStore::addToStore(const string & name, const Path & srcPath
 StorePath BinaryCacheStore::addTextToStore(const string & name, const string & s,
     const StorePathSet & references, RepairFlag repair)
 {
-    ValidPathInfo info(computeStorePathForText(name, s, references));
+    ValidPathInfo info {
+        computeStorePathForText(name, s, references),
+        Hash::dummy, // Will be fixed in addToStore, which recomputes nar hash
+    };
     info.references = references;
 
     if (repair || !isValidPath(info.path)) {
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index 4156cd678..afb2bb096 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -806,8 +806,8 @@ private:
     /* RAII object to delete the chroot directory. */
     std::shared_ptr<AutoDelete> autoDelChroot;
 
-    /* Whether this is a fixed-output derivation. */
-    bool fixedOutput;
+    /* The sort of derivation we are building. */
+    DerivationType derivationType;
 
     /* Whether to run the build in a private network namespace. */
     bool privateNetwork = false;
@@ -1181,8 +1181,8 @@ void DerivationGoal::haveDerivation()
 
     retrySubstitution = false;
 
-    for (auto & i : drv->outputs)
-        worker.store.addTempRoot(i.second.path(worker.store, drv->name));
+    for (auto & i : drv->outputsAndPaths(worker.store))
+        worker.store.addTempRoot(i.second.second);
 
     /* Check what outputs paths are not already valid. */
     auto invalidOutputs = checkPathValidity(false, buildMode == bmRepair);
@@ -1195,9 +1195,9 @@ void DerivationGoal::haveDerivation()
 
     parsedDrv = std::make_unique<ParsedDerivation>(drvPath, *drv);
 
-    if (parsedDrv->contentAddressed()) {
+    if (drv->type() == DerivationType::CAFloating) {
         settings.requireExperimentalFeature("ca-derivations");
-        throw Error("ca-derivations isn't implemented yet");
+        throw UnimplementedError("ca-derivations isn't implemented yet");
     }
 
 
@@ -1288,14 +1288,14 @@ void DerivationGoal::repairClosure()
 
     /* Get the output closure. */
     StorePathSet outputClosure;
-    for (auto & i : drv->outputs) {
+    for (auto & i : drv->outputsAndPaths(worker.store)) {
         if (!wantOutput(i.first, wantedOutputs)) continue;
-        worker.store.computeFSClosure(i.second.path(worker.store, drv->name), outputClosure);
+        worker.store.computeFSClosure(i.second.second, outputClosure);
     }
 
     /* Filter out our own outputs (which we have already checked). */
-    for (auto & i : drv->outputs)
-        outputClosure.erase(i.second.path(worker.store, drv->name));
+    for (auto & i : drv->outputsAndPaths(worker.store))
+        outputClosure.erase(i.second.second);
 
     /* Get all dependencies of this derivation so that we know which
        derivation is responsible for which path in the output
@@ -1306,8 +1306,8 @@ void DerivationGoal::repairClosure()
     for (auto & i : inputClosure)
         if (i.isDerivation()) {
             Derivation drv = worker.store.derivationFromPath(i);
-            for (auto & j : drv.outputs)
-                outputsToDrv.insert_or_assign(j.second.path(worker.store, drv.name), i);
+            for (auto & j : drv.outputsAndPaths(worker.store))
+                outputsToDrv.insert_or_assign(j.second.second, i);
         }
 
     /* Check each path (slow!). */
@@ -1392,12 +1392,12 @@ void DerivationGoal::inputsRealised()
 
     debug("added input paths %s", worker.store.showPaths(inputPaths));
 
-    /* Is this a fixed-output derivation? */
-    fixedOutput = drv->isFixedOutput();
+    /* What type of derivation are we building? */
+    derivationType = drv->type();
 
     /* Don't repeat fixed-output derivations since they're already
        verified by their output hash.*/
-    nrRounds = fixedOutput ? 1 : settings.buildRepeat + 1;
+    nrRounds = derivationIsFixed(derivationType) ? 1 : settings.buildRepeat + 1;
 
     /* Okay, try to build.  Note that here we don't wait for a build
        slot to become available, since we don't need one if there is a
@@ -1466,16 +1466,16 @@ void DerivationGoal::tryToBuild()
 
     /* If any of the outputs already exist but are not valid, delete
        them. */
-    for (auto & i : drv->outputs) {
-        if (worker.store.isValidPath(i.second.path(worker.store, drv->name))) continue;
-        debug("removing invalid path '%s'", worker.store.printStorePath(i.second.path(worker.store, drv->name)));
-        deletePath(worker.store.Store::toRealPath(i.second.path(worker.store, drv->name)));
+    for (auto & i : drv->outputsAndPaths(worker.store)) {
+        if (worker.store.isValidPath(i.second.second)) continue;
+        debug("removing invalid path '%s'", worker.store.printStorePath(i.second.second));
+        deletePath(worker.store.Store::toRealPath(i.second.second));
     }
 
     /* Don't do a remote build if the derivation has the attribute
        `preferLocalBuild' set.  Also, check and repair modes are only
        supported for local builds. */
-    bool buildLocally = buildMode != bmNormal || parsedDrv->willBuildLocally();
+    bool buildLocally = buildMode != bmNormal || parsedDrv->willBuildLocally(worker.store);
 
     /* Is the build hook willing to accept this job? */
     if (!buildLocally) {
@@ -1783,7 +1783,7 @@ void DerivationGoal::buildDone()
             st =
                 dynamic_cast<NotDeterministic*>(&e) ? BuildResult::NotDeterministic :
                 statusOk(status) ? BuildResult::OutputRejected :
-                fixedOutput || diskFull ? BuildResult::TransientFailure :
+                derivationIsImpure(derivationType) || diskFull ? BuildResult::TransientFailure :
                 BuildResult::PermanentFailure;
         }
 
@@ -1919,8 +1919,8 @@ StorePathSet DerivationGoal::exportReferences(const StorePathSet & storePaths)
     for (auto & j : paths2) {
         if (j.isDerivation()) {
             Derivation drv = worker.store.derivationFromPath(j);
-            for (auto & k : drv.outputs)
-                worker.store.computeFSClosure(k.second.path(worker.store, drv.name), paths);
+            for (auto & k : drv.outputsAndPaths(worker.store))
+                worker.store.computeFSClosure(k.second.second, paths);
         }
     }
 
@@ -1964,13 +1964,13 @@ void linkOrCopy(const Path & from, const Path & to)
 void DerivationGoal::startBuilder()
 {
     /* Right platform? */
-    if (!parsedDrv->canBuildLocally())
+    if (!parsedDrv->canBuildLocally(worker.store))
         throw Error("a '%s' with features {%s} is required to build '%s', but I am a '%s' with features {%s}",
             drv->platform,
             concatStringsSep(", ", parsedDrv->getRequiredSystemFeatures()),
             worker.store.printStorePath(drvPath),
             settings.thisSystem,
-            concatStringsSep<StringSet>(", ", settings.systemFeatures));
+            concatStringsSep<StringSet>(", ", worker.store.systemFeatures));
 
     if (drv->isBuiltin())
         preloadNSS();
@@ -1996,7 +1996,7 @@ void DerivationGoal::startBuilder()
         else if (settings.sandboxMode == smDisabled)
             useChroot = false;
         else if (settings.sandboxMode == smRelaxed)
-            useChroot = !fixedOutput && !noChroot;
+            useChroot = !(derivationIsImpure(derivationType)) && !noChroot;
     }
 
     if (worker.store.storeDir != worker.store.realStoreDir) {
@@ -2014,8 +2014,8 @@ void DerivationGoal::startBuilder()
     chownToBuilder(tmpDir);
 
     /* Substitute output placeholders with the actual output paths. */
-    for (auto & output : drv->outputs)
-        inputRewrites[hashPlaceholder(output.first)] = worker.store.printStorePath(output.second.path(worker.store, drv->name));
+    for (auto & output : drv->outputsAndPaths(worker.store))
+        inputRewrites[hashPlaceholder(output.first)] = worker.store.printStorePath(output.second.second);
 
     /* Construct the environment passed to the builder. */
     initEnv();
@@ -2165,7 +2165,7 @@ void DerivationGoal::startBuilder()
                 "nogroup:x:65534:\n") % sandboxGid).str());
 
         /* Create /etc/hosts with localhost entry. */
-        if (!fixedOutput)
+        if (!(derivationIsImpure(derivationType)))
             writeFile(chrootRootDir + "/etc/hosts", "127.0.0.1 localhost\n::1 localhost\n");
 
         /* Make the closure of the inputs available in the chroot,
@@ -2199,8 +2199,8 @@ void DerivationGoal::startBuilder()
            rebuilding a path that is in settings.dirsInChroot
            (typically the dependencies of /bin/sh).  Throw them
            out. */
-        for (auto & i : drv->outputs)
-            dirsInChroot.erase(worker.store.printStorePath(i.second.path(worker.store, drv->name)));
+        for (auto & i : drv->outputsAndPaths(worker.store))
+            dirsInChroot.erase(worker.store.printStorePath(i.second.second));
 
 #elif __APPLE__
         /* We don't really have any parent prep work to do (yet?)
@@ -2373,7 +2373,7 @@ void DerivationGoal::startBuilder()
            us.
         */
 
-        if (!fixedOutput)
+        if (!(derivationIsImpure(derivationType)))
             privateNetwork = true;
 
         userNamespaceSync.create();
@@ -2574,7 +2574,7 @@ void DerivationGoal::initEnv()
        derivation, tell the builder, so that for instance `fetchurl'
        can skip checking the output.  On older Nixes, this environment
        variable won't be set, so `fetchurl' will do the check. */
-    if (fixedOutput) env["NIX_OUTPUT_CHECKED"] = "1";
+    if (derivationIsFixed(derivationType)) env["NIX_OUTPUT_CHECKED"] = "1";
 
     /* *Only* if this is a fixed-output derivation, propagate the
        values of the environment variables specified in the
@@ -2585,7 +2585,7 @@ void DerivationGoal::initEnv()
        to the builder is generally impure, but the output of
        fixed-output derivations is by definition pure (since we
        already know the cryptographic hash of the output). */
-    if (fixedOutput) {
+    if (derivationIsImpure(derivationType)) {
         for (auto & i : parsedDrv->getStringsAttr("impureEnvVars").value_or(Strings()))
             env[i] = getEnv(i).value_or("");
     }
@@ -2612,8 +2612,8 @@ void DerivationGoal::writeStructuredAttrs()
 
     /* Add an "outputs" object containing the output paths. */
     nlohmann::json outputs;
-    for (auto & i : drv->outputs)
-        outputs[i.first] = rewriteStrings(worker.store.printStorePath(i.second.path(worker.store, drv->name)), inputRewrites);
+    for (auto & i : drv->outputsAndPaths(worker.store))
+        outputs[i.first] = rewriteStrings(worker.store.printStorePath(i.second.second), inputRewrites);
     json["outputs"] = outputs;
 
     /* Handle exportReferencesGraph. */
@@ -2815,9 +2815,9 @@ struct RestrictedStore : public LocalFSStore
                 if (!goal.isAllowed(path.path))
                     throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
                 auto drv = derivationFromPath(path.path);
-                for (auto & output : drv.outputs)
+                for (auto & output : drv.outputsAndPaths(*this))
                     if (wantOutput(output.first, path.outputs))
-                        newPaths.insert(output.second.path(*this, drv.name));
+                        newPaths.insert(output.second.second);
             } else if (!goal.isAllowed(path.path))
                 throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
         }
@@ -2920,7 +2920,8 @@ void DerivationGoal::startDaemon()
                 FdSink to(remote.get());
                 try {
                     daemon::processConnection(store, from, to,
-                        daemon::NotTrusted, daemon::Recursive, "nobody", 65535);
+                        daemon::NotTrusted, daemon::Recursive,
+                        [&](Store & store) { store.createUser("nobody", 65535); });
                     debug("terminated daemon connection");
                 } catch (SysError &) {
                     ignoreException();
@@ -3179,7 +3180,7 @@ void DerivationGoal::runChild()
                 createDirs(chrootRootDir + "/dev/shm");
                 createDirs(chrootRootDir + "/dev/pts");
                 ss.push_back("/dev/full");
-                if (settings.systemFeatures.get().count("kvm") && pathExists("/dev/kvm"))
+                if (worker.store.systemFeatures.get().count("kvm") && pathExists("/dev/kvm"))
                     ss.push_back("/dev/kvm");
                 ss.push_back("/dev/null");
                 ss.push_back("/dev/random");
@@ -3195,7 +3196,7 @@ void DerivationGoal::runChild()
             /* Fixed-output derivations typically need to access the
                network, so give them access to /etc/resolv.conf and so
                on. */
-            if (fixedOutput) {
+            if (derivationIsImpure(derivationType)) {
                 ss.push_back("/etc/resolv.conf");
 
                 // Only use nss functions to resolve hosts and
@@ -3436,7 +3437,7 @@ void DerivationGoal::runChild()
 
                 sandboxProfile += "(import \"sandbox-defaults.sb\")\n";
 
-                if (fixedOutput)
+                if (derivationIsImpure(derivationType))
                     sandboxProfile += "(import \"sandbox-network.sb\")\n";
 
                 /* Our rwx outputs */
@@ -3616,8 +3617,8 @@ void DerivationGoal::registerOutputs()
        to do anything here. */
     if (hook) {
         bool allValid = true;
-        for (auto & i : drv->outputs)
-            if (!worker.store.isValidPath(i.second.path(worker.store, drv->name))) allValid = false;
+        for (auto & i : drv->outputsAndPaths(worker.store))
+            if (!worker.store.isValidPath(i.second.second)) allValid = false;
         if (allValid) return;
     }
 
@@ -3638,23 +3639,23 @@ void DerivationGoal::registerOutputs()
        Nix calls. */
     StorePathSet referenceablePaths;
     for (auto & p : inputPaths) referenceablePaths.insert(p);
-    for (auto & i : drv->outputs) referenceablePaths.insert(i.second.path(worker.store, drv->name));
+    for (auto & i : drv->outputsAndPaths(worker.store)) referenceablePaths.insert(i.second.second);
     for (auto & p : addedPaths) referenceablePaths.insert(p);
 
     /* Check whether the output paths were created, and grep each
        output path to determine what other paths it references.  Also make all
        output paths read-only. */
-    for (auto & i : drv->outputs) {
-        auto path = worker.store.printStorePath(i.second.path(worker.store, drv->name));
-        if (!missingPaths.count(i.second.path(worker.store, drv->name))) continue;
+    for (auto & i : drv->outputsAndPaths(worker.store)) {
+        auto path = worker.store.printStorePath(i.second.second);
+        if (!missingPaths.count(i.second.second)) continue;
 
         Path actualPath = path;
         if (needsHashRewrite()) {
-            auto r = redirectedOutputs.find(i.second.path(worker.store, drv->name));
+            auto r = redirectedOutputs.find(i.second.second);
             if (r != redirectedOutputs.end()) {
                 auto redirected = worker.store.Store::toRealPath(r->second);
                 if (buildMode == bmRepair
-                    && redirectedBadOutputs.count(i.second.path(worker.store, drv->name))
+                    && redirectedBadOutputs.count(i.second.second)
                     && pathExists(redirected))
                     replaceValidPath(path, redirected);
                 if (buildMode == bmCheck)
@@ -3721,9 +3722,22 @@ void DerivationGoal::registerOutputs()
            hash). */
         std::optional<ContentAddress> ca;
 
-        if (fixedOutput) {
-
-            FixedOutputHash outputHash = std::get<DerivationOutputFixed>(i.second.output).hash;
+        if (! std::holds_alternative<DerivationOutputInputAddressed>(i.second.first.output)) {
+            DerivationOutputCAFloating outputHash;
+            std::visit(overloaded {
+                [&](DerivationOutputInputAddressed doi) {
+                    assert(false); // Enclosing `if` handles this case in other branch
+                },
+                [&](DerivationOutputCAFixed dof) {
+                    outputHash = DerivationOutputCAFloating {
+                        .method = dof.hash.method,
+                        .hashType = dof.hash.hash.type,
+                    };
+                },
+                [&](DerivationOutputCAFloating dof) {
+                    outputHash = dof;
+                },
+            }, i.second.first.output);
 
             if (outputHash.method == FileIngestionMethod::Flat) {
                 /* The output path should be a regular file without execute permission. */
@@ -3737,12 +3751,17 @@ void DerivationGoal::registerOutputs()
             /* Check the hash. In hash mode, move the path produced by
                the derivation to its content-addressed location. */
             Hash h2 = outputHash.method == FileIngestionMethod::Recursive
-                ? hashPath(outputHash.hash.type, actualPath).first
-                : hashFile(outputHash.hash.type, actualPath);
+                ? hashPath(outputHash.hashType, actualPath).first
+                : hashFile(outputHash.hashType, actualPath);
+
+            auto dest = worker.store.makeFixedOutputPath(outputHash.method, h2, i.second.second.name());
 
-            auto dest = worker.store.makeFixedOutputPath(outputHash.method, h2, i.second.path(worker.store, drv->name).name());
+            // true if either floating CA, or incorrect fixed hash.
+            bool needsMove = true;
 
-            if (outputHash.hash != h2) {
+            if (auto p = std::get_if<DerivationOutputCAFixed>(& i.second.first.output)) {
+              Hash & h = p->hash.hash;
+              if (h != h2) {
 
                 /* Throw an error after registering the path as
                    valid. */
@@ -3750,9 +3769,15 @@ void DerivationGoal::registerOutputs()
                 delayedException = std::make_exception_ptr(
                     BuildError("hash mismatch in fixed-output derivation '%s':\n  wanted: %s\n  got:    %s",
                         worker.store.printStorePath(dest),
-                        outputHash.hash.to_string(SRI, true),
+                        h.to_string(SRI, true),
                         h2.to_string(SRI, true)));
+              } else {
+                  // matched the fixed hash, so no move needed.
+                  needsMove = false;
+              }
+            }
 
+            if (needsMove) {
                 Path actualDest = worker.store.Store::toRealPath(dest);
 
                 if (worker.store.isValidPath(dest))
@@ -3840,8 +3865,10 @@ void DerivationGoal::registerOutputs()
             worker.markContentsGood(worker.store.parseStorePath(path));
         }
 
-        ValidPathInfo info(worker.store.parseStorePath(path));
-        info.narHash = hash.first;
+        ValidPathInfo info {
+            worker.store.parseStorePath(path),
+            hash.first,
+        };
         info.narSize = hash.second;
         info.references = std::move(references);
         info.deriver = drvPath;
@@ -3897,8 +3924,8 @@ void DerivationGoal::registerOutputs()
 
     /* If this is the first round of several, then move the output out of the way. */
     if (nrRounds > 1 && curRound == 1 && curRound < nrRounds && keepPreviousRound) {
-        for (auto & i : drv->outputs) {
-            auto path = worker.store.printStorePath(i.second.path(worker.store, drv->name));
+        for (auto & i : drv->outputsAndPaths(worker.store)) {
+            auto path = worker.store.printStorePath(i.second.second);
             Path prev = path + checkSuffix;
             deletePath(prev);
             Path dst = path + checkSuffix;
@@ -3915,8 +3942,8 @@ void DerivationGoal::registerOutputs()
     /* Remove the .check directories if we're done. FIXME: keep them
        if the result was not determistic? */
     if (curRound == nrRounds) {
-        for (auto & i : drv->outputs) {
-            Path prev = worker.store.printStorePath(i.second.path(worker.store, drv->name)) + checkSuffix;
+        for (auto & i : drv->outputsAndPaths(worker.store)) {
+            Path prev = worker.store.printStorePath(i.second.second) + checkSuffix;
             deletePath(prev);
         }
     }
@@ -4214,12 +4241,12 @@ void DerivationGoal::flushLine()
 StorePathSet DerivationGoal::checkPathValidity(bool returnValid, bool checkHash)
 {
     StorePathSet result;
-    for (auto & i : drv->outputs) {
+    for (auto & i : drv->outputsAndPaths(worker.store)) {
         if (!wantOutput(i.first, wantedOutputs)) continue;
         bool good =
-            worker.store.isValidPath(i.second.path(worker.store, drv->name)) &&
-            (!checkHash || worker.pathContentsGood(i.second.path(worker.store, drv->name)));
-        if (good == returnValid) result.insert(i.second.path(worker.store, drv->name));
+            worker.store.isValidPath(i.second.second) &&
+            (!checkHash || worker.pathContentsGood(i.second.second));
+        if (good == returnValid) result.insert(i.second.second);
     }
     return result;
 }
@@ -4852,8 +4879,17 @@ void Worker::run(const Goals & _topGoals)
             waitForInput();
         else {
             if (awake.empty() && 0 == settings.maxBuildJobs)
-                throw Error("unable to start any build; either increase '--max-jobs' "
-                            "or enable remote builds");
+            {
+                if (getMachines().empty())
+                   throw Error("unable to start any build; either increase '--max-jobs' "
+                            "or enable remote builds."
+                            "\nhttps://nixos.org/nix/manual/#chap-distributed-builds");
+                else
+                   throw Error("unable to start any build; remote machines may not have "
+                            "all required system features."
+                            "\nhttps://nixos.org/nix/manual/#chap-distributed-builds");
+
+            }
             assert(!awake.empty());
         }
     }
@@ -5037,7 +5073,7 @@ bool Worker::pathContentsGood(const StorePath & path)
     if (!pathExists(store.printStorePath(path)))
         res = false;
     else {
-        HashResult current = hashPath(info->narHash->type, store.printStorePath(path));
+        HashResult current = hashPath(info->narHash.type, store.printStorePath(path));
         Hash nullHash(htSHA256);
         res = info->narHash == nullHash || info->narHash == current.first;
     }
diff --git a/src/libstore/builtins/fetchurl.cc b/src/libstore/builtins/fetchurl.cc
index 6585a480d..4fb5d8a06 100644
--- a/src/libstore/builtins/fetchurl.cc
+++ b/src/libstore/builtins/fetchurl.cc
@@ -58,6 +58,20 @@ void builtinFetchurl(const BasicDerivation & drv, const std::string & netrcData)
         }
     };
 
+    /* Try the hashed mirrors first. */
+    if (getAttr("outputHashMode") == "flat")
+        for (auto hashedMirror : settings.hashedMirrors.get())
+            try {
+                if (!hasSuffix(hashedMirror, "/")) hashedMirror += '/';
+                std::optional<HashType> ht = parseHashTypeOpt(getAttr("outputHashAlgo"));
+                Hash h = newHashAllowEmpty(getAttr("outputHash"), ht);
+                fetch(hashedMirror + printHashType(h.type) + "/" + h.to_string(Base16, false));
+                return;
+            } catch (Error & e) {
+                debug(e.what());
+            }
+
+    /* Otherwise try the specified URL. */
     fetch(mainUrl);
 }
 
diff --git a/src/libstore/content-address.cc b/src/libstore/content-address.cc
index f83b98a98..0885c3d0e 100644
--- a/src/libstore/content-address.cc
+++ b/src/libstore/content-address.cc
@@ -1,4 +1,6 @@
+#include "args.hh"
 #include "content-address.hh"
+#include "split.hh"
 
 namespace nix {
 
@@ -24,10 +26,6 @@ std::string makeFixedOutputCA(FileIngestionMethod method, const Hash & hash)
         + hash.to_string(Base32, true);
 }
 
-// FIXME Put this somewhere?
-template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
-template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
-
 std::string renderContentAddress(ContentAddress ca) {
     return std::visit(overloaded {
         [](TextHash th) {
@@ -40,38 +38,46 @@ std::string renderContentAddress(ContentAddress ca) {
 }
 
 ContentAddress parseContentAddress(std::string_view rawCa) {
-    auto prefixSeparator = rawCa.find(':');
-    if (prefixSeparator != string::npos) {
-        auto prefix = string(rawCa, 0, prefixSeparator);
-        if (prefix == "text") {
-            auto hashTypeAndHash = rawCa.substr(prefixSeparator+1, string::npos);
-            Hash hash = Hash(string(hashTypeAndHash));
-            if (hash.type != htSHA256) {
-                throw Error("parseContentAddress: the text hash should have type SHA256");
-            }
-            return TextHash { hash };
-        } else if (prefix == "fixed") {
-            // This has to be an inverse of makeFixedOutputCA
-            auto methodAndHash = rawCa.substr(prefixSeparator+1, string::npos);
-            if (methodAndHash.substr(0,2) == "r:") {
-                std::string_view hashRaw = methodAndHash.substr(2,string::npos);
-                return FixedOutputHash {
-                    .method = FileIngestionMethod::Recursive,
-                    .hash = Hash(string(hashRaw)),
-                };
-            } else {
-                std::string_view hashRaw = methodAndHash;
-                return FixedOutputHash {
-                    .method = FileIngestionMethod::Flat,
-                    .hash = Hash(string(hashRaw)),
-                };
-            }
-        } else {
-            throw Error("parseContentAddress: format not recognized; has to be text or fixed");
-        }
-    } else {
-        throw Error("Not a content address because it lacks an appropriate prefix");
+    auto rest = rawCa;
+
+    std::string_view prefix;
+    {
+        auto optPrefix = splitPrefixTo(rest, ':');
+        if (!optPrefix)
+            throw UsageError("not a content address because it is not in the form '<prefix>:<rest>': %s", rawCa);
+        prefix = *optPrefix;
     }
+
+    auto parseHashType_ = [&](){
+        auto hashTypeRaw = splitPrefixTo(rest, ':');
+        if (!hashTypeRaw)
+            throw UsageError("content address hash must be in form '<algo>:<hash>', but found: %s", rawCa);
+        HashType hashType = parseHashType(*hashTypeRaw);
+        return std::move(hashType);
+    };
+
+    // Switch on prefix
+    if (prefix == "text") {
+        // No parsing of the method, "text" only support flat.
+        HashType hashType = parseHashType_();
+        if (hashType != htSHA256)
+            throw Error("text content address hash should use %s, but instead uses %s",
+                printHashType(htSHA256), printHashType(hashType));
+        return TextHash {
+            .hash = Hash::parseNonSRIUnprefixed(rest, std::move(hashType)),
+        };
+    } else if (prefix == "fixed") {
+        // Parse method
+        auto method = FileIngestionMethod::Flat;
+        if (splitPrefix(rest, "r:"))
+            method = FileIngestionMethod::Recursive;
+        HashType hashType = parseHashType_();
+        return FixedOutputHash {
+            .method = method,
+            .hash = Hash::parseNonSRIUnprefixed(rest, std::move(hashType)),
+        };
+    } else
+        throw UsageError("content address prefix '%s' is unrecognized. Recogonized prefixes are 'text' or 'fixed'", prefix);
 };
 
 std::optional<ContentAddress> parseContentAddressOpt(std::string_view rawCaOpt) {
diff --git a/src/libstore/daemon.cc b/src/libstore/daemon.cc
index b9a750425..ad3fe1847 100644
--- a/src/libstore/daemon.cc
+++ b/src/libstore/daemon.cc
@@ -289,7 +289,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         logger->startWork();
         auto hash = store->queryPathInfo(path)->narHash;
         logger->stopWork();
-        to << hash->to_string(Base16, false);
+        to << hash.to_string(Base16, false);
         break;
     }
 
@@ -454,8 +454,46 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         readDerivation(from, *store, drv, Derivation::nameFromPath(drvPath));
         BuildMode buildMode = (BuildMode) readInt(from);
         logger->startWork();
-        if (!trusted)
-            throw Error("you are not privileged to build derivations");
+
+        /* Content-addressed derivations are trustless because their output paths
+           are verified by their content alone, so any derivation is free to
+           try to produce such a path.
+
+           Input-addressed derivation output paths, however, are calculated
+           from the derivation closure that produced them---even knowing the
+           root derivation is not enough. That the output data actually came
+           from those derivations is fundamentally unverifiable, but the daemon
+           trusts itself on that matter. The question instead is whether the
+           submitted plan has rights to the output paths it wants to fill, and
+           at least the derivation closure proves that.
+
+           It would have been nice if input-address algorithm merely depended
+           on the build time closure, rather than depending on the derivation
+           closure. That would mean input-addressed paths used at build time
+           would just be trusted and not need their own evidence. This is in
+           fact fine as the same guarantees would hold *inductively*: either
+           the remote builder has those paths and already trusts them, or it
+           needs to build them too and thus their evidence must be provided in
+           turn.  The advantage of this variant algorithm is that the evidence
+           for input-addressed paths which the remote builder already has
+           doesn't need to be sent again.
+
+           That said, now that we have floating CA derivations, it is better
+           that people just migrate to those which also solve this problem, and
+           others. It's the same migration difficulty with strictly more
+           benefit.
+
+           Lastly, do note that when we parse fixed-output content-addressed
+           derivations, we throw out the precomputed output paths and just
+           store the hashes, so there aren't two competing sources of truth an
+           attacker could exploit. */
+        if (drv.type() == DerivationType::InputAddressed && !trusted)
+            throw Error("you are not privileged to build input-addressed derivations");
+
+        /* Make sure that the non-input-addressed derivations that got this far
+           are in fact content-addressed if we don't trust them. */
+        assert(derivationIsCA(drv.type()) || trusted);
+
         auto res = store->buildDerivation(drvPath, drv, buildMode);
         logger->stopWork();
         to << res.status << res.errorMsg;
@@ -638,7 +676,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
             if (GET_PROTOCOL_MINOR(clientVersion) >= 17)
                 to << 1;
             to << (info->deriver ? store->printStorePath(*info->deriver) : "")
-               << info->narHash->to_string(Base16, false);
+               << info->narHash.to_string(Base16, false);
             writeStorePaths(*store, to, info->references);
             to << info->registrationTime << info->narSize;
             if (GET_PROTOCOL_MINOR(clientVersion) >= 16) {
@@ -688,17 +726,18 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         auto path = store->parseStorePath(readString(from));
         logger->startWork();
         logger->stopWork();
-        dumpPath(store->printStorePath(path), to);
+        dumpPath(store->toRealPath(path), to);
         break;
     }
 
     case wopAddToStoreNar: {
         bool repair, dontCheckSigs;
-        ValidPathInfo info(store->parseStorePath(readString(from)));
+        auto path = store->parseStorePath(readString(from));
         auto deriver = readString(from);
+        auto narHash = Hash::parseAny(readString(from), htSHA256);
+        ValidPathInfo info { path, narHash };
         if (deriver != "")
             info.deriver = store->parseStorePath(deriver);
-        info.narHash = Hash(readString(from), htSHA256);
         info.references = readStorePaths<StorePathSet>(*store, from);
         from >> info.registrationTime >> info.narSize >> info.ultimate;
         info.sigs = readStrings<StringSet>(from);
@@ -817,8 +856,7 @@ void processConnection(
     FdSink & to,
     TrustedFlag trusted,
     RecursiveFlag recursive,
-    const std::string & userName,
-    uid_t userId)
+    std::function<void(Store &)> authHook)
 {
     auto monitor = !recursive ? std::make_unique<MonitorFdHup>(from.fd) : nullptr;
 
@@ -859,15 +897,7 @@ void processConnection(
 
         /* If we can't accept clientVersion, then throw an error
            *here* (not above). */
-
-#if 0
-        /* Prevent users from doing something very dangerous. */
-        if (geteuid() == 0 &&
-            querySetting("build-users-group", "") == "")
-            throw Error("if you run 'nix-daemon' as root, then you MUST set 'build-users-group'!");
-#endif
-
-        store->createUser(userName, userId);
+        authHook(*store);
 
         tunnelLogger->stopWork();
         to.flush();
diff --git a/src/libstore/daemon.hh b/src/libstore/daemon.hh
index 266932013..841ace316 100644
--- a/src/libstore/daemon.hh
+++ b/src/libstore/daemon.hh
@@ -12,7 +12,10 @@ void processConnection(
     FdSink & to,
     TrustedFlag trusted,
     RecursiveFlag recursive,
-    const std::string & userName,
-    uid_t userId);
+    /* Arbitrary hook to check authorization / initialize user data / whatever
+       after the protocol has been negotiated. The idea is that this function
+       and everything it calls doesn't know about this stuff, and the
+       `nix-daemon` handles that instead. */
+    std::function<void(Store &)> authHook);
 
 }
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index 8815c4632..abbef9aa2 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -7,23 +7,54 @@
 
 namespace nix {
 
-// FIXME Put this somewhere?
-template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
-template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
-
-StorePath DerivationOutput::path(const Store & store, std::string_view drvName) const
+std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::string_view drvName) const
 {
     return std::visit(overloaded {
-        [](DerivationOutputInputAddressed doi) {
-            return doi.path;
+        [](DerivationOutputInputAddressed doi) -> std::optional<StorePath> {
+            return { doi.path };
+        },
+        [&](DerivationOutputCAFixed dof) -> std::optional<StorePath> {
+            return {
+                store.makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName)
+            };
+        },
+        [](DerivationOutputCAFloating dof) -> std::optional<StorePath> {
+            return std::nullopt;
         },
-        [&](DerivationOutputFixed dof) {
-            return store.makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName);
-        }
     }, output);
 }
 
 
+bool derivationIsCA(DerivationType dt) {
+    switch (dt) {
+    case DerivationType::InputAddressed: return false;
+    case DerivationType::CAFixed: return true;
+    case DerivationType::CAFloating: return true;
+    };
+    // Since enums can have non-variant values, but making a `default:` would
+    // disable exhaustiveness warnings.
+    assert(false);
+}
+
+bool derivationIsFixed(DerivationType dt) {
+    switch (dt) {
+    case DerivationType::InputAddressed: return false;
+    case DerivationType::CAFixed: return true;
+    case DerivationType::CAFloating: return false;
+    };
+    assert(false);
+}
+
+bool derivationIsImpure(DerivationType dt) {
+    switch (dt) {
+    case DerivationType::InputAddressed: return false;
+    case DerivationType::CAFixed: return true;
+    case DerivationType::CAFloating: return false;
+    };
+    assert(false);
+}
+
+
 bool BasicDerivation::isBuiltin() const
 {
     return string(builder, 0, 8) == "builtin:";
@@ -31,7 +62,7 @@ bool BasicDerivation::isBuiltin() const
 
 
 StorePath writeDerivation(ref<Store> store,
-    const Derivation & drv, std::string_view name, RepairFlag repair)
+    const Derivation & drv, RepairFlag repair)
 {
     auto references = drv.inputSrcs;
     for (auto & i : drv.inputDrvs)
@@ -39,7 +70,7 @@ StorePath writeDerivation(ref<Store> store,
     /* Note that the outputs of a derivation are *not* references
        (that can be missing (of course) and should not necessarily be
        held during a garbage collection). */
-    auto suffix = std::string(name) + drvExtension;
+    auto suffix = std::string(drv.name) + drvExtension;
     auto contents = drv.unparse(*store, false);
     return settings.readOnlyMode
         ? store->computeStorePathForText(suffix, contents, references)
@@ -108,29 +139,33 @@ static StringSet parseStrings(std::istream & str, bool arePaths)
 }
 
 
-static DerivationOutput parseDerivationOutput(const Store & store, std::istringstream & str)
+static DerivationOutput parseDerivationOutput(const Store & store,
+    StorePath path, std::string_view hashAlgo, std::string_view hash)
 {
-    expect(str, ","); auto path = store.parseStorePath(parsePath(str));
-    expect(str, ","); auto hashAlgo = parseString(str);
-    expect(str, ","); const auto hash = parseString(str);
-    expect(str, ")");
-
     if (hashAlgo != "") {
         auto method = FileIngestionMethod::Flat;
         if (string(hashAlgo, 0, 2) == "r:") {
             method = FileIngestionMethod::Recursive;
-            hashAlgo = string(hashAlgo, 2);
+            hashAlgo = hashAlgo.substr(2);
         }
         const HashType hashType = parseHashType(hashAlgo);
 
-        return DerivationOutput {
-            .output = DerivationOutputFixed {
-                .hash = FixedOutputHash {
-                    .method = std::move(method),
-                    .hash = Hash(hash, hashType),
-                },
-            }
-        };
+        return hash != ""
+            ? DerivationOutput {
+                  .output = DerivationOutputCAFixed {
+                      .hash = FixedOutputHash {
+                          .method = std::move(method),
+                          .hash = Hash::parseNonSRIUnprefixed(hash, hashType),
+                      },
+                  }
+               }
+            : (settings.requireExperimentalFeature("ca-derivations"),
+              DerivationOutput {
+                  .output =  DerivationOutputCAFloating {
+                      .method = std::move(method),
+                      .hashType = std::move(hashType),
+                  },
+              });
     } else
         return DerivationOutput {
             .output = DerivationOutputInputAddressed {
@@ -139,6 +174,16 @@ static DerivationOutput parseDerivationOutput(const Store & store, std::istrings
         };
 }
 
+static DerivationOutput parseDerivationOutput(const Store & store, std::istringstream & str)
+{
+    expect(str, ","); auto path = store.parseStorePath(parsePath(str));
+    expect(str, ","); const auto hashAlgo = parseString(str);
+    expect(str, ","); const auto hash = parseString(str);
+    expect(str, ")");
+
+    return parseDerivationOutput(store, std::move(path), hashAlgo, hash);
+}
+
 
 Derivation parseDerivation(const Store & store, std::string && s, std::string_view name)
 {
@@ -250,13 +295,20 @@ string Derivation::unparse(const Store & store, bool maskOutputs,
         if (first) first = false; else s += ',';
         s += '('; printUnquotedString(s, i.first);
         s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(i.second.path(store, name)));
-        if (auto hash = std::get_if<DerivationOutputFixed>(&i.second.output)) {
-            s += ','; printUnquotedString(s, hash->hash.printMethodAlgo());
-            s += ','; printUnquotedString(s, hash->hash.hash.to_string(Base16, false));
-        } else {
-            s += ','; printUnquotedString(s, "");
-            s += ','; printUnquotedString(s, "");
-        }
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed doi) {
+                s += ','; printUnquotedString(s, "");
+                s += ','; printUnquotedString(s, "");
+            },
+            [&](DerivationOutputCAFixed dof) {
+                s += ','; printUnquotedString(s, dof.hash.printMethodAlgo());
+                s += ','; printUnquotedString(s, dof.hash.hash.to_string(Base16, false));
+            },
+            [&](DerivationOutputCAFloating dof) {
+                s += ','; printUnquotedString(s, makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
+                s += ','; printUnquotedString(s, "");
+            },
+        }, i.second.output);
         s += ')';
     }
 
@@ -308,60 +360,134 @@ bool isDerivation(const string & fileName)
 }
 
 
-bool BasicDerivation::isFixedOutput() const
+DerivationType BasicDerivation::type() const
 {
-    return outputs.size() == 1 &&
-        outputs.begin()->first == "out" &&
-        std::holds_alternative<DerivationOutputFixed>(outputs.begin()->second.output);
+    std::set<std::string_view> inputAddressedOutputs, fixedCAOutputs, floatingCAOutputs;
+    std::optional<HashType> floatingHashType;
+    for (auto & i : outputs) {
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed _) {
+               inputAddressedOutputs.insert(i.first);
+            },
+            [&](DerivationOutputCAFixed _) {
+                fixedCAOutputs.insert(i.first);
+            },
+            [&](DerivationOutputCAFloating dof) {
+                floatingCAOutputs.insert(i.first);
+                if (!floatingHashType) {
+                    floatingHashType = dof.hashType;
+                } else {
+                    if (*floatingHashType != dof.hashType)
+                        throw Error("All floating outputs must use the same hash type");
+                }
+            },
+        }, i.second.output);
+    }
+
+    if (inputAddressedOutputs.empty() && fixedCAOutputs.empty() && floatingCAOutputs.empty()) {
+        throw Error("Must have at least one output");
+    } else if (! inputAddressedOutputs.empty() && fixedCAOutputs.empty() && floatingCAOutputs.empty()) {
+        return DerivationType::InputAddressed;
+    } else if (inputAddressedOutputs.empty() && ! fixedCAOutputs.empty() && floatingCAOutputs.empty()) {
+        if (fixedCAOutputs.size() > 1)
+            // FIXME: Experimental feature?
+            throw Error("Only one fixed output is allowed for now");
+        if (*fixedCAOutputs.begin() != "out")
+            throw Error("Single fixed output must be named \"out\"");
+        return DerivationType::CAFixed;
+    } else if (inputAddressedOutputs.empty() && fixedCAOutputs.empty() && ! floatingCAOutputs.empty()) {
+        return DerivationType::CAFloating;
+    } else {
+        throw Error("Can't mix derivation output types");
+    }
 }
 
 
 DrvHashes drvHashes;
 
+/* pathDerivationModulo and hashDerivationModulo are mutually recursive
+ */
+
+/* Look up the derivation by value and memoize the
+   `hashDerivationModulo` call.
+ */
+static const DrvHashModulo & pathDerivationModulo(Store & store, const StorePath & drvPath)
+{
+    auto h = drvHashes.find(drvPath);
+    if (h == drvHashes.end()) {
+        assert(store.isValidPath(drvPath));
+        // Cache it
+        h = drvHashes.insert_or_assign(
+            drvPath,
+            hashDerivationModulo(
+                store,
+                store.readDerivation(drvPath),
+                false)).first;
+    }
+    return h->second;
+}
 
-/* Returns the hash of a derivation modulo fixed-output
-   subderivations.  A fixed-output derivation is a derivation with one
-   output (`out') for which an expected hash and hash algorithm are
-   specified (using the `outputHash' and `outputHashAlgo'
-   attributes).  We don't want changes to such derivations to
-   propagate upwards through the dependency graph, changing output
-   paths everywhere.
-
-   For instance, if we change the url in a call to the `fetchurl'
-   function, we do not want to rebuild everything depending on it
-   (after all, (the hash of) the file being downloaded is unchanged).
-   So the *output paths* should not change.  On the other hand, the
-   *derivation paths* should change to reflect the new dependency
-   graph.
-
-   That's what this function does: it returns a hash which is just the
-   hash of the derivation ATerm, except that any input derivation
-   paths have been replaced by the result of a recursive call to this
-   function, and that for fixed-output derivations we return a hash of
-   its output path. */
-Hash hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs)
+/* See the header for interface details. These are the implementation details.
+
+   For fixed-output derivations, each hash in the map is not the
+   corresponding output's content hash, but a hash of that hash along
+   with other constant data. The key point is that the value is a pure
+   function of the output's contents, and there are no preimage attacks
+   either spoofing an output's contents for a derivation, or
+   spoofing a derivation for an output's contents.
+
+   For regular derivations, it looks up each subderivation from its hash
+   and recurs. If the subderivation is also regular, it simply
+   substitutes the derivation path with its hash. If the subderivation
+   is fixed-output, however, it takes each output hash and pretends it
+   is a derivation hash producing a single "out" output. This is so we
+   don't leak the provenance of fixed outputs, reducing pointless cache
+   misses as the build itself won't know this.
+ */
+DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs)
 {
     /* Return a fixed hash for fixed-output derivations. */
-    if (drv.isFixedOutput()) {
-        DerivationOutputs::const_iterator i = drv.outputs.begin();
-        auto hash = std::get<DerivationOutputFixed>(i->second.output);
-        return hashString(htSHA256, "fixed:out:"
-            + hash.hash.printMethodAlgo() + ":"
-            + hash.hash.hash.to_string(Base16, false) + ":"
-            + store.printStorePath(i->second.path(store, drv.name)));
+    switch (drv.type()) {
+    case DerivationType::CAFloating:
+        throw Error("Regular input-addressed derivations are not yet allowed to depend on CA derivations");
+    case DerivationType::CAFixed: {
+        std::map<std::string, Hash> outputHashes;
+        for (const auto & i : drv.outputsAndPaths(store)) {
+            auto & dof = std::get<DerivationOutputCAFixed>(i.second.first.output);
+            auto hash = hashString(htSHA256, "fixed:out:"
+                + dof.hash.printMethodAlgo() + ":"
+                + dof.hash.hash.to_string(Base16, false) + ":"
+                + store.printStorePath(i.second.second));
+            outputHashes.insert_or_assign(i.first, std::move(hash));
+        }
+        return outputHashes;
+    }
+    case DerivationType::InputAddressed:
+        break;
     }
 
     /* For other derivations, replace the inputs paths with recursive
-       calls to this function.*/
+       calls to this function. */
     std::map<std::string, StringSet> inputs2;
     for (auto & i : drv.inputDrvs) {
-        auto h = drvHashes.find(i.first);
-        if (h == drvHashes.end()) {
-            assert(store.isValidPath(i.first));
-            h = drvHashes.insert_or_assign(i.first, hashDerivationModulo(store,
-                store.readDerivation(i.first), false)).first;
-        }
-        inputs2.insert_or_assign(h->second.to_string(Base16, false), i.second);
+        const auto & res = pathDerivationModulo(store, i.first);
+        std::visit(overloaded {
+            // Regular non-CA derivation, replace derivation
+            [&](Hash drvHash) {
+                inputs2.insert_or_assign(drvHash.to_string(Base16, false), i.second);
+            },
+            // CA derivation's output hashes
+            [&](CaOutputHashes outputHashes) {
+                std::set<std::string> justOut = { "out" };
+                for (auto & output : i.second) {
+                    /* Put each one in with a single "out" output.. */
+                    const auto h = outputHashes.at(output);
+                    inputs2.insert_or_assign(
+                        h.to_string(Base16, false),
+                        justOut);
+                }
+            },
+        }, res);
     }
 
     return hashString(htSHA256, drv.unparse(store, maskOutputs, &inputs2));
@@ -385,38 +511,18 @@ bool wantOutput(const string & output, const std::set<string> & wanted)
 StorePathSet BasicDerivation::outputPaths(const Store & store) const
 {
     StorePathSet paths;
-    for (auto & i : outputs)
-        paths.insert(i.second.path(store, name));
+    for (auto & i : outputsAndPaths(store))
+        paths.insert(i.second.second);
     return paths;
 }
 
 static DerivationOutput readDerivationOutput(Source & in, const Store & store)
 {
     auto path = store.parseStorePath(readString(in));
-    auto hashAlgo = readString(in);
-    auto hash = readString(in);
+    const auto hashAlgo = readString(in);
+    const auto hash = readString(in);
 
-    if (hashAlgo != "") {
-        auto method = FileIngestionMethod::Flat;
-        if (string(hashAlgo, 0, 2) == "r:") {
-            method = FileIngestionMethod::Recursive;
-            hashAlgo = string(hashAlgo, 2);
-        }
-        auto hashType = parseHashType(hashAlgo);
-        return DerivationOutput {
-            .output = DerivationOutputFixed {
-                .hash = FixedOutputHash {
-                    .method = std::move(method),
-                    .hash = Hash(hash, hashType),
-                },
-            }
-        };
-    } else
-        return DerivationOutput {
-            .output = DerivationOutputInputAddressed {
-                .path = std::move(path),
-            }
-        };
+    return parseDerivationOutput(store, std::move(path), hashAlgo, hash);
 }
 
 StringSet BasicDerivation::outputNames() const
@@ -427,6 +533,27 @@ StringSet BasicDerivation::outputNames() const
     return names;
 }
 
+DerivationOutputsAndPaths BasicDerivation::outputsAndPaths(const Store & store) const {
+    DerivationOutputsAndPaths outsAndPaths;
+    for (auto output : outputs)
+        outsAndPaths.insert(std::make_pair(
+            output.first,
+            std::make_pair(output.second, output.second.path(store, name))
+            )
+        );
+    return outsAndPaths;
+}
+
+DerivationOutputsAndOptPaths BasicDerivation::outputsAndOptPaths(const Store & store) const {
+    DerivationOutputsAndOptPaths outsAndOptPaths;
+    for (auto output : outputs)
+        outsAndOptPaths.insert(std::make_pair(
+            output.first,
+            std::make_pair(output.second, output.second.pathOpt(store, output.first))
+            )
+        );
+    return outsAndOptPaths;
+}
 
 std::string_view BasicDerivation::nameFromPath(const StorePath & drvPath) {
     auto nameWithSuffix = drvPath.name();
@@ -467,15 +594,22 @@ Source & readDerivation(Source & in, const Store & store, BasicDerivation & drv,
 void writeDerivation(Sink & out, const Store & store, const BasicDerivation & drv)
 {
     out << drv.outputs.size();
-    for (auto & i : drv.outputs) {
+    for (auto & i : drv.outputsAndPaths(store)) {
         out << i.first
-            << store.printStorePath(i.second.path(store, drv.name));
-        if (auto hash = std::get_if<DerivationOutputFixed>(&i.second.output)) {
-            out << hash->hash.printMethodAlgo()
-                << hash->hash.hash.to_string(Base16, false);
-        } else {
-            out << "" << "";
-        }
+            << store.printStorePath(i.second.second);
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed doi) {
+                out << "" << "";
+            },
+            [&](DerivationOutputCAFixed dof) {
+                out << dof.hash.printMethodAlgo()
+                    << dof.hash.hash.to_string(Base16, false);
+            },
+            [&](DerivationOutputCAFloating dof) {
+                out << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
+                    << "";
+            },
+        }, i.second.first.output);
     }
     writeStorePaths(store, out, drv.inputSrcs);
     out << drv.platform << drv.builder << drv.args;
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 112b2a8ca..38c4b75c0 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -6,6 +6,7 @@
 #include "content-address.hh"
 
 #include <map>
+#include <variant>
 
 
 namespace nix {
@@ -13,30 +14,87 @@ namespace nix {
 
 /* Abstract syntax of derivations. */
 
+/* The traditional non-fixed-output derivation type. */
 struct DerivationOutputInputAddressed
 {
+    /* Will need to become `std::optional<StorePath>` once input-addressed
+       derivations are allowed to depend on cont-addressed derivations */
     StorePath path;
 };
 
-struct DerivationOutputFixed
+/* Fixed-output derivations, whose output paths are content addressed
+   according to that fixed output. */
+struct DerivationOutputCAFixed
 {
     FixedOutputHash hash; /* hash used for expected hash computation */
 };
 
+/* Floating-output derivations, whose output paths are content addressed, but
+   not fixed, and so are dynamically calculated from whatever the output ends
+   up being. */
+struct DerivationOutputCAFloating
+{
+    /* information used for expected hash computation */
+    FileIngestionMethod method;
+    HashType hashType;
+};
+
 struct DerivationOutput
 {
-    std::variant<DerivationOutputInputAddressed, DerivationOutputFixed> output;
-    StorePath path(const Store & store, std::string_view drvName) const;
+    std::variant<
+        DerivationOutputInputAddressed,
+        DerivationOutputCAFixed,
+        DerivationOutputCAFloating
+    > 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::outputsAndPaths */
+    std::optional<StorePath> pathOpt(const Store & store, std::string_view drvName) const;
+    /* DEPRECATED: Remove after CA drvs are fully implemented */
+    StorePath path(const Store & store, std::string_view drvName) const {
+        auto p = pathOpt(store, drvName);
+        if (!p) throw UnimplementedError("floating content-addressed derivations are not yet implemented");
+        return *p;
+    }
 };
 
 typedef std::map<string, DerivationOutput> DerivationOutputs;
 
+/* These are analogues to the previous DerivationOutputs data type, but they
+   also contains, for each output, the (optional) store path in which it would
+   be written. To calculate values of these types, see the corresponding
+   functions in BasicDerivation */
+typedef std::map<string, std::pair<DerivationOutput, StorePath>>
+  DerivationOutputsAndPaths;
+typedef std::map<string, std::pair<DerivationOutput, std::optional<StorePath>>>
+  DerivationOutputsAndOptPaths;
+
 /* For inputs that are sub-derivations, we specify exactly which
    output IDs we are interested in. */
 typedef std::map<StorePath, StringSet> DerivationInputs;
 
 typedef std::map<string, string> StringPairs;
 
+enum struct DerivationType : uint8_t {
+    InputAddressed,
+    CAFixed,
+    CAFloating,
+};
+
+/* Do the outputs of the derivation have paths calculated from their content,
+   or from the derivation itself? */
+bool derivationIsCA(DerivationType);
+
+/* Is the content of the outputs fixed a-priori via a hash? Never true for
+   non-CA derivations. */
+bool derivationIsFixed(DerivationType);
+
+/* Is the derivation impure and needs to access non-deterministic resources, or
+   pure and can be sandboxed? Note that whether or not we actually sandbox the
+   derivation is controlled separately. Never true for non-CA derivations. */
+bool derivationIsImpure(DerivationType);
+
 struct BasicDerivation
 {
     DerivationOutputs outputs; /* keyed on symbolic IDs */
@@ -53,7 +111,7 @@ struct BasicDerivation
     bool isBuiltin() const;
 
     /* Return true iff this is a fixed-output derivation. */
-    bool isFixedOutput() const;
+    DerivationType type() const;
 
     /* Return the output paths of a derivation. */
     StorePathSet outputPaths(const Store & store) const;
@@ -61,6 +119,13 @@ struct BasicDerivation
     /* Return the output names of a derivation. */
     StringSet outputNames() const;
 
+    /* Calculates the maps that contains all the DerivationOutputs, but
+       augmented with knowledge of the Store paths they would be written into.
+       The first one of these functions will be removed when the CA work is
+       completed */
+    DerivationOutputsAndPaths outputsAndPaths(const Store & store) const;
+    DerivationOutputsAndOptPaths outputsAndOptPaths(const Store & store) const;
+
     static std::string_view nameFromPath(const StorePath & storePath);
 };
 
@@ -82,7 +147,7 @@ enum RepairFlag : bool { NoRepair = false, Repair = true };
 
 /* Write a derivation to the Nix store, and return its path. */
 StorePath writeDerivation(ref<Store> store,
-    const Derivation & drv, std::string_view name, RepairFlag repair = NoRepair);
+    const Derivation & drv, RepairFlag repair = NoRepair);
 
 /* Read a derivation from a file. */
 Derivation parseDerivation(const Store & store, std::string && s, std::string_view name);
@@ -90,10 +155,42 @@ Derivation parseDerivation(const Store & store, std::string && s, std::string_vi
 // FIXME: remove
 bool isDerivation(const string & fileName);
 
-Hash hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs);
+// known CA drv's output hashes, current just for fixed-output derivations
+// whose output hashes are always known since they are fixed up-front.
+typedef std::map<std::string, Hash> CaOutputHashes;
+
+typedef std::variant<
+    Hash, // regular DRV normalized hash
+    CaOutputHashes
+> DrvHashModulo;
+
+/* Returns hashes with the details of fixed-output subderivations
+   expunged.
+
+   A fixed-output derivation is a derivation whose outputs have a
+   specified content hash and hash algorithm. (Currently they must have
+   exactly one output (`out'), which is specified using the `outputHash'
+   and `outputHashAlgo' attributes, but the algorithm doesn't assume
+   this.) We don't want changes to such derivations to propagate upwards
+   through the dependency graph, changing output paths everywhere.
+
+   For instance, if we change the url in a call to the `fetchurl'
+   function, we do not want to rebuild everything depending on it---after
+   all, (the hash of) the file being downloaded is unchanged.  So the
+   *output paths* should not change. On the other hand, the *derivation
+   paths* should change to reflect the new dependency graph.
+
+   For fixed-output derivations, this returns a map from the name of
+   each output to its hash, unique up to the output's contents.
+
+   For regular derivations, it returns a single hash of the derivation
+   ATerm, after subderivations have been likewise expunged from that
+   derivation.
+ */
+DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs);
 
 /* Memoisation of hashDerivationModulo(). */
-typedef std::map<StorePath, Hash> DrvHashes;
+typedef std::map<StorePath, DrvHashModulo> DrvHashes;
 
 extern DrvHashes drvHashes; // FIXME: global, not thread-safe
 
diff --git a/src/libstore/export-import.cc b/src/libstore/export-import.cc
index a0fc22264..ccd466d09 100644
--- a/src/libstore/export-import.cc
+++ b/src/libstore/export-import.cc
@@ -38,9 +38,9 @@ void Store::exportPath(const StorePath & path, Sink & sink)
        filesystem corruption from spreading to other machines.
        Don't complain if the stored hash is zero (unknown). */
     Hash hash = hashSink.currentHash().first;
-    if (hash != info->narHash && info->narHash != Hash(info->narHash->type))
+    if (hash != info->narHash && info->narHash != Hash(info->narHash.type))
         throw Error("hash of path '%s' has changed from '%s' to '%s'!",
-            printStorePath(path), info->narHash->to_string(Base32, true), hash.to_string(Base32, true));
+            printStorePath(path), info->narHash.to_string(Base32, true), hash.to_string(Base32, true));
 
     teeSink
         << exportMagic
@@ -69,17 +69,18 @@ StorePaths Store::importPaths(Source & source, CheckSigsFlag checkSigs)
         if (magic != exportMagic)
             throw Error("Nix archive cannot be imported; wrong format");
 
-        ValidPathInfo info(parseStorePath(readString(source)));
+        auto path = parseStorePath(readString(source));
 
         //Activity act(*logger, lvlInfo, format("importing path '%s'") % info.path);
 
-        info.references = readStorePaths<StorePathSet>(*this, source);
-
+        auto references = readStorePaths<StorePathSet>(*this, source);
         auto deriver = readString(source);
+        auto narHash = hashString(htSHA256, *saved.s);
+
+        ValidPathInfo info { path, narHash };
         if (deriver != "")
             info.deriver = parseStorePath(deriver);
-
-        info.narHash = hashString(htSHA256, *saved.s);
+        info.references = references;
         info.narSize = saved.s->size();
 
         // Ignore optional legacy signature.
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
index 3406a9331..e3bb4cf84 100644
--- a/src/libstore/globals.hh
+++ b/src/libstore/globals.hh
@@ -335,6 +335,9 @@ public:
         "setuid/setgid bits or with file capabilities."};
 #endif
 
+    Setting<Strings> hashedMirrors{this, {}, "hashed-mirrors",
+        "A list of servers used by builtins.fetchurl to fetch files by hash."};
+
     Setting<uint64_t> minFree{this, 0, "min-free",
         "Automatically run the garbage collector when free disk space drops below the specified amount."};
 
diff --git a/src/libstore/legacy-ssh-store.cc b/src/libstore/legacy-ssh-store.cc
index 5d7566121..dc03313f0 100644
--- a/src/libstore/legacy-ssh-store.cc
+++ b/src/libstore/legacy-ssh-store.cc
@@ -93,6 +93,9 @@ struct LegacySSHStore : public Store
         try {
             auto conn(connections->get());
 
+            /* No longer support missing NAR hash */
+            assert(GET_PROTOCOL_MINOR(conn->remoteVersion) >= 4);
+
             debug("querying remote host '%s' for info on '%s'", host, printStorePath(path));
 
             conn->to << cmdQueryPathInfos << PathSet{printStorePath(path)};
@@ -100,8 +103,10 @@ struct LegacySSHStore : public Store
 
             auto p = readString(conn->from);
             if (p.empty()) return callback(nullptr);
-            auto info = std::make_shared<ValidPathInfo>(parseStorePath(p));
-            assert(path == info->path);
+            auto path2 = parseStorePath(p);
+            assert(path == path2);
+            /* Hash will be set below. FIXME construct ValidPathInfo at end. */
+            auto info = std::make_shared<ValidPathInfo>(path, Hash::dummy);
 
             PathSet references;
             auto deriver = readString(conn->from);
@@ -111,12 +116,14 @@ struct LegacySSHStore : public Store
             readLongLong(conn->from); // download size
             info->narSize = readLongLong(conn->from);
 
-            if (GET_PROTOCOL_MINOR(conn->remoteVersion) >= 4) {
+            {
                 auto s = readString(conn->from);
-                info->narHash = s.empty() ? std::optional<Hash>{} : Hash{s};
-                info->ca = parseContentAddressOpt(readString(conn->from));
-                info->sigs = readStrings<StringSet>(conn->from);
+                if (s == "")
+                    throw Error("NAR hash is now mandatory");
+                info->narHash = Hash::parseAnyPrefixed(s);
             }
+            info->ca = parseContentAddressOpt(readString(conn->from));
+            info->sigs = readStrings<StringSet>(conn->from);
 
             auto s = readString(conn->from);
             assert(s == "");
@@ -138,7 +145,7 @@ struct LegacySSHStore : public Store
                 << cmdAddToStoreNar
                 << printStorePath(info.path)
                 << (info.deriver ? printStorePath(*info.deriver) : "")
-                << info.narHash->to_string(Base16, false);
+                << info.narHash.to_string(Base16, false);
             writeStorePaths(*this, conn->to, info.references);
             conn->to
                 << info.registrationTime
@@ -202,6 +209,24 @@ struct LegacySSHStore : public Store
         const StorePathSet & references, RepairFlag repair) override
     { unsupported("addTextToStore"); }
 
+private:
+
+    void putBuildSettings(Connection & conn)
+    {
+        conn.to
+            << settings.maxSilentTime
+            << settings.buildTimeout;
+        if (GET_PROTOCOL_MINOR(conn.remoteVersion) >= 2)
+            conn.to
+                << settings.maxLogSize;
+        if (GET_PROTOCOL_MINOR(conn.remoteVersion) >= 3)
+            conn.to
+                << settings.buildRepeat
+                << settings.enforceDeterminism;
+    }
+
+public:
+
     BuildResult buildDerivation(const StorePath & drvPath, const BasicDerivation & drv,
         BuildMode buildMode) override
     {
@@ -211,16 +236,8 @@ struct LegacySSHStore : public Store
             << cmdBuildDerivation
             << printStorePath(drvPath);
         writeDerivation(conn->to, *this, drv);
-        conn->to
-            << settings.maxSilentTime
-            << settings.buildTimeout;
-        if (GET_PROTOCOL_MINOR(conn->remoteVersion) >= 2)
-            conn->to
-                << settings.maxLogSize;
-        if (GET_PROTOCOL_MINOR(conn->remoteVersion) >= 3)
-            conn->to
-                << settings.buildRepeat
-                << settings.enforceDeterminism;
+
+        putBuildSettings(*conn);
 
         conn->to.flush();
 
@@ -234,6 +251,29 @@ struct LegacySSHStore : public Store
         return status;
     }
 
+    void buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode) override
+    {
+        auto conn(connections->get());
+
+        conn->to << cmdBuildPaths;
+        Strings ss;
+        for (auto & p : drvPaths)
+            ss.push_back(p.to_string(*this));
+        conn->to << ss;
+
+        putBuildSettings(*conn);
+
+        conn->to.flush();
+
+        BuildResult result;
+        result.status = (BuildResult::Status) readInt(conn->from);
+
+        if (!result.success()) {
+            conn->from >> result.errorMsg;
+            throw Error(result.status, result.errorMsg);
+        }
+    }
+
     void ensurePath(const StorePath & path) override
     { unsupported("ensurePath"); }
 
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index f6ce8877e..bccd77b68 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -544,11 +544,8 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
     std::string drvName(drvPath.name());
     drvName = string(drvName, 0, drvName.size() - drvExtension.size());
 
-    auto check = [&](const StorePath & expected, const StorePath & actual, const std::string & varName)
+    auto envHasRightPath = [&](const StorePath & actual, const std::string & varName)
     {
-        if (actual != expected)
-            throw Error("derivation '%s' has incorrect output '%s', should be '%s'",
-                printStorePath(drvPath), printStorePath(actual), printStorePath(expected));
         auto j = drv.env.find(varName);
         if (j == drv.env.end() || parseStorePath(j->second) != actual)
             throw Error("derivation '%s' has incorrect environment variable '%s', should be '%s'",
@@ -556,16 +553,34 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
     };
 
 
-    if (drv.isFixedOutput()) {
-        DerivationOutputs::const_iterator out = drv.outputs.find("out");
-        if (out == drv.outputs.end())
-            throw Error("derivation '%s' does not have an output named 'out'", printStorePath(drvPath));
-    }
+    // Don't need the answer, but do this anyways to assert is proper
+    // combination. The code below is more general and naturally allows
+    // combinations that are currently prohibited.
+    drv.type();
 
-    else {
-        Hash h = hashDerivationModulo(*this, drv, true);
-        for (auto & i : drv.outputs)
-            check(makeOutputPath(i.first, h, drvName), i.second.path(*this, drv.name), i.first);
+    std::optional<Hash> h;
+    for (auto & i : drv.outputs) {
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed doia) {
+                if (!h) {
+                    // somewhat expensive so we do lazily
+                    auto temp = hashDerivationModulo(*this, drv, true);
+                    h = std::get<Hash>(temp);
+                }
+                StorePath recomputed = makeOutputPath(i.first, *h, drvName);
+                if (doia.path != recomputed)
+                    throw Error("derivation '%s' has incorrect output '%s', should be '%s'",
+                        printStorePath(drvPath), printStorePath(doia.path), printStorePath(recomputed));
+                envHasRightPath(doia.path, i.first);
+            },
+            [&](DerivationOutputCAFixed dof) {
+                StorePath path = makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName);
+                envHasRightPath(path, i.first);
+            },
+            [&](DerivationOutputCAFloating _) {
+                throw UnimplementedError("floating CA output derivations are not yet implemented");
+            },
+        }, i.second.output);
     }
 }
 
@@ -579,7 +594,7 @@ uint64_t LocalStore::addValidPath(State & state,
 
     state.stmtRegisterValidPath.use()
         (printStorePath(info.path))
-        (info.narHash->to_string(Base16, true))
+        (info.narHash.to_string(Base16, true))
         (info.registrationTime == 0 ? time(0) : info.registrationTime)
         (info.deriver ? printStorePath(*info.deriver) : "", (bool) info.deriver)
         (info.narSize, info.narSize != 0)
@@ -603,11 +618,11 @@ uint64_t LocalStore::addValidPath(State & state,
            registration above is undone. */
         if (checkOutputs) checkDerivationOutputs(info.path, drv);
 
-        for (auto & i : drv.outputs) {
+        for (auto & i : drv.outputsAndPaths(*this)) {
             state.stmtAddDerivationOutput.use()
                 (id)
                 (i.first)
-                (printStorePath(i.second.path(*this, drv.name)))
+                (printStorePath(i.second.second))
                 .exec();
         }
     }
@@ -626,25 +641,28 @@ void LocalStore::queryPathInfoUncached(const StorePath & path,
     Callback<std::shared_ptr<const ValidPathInfo>> callback) noexcept
 {
     try {
-        auto info = std::make_shared<ValidPathInfo>(path);
-
         callback(retrySQLite<std::shared_ptr<ValidPathInfo>>([&]() {
             auto state(_state.lock());
 
             /* Get the path info. */
-            auto useQueryPathInfo(state->stmtQueryPathInfo.use()(printStorePath(info->path)));
+            auto useQueryPathInfo(state->stmtQueryPathInfo.use()(printStorePath(path)));
 
             if (!useQueryPathInfo.next())
                 return std::shared_ptr<ValidPathInfo>();
 
-            info->id = useQueryPathInfo.getInt(0);
+            auto id = useQueryPathInfo.getInt(0);
 
+            auto narHash = Hash::dummy;
             try {
-                info->narHash = Hash(useQueryPathInfo.getStr(1));
+                narHash = Hash::parseAnyPrefixed(useQueryPathInfo.getStr(1));
             } catch (BadHash & e) {
-                throw Error("in valid-path entry for '%s': %s", printStorePath(path), e.what());
+                throw Error("invalid-path entry for '%s': %s", printStorePath(path), e.what());
             }
 
+            auto info = std::make_shared<ValidPathInfo>(path, narHash);
+
+            info->id = id;
+
             info->registrationTime = useQueryPathInfo.getInt(2);
 
             auto s = (const char *) sqlite3_column_text(state->stmtQueryPathInfo, 3);
@@ -679,7 +697,7 @@ void LocalStore::updatePathInfo(State & state, const ValidPathInfo & info)
 {
     state.stmtUpdatePathInfo.use()
         (info.narSize, info.narSize != 0)
-        (info.narHash->to_string(Base16, true))
+        (info.narHash.to_string(Base16, true))
         (info.ultimate ? 1 : 0, info.ultimate)
         (concatStringsSep(" ", info.sigs), !info.sigs.empty())
         (renderContentAddress(info.ca), (bool) info.ca)
@@ -905,7 +923,7 @@ void LocalStore::registerValidPaths(const ValidPathInfos & infos)
         StorePathSet paths;
 
         for (auto & i : infos) {
-            assert(i.narHash && i.narHash->type == htSHA256);
+            assert(i.narHash.type == htSHA256);
             if (isValidPath_(*state, i.path))
                 updatePathInfo(*state, i);
             else
@@ -969,9 +987,6 @@ const PublicKeys & LocalStore::getPublicKeys()
 void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
     RepairFlag repair, CheckSigsFlag checkSigs)
 {
-    if (!info.narHash)
-        throw Error("cannot add path '%s' because it lacks a hash", printStorePath(info.path));
-
     if (requireSigs && checkSigs && !info.checkSignatures(*this, getPublicKeys()))
         throw Error("cannot add path '%s' because it lacks a valid signature", printStorePath(info.path));
 
@@ -1006,11 +1021,7 @@ void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
             else
                 hashSink = std::make_unique<HashModuloSink>(htSHA256, std::string(info.path.hashPart()));
 
-            LambdaSource wrapperSource([&](unsigned char * data, size_t len) -> size_t {
-                size_t n = source.read(data, len);
-                (*hashSink)(data, n);
-                return n;
-            });
+            TeeSource wrapperSource { source, *hashSink };
 
             restorePath(realPath, wrapperSource);
 
@@ -1018,7 +1029,7 @@ void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
 
             if (hashResult.first != info.narHash)
                 throw Error("hash mismatch importing path '%s';\n  wanted: %s\n  got:    %s",
-                    printStorePath(info.path), info.narHash->to_string(Base32, true), hashResult.first.to_string(Base32, true));
+                    printStorePath(info.path), info.narHash.to_string(Base32, true), hashResult.first.to_string(Base32, true));
 
             if (hashResult.second != info.narSize)
                 throw Error("size mismatch importing path '%s';\n  wanted: %s\n  got:   %s",
@@ -1038,20 +1049,6 @@ void LocalStore::addToStore(const ValidPathInfo & info, Source & source,
 }
 
 
-StorePath LocalStore::addToStore(const string & name, const Path & _srcPath,
-    FileIngestionMethod method, HashType hashAlgo, PathFilter & filter, RepairFlag repair)
-{
-    Path srcPath(absPath(_srcPath));
-    auto source = sinkToSource([&](Sink & sink) {
-        if (method == FileIngestionMethod::Recursive)
-            dumpPath(srcPath, sink, filter);
-        else
-            readFile(srcPath, sink);
-    });
-    return addToStoreFromDump(*source, name, method, hashAlgo, repair);
-}
-
-
 StorePath LocalStore::addToStoreFromDump(Source & source0, const string & name,
     FileIngestionMethod method, HashType hashAlgo, RepairFlag repair)
 {
@@ -1154,8 +1151,7 @@ StorePath LocalStore::addToStoreFromDump(Source & source0, const string & name,
 
             optimisePath(realPath);
 
-            ValidPathInfo info(dstPath);
-            info.narHash = narHash.first;
+            ValidPathInfo info { dstPath, narHash.first };
             info.narSize = narHash.second;
             info.ca = FixedOutputHash { .method = method, .hash = hash };
             registerValidPath(info);
@@ -1198,8 +1194,7 @@ StorePath LocalStore::addTextToStore(const string & name, const string & s,
 
             optimisePath(realPath);
 
-            ValidPathInfo info(dstPath);
-            info.narHash = narHash;
+            ValidPathInfo info { dstPath, narHash };
             info.narSize = sink.s->size();
             info.references = references;
             info.ca = TextHash { .hash = hash };
@@ -1314,9 +1309,9 @@ bool LocalStore::verifyStore(bool checkContents, RepairFlag repair)
 
                 std::unique_ptr<AbstractHashSink> hashSink;
                 if (!info->ca || !info->references.count(info->path))
-                    hashSink = std::make_unique<HashSink>(info->narHash->type);
+                    hashSink = std::make_unique<HashSink>(info->narHash.type);
                 else
-                    hashSink = std::make_unique<HashModuloSink>(info->narHash->type, std::string(info->path.hashPart()));
+                    hashSink = std::make_unique<HashModuloSink>(info->narHash.type, std::string(info->path.hashPart()));
 
                 dumpPath(Store::toRealPath(i), *hashSink);
                 auto current = hashSink->finish();
@@ -1325,7 +1320,7 @@ bool LocalStore::verifyStore(bool checkContents, RepairFlag repair)
                     logError({
                         .name = "Invalid hash - path modified",
                         .hint = hintfmt("path '%s' was modified! expected hash '%s', got '%s'",
-                        printStorePath(i), info->narHash->to_string(Base32, true), current.first.to_string(Base32, true))
+                        printStorePath(i), info->narHash.to_string(Base32, true), current.first.to_string(Base32, true))
                     });
                     if (repair) repairPath(i); else errors = true;
                 } else {
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 807619d29..0649b4094 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -142,16 +142,8 @@ public:
     void addToStore(const ValidPathInfo & info, Source & source,
         RepairFlag repair, CheckSigsFlag checkSigs) override;
 
-    StorePath addToStore(const string & name, const Path & srcPath,
-        FileIngestionMethod method, HashType hashAlgo,
-        PathFilter & filter, RepairFlag repair) override;
-
-    /* Like addToStore(), but the contents of the path are contained
-       in `dump', which is either a NAR serialisation (if recursive ==
-       true) or simply the contents of a regular file (if recursive ==
-       false). */
     StorePath addToStoreFromDump(Source & dump, const string & name,
-        FileIngestionMethod method = FileIngestionMethod::Recursive, HashType hashAlgo = htSHA256, RepairFlag repair = NoRepair) override;
+        FileIngestionMethod method, HashType hashAlgo, RepairFlag repair) override;
 
     StorePath addTextToStore(const string & name, const string & s,
         const StorePathSet & references, RepairFlag repair) override;
diff --git a/src/libstore/machines.cc b/src/libstore/machines.cc
index f848582da..7db2556f4 100644
--- a/src/libstore/machines.cc
+++ b/src/libstore/machines.cc
@@ -1,6 +1,7 @@
 #include "machines.hh"
 #include "util.hh"
 #include "globals.hh"
+#include "store-api.hh"
 
 #include <algorithm>
 
@@ -48,6 +49,29 @@ bool Machine::mandatoryMet(const std::set<string> & features) const {
         });
 }
 
+ref<Store> Machine::openStore() const {
+    Store::Params storeParams;
+    if (hasPrefix(storeUri, "ssh://")) {
+        storeParams["max-connections"] = "1";
+        storeParams["log-fd"] = "4";
+        if (sshKey != "")
+            storeParams["ssh-key"] = sshKey;
+    }
+    {
+        auto & fs = storeParams["system-features"];
+        auto append = [&](auto feats) {
+            for (auto & f : feats) {
+                if (fs.size() > 0) fs += ' ';
+                fs += f;
+            }
+        };
+        append(supportedFeatures);
+        append(mandatoryFeatures);
+    }
+
+    return nix::openStore(storeUri, storeParams);
+}
+
 void parseMachines(const std::string & s, Machines & machines)
 {
     for (auto line : tokenizeString<std::vector<string>>(s, "\n;")) {
diff --git a/src/libstore/machines.hh b/src/libstore/machines.hh
index de92eb924..341d9bd97 100644
--- a/src/libstore/machines.hh
+++ b/src/libstore/machines.hh
@@ -4,6 +4,8 @@
 
 namespace nix {
 
+class Store;
+
 struct Machine {
 
     const string storeUri;
@@ -28,6 +30,8 @@ struct Machine {
         decltype(supportedFeatures) supportedFeatures,
         decltype(mandatoryFeatures) mandatoryFeatures,
         decltype(sshPublicHostKey) sshPublicHostKey);
+
+    ref<Store> openStore() const;
 };
 
 typedef std::vector<Machine> Machines;
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 7f1b62f26..f6aa570bb 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -4,6 +4,7 @@
 #include "local-store.hh"
 #include "store-api.hh"
 #include "thread-pool.hh"
+#include "topo-sort.hh"
 
 
 namespace nix {
@@ -112,7 +113,7 @@ std::optional<ContentAddress> getDerivationCA(const BasicDerivation & drv)
 {
     auto out = drv.outputs.find("out");
     if (out != drv.outputs.end()) {
-        if (auto v = std::get_if<DerivationOutputFixed>(&out->second.output))
+        if (auto v = std::get_if<DerivationOutputCAFixed>(&out->second.output))
             return v->hash;
     }
     return std::nullopt;
@@ -206,10 +207,10 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
             ParsedDerivation parsedDrv(StorePath(path.path), *drv);
 
             PathSet invalid;
-            for (auto & j : drv->outputs)
+            for (auto & j : drv->outputsAndPaths(*this))
                 if (wantOutput(j.first, path.outputs)
-                    && !isValidPath(j.second.path(*this, drv->name)))
-                    invalid.insert(printStorePath(j.second.path(*this, drv->name)));
+                    && !isValidPath(j.second.second))
+                    invalid.insert(printStorePath(j.second.second));
             if (invalid.empty()) return;
 
             if (settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
@@ -256,41 +257,21 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
 
 StorePaths Store::topoSortPaths(const StorePathSet & paths)
 {
-    StorePaths sorted;
-    StorePathSet visited, parents;
-
-    std::function<void(const StorePath & path, const StorePath * parent)> dfsVisit;
-
-    dfsVisit = [&](const StorePath & path, const StorePath * parent) {
-        if (parents.count(path))
-            throw BuildError("cycle detected in the references of '%s' from '%s'",
-                printStorePath(path), printStorePath(*parent));
-
-        if (!visited.insert(path).second) return;
-        parents.insert(path);
-
-        StorePathSet references;
-        try {
-            references = queryPathInfo(path)->references;
-        } catch (InvalidPath &) {
-        }
-
-        for (auto & i : references)
-            /* Don't traverse into paths that don't exist.  That can
-               happen due to substitutes for non-existent paths. */
-            if (i != path && paths.count(i))
-                dfsVisit(i, &path);
-
-        sorted.push_back(path);
-        parents.erase(path);
-    };
-
-    for (auto & i : paths)
-        dfsVisit(i, nullptr);
-
-    std::reverse(sorted.begin(), sorted.end());
-
-    return sorted;
+    return topoSort(paths,
+        {[&](const StorePath & path) {
+            StorePathSet references;
+            try {
+                references = queryPathInfo(path)->references;
+            } catch (InvalidPath &) {
+            }
+            return references;
+        }},
+        {[&](const StorePath & path, const StorePath & parent) {
+            return BuildError(
+                "cycle detected in the references of '%s' from '%s'",
+                printStorePath(path),
+                printStorePath(parent));
+        }});
 }
 
 
diff --git a/src/libstore/nar-info-disk-cache.cc b/src/libstore/nar-info-disk-cache.cc
index 9ddb9957f..8541cc51f 100644
--- a/src/libstore/nar-info-disk-cache.cc
+++ b/src/libstore/nar-info-disk-cache.cc
@@ -189,13 +189,14 @@ public:
                 return {oInvalid, 0};
 
             auto namePart = queryNAR.getStr(1);
-            auto narInfo = make_ref<NarInfo>(StorePath(hashPart + "-" + namePart));
+            auto narInfo = make_ref<NarInfo>(
+                StorePath(hashPart + "-" + namePart),
+                Hash::parseAnyPrefixed(queryNAR.getStr(6)));
             narInfo->url = queryNAR.getStr(2);
             narInfo->compression = queryNAR.getStr(3);
             if (!queryNAR.isNull(4))
-                narInfo->fileHash = Hash(queryNAR.getStr(4));
+                narInfo->fileHash = Hash::parseAnyPrefixed(queryNAR.getStr(4));
             narInfo->fileSize = queryNAR.getInt(5);
-            narInfo->narHash = Hash(queryNAR.getStr(6));
             narInfo->narSize = queryNAR.getInt(7);
             for (auto & r : tokenizeString<Strings>(queryNAR.getStr(8), " "))
                 narInfo->references.insert(StorePath(r));
@@ -232,7 +233,7 @@ public:
                     (narInfo ? narInfo->compression : "", narInfo != 0)
                     (narInfo && narInfo->fileHash ? narInfo->fileHash->to_string(Base32, true) : "", narInfo && narInfo->fileHash)
                     (narInfo ? narInfo->fileSize : 0, narInfo != 0 && narInfo->fileSize)
-                    (info->narHash->to_string(Base32, true))
+                    (info->narHash.to_string(Base32, true))
                     (info->narSize)
                     (concatStringsSep(" ", info->shortRefs()))
                     (info->deriver ? std::string(info->deriver->to_string()) : "", (bool) info->deriver)
diff --git a/src/libstore/nar-info.cc b/src/libstore/nar-info.cc
index ca471463c..3454f34bb 100644
--- a/src/libstore/nar-info.cc
+++ b/src/libstore/nar-info.cc
@@ -1,10 +1,11 @@
 #include "globals.hh"
 #include "nar-info.hh"
+#include "store-api.hh"
 
 namespace nix {
 
 NarInfo::NarInfo(const Store & store, const std::string & s, const std::string & whence)
-    : ValidPathInfo(StorePath(StorePath::dummy)) // FIXME: hack
+    : ValidPathInfo(StorePath(StorePath::dummy), Hash(Hash::dummy)) // FIXME: hack
 {
     auto corrupt = [&]() {
         return Error("NAR info file '%1%' is corrupt", whence);
@@ -12,13 +13,14 @@ NarInfo::NarInfo(const Store & store, const std::string & s, const std::string &
 
     auto parseHashField = [&](const string & s) {
         try {
-            return Hash(s);
+            return Hash::parseAnyPrefixed(s);
         } catch (BadHash &) {
             throw corrupt();
         }
     };
 
     bool havePath = false;
+    bool haveNarHash = false;
 
     size_t pos = 0;
     while (pos < s.size()) {
@@ -46,8 +48,10 @@ NarInfo::NarInfo(const Store & store, const std::string & s, const std::string &
         else if (name == "FileSize") {
             if (!string2Int(value, fileSize)) throw corrupt();
         }
-        else if (name == "NarHash")
+        else if (name == "NarHash") {
             narHash = parseHashField(value);
+            haveNarHash = true;
+        }
         else if (name == "NarSize") {
             if (!string2Int(value, narSize)) throw corrupt();
         }
@@ -76,7 +80,7 @@ NarInfo::NarInfo(const Store & store, const std::string & s, const std::string &
 
     if (compression == "") compression = "bzip2";
 
-    if (!havePath || url.empty() || narSize == 0 || !narHash) throw corrupt();
+    if (!havePath || !haveNarHash || url.empty() || narSize == 0) throw corrupt();
 }
 
 std::string NarInfo::to_string(const Store & store) const
@@ -89,8 +93,8 @@ std::string NarInfo::to_string(const Store & store) const
     assert(fileHash && fileHash->type == htSHA256);
     res += "FileHash: " + fileHash->to_string(Base32, true) + "\n";
     res += "FileSize: " + std::to_string(fileSize) + "\n";
-    assert(narHash && narHash->type == htSHA256);
-    res += "NarHash: " + narHash->to_string(Base32, true) + "\n";
+    assert(narHash.type == htSHA256);
+    res += "NarHash: " + narHash.to_string(Base32, true) + "\n";
     res += "NarSize: " + std::to_string(narSize) + "\n";
 
     res += "References: " + concatStringsSep(" ", shortRefs()) + "\n";
diff --git a/src/libstore/nar-info.hh b/src/libstore/nar-info.hh
index eff19f0ef..39ced76e5 100644
--- a/src/libstore/nar-info.hh
+++ b/src/libstore/nar-info.hh
@@ -2,10 +2,12 @@
 
 #include "types.hh"
 #include "hash.hh"
-#include "store-api.hh"
+#include "path-info.hh"
 
 namespace nix {
 
+class Store;
+
 struct NarInfo : ValidPathInfo
 {
     std::string url;
@@ -15,7 +17,7 @@ struct NarInfo : ValidPathInfo
     std::string system;
 
     NarInfo() = delete;
-    NarInfo(StorePath && path) : ValidPathInfo(std::move(path)) { }
+    NarInfo(StorePath && path, Hash narHash) : ValidPathInfo(std::move(path), narHash) { }
     NarInfo(const ValidPathInfo & info) : ValidPathInfo(info) { }
     NarInfo(const Store & store, const std::string & s, const std::string & whence);
 
diff --git a/src/libstore/parsed-derivations.cc b/src/libstore/parsed-derivations.cc
index c7797b730..e7b7202d4 100644
--- a/src/libstore/parsed-derivations.cc
+++ b/src/libstore/parsed-derivations.cc
@@ -94,7 +94,7 @@ StringSet ParsedDerivation::getRequiredSystemFeatures() const
     return res;
 }
 
-bool ParsedDerivation::canBuildLocally() const
+bool ParsedDerivation::canBuildLocally(Store & localStore) const
 {
     if (drv.platform != settings.thisSystem.get()
         && !settings.extraPlatforms.get().count(drv.platform)
@@ -102,14 +102,14 @@ bool ParsedDerivation::canBuildLocally() const
         return false;
 
     for (auto & feature : getRequiredSystemFeatures())
-        if (!settings.systemFeatures.get().count(feature)) return false;
+        if (!localStore.systemFeatures.get().count(feature)) return false;
 
     return true;
 }
 
-bool ParsedDerivation::willBuildLocally() const
+bool ParsedDerivation::willBuildLocally(Store & localStore) const
 {
-    return getBoolAttr("preferLocalBuild") && canBuildLocally();
+    return getBoolAttr("preferLocalBuild") && canBuildLocally(localStore);
 }
 
 bool ParsedDerivation::substitutesAllowed() const
@@ -117,9 +117,4 @@ bool ParsedDerivation::substitutesAllowed() const
     return getBoolAttr("allowSubstitutes", true);
 }
 
-bool ParsedDerivation::contentAddressed() const
-{
-    return getBoolAttr("__contentAddressed", false);
-}
-
 }
diff --git a/src/libstore/parsed-derivations.hh b/src/libstore/parsed-derivations.hh
index 0b8e8d031..3fa09f34f 100644
--- a/src/libstore/parsed-derivations.hh
+++ b/src/libstore/parsed-derivations.hh
@@ -29,13 +29,11 @@ public:
 
     StringSet getRequiredSystemFeatures() const;
 
-    bool canBuildLocally() const;
+    bool canBuildLocally(Store & localStore) const;
 
-    bool willBuildLocally() const;
+    bool willBuildLocally(Store & localStore) const;
 
     bool substitutesAllowed() const;
-
-    bool contentAddressed() const;
 };
 
 }
diff --git a/src/libstore/path-info.hh b/src/libstore/path-info.hh
new file mode 100644
index 000000000..8ff5c466e
--- /dev/null
+++ b/src/libstore/path-info.hh
@@ -0,0 +1,112 @@
+#pragma once
+
+#include "crypto.hh"
+#include "path.hh"
+#include "hash.hh"
+#include "content-address.hh"
+
+#include <string>
+#include <optional>
+
+namespace nix {
+
+
+class Store;
+
+
+struct SubstitutablePathInfo
+{
+    std::optional<StorePath> deriver;
+    StorePathSet references;
+    uint64_t downloadSize; /* 0 = unknown or inapplicable */
+    uint64_t narSize; /* 0 = unknown */
+};
+
+typedef std::map<StorePath, SubstitutablePathInfo> SubstitutablePathInfos;
+
+
+struct ValidPathInfo
+{
+    StorePath path;
+    std::optional<StorePath> deriver;
+    // TODO document this
+    Hash narHash;
+    StorePathSet references;
+    time_t registrationTime = 0;
+    uint64_t narSize = 0; // 0 = unknown
+    uint64_t id; // internal use only
+
+    /* Whether the path is ultimately trusted, that is, it's a
+       derivation output that was built locally. */
+    bool ultimate = false;
+
+    StringSet sigs; // note: not necessarily verified
+
+    /* If non-empty, an assertion that the path is content-addressed,
+       i.e., that the store path is computed from a cryptographic hash
+       of the contents of the path, plus some other bits of data like
+       the "name" part of the path. Such a path doesn't need
+       signatures, since we don't have to trust anybody's claim that
+       the path is the output of a particular derivation. (In the
+       extensional store model, we have to trust that the *contents*
+       of an output path of a derivation were actually produced by
+       that derivation. In the intensional model, we have to trust
+       that a particular output path was produced by a derivation; the
+       path then implies the contents.)
+
+       Ideally, the content-addressability assertion would just be a Boolean,
+       and the store path would be computed from the name component, ‘narHash’
+       and ‘references’. However, we support many types of content addresses.
+    */
+    std::optional<ContentAddress> ca;
+
+    bool operator == (const ValidPathInfo & i) const
+    {
+        return
+            path == i.path
+            && narHash == i.narHash
+            && references == i.references;
+    }
+
+    /* Return a fingerprint of the store path to be used in binary
+       cache signatures. It contains the store path, the base-32
+       SHA-256 hash of the NAR serialisation of the path, the size of
+       the NAR, and the sorted references. The size field is strictly
+       speaking superfluous, but might prevent endless/excessive data
+       attacks. */
+    std::string fingerprint(const Store & store) const;
+
+    void sign(const Store & store, const SecretKey & secretKey);
+
+    /* Return true iff the path is verifiably content-addressed. */
+    bool isContentAddressed(const Store & store) const;
+
+    /* Functions to view references + hasSelfReference as one set, mainly for
+       compatibility's sake. */
+    StorePathSet referencesPossiblyToSelf() const;
+    void insertReferencePossiblyToSelf(StorePath && ref);
+    void setReferencesPossiblyToSelf(StorePathSet && refs);
+
+    static const size_t maxSigs = std::numeric_limits<size_t>::max();
+
+    /* Return the number of signatures on this .narinfo that were
+       produced by one of the specified keys, or maxSigs if the path
+       is content-addressed. */
+    size_t checkSignatures(const Store & store, const PublicKeys & publicKeys) const;
+
+    /* Verify a single signature. */
+    bool checkSignature(const Store & store, const PublicKeys & publicKeys, const std::string & sig) const;
+
+    Strings shortRefs() const;
+
+    ValidPathInfo(const ValidPathInfo & other) = default;
+
+    ValidPathInfo(StorePath && path, Hash narHash) : path(std::move(path)), narHash(narHash) { };
+    ValidPathInfo(const StorePath & path, Hash narHash) : path(path), narHash(narHash) { };
+
+    virtual ~ValidPathInfo() { }
+};
+
+typedef list<ValidPathInfo> ValidPathInfos;
+
+}
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 0c65bcd29..8dcc1d710 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -419,10 +419,10 @@ void RemoteStore::queryPathInfoUncached(const StorePath & path,
                 bool valid; conn->from >> valid;
                 if (!valid) throw InvalidPath("path '%s' is not valid", printStorePath(path));
             }
-            info = std::make_shared<ValidPathInfo>(StorePath(path));
             auto deriver = readString(conn->from);
+            auto narHash = Hash::parseAny(readString(conn->from), htSHA256);
+            info = std::make_shared<ValidPathInfo>(path, narHash);
             if (deriver != "") info->deriver = parseStorePath(deriver);
-            info->narHash = Hash(readString(conn->from), htSHA256);
             info->references = readStorePaths<StorePathSet>(*this, conn->from);
             conn->from >> info->registrationTime >> info->narSize;
             if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 16) {
@@ -521,7 +521,7 @@ void RemoteStore::addToStore(const ValidPathInfo & info, Source & source,
         conn->to << wopAddToStoreNar
                  << printStorePath(info.path)
                  << (info.deriver ? printStorePath(*info.deriver) : "")
-                 << info.narHash->to_string(Base16, false);
+                 << info.narHash.to_string(Base16, false);
         writeStorePaths(*this, conn->to, info.references);
         conn->to << info.registrationTime << info.narSize
                  << info.ultimate << info.sigs << renderContentAddress(info.ca)
diff --git a/src/libstore/s3-binary-cache-store.cc b/src/libstore/s3-binary-cache-store.cc
index 67935f3ba..a0a446bd3 100644
--- a/src/libstore/s3-binary-cache-store.cc
+++ b/src/libstore/s3-binary-cache-store.cc
@@ -266,6 +266,10 @@ struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
         const std::string & mimeType,
         const std::string & contentEncoding)
     {
+        istream->seekg(0, istream->end);
+        auto size = istream->tellg();
+        istream->seekg(0, istream->beg);
+
         auto maxThreads = std::thread::hardware_concurrency();
 
         static std::shared_ptr<Aws::Utils::Threading::PooledThreadExecutor>
@@ -343,10 +347,11 @@ struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
             std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1)
                 .count();
 
-        printInfo("uploaded 's3://%s/%s' in %d ms",
-            bucketName, path, duration);
+        printInfo("uploaded 's3://%s/%s' (%d bytes) in %d ms",
+            bucketName, path, size, duration);
 
         stats.putTimeMs += duration;
+        stats.putBytes += std::max(size, (decltype(size)) 0);
         stats.put++;
     }
 
diff --git a/src/libstore/s3-binary-cache-store.hh b/src/libstore/s3-binary-cache-store.hh
index b2b75d498..4d43fe4d2 100644
--- a/src/libstore/s3-binary-cache-store.hh
+++ b/src/libstore/s3-binary-cache-store.hh
@@ -19,6 +19,7 @@ public:
     struct Stats
     {
         std::atomic<uint64_t> put{0};
+        std::atomic<uint64_t> putBytes{0};
         std::atomic<uint64_t> putTimeMs{0};
         std::atomic<uint64_t> get{0};
         std::atomic<uint64_t> getBytes{0};
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index 7b0dede49..676b83391 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -193,10 +193,6 @@ StorePath Store::makeFixedOutputPath(
     }
 }
 
-// FIXME Put this somewhere?
-template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
-template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
-
 StorePath Store::makeFixedOutputPathFromCA(std::string_view name, ContentAddress ca,
     const StorePathSet & references, bool hasSelfReference) const
 {
@@ -239,6 +235,20 @@ StorePath Store::computeStorePathForText(const string & name, const string & s,
 }
 
 
+StorePath Store::addToStore(const string & name, const Path & _srcPath,
+    FileIngestionMethod method, HashType hashAlgo, PathFilter & filter, RepairFlag repair)
+{
+    Path srcPath(absPath(_srcPath));
+    auto source = sinkToSource([&](Sink & sink) {
+        if (method == FileIngestionMethod::Recursive)
+            dumpPath(srcPath, sink, filter);
+        else
+            readFile(srcPath, sink);
+    });
+    return addToStoreFromDump(*source, name, method, hashAlgo, repair);
+}
+
+
 /*
 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
@@ -310,8 +320,10 @@ ValidPathInfo Store::addToStoreSlow(std::string_view name, const Path & srcPath,
     if (expectedCAHash && expectedCAHash != hash)
         throw Error("hash mismatch for '%s'", srcPath);
 
-    ValidPathInfo info(makeFixedOutputPath(method, hash, name));
-    info.narHash = narHash;
+    ValidPathInfo info {
+        makeFixedOutputPath(method, hash, name),
+        narHash,
+    };
     info.narSize = narSize;
     info.ca = FixedOutputHash { .method = method, .hash = hash };
 
@@ -555,7 +567,7 @@ string Store::makeValidityRegistration(const StorePathSet & paths,
         auto info = queryPathInfo(i);
 
         if (showHash) {
-            s += info->narHash->to_string(Base16, false) + "\n";
+            s += info->narHash.to_string(Base16, false) + "\n";
             s += (format("%1%\n") % info->narSize).str();
         }
 
@@ -587,7 +599,7 @@ void Store::pathInfoToJSON(JSONPlaceholder & jsonOut, const StorePathSet & store
             auto info = queryPathInfo(storePath);
 
             jsonPath
-                .attr("narHash", info->narHash->to_string(hashBase, true))
+                .attr("narHash", info->narHash.to_string(hashBase, true))
                 .attr("narSize", info->narSize);
 
             {
@@ -715,20 +727,6 @@ void copyStorePath(ref<Store> srcStore, ref<Store> dstStore,
         info = info2;
     }
 
-    if (!info->narHash) {
-        StringSink sink;
-        srcStore->narFromPath({storePath}, sink);
-        auto info2 = make_ref<ValidPathInfo>(*info);
-        info2->narHash = hashString(htSHA256, *sink.s);
-        if (!info->narSize) info2->narSize = sink.s->size();
-        if (info->ultimate) info2->ultimate = false;
-        info = info2;
-
-        StringSource source(*sink.s);
-        dstStore->addToStore(*info, source, repair, checkSigs);
-        return;
-    }
-
     if (info->ultimate) {
         auto info2 = make_ref<ValidPathInfo>(*info);
         info2->ultimate = false;
@@ -736,12 +734,12 @@ void copyStorePath(ref<Store> srcStore, ref<Store> dstStore,
     }
 
     auto source = sinkToSource([&](Sink & sink) {
-        LambdaSink wrapperSink([&](const unsigned char * data, size_t len) {
-            sink(data, len);
+        LambdaSink progressSink([&](const unsigned char * data, size_t len) {
             total += len;
             act.progress(total, info->narSize);
         });
-        srcStore->narFromPath(storePath, wrapperSink);
+        TeeSink tee { sink, progressSink };
+        srcStore->narFromPath(storePath, tee);
     }, [&]() {
            throw EndOfFile("NAR for '%s' fetched from '%s' is incomplete", srcStore->printStorePath(storePath), srcStore->getUri());
     });
@@ -853,19 +851,22 @@ void copyClosure(ref<Store> srcStore, ref<Store> dstStore,
 }
 
 
-std::optional<ValidPathInfo> decodeValidPathInfo(const Store & store, std::istream & str, bool hashGiven)
+std::optional<ValidPathInfo> decodeValidPathInfo(const Store & store, std::istream & str, std::optional<HashResult> hashGiven)
 {
     std::string path;
     getline(str, path);
     if (str.eof()) { return {}; }
-    ValidPathInfo info(store.parseStorePath(path));
-    if (hashGiven) {
+    if (!hashGiven) {
         string s;
         getline(str, s);
-        info.narHash = Hash(s, htSHA256);
+        auto narHash = Hash::parseAny(s, htSHA256);
         getline(str, s);
-        if (!string2Int(s, info.narSize)) throw Error("number expected");
+        uint64_t narSize;
+        if (!string2Int(s, narSize)) throw Error("number expected");
+        hashGiven = { narHash, narSize };
     }
+    ValidPathInfo info(store.parseStorePath(path), hashGiven->first);
+    info.narSize = hashGiven->second;
     std::string deriver;
     getline(str, deriver);
     if (deriver != "") info.deriver = store.parseStorePath(deriver);
@@ -900,12 +901,12 @@ string showPaths(const PathSet & paths)
 
 std::string ValidPathInfo::fingerprint(const Store & store) const
 {
-    if (narSize == 0 || !narHash)
-        throw Error("cannot calculate fingerprint of path '%s' because its size/hash is not known",
+    if (narSize == 0)
+        throw Error("cannot calculate fingerprint of path '%s' because its size is not known",
             store.printStorePath(path));
     return
         "1;" + store.printStorePath(path) + ";"
-        + narHash->to_string(Base32, true) + ";"
+        + narHash.to_string(Base32, true) + ";"
         + std::to_string(narSize) + ";"
         + concatStringsSep(",", store.printStorePathSet(references));
 }
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 49da19496..128682e7a 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -4,12 +4,12 @@
 #include "hash.hh"
 #include "content-address.hh"
 #include "serialise.hh"
-#include "crypto.hh"
 #include "lru-cache.hh"
 #include "sync.hh"
 #include "globals.hh"
 #include "config.hh"
 #include "derivations.hh"
+#include "path-info.hh"
 
 #include <atomic>
 #include <limits>
@@ -101,95 +101,6 @@ struct GCResults
 };
 
 
-struct SubstitutablePathInfo
-{
-    std::optional<StorePath> deriver;
-    StorePathSet references;
-    uint64_t downloadSize; /* 0 = unknown or inapplicable */
-    uint64_t narSize; /* 0 = unknown */
-};
-
-typedef std::map<StorePath, SubstitutablePathInfo> SubstitutablePathInfos;
-
-struct ValidPathInfo
-{
-    StorePath path;
-    std::optional<StorePath> deriver;
-    // TODO document this
-    std::optional<Hash> narHash;
-    StorePathSet references;
-    time_t registrationTime = 0;
-    uint64_t narSize = 0; // 0 = unknown
-    uint64_t id; // internal use only
-
-    /* Whether the path is ultimately trusted, that is, it's a
-       derivation output that was built locally. */
-    bool ultimate = false;
-
-    StringSet sigs; // note: not necessarily verified
-
-    /* If non-empty, an assertion that the path is content-addressed,
-       i.e., that the store path is computed from a cryptographic hash
-       of the contents of the path, plus some other bits of data like
-       the "name" part of the path. Such a path doesn't need
-       signatures, since we don't have to trust anybody's claim that
-       the path is the output of a particular derivation. (In the
-       extensional store model, we have to trust that the *contents*
-       of an output path of a derivation were actually produced by
-       that derivation. In the intensional model, we have to trust
-       that a particular output path was produced by a derivation; the
-       path then implies the contents.)
-
-       Ideally, the content-addressability assertion would just be a Boolean,
-       and the store path would be computed from the name component, ‘narHash’
-       and ‘references’. However, we support many types of content addresses.
-    */
-    std::optional<ContentAddress> ca;
-
-    bool operator == (const ValidPathInfo & i) const
-    {
-        return
-            path == i.path
-            && narHash == i.narHash
-            && references == i.references;
-    }
-
-    /* Return a fingerprint of the store path to be used in binary
-       cache signatures. It contains the store path, the base-32
-       SHA-256 hash of the NAR serialisation of the path, the size of
-       the NAR, and the sorted references. The size field is strictly
-       speaking superfluous, but might prevent endless/excessive data
-       attacks. */
-    std::string fingerprint(const Store & store) const;
-
-    void sign(const Store & store, const SecretKey & secretKey);
-
-    /* Return true iff the path is verifiably content-addressed. */
-    bool isContentAddressed(const Store & store) const;
-
-    static const size_t maxSigs = std::numeric_limits<size_t>::max();
-
-    /* Return the number of signatures on this .narinfo that were
-       produced by one of the specified keys, or maxSigs if the path
-       is content-addressed. */
-    size_t checkSignatures(const Store & store, const PublicKeys & publicKeys) const;
-
-    /* Verify a single signature. */
-    bool checkSignature(const Store & store, const PublicKeys & publicKeys, const std::string & sig) const;
-
-    Strings shortRefs() const;
-
-    ValidPathInfo(const ValidPathInfo & other) = default;
-
-    ValidPathInfo(StorePath && path) : path(std::move(path)) { };
-    ValidPathInfo(const StorePath & path) : path(path) { };
-
-    virtual ~ValidPathInfo() { }
-};
-
-typedef list<ValidPathInfo> ValidPathInfos;
-
-
 enum BuildMode { bmNormal, bmRepair, bmCheck };
 
 
@@ -252,6 +163,10 @@ public:
 
     Setting<bool> wantMassQuery{this, false, "want-mass-query", "whether this substituter can be queried efficiently for path validity"};
 
+    Setting<StringSet> systemFeatures{this, settings.systemFeatures,
+        "system-features",
+        "Optional features that the system this store builds on implements (like \"kvm\")."};
+
 protected:
 
     struct PathInfoCacheValue {
@@ -456,7 +371,7 @@ public:
        libutil/archive.hh). */
     virtual StorePath addToStore(const string & name, const Path & srcPath,
         FileIngestionMethod method = FileIngestionMethod::Recursive, HashType hashAlgo = htSHA256,
-        PathFilter & filter = defaultPathFilter, RepairFlag repair = NoRepair) = 0;
+        PathFilter & filter = defaultPathFilter, RepairFlag repair = NoRepair);
 
     /* Copy the contents of a path to the store and register the
        validity the resulting path, using a constant amount of
@@ -465,6 +380,10 @@ public:
         FileIngestionMethod method = FileIngestionMethod::Recursive, HashType hashAlgo = htSHA256,
         std::optional<Hash> expectedCAHash = {});
 
+    /* Like addToStore(), but the contents of the path are contained
+       in `dump', which is either a NAR serialisation (if recursive ==
+       true) or simply the contents of a regular file (if recursive ==
+       false). */
     // FIXME: remove?
     virtual StorePath addToStoreFromDump(Source & dump, const string & name,
         FileIngestionMethod method = FileIngestionMethod::Recursive, HashType hashAlgo = htSHA256, RepairFlag repair = NoRepair)
@@ -845,7 +764,7 @@ string showPaths(const PathSet & paths);
 std::optional<ValidPathInfo> decodeValidPathInfo(
     const Store & store,
     std::istream & str,
-    bool hashGiven = false);
+    std::optional<HashResult> hashGiven = std::nullopt);
 
 /* Split URI into protocol+hierarchy part and its parameter set. */
 std::pair<std::string, Store::Params> splitUriAndParams(const std::string & uri);
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index f76b13fb4..5eddaff56 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -6,7 +6,7 @@ namespace nix {
 #define WORKER_MAGIC_1 0x6e697863
 #define WORKER_MAGIC_2 0x6478696f
 
-#define PROTOCOL_VERSION 0x117
+#define PROTOCOL_VERSION 0x118
 #define GET_PROTOCOL_MAJOR(x) ((x) & 0xff00)
 #define GET_PROTOCOL_MINOR(x) ((x) & 0x00ff)