an immutable transaction ledger where calculating account balance is quite fast

OCSL.md

Offer-based Chain of State Ledger

UTXOs make it hard to calculate account balance. This can be fixed by merging all UTXOs of an account into one UTXO, and forking that UTXO into one to the recipient account and the remainder to the same account, for "spending". This constraint can be baked into all transactions, which turns the ledger into an effective snapshot history of each account (chain of state), while still being as secure, predictable and light-weight, though with reduced parallelizability.

Since during each transfer affected UTXOs are "locked" (concurrent operations on them result in conflicts and all but one of such conflicting changes will be dropped, or alternatively they are locked to avoid concurrent modifications), and since in such a mechanism each account will be a single UTXO, conducting the fork (from source account) and merge (into target account) at once would require locking both accounts, limiting transaction flow. To overcome this, an itermediary "offer" transaction can be introduced, avoiding simultaenous lock on sender and recipient accounts, while also enabling a native "reserve" or "seamless soon-enough revert" feature.

General Concept

──(10)──▷ :a ──┬──(6)──▷ a:a
               │
              (4)
               │
               └──▷ a:b ──┐
                          │
                         (4)
                          │
                          ▽
──(10)──▷ :b ═══(10)═══▷ b:b

Assume Alice wants to pay some money to Bob. This comprises of two steps under OCSL:

1. Alice makes an offer, and sets the rest of her money aside.
2. Bob accepts the offer, merging the offered amount into the rest of his money.

To be more precise, each user has a unique "balance" transaction, which determines the balance of their account, and should be consumed in any future transaction.

1. Alice consumes her balance to create two transactions:
   1.a. One to Bob, "offering" the money,
   1.b. One to herself, for the rest of the money. This becomes her balance now.
2. Bob consumes the offer transaction, and merging into his own balance transaction, to "accept" the offer.
   This "merged" transaction becomes his balance now.

Transactions

In OCSL, the ledger consists only of transactions. Each transaction occurs "from" one user "to" another (possibly themselves). A transaction's resources come from another transaction it "consumes", and it can potentially also "merge" another transaction into the one it "consumes". More precisely, transactions follow this schema:

field	description	type	constraints
id	identifier of this transaction	primary key	required & unique
from	user initiating the transacion	ref user	optional
to	recipient of the transaction	ref user	required
consume	main source of the transaction	ref transaction	optional
value	value consumed (from "consume")	unsigned number	required
merge	the transaction being merged (into "consume")	ref transaction	optional
mval	value carried over by the merged transaction	unsigned number	default 0

A transaction not consuming or merging any other transaction is an "initial" transaction, indicating resources allocated to a user externally. The "total" of each transaction is the sum of the value it consumes and the value carried by the merge transaction, i.e.

initial = p => p.consume == null && p.merge == null

total = p => p.val + p.mval

A transaction from a user to themselves, or an initial transaction to that user, is called a "state" transaction, and from one user to another, a "transfer". A transfer might be an offer made, an offer being accepted, or an offer being rescinded.

state = p => initial(p) || p.from == p.to

A transaction that is neither consumed nor merged is called "unused". In a valid ledger, each user has exactly one unused state transaction, which also must be their last state transaction. This is the "balance" transaction of a user, meaning its total is the total amount a user can spend.

unused = p => !tx.exists(q => q.consume == p || q.merge == p)

balance = p => state(p) && unused(p)

Transaction Graph Notation

For a more intuitive overview of transaction flow and the rules, I've used directed graphs. Each vertex of these graphs represents a transaction, labeld by either a:b, indicating it is a transaction "from" a to b, or by p, indicating its identifier is p. Initial transactions are denoted by :a (they aren't "from" anyone). Edges connect each transaction to the transaction it consumes or merges (with double-stroke edges for merges), with the value on the edge indicating the value contributed by the consumed or carried by merge.

Initial transaction of x units to a

from	to	consume	value	merge	mval
-	a	-	x	-	0

