Module akd::proof_structs
source · Expand description
Note that the proofs AppendOnlyProof
, MembershipProof
and NonMembershipProof
are Merkle Patricia tree proofs,
while the proofs HistoryProof
and LookupProof
are AKD proofs.
Structs
Proof that no leaves were deleted from the initial epoch.
This is done using a list of SingleAppendOnly proofs, one proof
for each epoch between the initial epoch and final epochs which are
being audited.
This proof is an array of
UpdateProof
s
and proofs of non-membership of future entriesProof value at a single layer of the tree
Note that this is really a helper struct to
hold the sibling path for a Merkle tree proof.
When sending a sibling path, you need to know
which direction to hash a node (left or right)
since in a compressed tree, the label alone is not
enough to derive the path.
Thus, we include the direction at which to place the
ancestor of the node for which a proof is being generated.
The parent is the parent of the level in the tree at which you are.
See documentation for
MembershipProof
to see how this is used.Proof that a given label was at a particular state at the given epoch.
This means we need to show that the state and version we are claiming for this node must have been:
Merkle proof of membership of a
NodeLabel
with a particular hash value
in the tree at a given epoch.Merkle Patricia proof of non-membership for a
NodeLabel
in the tree
at a given epoch.Proof that no leaves were deleted from the initial epoch.
This means that unchanged_nodes should hash to the initial root hash
and the vec of inserted is the set of leaves inserted between these epochs.
If we built the tree using the nodes in inserted and the nodes in unchanged_nodes
as the leaves with the correct epoch of insertion,
it should result in the final root hash.
A vector of UpdateProofs are sent as the proof to a history query for a particular key.
For each version of the value associated with the key, the verifier must check that: