The following script estimates the cost of FCMPs under various considerations (extending the program size to reduce the amount of commitments needed, various input counts). It also provides reference via estimating the cost of Bulletproofs+ (currently used as a range proof for the outputs).
These are not guaranteed to be 100% accurate yet should only have minor discrepancies from the actual proof sizes.
import math
print("-- FCMPs --")
for extraneous_compute in range(1, 8 + 1):
if pow(2, math.ceil(math.log2(extraneous_compute))) != extraneous_compute:
continue
for i in range(1, 16 + 1):
target_layers = 8
proof_1_target_layers = math.floor(target_layers / 2) + (target_layers % 2)
proof_2_target_layers = math.floor(target_layers / 2)
proof_1_gates_for_target_layers = extraneous_compute * 256
proof_2_gates_for_target_layers = extraneous_compute * 128
proof_commitments = 3
proof_1_ip_commitments = 2 * math.ceil(math.log2(i * proof_1_gates_for_target_layers))
proof_2_ip_commitments = 2 * math.ceil(math.log2(i * proof_2_gates_for_target_layers))
proof_1_branches = i * proof_1_target_layers
# The root for 8 layers is on the second proof, and it's shared for all inputs
# Accordingly, it's only committed to once
proof_2_branches = (i * (proof_2_target_layers - 1)) + 1
claimed_point_variables = 2 * 256
divisor_variables = 256
# Proof 1 has 4 claimed points, 1 append divisor, and (proof_1_target_layers - 1) claimed points
proof_1_variables_committed_to_per_input_for_target_layers = (4 * claimed_point_variables) + divisor_variables + ((proof_1_target_layers - 1) * claimed_point_variables)
# Proof 2 has proof_2_target_layers claimed points
proof_2_variables_committed_to_per_input_for_target_layers = proof_2_target_layers * claimed_point_variables
circuit_1_width = pow(2, math.ceil(math.log2(i * proof_1_gates_for_target_layers)))
circuit_2_width = pow(2, math.ceil(math.log2(i * proof_2_gates_for_target_layers)))
proof_1_variable_commitments = math.ceil((i * proof_1_variables_committed_to_per_input_for_target_layers) / circuit_1_width)
proof_2_variable_commitments = math.ceil((i * proof_2_variables_committed_to_per_input_for_target_layers) / circuit_2_width)
proof_1_vector_commitments = proof_1_branches + proof_1_variable_commitments
proof_2_vector_commitments = proof_2_branches + proof_2_variable_commitments
# n'
n__1 = 2 * (math.floor(proof_1_vector_commitments / 2) + 1)
n__2 = 2 * (math.floor(proof_2_vector_commitments / 2) + 1)
# i == n' isn't sent
proof_1_t_commitments = (2 * (n__1 + 1)) - 1
proof_2_t_commitments = (2 * (n__2 + 1)) - 1
all_proof_commitments = proof_commitments + proof_1_t_commitments + proof_1_ip_commitments + proof_1_vector_commitments + proof_commitments + proof_2_t_commitments + proof_2_ip_commitments + proof_2_vector_commitments
all_proof_scalars = 2 * 5
full_proof_size = (all_proof_commitments + all_proof_scalars) * 32
print(
"Compute Factor:", extraneous_compute,
", Inputs:", i,
", Proof 1 Base Cost:", circuit_1_width,
", Proof 2 Base Cost:", circuit_2_width,
", Commitments:", proof_commitments + proof_1_t_commitments + proof_1_ip_commitments + proof_1_vector_commitments + proof_commitments + proof_2_t_commitments + proof_2_ip_commitments + proof_2_vector_commitments,
"(p1vcs:", proof_1_variable_commitments, ", p2vcs:", proof_2_variable_commitments, ")",
", Size:", full_proof_size
)
print()
print("-- BP+ Range --")
for i in range(1, 16 + 1):
proof_commitments = 3
ip_commitments = 2 * math.ceil(math.log2(64 * i))
amount_commitments = i
commitments = proof_commitments + ip_commitments + amount_commitments
scalars = 3
full_proof_size = (commitments + scalars) * 32
print("Outputs:", i, ", Base Cost:", 64 * i, ", Commitments:", commitments, ", Size:", full_proof_size)The output is as follows.
-- FCMPs --
Compute Factor: 1 , Inputs: 1 , Proof 1 Base Cost: 256 , Proof 2 Base Cost: 128 , Commitments: 161 (p1vcs: 15 , p2vcs: 16 ) , Size: 5472
Compute Factor: 1 , Inputs: 2 , Proof 1 Base Cost: 512 , Proof 2 Base Cost: 256 , Commitments: 184 (p1vcs: 15 , p2vcs: 16 ) , Size: 6208
Compute Factor: 1 , Inputs: 3 , Proof 1 Base Cost: 1024 , Proof 2 Base Cost: 512 , Commitments: 192 (p1vcs: 12 , p2vcs: 12 ) , Size: 6464
Compute Factor: 1 , Inputs: 4 , Proof 1 Base Cost: 1024 , Proof 2 Base Cost: 512 , Commitments: 230 (p1vcs: 15 , p2vcs: 16 ) , Size: 7680
Compute Factor: 1 , Inputs: 5 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 226 (p1vcs: 10 , p2vcs: 10 ) , Size: 7552
Compute Factor: 1 , Inputs: 6 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 257 (p1vcs: 12 , p2vcs: 12 ) , Size: 8544
Compute Factor: 1 , Inputs: 7 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 292 (p1vcs: 14 , p2vcs: 14 ) , Size: 9664
Compute Factor: 1 , Inputs: 8 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 318 (p1vcs: 15 , p2vcs: 16 ) , Size: 10496
Compute Factor: 1 , Inputs: 9 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 304 (p1vcs: 9 , p2vcs: 9 ) , Size: 10048
Compute Factor: 1 , Inputs: 10 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 333 (p1vcs: 10 , p2vcs: 10 ) , Size: 10976
Compute Factor: 1 , Inputs: 11 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 358 (p1vcs: 11 , p2vcs: 11 ) , Size: 11776
Compute Factor: 1 , Inputs: 12 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 387 (p1vcs: 12 , p2vcs: 12 ) , Size: 12704
Compute Factor: 1 , Inputs: 13 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 412 (p1vcs: 13 , p2vcs: 13 ) , Size: 13504
Compute Factor: 1 , Inputs: 14 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 441 (p1vcs: 14 , p2vcs: 14 ) , Size: 14432
Compute Factor: 1 , Inputs: 15 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 466 (p1vcs: 15 , p2vcs: 15 ) , Size: 15232
Compute Factor: 1 , Inputs: 16 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 490 (p1vcs: 15 , p2vcs: 16 ) , Size: 16000
Compute Factor: 2 , Inputs: 1 , Proof 1 Base Cost: 512 , Proof 2 Base Cost: 256 , Commitments: 122 (p1vcs: 8 , p2vcs: 8 ) , Size: 4224
Compute Factor: 2 , Inputs: 2 , Proof 1 Base Cost: 1024 , Proof 2 Base Cost: 512 , Commitments: 145 (p1vcs: 8 , p2vcs: 8 ) , Size: 4960
Compute Factor: 2 , Inputs: 3 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 160 (p1vcs: 6 , p2vcs: 6 ) , Size: 5440
Compute Factor: 2 , Inputs: 4 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 191 (p1vcs: 8 , p2vcs: 8 ) , Size: 6432
Compute Factor: 2 , Inputs: 5 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 196 (p1vcs: 5 , p2vcs: 5 ) , Size: 6592
Compute Factor: 2 , Inputs: 6 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 225 (p1vcs: 6 , p2vcs: 6 ) , Size: 7520
Compute Factor: 2 , Inputs: 7 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 250 (p1vcs: 7 , p2vcs: 7 ) , Size: 8320
Compute Factor: 2 , Inputs: 8 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 279 (p1vcs: 8 , p2vcs: 8 ) , Size: 9248
Compute Factor: 2 , Inputs: 9 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 284 (p1vcs: 5 , p2vcs: 5 ) , Size: 9408
Compute Factor: 2 , Inputs: 10 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 307 (p1vcs: 5 , p2vcs: 5 ) , Size: 10144
Compute Factor: 2 , Inputs: 11 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 336 (p1vcs: 6 , p2vcs: 6 ) , Size: 11072
Compute Factor: 2 , Inputs: 12 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 355 (p1vcs: 6 , p2vcs: 6 ) , Size: 11680
Compute Factor: 2 , Inputs: 13 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 380 (p1vcs: 7 , p2vcs: 7 ) , Size: 12480
Compute Factor: 2 , Inputs: 14 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 403 (p1vcs: 7 , p2vcs: 7 ) , Size: 13216
Compute Factor: 2 , Inputs: 15 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 432 (p1vcs: 8 , p2vcs: 8 ) , Size: 14144
Compute Factor: 2 , Inputs: 16 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 451 (p1vcs: 8 , p2vcs: 8 ) , Size: 14752
Compute Factor: 4 , Inputs: 1 , Proof 1 Base Cost: 1024 , Proof 2 Base Cost: 512 , Commitments: 102 (p1vcs: 4 , p2vcs: 4 ) , Size: 3584
Compute Factor: 4 , Inputs: 2 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 125 (p1vcs: 4 , p2vcs: 4 ) , Size: 4320
Compute Factor: 4 , Inputs: 3 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 142 (p1vcs: 3 , p2vcs: 3 ) , Size: 4864
Compute Factor: 4 , Inputs: 4 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 171 (p1vcs: 4 , p2vcs: 4 ) , Size: 5792
Compute Factor: 4 , Inputs: 5 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 188 (p1vcs: 3 , p2vcs: 3 ) , Size: 6336
Compute Factor: 4 , Inputs: 6 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 211 (p1vcs: 3 , p2vcs: 3 ) , Size: 7072
Compute Factor: 4 , Inputs: 7 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 240 (p1vcs: 4 , p2vcs: 4 ) , Size: 8000
Compute Factor: 4 , Inputs: 8 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 259 (p1vcs: 4 , p2vcs: 4 ) , Size: 8608
Compute Factor: 4 , Inputs: 9 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 276 (p1vcs: 3 , p2vcs: 3 ) , Size: 9152
Compute Factor: 4 , Inputs: 10 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 299 (p1vcs: 3 , p2vcs: 3 ) , Size: 9888
Compute Factor: 4 , Inputs: 11 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 318 (p1vcs: 3 , p2vcs: 3 ) , Size: 10496
Compute Factor: 4 , Inputs: 12 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 341 (p1vcs: 3 , p2vcs: 3 ) , Size: 11232
Compute Factor: 4 , Inputs: 13 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 370 (p1vcs: 4 , p2vcs: 4 ) , Size: 12160
Compute Factor: 4 , Inputs: 14 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 389 (p1vcs: 4 , p2vcs: 4 ) , Size: 12768
Compute Factor: 4 , Inputs: 15 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 412 (p1vcs: 4 , p2vcs: 4 ) , Size: 13504
Compute Factor: 4 , Inputs: 16 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 431 (p1vcs: 4 , p2vcs: 4 ) , Size: 14112
Compute Factor: 8 , Inputs: 1 , Proof 1 Base Cost: 2048 , Proof 2 Base Cost: 1024 , Commitments: 94 (p1vcs: 2 , p2vcs: 2 ) , Size: 3328
Compute Factor: 8 , Inputs: 2 , Proof 1 Base Cost: 4096 , Proof 2 Base Cost: 2048 , Commitments: 117 (p1vcs: 2 , p2vcs: 2 ) , Size: 4064
Compute Factor: 8 , Inputs: 3 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 144 (p1vcs: 2 , p2vcs: 2 ) , Size: 4928
Compute Factor: 8 , Inputs: 4 , Proof 1 Base Cost: 8192 , Proof 2 Base Cost: 4096 , Commitments: 163 (p1vcs: 2 , p2vcs: 2 ) , Size: 5536
Compute Factor: 8 , Inputs: 5 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 190 (p1vcs: 2 , p2vcs: 2 ) , Size: 6400
Compute Factor: 8 , Inputs: 6 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 209 (p1vcs: 2 , p2vcs: 2 ) , Size: 7008
Compute Factor: 8 , Inputs: 7 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 232 (p1vcs: 2 , p2vcs: 2 ) , Size: 7744
Compute Factor: 8 , Inputs: 8 , Proof 1 Base Cost: 16384 , Proof 2 Base Cost: 8192 , Commitments: 251 (p1vcs: 2 , p2vcs: 2 ) , Size: 8352
Compute Factor: 8 , Inputs: 9 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 278 (p1vcs: 2 , p2vcs: 2 ) , Size: 9216
Compute Factor: 8 , Inputs: 10 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 297 (p1vcs: 2 , p2vcs: 2 ) , Size: 9824
Compute Factor: 8 , Inputs: 11 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 320 (p1vcs: 2 , p2vcs: 2 ) , Size: 10560
Compute Factor: 8 , Inputs: 12 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 339 (p1vcs: 2 , p2vcs: 2 ) , Size: 11168
Compute Factor: 8 , Inputs: 13 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 362 (p1vcs: 2 , p2vcs: 2 ) , Size: 11904
Compute Factor: 8 , Inputs: 14 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 381 (p1vcs: 2 , p2vcs: 2 ) , Size: 12512
Compute Factor: 8 , Inputs: 15 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 404 (p1vcs: 2 , p2vcs: 2 ) , Size: 13248
Compute Factor: 8 , Inputs: 16 , Proof 1 Base Cost: 32768 , Proof 2 Base Cost: 16384 , Commitments: 423 (p1vcs: 2 , p2vcs: 2 ) , Size: 13856
-- BP+ Range --
Outputs: 1 , Base Cost: 64 , Commitments: 16 , Size: 608
Outputs: 2 , Base Cost: 128 , Commitments: 19 , Size: 704
Outputs: 3 , Base Cost: 192 , Commitments: 22 , Size: 800
Outputs: 4 , Base Cost: 256 , Commitments: 23 , Size: 832
Outputs: 5 , Base Cost: 320 , Commitments: 26 , Size: 928
Outputs: 6 , Base Cost: 384 , Commitments: 27 , Size: 960
Outputs: 7 , Base Cost: 448 , Commitments: 28 , Size: 992
Outputs: 8 , Base Cost: 512 , Commitments: 29 , Size: 1024
Outputs: 9 , Base Cost: 576 , Commitments: 32 , Size: 1120
Outputs: 10 , Base Cost: 640 , Commitments: 33 , Size: 1152
Outputs: 11 , Base Cost: 704 , Commitments: 34 , Size: 1184
Outputs: 12 , Base Cost: 768 , Commitments: 35 , Size: 1216
Outputs: 13 , Base Cost: 832 , Commitments: 36 , Size: 1248
Outputs: 14 , Base Cost: 896 , Commitments: 37 , Size: 1280
Outputs: 15 , Base Cost: 960 , Commitments: 38 , Size: 1312
Outputs: 16 , Base Cost: 1024 , Commitments: 39 , Size: 1344
The compute factor is a time/space tradeoff. The base cost is the cost paid for verifying a batch of
FCMPs (itself a pair of two proofs). The base cost paid for the entire batch is the base cost of the
singular proof with the most inputs (so if all proofs are for two inputs, except a single sixteen
input proof, the base cost is still 4096 + 2048). After the base cost is paid, each proof only
pays its amount of commitments (so a batch of two two-input proofs and one four-input proof pays
(1024 + 512) + (2 * 230) + 184). Higher compute factors do perform better when batch verifying.
While they pay a higher base cost, the cost per-proof decreases.
5472 exceeds the originally estimated ~2.5kB by a notable margin. The belief for this is an
under-estimation of the cost of each Pedersen Vector Commitment. While each PVC is only 32 bytes,
each grows the l/r polynomials, growing the t polynomial (a result of their inner-product) by
2 coefficients. Each coefficient in the t polynomial itself has a commitment transmitted. This
means each PVC actually takes 3 commitments, not 1.
p1vcs, p2vcs stands for the variable commitments. These are PVCs we use to commit to variables
(which don't require any structure for their commitments). The amount of variables increase with
each input, yet so does the amount of variables which can fit into a commitment. Accordingly, the
amount of commitments required to commit to all the variables never actually increases.
Commitments refers to any group element transmitted during the proof however, inclusive to the
variable commitments (which are PVCs), the blinded branches of the Merkle tree (which are PVCs), the
t polynomial commitments, and the Bulletproof's IP argument commitments. The t polynomial only
grows with PVCs, and the Bulletproof's IP argument commitments only grow 64 bytes per doubling of
the program size (2 inputs, 4 inputs, 8 inputs...).
Branches can't take advantage of how with more inputs, the commitment size grows, as branches need
to only contain the specific children present under the tree branch. They're mostly wasted space due
to this. The recent
Curve Forests
proposal solves this, only having one set of branches regardless of the amount of elements proved
for, by building n trees instead of just one. This increases the work a daemon must do and the
work a wallet must do (either locally building the tree or downloading n times as much tree
information). For a sufficiently low MAX_INPUTS, or with sufficiently high use of proofs with more
inputs, this is still more computationally efficient than verifying proofs under the Curve Trees
methodology. The cost of building the additional trees is less than the cost of verifying the more
inefficient proofs, so long as the additional trees are used.
Curve Forests also decreases the amount of scalar multiplications which need to be done from
(4 + 7) n to 4 n + 7. This would decrease the amount of variables we need to commitment to and
cause less variable commitments to be used.
Beyond the Curve Forests design, we can further review Generalized Bulletproofs. The original
proofs from Aaron Feickert (while at Cypher Stack) proposed doubling the amount of variables which
could fit into a single PVC, without additional cost. The design failed to consider certain
cross-products, and the final proofs doubled the amount of variables in a PVC while doubling the
cost per-PVC (though letting us use half as many PVCs). The plan is to restore the original
non-double-size PVCs (causing twice as many PVC though with half as many t commitments for them)
due to their working better in our specific use-case, yet someone who can resolve the
cross-products question (which Aaron didn't see a way to in the brief time they considered the
problem) would reduce our amount of PVCs without increasing our amount of t commitments (achieving
smaller proofs with a reduced MSM growth rate).
There was also a recent paper on extending Halo 2 to open PVCs (as necessary for the Curve {Trees, Forests} design and our scalar multiplication gadget). This was labeled as a Proof of Concept and I haven't fully sat down with it to understand how far away it is from being ready for production use, nor the literal performance which could be expected.
My immediate proposal/recommendation is set the compute factor to 4 (creating a ~3.6 kB proof with
~700 bytes growth per additional input). This will increase the base cost yet still perform well
when batch verifying (such as when syncing the blockchain). This does highlight the need for
optimized Helios/Selene arithmetic so that the 4x higher base cost is offset but ideally ~2x faster
underlying arithmetic. Long-term, I'd propose moving to Curve Forests in a follow up hard fork. This will create an amount of branches constant to tree depth and decrease the amount of variable commitments with more inputs. This means we should expect to pay not just for one tree now yet n trees in the future (whatever MAX_INPUTS is).