Trust Machines Tech Meeting, Jun ‘23
Byzantine Data Types
Bridging application programming and smart contracts
Santiago Bazerque
Application programming, computing & trust
Group chat app, behavioral rules:
Client-Server The server is trusted
- Only admins can delete other
people’s messages
- Only the author of a message can Wallet-Chain The chain is trusted
edit its content
- Only members can see the content
of private channels Fully distributed We trust nobody
- Etc.
Each node has a replica of state.
Small networks + gossip + BFT
sync protocol.
Small Networks + Gossip + BFT Sync
Group chat app, network topology example:
(Notice there are no mandatory network layers or data linearization here)
You, running the app on your laptop:
- A local replica of the data
- Peer discovery
- Connected to 4 peers:
Trust Machines - Running gossip about data
company chat group changes
- Running a BFT sync protocol
Need to check absolutely everything
about incoming data
Sunday soccer
league chat group
Byzantine Data Types
Creating a replicable data structure and designing a BFT sync protocol per app is… challenging 😱
💡Idea: create a library of basic, Securely replicable sets, maps,
composable data types that include a lists, arrays, references,
ready-made BFT sync protocol counters, structs, etc.
<data type, sync protocol> Byzantine Data Type
Hyper Hyper Space
An open source, non-for-profit framework for working with Byzantine Data Types
Written in Typescript, runs in browsers & node
Unified data representation: append-only immutable
Merkle-DAGs
Single gossip+sync protocol, flexible enough to be
used over many different types
Eventual consistency, inspired by CRDTs +
extensions: elementary, coordination-free types
Work in progress (!)
Application Architecture
Device (smartphone, laptop, server, etc.)
Application
(Type definitions, UI, etc.)
set-up Mesh Network
read, write
Store read, write Mesh Node gossip + sync
App works over a local (reactive) store:
Hyper Hyper Space // adding a message
let m = new Message(‘hello’);
Data model: HashedObject, MutableSet, [Link](santi);
MutableArray, MutableReference, etc.
Storage: Store, IdbBackend, SQLiteBackend, [Link](m);
etc. [Link]();
Sync: Mesh
// for the UI, also see react bind.
App-level type definitions: [Link]();
[Link](…);
class ChatGroup
extends HashedObject {
owner : Identity; Sync works at the store level:
moderators : MutableSet<Identity>; let chat = new ChatGroup(…);
members : MutableSet<Identity>; let peers =
new ContainerBasedSource([Link]);
messages : MutableSet<Message>;
… [Link](chat, peers);
Data Model
Internally, information is represented an append-only Merkle DAG of typed, immutable objects.
let kp = [Link](2048); Hash Type Value
let santi = #f361d… KeyPair { public: ‘--BEGIN…
new Identity({name: ‘Santi’}, kp);
#4a455… Identity { name: ‘Santi’, keypair: #f361d…
let message = new Message(‘Hello!’);
[Link](santi); #a6fd2… Message { text: ‘hi’, author: #4a455… }
[Link]()
save() automatically serializes & hashes
KeyPair #f361d…
objects, and replaces memory-based
references by the corresponding hashes. keypair Identity #4a55…
Message #a6fd
author
Mutability
Objects that support mutations are operational. Each time they change, they create a new
operation object.
class MutableSet<T> extends MutableObject {
_contents = new Set<T>();
add(elem: T) { // <- you call this method
let op = new AddOp(elem);
[Link](this);
[Link](op);
}
mutate(op: MutationOp) { // <- actual mutation, called from “add” and from sync
if (op instanceof AddOp) {
this._contents.add([Link]);
} else if (op instanceof DeleteOp) {
Mutability
Objects that support mutations are operational. Each time they change, they create a new
operation object, that’s appended to the DAG. These objects are partially ordered using a special
field, prevOps.
let s = new MutableSet(); Hash Type Value
[Link](s);
#66ad3… Mutable { seed: ‘a53af…’ }
Set
[Link](‘apple’); #bb8c3… AddOp { element: ‘apple’,
[Link](‘orange’); target: ref<#66ad3…,
prevOps: {} }
[Link](s);
#39d46… AddOp { element: ‘orange’,
target: ref<#66ad3…,
prevOps: {#bb8c3…} }
History DAGs
Each [Link] call is generating an operation object, that is saved to the store. Conceptually, they
form a history DAG:
AddOp
let s = new MutableSet(); orange
[Link](s);
AddOp
apple
[Link](‘apple’);
[Link](‘orange’);
MutableSet
[Link](s); Seed: a53af…
Op Commutativity (1)
If a second peer is modifying the set, history becomes non-linear. Notice how the DeleteOp
references the AddOps it’s removing, not the elements. This guarantees commutativity.
AddOp sync
grapes
let s = new MutableSet();
[Link](s); {}
AddOp DeleteOp
[Link](‘apple’); {‘apple’} orange
[Link](‘orange’); {‘apple’, ‘orange’}
[Link](s);
// sync runs {‘apple’, ‘bananas’} AddOp AddOp
apple bananas
[Link](‘grapes’);
[Link](s); {‘apple’, ‘bananas’,
’grapes’}
MutableSet
Seed: a53af…
Op Commutativity (2)
In this scenario, ‘apple’ was sync AddOp sync
added again by a different peer. grapes
After sync is done, there is no
ambiguity about whether ‘apple’ AddOp DeleteOp
is in the set or not. orange
This is equivalent to an OR-set
CRDT with tombstones (but AddOp AddOp AddOp
Byzantine fault tolerant!). apple apple bananas
Reference for combining CRDTs and Merke DAGs:
MutableSet
Seed: a53af…
[Link]
Reference for general BFT in CRDTs:
[Link]
Observation: Explicit deletes would not work
This doesn’t work! Is apple in sync AddOp sync
grapes
the set or not?
It depends on the order in which DeleteOp
we receive the operations. AddOp
orange apple
AddOp AddOp AddOp
That’s why DeleteOp uses a bananas
apple apple
reference to the AddOp(s) it is
invalidating. The ambiguity is
resolved by including some info
about the local state at the time MutableSet
Seed: a53af…
the DeleteOp is created.
Mutable Types Summary
- Shared state is modelled using special mutable types provided by the
library (can be extended with new ones).
- Mutable types work operationally: they are changed by creating partially
ordered operations, that are both applied locally and shipped over the
network via gossip+sync.
- The operations are only partially ordered, using local history. This limits
what types can be modelled, since we still need eventual consistency
(operations must commute).
- CRDTs + Merkle-ized operational history are safe to use (can be
BFT-sync’d).
Causal Composition (1)
Only admins can delete other people’s
App-level type definitions: messages
class ChatGroup
extends HashedObject {
owner : Identity; Alice, a moderator, Alice deletes a message
is removed from the from Bob, using her
moderators : MutableSet<Identity>;
members : MutableSet<Identity>; moderators set moderator rights.
messages : MutableSet<Message>;
…
Race condition 😭
Causal Composition (2)
We need to make inter-object causal dependencies explicit. HHS has a family of causal collections for that:
CausalSet, CausalArray, CausalReference, etc.
These causal collections have an extra operation, that attests something about the current state:
class CausalSet<T> extends MutableObject {
add(elem: T) { …
delete(elem: T) { …
attestMembershipForOp(elem: T, op: MutationOp) { …
Attestation ops exist in the history DAG of the set. When a DeleteOp is added, the system will automatically
invalidate any attestations that are not its predecessors according to the prevOps partial order using an
special Undo Op.
Causal Composition (3)
Now using moderator rights requires an attestation. The attestation creates an explicit causal link
between the operation deleting the message, and the one that added Alice to the moderator set:
class ChatGroup extends MutableObject {
moderators : CausalSet<Identity>;
messages : CausalSet<Message>;
moderate(m: Message, mod: Identity) {
// simplified for clarity
let op = new DeleteOp(m);
[Link](mod, op);
[Link](op);
}
Causal Composition: No race
Now using moderator rights requires an attestation. The attestation creates an explicit causal link
between the operation deleting the message, and the one that added Alice to the moderator set:
partial ordering sync
DeleteOp
op target
AttestOp DeleteOp
AddOp AddOp
alice m by Bob
Moderators Messages
Seed: 43c3f… Seed: ad113…
Causal Composition: Race & cascaded undos
Here Alice’s deletion from the moderator set and the attestation used to exert her moderation
rights are concurrent. The system detects an untimely causal dependency, and generates a
cascade of undos to resolve it.
sync UndoOp UndoOp
partial ordering
op target
DeleteOp AttestOp DeleteOp
AddOp AddOp
alice m by Bob
Moderators Messages
Seed: 43c3f… Seed: ad113…
Causal Composition Summary
- While mutable types, when used individually, are eventually consistent,
consistency breaks if there are inter-type causal dependencies.
- We can model these causal dependencies explicitly, through causal types,
and use operational history to restore deterministic behavior.
- Causal dependencies are encoded by adding additional attestation
operations to mutable types.
- This suffices for creating user permission & access control systems that
are eventually consistent.
- We still don’t know how to make arbitrary attestations efficient (example:
you can attest that an element is in an array, but attesting its position within
the array is… a mess).
Beyond commutativity: Forking
Some use-case just can’t be expressed using only commutative operations.
Examples: a non-negative counter, a ledger.
In these cases, individual types can incorporate forking and a fork choice rule.
Consensus mechanisms may work natively (Nakamoto, etc.) or depend on external
systems, not bound by the no-coordination commutativity restrictions of Hyper Hyper
Space. These types can be nested and composed with the causal types we discussed
before.
class NonNegativeCounter
extends ForkableObject<CounterChangeOp, CounterSettlementOp> {
Take aways
- Local state + byzantine data sync seems feasible for some applications.
(we could replace most if not all of slack, for example, vis-a-vis)
- The Merkle-DAG becomes a shared medium, a bit like the web.
- The theory and tools to do this are still in the making!
[Link]
[Link]
[Link]
