Apex Path Sharing considering partitions

Goal

Optimizing cost of inclusion proofs across multiple partitions with segmented challenges.

Description

Assume number of partitions $P = 16 = 2^{Pd}$ and sub-apex height $A$ and CommD height of $D$

The challenges are generated such that the high $\log_2P = 4 = Pd$ bits are the same in given partition (ParitionID which is taken as public input).

The proof from the leaf of the CommD tree goes through a following path.

• Inclusion proof of length $D - A- Pd$ from the leaf of CommD tree to a leaf of full Merkle tree
• Merkle apex tree of height $A$ with root at a leaf of partition inclusion proof
• Partition inclusion proof from root of the apex of the Merkle tree to the CommD

The full challenge bits are following: $\text{ParitionID}^{[Pd]}, \text{ApexPath}^{[A]}, \text{InclusionPath}^{[D-A-Pd]}$

ParitionID is a public input, ApexPath and InclusionPath are based on challenge generation.

Number of challenges needs to be divisible only by the number of partitions.

https://excalidraw.com/#json=4896727920279552,zRbZAvUJ-lDLuCwd_4-YBg

Comparisons

Apex Path Sharing gives us about ~9.5 partition worth of constraints, naive-Apex 11 and naive inclusion 17 partitions.

The drawback of doing Apex Path Sharing is the requirement of doing 16 partitions which may necessitate aggregation.