Sarang Noether here again, with the last of three monthly reports for my current funding period. As always, it's been a flurry of exciting activity and developments in Moneroland, and I'm pleased to present this summary of my work for November.
The beginning of the month was spent on a couple of big whitepapers that were being vetted for the project. The first was SPECTRE, a new technique for managing peer consensus. It should come as no surprise that we currently use a chain structure for managing block evolution, and apply simple longest-chain consensus to determine which of multiple competing chains a node should accept. The SPECTRE protocol does away with a single chain altogether in favor of a more general structure called a directed acyclic graph. In some ways, this simplifies the addition of multiple blocks, since order properties are changed. Correspondingly, the consensus algorithm is changed significantly. Instead of nodes voting based on longest chains, the blocks of the graph themselves vote on the order of other block pairs using the graph topology and ordering properties. It gets a little hairy to write down, but the security and scaling benefits can be significant. Throughput can climb without the corresponding hit on security that longest-chain consensus suffers. There are, however, issues that arose that could make pruning challenging. I and the rest of the Lab continue to keep our mathematical eyes open for further developments in this area.
Still on the topic of the blockchain/blockgraph, I performed an analysis of another construction, non-interactive proofs of proof-of-work (NIPoPoWs). Currently, a new node that comes online must request and validate the entire blockchain before it can be securely assured of the correctness of recent blocks it receives. If the node came online to watch transactions to a new wallet, it may be a substantial time before it can receive and spend funds reliably. With a NIPoPoW construction, a "diet node" can instead request a much smaller modified blockchain structure from a peer node that includes a short tail of recent blocks. To ensure that the diet node can trust these blocks, it also requests a supporting subset of historical blocks that include extra header data linking them to each other. The statistics behind these block headers allow the diet node to review competing supporting data from multiple peers and easily determine which to accept. The benefit is that the supporting block subset grows only logarithmically with the total size of the blockchain, so the diet node can much more quickly receive and send funds with new wallets whose transactions are only in the tail of the blockchain. There are shortcomings in that the diet node cannot use funds from blocks outside of the tail until it actually receives them in full; however, a NIPoPoW construction could be used to securely bootstrap new nodes until they receive the complete blockchain, helping to create a faster and smoother experience for new users. This work is ongoing.
The biggest new development, and the one that has received perhaps the most discussion in the cryptocurrency community, is in the topic of range proofs. Range proofs are used in Monero to support confidential transactions and prove that hidden amounts lie within a mathematically acceptable range to prevent certain attacks. However, our current construction uses a substantial amount of space and scales linearly with both the size of the range and the number of outputs in a transaction. A new whitepaper introduced bulletproofs, an alternative construction. Instead of using ring signatures on individual bits of the hidden amount, bulletproofs use a clever polynomial inner product protocol. The benefits for transaction size are significant, since the size of a bulletproof scales only logarithmically with both the size of the range and number of outputs. For a single-output transaction, it reduces the size of the range proof to around a tenth of its current size. For a two-output transaction, the savings are even greater. Unlike many other approaches where size and complexity battle it out, bulletproofs are efficient at verification, depending on optimizations to certain elliptic curve operations that are under investigation. I produced and tested a working Java implementation of linear bulletproofs (an initial simplification by the authors) and logarithmic bulletproofs to demonstrate correctness. Work is ongoing to optimize the logarithmic extension of the code, complete the verification complexity study, and implement efficient bulletproofs in the Monero codebase if so desired.
Finally, I and others in the Lab have discussed at length the importance of educational outreach. The cryptocurrency space continues to grow by leaps and bounds, but few students have the opportunity to study it. Cryptocurrencies like Monero are a unique blend of pure cryptography, mathematics of all sorts, clever computer science, and a bit of economics. Engaging new generations of students will help drive cryptocurrencies into the mainstream, which can benefit many different projects like Monero. There are opportunities for our researchers (including me) to conduct short courses of our own design on cryptocurrencies and distributed ledger technologies. I remain in active discussion with several academic organizations to plan such courses, the first of which may occur as early as next summer. It's been the consensus of the community that student outreach is an excellent investment in the future of our technology, and it highlights the fact that Monero supporters want to give back to society in productive ways.
This report ends my current funding period. I am eager and excited to continue work on new developments through March 2018, the work period for the round of funding that was recently completed. My deepest thanks and appreciation are extended to everyone who has offered support! The goodwill and support of the community continue to help the Monero Research Lab bring new and cutting-edge research to the table, now and in the future.