We present Charlotte, a framework for composable, Authenticated Distributed Data Structures (ADDSs). Charlotte data is stored in blocks that reference each other by hash. Together, all Charlotte blocks form a directed acyclic graph, the blockweb; all observers and applications use subgraphs of the blockweb. Unlike in prior systems, Charlotte data structures are composable: applications and data structures can operate fully independently when possible, but can also share blocks when desired. To support this composability, we define a language-independent format for Charlotte blocks and a network API for Charlotte servers.
ADDSs guarantee that data is immutable and self-authenticating: data referenced will be unchanged when it is retrieved. Charlotte extends traditional ADDS guarantees by allowing applications to plug in their own mechanisms for ensuring availability and integrity of data structures. Unlike most traditional distributed systems, including blockchains, Charlotte supports heterogeneous trust: different observers may have their own beliefs about who might fail, and how. Despite heterogeneity of trust, Charlotte presents each observer with a consistent, available view of data.
We demonstrate the flexibility of Charlotte by implementing a variety of integrity mechanisms, including Consensus and Proof-of-Work. We study the power of disentangling availability and integrity mechanisms by building a variety of applications. The results from these example applications suggest that future ADDS developers can use Charlotte to build flexible, fast, composable applications with strong guarantees.