This repository was archived by the owner on Apr 18, 2025. It is now read-only.
forked from privacy-scaling-explorations/zkevm-circuits
-
Notifications
You must be signed in to change notification settings - Fork 390
/
Copy pathlib.rs
237 lines (233 loc) · 10.4 KB
/
lib.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
//! 
//! Bus-Mapping is a crate designed to parse EVM execution traces and manipulate
//! all of the data they provide in order to obtain structured witness inputs
//! for the EVM Proof and the State Proof.
//!
//! ## Introduction
//! At the moment every node on ethereum has to validate every transaction in
//! the ethereum virtual machine. This means that every transaction adds work
//! that everyone needs to do to verify Ethereum’s history. Worse still is that
//! each transaction needs to be verified by every new node. Which means the
//! amount of work a new node needs to do the sync the network is growing
//! constantly. We want to build a proof of validity for the Ethereum blocks to
//! avoid this.
//!
//! This means making a proof of validity for the EVM + state reads / writes +
//! signatures.
//! To simplify we separate our proofs into two components.
//!
//! - State proof: State/memory/stack ops have been performed correctly. This
//! does not check if the correct location has been read/written. We allow our
//! prover to pick any location here and in the EVM proof confirm it is correct.
//!
//! - EVM proof: This checks that the correct opcode is called at the correct
//! time. It checks the validity of these opcodes. It also confirms that for
//! each of these opcodes the state proof performed the correct operation.
//!
//! Only after verifying both proofs are we confident that that Ethereum block
//! is executed correctly.
//!
//! ## Bus Mapping
//! The goal of this crate is to serve as:
//! - A parsing lib for EVM execution traces.
//! - A way to infer some witness data that can only be constructed once we've analyzed the full
//! exec trace.
//! - An easy interface to collect all of the data to witness into the circuits and witness it with
//! few function calls.
//!
//! ## Parsing
//! Provided a JSON file or a JSON as a stream of bytes, which contains an
//! execution trace from an EVM, you can parse it and construct an
//! `ExecutionTrace` instance from it. That will automatically fill all of the
//! bus-mapping instances of each
//! [`GethExecStep`](eth_types::GethExecStep). Then the
//! [`CircuitInputBuilder`](crate::circuit_input_builder::CircuitInputBuilder)
//! will fill in an
//! [`OperationContainer`](crate::operation::container::OperationContainer)
//! with all of the Memory, Stack and Storage ops performed
//! by the provided trace.
//!
//! ```rust, no_run
//! use bus_mapping::{Error, mock::BlockData};
//! use eth_types::{
//! self, address, Address, Word, Hash, U64, GethExecTrace, GethExecStep, geth_types::GethData, bytecode, state_db::{self, StateDB, CodeDB}
//! };
//! use mock::test_ctx::{TestContext, helpers::*};
//! use eth_types::evm_types::Gas;
//! use bus_mapping::circuit_input_builder::{Block, CircuitInputBuilder};
//!
//! let input_trace = r#"
//! [
//! {
//! "pc": 5,
//! "op": "PUSH1",
//! "gas": 82,
//! "gasCost": 3,
//! "refund": 0,
//! "depth": 1,
//! "stack": [],
//! "memory": [
//! "0000000000000000000000000000000000000000000000000000000000000000",
//! "0000000000000000000000000000000000000000000000000000000000000000",
//! "0000000000000000000000000000000000000000000000000000000000000080"
//! ]
//! },
//! {
//! "pc": 7,
//! "op": "MLOAD",
//! "gas": 79,
//! "gasCost": 3,
//! "refund": 0,
//! "depth": 1,
//! "stack": [
//! "40"
//! ],
//! "memory": [
//! "0000000000000000000000000000000000000000000000000000000000000000",
//! "0000000000000000000000000000000000000000000000000000000000000000",
//! "0000000000000000000000000000000000000000000000000000000000000080"
//! ]
//! },
//! {
//! "pc": 8,
//! "op": "STOP",
//! "gas": 76,
//! "gasCost": 0,
//! "refund": 0,
//! "depth": 1,
//! "stack": [
//! "80"
//! ],
//! "memory": [
//! "0000000000000000000000000000000000000000000000000000000000000000",
//! "0000000000000000000000000000000000000000000000000000000000000000",
//! "0000000000000000000000000000000000000000000000000000000000000080"
//! ]
//! }
//! ]
//! "#;
//!
//! // We use the [`TestContext`] struct to mock a block.
//! let code = bytecode! {
//! // Write 0x6f to storage slot 0
//! PUSH1(0x6fu64)
//! PUSH1(0x00u64)
//! SSTORE
//! // Load storage slot 0
//! PUSH1(0x00u64)
//! SLOAD
//! STOP
//! };
//!
//! // Get the execution steps from the external tracer
//! let block: GethData = TestContext::<2, 1>::new(
//! None,
//! account_0_code_account_1_no_code(code),
//! tx_from_1_to_0,
//! |block, _tx| block.number(0xcafeu64),
//! )
//! .unwrap()
//! .into();
//!
//! // Here we update the circuit input with the data from the transaction trace.
//! let mut builder = BlockData::new_from_geth_data(block.clone()).new_circuit_input_builder();
//! builder
//! .handle_block(&block.eth_block, &block.geth_traces)
//! .unwrap();
//!
//! let geth_steps: Vec<GethExecStep> = serde_json::from_str(input_trace).unwrap();
//!
//! // Get an ordered vector with all of the Stack operations of this trace.
//! let stack_ops = builder.block.container.sorted_stack();
//!
//! // You can also iterate over the steps of the trace and witness the EVM Proof.
//! builder.block.txs()[0].steps().iter();
//! ```
//!
//! Assume we have the following trace:
//! ```text,ignore
//! pc op stack (top -> down) memory
//! -- -------------- ---------------------------------- ---------------------------------------
//! ...
//! 53 JUMPDEST [ , , , ] {40: 80, 80: , a0: }
//! 54 PUSH1 40 [ , , , 40] {40: 80, 80: , a0: }
//! 56 MLOAD [ , , , 80] {40: 80, 80: , a0: }
//! 57 PUSH4 deadbeaf [ , , deadbeef, 80] {40: 80, 80: , a0: }
//! 62 DUP2 [ , 80, deadbeef, 80] {40: 80, 80: , a0: }
//! 63 MSTORE [ , , , 80] {40: 80, 80: deadbeef, a0: }
//! 64 PUSH4 faceb00c [ , , faceb00c, 80] {40: 80, 80: deadbeef, a0: }
//! 69 DUP2 [ , 80, faceb00c, 80] {40: 80, 80: deadbeef, a0: }
//! 70 MLOAD [ , deadbeef, faceb00c, 80] {40: 80, 80: deadbeef, a0: }
//! 71 ADD [ , , 1d97c6efb, 80] {40: 80, 80: deadbeef, a0: }
//! 72 DUP2 [ , 80, 1d97c6efb, 80] {40: 80, 80: deadbeef, a0: }
//! 73 MSTORE [ , , , 80] {40: 80, 80: 1d97c6efb, a0: }
//! 74 PUSH4 cafeb0ba [ , , cafeb0ba, 80] {40: 80, 80: 1d97c6efb, a0: }
//! 79 PUSH1 20 [ , 20, cafeb0ba, 80] {40: 80, 80: 1d97c6efb, a0: }
//! 81 DUP3 [ 80, 20, cafeb0ba, 80] {40: 80, 80: 1d97c6efb, a0: }
//! 82 ADD [ , a0, cafeb0ba, 80] {40: 80, 80: 1d97c6efb, a0: }
//! 83 MSTORE [ , , , 80] {40: 80, 80: 1d97c6efb, a0: cafeb0ba}
//! 84 POP [ , , , ] {40: 80, 80: 1d97c6efb, a0: cafeb0ba}
//! ...
//! ```
//!
//! Once you have the trace built (following the code found above) you can
//! basically:
//! - Get an iterator/vector over the `Stack`, `Memory` or `Storage` operations ordered on the way
//! the State Proof needs.
//!
//! On that way, we would get something like this for the Memory ops:
//! ```text,ignore
//! | `key` | `val` | `rw` | `gc` | Note |
//! |:------:| ------------- | ------- | ---- | ---------------------------------------- |
//! | `0x40` | `0` | `Write` | | Init |
//! | `0x40` | `0x80` | `Write` | 0 | Assume written at the beginning of `code`|
//! | `0x40` | `0x80` | `Read` | 4 | `56 MLOAD` |
//! | - | | | | |
//! | `0x80` | `0` | `Write` | | Init |
//! | `0x80` | `0xdeadbeef` | `Write` | 10 | `63 MSTORE` |
//! | `0x80` | `0xdeadbeef` | `Read` | 16 | `70 MLOAD` |
//! | `0x80` | `0x1d97c6efb` | `Write` | 24 | `73 MSTORE` |
//! | - | | | | |
//! | `0xa0` | `0` | `Write` | | Init |
//! | `0xa0` | `0xcafeb0ba` | `Write` | 34 | `83 MSTORE`
//! ```
//!
//! Where as you see, we group by `memory_address` and then order by
//! `global_counter`.
//!
//! - Iterate over the `ExecutionTrace` itself over
//! each `ExecutionStep`'s is formed by and check which Stack/Memory&Storage
//! operations are linked to each step. This is also automatically done via the
//! [`Opcode`](crate::evm::opcodes::Opcode) trait defined in this crate.
//!
//! ## Documentation
//! For extra documentation, check the book with the specs written for the
//! entire ZK-EVM solution.
//! See: <https://hackmd.io/@liangcc/zkvmbook/https%3A%2F%2Fhackmd.io%2FAmhZ2ryITxicmhYFyQ0DEw#Bus-Mapping>
#![cfg_attr(docsrs, feature(doc_cfg))]
// Temporary until we have more of the crate implemented.
#![allow(dead_code)]
// We want to have UPPERCASE idents sometimes.
#![allow(non_snake_case)]
// Catch documentation errors caused by code changes.
#![deny(rustdoc::broken_intra_doc_links)]
#![deny(missing_docs)]
#![allow(clippy::upper_case_acronyms)] // Too pedantic
#![allow(clippy::bool_to_int_with_if)]
#![allow(clippy::result_large_err)] // it's large, but what can we do?
#![allow(clippy::collapsible_else_if)]
#![allow(incomplete_features)]
#![feature(adt_const_params)]
extern crate alloc;
extern crate core;
pub mod circuit_input_builder;
pub mod error;
pub mod evm;
pub mod exec_trace;
pub use eth_types::l2_predeployed;
pub mod mock;
pub mod operation;
pub mod precompile;
pub mod rpc;
pub mod util;
pub use error::Error;