The Tributary Framework

Serai is a decentralized exchange which uses threshold signatures to sign transactions on external networks such as Bitcoin, Ethereum, and Monero. In order for its validators to achieve agreement over these networks, and to sign signatures, two primitives were effectively required:

  • Verifiable Broadcast: When a validator sends a message to every other validator, all of the other validators agree on the message which was sent.
  • Agreement: When given a choice between two options, the validators can come to consensus on a single choice to move forward with.

Such protocols are extensively discussed in literature, for a variety of specific and general purposes. Here, we want to focus on the exact scenarios Serai has and give a brief overview, as will contextualize our decision in the end.

Serai's own Distributed Key Generation protocol uses cryptographic proofs to ensure each validator only has a single possible valid message. This simplifies its "Verifiable Broadcast" step from,

  • Did we receive a message?
  • Did everyone else receive a message?
  • Did we all receive the same message?

to solely "Did I receive a message?". If the message locally received is valid, then either:

  • Everyone else has yet to receive a message, but I can forward the message I received to them so they have also received the message
  • Everyone else has received a message, and by definition, it has to be the same message I received

However, Serai's key generation protocol still requires agreement.

In order to ensure that Serai can continue functioning even when some validators are offline, Serai's signing protocols only require a threshold of validators to participate to produce a signature. Similarly, when generating a key, we only require a threshold of validators participate. However, while each validator has only a single message they may participate with, the resulting list of messages is still dependent on which validators sent messages. A key generated by Alice and Bob will look different from one generated by Alice and Charlie, even if Alice sent the same message regardless of which validators participated in the end.

This is traditionally referred to as the Asynchronous Common Subset problem. Here, Serai's validators want to agree on a common set of validators that everyone agrees sent a valid message to participate in the key generation protocol. The "asynchronous" part refers to operating over an asynchronous network, where messages may be arbitrarily delayed or arrive in any order, and we do not assume that the internet 'just works'.

Note Serai's key generation protocol can actually be run without a protocol for agreement, but only if it requires everyone participate in key generation (and is not tolerant to anyone being offline). While this is not how our key generation protocol is used within Serai, it's a really amazing feature for how it allows avoiding this problem and discussion entirely.

For signing, Serai makes use of the FROST signing protocol, as popular. FROST may fail to produce a signature if a validator goes offline however, and practically requires a wrapper which retries as necessary to guarantee the output of a signature. One such protocol was ROAST which designated a 'leader' for each signing attempt. Instead of validators sending their signing messages to all other validators, the signing messages are solely sent to the leader. Then, the leader decides:

  • Who is participating in the signing attempt
  • The message each participant sent, which is now the message everyone will use

Instead of using decentralized protocols for verifiable broadcast and agreement, declaring a single participant as the leader allows achieving these decisions immediately, by decree of the leader. However, if the leader goes offline, is compromised, malicious, or otherwise faulty, they're able to make bad decisions which doom the signing attempt to fail. ROAST solves this by declaring several leaders and simultaneously trying a variety of signing attempts until at least one succeeds.

For Serai, these two problems together would imply we need:

  • An Asynchronous Common Subset protocol for key generation
  • An implementation of ROAST for signing

However, Serai also needs to ensure its validators agree on the latest blocks and when they occurred with regards to other events within the system. This would suggest we'd also need yet another solution.

To avoid this complexity, Serai has a single solution: a tributary.

A tributary is a blockchain. With each new set of validators, they each spawn their own tributary. This provides an ordered, append-only view of data, as communicated between and participated in by the validators. We now just require each validator sync their tributary to receive the messages sent by other validators, the tributary providing when the messages were sent as well. From there, we can define the participants in a subprotocol simply as whoever is first to send a message to participate, and agree on the results of the subprotocol by witnessing it happen on our mutual data layer.

The tributary's namesake is from a watershed, where a tributary is a body of water which feeds into a larger river. Each individual tributary feeds into the Serai network as a whole, contributing to its flow.

As the tributary is a blockchain, it still needs a consensus mechanism. The point of the tributary is we implement one generic, competent solution for consensus, before applying it to all of our needs in a portable way. At this time, our tributaries rely upon Tendermint consensus, as we've prior written about.

On top of this implementation of the consensus itself, we have yet another library: the Tributary Framework. This is a basic, flexible definition of a blockchain intended to be embedded within a larger application. It is not intended to be the future of blockchain, with infinite scalability. It is for when consensus is the means, not the end, providing a well-defined abstract machine for data. Specifically, it's modular to the literal 'transaction' type (which defines how data is communicated) and the peer-to-peer network (allowing reusing however applications already communicate with each other).

We built the Tributary Framework as a public good and hope it may be of interest to other developers, projects, and applications. The current code should be extensively documented and friendly to pick up. All of Serai's specific usage, deciding on who was first to participate in key generation and signing attempts, happens within Serai's own libraries, via its own transaction type, and not within the framework itself.

To emphasize why we built it, it is not that one cannot simply shunt signing attempts onto a peer-to-peer network and see if they appear to eventually output a signature. Doing so may invalidate the signing protocol's security proofs, if it assumed an synchronous (ideal) network however. Not only did Serai wish to provide an effectively ideal network (under the trust assumptions of its consensus algorithm) to ensure we could argue our formal security, we wanted to ensure this actually worked. If some validators intermittently go offline, that would not be an excuse for the Serai protocol to halt. It must be fault tolerant, able to run even in the presence of some faulty validators. It also must be autonomous, where if the network is degraded, users do not look to some leader to publish a new configuration, or change some settings, or to write a more competent solution. To do so would leave Serai chained to its developers, requiring their regular involvement and active maintenance for the project's mere survival.

This philosophy shapes all of Serai's development. The project has aimed for years to develop the necessary infrastructure, competently, to enable a decentralized exchange. One without enshrined admins, one which won't require weekly patches, and one which can be trusted to be a reliable solution to swap coins without relying on opaque, centralized exchanges.

The Tributary Framework has existed for years within Serai's codebase, but became the least maintained (and worst off) part of it. With our recent work, it's been built into a solution we're proud of and are happy to announce like this. While this was accomplished via rewriting large swaths of it, despite its bones being in the right place, we are happy to say we don't expect any more such rewrites moving forward. The emphasis for Serai has already been on reviewing and testing its code, leading up to its next testnet, where the outstanding libraries should be much more straightforward and in line with that stated goal.

If you would like to keep an eye, we welcome you to follow Serai on Twitter, or join our community via Discord or Matrix.