Puzzle #14
Sacred Geometry
HuffHuff's logo.Puzzle
Curtacallsverify()
1
//! ```
2
//! Sacred Geometry
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
//! ## Memory Layout
31
//!
32
//! | index | value |
33
//! | ------ | ----------------- |
34
//! | 0x0000 | op_halt_dest |
35
//! | 0x0020 | op_add_dest |
36
//! | 0x0040 | op_sub_dest |
37
//! | 0x0060 | op_mul_dest |
38
//! | 0x0080 | op_div_dest |
39
//! | 0x00a0 | op_swap1_dest |
40
//! | 0x00c0 | op_swap2_dest |
41
//! | 0x00e0 | op_swap3_dest |
42
//! | 0x0100 | op_swap4_dest |
43
//! | 0x0120 | op_swap5_dest |
44
//! | 0x0140 | op_swap6_dest |
45
//! | 0x0160 | op_swap7_dest |
46
//! | 0x0180 | program_counter |
47
//! | 0x01a0 | executable |
48
//! | 0x01c0 | virtual_stack_ptr |
49
//!
50
//! ## Instruction Set
51
//!
52
//! | opcode | byte |
53
//! | ------ | ---- |
54
//! | HALT | 0x00 |
55
//! | ADD | 0x01 |
56
//! | SUB | 0x02 |
57
//! | MUL | 0x03 |
58
//! | DIV | 0x04 |
59
//! | SWAP1 | 0x05 |
60
//! | SWAP2 | 0x06 |
61
//! | SWAP3 | 0x07 |
62
//! | SWAP4 | 0x08 |
63
//! | SWAP5 | 0x09 |
64
//! | SWAP6 | 0x0a |
65
//! | SWAP7 | 0x0b |
66
67
// --- Application Binary Interface ---
68
69
#define function name() pure returns (string)
70
#define function generate(address) pure returns (uint256)
71
#define function verify(uint256,uint256) pure returns (bool)
72
73
// --- Constants ---
74
75
#define constant NAME_STR = 0x0f5361637265642047656f6d65747279
76
#define constant MAX_VALUE = 0x06
77
#define constant VIRTUAL_STACK_PTR = 0x07
78
#define constant OPCODE_MOD = 0x0c
79
80
#define constant PC_PTR = 0x0180
81
#define constant EXECUTABLE_PTR = 0x01a0
82
#define constant VIRTUAL_STACK_PTR_PTR = 0x01c0
83
84
#define constant ARG0_CD_PTR = 0x04
85
#define constant ARG1_CD_PTR = 0x24
86
87
#define constant PRIME_0 = 0x0d
88
#define constant PRIME_1 = 0x11
89
#define constant PRIME_2 = 0x13
90
91
#define constant INPUT_0 = 0x1f
92
#define constant INPUT_1 = 0x1e
93
#define constant INPUT_2 = 0x1d
94
#define constant INPUT_3 = 0x1c
95
#define constant INPUT_4 = 0x1b
96
#define constant INPUT_5 = 0x1a
97
#define constant INPUT_6 = 0x19
98
#define constant INPUT_7 = 0x18
99
100
// --- Macros ---
101
102
/// ## Entry Point
103
///
104
/// ### Directives
105
///
106
/// 1. Dispatch function by selector.
107
/// 2. Revert if selector is not matched.
108
///
109
/// ### Panics
110
///
111
/// - When selector is not matched.
112
/// - When `VERIFY` panics.
113
#define macro MAIN() = takes (0) returns (0) {
114
0x00 calldataload 0xe0 shr
115
dup1 __FUNC_SIG(name) eq is_name jumpi
116
dup1 __FUNC_SIG(generate) eq is_generate jumpi
117
dup1 __FUNC_SIG(verify) eq is_verify jumpi
118
0x00 0x00 revert
119
120
is_name:
121
NAME()
122
is_generate:
123
GENERATE()
124
is_verify:
125
VERIFY()
126
}
127
128
/// ## Return Name
129
///
130
/// ### Directives
131
///
132
/// 1. Store name in memory.
133
/// 2. Return from memory.
134
#define macro NAME() = takes (0) returns (0) {
135
0x20 // [ptr]
136
0x00 // [mem_ptr, ptr]
137
mstore // []
138
[NAME_STR] // [name]
139
0x2f // [mem_ptr, name]
140
mstore // []
141
0x60 // [mem_len]
142
0x00 // [mem_ptr, mem_len]
143
return // []
144
}
145
146
/// ## Generate Random Number
147
///
148
/// ### Directives
149
///
150
/// 1. Load seed from calldata.
151
/// 2. Generate 8 bytes with `GEN_BYTE`.
152
/// 3. Return the bytes, left padded in a single uint256.
153
#define macro GENERATE() = takes (0) returns (0) {
154
0x04 // [seed_cd_ptr]
155
calldataload // [seed]
156
GEN_BYTE(INPUT_0) // [seed]
157
GEN_BYTE(INPUT_1) // [seed]
158
GEN_BYTE(INPUT_2) // [seed]
159
GEN_BYTE(INPUT_3) // [seed]
160
GEN_BYTE(INPUT_4) // [seed]
161
GEN_BYTE(INPUT_5) // [seed]
162
GEN_BYTE(INPUT_6) // [seed]
163
GEN_BYTE(INPUT_7) // [seed]
164
0x20 // [mem_len, seed]
165
0x00 // [mem_ptr, mem_len, seed]
166
return // []
167
}
168
169
/// ## Verify Solution
170
///
171
/// ### Directives
172
///
173
/// 1. Initialize the VM with `INITIALIZE_VM`.
174
/// 2. Start execution loop.
175
/// 3. Get current opcode with `GET_OPCODE`.
176
/// 4. Increment program counter with `INCREMENT_PC`.
177
/// 5. Dispatch opcode with `DISPATCH_OPCODE`.
178
/// 6. Based on opcode, perform operation.
179
/// 7. If the opcode is not HALT, jump to exec_start, continue at step 3.
180
/// 8. If the opcode is HALT, check the output with `CHECK_OUTPUT`.
181
/// 9. If the output is correct, return true, else return false.
182
///
183
/// ### Panics
184
///
185
/// - When the stack underflows.
186
#define macro VERIFY() = takes (0) returns (0) {
187
INITIALIZE_VM() // [input_0, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
188
189
exec_start: // [..inputs]
190
GET_OPCODE() // [opcode, ..inputs]
191
INCREMENT_PC() // [opcode, ..inputs]
192
DISPATCH_OPCODE() // []
193
194
op_add: // [a, b, ..inputs]
195
DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
196
add // [sum, ..inputs]
197
exec_start jump // [sum, ..inputs]
198
199
op_sub: // [a, b, ..inputs]
200
DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
201
sub // [difference, ..inputs]
202
exec_start jump // [difference, ..inputs]
203
204
op_mul: // [a, b, ..inputs]
205
DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
206
mul // [prod, ..inputs]
207
exec_start jump // [prod, ..inputs]
208
209
op_div: // [a, b, ..inputs]
210
DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
211
div // [quotient, ..inputs]
212
exec_start jump // [quotient, ..inputs]
213
214
op_swap1: // [a, b, ..inputs]
215
swap1 // [b, a, ..inputs]
216
exec_start jump // [b, a, ..inputs]
217
218
op_swap2: // [a, _, b, ..inputs]
219
swap2 // [b, _, a, ..inputs]
220
exec_start jump // [b, _, a, ..inputs]
221
222
op_swap3: // [a, _, _, b, ..inputs]
223
swap3 // [b, _, _, a, ..inputs]
224
exec_start jump // [b, _, _, a, ..inputs]
225
226
op_swap4: // [a, _, _, _, b, ..inputs]
227
swap4 // [b, _, _, _, a, ..inputs]
228
exec_start jump // [b, _, _, _, a, ..inputs]
229
230
op_swap5: // [a, _, _, _, _, b, ..inputs]
231
swap5 // [b, _, _, _, _, a, ..inputs]
232
exec_start jump // [b, _, _, _, _, a, ..inputs]
233
234
op_swap6: // [a, _, _, _, _, _, b, ..inputs]
235
swap6 // [b, _, _, _, _, _, a, ..inputs]
236
exec_start jump // [b, _, _, _, _, _, a, ..inputs]
237
238
op_swap7: // [a, _, _, _, _, _, _, b]
239
swap7 // [b, _, _, _, _, _, _, a]
240
exec_start jump // [b, _, _, _, _, _, _, a]
241
242
op_halt: // [result]
243
CHECK_OUTPUT() // [is_valid_prime]
244
0x00 // [mem_ptr, is_valid_prime]
245
mstore // []
246
0x20 // [mem_len]
247
0x00 // [mem_ptr, mem_len]
248
return // []
249
}
250
251
// --- Virtual Machine Operations ---
252
253
/// ## Initialize VM
254
///
255
/// > Note: The program counter (`memory[0x0180]`) is implicitly initialized to 0.
256
///
257
/// ### Directives
258
///
259
/// 1. Store the opcode jumptable in memory.
260
/// 2. Write the executable to memory.
261
/// 3. Write the virtual stack depth to memory.
262
/// 4. Read the program input from calldata.
263
/// 5. Get and push each random number to the stack with `PUSH_NUMBER`.
264
#define macro INITIALIZE_VM() = takes (0) returns (1) {
265
__tablesize(OPCODE_TABLE) // [opcode_table_len]
266
__tablestart(OPCODE_TABLE) // [opcode_table_ptr, opcode_table_len]
267
0x00 // [mem_ptr, opcode_table_ptr, opcode_table_len]
268
codecopy // []
269
270
[ARG1_CD_PTR] // [executable_cd_ptr]
271
calldataload // [executable]
272
[EXECUTABLE_PTR] // [mem_ptr, executable]
273
mstore // []
274
275
[VIRTUAL_STACK_PTR] // [virtual_stack_depth]
276
[VIRTUAL_STACK_PTR_PTR] // [virtual_stack_ptr_ptr, virtual_stack_depth]
277
mstore // []
278
279
[ARG0_CD_PTR] // [program_input_cd_ptr]
280
calldataload // [program_input]
281
PUSH_NUMBER(INPUT_7) // [program_input, input_7]
282
PUSH_NUMBER(INPUT_6) // [program_input, input_6, input_7]
283
PUSH_NUMBER(INPUT_5) // [program_input, input_5, input_6, input_7]
284
PUSH_NUMBER(INPUT_4) // [program_input, input_4, input_5, input_6, input_7]
285
PUSH_NUMBER(INPUT_3) // [program_input, input_3, input_4, input_5, input_6, input_7]
286
PUSH_NUMBER(INPUT_2) // [program_input, input_2, input_3, input_4, input_5, input_6, input_7]
287
PUSH_NUMBER(INPUT_1) // [program_input, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
288
PUSH_NUMBER(INPUT_0) // [program_input, input_0, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
289
pop // [input_0, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
290
}
291
292
/// ## Get Opcode
293
///
294
/// ### Directives
295
///
296
/// 1. Read the program counter from memory.
297
/// 2. Add the executable offer to the program counter.
298
/// 3. Read the opcode from memory.
299
/// 4. Shift the opcode to the right by 248 bits.
300
/// 5. Mask the opcode with seven.
301
#define macro GET_OPCODE() = takes (0) returns (1) {
302
[PC_PTR] // [program_counter_ptr]
303
mload // [program_counter]
304
[EXECUTABLE_PTR] // [executable_start, program_counter]
305
add // [opcode_ptr]
306
mload // [opcode_word]
307
0xf8 // [shift, opcode_word]
308
shr // [opcode]
309
[OPCODE_MOD] // [opcode_mod, opcode]
310
swap1 // [opcode, opcode_mod]
311
mod // [valid_opcode]
312
}
313
314
/// ## Increment Program Counter
315
///
316
/// ### Directives
317
///
318
/// 1. Read the program counter from memory.
319
/// 2. Add one to the program counter.
320
/// 3. Write the new program counter to memory.
321
#define macro INCREMENT_PC() = takes (0) returns (0) {
322
[PC_PTR] // [program_counter_ptr, opcode]
323
dup1 // [program_counter_ptr, program_counter_ptr, opcode]
324
mload // [program_counter, program_counter_ptr, opcode]
325
0x01 // [one, program_counter, program_counter_ptr, opcode]
326
add // [new_program_counter, program_counter_ptr, opcode]
327
swap1 // [program_counter_ptr, new_program_counter, opcode]
328
mstore // [opcode]
329
}
330
331
/// ## Dispatch Opcode
332
///
333
/// ### Directives
334
///
335
/// 1. Shift the opcode to the left by five bits.
336
/// 2. Read the opcode from the jumptable in memory.
337
#define macro DISPATCH_OPCODE() = takes (1) returns (0) {
338
0x05 // [shift, opcode]
339
shl // [op_dispatch_ptr]
340
mload // [op_dispatch_dest]
341
jump // []
342
}
343
344
/// ## Decrement Virtual Stack Pointer
345
///
346
/// ### Directives
347
///
348
/// 1. Read the virtual stack pointer from memory.
349
/// 2. Subtract one from the virtual stack pointer.
350
/// 3. Write the new virtual stack pointer to memory.
351
#define macro DEC_VIRTUAL_STACK_PTR() = takes (0) returns (0) {
352
[VIRTUAL_STACK_PTR_PTR] // [virtual_stack_ptr_ptr]
353
0x01 // [one, virtual_stack_ptr_ptr]
354
dup2 // [virtual_stack_ptr_ptr, one, virtual_stack_ptr_ptr]
355
mload // [virtual_stack_ptr, one, virtual_stack_ptr_ptr]
356
sub // [new_virtual_stack_ptr, virtual_stack_ptr_ptr]
357
swap1 // [virtual_stack_ptr_ptr, new_virtual_stack_ptr]
358
mstore // []
359
}
360
361
/// ## Check the Program Output
362
///
363
/// ### Directives
364
///
365
/// 1. Checks if the result is equal to prime 0.
366
/// 2. Checks if the result is equal to prime 1.
367
/// 3. Checks if the result is equal to prime 2.
368
/// 4. Accumulates the result of the three checks.
369
/// 5. Checks if the stack is empty.
370
/// 6. Accumulates the result of the two checks.
371
#define macro CHECK_OUTPUT() = takes (1) returns (1) {
372
// takes: // [result]
373
dup1 dup1 // [result, result, result]
374
[PRIME_0] // [prime_0, result, result, result]
375
eq // [is_prime_0, result, result]
376
377
swap1 // [result, is_prime_0, result]
378
[PRIME_1] // [prime_1, result, is_prime_0, result]
379
eq // [is_prime_1, is_prime_0, result]
380
381
swap2 // [result, is_prime_1, is_prime_0]
382
[PRIME_2] // [prime_2, result, is_prime_1, is_prime_0]
383
eq // [is_prime_2, is_prime_1, is_prime_0]
384
385
or or // [is_valid_prime]
386
387
[VIRTUAL_STACK_PTR_PTR] // [virtual_stack_ptr_ptr, is_valid_prime]
388
mload // [virtual_stack_ptr, is_valid_prime]
389
iszero // [is_stack_empty, is_valid_prime]
390
and // [is_valid_output]
391
}
392
393
// --- Utilities ---
394
395
/// ## Generate Byte of Pseudorandom Number
396
///
397
/// ### Directives
398
///
399
/// 1. Extract a byte from the `seed` index `idx`.
400
/// 2. Modulo the byte by the `MAX_VALUE`.
401
/// 3. Add one to the result.
402
/// 4. Store the result in memory.
403
#define macro GEN_BYTE(idx) = takes (1) returns (1) {
404
// takes: // [seed]
405
[MAX_VALUE] // [mod, seed]
406
dup2 // [seed, mod, seed]
407
<idx> // [idx, seed, mod, seed]
408
byte // [byte, mod, seed]
409
mod // [rand, seed]
410
0x01 // [one, rand, seed]
411
add // [rand, seed]
412
<idx> // [idx, rand, seed]
413
mstore8 // [seed]
414
}
415
416
/// ## Push Pseudorandom Number to Stack
417
///
418
/// ### Directives
419
///
420
/// 1. Extract a byte from the `program_input` index `idx`.
421
#define macro PUSH_NUMBER(idx) = takes (1) returns (2) {
422
// takes: // [program_input]
423
dup1 // [program_input, program_input]
424
<idx> // [idx, program_input, program_input]
425
byte // [byte, program_input]
426
swap1 // [program_input, byte]
427
}
428
429
// --- Jumptable ---
430
431
/// ## Opcode Jumptable
432
///
433
/// Maps opcodes to jumptable indices in memory.
434
#define jumptable OPCODE_TABLE {
435
op_halt // 0x0000
436
op_add // 0x0020
437
op_sub // 0x0040
438
op_mul // 0x0060
439
op_div // 0x0080
440
op_swap1 // 0x00a0
441
op_swap2 // 0x00c0
442
op_swap3 // 0x00e0
443
op_swap4 // 0x0100
444
op_swap5 // 0x0120
445
op_swap6 // 0x0140
446
op_swap7 // 0x0160
447
}
First Blood
chainlight.io
00:30:36
24
Time Left

Solve locally (WIP)

  1. Clone GitHub repo + install deps
git clone https://github.com/waterfall-mkt/curta-puzzles.git && cd curta-puzzles && forge install
  1. Set RPC_URL_MAINNET in .env
.env
RPC_URL_MAINNET=""
  1. Write solution + run script
forge script <PATH_TO_PUZZLE> -f mainnet -vvv
This is still WIP.
Waterfall