Operation | Hyperproofs cost | Verkle trees cost (KZG, arity = B) | Our cost |
---|---|---|---|

Commit | n πΎ1 | ~ n πΎ1 | |

Compute all proofs | n log(n) πΎ1 | ~n lgB | |

Update digest | 1 πΎ1 | πΎ1 | |

Update all proofs (βstateβ) | log n πΎ1 | πΎ1 | |

Verify 1 proof | log n β | β | |

Aggregate m proofs | m log n (πΎ1+πΎ2+β) | ||

Verify aggr. of m proofs | m log n (πΎ2+πΎT+β) | no aggregation | |

Size of one proof | log n πΎ1 | +1 ) πΎ1 | |

Size of aggregated proof | log( m log n) πΎT | no aggregation | |

Group requirements | |||

Aggregation | via IPA (costly) | no aggregation | |

Updates | Yes | No updates | |

Maintainability (update all) | Yes | Yes | |

Compute/Update a fraction β of the tree | |||

Total # of proofs in Verkle Trees | NA | πΎ1 | |

Notes | NA | d is depth of VT; B is branching factor. It holds that , i.e., |

$\log_B(n)$

$\log_B(n)$

$\log_B(n)$

$(\log_B(n)$

$O(\alpha)$

$O(n \log B)$

$B^d + B^{d-1} + ... + B$

$n = B^d$

$d = \log_B(n)$