1342974 - Generate a Merkle Tree to summarize the realease

Status: RESOLVED FIXED

(Release Engineering :: Release Automation, defect)

Description

[Richard Barnes [:rbarnes]]

For binary transparency, we need a single hash value that represents a release and an efficient way to tie any given binary to that hash value.  A Merkle tree on top of the existing SHAXXXSUMS files provides these things.

Comment 1

[Richard Barnes [:rbarnes]]

Attachment: Bug 1342974 - Add code to generate a Merkle tree summary of a release

Review commit: https://reviewboard.mozilla.org/r/115796/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/115796/

Comment 2

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

This patch augments generate-checksums.py so that it also builds a Merkle tree on the checksums it finds.  It then writes a SHAXXXSUMMARY file containing (1) the tree head and (2) an inclusion proof for each file.

rail, catlee: Does this look like the right direction to be headed?  Review ready?

Comment 3

[Chris AtLee [:catlee]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

https://reviewboard.mozilla.org/r/115796/#review117184

Looks good overall! As mentioned below, I think this could benefit from being split out into its own file, and definitely could use some tests given that I don't think the code as written will actually run.

::: testing/mozharness/scripts/release/generate-checksums.py:18
(Diff revision 1)
>  from mozharness.base.vcs.vcsbase import VCSMixin
>  from mozharness.mozilla.checksums import parse_checksums_file
>  from mozharness.mozilla.signing import SigningMixin
>  from mozharness.mozilla.buildbot import BuildbotMixin
>  
> +class MerkleTree:

having this broken out into its own file, with some tests, would probably be clearer.

::: testing/mozharness/scripts/release/generate-checksums.py:34
(Diff revision 1)
> +        self.hash_fn = hash_fn
> +
> +        self.nodes = self.n * [None]
> +        for i in range(self.n):
> +            self.nodes[i] = self.n * [None]
> +            self.nodes[i][0] = self.leafHash(data[i])

this data structure is a little opaque. can you document what you are trying to do here? would a dict work better? or memoizing intermediate node calculations for the inclusion proof path generation?

::: testing/mozharness/scripts/release/generate-checksums.py:36
(Diff revision 1)
> +        self.nodes = self.n * [None]
> +        for i in range(self.n):
> +            self.nodes[i] = self.n * [None]
> +            self.nodes[i][0] = self.leafHash(data[i])
> +
> +    def round2(n):

this looks like it's intended to be a regular function (outside of a class), not an instance method.

::: testing/mozharness/scripts/release/generate-checksums.py:52
(Diff revision 1)
> +
> +    def node(self, start, end):
> +        if self.nodes[start][end-start-1] != None:
> +            return self.nodes[start][end-start-1]
> +
> +        k = round2(end - start)

this won't work unless called via self.round2, or if round2 is moved outside of the class

Comment 4

[Rail Aliiev [:rail]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

https://reviewboard.mozilla.org/r/115796/#review117176

::: testing/mozharness/scripts/release/generate-checksums.py:45
(Diff revision 1)
> +        return k >> 1
> +
> +    def leafHash(self, a):
> +        return self.hash_fn('\x00' + a).digest()
> +
> +    def pairHash(self, a, b):

I'd name the methods using the same approach, and rename this one to `pair_hash()` to be consistent with others.

::: testing/mozharness/scripts/release/generate-checksums.py:248
(Diff revision 1)
> +        if format_ == "sha256":
> +            return hashlib.sha256
> +        elif format_ == "sha384":
> +            return hashlib.sha384
> +        elif format_ == "sha512":
> +            return hashlib.sha512

You can probably "optimize" this as
```python
if format_ in ("sha256", "sha384", "sha512"):
    return getattr(hashlib, format_)
else:
    ...
```

but meh :)

::: testing/mozharness/scripts/release/generate-checksums.py:316
(Diff revision 1)
>                          self.checksums[f] = info
>                          break
>                  else:
>                      self.debug("Ignoring checksums for file: {}".format(f))
>  
> +    def compute_summary_info(self):

This action should be added to `all_actions`, so we can call the script with `--compute-summary-info`

::: testing/mozharness/scripts/release/generate-checksums.py:333
(Diff revision 1)
> +            head = tree.head().encode("hex")
> +            proofs = [tree.inclusion_proof(i).encode("hex") for i in range(len(files))]
> +
> +            summary = self._get_summary_filename(fmt)
> +            self.info("Creating summary file: {}".format(summary))
> +            with open(sums, "w+") as output_file:

You can use `self.write_to_file()` (see https://dxr.mozilla.org/mozilla-central/source/testing/mozharness/mozharness/base/script.py#902) instead. Don't ask me why the following function uses `with open` :), probably we ported the script from another repo.

Comment 5

[Rail Aliiev [:rail]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

In overall it looks good, just need to address some comments and test. Thank you!

Comment 6

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/115796/diff/1-2/

Comment 7

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/115796/diff/2-3/

Comment 8

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Updated version:

- Factors out Merkle tree computations to a separate file
- Adds unit tests for Merkle tree operations in testing/mozharness/tests
- Uses a more pythonic caching structure (I think?)
- names_with_underscores
- write_to_file

Comment 9

[Chris AtLee [:catlee]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

https://reviewboard.mozilla.org/r/115796/#review117570

Comment 10

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/115796/diff/3-4/

Comment 11

[Stephanie Ouillon [:arroway] (needinfo me)]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

https://reviewboard.mozilla.org/r/115796/#review118322

::: testing/mozharness/mozharness/mozilla/merkle.py:41
(Diff revision 4)
> +      - 8 octets of leaf_index = m
> +      - 2 octets of path length, followed by
> +      * 1 + N octets of NodeHash
> +    """
> +
> +    # Pre-generated 'log ID'.  Not used by Firefox; it is only needed becuase

"becuase" -> "because"

Comment 12

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/115796/diff/4-5/

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/dac6db07aabb
Add code to generate a Merkle tree summary of a release r=arroway,catlee

Comment 14

[Richard Barnes [:rbarnes]]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Approval Request Comment
[Feature/Bug causing the regression]: N/A
[User impact if declined]: Unnecessary delay; this code is not run for Nightly or Aurora, so there's no point to having it wait there for two cycles
[Is this code covered by automated tests?]: Yes; see tests included in patch
[Has the fix been verified in Nightly?]: N/A; this code is not run for Nightly or Aurora
[Needs manual test from QE? If yes, steps to reproduce]: No
[List of other uplifts needed for the feature/fix]: None
[Is the change risky?]: Low risk
[Why is the change risky/not risky?]: The only code this change affects is code for generating release metadata.  The worst possible impact is that it could delay shipping a beta release.
[String changes made/needed]: None

Comment 15

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/dac6db07aabb

Comment 16

[Liz Henry (:lizzard) (relman/hg->git project)]

Comment on attachment 8841638 [details]
Bug 1342974 - Add code to generate a Merkle tree summary of a release

Context: https://wiki.mozilla.org/Security/Binary_Transparency
This should land for the beta 2 build next Monday.

Comment 17

[(PTO June 19-July 7) Ryan VanderMeulen]

https://hg.mozilla.org/releases/mozilla-beta/rev/f4c59968a6ea

Comment 18

[Rail Aliiev [:rail]]

we need to add a line here: https://hg.mozilla.org/releases/mozilla-beta/file/f4c59968a6ea/testing/mozharness/scripts/release/generate-checksums.py#l294 and call _get_summary_filename() to upload the files.

Comment 19

[Rail Aliiev [:rail]]

Attachment: Bug 1342974 - Upload Merkle Tree summary a=release DONTBUILD

Review commit: https://reviewboard.mozilla.org/r/120602/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/120602/

Comment 20

[Jordan Lund (:jlund)]

Comment on attachment 8847686 [details]
Bug 1342974 - Upload Merkle Tree summary  a=release DONTBUILD

https://reviewboard.mozilla.org/r/120602/#review123110

::: testing/mozharness/scripts/release/generate-checksums.py:296
(Diff revision 1)
>          files = ['KEY']
>  
>          for fmt in self.config["formats"]:
>              files.append(self._get_sums_filename(fmt))
>              files.append("{}.asc".format(self._get_sums_filename(fmt)))
> +            files.append(self._get_summary_filename(fmt))

having _get_summary_filename and _get_sums_filename seems wrong. Should we rename method name?

Comment 21

[Rail Aliiev [:rail]]

Comment on attachment 8847686 [details]
Bug 1342974 - Upload Merkle Tree summary  a=release DONTBUILD

https://reviewboard.mozilla.org/r/120602/#review123886

::: testing/mozharness/scripts/release/generate-checksums.py:296
(Diff revision 1)
>          files = ['KEY']
>  
>          for fmt in self.config["formats"]:
>              files.append(self._get_sums_filename(fmt))
>              files.append("{}.asc".format(self._get_sums_filename(fmt)))
> +            files.append(self._get_summary_filename(fmt))

Can you elaborate on this? Do you find both names conflicting and confusing?

Comment 22

[Jordan Lund (:jlund)]

Comment on attachment 8847686 [details]
Bug 1342974 - Upload Merkle Tree summary  a=release DONTBUILD

https://reviewboard.mozilla.org/r/120602/#review123886

> Can you elaborate on this? Do you find both names conflicting and confusing?

sorry, should have been more explicit. Yes I initially found them conflicting. However, rereading, I suppose 'sums' vs 'summary' isn't so bad.

I won't push back if you think it's fine.

Comment 23

[Jordan Lund (:jlund)]

Comment on attachment 8847686 [details]
Bug 1342974 - Upload Merkle Tree summary  a=release DONTBUILD

https://reviewboard.mozilla.org/r/120602/#review124640

Comment 24

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/1deede261ebf
Upload Merkle Tree summary r=jlund a=release DONTBUILD

Comment 25

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/1deede261ebf

Comment 26

[Rail Aliiev [:rail]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/02747e813bf00e7d2d862f30129c26088463b7f1
https://hg.mozilla.org/releases/mozilla-beta/rev/44f9af6ad433e022479f2e32fb499036ee1440d5

Comment 27

[Firefox Bug Husbandry Bot]

Removing leave-open keyword from resolved bugs, per :sylvestre.