──(x)──▷ :a

A transfer of x units from a to b consuming p

from	to	consume	value	merge	mval
a	b	p	x	-	0

p ──(x)──▷ a:b

A transfer of y units from a to b consuming p, with a sending the remainder x units to themselves

from	to	consume	value	merge	mval
a	a	p	x	-	0
a	b	p	y	-	0

p ──┬──(x)──▷ a:a
    │
    └──(y)──▷ a:b

User a consuming x units from p, merging them to the y units of q

from	to	consume	value	merge	mval
a	a	p	x	q	y

p ───(x)────┐
            │
            ▽
q ══(y)══▷ a:a

Some Examples

👉 Alice and Bob start with 10 units each. Alice offers Bob 4 units, but Bob accepts 2, offering the remainder back to Alice.

──(10)──▷ :a ──┬──(6)──▷ a:a ═══(6)════▷ a:a
               │                          △
              (4)                         │
               │                         (2)
               └──▷ a:b ──┬──(2)──▷ b:a ──┘
                          │
                         (2)
                          │
                          ▽
──(10)──▷ :b ═══(10)═══▷ b:b

Transaction Details

1. Alice is initialized with 10 units,
2. Bob is initialized with 10 units,
3. Alice makes a transaction to herself, forking 6 units,
4. Alice makes a transaction to Bob, offering the remaining 4,
5. Bob accepts 2, merging it into his initial transaction,
6. Bob forks another 2 from the offer, offering it back to Alice,
7. Alice accepts Bob's offer, merging it into her balance.

id	from	to	consume	value	merge	mval
1	-	alice	-	10	-	0
2	-	bob	-	10	-	0
3	alice	alice	1	6	-	0
4	alice	bob	1	4	-	0
5	bob	bob	4	2	2	10
6	bob	alice	4	2	-	0
7	alice	alice	6	2	3	6

---

👉 Alice and Bob start with 10 units each. Alice offers 4 units to Bob, but rescinds this offer.

──(10)──▷ :a ──┬──(6)──▷ a:a ══(6)══▷ a:a
               │                       △
              (4)                      │
               │                      (4)
               └────────▷ a:b ─────────┘
──(10)──▷ :b

Transaction Details

1. Alice is initialized with 10 units.
2. Bob is initialized with 10 units.
3. Alice makes a transaction to herself, forking 6 units.
4. Alice makes a transaction to Bob, offering 4 units.
5. Alice merges this offer back to her latest balance transaction, rescinding the offer.

id	from	to	consume	value	merge	mval
1	-	alice	-	10	-	0
2	-	bob	-	10	-	0
3	alice	alice	1	6	-	0
4	alice	bob	1	4	-	0
5	alice	alice	4	4	3	6

---

👉 Alice and Bob start with 10 units each. Alice offers 4 units to Bob, but rescinds 2 units. Bob accepts the remaining 2.

──(10)──▷ :a ──┬──(6)──▷ a:a ══(6)══▷ a:a
               │                       △
              (4)                      │
               │                      (2)
               └────────▷ a:b ─────────┘
                           │
                          (2)
                           │
                           ▽
──(10)──▷ :b ════(10)═══▷ b:b

Transaction Details

1. Alice is initialised with 10 units.
2. Bob is initialised with 10 units.
3. Alice makes a transaction to herself, forking 6 units.
4. Alice makes a transaction to Bob, offering 4 units.
5. Alice partially merges this offer back to her balance, rescinding 2 units.
6. Bob merges the remainder back to his balance, making a transaction of 2 units.

id	from	to	consume	value	merge	mval
1	-	alice	-	10	-	0
2	-	bob	-	10	-	0
3	alice	alice	1	6	-	0
4	alice	bob	1	4	-	0
5	alice	alice	4	2	3	6
6	bob	bob	4	2	2	10

Transaction Rules

Authorization

Assets are controlled by their owners.

