[Openembedded-architecture] [openembedded-architecture] sstate equivalency

[Joshua Watt]

Hello all,

I've been looking into the sstate equivalency mechanism discussed
[previously][1], and decided that it is probably time to report what I
am proposing, so that more discussion can be had.

[1]: http://lists.openembedded.org/pipermail/openembedded-architecture/
2018-May/000745.html

Please make note of the **QUESTION** lines, as they indicate
(known) outstanding issues haven't sorted out yet.

Apologies for the length. You can also see this in all of its markdown
glory
[here](https://gist.github.com/JPEWdev/506b70157cdbb59454e445fe71a57c7e
)

# Hash Equivalency Server

This design proposes a design for a Hash Equivalence Server that can
be use to centralize the records of what task hashes can be considered
equivalent. The server implements a REST HTTP API based on JSON data
to report to bitbake clients what task hash can be considered
equivalent on request, and also allow selected clients to report new
known equivalent hashes.

The hash equivalency server identifies task hashes based on these main
attributes:

1. `taskhash`: *Task Hash* - This is the value `${BB_TASKHASH}` that
   bitbake calculates from the inputs to the hash
2. `method`: *Output Hash Method* - The string method used to
   calculate the output hash. These will be described in detail later.
3. `outhash`: *Output Hash*: The hash derived from the build outputs
   using the `method`

**QUESTION** Do we need the `method`? Presumably, a hash is a hash is
hash is unique, so the method is unnecessary since different hashing
methods will produce different hashes from the same input, but at the
same time we also *expect* different a `outhash` when the `method`
differs.

The server may track and report other additional information about the
task hashes, but the items described above are the minimum required.

Once bitbake has calculated the task hash and determined that it needs
to rerun a task, it can send a HTTP GET request to the Hash
Equivalency Server to ask if knows any equivalent tasks that can be
used in place of rebuilding. This GET request is formulated as:

    GET /v1/outhashes?taskhash=<TASKHASH>&method=<METHOD>

In this request, `<TASKHASH>` and `<METHOD>` are replaced by the
appropriate information about the task for which bitbake is making the
request.

**QUESTION** I think we only need to request equivalent hashes for
things that have to be rebuilt... is there any reason to request them
for all tasks regardless of if they need to be rebuilt or not?

**QUESTION** You could pretty easily get some useful statistics on how
many users are (re)building a given taskhash. I know that's a more
controversial topic that I would mostly like to avoid (for now), but
keep it in mind... In general I think having a hash equivalency server
opens up a lot of those kinds of possibilities.

The response from the GET request will return the HTTP 200 OK code,
and the result body will be a JSON object that describes the
equivalent hash. At a minimum, the object will provide the `outhash`
field, as this is required for bitbake to discover a matching sstate
object. In the event there are no equivalent hashes, an empty object
is returned. The following is an example of the returned JSON:

```json
{
    "outhash": "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"
}
```

**QUESTION** Is there any reason to return more than one equivalent
hash?

Once an output hash is discovered for a task, the sstate task will use
it in place of the `BB_TASKHASH` variable for the purpose of looking
up sstate objects.

# Writing new sstate objects

In the event that a bitbake executor cannot find an equivalent hash
(either because no output hashes were reported, or no such sstate
objects exist), it will end up performing the build, then needing to
write out a new sstate object. These new sstate objects will always be
written using the output hash in the file name (in place of the
current `BB_TASKHASH`). These output hashes are calculated using one
of the hash calculation methods described below.

**QUESTION** Is there any desire to be able to do a build later
without the hash equivalency server? I don't think it would be
terribly difficult to have the sstate cache create symbolic links to
the equivalent task hashes with the name of the original task hash so
that builders who are unaware of the equivalency server can still find
the sstate objects.

# Reporting New Equivalent Hashes

A bitbake executor can report newly discovered equivalent hashes to
the hash equivalency server also via a REST API. These hashes can be
reported at the time the sstate object is written, using a POST
request:

    POST /v1/taskhashes

The body of the request must contain an array of JSON object that
describes the equivalent hashes. At a minimum, each object must
contain the `taskhash`, `method`, and `outhash` fields. For example:

```json
[
    {
        "taskhash": "c7c51be323b56305e1e7e74f4011e810fd340908",
        "method": "basic",
        "outhash": "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"
    },
    {
        "taskhash": "e7a3049fa3a27861d4b54d29b2e3b781f0dbf304",
        "method": "basic",
        "outhash": "114aa9bac59642fa951a0fed8359930fc602679d"
    },
]
```

**QUESTION** What do we do if multiple different output hashes are
reported for the same taskhash? This is actually pretty useful
information, since it would indicate a non-reproducible build.

**QUESTION** You can go pretty crazy with reporting here....
Hopefully, the three required fields are anonymous enough that there
are no qualms with reporting them.  Anything beyond that would
obviously be enormously helpful from a data-mining and statistics
perspective. You wouldn't be able to keep that anonymous enough, so it
would *have* to be opt-in. Again, not the focus of this discussion,
but keep it in mind

## Hash reporting security

The use of a public hash equivalency server has the potential
introduce serious security flaws into consumers that choose to use it.
For example, it would be trivial for a malicious user to upload an
outhash for an unpatched version of software as being equivalent to
the patched version's taskhash. As such, it is important that the
identity for the source of all reported taskhash be confirmed before
they are submitted to the database. To confirm the identity of posted
task hashes, users who wish to supply hashes must first upload a
public RSA key to the server which is tied to a username. When the
user wishes to POST a hash, the HTTP body doesn't contain the raw
JSON, but instead contains a JSON Web Signature string (per
[RFC7515](https://tools.ietf.org/html/rfc7515)), signed with the users
private key. In order for the server to identify which user/key should
be used to verify the signature, the message should contain the "kid"
parameter in the unprotected header that is set to the username
corresponding to the signing key. Additionally, the request must also
include a numeric "nonce", field in the protected header. This nonce
value must be numerically larger than the last reported nonce by that
user, or the request will be rejected with an error. In this case,
bitbake will be made aware of the error and the last reported nonce
value so it can retry with a higher value.

The server will store the username associated with all reported hashes
to allow for easy revocation of hashes in the event of a private key
breech, or a request to clear out reported hashes from the user for
privacy reasons.

**QUESTION** Web technology isn't really my thing... is there a better
way?

# Hashing Methods

The hashing equivalency code needs to be provided with a hashing
algorithm to determine if two taskhashes are equivalent. The default
algorithm provided with the implementation will be named "basic" and
calculates a SHA1 using the algorithm found
[here](https://gist.github.com/JPEWdev/d5e8d339d6d33a505fee1fd049994262
)

**QUESTION** It is important to note what that algorithm does hash
(file path, mode, file type, contents), but also what it *doesn't*
hash (namely the owner/group and timestamps). I think this is what we
would like. Any suggestions?


Thanks,
Joshua Watt