State encryption


#1

Unlike any other blockchain, where user-supplied arguments and the state are fully public, in Enigma, these can be encrypted at all times. An important question is how to efficiently maintain an encrypted state, communicate it to other nodes - and do all that without leaking any side-channel information.

Some background: essentially, a blockchain (or more specifically, a single secret contract) state can be formalized as a dictionary S, parameterized at time t. In the beginning of time (contract creation) the state is defined as S(0). At any time t, the state is defined as S(t). Therefore, the current time T is associated with the state S(T).

As mentioned, in Enigma we wish to allow having an encrypted state. The trivial, and most secure solution to this is to encrypt the state as a single unit. This means that at time t, the state is stored as E(S(t)), where E() denotes an encryption function (or a secret sharing scheme in MPC). This is the most secure option, because nothing leaks about the information stored inside the state, nor can an outside observer learn anything about what part of the state was altered. On the other hand, efficiency suffers, since even a change of a single bit in a large state (think 1GB+), forces nodes to broadcast the complete new state to the network.

Another option is to only encrypt the internal values in the state. This gets complicated (think nesting), but would be very efficient. Only values that are encrypted need to be updated across state updates. It does, however, leak perfect information about which values have been updated - it’s just that those values do not leak to the user.

We can treat these two options as extremes on a spectrum between efficiency and (meta)-data leakage. In between, there are other options, such as -

  1. Splitting the memory into equal chunks (e.g., 1MB ones). Now you only need to update a constant amount of chunks per constant-sized item, which still leaks the identity of the chunks, but generally minimizes the leakage. To improve on this, Moria proposed to permute the chunks after every operation (or every several operations). This gets us closer to ORAM solutions which is the type of science that deals with memory-traces leakage.

  2. ‘Delta-scheme’: Instead of encrypting the full state in every round, only encrypt the delta. Then S(t) = S(0) + dS(1) ... dS(t). This solution leaks much less data (although it still leaks some information - such as how big the update was), and minimizes communication and storage. The biggest disadvantage of this technique, is that it requires a node to fully reconstruct the state before every computation.

There are many other techniques that can improve working with an encrypted state. This is a unique aspect that Enigma needs to deal with that no other blockchain solution has to think about (because they just ignore privacy ;)). For now, the best trade-off seems to be working with the Delta-scheme.


Permissioned queries