Fork: A transaction is either from the recipient of the transaction it consumes or its sender. If the transaction doesn't consume any other transaction, then it should have no sender as well.

──▷ a:b ──▷ b:x ──▷

OR

──▷ a:b ──▷ a:x ──▷ 

(p.from == p.consume?.to)
|| (p.from == p.consume?.from)

Merge: Only unconsumed states can be merged, into a single other state of the same user.

             │
             ▽
──▷ a:a ══▷ a:a

p.merge == null
|| (
  state(p) && state(p.merge)
  && p.to == p.merge.to
  && !tx.exists(q => q.consume == p.merge)
  && !tx.exists(q => q.merge == p.merge && p !== q)
)

Correctness

No money is created or lost.

Fork: The total of any consumed transaction is equal to the sum of values of its consumers.

         │
        (y)
         │   ┌──(v_1)──▷ q_1
         ▽   │
──(x)──▷ p ──┼──(v_2)──▷ q_2      Σ v_i = x + y
             │
             ┆   ...
             │
             └──(v_n)──▷ q_n             

tx.find(q => q.consume == p).sum(q => q.value) == total(p)

Merge: A merged transaction carries its total value to the merge.

          │              │
         (y)             │
          │              │
          ▽              ▽
──(x)──▷ a:a ══(x+y)══▷ b:b

p.merge == null || total(p.merge) == p.mval

Completeness

Non-initial states aren't created or destroyed.

Fork: A consumed state has exactly one state consumer.

          │
         (y)
          │    ┌──▷ b:b
          ▽    │
──(x)──▷ a:a ──┼──▷ q_1
               │
               ┆   ...
               │
               └──▷ q_n             

!state(p) || unused(p)
|| tx.filter(
  q => state(q) && q.consume == p && q.to == p.to
).length == 1

Merge: A non-initial state either merges another state or consumes another state.

──▷ a:a ──┬──▷ b:b                ──▷ a:a ══▷ b:b
          │              OR                    △
          ┆                                    │

!state(p) || initial(p)
|| (p.merge.from == p.merge.to)
|| (p.consume.from == p.consume.to)

Acyclicality

Tracing transactions back (either through transactions they consume or transactions they merge) never passes the same transaction twice (and so eventually stops).

Ledger Validity

A ledger that is authorized, correct, complete, and acyclical is called "valid". A valid ledger can be shown to have two important desired properties: value is constant and equal to what is injected via initial states, and each user has a unique "state" in the ledger at all times (assuming they have only a single initial state).

Conservation of Value

In a valid ledger, the sum total of all unused transactions equals the sum total of all initial states.

Proof Schema: Acyclicality of the graph means the ledger has sources and sinks, and authorization ensures the sources are always initial states. Correctness ensures value going in a transformation equals value coming out, so we should be able to trace the value in the sinks of the ledger (unused transactions) back to the sources (initial states).

Proof

We prove this property for the more general case of authorized, correct and acyclical ledgers, using induction on n, the number of non-initial states in the ledger. For the base case of n = 0, there can be no merges due to (merge) authorization, so the ledger forms a union of trees, and the result can be proven for each such tree using induction on its depth. The base case is a single initial state, and for a tree with depth d, take a leaf at depth d, which consumes transaction p. Since d is the maximum depth, all consumers of p must be unconsumed transactions, and due to (fork) correctness, their sum total should equal total value of p, so removing them leaves us with a tree with the same sum total of unconsumed transactions, while preserving acyclicality, authorization and correctness. Repeat this process for all leafs at depth d, and we are left with an authorized, correct and acyclical tree with depth d - 1 with the same sum total of unconsumed transactions, which should be equal to the total of the root of the tree, i.e. the initial state.

For the induction step, we take a valid ledger with n non-initial states, and construct another valid ledger with the same initial states and same sum total for unused transactions, but with n - 1 non-initial states. To do that, we can pick an arbitrary non-initial state m, and:

• If m is unused and merges another transaction, stop the process with m.
• If m is unused and doesn't merge another transaction, find the sibling (transaction consuming the same transaction) with a descendant (consumer, or consumer of a descendant) that merges into a state m', and repeat the process for m'. If there are no such siblings, stop the process with m.
• If m is consumed, then find the descendant that merges into another state m', and repeat the process for m'. If no such descendant exists, stop the process with m.

Since the ledger is acyclical, this process has to stop at some state m = a:a. Assume the first stop condition, i.e. m is unused and it merges transactions p into q:

──▷ p ────(x)───┐
                │
                ▽
──▷ q ══(y)══▷ a:a

Introduce a new null user N, who doesn't have any state transactions, and replace the above part of the ledger with the following:

──▷ p ──(x)──▷ a:N

──▷ q

Due to (merge) correctness, q's total value must have been y. This new ledger has n - 1 non-initial states, the same initial states, and since we replaced m, of total value of x + y, with two other unused transactions with total values of x and y respectively, the sum total of unused transactions remains the same. Additionally, it is still acyclical and correct (q is no longer merged, p has the same amount of consumed value as before, just into another transaction) and authorized (p must have been from or to a, so it can be consumed by a:N).

If m is unused but does not merge another transaction, since the subgraph of the consumers of its parent (the transaction it consumes), say p, does not have any merges, it constitutes a tree. Similar to the base case of the induction, it is easy to verify that this subtree can be removed while preserving correctness, auhtorization and acyclicality. Additionally, with a similar induction on depth it can be verified that the sum total of unused transactions of the tree are also equal to the total value of p itself, so again, and since this subtree contains exactly one non-initial state (m), removing it yields a ledger with the same initial states, same sum total of unused transactions, and exactly n - 1 non-initial states, that is also authorized, correct and acyclical.

For the last case, where m is consumed, again since the subgraph of its consumers don't have any merges, it constitutes a tree. Removing this tree however might not necessarily reduce the number of non-initial states, in which case we simply replace m = a:a with a transaction a:N, similar to the first scenario.

Conservation of Balance Transaction

In a valid ledger any user with a single initial state has a unique balance.

Proof Schema: If a user has a single initial state, we can follow this state down to other user states (through consumption or merger), which fork completeness and merge authorization ensure is unique, finally reaching "a" balance transaction for the user. we can trace any other balance transaction "back up", which due to merge completeness should also uniquely reach the same initial state, which is a contradiction since the path down the initial state was unique.

Proof

We first prove that in a fork complete, authorized, acyclical ledger, any user with a single initial state has at least one balance (unused state). For arbitrary user a with a single initial state, set m to the initial state, and:

• If m is unused, then stop.
• If m is merged, due to merge authorization, it must be merged into another state of a. Repeat the process for that state.
• If m is consumed, due to fork completeness, it must be consumed by exactly one state transaction, which due to fork authorization must be of a as well. Repeat the process for that state.

Since the ledger is acyclical, this process must stop at some point, but due to stopping condition, it must stop at an unused state of a, proving the claim.

For the inverse, we utilize a weaker form of fork completeness: that a consumed state has at most one state consumer. We then prove that in a weakly fork complete, merge complete, authorized and acyclical ledger any user with one initial state at most has one balance transaction, using induction on number of non-initial states n.

The base case of n = 0 is trivial, since each user with one initial state which might or might not be used, has at most one balance transaction by definition. For the induction step n, we assume two balance transactions for user a (who has a single initial state), m and m', and construct a weakly fork complete, merge complete, authorized and acyclical ledger with the same initial states but with n - 1 non-initial states, and show that this ledger must have two balance transactions for a as well, contradicting the assumption of the induction step.

