Research program to work on hardening Cardano against quantum computers
1 February 2018 5 mins read
At its heart, cryptography is the science of secure communication. We have all secrets, expectations of privacy and assertions of truth about messages we receive that require some notion of verification or quantification of trust. Cryptography provides us with a toolbox to better understand how to transmit and verify these artifacts of communication in the presence of an adversary. The challenge is that transmission mediums change and the capabilities of an adversary change with them. The earliest days of secret communication ranging from Caesar to the American Confederacy involved substitution ciphers and elegant physical devices to accommodate the decryption of messages.
The apex of these approaches was the Enigma machine used by the Nazis during World War Two.
As with all cryptographic algorithms, the security of such techniques is always dependent upon assumptions about the capabilities of the adversary. For example, interception of encrypted messages was a deeply personal affair involving finding the spy or messenger moving the scroll. With the invention of wireless communication, listening posts could easily collect all messages transmitted without the sender even knowing.
Decryption without the trusted hardware device, would require the adversary to have special knowledge and the ability to perform enormous amounts of calculations. The creation of the Bombe at Bletchley Park made this task automated for the first time in human history.
The invention of computers and later the internet has fundamentally changed the entire field of cryptography. Human and transmission limitations as well as knowledge transfer are now such that cryptography had to transform from clever algorithms and security through obscurity to a science assuming an increasingly more sophisticated adversary that is usually only constrained by physics and mathematically hard problems.
For the past few decades, we’ve been converging into a reasonable model of security that is comfortable for internet connected devices. Usually security is no longer compromised by an unknown weakness in our ciphers, but rather a flaw in their use or implementation in software.
As much of a triumph this convergence is for the field of cryptography, like Bombe in the 1940s, we are now forced to contend with a new adversary capability: quantum computation.
Quantum computers seem to present the challenge that fundamentally hard problems which secure our modern cryptographic algorithms may not be hard anymore. Should this occur, most of the modern algorithms we use will have to be phased out and replaced with fundamentally different ones. Cryptocurrencies are consumers of these modern cryptographic algorithms from the simple, such as public key systems and hash functions, to the complex, such as zero knowledge proofs and multiparty computation. As there is an explicit and ever increasing bounty for breaking the security behind a cryptocurrency, the challenge for IOHK is to imagine how to provide long-term security in the face of future adversaries, including ones that possess quantum computers.
Therefore, we have launched a long-term research agenda to gradually harden all algorithms used in Cardano’s protocol stack against an adversary who possesses a quantum computer. The first part of this agenda is to harden our consensus algorithm Ouroboros.
All good research agendas need strong leaders who have a proven record and thus we are extremely fortunate to anticipate the inclusion of Professor Alexander Russell of University of Connecticut, USA as a senior research fellow in IOHK research and an external collaboration with Assistant Professor Peter Schwabe of Radboud University. They will play key roles in our first attempt at hardening the Ouroboros protocol for the post quantum setting.
Professor Russell (Ph.D. MIT 1996) has a deep understanding of quantum computation that spans over two decades. His work on quantum computing has focused on algorithms for algebraic problems, intractability results, and quantum-secure cryptography. He was also one of the co-authors of the Ouroboros papers and thus the combination of his deep understanding of blockchain protocol security and his expertise of quantum computation and post-quantum security put him at a unique position to lead the effort of projecting Ouroboros to the post-quantum setting.
Professor Schwabe (Ph.D. Eindhoven 2011) is one of the rising stars of the field with contributions from his work on SPHINCS to lattice signatures such as Tesla and Dilithium. He is also participating in NIST’s competition to harden the cryptographic algorithms used by the United States government against quantum computers.
As this is long arc research, the output will be many papers, conference discussions and iterations; however, we are excited to start the process and conversation. It is our belief that over the next 50 years cryptocurrencies will become the standard way of representing and transacting value.
Therefore, it is essential for us to proactively prepare our protocols against the threats of the future with the hope that Cardano can enjoy the durability that TCP/IP and other long-lived protocols have demonstrated. We also believe it is essential to structure the conversation within the cryptocurrency community to involve university partners and domain experts as soon as possible in order to avoid common mistakes, incomplete solutions, and have access to the best available knowledge.
In the short term, the first output of this workstream will be to choose and properly parameterize a post-quantum signature scheme for Ouroboros Praos as well as examining our protocol against the capabilities of an adversary in possession of a quantum computer. Our hope is that this work will be finished and implemented before the end of 2018 in Shelley’s first major upgrade.
Now that the dust has settled after travelling to more than 20 countries, dozens of conferences, major events and community meet and greets this year, I’ve finally had the time to reflect on the progress of the Cardano project as well as some of the lessons I’ve learned. It’s honestly been the most challenging year of my life, filled with drama, stress, death and some unbelievably cruel people. It’s also been one of the most rewarding and joyful years, having had the chance to meet thousands of passionate and kind fans, technologists and scientists – I can see the inspiration that Charles Dickens had when he said it was the best of times and the worst of times. The reality is that the internet and in particular the cryptocurrency space can be a really toxic place if you allow it to get to you. There were times after reading some blog post or comment on Reddit that I seriously questioned if this effort was worth it. I can understand why Mike Hearn left Bitcoin.
But I’ve never been here for the short term, it’s always been the dream of finding a way to get financial services to the three billion people who don’t have them using technology that was only a dream a generation ago. And I think we are making great progress there.
In January of 2017, Cardano was still mostly in a very early alpha stage. We had tremendous engineering difficulty getting Haskell, our DevOps and the new protocols such as Ouroboros and Scrape to play nicely together. Rather it was a constant learning curve of how to tame the three headed dragon of research, decentralized teams and exotic programming languages while managing the expectations of a huge community.
As an aside, Cardano has one of the fastest growing and most intelligent fanbases. We actively invited people who care about formal methods, peer review and functional programming to come and see what we are working on. These people aren’t swayed by jargon or flashy marketing. They were born with bullshit detectors in their cribs.
I’ve gained significant strength and a much needed boost in morale from interacting with our community. For example, one member asked about how we were verifying the proofs in the Ouroboros paper and I posted a link to Kawin’s Isabelle repo. Most would simply say ‘that’s nice’ and move on. This member took the time to read the code and mentioned we had a long way to go with specific examples.
For most people, Isabelle is a name followed by a lake in Minnesota. For our community, some can actually read the code and comment on it. That’s a rare gift and it’s the privilege of a lifetime to be in this kind of environment (we ended up hiring the person who commented on the code).
Moving through the months, Cardano moved from the lab to a series of testnets to eventually being released in September. Dealing with these transitions gave us a newfound appreciation for just how many different computer and network configurations exist. I can almost feel a Windows force ghost whispering “I told you so” in a smug voice.
We designed Byron (the September release of Cardano) to be the minimum viable product necessary to test the concepts Cardano is built upon. We wanted to run Ouroboros in a production setting to see epochs function properly. We wanted extensive logging of both the edge nodes and relays to see how our network is being used. We wanted to have third parties play with our APIs and tell us where we screwed up (boy did they ever!). We wanted to test the update system a few times.
Overall, the experiment has been a tremendous success. There are several thousand edge nodes concurrently connected to the network. There are several exchanges and other third parties using our software in the harshest possible way. There is a wealth of data flowing in that is giving us a much better sense of what we need to do to make Cardano better.
Since launch, we’ve already pushed three updates to the network without incident. We’ve started a very rapid redesign of our middleware and its associated APIs to make it easier for third parties to integrate. We’ve started a series of systematic improvements to our network stack that will be finished with the Shelley release that should dramatically improve things.
However, what excites me most about 2018 is that Cardano is starting to open up to the world. Delegation and staking will be rolled out all throughout Q1 and Q2 in coordination with the community. Soon we’ll have a testnet running IELE allowing developers to play around with our smart contract model for the first time. And we’ll be deploying our first verified protocol with Praos thereby engaging the formal methods community.
Constantly living in the moment, one tends to eschew Cardano’s vast scope in exchange for the problem of the week. But looking at our ever growing Cardano whiteboard series demonstrates how many brilliant people wake up every morning thinking about how to solve the problems of scalability, interoperability and sustainability. These aren’t just hypothetical lectures. They are backed by papers, funding and developers working full time.
Then there are the new things. The work by Professor Rosu and Runtime Verification on K and semantics based compilation isn’t just really smart competitive differentiation, it’s literally moving the chains of the entire field of programming language theory. The Cardano project is creating a financial incentive to have correct by construction infrastructure from virtual machines to compilers. Our success means you don’t have to handwrite this code ever again – not just in a cryptocurrency context but in a general context.
Our research efforts at Tokyo Tech under Professors Mario Larangeira and Bernardo David with multiparty computation is rapidly bringing these protocols into practical use. Kaleidoscope and Royale are case studies on how to achieve everything that Ethereum does off chain, in a low latency setting, privately and at a scale of millions of concurrent users each in their own domain. Further abstractions will push this work into more useful domains like decentralized exchange. And eventually DApp developers will be able to integrate these protocols into their code via libraries.
Professor Bingsheng Zhang’s research on treasuries and voting is groundbreaking. It gives our project the ability to open a discussion about how changes to cryptocurrencies should be proposed, debated, approved and funded. What’s most special here is the interdisciplinary nature of the effort that can draw from political science, game theory, sociology, open source software governance and computer science. There is something for everybody.
Moving into 2018, we are going to open this discussion up by both engaging the community directly and by holding a conference in Switzerland. More details will be published later, but the basic idea is that this area isn’t a Cardano problem. It’s a cryptocurrency problem. And there are many great projects from Dash to Pivx who are trying to solve it in a novel way. We ought to talk to each other.
I could continue to enumerate our research efforts (there’s a lot more to write), but I think the point has been made. Cardano isn’t a cryptocurrency as much as it is a movement of minds who are frustrated with the way technology works in practice.
The functional programming community has for decades had great solutions to many of the problems plaguing modern developers, but they have been historically ignored. Our RINA guys, if given a chance, could build a much better and more fair internet. Layering protocol development with formal methods extracts a much cleaner and more meaningful design process where ambiguity and hand waving is slain.
What Cardano has given us is a chance to answer if only the world worked this way with why not? We have the freedom to dream again and the freedom to try new things without asking permission. I even have a chance to work with my heroes like Phil Wadler. 2018 is going to be one hell of a year.
Thanks for reading.
Cardano has been an incredibly challenging and fun project to work on involving many teams throughout the world with different skills and opinions on design, process and quality. Our core technology team consists of Well Typed, Serokell, Runtime Verification, Predictable Network Solutions and ATIX, with IOHK leading them. Then we have external auditors such as Grimm, RPI Sec and FP Complete ensuring quality and holding us accountable to delivering what we have promised. When dealing with a consortium, it’s important to be aligned not only on day to day affairs, but on the broader engineering philosophy of why and how things should be constructed, as well as the pace of development. I’d like to spend a few paragraphs exploring the principles that guide our roadmap.
First, we can only grow as fast as our community. At the moment, more than half of our community has never used a cryptocurrency before. This reality means that while it would be awesome to introduce complex features like stake pools, blockchain based voting and subscribable checkpoints, they would be underutilized and therefore ineffective until the community catches up. To this end, we’ve provisioned resources towards a help desk tour, a dedicated support channel and trying to interact with our community as much as possible as they grow. This is tremendously time consuming, but it really does force our software to become simpler and more useable.
This effort challenges design assumptions, such as what the capabilities of the average node in our system should be. Throughout the next few months, a large part of our focus will be on answering questions, debugging software, improving the user experience and community education. The output will be that more people use Daedalus comfortably and back up their Ada, are able to use exchanges according to best practices, and understand why Cardano is a special project. It also means our software will slowly become more bug free and compatible with different configurations.
Second, we believe firmly in the vision of Satoshi that these networks must be resilient and distributed. Resilience means we cannot optimize around a collection of trusted or usually reliable nodes to maintain the network. Distributed means that wherever possible, every node contributes to propagating the network and its DNA. This creates tremendous design challenges. One is at the mercy of the weakest links when replication is the tool used for resilience because it dramatically slows the network as more users come online. While we feel that a protocol like Ouroboros is perfectly suited to properly balance these conflicting demands, we admit that general network and database capacities aren’t quite ready for this task. The sole – and temporary – advantage that Cardano enjoys here is that we are new and won’t feel the pain of scale for the next year.
Yet we must remain vigilant in our efforts to address these concerns systematically as we have done with Ouroboros. Therefore, many of the most significant network improvements will be scheduled for deployment in late 2018 and throughout 2019. Third, there is a difficult balance between research and deployment. We have great protocols and protocol developers. We also have a unique advantage in being able to quickly submit papers for peer review in order to promptly validate them or fail fast, instead of enduring difficult lessons of hindsight that can result in the loss of funds. However, we cannot allow the urge to have something ready soon for commercial advantage to drown out proper process. With Ouroboros for example, we have a serious and ongoing formal specification effort using Psi Calculus to model and remove all ambiguity from our consensus protocol. This effort has been fruitful in dramatically increasing our understanding of all the benefits and sins of Ouroboros, but will not yield working code until the second half of 2018.
We deployed a rigorously built protocol for Byron, but one that does not enjoy a formal specification. There is always the chance we did something wrong, as with all software projects. There is always the chance we haven’t followed the intent of the scientists, despite our best engineering efforts. The broader point is that as our protocols increase in complexity, interdependence and with the use of more exotic cryptographic primitives, finding a balance will become more challenging. The saving grace we have is that many of our security assumptions are somewhat composable, we use great methods like Red-Black teams, peer review and formal specs, and using Haskell forces deeper conversations about intent.
The question of when to introduce smart contracts has become the most difficult issue of our roadmap. IOHK has brought some of the best minds from the programming language theory world, such as Professor Rosu and Professor Wadler, into the area of smart contracts. They have watched the world evolve from simple computers measuring performance in the megahertz and kilobytes of RAM to the internet age of big data, AI on demand and nearly unlimited processing power.
It’s an extraordinary honor and privilege to work with people with so much wisdom, hindsight and proven contributions to the fabric of computer science. Yet we also have the demands of Ethereum and the other systems that while lacking rigorous foundations have proven to attach a large following and much mindshare. We won’t accept the model of smart contracts is a closed matter and that these issues are now just a matter of optimization. We won’t accept that society is anywhere close to mass adoption of this new paradigm. It’s the beginning and it would be foolish to say Ethereum’s model is the one to back. Yet we acknowledge the need for something like that model. Therefore, we’ve decided to increase our allocation of resources towards two parallel tracks of research.
One is focused on fixing the issues that Ethereum’s hastily driven design process has yielded to the despair of those who have lost funds as a result. The other is focused on the ontology of smart contracts in general as well as different computational models that achieve similar ends without necessarily involving the new complexity or cost that Ethereum introduces. Professor Rosu’s team at the University of Illinois and the partnership with Runtime Verification is focused on the former effort. The work of Professor Wadler’s team is focused on the future and broader theory. We hope to establish more foundational research in the field of smart contracts, as Professor Aggelos Kiayias did with the GKL model and Ouroboros.
Next, there is the interplay between good partners like Bittrex, Ledger and others who are consumers of our APIs and have to deploy our software for thousands to use. The reality is that all interfaces are best guesses until they are used and then must change to conform with reality, not best intentions. We’ve already seen lots of room for improvement for our middleware layer, Daedalus’s design and also new features that would be helpful in making integration simpler and more cost effective. To this end, we’d like our first light clients to come from third parties instead of directly from IOHK, to force our documentation to improve and our software to become less arcane. Much of the effort towards Shelley (Cardano’s next major release) will be focused towards these types of improvements. They create a wonderful feedback loop that helps us make better decisions that benefit larger groups of users. Finally, the Cardano roadmap isn’t the property of IOHK, Cardano Foundation or Emurgo. It belongs to the community. When a cryptocurrency is new, it needs good shepherds to guide and steer, but we cannot allow the ecosystem to be ruled by a beneficent dictator or oligarchy.
This requirement creates some issues about scope. We have a clear idea of what needs to be done over the next 18 months to realize some of the technical requirements of Cardano from scalability to interoperability, but we cannot operate as a dictatorship pushing along and telling everyone to accept it. Cardano belongs to those who hold Ada. Thus we’ve decided to execute with three parallel paths. First, Shelley is our path to the full decentralization of Cardano. This must be done and we have decided to publish in full what Shelley entails. Next, there is the issue of Cardano Improvement Proposals (CIPs) and gathering consent for moving forward on whichever one is decided upon. We have invested a great deal of effort into building a solid voting system and will be releasing it for public review soon. This includes a standard for CIPs.
After Shelley, we will be proposing all changes to Cardano as CIPs and adding increasingly better democratic mechanisms to gather consent for these changes. The burden should be on us to inform and rally the community behind a direction. We cannot allow a technocracy to form alongside a cult of personality of the good leaders. Cardano must have the legitimacy of consent from its users. Finally, the roadmap needs to be often reviewed and updated. It cannot be a static document so we are going to run a monthly clock and update it frequently. We are also going to create a channel for people to proposal alternative roadmaps. As our users become more sophisticated and we accrue more enterprise partnerships, we fully expect divergent paths to be proposed and our hope is that they are better than our own. As a last thought, a cryptocurrency is only as good as the community behind it. We’ve been humbled by how amazing, patient and helpful our community has been. Our hope is that the roadmap is something we can build together over time and it becomes one of our strongest pillars.
To learn more about the project see the recent whiteboard video. Filmed on location at IOHK's Blockchain technology lab, Tokyo Institute of Technology - 東京工業大学
IOHK received both Bitcoin and Ada for its contract to work on the Cardano project. IOHK converted most of its Bitcoin at the time of receiving it to fiat in order to ensure project stability. With respect to IOHK's holdings of Ada, IOHK does not expect a need to liquidate any of its Ada to cover immediate costs related to the Cardano project until 2019. However, like most ventures in the cryptocurrency space, we have made certain payroll commitments in Ada to several IOHK personnel, contractors and third party firms.
Therefore, IOHK will voluntarily adopt the following vesting schedule for its Ada. A third of IOHK's Ada holdings will be immediately available to IOHK. A third will be made available after June 1st of 2018. The final third of IOHK's Ada will be made available after June 1st of 2019.
Charles Hoskinson will not receive any Ada until the final third of supply unlocks in June of 2019. When the computation layer of Cardano is released next year, IOHK will move its total Ada supply into a custom vesting contract to reflect the above policy.
In the spirit of full disclosure, IOHK's initial Ada address is: fa2d2a70c0b5fd45cb6c3989f02813061f9d27f15f30ecddd38780c59f413c62. We will make a follow-up statement when funds are moved to a custom vesting address.
As for Emurgo and the Cardano Foundation, we have requested both partners to make a similar statement about use of funds. As they are independent businesses, they will do so at a time and manner of their choosing.
Thank you all for being a part of Cardano
10 October 2017 3 mins read
Over two years ago IOHK joined a movement to build a truly unique collection of technology that married the best engineering principles with the dreams of scientists in far removed universities. It was a tremendously ambitious and complex project to grasp. Tens of millions of dollars would need to be gathered, long term roadmaps developed, research institutions established and properly managed as well as numerous entities staffed. In short, it was an insane project to attempt. Yet we attempted it.
Now there are well over 100 people working full time on the Cardano project, three research centers drafting peer reviewed papers, a legion of haskell developers pushing the limits of the language and three well capitalized entities with a mandate and funding to build Cardano until 2020 - IOHK, the Cardano Foundation and Emurgo.
It’s both unbelievable and humbling to see how far we have gone in such a short time. Cardano is literally evolving computer science from semantics based compilation to entirely new cryptographic protocols to formal verification of code. Cardano also managed to build an amazing community more than 10,000 strong in a slow and methodical way.
We launched the mainnet recently with very little fanfare and marketing. Rather it seems to be a small stop on a much longer and more elegant journey. While it’s certainly a challenging sojourn, I’m confident that we have come to know it and have developed the endurance to survive.
In reflection, I’ve been to over 30 countries since we started our journey. I’ve met thousands of people ranging from the bizarre to the saintly with a few notorious ones littered in between. The most remarkable thing so far has been experiencing the near unlimited excitement and youth regardless of where I went.
The world really does seem like it’s ready for a new financial system. It’s hard to say if Cardano can get us there, yet we aren’t alone any more. There’s now an army of some of the best throughout the world on this journey. Leaderless, inspired and brilliant, it’s an honor to be among them. I never believed I could be part of something like this movement.
Thank you all for being part of Cardano. Thank you for your patience when we have fallen. Thank you for your support and kind words. Thank you for your dreams. Now let’s get back to the road ahead. I’ve come to know this place for the first time.