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

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.

Apex Path Sharing considering partitions

Goal

Description

Comparisons