Paper 2026/1552

BORG: Extendable Distributed Vector Commitments from Reconfigurable Erasure Codes

Abstract

Updatable vector commitments let users store and authenticate values contained within an evolving data vector. Existing work on updatable vector commitments studies how clients can store only the values and authentication proofs relevant to them, and can refresh stale opening proofs, with the help of an online maintainer that keeps the current vector and proof state. This work studies the complementary problem: how to decentralize the maintainer, in order to distribute the cost and availability requirements. We formalize this problem as extendable distributed vector commitments (EDVC). A public control plane, such as consensus or a trusted party, determines batches of updates and extensions of stored vector. Maintainers accept and apply a batch only after validating it against the current authenticated state. The resulting state is stored across many maintainer nodes, each of which holds a publicly assigned coded data fragment and updates it non-interactively. A stale client can obtain the current state, and a fresh authenticated opening, from the current maintainers (without replaying the updates history). We construct the first EDVC protocol, called Borg, from two components: a sparse vector commitment, and a coded storage layer that can be updated by linear operations. This construction applies when all active positions lie within a known growing prefix of the vector. We then construct a coded storage layer with the operations needed for this setting, including single-position openings, aligned range openings, public updates, adding new nodes, repairing failed nodes, and moving storage responsibilities between nodes. This is then used to flexibly distribute the data alongside a sparse Merkle tree for authentication. Our construction is particularly simple when the maintained data is an append-only public log (e.g., a blockchain’s block archive, or certificate transparency logs). In this setting, distributed updates to the data and its authentication structure can be made just by broadcasting the new log entries, with no coordination across maintainer nodes. We empirically evaluate maintainers’ cost for various workflows, showing that nodes can process hundreds of thousands of updates per second. We also show that node addition, repair of lost local state, and changes to the proof-serving threshold can all be supported efficiently.