Passing state transition tests, re-licensing, merkle caching, p2p development + more.

Summary

Achievements

• Presented at EDCON and hosted Eth2 implementers and hosted EF researchers in our office.
• Re-licensed from GPLv2 to Apache 2.
• Now passing the v0.5.1 state transition tests.
• Assisted with the inter-chain BLS stigmatisation efforts.
• Implemented cached merkle hashing, which saw massive speed gains.

Next Steps

• Update to spec v0.6.0 (already started).
• Implement discv5 (peer-to-peer network discovery mechanism).
• Instantiate a state-of-the-art public test-net.

Achievements

EDCON

Adrian and I were honoured to appear on stage at EDCON 2019, providing descriptions, benchmarks, and demonstrations of Lighthouse. While the testnet was demonstrated on stage, Adrian chose not to challenge the demo-gods and instead chose to pre-record his demonstration. Smart move.

Sigma Prime was also pleased to host some distinguished guests from the Ethereum community in our offices while they visited Sydney for EDCON. It was a fantastic opportunity to discuss progress and directions with other Eth2.0 implementers, and it was our absolute delight to show off our beautiful city and country.

Re-licensing to Apache 2

We're very happy to announce that Lighthouse is now an Apache 2.0 open source project! We have managed to successfully re-license the project from GPLv2, thanks to the unanimous agreement of our contributors.

As explained by Mehdi in this tweetstorm, Apache 2.0 is less restrictive and more permissive than GPL, since it does not require derivative works to be open source. At Sigma Prime, while being avid supporters of open source software, we acknowledge and understand the intellectual property protection requirements that face some large enterprises. We would like to ensure that they aren't prevented from building on our beacon node and validator client implementations.

State transition tests

We are pleased to be passing the specification v0.5.1 state transition tests, and thankfully our spec state transition functions only required a handful of fixes. These were mostly related to the intricacies of "tree hash", the merkle hashing scheme for Eth2.0.

This confirms that our far more performant spec implementation is indeed consistent with the Python implementation detailed in the spec. Well, at least as consistent as those tests are concerned anyway. Passing the v0.5.1 tests does a lot of ground work which ease our transition into the soon-to-be-released 0.6.1 test suite.

Assisted with the inter-chain BLS standardisation.

There is a drive currently lead by Alogrand to standardise BLS Signatures with a strong focus on BLS12-381. Standardisation will allow all parities using BLS Signatures to have comparable signatures, that is anyone who signs the same message with a the same secret key will get the same signature no matter which platform they are operating on.

Standardisation is highly beneficial to all parties involved as it reduces repeated work, is easier to maintain, allows for easier communications between platforms, and reduces the likelihood of mistakes in implementations.

The key areas that need standardising for BLS Signatures are - hash-to-curve (converting a message to a point on the curve) - serialisation (converting a point on the curve to bytes) - protection against the rogue public key attack

We have currently written and implemented BLS Signature benchmarks for two methods of hash-to-curve: hash-and-test (kind of like guess and check until you find a valid point) and the Forque-Tibouchi method (a mathematical approach that can be used to guarantee finding a point in constant time). We are also currently implementing a recently released method.

Sigma Prime has been working alongside Chia, the Ethereum Foundation, Algorand, and researchers such as Raid Wahby and Dan Boneh to implement, test, and benchmark different alternatives. You can read more about BLS and the rogue public key attack and find an initial draft of the standard.

Merkle hashing

Note: this section assumes an understanding of merkle trees.

We implemented a cached-merkle hashing algorithm which has demonstrated a ~25x CPU-time improvement than the naive tree-hashing algorithm in some cases.

All block and state hashes in Eth2 are merkle roots, which the spec calls "tree hashes". Hashing in this manner allows for succinct proofs-of-inclusion (merkle-proofs) which are valuable for light clients, however it is far more CPU intensive than a regular hash. Tree hashing a BeaconBlock object could easily require thousands of more hashes than just regular "flat" hashes.

An Eth2 client must perform a tree-hash of the BeaconState every 6 seconds (a slot) and for each new BeaconBlock. This is a large object and we've seen a modern i7 CPU take > 1 second to perform this tree hash; this time is simply unacceptable. Thankfully, because the BeaconState only changes slightly between each hash there is a solution to significantly reduce the hashing time.

If we cache the "internal nodes" (those nodes which are just hashes of values, or hashes of hashes of values, etc.) we can scan the leaves of the tree, determine which leaves have changed and then only re-compute the hash for those internal nodes affected.

An Eth2 state transition has several places where a list of size 8,192 needs to be tree hashed and only one element of that list has changed since the last hash. With tree hash caching we perform only 12 hashes, instead of the 8,191 that would be required without caching.

In a familiar fashion, this CPU-time speed up comes at the cost of memory/storage. The size of a tree hash cache for a given object is roughly the same size as that object, doubling our storage requirements. Future iterations of our caching algorithm may focus on ways to reduce this.

Next steps

Update to spec v0.6.0

A few days after we started passing the v0.5.1 tests, the new v0.6.0 specification was released. This update includes some bug fixes and simplifications that are quite valuable.

Michael and Paul are now working on these updates and expect to be completed in approximately two weeks. After the specification has been implemented we will focus heavily on parsing the new tests that Diederik (from the Ethereum Foundation) has been working on.

Discv5

How peers discover each other over the network is an active discussion topic for Ethereum 2.0 researchers and implementers. Ethereum 1.0 uses a discovery protocol called discv4. Felix Lange has put together a specification which improves on a number of short-comings in discv4, which is aptly named discv5. Adrian will attempt to implement the new discovery protocol over the upcoming weeks, which will allow Lighthouse to begin using the discovery protocol that will most likely be used on the Eth2.0 mainnet.

Instantiate a long-standing testnet

Once we have v0.6.0 tests passing and discv5 implemented, we will focus our efforts on establishing a long-standing, single-client, public testnet. Our aim is for this testnet to adhere to all published specifications and provide empirical feedback to our developers, Ethereum researchers, and the community at large.