Skip to content

Simple Head and Tail

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

We discuss three topics:

  • why the standard head protocol is inherently complicated, a simplified head protocol that is much easier to implement without

Standard Head-Protocol Complications

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 will follow 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 (in the sense of obtaining a valid multisignature).
    • Case 1: P had tx confirmed and does 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 does not see it confirmed, and thus signs SN. Even if tx eventually gets confirmed, the SN will have precedence, and SN confirmed implies that all honest parties signed it, and thus no honest party tx as confirmed.

Handling of Time Constraints (see also ePrint, Appendix D.2.

(Note that we do not have an implementation of 'time' in the head protocol. The idea is to couple it to the mainchain---somehow.)

Each EUTxO transaction specifies a time interval [rmin,rmax]. A valid transaction implies that the slot of its containing block (i.e., its timestamp) lies in this interval. This concept causes problems in the head as head operations are asynchronous. Even assuming a notion of time in the head, what does it mean that a transaction's timestamp lies in the specified interval?

We adapt the confirmation rule by the natural rule that a party only sings a transaction if it observes it during the time interval [rmin,rmax].

Time handling now complicates conflict resolution as even a non-conflicting transaction can be on track to be confirmed but finally fails because some parties get to see it too late.

Simplified Head Protocol

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