EY Nightfall: Timber

EY Nightfall is a Layer 2 private transaction framework that fairly recently has garnered major attention in the sphere. Nightfall uses zero knowledge proofs together with off-chain transaction processing and achieves functionality similar to ZCash, but on Ethereum:

• the users make blinded commitments to their coins in a Merkle tree;
• coins are spent by constructing a SNARK proving that there is an unspent coin known to the user somewhere in the tree, without revealing which coin;
• when the coin is spent, the user also attaches a nullifier — a commitment-determinant string that ensures the same coin will not be spent in the future.

While the Nightfall design around zero knowledge is solid, it is not the primary innovation of the project, as it for the most part follows the construction of ZCash. What is truly interesting about it, however, is its approach to data availability.

Data availability is an ever-present issue in Layer 2 designs, which leads to users’ inability to withdraw their assets from the off-chain network back onto the chain in the worst case where the operator of the off-chain network refuses to provide necessary data/witnesses.

There are various approaches to this problem, but in this article we will focus on the Nightfall’s protocol for solving data availability called Timber. Timber facilitates on-chain availability, which means that the entirety of the data required for a withdrawal can be reconstructed from the synchronizable chain history. While on-chain availability is in general costly in terms of Layer 1 storage, Timber uses a set of clever tricks to minimize the amount of stored data, thus achieving the solution in a relatively cheap way.

Timber utilizes the fact that the tree of commitments (which is all the data necessary to withdraw coins in this ZCash-like architecture) is append-only, so with each new addition only a small subset of tree nodes needs to get recomputed. Therefore, Timber does not store the entire tree, instead storing in a contract a small (O(log(n)), to be precise) number of nodes called “frontier”. The frontier contains only the nodes that are required to recompute the root when adding a new leaf into the tree.

Illustration of Timber’s on-chain storage mechanics. Courtesy of Michael Connor.

This technique allows to ensure the consistency of the tree root while severely cutting down on storage costs. Note, however, that it does not make addition of individual leaves efficient — since at least one new node will be written/rewritten in the frontier — but with batch addition the frontier is only updated after the entire batch, which means that O(n) leaves may be added at the cost of O(log(n)) storage writes.

Another interesting approach reflects in some ways the design philosophy of Ethereum 2.0 regarding application layer: instead of storing the state of the system within the smart contract (which is expensive), the app enables users to build the full state locally from history, which is fully on-chain. Only a small amount of data is stored on-chain to help users check the consistency of the final state. Consequently, instead of storing leaves on-chain, Timber emits an event for each new leaf, specifying the leaf index and value, and the new root. Nightfall also provides a local listener that detects “NewLeaf” events and builds locally a full Merkle tree. The user can then use this local tree to construct SNARKs that verify with the on-chain root. Since events are much cheaper than storage writes, this allows to further reduce the cost.

Overall, with proper batching and without taking SNARK verification into consideration (efficiently verifying SNARKs on-chain, although very much doable, is a big separate topic), the amortized cost of each transaction in Nightfall is ~10k gas (which mostly covers event emission) which is 2x times cheaper than ordinary Ethereum transfers with an added benefit of privacy on top.

Timber is exciting to us is because it can be a useful and mechanically simple data availability solution for future projects, and can be used as a ready-made primitive by architects when designing Layer 2 applications. All Timber requires to work is the state tree being append-only, which can be done even for complex state transition functions (which is illustrated in the same Ethresearch thread). While it still limits scalability to some degree, it fits very well into the Ethereum 2.0 paradigm of “history first, storage second”, and we are likely to see this mechanism used extensively as Ethereum’s ecosystem grows.

If you want to learn more, check out the Github repository for Timber.