Abstract
A recent evolution of the blockchain structure is emerging to address the performance issue of permissionless chain-based ledgers, in particular the small number of transactions confirmed per second. To address such an issue, new designs have been brought forward, including Bitcoin-NG, which favors an off-chain mechanism in which blocks refer to a leader in charge of validating transactions batched in micro-blocks out of the chain [6]; Lightning [10], which follows the same principle but only publishes the outcome of repeated transactions among a set of parties. Others propositions such as HashGraph [2], ByteBall [5], and Iota [4] leverage the presence of well known institutions to get rid of blocks, while Ghost [12] and Spectre [11] protocols family modifies the blockchain data structure from a totally ordered sequence of blocks to a directed graph of blocks. Blocks are built so that they commit the state of the directed graph at the time blocks were created which decreases the opportunity for powerful attackers to create blocks in advance. Regarding the graph-based approach, the absence of mechanisms to prevent the presence of conflicting records (i.e., blocks with conflicting transactions) or the presence of cycles in the directed graph (Spectre [11] organises blocks in a directed, but not acyclic, graph of blocks) require that participants execute a complex algorithm to extract from the graph the set of accepted (i.e., valid) transactions [11]. Sycomore1 is an immutable permissionless distributed ledger whose structure is a particular directed acyclic graph of blocks, called SYC-DAG [1]. Its design differs from existing distributed ledgers in that its graph structure dynamically adapts to fluctuations in transaction submission rates: When the leaf block of a chain (more precisely the last blocks appended to a chain) of the graph exceeds a maximal loading threshold (the load is measured in Bytes), subsequent blocks are partitioned over two sibling chains, and these blocks are mined in parallel (as will be described shortly, even if blocks are appended in parallel to the SYC-DAG they cannot be conflicting, i.e., each valid transaction cannot appear in more than one block). Conversely, when the leaf blocks of two sibling chains (again the last blocks of two sibling chains) fall short of a minimal loading threshold, subsequent blocks will belong to a unique chain. The decision to split a leaf chain of the SYC-DAG or to merge two sibling ones is locally taken by each miner, and soundness of this decision is verifiable by everyone at any time [1]. Actually, Sycomore has been designed to meet the following properties [1]:
P1. Self-adaptation to transaction load. A rise or a drop in the current number of submitted transactions is dynamically handled by the progressive creation or disappearance of sibling leaf chains in the SYC-DAG;
P2. Balanced partitioning of transactions. There does not exist any transaction that belongs to two different blocks.
P3. Unpredictability of the predecessor. The leaf chain to which a new block is appended can neither be chosen nor predicted among all the leaf blocks of the SYC-DAG.
P4. Chain fairness. All the leaf chains of the SYC-DAG grow at the same speed.
P5. Negligible probability of forks. The probability of forks is maximal when the SYC-DAG is reduced to a single chain (i.e, 1, 2 X 10-3 in the time interval of 30 seconds) and decreases proportionally with the number of leaf blocks.
