## 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.

```
import math
C = 1375
d = 30
maxConstraints = 2**27
flatOverhead = math.ceil(7.5e6/2200) # non-sha overhead
SHA = 45331
P = 16
Pd = math.log2(P)
for a in range(0, 15, 1):
C2 = P * math.ceil(C/P))
regularInclusionProofs = SHA*(d-a-Pd)*C2
partitionInclusionProofs = P * SHA*Pd
apexTrees = P * SHA*(2**a-12)
overhead = flatOverhead*C2 + 2**a*C2 # 2**a * C2 is the overhead of dynamic lookup
main = regularInclusionProofs + partitionInclusionProofs + apexTrees + overhead
partitions = main / maxConstraints
print(f"Apex {a} ({C2}) constraints: {main}, partitions: {partitions:.2f}")
```

```
Results:
Apex 0 (1376.0) constraints: 1629356575.0, partitions: 12.14
Apex 1 (1376.0) constraints: 1567707790.0, partitions: 11.68
Apex 2 (1376.0) constraints: 1506785676.0, partitions: 11.23
Apex 3 (1376.0) constraints: 1447316904.0, partitions: 10.78
Apex 4 (1376.0) constraints: 1390754816.0, partitions: 10.36
Apex 5 (1376.0) constraints: 1340006096.0, partitions: 9.98
Apex 6 (1376.0) constraints: 1300884112.0, partitions: 9.69
Apex 7 (1376.0) constraints: 1285015600.0, partitions: 9.57
Apex 8 (1376.0) constraints: 1315654032.0, partitions: 9.80
Apex 9 (1376.0) constraints: 1439306352.0, partitions: 10.72
Apex 10 (1376.0) constraints: 1748986448.0, partitions: 13.03
Apex 11 (1376.0) constraints: 2430722096.0, partitions: 18.11
Apex 12 (1376.0) constraints: 3856568848.0, partitions: 28.73
Apex 13 (1376.0) constraints: 6770637808.0, partitions: 50.45
Apex 14 (1376.0) constraints: 12661151184.0, partitions: 94.33
```

### 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.