Motivation
Proof of Necessary Work

Proof of Necessary Work
Using Proof of Work to Verify State
Assimakis Kattis & Joseph Bonneau
New York University

May 9th 2019

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work1 / 22

Motivation
Proof of Necessary WorkA Problem of Size
Bitcoin Scaling Limitations

Blockchain size increases linearly over time
New clients require lots of brandwith & computation to join
Inefficient : All new clients need to do the same verification
work to join the network from the beginning

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work2 / 22

Motivation
Proof of Necessary Work

Our ContributionsProof of Necessary Work

Proof of Necessary Work : Use PoW to verify transactions
1

Allow light clients to verify state with minimal processing

2

Generate proofs ‘for free’ through PoWAssimakis Kattis & Joseph Bonneau

Proof of Necessary Work3 / 22

Motivation
Proof of Necessary Work

Design Challenge
Proofs of State Validity

Important results from CS Theory :1

There exist ‘small’ proofs for any NP statement

2

Such proofs can verify previous proofs efficiently

Need proofs of state validity that :1

can verify correctness of the whole chain

2are small enough to add to the blockchain

3

can be checked with minimal resources

Idea : Use recursive SNARKs !

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work4 / 22

Motivation
Proof of Necessary Work

Proofs of State Validity
Succinct Blockchain Instantiation

Bitcoin naturally fits Incrementally Verifiable Computation
Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

5 / 22

Motivation
Proof of Necessary Work

Prototype Design

Account-based prototype with simple payment functionality
Similar but not equivalent to Bitcoin :1No script or UTXOs

2

Doesn’t support MULTISIG or arbitrary transaction types

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

6 / 22

Motivation
Proof of Necessary Work

Proofs of State Validity
Implementation Results

Succinct blockchain prototype results

Benchmark : AWS ra5.2xlarge with 8 cores and 64GB of RAM

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

7 / 22

Motivation
Proof of Necessary Work

What did we achieve ?

Our prototype :produces block headers of size < 500 bytes for any numberof transactions per blockallows stateless clients to verify a block in < 60ms
can achieve throughput of 100 tx/block using libsnark
Problem : The proofs take a long time to generate
Idea : Create them as part of the PoW process !

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

8 / 22

Motivation
Proof of Necessary Work

PoW from Proof Generation
Initial Approach

Generate π and accept if H(π) ≤ d, repeat otherwise
Need to add a random nonce to the proof every iteration
Nonce is randomly sampled, changing π
Probability of success is exponentially distributed

Problem : We can change n without recomputing all of π
Process favors returns to scale, leading to centralization !

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

9 / 22Motivation
Proof of Necessary Work

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

10 / 22

Motivation
Proof of Necessary Work

Modelling Proof Generation

Need to ensure our predicate is ‘hard’ to solve in general
We model this using a ‘hardness’ oracle O
O simulates hard computations used to generate π
Prover has access to O but can reuse previous information
In current succinct SNARK implementations, O provides accessto modular exponentiation in some group G
Reduces to hardness in the Generic Group Model (GGM) !

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

11 / 22Motivation
Proof of Necessary Work

Formalizing the ModelDefinition (-Hardness)
For ` ∈ poly(λ) and length λ inputs, f O is -hard if ∀A
performing less than (1 − )N ` queries to oracle O, where N
number of queries required for one evaluation of f O , thefollowing is negligible in λ :
∀i ∈ [`], πi = f O (ai ){πi , ai }`i=1 ← A(1λ )Pr∀i, j ∈ [`], ai 6= aj ⇔ i 6= j
Intuition : A large prover only gets an  advantage fromprevious computation when generating proofs

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

12 / 22

Motivation
Proof of Necessary Work

Committing to the Nonce
Leveling the Playing Field

We hope to solve this by committing to the nonce in the proof
Valid blocks now a (sensitive) function of n
Changing any input leads to an invalid configuration
Prevents previous proofs from inducing speedups
Computing proofs with random n prevents returns to scale
Result : Miners have to compute the whole proof

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

13 / 22

Motivation
Proof of Necessary Work

Adding Nonce to State
Altering Merkle Computations

Account-based models keep state in a Merkle tree :1

Checks old Merkle paths

2

Computes new Merkle paths

3

Checks that signature and amounts are valid

Idea #1 : Link state and nonce through a ‘seed’ parameter :ρ = H(n|state). Requires only one verification of a PRF H
Result : Altering any part of the input means a new valid ρ isrequired, which is unpredictable by the security of H

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

14 / 22

Motivation
Proof of Necessary Work

Creating Hard Predicates

State verification happens without the seed. Most computation(∼ 97%) in current account-based models verify Merkle paths
Problem : This only requires access to state ! An adversary canreuse work as ρ doesn’t alter the vast majority of computation
Goal : Alter predicate to embed ρ in the verification process

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

15 / 22

Motivation
Proof of Necessary Work

Strawman : Insert n in every updated leaf. New Merkle paths
then change unpredictably as a function of the nonce
If we could inject our nonce in all Merkle paths, would be done
Problem : We only alter half of them ! Gives an  ≈ 1/2

New Idea : Modify hash function by ‘cloaking’ it with ρDesign Challenge : Modify our hash function to use ρ ‘almost
everywhere’, while outputting the same result as before

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

16 / 22

Motivation
Proof of Necessary Work

Cloaking the Pedersen Hash

For generators {gi }ni=1 in Z∗p , an n-bit Pedersen hash is :nYH(x) =gixi where xi the i-th bit of x
i=10Idea # 2 : Compute H(ρ) and then calculate H (x ⊕ ρ, H(ρ))
Can compute H(ρ) once per block. We can then use this with a00transformation H for which H (x ⊕ ρ, , H(ρ)) = H(x) for any x
Efficiency : Need to verify the XOR input. Adds O(n)overhead for a ∼ 20% increase in proving time per H circuit

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

17 / 22

Motivation
Proof of Necessary Work

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

18 / 22

Motivation
Proof of Necessary Work

Putting it all together

We demonstrate how to cloak predicates with a nonce n,making information reuse impossible ≈ 3% with overhead ∼ 20% per block in our predicate when
implementing the previous ideas w/o optimization
For our 20 tx predicate, this means  ≥ 0.3% if using SHA
 ≥ |CPRF |/|CBlock | becomes our lower-bound

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

19 / 22

Motivation
Proof of Necessary Work

Proof Chains
Improving System Throughput

Discarding previous proofs is also wasteful - can we do better ?
We propose ‘Proof Chains’, an extension to PoNW that :requires miners to build on top of previous proofs
submits all proofs in the chain when difficulty is satisfied

Result : Throughput increase ‘for free’ in our implementation

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

20 / 22

Motivation
Proof of Necessary Work

Related Work

An ideal proof system would :1

require verifier succinctness (for efficient IVC),

2

also be trustless (no trusted setup),3

and quantum-resistant.

Recent work is rapidly approaching these capabilities
Since our modifications are on the predicate layer, such
improvements are complementary to our approach
Remark : Our design uses IVC as a black box. Can switch inany proof system that does IVC with the same guarantees

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

21 / 22

Motivation
Proof of Necessary Work

Future Work

We identify various areas for future work :Generalize to arbitrary proof systems
Design cloaking properties for other (faster) hash functions
Extend to full Bitcoin functionality (soft fork ?)Contact : kattis@cs.nyu.edu

Assimakis Kattis & Joseph Bonneau

Proof of Necessary Work

22 / 22