First let's assume neither m nor m' merge any transactions. they must consume different transactions, p, and p', as per merge completeness they must consume a state, so p and p' must be states, and by weak fork completeness p can't be consumed by more than one state, meaning p' != p. We remove m, and have all its siblings consume p' instead of p. Since p' also belongs to a, this preserves fork authorization, and since p can't have any other state consumers besides m, this also preserves weak fork completeness. This new ledger has n - 1 non-initial states, is authorized, weakly fork complete, merge complete and acyclical, but it has two balance transactions for a, m' and p.

Now let's assume either one of m or m' merges another transaction. Without loss of generality, we assume m merges another state, p. Note that due to merge authorization, m' can't consume or merge p, so the ledger looks like this:

──▷ m'

──▷ q ────┐
          │
          ▽
──▷ p ══▷ m

We introduce a new null user N without any initial states, and replace this part of the ledger with the following:

──▷ m'

──▷ q ──▷ a:N

──▷ p

This new ledger has n - 1 non-initial states, is weakly fork complete, authorized (since q must have been from or to a), merge complete, and acyclical, but it has two unused states for a, namely p and m', contradicting the induction step's assumption.

Operational Notes

OCLS is mainly designed out of a desire of having auditability of UTXOs in a managed system, hence reducing the inherent need of concurrency that would have been present in an essentially decentralized system. It is operationally comparable to the following alternative models:

• UTXO: OCLS provides instant account balance overview, but with no concurrency per account.
• Account Model: OCLS provides inherent robustness and auditability, but with added complexity.
• Block Lattice: OCLS is quite similar, providing more flexibility with its transfers, again at the cost of added complexity.

Balance Lookup

Since balance is unique per user, in a managed system it might be a good idea to maintain a reference to each user's balance, which is updated by each fork / merge. It is highly recommended that transactions are kept atomic to avoid corrupt states, though checking a corrupt state (where a recorder user balance is consumed or is not a state) and fixing them is straightforward.

Another alternative would be to add a mutable used column to each transaction, for faster balance lookups. This could also speed up detection of corrupt states even when a direct reference to user balance is maintained. This can be paired with an immutable precomputed field state, or a partial index if supported by storage mechanism, to further speed up state lookup.

Offer Locking

For some use cases, it might be useful to "lock" offers after a while so the sender can't rescind them anymore. This might be done by introducing a transaction_time and rescission_deadline columns for transactions, and adding the authorization constraint like the following:

(p.from == p.consume?.to)
|| (
  p.from == p.consume?.from
  && p.transaction_time < p.consume?.rescission_deadline
)

Alternatively, an immutable locked column can be introduced, where a transfer is consumed by an identical but "locked" transfer, and a locked transfer can only be further transferred by its recipient (no rescission), i.e. modifying fork authorization constraint as follows:

(p.from == p.consume?.to)
|| (p.from == p.consume?.from && !p.consume?.locked)

Note that while in a typical ledger each transaction is expected to be authorized only by the user where the transaction is "from", this method of locking would require allowing also the user who the transaction is "to" to also be able to lock a transaction, adding complexity to access control of the ledger.

Concurrency

Ledgers are linear on balance of each user, i.e. any change (fork and merge) of a user balance needs to be sequentially ordered with regards to other changes, or in other words, changes to user balance need to happen one at a time. This limits per account concurrency and reduces transaction flow for busy accounts.

Since concurrency is bound by account, use of "satellite" accounts can increase concurrency bandwidth. A satellite account is an account controlled by the same entity controlling a "main" account, allowing them in typical use to conduct parallel transactions at least to the number of their satellite accounts.

This concurrency increase can be amplified if the ledger boasts a locking mechanism as well, as satellite accounts can simply avoid "merging" incoming offers (either made by the main account for parallel offers to various recipients, or redirects from the main account for parallel acceptance of offers made by various senders), and only "lock" incoming transactions. Note that the more unmerged transfers an account has associated with it, the more complex calculation of its actual spendable balance would become, but through this means high influx accounts can create an effective layer of UTXOs on top of their main account, with much increased concurrency (in exchange for more complex balance calculation).