Kimono — trustless secret sharing using time-locks on Ethereum

The first version of the Kimono protocol was designed and built at ETHBuenosAires in May 2018 by Feridun Mert Celebi, Paul Fletcher-Hill, Graham Kaemmer, and Daniel Que.

Introduction

A time-lock is a way of securing a file or message until a certain time in the future. It’s an important concept for whistle-blowers, document embargoes, and blind auctions. But time-locking in practice has been difficult, especially on public blockchains like Ethereum. Existing solutions include time-lock encryption and commit and reveal schemes, though they all have trade-offs.

Time-lock encryption

Time-lock encryption is a novel cryptographic scheme where data is encrypted so that it can only be revealed by running a decryption algorithm on it N times synchronously. As long as the time it takes to run one decryption cycle doesn’t change significantly, it’s possible to time-lock data for varying lengths of time by adjusting the number of decrypt cycles needed to fully reveal it.

The downside with time-lock encryption is that it is computationally intensive, requiring significant resources to unlock especially long time-locks. Furthermore, the time-lock accuracy depends on when the decryption process began — time-lock encrypting data for a year only works if the decryption process starts immediately.

Commit and reveal

Another option for effectively time-locking data is to share the data in encrypted form immediately and publish the decryption key once the time-lock is complete. While this scheme is far more resource efficient than time-lock encryption, it requires additional work for the creator of the time-lock. And in situations where the owner of time-locked data is uncertain if they will be able to take further action in the future — consider dead man’s switches or whistle-blowers — the extra step may defeat the purpose of a time-lock entirely.

Trusted commit and reveal

One easy way of preventing the owner of time-locked data from having to post the secret key themselves is to give the key to a trusted third party. Trusted commit and reveal may be the simplest construction of the three, but it requires the creator of a time-lock to put considerable trust in a third party. Trusting a third party may be okay for some situations, like basic banking. But if a regulator or powerful entity wants to prevent information from being made public, a trusted party for releasing secret keys may become a target and point of failure.

Trustless secret sharing with Kimono

Kimono is a protocol that aims to accomplish time-locking without spending significant compute resources, without requiring multiple actions by the creator of the time-lock, and without trusting a single third party with the process. The platform uses a commit and reveal scheme but distributes the secret for each piece of data across a network of peers who share it with the public only once the time-lock is complete.

The platform has four stages, which we’ll discuss in more detail below:

  1. Secret splitting
  2. Secret fragment distribution
  3. Secret fragment publishing
  4. Secret reconstruction

Secret splitting

Kimono relies on an algorithm called Shamir’s Secret Sharing, which makes it possible to create N fragments from a secret such that any K of the fragments can reconstruct the original secret. A simple way of understanding Shamir’s is to think of a secret as a polynomial (specifically the constant in a polynomial). For a polynomial of degree 1 (i.e. a line), you can describe the entire line from any two points. Similarly, a parabola can be described by three points, a cubic function by four points, etc. Shamir’s Secret Sharing applies the concept to secrets, such that any K fragments of a secret (i.e. points) can reconstruct the original secret (i.e. the polynomial).

In Kimono, we call the data that is being time-locked the message. And the user who creates the message is the creator. To begin, a creator encrypts a message with a secret key that only they know. Then they use Shamir’s scheme to create N fragments of that secret, where any K fragments can reconstruct the secret. The specific values of N and K are up to the user.

Secret fragment distribution

Kimono’s goal is to distribute the responsibility of managing secrets to a network of trustless peers. We call these peers revealers. Because the secret is split into fragments using Shamir’s algorithm, no single revealer (or group of K — 1 or fewer revealers) can reconstruct the secret.

Kimono uses IPFS to distribute the secret fragments to revealers. Because IPFS is public, Kimono has the message creator encrypt each secret fragment with the public key of the revealers they are giving work to. The collection of encrypted fragments is then published to IPFS and linked to from the Kimono smart contract. The full list of data committed to Ethereum with a Kimono message is below:

Secret fragment publishing

Nothing happens with a message until the revealBlock is added to Ethereum (i.e. when the time-lock is complete). At that point, the revealers who were assigned fragments of the secret when the message was created race to publish the decrypted version of their secret fragment to the Kimono smart contract. The protocol is designed to incentivize revealers not just to reveal their fragments after the time-lock but to reveal their fragments as soon as possible after the time-lock.

Secret reconstruction

A second kind of process exists in the Kimono network called a combiner. A combiner watches for secret fragments to be published to a message and tries to reconstruct the secret given the available fragments. Once the secret has been reconstructed, the original data is public — anyone can use the secret to decrypt the message in IPFS.

Because each secret can be reconstructed from a subset of its fragments (K fragments out of N), not all fragments will be used for reconstruction, which is the basis for the game the protocol manufactures between revealers. The creator’s reward is split between the combiner and the contributing revealers — specifically the revealers who published their secret fragments before the combiner reconstructs the secret. The revealers are incentivized to publish their fragments first, and the combiner is incentivized to reconstruct the secret as early as possible — both to maximize their split of the reward. The reward will be split among at least K + 1 and at most N + 1 peers.

Each message has both a revealBlock and a revealPeriod, which is represented as a number of blocks after the revealBlock. If a revealer doesn’t post their decrypted secret fragment by the end of the reveal period, their stake can be taken by the creator. So even if revealers are not rewarded for posting their fragments before the secret is reconstructed, they are still incentivized to post their fragment, because otherwise they run the risk of having their stake taken.

Robustness

There are three primary attack vectors against Kimono: (1) rogue revealers posting bogus or incomplete secret fragments, (2) revealers posting fragments prematurely, and (3) off-chain collusion between revealers. The first two are solved in a straightforward way, and the third attack can be mitigated by a strategy we call tattling.

To prevent revealers or combiners from submitting incorrect or fraudulent secret fragments or reconstructed secrets, the Kimono smart contract stores hashes of all secret fragments and a hash of the original secret. If the revealer or combiner post anything that when hashed does not match the hash stored in the contract, it is not accepted. Similarly, the contract will not let revealers or combiners post data to a message before the time-lock is complete.

As for off-chain collusion, Kimono uses a strategy we call tattling to discourage collusion. Inspired by the prisoner’s dilemma, Kimono lets anyone steal the stake of any revealer by proving they have that revealer’s decrypted secret fragment. Collusion would require peers to share their secret fragments with each other in order to reconstruct the secret, so by colluding they directly put their stake at risk.

Use cases

Time-locking is a specific yet useful primitive for decentralized networks. Whistle-blowers can use time-locks as insurance policies, publishing information that they know will eventually be revealed. Journalists and media companies can use time-locks to embargo information or stories until specific times in the future. Families can use time-locks to guarantee that access to trusts are shared only at specific times. Secret voting can be done via time-locks to be revealed on election day or at specific times. And entertainment companies could structure time-based media like comic strips or weekly TV shows as time-locks.

Future work

We started thinking about the problem of automatic time-locking in the context of another project, one that has yet to be announced. The project has to do with building markets for yet-to-be-revealed information and will make use of Kimono’s secret sharing network.

More information about the project will be revealed soon. In fact, it’s already published on Kimono (on Rinkeby): https://kimono.network/1130418214479365380170725988390953298054427900348419403539. Stay tuned, because the message will be revealed after block 2405701.

Links

Kimono is live and deployed to the Rinkeby test network: https://kimono.network

Kimono is open-source on Github: https://github.com/hillstreetlabs/kimono

Feridun Mert Celebi, Paul Fletcher-Hill, Graham Kaemmer, and Daniel Que contributed to the project at ETHBuenosAires.

If you’re interested in collaborating with us on Kimono or building on top of it, get in touch on twitter or open an issue on Github.