Skip to content

Simple Head and Tail

Jump to bottom
Matthias Fitzi edited this page Mar 22, 2021 · 25 revisions

Simple Head-Protocol Variant

The solution described in the FC21 paper and on ePrint allows for concurrent transaction confirmation in the head. This allows for better throughput and/or latency but implies some serious complications of the protocol as listed below.

Conflict Resolution

Consider a party P who receives a reqTx(tx) or transaction tx, signs it, and later receives reqTx(tx') for a conflicting transaction tx'. Note that this does not imply that any party has misbehaved as this can naturally happen with smart contracts. Thus, liveness must be guaranteed, i.e., the head cannot simply be aborted in this case. Also, P cannot sign both transactions as this could lead to the confirmation of two conflicting transactions.

The solution to this problem is to resolve conflicts in the snapshots. In addition to the confirmed transactions to be applied to the predecessor snapshot (the original purpose of the snapshots), the leader includes all transactions Tx he has signed so far and for which he has seen conflicting transactions, and also includes Tx', the set of such conflicting transactions. The snapshot is then computed by applying the transactions in Tx (in addition to the confirmed ones), and 'deleting' the transactions in Tx'.

A short safety argument

The potential problem of conflict resolution is that, still, a transaction tx could be confirmed on 'transaction level', while a conflicting transaction tx' is confirmed on 'snapshot level', overriding the confirmation of tx. Here is a short argument why this is not a problem (and what the rule is to guarantee this).

  • Assume that party P signs a snapshot overriding tx with tx', SN(tx',~tx) before seeing tx. Then he signs the snapshot and will simply ignore tx forever. This implies that tx will never be confirmed (P's signature is missing).
  • Assume that party P signs tx first and then receives a snapshot request for SN(tx',~tx). Then he signs the snapshot exactly if it has not accepted tx as confirmed yet. Note that this situation can indeed lead to the situation where both, tx and SN(tx',~tx) get confirmed.
  • Case 1: P had tx confirmed and did not sign SN. The protocol now stalls. However, the snapshot leader is detected to be faulty (he signed tx and created SN(tx',~tx), although the rule says that he has to resolve in favour of his local view, i.e., tx instead of tx'). Liveness is not guaranteed but does not have to as we have a corrupted head member.
  • Case 2: P signed tx but did not have it confirmed, and thus signed SN. Even if tx eventually gets confirmed, the SN will have precedence, and SN confirmed implies that all honest parties signed it, and thus did not accept tx as confirmed.

Handling of Time Constraints

TODO

Tail-Protocol Vision

In contrast (and as the main difference) to the head protocol, the tail protocol is asymmetric in the sense that there is one central server and a potentially large number of clients who delegate the maintenance of the ledger to the server.

The server is always online and computationally powerful whereas the clients may be lightweight and may only connect every now and then. When a client reconnects, the server updates him about 'missed' updates such that the client is up to date and can submit transaction to be executed in the tail. Furthermore, all parties in the head protocol (attempt to) share the same full state while, in the tail protocol, a clilent may only be interested in a small portion of the operations, and thus, the clients may maintain only partial state of the full tail.

Unlike the head protocol that can be unilaterally terminated, the tail is guaranteed to persist over a long time range (e.g., per an expiry date). In particular, detected misbehavior (by server or clients) must be resolved on-chain in a 'non-terminating' way, such that the tail can continue to operate off-chain.

In terms of blockchain lingo, the tail can be seen as sort of a 'non-custodial chain' while the head is a 'classical' multi-party state channel.

The main distinguishing properties thus are:

  • offline-tolerance of clients
    • possibly large messages required from the server to update a reconnecting client.
    • possible impact on message queuing?
  • asymmetric operations
    • asymmetric resource requirements for the nodes (server versus client).
    • message broadcast is likely not suitable as messages are typically only of interest to a small amount of participants.
  • faulty behavior has to be repeatedly corrected without the possibility for early abort
    • more chain interaction than in the head protocol
Clone this wiki locally