Simple Head and Tail
We discuss three topics:
- why the standard head protocol is inherently complicated;
- a simplified head protocol that is much easier to implement without substantially reducing performance; and
- a short preview of the differences between the Head and the Tail protocol.
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.
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'.
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 fail because some parties get to see it too late. A snapshot leader now does not have sufficient information to make correct decisions and thus has to make temporary decisions that might later be reverted:
Assume that the leader signs tx, later receives conflicting tx', and when leading the snapshot, observes tx as not confirmed but expired (t>rmax). This means that either tx has been confirmed on time but the leader has not seen this information yet (and that tx must be confirmed in the snapshot); or that the confirmation has stalled because of a (local) timeout (and that tx' must be confirmed in the snapshot). Thus the leader cannot make a final decision on whether tx or tx' will be confirmed in the snapshot. Instead of a decision, he includes tx in its 'obituary set' in expectation that the tx is 'dead'. During a full cycle of snapshot leaders, every party now has a chance to 'resurrect' tx by proving its confirmation in the snapshot. If this does not happen during a full cycle, tx can be safely discarded. We refer to this protocol as the 'Easter' protocol. See the references appendix for more details.
Even worse, note that we haven't proven the security of this procedure yet.
The protocol can be simplified by avoiding concurrent transaction confirmation but having the snapshot leader coordinate transaction confirmation:
- Transactions are broadcast as before (concurrently)
- The current leader collects a (maximal) set of transactions that can be applied to the latest snapshot, includes the hashes of the included transactions in his snapshot, adds a timestamp to the snapshot, and broadcasts the snapshot (reqSn).
- All parties acknowledge the snapshot by broadcast if they agree (ackSn).
- The parties locallly confirm the snapshot if they could aggregate a valid multisignature.
No conflict resolution is required since all transactions are sequentialized by the snapshots.
A valid transaction implies that its containing snapshot has a timestamp in the interval [rmin,rmax]. Note that this gives the leader more freedom to manipulate time than in the standard protocol (by claiming that an old transaction was on time). However, the non-leaders still have the possibility to abort in case they do not agree.
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