1 of 63

Zero-Knowledge Proof with Fully Distributed Proof Generation

Tianyi Liu

Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Dawn Song

1

2 of 63

Background and motivation

2

3 of 63

Zero-knowledge Proof

3

The verifier

The prover

Yes or no

4 of 63

Zero-knowledge Proof

4

The verifier

The prover

Yes or no

x

+

0

1

0

witness

5 of 63

Zero-knowledge Proof

5

The verifier

The prover

Yes or no

x

+

0

1

0

witness

Completeness: if correct, V accepts the proof with high probability.
Soundness: if wrong, V rejects the proof except for negligible probability.

Proof

Zero-knowledge

6 of 63

Application: ZK-Rollups and zkEVM

6

Block 1

Block 2

Block 3

Tx 1	Alice -> Bob, 5
Tx 2	Bob -> Cathy, 5
Tx 3	Cathy -> Alice, 3
Tx 4	Cathy -> Alice, 1

Tx 1	Alice -> Bob, 5
Tx 2	Bob -> Cathy, 5
Tx 3	Cathy -> Alice, 3
Tx 4	Cathy -> Alice, 1

Ledger
Alice	5
Bob	0
Cathy	0

Ledger
Alice	0
Bob	5
Cathy	0

Ledger
Alice	0
Bob	0
Cathy	5

Ledger
Alice	3
Bob	0
Cathy	2

Ledger
Alice	4
Bob	0
Cathy	1

Tx 1

Tx 2

Tx 3

Tx 4

7 of 63

Application: ZK-Rollups and zkEVM

7

Block 1

Block 2

Block 3

Tx 1	Alice -> Bob, 5
Tx 2	Bob -> Cathy, 5
Tx 3	Cathy -> Alice, 3
Tx 4	Cathy -> Alice, 1

Tx 1	Alice -> Bob, 5
Tx 2	Bob -> Cathy, 5
Tx 3	Cathy -> Alice, 3
Tx 4	Cathy -> Alice, 1

Ledger
Alice	5
Bob	0
Cathy	0

Ledger
Alice	4
Bob	0
Cathy	1

Verify proof π, update the state

∆ledger: Alice 4, Bob 0, Cathy 1

Proof: π

(zero-knowledge) proof

Improve the scalability

8 of 63

Motivation

8

9 of 63

Motivation

9

Current solution: Prover based on Plonk with customized gate and lookup argument

10 of 63

Motivation

10

Challenge: large memory usage

(100+GB for 64 TXs, in our experiment)

Current solution: Prover based on Plonk with customized gates and lookup argument

11 of 63

Motivation

11

Challenge: large memory usage

(100+GB for 64 TXs, in our experiment)

Our solution: fully distributed scheme based on Plonk

Current solution: Prover based on Plonk with customized gate and lookup argument

12 of 63

Brief introduction of Plonk

12

13 of 63

Constraint system for CIRCUIT-SAT

13

x

+

1

2

0

2

7

1

9

6

54

3

||

5

Circuit or Input

Witness

Arithmetic Circuit

14 of 63

Constraint system for CIRCUIT-SAT

14

x

+

1

2

0

2

7

1

9

6

54

3

||

5


0

x

Circuit or Input

Witness

Arithmetic Circuit

15 of 63

Constraint system for CIRCUIT-SAT

15

x

+

1

2

0

2

7

1

9

6

54

3

||

5


0
1
2

+

x

Circuit or Input

Witness

Arithmetic Circuit

16 of 63

Constraint system for CIRCUIT-SAT

16

x

+

1

2

0

2

7

1

9

6

54

3

||

5


0
1
2
3

+

x

=5

Circuit or Input

Witness

Arithmetic Circuit

17 of 63

Constraint system for CIRCUIT-SAT

17

x

+

1

2

0

2

7

1

9

6

54

3

||

5


0
1
2
3

+

x

=5

Circuit or Input

Witness

Arithmetic Circuit

18 of 63

Vector constraint system

18

The verifier

The prover

19 of 63

Vector constraint system

19

The verifier

The prover

20 of 63

Polynomial constraint system

20

21 of 63

Polynomial constraint system

21

22 of 63

Polynomial constraint system

22

23 of 63

Polynomial constraint system

23

In Witness

24 of 63

Verify polynomial identity

24

25 of 63

Verify polynomial identity

25

x

26 of 63

Verify polynomial identity

26

x

Schwartz-Zipple lemma

completeness

soundness

27 of 63

Remaining problem

27

x

+

1

2

0

2

7

1

9

6

54

3

||

5


0
1
2
3

28 of 63

Remaining problem

28

x

+

1

2

0

2

7

1

9

6

54

3

||

5


0
1
2
3

Permutation argument

29 of 63

The logic of the proof scheme

29

Computation model

A set of polynomial identities

x

+

1

2

0

2

7

1

9

6

54

3

||

5

30 of 63

Constant round polynomial Interactive oracle proof (IOP)�

30

The verifier

The prover

31 of 63

Constant round polynomial Interactive oracle proof (IOP)�

31

The verifier

The prover

32 of 63

Constant round polynomial Interactive oracle proof (IOP)�

32

The verifier

The prover

33 of 63

Constant round polynomial Interactive oracle proof (IOP)�

33

The verifier

The prover

34 of 63

Constant round polynomial Interactive oracle proof (IOP)�

34

The verifier

The prover

Polynomial commitment

35 of 63

Instantiate polynomial oracles: � -- polynomial commitment

35

The verifier

The prover

Properties:

Hiding
Binding

36 of 63

KZG polynomial commitment � based on DLog and qSDH assumption

36

The verifier

The prover

Properties:

Hiding from DLog
Binding from qSDH

37 of 63

Complexity

37

38 of 63

Fully distributed Plonk

38

39 of 63

Generate proof in a distributed way

39

+

x

=5

Directly distribute computation into multiple machines?

40 of 63

Usage of NTT in the proving process

40

Polynomial interpolation

Polynomial arithmetic operations

41 of 63

Difficulty of distributed NTT

41

output

input

42 of 63

Difficulty of distributed NTT

42

output

input

transpose

Large communication!

43 of 63

Partition circuit if highly parallelable

43

+

x

=5

44 of 63

Partition circuit if highly parallelable

44

Part 1

Part 2

+

x

=5

45 of 63

Partition circuit if highly parallelable

45

Part 1

Part 2

+

x

=5

Half size

46 of 63

If generating proof for each part…

46

Part 1

Part 2

+

x

=5

47 of 63

If generating proof for each part…

47

Part 1

Part 2

+

x

=5

Verifier cost will increase as #parts grows

48 of 63