Skip to content

Proof Verification

Jump to bottom
Daniele Bianco edited this page Nov 9, 2025 · 5 revisions

In case of boot-transparency, a "proof" is a proof of public logging that is used in a very similar way to a detached signature applied to the target binary at building time.

By-design, the verification logic in boot-transparency library is only including an inclusion check.

Indeed, the consistency check against any previous checkpoint is not required at bootloader, nor updating tool, layer. This check is off-loaded to witnessing network that thanks to its continuous log monitoring activity, is guaranteeing, via the cosigning process, that:

  1. A certain leaf has been publicly seen in the log at some point in time.
  2. Every leaf appeared in tree maintaining consistency with the previous ancient version (i.e. append-only evolution of the log).

These two aspects together, allow relaxing the requirements for the proof verification and reduce the complexity of the proof-bundle. This represents an advantage especially in cases where the transparency proof is verified "off-line".

The transparency proof verification in the boot-transparency library is then summarized as follows:

  1. Compute checksum of the claim.
  2. Check the keyhashes for both the log and leaf, to ensure the correspondent log and submitter pubkeys are available.
  3. Check that the leaf signature (with checksum computed as above) is valid.
  4. Check that the log's tree head signature is valid.
  5. Verify all cosignatures for witnesses known to the verifier.
  6. Verify the inclusion proof is valid by computing the leaf hash from the checksum together with the keyhash and signature from the leaf line.

A very similar logic is illustrated in: Sigsum - verifying a proof

This verification logic, implies that the proof bundle must include:

  1. The signed tree head (i.e. tree size, root hash, log signature, witness co-signatures)
  2. The signed leaf correspondent to the booting bundle manifest (signed with the submitter's key)
  3. The inclusion proof, which is basically the leaf line: all the sibling hashes of nodes along the path - from the leaf at point 2. up to the tree head.

This simplified design does not require to save any previous checkpoint in the verifier, as this would be needed to autonomously verify consistency proof, and does not require to pass the entire log tree (i.e. all level-0 leaves) in the proof bundle.

Important

As said, the design of the proof verification mechanism is simplified by off-loading the consistency check to the witnessing network.

Without witnessing support, an additional consistency check would be required to complete the transparency proof. Then, two additional requirements would arise in cases where the entities performing the consistency check are off-line:

  • on the bootloader side, the last seen checkpoint must be saved.
  • on the submitter side, the proof bundle must be assembled including all the missing leaves.

This latter point is a consequence from the fact that any off-line bootloader cannot obtain the missing leaf hashes directly from the public log.

A similar approach that overcomes to the off-line limitations is adopted in the inclusion verification implementation in armory-drive.

Sigsum

Sigsum already specifies a format for both the witness policy and proofs of logging:

The boot-transparency library is supporting both these formats. When using Sigsum as transparency engine the following keys must be provided to boot-transparency in order to enable proof verification:

  • log's public keys
  • submitter's public keys
  • cosigner's public keys (i.e. some of the witnesses public keys)

Sigsum uses Ed25519 keys in SSH key-file format:

"ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIKwmwKhVrEUaZTlHjhoWA4jwJLOF8TY+/NpHAXAHbAHl"

Following Sigsum specifications, an inclusion proof should be aligned with the following plain ASCII format (this example already includes cosignature to support the witnesses quorum functionality):

version=2
log=KEYHASH
leaf=KEYHASH SIGNATURE

tree_size=NUMBER
root_hash=HASH
signature=SIGNATURE
cosignature=KEYHASH TIMESTAMP SIGNATURE
cosignature=...

leaf_index=NUMBER
node_hash=HASH
node_hash=...

To efficiently enable witnessing, the library exposes a witnessing policy import functionality supporting the Sigsum policy format:

log <key>
witness X1 <key>
witness X2 <key>
witness X3 <key>
group X-witnesses 2 X1 X2 X3

witness Y1 <key>
witness Y2 <key>
witness Y3 <key>
group Y-witnesses any Y1 Y2 Y3

group X-and-Y all X-witnesses Y-witnesses
quorum X-and-Y

Tessera

Witness policy configuration in Tessera is performed by instantiating a new WitnessGroup directly from the policy file that should follow the Sigsum policy format.

The witness group can verify if a given checkpoint satisfy the signing requirements for the given witness policy (see Satisfied function defined for the WitnessGroup).

The inclusion verification function in Tessera (i.e. proof.VerifyInclusion) requires the following inputs:

  • root hash and tree size
  • leaf hash and index
  • inclusion proof
// Simplified version of the Tessera inclusionProbe structure
type Probe struct {
        // Log origin is needed to probe the correct log where
        // the leaf has been logged to
        Origin string `json:"origin"`
        // Leaf index
        LeafIdx uint64 `json:"leafIdx"`
        // Tree size
        TreeSize uint64 `json:"treeSize"`
        // Root hash
        Root []byte `json:"root"`
        // the LeafHash is not present as it is computed hashing
        // the ProofBundle.Statement.
        // LeafHash []byte   `json:"leafHash"`
        // Log public key is needed to verify that the proof is
        // signed with a trusted log key
        LogPublicKey string `json:"log_public_key"`
}

When Tessera engine is selected, the verification logic implemented by boot-transparency can be summarized as follows:

  1. instantiate a new witness group from a given witness policy
  2. retrieve the checkpoint from the proof bundle, or by fetching the latest one from the public log
  3. verify that signatures appended to the checkpoint are satisfying the witness policy requirements
  4. retrieve the proof of inclusion from the proof bundle, or by fetching it from the public log given the root hash and tree size specified in the latest checkpoint
  5. verify the proof of inclusion.

To assemble the inclusion proof, when the transparency engine is configured in on-line mode, boot-transparency leverages on the following Tessera functions:

  1. FetchCheckpoint downloads the latest checkpoint for a given origin
  2. NewProofBuilder creates the new ProofBuilder object for a given checkpoint (i.e. tree size).
  3. the ProofBuilder.InclusionProof function is used to build the inclusion proof given the tree size passed in step 2. and the leaf index passed as input to the function. This function would return Proof [][]byte.

Note

The leaf index should be saved at the time of leaf submission to the log. A similar process is illustrated in tessera/integration/integration_test.go

Clone this wiki locally