evm-rs/src/lib.rs
src/lib.rsRaw
1#![allow(dead_code)]
2
3use num_bigint::BigUint;
4use std::collections::HashMap;
5
6// Non-opcode gas prices
7const GDEFAULT: usize = 1;
8const GMEMORY: usize = 3;
9const GQUADRATICMEMDENOM: usize = 512; // 1 gas per 512 quadwords
10const GSTORAGEREFUND: usize = 15000;
11const GSTORAGEKILL: usize = 5000;
12const GSTORAGEMOD: usize = 5000;
13const GSTORAGEADD: usize = 20000;
14const GEXPONENTBYTE: usize = 10; // cost of EXP exponent per byte
15const GCOPY: usize = 3; // cost to copy one 32 byte word
16const GCONTRACTBYTE: usize = 200; // one byte of code in contract creation
17const GCALLVALUETRANSFER: usize = 9000; // non-zero-valued call
18const GLOGBYTE: usize = 8; // cost of a byte of logdata
19
20const GTXCOST: usize = 21000; // TX BASE GAS COST
21const GTXDATAZERO: usize = 4; // TX DATA ZERO BYTE GAS COST
22const GTXDATANONZERO: usize = 68; // TX DATA NON ZERO BYTE GAS COST
23const GSHA3WORD: usize = 6; // Cost of SHA3 per word
24const GSHA256BASE: usize = 60; // Base c of SHA256
25const GSHA256WORD: usize = 12; // Cost of SHA256 per word
26const GRIPEMD160BASE: usize = 600; // Base cost of RIPEMD160
27const GRIPEMD160WORD: usize = 120; // Cost of RIPEMD160 per word
28const GIDENTITYBASE: usize = 15; // Base cost of indentity
29const GIDENTITYWORD: usize = 3; // Cost of identity per word
30const GECRECOVER: usize = 3000; // Cost of ecrecover op
31
32const GSTIPEND: usize = 2300;
33
34const GCALLNEWACCOUNT: usize = 25000;
35const GSUICIDEREFUND: usize = 24000;
36
37pub struct Stack {
38 pc: usize,
39 calldata_i: usize,
40 stack: Vec<[u8; 32]>,
41 mem: Vec<u8>,
42 gas: u64,
43 opcodes: HashMap<u8, Opcode>,
44}
45
46impl Stack {
47 pub fn new() -> Stack {
48 let mut s = Stack {
49 pc: 0,
50 calldata_i: 0,
51 stack: Vec::new(),
52 mem: Vec::new(),
53 gas: 10000000000,
54 opcodes: HashMap::new(),
55 };
56 s.opcodes = new_opcodes();
57 s
58 }
59 fn print_stack(&self) {
60 for i in (0..self.stack.len()).rev() {
61 println!("{:x?}", &self.stack[i][28..]);
62 }
63 }
64 fn push(&mut self, b: [u8; 32]) {
65 self.stack.push(b);
66 }
67 // push_arbitrary performs a push, but first converting the arbitrary-length input into a 32
68 // byte array
69 fn push_arbitrary(&mut self, b: &[u8]) {
70 // TODO if b.len()>32 return error
71 let mut d: [u8; 32] = [0; 32];
72 d[32 - b.len()..].copy_from_slice(&b[..]);
73 self.stack.push(d);
74 }
75 // put_arbitrary puts in the last element of the stack the value
76 fn put_arbitrary(&mut self, b: &[u8]) {
77 // TODO if b.len()>32 return error
78 let mut d: [u8; 32] = [0; 32];
79 d[32 - b.len()..].copy_from_slice(&b[..]);
80 let l = self.stack.len();
81 self.stack[l - 1] = d;
82 }
83 fn pop(&mut self) -> [u8; 32] {
84 match self.stack.pop() {
85 Some(x) => return x,
86 None => panic!("err"),
87 }
88 }
89 fn execute(&mut self, code: &[u8], calldata: &[u8], debug: bool) -> Vec<u8> {
90 self.pc = 0;
91 self.calldata_i = 0;
92 let l = code.len();
93
94 while self.pc < l {
95 let opcode = code[self.pc];
96 if !self.opcodes.contains_key(&opcode) {
97 panic!("invalid opcode {:x}", opcode);
98 }
99
100 if debug {
101 println!(
102 "{:?} (0x{:x}): pc={:?} gas={:?}\nstack:",
103 self.opcodes.get(&opcode).unwrap().name,
104 opcode,
105 self.pc,
106 self.gas,
107 );
108 self.print_stack();
109 println!("");
110 }
111 match opcode & 0xf0 {
112 0x00 => {
113 // arithmetic
114 match opcode {
115 0x00 => {
116 return Vec::new();
117 }
118 0x01 => self.add(),
119 0x02 => self.mul(),
120 0x03 => self.sub(),
121 0x04 => self.div(),
122 0x05 => self.sdiv(),
123 0x06 => self.modulus(),
124 0x07 => self.smod(),
125 0x08 => self.add_mod(),
126 0x09 => self.mul_mod(),
127 0x0a => self.exp(),
128 // 0x0b => self.sign_extend(),
129 _ => panic!("unimplemented {:x}", opcode),
130 }
131 self.pc += 1;
132 }
133 0x30 => {
134 match opcode {
135 0x35 => {
136 self.calldata_load(&calldata);
137 }
138 _ => panic!("unimplemented {:x}", opcode),
139 }
140 self.pc += 1;
141 }
142 0x50 => {
143 self.pc += 1;
144 match opcode {
145 0x51 => self.mload(),
146 0x52 => self.mstore(),
147 0x56 => self.jump(),
148 0x57 => {
149 self.jump_i();
150 }
151 0x5b => {
152 self.jump_dest();
153 }
154 _ => panic!("unimplemented {:x}", opcode),
155 }
156 }
157 0x60 | 0x70 => {
158 // push
159 let n = (opcode - 0x5f) as usize;
160 self.push_arbitrary(&code[self.pc + 1..self.pc + 1 + n]);
161 self.pc += 1 + n;
162 }
163 0x80 => {
164 // 0x8x dup
165 let l = self.stack.len();
166 if opcode > 0x7f {
167 self.stack.push(self.stack[l - (opcode - 0x7f) as usize]);
168 } else {
169 self.stack.push(self.stack[(0x7f - opcode) as usize]);
170 }
171 self.pc += 1;
172 }
173 0x90 => {
174 // 0x9x swap
175 let l = self.stack.len();
176 let pos;
177 if opcode > 0x8e {
178 pos = l - (opcode - 0x8e) as usize;
179 } else {
180 pos = (0x8e - opcode) as usize;
181 }
182 let tmp = self.stack[pos];
183 self.stack[pos] = self.stack[l - 1];
184 self.stack[l - 1] = tmp;
185 self.pc += 1;
186 }
187 0xf0 => {
188 if opcode == 0xf3 {
189 let pos_to_return = u256_to_u64(self.pop()) as usize;
190 let len_to_return = u256_to_u64(self.pop()) as usize;
191 return self.mem[pos_to_return..pos_to_return + len_to_return].to_vec();
192 }
193 }
194 _ => {
195 panic!("unimplemented {:x}", opcode);
196 }
197 }
198 self.gas -= self.opcodes.get(&opcode).unwrap().gas;
199 }
200 return Vec::new();
201 }
202
203 // arithmetic
204 // TODO instead of [u8;32] converted to BigUint, use custom type uint256 that implements all
205 // the arithmetic
206 fn add(&mut self) {
207 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
208 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
209 self.push_arbitrary(&(b0 + b1).to_bytes_be());
210 }
211 fn mul(&mut self) {
212 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
213 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
214 self.push_arbitrary(&(b0 * b1).to_bytes_be());
215 }
216 fn sub(&mut self) {
217 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
218 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
219 if b0 >= b1 {
220 self.push_arbitrary(&(b0 - b1).to_bytes_be());
221 } else {
222 // 2**256
223 let max =
224 "115792089237316195423570985008687907853269984665640564039457584007913129639936"
225 .parse::<BigUint>()
226 .unwrap();
227 self.push_arbitrary(&(max + b0 - b1).to_bytes_be());
228 }
229 }
230 fn div(&mut self) {
231 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
232 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
233 self.push_arbitrary(&(b0 / b1).to_bytes_be());
234 }
235 fn sdiv(&mut self) {
236 panic!("unimplemented");
237 }
238 fn modulus(&mut self) {
239 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
240 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
241 self.push_arbitrary(&(b0 % b1).to_bytes_be());
242 }
243 fn smod(&mut self) {
244 panic!("unimplemented");
245 }
246 fn add_mod(&mut self) {
247 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
248 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
249 let b2 = BigUint::from_bytes_be(&self.pop()[..]);
250 self.push_arbitrary(&(b0 + b1 % b2).to_bytes_be());
251 }
252 fn mul_mod(&mut self) {
253 let b0 = BigUint::from_bytes_be(&self.pop()[..]);
254 let b1 = BigUint::from_bytes_be(&self.pop()[..]);
255 let b2 = BigUint::from_bytes_be(&self.pop()[..]);
256 self.push_arbitrary(&(b0 * b1 % b2).to_bytes_be());
257 }
258 fn exp(&mut self) {
259 panic!("unimplemented");
260 // let b0 = BigUint::from_bytes_be(&self.pop()[..]);
261 // let b1 = BigUint::from_bytes_be(&self.pop()[..]);
262 // self.push_arbitrary(&(pow(b0, b1)).to_bytes_be());
263 }
264
265 // boolean
266 // crypto
267
268 // contract context
269 fn calldata_load(&mut self, calldata: &[u8]) {
270 self.put_arbitrary(&calldata[self.calldata_i..self.calldata_i + 32]);
271 self.calldata_i += 32;
272 }
273
274 // blockchain context
275
276 // storage and execution
277 fn extend_mem(&mut self, start: usize, size: usize) {
278 if size <= self.mem.len() || start + size <= self.mem.len() {
279 return;
280 }
281 let old_size = self.mem.len() / 32;
282 let new_size = (start + size) / 32;
283 let old_total_fee = old_size * GMEMORY + old_size.pow(2) / GQUADRATICMEMDENOM;
284 let new_total_fee = new_size * GMEMORY + new_size.pow(2) / GQUADRATICMEMDENOM;
285 let mem_fee = new_total_fee - old_total_fee;
286 self.gas -= mem_fee as u64;
287 let mut new_bytes: Vec<u8> = vec![0; size];
288 self.mem.append(&mut new_bytes);
289 }
290 fn mload(&mut self) {
291 let pos = u256_to_u64(self.pop()) as usize;
292 self.extend_mem(pos as usize, 32);
293 let mem32 = self.mem[pos..pos + 32].to_vec();
294 self.push_arbitrary(&mem32);
295 }
296 fn mstore(&mut self) {
297 let pos = u256_to_u64(self.pop());
298 let val = self.pop();
299 self.extend_mem(pos as usize, 32);
300
301 self.mem[pos as usize..].copy_from_slice(&val);
302 }
303 fn jump(&mut self) {
304 // TODO that jump destination is valid
305 self.pc = u256_to_u64(self.pop()) as usize;
306 }
307 fn jump_i(&mut self) {
308 let new_pc = u256_to_u64(self.pop()) as usize;
309 if self.stack.len() > 0 {
310 let cond = u256_to_u64(self.pop()) as usize;
311 if cond != 0 {
312 self.pc = new_pc;
313 }
314 }
315 // let cont = self.pop();
316 // if cont {} // TODO depends on having impl Err in pop()
317 }
318 fn jump_dest(&mut self) {
319 // TODO
320 }
321}
322
323fn u256_to_u64(a: [u8; 32]) -> u64 {
324 let mut b8: [u8; 8] = [0; 8];
325 b8.copy_from_slice(&a[32 - 8..32]);
326 let pos = u64::from_be_bytes(b8);
327 pos
328}
329fn str_to_u256(s: &str) -> [u8; 32] {
330 let bi = s.parse::<BigUint>().unwrap().to_bytes_be();
331 let mut r: [u8; 32] = [0; 32];
332 r[32 - bi.len()..].copy_from_slice(&bi[..]);
333 r
334}
335
336struct Opcode {
337 name: String,
338 ins: u32,
339 outs: u32,
340 gas: u64,
341 // operation: fn(),
342}
343
344fn new_opcode(name: &str, ins: u32, outs: u32, gas: u64) -> Opcode {
345 Opcode {
346 name: name.to_string(),
347 ins,
348 outs,
349 gas,
350 }
351}
352
353fn new_opcodes() -> HashMap<u8, Opcode> {
354 let mut opcodes: HashMap<u8, Opcode> = HashMap::new();
355
356 // arithmetic
357 opcodes.insert(0x00, new_opcode("STOP", 0, 0, 0));
358 opcodes.insert(0x01, new_opcode("ADD", 2, 1, 3));
359 opcodes.insert(0x02, new_opcode("MUL", 2, 1, 5));
360 opcodes.insert(0x03, new_opcode("SUB", 2, 1, 3));
361 opcodes.insert(0x04, new_opcode("DIV", 2, 1, 5));
362 opcodes.insert(0x05, new_opcode("SDIV", 2, 1, 5));
363 opcodes.insert(0x06, new_opcode("MOD", 2, 1, 5));
364 opcodes.insert(0x07, new_opcode("SMOD", 2, 1, 5));
365 opcodes.insert(0x08, new_opcode("ADDMOD", 3, 1, 8));
366 opcodes.insert(0x09, new_opcode("MULMOD", 3, 1, 8));
367 opcodes.insert(0x0a, new_opcode("EXP", 2, 1, 10));
368 opcodes.insert(0x0b, new_opcode("SIGNEXTEND", 2, 1, 5));
369
370 // boolean
371 opcodes.insert(0x10, new_opcode("LT", 2, 1, 3));
372 opcodes.insert(0x11, new_opcode("GT", 2, 1, 3));
373 opcodes.insert(0x12, new_opcode("SLT", 2, 1, 3));
374 opcodes.insert(0x13, new_opcode("SGT", 2, 1, 3));
375 opcodes.insert(0x14, new_opcode("EQ", 2, 1, 3));
376 opcodes.insert(0x15, new_opcode("ISZERO", 1, 1, 3));
377 opcodes.insert(0x16, new_opcode("AND", 2, 1, 3));
378 opcodes.insert(0x17, new_opcode("OR", 2, 1, 3));
379 opcodes.insert(0x18, new_opcode("XOR", 2, 1, 3));
380 opcodes.insert(0x19, new_opcode("NOT", 1, 1, 3));
381 opcodes.insert(0x1a, new_opcode("BYTE", 2, 1, 3));
382
383 // crypto
384 opcodes.insert(0x20, new_opcode("SHA3", 2, 1, 30));
385
386 // contract context
387 opcodes.insert(0x30, new_opcode("ADDRESS", 0, 1, 2));
388 opcodes.insert(0x31, new_opcode("BALANCE", 1, 1, 20));
389 opcodes.insert(0x32, new_opcode("ORIGIN", 0, 1, 2));
390 opcodes.insert(0x33, new_opcode("CALLER", 0, 1, 2));
391 opcodes.insert(0x34, new_opcode("CALLVALUE", 0, 1, 2));
392 opcodes.insert(0x35, new_opcode("CALLDATALOAD", 1, 1, 3));
393 opcodes.insert(0x36, new_opcode("CALLDATASIZE", 0, 1, 2));
394 opcodes.insert(0x37, new_opcode("CALLDATACOPY", 3, 0, 3));
395 opcodes.insert(0x38, new_opcode("CODESIZE", 0, 1, 2));
396 opcodes.insert(0x39, new_opcode("CODECOPY", 3, 0, 3));
397 opcodes.insert(0x3a, new_opcode("GASPRICE", 0, 1, 2));
398 opcodes.insert(0x3b, new_opcode("EXTCODESIZE", 1, 1, 20));
399 opcodes.insert(0x3c, new_opcode("EXTCODECOPY", 4, 0, 20));
400
401 // blockchain context
402 opcodes.insert(0x40, new_opcode("BLOCKHASH", 1, 1, 20));
403 opcodes.insert(0x41, new_opcode("COINBASE", 0, 1, 2));
404 opcodes.insert(0x42, new_opcode("TIMESTAMP", 0, 1, 2));
405 opcodes.insert(0x43, new_opcode("NUMBER", 0, 1, 2));
406 opcodes.insert(0x44, new_opcode("DIFFICULTY", 0, 1, 2));
407 opcodes.insert(0x45, new_opcode("GASLIMIT", 0, 1, 2));
408
409 // storage and execution
410 opcodes.insert(0x50, new_opcode("POP", 1, 0, 2));
411 opcodes.insert(0x51, new_opcode("MLOAD", 1, 1, 3));
412 opcodes.insert(0x52, new_opcode("MSTORE", 2, 0, 3));
413 opcodes.insert(0x53, new_opcode("MSTORE8", 2, 0, 3));
414 opcodes.insert(0x54, new_opcode("SLOAD", 1, 1, 50));
415 opcodes.insert(0x55, new_opcode("SSTORE", 2, 0, 0));
416 opcodes.insert(0x56, new_opcode("JUMP", 1, 0, 8));
417 opcodes.insert(0x57, new_opcode("JUMPI", 2, 0, 10));
418 opcodes.insert(0x58, new_opcode("PC", 0, 1, 2));
419 opcodes.insert(0x59, new_opcode("MSIZE", 0, 1, 2));
420 opcodes.insert(0x5a, new_opcode("GAS", 0, 1, 2));
421 opcodes.insert(0x5b, new_opcode("JUMPDEST", 0, 0, 1));
422
423 // logging
424 opcodes.insert(0xa0, new_opcode("LOG0", 2, 0, 375));
425 opcodes.insert(0xa1, new_opcode("LOG1", 3, 0, 750));
426 opcodes.insert(0xa2, new_opcode("LOG2", 4, 0, 1125));
427 opcodes.insert(0xa3, new_opcode("LOG3", 5, 0, 1500));
428 opcodes.insert(0xa4, new_opcode("LOG4", 6, 0, 1875));
429
430 // closures
431 opcodes.insert(0xf0, new_opcode("CREATE", 3, 1, 32000));
432 opcodes.insert(0xf1, new_opcode("CALL", 7, 1, 40));
433 opcodes.insert(0xf2, new_opcode("CALLCODE", 7, 1, 40));
434 opcodes.insert(0xf3, new_opcode("RETURN", 2, 0, 0));
435 opcodes.insert(0xf4, new_opcode("DELEGATECALL", 6, 0, 40));
436 opcodes.insert(0xff, new_opcode("SUICIDE", 1, 0, 0));
437
438 for i in 1..33 {
439 let name = format!("PUSH{}", i);
440 opcodes.insert(0x5f + i, new_opcode(&name, 0, 1, 3));
441 }
442
443 for i in 1..17 {
444 let name = format!("DUP{}", i);
445 opcodes.insert(0x7f + i, new_opcode(&name, i as u32, i as u32 + 1, 3));
446
447 let name = format!("SWAP{}", i);
448 opcodes.insert(0x8f + i, new_opcode(&name, i as u32 + 1, i as u32 + 1, 3));
449 }
450
451 opcodes
452}
453
454#[cfg(test)]
455mod tests {
456 use super::*;
457
458 #[test]
459 fn stack_simple_push_pop() {
460 let mut s = Stack::new();
461 s.push(str_to_u256("1"));
462 s.push(str_to_u256("2"));
463 s.push(str_to_u256("3"));
464 assert_eq!(s.pop(), str_to_u256("3"));
465 assert_eq!(s.pop(), str_to_u256("2"));
466 assert_eq!(s.pop(), str_to_u256("1"));
467 // assert_eq!(s.pop(), str_to_u256("1"));
468 // assert_eq!(s.pop(), error); // TODO expect error as stack is empty
469 }
470
471 // arithmetic
472 #[test]
473 fn execute_opcodes_0() {
474 let code = hex::decode("6005600c01").unwrap(); // 5+12
475 let calldata = vec![];
476
477 let mut s = Stack::new();
478 s.execute(&code, &calldata, false);
479 assert_eq!(s.pop(), str_to_u256("17"));
480 assert_eq!(s.gas, 9999999991);
481 assert_eq!(s.pc, 5);
482 }
483
484 #[test]
485 fn execute_opcodes_1() {
486 let code = hex::decode("60056004016000526001601ff3").unwrap();
487 let calldata = vec![];
488
489 let mut s = Stack::new();
490 let out = s.execute(&code, &calldata, false);
491
492 assert_eq!(out[0], 0x09);
493 assert_eq!(s.gas, 9999999976);
494 assert_eq!(s.pc, 12);
495 // assert_eq!(s.pop(), err); // TODO expect error as stack is empty
496 }
497
498 #[test]
499 fn execute_opcodes_2() {
500 let code = hex::decode("61010161010201").unwrap();
501 let calldata = vec![];
502
503 let mut s = Stack::new();
504 s.execute(&code, &calldata, false);
505
506 // assert_eq!(out[0], 0x09);
507 assert_eq!(s.gas, 9999999991);
508 assert_eq!(s.pc, 7);
509 assert_eq!(s.pop(), str_to_u256("515"));
510 }
511
512 #[test]
513 fn execute_opcodes_3() {
514 // contains calldata
515 let code = hex::decode("60003560203501").unwrap();
516 let calldata = hex::decode("00000000000000000000000000000000000000000000000000000000000000050000000000000000000000000000000000000000000000000000000000000004").unwrap();
517
518 let mut s = Stack::new();
519 s.execute(&code, &calldata, false);
520
521 assert_eq!(s.gas, 9999999985);
522 assert_eq!(s.pc, 7);
523 assert_eq!(s.pop(), str_to_u256("9"));
524 }
525
526 // storage and execution
527 #[test]
528 fn execute_opcodes_4() {
529 // contains loops
530 let code = hex::decode("6000356000525b600160005103600052600051600657").unwrap();
531 let calldata =
532 hex::decode("0000000000000000000000000000000000000000000000000000000000000005")
533 .unwrap();
534
535 let mut s = Stack::new();
536 s.execute(&code, &calldata, false);
537
538 assert_eq!(s.gas, 9999999795);
539 assert_eq!(s.pc, 22);
540 assert_eq!(s.stack.len(), 0);
541 }
542 #[test]
543 fn execute_opcodes_5() {
544 // contains loops, without using mem
545 let code = hex::decode("6000355b6001900380600357").unwrap();
546 let calldata =
547 hex::decode("0000000000000000000000000000000000000000000000000000000000000001")
548 .unwrap();
549
550 let mut s = Stack::new();
551 s.execute(&code, &calldata, false);
552
553 assert_eq!(s.gas, 9999999968);
554 assert_eq!(s.pc, 12);
555
556 let code = hex::decode("6000355b6001900380600357").unwrap();
557 let calldata =
558 hex::decode("0000000000000000000000000000000000000000000000000000000000000002")
559 .unwrap();
560
561 let mut s = Stack::new();
562 s.execute(&code, &calldata, false);
563
564 assert_eq!(s.gas, 9999999942);
565 assert_eq!(s.pc, 12);
566
567 let code = hex::decode("6000355b6001900380600357").unwrap();
568 let calldata =
569 hex::decode("0000000000000000000000000000000000000000000000000000000000000005")
570 .unwrap();
571
572 let mut s = Stack::new();
573 s.execute(&code, &calldata, false);
574
575 assert_eq!(s.gas, 9999999864);
576 assert_eq!(s.pc, 12);
577 }
578}