Dhvani Patel

Provable State

Background

Previously, we saw how ZK programs add an additional output to a program which is a proof. Instead of input -> program -> output, we have input -> program -> (output, proof).

We essentially have the ability to prove the execution of programs while hiding the inputs. However, we have no notion of “state”. For example, I can write a program which decrements an object’s input durability by 1, but what is the thing that says that the canonical “axe” object is the one that was decremented and not the unused one.

To achieve this, we introduce the notion of provable state.

Anchored Data

Instead of simply “state”, we introduce an additional component which can be thought of as an anchor for that state/data, called commitment. So we have (state, commitment).

The simplest way to calculate a commitment is as the hash of the state. A commitment gives us provable state, as we can make the program proof include the hash of the state it operated on as one of the public statements.

For all participants in the system to agree on the same state of the world, we will need some protocol.

Example

This example uses a simple protocol where Ethereum is used as a public broadcast channel, one that also gives us a canonical order of things. Each user will have a client running that is listening to messages from Ethereum and building the global state on their computers.

Let’s first construct an axe object via a provable program that verifies we did some proof of work. The axe’s properties like durability will be private, but we will make public the hash of the created axe: 0x1234.

User A can then create a commitment to their axe by posting the hash to Ethereum Blobs. The state of the world is now:

Global:
created_objects: [ 0x1234 ]
consumed_objects: [ ]

Local to User A:
(axe_object, 0x1234) = {
    durability: 100
}

Later, let’s say user A uses the axe to chop some wood. To do this, the user will run a ChopWood program which will verify the new axe’s durability and output the hash of the input and output axe, plus the output wood.

ChopWood(old_axe, new_axe, wood){
  assert(old_axe.durability > 0);
  assert(new_axe.durability == old_axe.durability - 1);
  return (H(new_axe), H(old_axe), H(wood));
}

User A then commits to the new axe by posting the proof to Ethereum.

Other users will then accept this as a valid “transaction” or “state transition” if:

  • the proof verifies
  • H(old_axe) is currently in created_objects, but not in consumed_objects
  • H(new_axe) and H(wood) are in neither created_objects nor consumed_objects

The newly updated state will then be the following:

Global:
created_objects: [ 0x5678, 0x9012 ]
consumed_objects: [ 0x1234 ]

Local to User A:
(new_wood_object, 0x9012) {
    key: ""
}

(new_axe_object, 0x5678) {
    durability: 99
}

(old_axe_object, 0x1234) {
    durability: 100
}

We now have state!

You can see that other users only learn that user A has created two new objects and consumed another, but do not learn what those objects are.

User A could prove to other users they still have an axe which is valid (ie durability > 0) and would not be able to fool others by using an old axe object, because of the anchor, or commitment hash posted to Ethereum. They will also only be allowed to mine a maximum of 100 wood with a single axe. All clients will reject ChopWood updates (which may have a valid proof) where an axe was an input that was already consumed.

Note: Users need to agree on the protocol beforehand:

  • what programs they consider valid
  • what the global state data struct is
  • rules for how the global state updates based on the proof’s public statements

Programmable objects which would allow for a protocol to allow a dynamic range of programs is not covered in this document.

Protocol

We just saw a simple example of a user crafting an axe and then using it to chop some wood.

In the digital objects poc, the protocol also uses Ethereum Blobs and keeps track of created and consumed objects by verifying CommitCreation proofs.

In the blobs poc, the protocol uses Ethereum Blobs and keeps track of database updates by verifying the predicate proofs specified during the database creation. The specific DB predicate in the poc is an update predicate for a membership group. User A can request an update in User B’s private DB and verify that it was included.

We can do more complex things by changing the protocol run by the users. Here are 2 examples to illustrate:

Rubik’s Cube

  • User B causes User A to turn their Rubik’s cube, without User B learning what the Rubik’s cube looks like

The protocol has an inbox for each object and new commitments to an object must process any existing messages in its respective inbox.

User B can then send a TxProof with an action like “TurnLeft”, and User A can process it by posting a new Rubik’s cube hash with a public output being User B’s tx hash. The protocol will not allow any other updates to the Rubik’s cube. For eg, if User A tries to run TurnRight, the protocol will ignore the published new Rubik’s cube as invalid.

Car Battery

  • User B creates a car object which uses User A’s battery object: every time the car moves, the battery’s capacity decreases

The protocol allows objects to be tagged as being for other objects and enforce that it can’t be updated further until it is used.

User A can run a UseBattery program, which as one of its outputs, has the Car object hash it’s for. User B can then input in the latest battery hash, to run MoveCar. The protocol will not allow User A to continue using the battery or doing something else with it, until User B causes their car to move with this battery.

Note: In this example, User A might be positively incentivized to provide the battery (for eg, by some payment), but there may be cases in other applications where the user is not.

For example, User B hits User A’s shield with their sword object. Afterwards, both User B’s sword should lose durability and User A’s shield should lose hp. In this case, the protocol might need something like encrypted actions.

Queries

One component the protocol could include is a query engine. This would allow users to be able to get information about local state without revealing the state itself.

For example, User B could query all users in the system to see how many axes there are with durability 0, to get an idea of how many axes have been used up so far.

Besides aggregate statistics, this could be a discovery mechanism for users to link their objects. For example, User B rents out a battery from User A to move their car.

Conclusion

We achieve provable state in the system by using anchors for data and a protocol to update those anchors. ZK proofs are one part of the protocol to update the anchors as it lets us enforce valid state transitions, but the design space for the protocol is much wider.

Each protocol will have its own implications on censorship resistance, performance bottlenecks, upgradeability, guarantees, etc.

Like POD is a framework that makes it easy to generate provable computation for logical relations, is there a protocol design which covers a good portion of applications?

It’s also worth asking if this question is worth asking at this stage? Or if it makes sense to design protocols specific to applications, and let the general protocol design emerge.