Compression of proofs of seal's non-inclusion into consecutive headers

[Frommi]

Proving validity of closing a seal includes proving non-inclusion of it's closing in all previous headers after it's open. It should be possible to reduce the amount of proofs by a constant $K$ multiplier if a single proof of non-inclusion can be created for $K$ consecutive headers.

To achieve that, a new Merkle tree big-PMT is defined that holds in it's leaves pairs of (unique_id, header_index) for each unique_id included in the headers from $t - K + 1$ to $t$ for header $t$ where the header_index is an index of the header including that unique_id. (if for some reason a single unique_id is used multiple times, the smallest header_index is used). Big-PMT's root and height should also be included in the header.

Big-PMT can be used to prove non-inclusion of the seal in the intersection of it's history and big-PMT's headers. A proof of non-inclusion for a seal for all of it's history thus can be proved with any number of big-PMTs (and regular PMTs) that exhaustively cover lifetime of the seal, but may overlap with each other or extend before or after seal's lifetime. A proof of inclusion (unique_id, header_index) in the big-PMT actually gives the proof of non-inclusion in [t - K + 1; header_index - 1] allowing us to use big-PMT that ends after a seal's lifetime for non-inclusion proofs.

That big-PMT is quite big indeed and there is one for each header, but there is no need to store full tree explicitly in memory even by miners producing it, but all peers are still required to keep at least all $K$ regular PMTs and an ordered set of (unique_id, header_index) pairs. When a miner creates a new header and it's PMT it should not discard and publish top $H - log(K)$ layers of the big-PMT which all the peers also keep (where $H$ is the height of the full big-PMT). That amount of layers is chosen such that this top part is no larger than biggest regular PMT that it includes so the data transferred over-the-wire is not impacted too much.

When peers receive a header and corresponding PMT and the top part of the big-PMT, the PMT is verified to have the same root as in the header and this also should be done for the big-PMT. To check the big-PMT, first, its checked that the top part is correct assuming valid leaves and then all the leaves are checked. A leaf in that top part of big-PMT is a root in a small subtree. A peer needs to find all (unique_id, header_index) pairs included into that subtree. To make it efficient, we can modify example formula for the slot from the paper (slot_id = unique_id % 2^h) to slot_id = unique_id >> (256 - h) for 256-bit ids integer type. This formula preserves the order of (unique_id, header_index) pairs for any h allowing for a quick retrieval of all the pairs that are included into the subtree of big-PMT. The subtree is recreated and checked against the leaf of the top part of big-PMT after which it can be discarded again.

To generate a proof for big-PMT, the subtree into which the seal would land is recreated the same way as during checking and with the path from the stored top part of that big-PMT it gives us full proof. To efficiently find all elements of that subtree for some old big-PMT if more than $K$ PMTs and big-PMT tops are stored with minimal memory overhead we can use a forest of treaps as our ordered set storing the (unique_id, header_index) pairs. A treap for each header. Whenever we need to find the elements in a subtree of some big-PMT we merge all treaps corresponding to headers represented in that big-PMT for $O(K \times log(N))$, find all the elements with two bin searches and split it all back up for the same time complexity as merge. Fix is in the next comment.

If a big-PMT tree is constructed faultily the proof of that is very short: either a reference to the wrong value of a node in the top part of the tree or just the wrongly constructed subtree. This proof of faulty big-PMT can also be checked quickly be other peers making rejecting a header with faulty big-PMT root value relatively smooth.

This proposal has following trade-offs it makes:

• Miner and peer compute time to construct/check PMTs is multiplied by $K$.
• Peers have to store at least the last $K$ PMTs to fully check header validity instead of one. This is not too bad as even though PMTs are ephemeral, they are not expected to be immediately discarded for longer availability.

But the benefit is compression of the proofs needed to be stored by users and uploaded on ownership transfer. $T$ consecutive non-use headers would require just $\lceil \frac{T}{K} \rceil$ proofs.

As for the zero-knowledge proofs, my uneducated guess is that it would significantly speed up history compression, just from reducing the size of proofs to compress while preserving the structure of the proofs (big-PMT proofs are the same as PMT proofs, just a bit longer).

[Frommi]

Forest of treaps won't work, because splitting them back up needs to be done by header_index, not unique_id. Here is other solution, we need to store:

1. A sorted list for each header_index to generate proofs.
2. A regular ordered set containing pairs for the last $K$ headers to check validity of the last big-PMT.

• To generate a proof of some maybe old big-PMT just do $K$ bin searches to find first and last unique_id that will go into the subtree of the big-PMT. Complexity: $O(K log(N))$, good enough.
• To check the validity of the new big-PMT, we update the ordered set by removing all unique_ids from the header that is now $K + 1$ old and insert all new ones from the new header, complexity $O(N Log(N))$. We will then go through the set, so the check will involve $O(NK)$ more time. $K$ is comparable or larger than $log(N)$, so this is good enough. It is important to do that operation quickly, because the check itself can be done on a consumer-grade GPU while this ordered set manipulation probably can't be.

[Frommi]

I think I figured out how to remove the trade-off of increasing compute $K$ times:

The header $t$ now stores the root of a big-PMT for headers $[t - 2K + 1; t - K]$ and only every $K$-th header has it. The whole timeline is covered by big-PMTs of the size $K$ without overlap, but with a lag. We construct and include big-PMTs of 2 sizes: some $K$ and $\sqrt K$.

This means that each peer has $K$ header's time to calculate the root of the big-PMT the size of $O(NK)$ and $O(\sqrt K)$ time for the $O(N\sqrt K)$ one. This is the same compute speed requirement as checking a regular PMT, so it is just 3 times more computation compared to only checking regular PMTs.

When compressing proofs of non-inclusion, a user would use $K$-sized big-PMTs for the part of lifetime that is at least $K$ old, $\sqrt K$-sized for at least $K - 1$ old and at most $\sqrt K - 1$ proofs from regular PMTs. Whenever enough time passes the current owner of the seal can replace smaller proofs with a proof from a larger big-PMT even if the ownership changed. This is because of the proof of first inclusion being proof of non-inclusion until that header. This means that the compression for consecutive non-inclusion in $T$ headers will be $\lceil \frac{T}{K} \rceil + 2\sqrt K$ proofs for currently open seals and $\lceil \frac{T}{K} \rceil + 1$ for seals that closed at least $K$ headers in the past.