Strongly stateless consensus mechanism with PCDs

# Strongly stateless consensus mechanism with PCDs This is a draft of a highly experimental idea. We would really appreciate if you left comments on the [Doc here](https://docs.google.com/document/d/1nKRsqE3ZZN5dlECX8Re_0fBmFNnNsyBCc7uessgx-uI/edit?usp=sharing) # Intro A large problem with Ethereum is state size, since all past transactions are stored, running a node can use up hundreds of GB of expensive (and fast) SSD space. As pointed out by [Moxie](https://moxie.org/2022/01/07/web3-first-impressions.html) this results in the current Node-as-a-Service model providers (Infura, Alchemy), which overall undermine the prospects of decentralisation. In order to allow anyone to run a small node on a phone or cheap computer, state storage needs to be solved while keeping a consensus mechanism in place. As previously written by [Dankrad](https://dankradfeist.de/ethereum/2021/02/14/why-stateless.html) [Feist](https://notes.ethereum.org/Yn_mwNa2SeeQHnKsRgekKg) and [Vitalik](https://notes.ethereum.org/@vbuterin/verkle_and_state_expiry_proposal), Ethereum is heading in the direction of being fully (weakly) stateless with [The Verge](https://twitter.com/VitalikButerin/status/1466411377107558402). However, this is still weakly stateless, meaning the block producers need to have the full state while the validator nodes can run stateless. Here we outline a strongly stateless consensus mechanism with the help of [Proof-Carrying Data](https://eprint.iacr.org/2012/095.pdf) (PCD) systems. The key insight is that iterated local consensus over a long enough stretch of time can stop the system from locally forking and losing its integrity, and hence can replace global consensus. # Technical details: **We are proposing a local rule set that can manage a Virtual Machine (VM) and can create consensus (does not allow forking). This rule also scales, allowing interactions between a large number of users.** For this we will use the well researched concept of PCD-s. As described in [this [BCCT12] paper](https://eprint.iacr.org/2012/095.pdf): “_Proof-carrying data (PCD) [CT10] is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely, while ensuring that the correctness of every intermediate state of the computation can be verified efficiently_.” Proving a concrete calculation is done with the help of ZKP-s. We propose to make the consensus of a VM a PCD computation. A PCD computation means that the computation is distributed across a large number of nodes, and each node will pass along both the result of their computations as well as the proof of these computations. Hence the ZKP-s are composed recursively as they are passed along from node to node. A PCD system at its foundation relies on ZKP-s, this means that on the computational level, all calculations are verifiable, since we prove the past computations. The fundamental problem here is that our system depends on non-deterministic, human inputs, which are prone to introduce forks if not dealt with appropriately. To understand non-deterministic inputs, think about this toy example: assuming there are no inputs to the nodes, meaning there are no human transactions, (only deterministic transactions originating in account abstractions), we could just ZKP the deterministic process; each node could prove how its state changes deterministically. But we also have inputs to the nodes. This means that a node can run multiple parallel ZKP-s based on different inputs, and pass these different ZKP-s and states to other nodes. This would allow forking, so our computations cannot be verified by ZKP-s alone. So for this system to satisfy our initial criteria, we need to make consensus a consequence of iterated local calculations of the system.** **These local calculations have to stop local forking. This requires that in our PCD nodes not only pass the proofs along a predetermined path, but dynamically interact with each other in small groups, to create local consensus about non-deterministic inputs. These small groups take the form of randomly chosen nodes verifying the state changes. We keep the public key of the potential Verifiers in the state of the Sender, and the Verifiers are drawn randomly but deterministically from this list. This makes the identity of the verifiers deterministic, so they can be included into the ZKP-s that go along with the state of each node. The next verifier will have to verify the next transaction of the spender. We note that the validity of the calculations are still verified with ZKP-s, the verifiers are only used to verify the choice of the non-deterministic inputs. However a fork can occur here if all the participants (Sender, Receiver and Verifier) are willing to participate in both forks. So we include the fact of this verification in the state of the Verifier, changing its state. So if there is a fork, the Verifier's state changes in two different ways. Then at the next transaction of the verifier, the meta Verifiers (Verifiers of the Verifier), also have to validate both forks, as they have to validate both states of the Verifier. This is harder to achieve. As the transaction spreads further and further, there will be more and more Meta Verifiers, so keeping up both forks will be impossible. To conclude we achieve global consensus through iterated local consensus. A random predetermined Verifier verifies the state changes, and broadcasts it to the further network implicitly within their states. This makes forking hard to maintain and hence very unlikely, as a large number of nodes would have to maintain two parallel states. ![](https://i.imgur.com/xTIOCwQ.jpg) Here in Transaction K, the Sender (S1) transacts with the Receiver (R1) which is verified by the three Verifiers (V1, V2, V3). In a future Transaction L, the Verifier V1 from a previous transaction transacts with R2 (and is verified by a new set of Verifiers). In another future Transaction M, the Verifier V4 transacts with R3 (and is verified by a new set of Verifiers). These transactions overall result in propagation of the original Transaction K being propagated across the network, as the Transaction K is included in the state of V1 etc. ## Links: * [https://dankradfeist.de/ethereum/2021/02/14/why-stateless.html](https://dankradfeist.de/ethereum/2021/02/14/why-stateless.html) * [https://notes.ethereum.org/Yn_mwNa2SeeQHnKsRgekKg](https://notes.ethereum.org/Yn_mwNa2SeeQHnKsRgekKg) * [https://notes.ethereum.org/@vbuterin/verkle_and_state_expiry_proposal](https://notes.ethereum.org/@vbuterin/verkle_and_state_expiry_proposal) * [BCCT12]: [Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data](https://eprint.iacr.org/2012/095.pdf) * [CT10]: [Proof-Carrying Data and Hearsay Arguments from Signature Cards](https://people.eecs.berkeley.edu/~alexch/docs/CT10.pdf)