Hey,

So, I've finally got around to actually looking at what code changes
might be involved in changing how users of Guix substitutes trust which
substitutes to use, and which not to use. This follows on from some of
the build reproducibility metrics work that happened recently [1].

1: https://lists.gnu.org/archive/html/guix-devel/2020-06/msg00034.html

The current situation as I understand it is that as a user, you list
public keys in your ACL (access control list), and Guix will trust a
substitute from a particular cache if it can find a narinfo for that
hash with a valid signature, made with a public key listed in the
ACL. There's some useful complexity here, because you can end up
downloading substitutes from a cache you don't directly trust, but
because you trust a different cache that's generated the same substitute
(it built reproducibly).

As described above, build reproducibility is already making some useful
behaviour possible. However, there's no current way of trusting
substitutes based on the agreement of multiple substitute servers
(caches). Making that possible would allow users to reduce the risk in
using substitutes by supporting a more distributed approach to trust.

My feeling is that making some initial step forward in this area is
going to be tricky, care needs to be taken around the security and
backwards compatibility aspects. I've now got around to actually
thinking about potential ways to make parts of this happen though, and
even changed some code [2] (although I haven't actually tried to run it
yet).

2: https://git.cbaines.net/guix/log/?h=k-of-n-substitute-trust&qt=range&q=k-of-n-substitute-trust...master

As I understand, the format for the ACL is based around [3] and I was
excited to see as part of that specification is something I think might
overlap with what I describe wanting above. Specifically, the k-of-n
<subj-thresh> bit. I think this could work something like this in an
ACL:

(acl
 (entry
  (k-of-n
   2
   3
   (public-key
    (ecc
     (curve Ed25519)
     (q #5F5F4F321533D3A38F909785E682798933BA9BE257C97E5ABC07DD08F27B8DBF#)
     )
    )
   (public-key
    (ecc
     (curve Ed25519)
     (q #3AF2631C5E78F520CB1DC0D438D8D6F88EEF4B8E11097A62EE2DF390E946AED0#)
     )
    )
   (public-key
    (ecc
     (curve Ed25519)
     (q #1EEE5340C3AAD6E062A1395A88A86FC75982E8BC7DCBAE171858EEAAB14AAB77#)
     )
    )
  )
  (tag
   (guix import)
   )
  )
)

3: http://theworld.com/~cme/spki.txt

Using the above ACL, you'd trust a substitute for a path with a specific
hash if you can find 2 narinfos for that path and hash if they're signed
with keys in that entry. Multiple entries would still be supported, and
you wouldn't need to specify the k-of-n bit if you don't want to.

I'm not quite sure how expressive this is, or if there are some policies
that would be good to support that either can't be expressed, or can't
be expressed easily. There's probably other approaches, and how to
support trusting substitutes is an important part to consider.

Let me know if you have any thoughts or questions,

Thanks,

Chris