1
// SPDX-License-Identifier: MIT
2

3
pragma solidity ^0.8.13;
4

5
import {IPuzzle} from "./IPuzzle.sol";
6
import {TxHashSimulator} from "./TxHashSimulator.sol";
7

8
contract Submerged is IPuzzle {
9
    TxHashSimulator public simulator = new TxHashSimulator();
10

11
    mapping (bytes32 => bool) public submergedTxs;
12
    mapping (bytes32 => bool) public submergedSeeds;
13

14
    function name() external pure returns (string memory) {
15
        return "Submerged";
16
    }
17

18
    function generate(address seed) external pure returns (uint256) {
19
        return uint256(keccak256(abi.encode(seed)));
20
    }
21

22
    function verify(uint256 seed, uint256 solution) external view returns (bool) {
23
        return submergedSeeds[keccak256(abi.encode(seed, solution))];
24
    }
25

26
    function proveSubmergedTx() external {
27
        bytes32 txHash = simulator.TXHASH();
28
        require(txHash != bytes32(0), "must use TxHashSimulator");
29
        require(address(tx.origin).balance == 0, "not fully submerged");
30

31
        submergedTxs[txHash] = true;
32
    }
33

34
    function proveSubmergedSeed(bytes calldata rawTx) external {
35
        require(submergedTxs[keccak256(rawTx)], "tx not submerged");
36

37
        bytes calldata data = rawTx;
38
        uint256 off;
39
        (, off) = RLP.parseList(data);
40
        data = data[off:];
41

42
        data = RLP.skip(data); // nonce
43
        data = RLP.skip(data); // gasPrice
44
        data = RLP.skip(data); // gasLimit
45
        data = RLP.skip(data); // to
46
        data = RLP.skip(data); // value
47

48
        (data, ) = RLP.splitBytes(data); // extra the tx calldata
49
        bytes32 seed = bytes32(data[:32]);
50

51
        submergedSeeds[seed] = true;
52
    }
53
}
54

55
contract TxHashSimulator {
56
    // wen TSTORE
57
    bytes32 public TXHASH;
58

59
    function getCurrentTxHash() internal view returns (bytes32 txHash) {
60
        require(tx.origin == msg.sender, "can only verify txHash if sender is origin");
61

62
        // collect parameters
63
        // note: gasLimit could be derived from entry gas and calldata,
64
        //       but it's cheaper to require it in calldata
65
        uint256 gasLimit;
66
        bytes32 seed;
67
        assembly {
68
            seed := calldataload(0)
69
            gasLimit := calldataload(32)
70
        }
71

72
        uint8 v = 27;
73
        bytes32 r;
74
        bytes32 s;
75
        assembly {
76
            mstore(0, seed)
77
            r := keccak256(0, 32)
78
            mstore(0, r)
79
            s := keccak256(0, 32)
80
        }
81

82
        bytes[] memory txList = new bytes[](9);
83
        txList[0] = RLP.encodeUint(0); // nonce
84
        txList[1] = RLP.encodeUint(tx.gasprice); // gas price
85
        txList[2] = RLP.encodeUint(gasLimit); // claimed gasLimit
86
        txList[3] = RLP.encodeUint(uint256(uint160(address(this)))); // to address
87
        txList[4] = RLP.encodeUint(msg.value); // tx value
88
        txList[5] = RLP.encodeBytes(msg.data); // tx data
89
        txList[6] = RLP.encodeUint(uint256(v)); // v
90
        txList[7] = RLP.encodeUint(uint256(r)); // r
91
        txList[8] = RLP.encodeUint(uint256(s)); // s
92

93
        txHash = keccak256(RLP.encodeList(txList));
94

95
        // truncate the tx fields to exclude the signature data
96
        assembly {
97
            mstore(txList, 6)
98
        }
99

100
        bytes32 signingHash = keccak256(RLP.encodeList(txList));
101
        require(
102
            ecrecover(signingHash, v, r, s) == msg.sender,
103
            "could not verify tx hash"
104
        );
105
    }
106

107
    fallback() external {
108
        TXHASH = getCurrentTxHash();
109

110
        assembly {
111
            let target := calldataload(64)
112
            let len := sub(calldatasize(), 96)
113
            calldatacopy(0, 96, len)
114
            let res := call(
115
                gas(),
116
                target,
117
                callvalue(),
118
                0,
119
                len,
120
                0,
121
                0
122
            )
123
            sstore(TXHASH.slot, 0)
124
            if res {
125
                returndatacopy(0, 0, returndatasize())
126
                return(0, returndatasize())
127
            }
128
            returndatacopy(0, 0, returndatasize())
129
            revert(0, returndatasize())
130
        }
131
    }
132
}
133

134

135
library RLP {
136
    function parseUint(bytes calldata buf) internal pure returns (uint256 result, uint256 size) {
137
        assembly {
138
            // check that we have at least one byte of input
139
            if iszero(buf.length) {
140
                revert(0, 0)
141
            }
142
            let first32 := calldataload(buf.offset)
143
            let kind := shr(248, first32)
144

145
            // ensure it's a not a long string or list (> 0xB7)
146
            // also ensure it's not a short string longer than 32 bytes (> 0xA0)
147
            if gt(kind, 0xA0) {
148
                revert(0, 0)
149
            }
150

151
            switch lt(kind, 0x80)
152
            case true {
153
                // small single byte
154
                result := kind
155
                size := 1
156
            }
157
            case false {
158
                // short string
159
                size := sub(kind, 0x80)
160

161
                // ensure it's not reading out of bounds
162
                if lt(buf.length, size) {
163
                    revert(0, 0)
164
                }
165

166
                switch eq(size, 32)
167
                case true {
168
                    // if it's exactly 32 bytes, read it from calldata
169
                    result := calldataload(add(buf.offset, 1))
170
                }
171
                case false {
172
                    // if it's < 32 bytes, we've already read it from calldata
173
                    result := shr(shl(3, sub(32, size)), shl(8, first32))
174
                }
175
                size := add(size, 1)
176
            }
177
        }
178
    }
179

180
    function nextSize(bytes calldata buf) internal pure returns (uint256 size) {
181
        assembly {
182
            if iszero(buf.length) {
183
                revert(0, 0)
184
            }
185
            let first32 := calldataload(buf.offset)
186
            let kind := shr(248, first32)
187

188
            switch lt(kind, 0x80)
189
            case true {
190
                // small single byte
191
                size := 1
192
            }
193
            case false {
194
                switch lt(kind, 0xB8)
195
                case true {
196
                    // short string
197
                    size := add(1, sub(kind, 0x80))
198
                }
199
                case false {
200
                    switch lt(kind, 0xC0)
201
                    case true {
202
                        // long string
203
                        let lengthSize := sub(kind, 0xB7)
204

205
                        // ensure that we don't overflow
206
                        if gt(lengthSize, 31) {
207
                            revert(0, 0)
208
                        }
209

210
                        // ensure that we don't read out of bounds
211
                        if lt(buf.length, lengthSize) {
212
                            revert(0, 0)
213
                        }
214
                        size := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
215
                        size := add(size, add(1, lengthSize))
216
                    }
217
                    case false {
218
                        switch lt(kind, 0xF8)
219
                        case true {
220
                            // short list
221
                            size := add(1, sub(kind, 0xC0))
222
                        }
223
                        case false {
224
                            let lengthSize := sub(kind, 0xF7)
225

226
                            // ensure that we don't overflow
227
                            if gt(lengthSize, 31) {
228
                                revert(0, 0)
229
                            }
230
                            // ensure that we don't read out of bounds
231
                            if lt(buf.length, lengthSize) {
232
                                revert(0, 0)
233
                            }
234
                            size := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
235
                            size := add(size, add(1, lengthSize))
236
                        }
237
                    }
238
                }
239
            }
240
        }
241
    }
242

243
    function skip(bytes calldata buf) internal pure returns (bytes calldata) {
244
        uint256 size = RLP.nextSize(buf);
245
        assembly {
246
            buf.offset := add(buf.offset, size)
247
            buf.length := sub(buf.length, size)
248
        }
249
        return buf;
250
    }
251

252
    function parseList(bytes calldata buf)
253
        internal
254
        pure
255
        returns (uint256 listSize, uint256 offset)
256
    {
257
        assembly {
258
            // check that we have at least one byte of input
259
            if iszero(buf.length) {
260
                revert(0, 0)
261
            }
262
            let first32 := calldataload(buf.offset)
263
            let kind := shr(248, first32)
264

265
            // ensure it's a list
266
            if lt(kind, 0xC0) {
267
                revert(0, 0)
268
            }
269

270
            switch lt(kind, 0xF8)
271
            case true {
272
                // short list
273
                listSize := sub(kind, 0xC0)
274
                offset := 1
275
            }
276
            case false {
277
                // long list
278
                let lengthSize := sub(kind, 0xF7)
279

280
                // ensure that we don't overflow
281
                if gt(lengthSize, 31) {
282
                    revert(0, 0)
283
                }
284
                // ensure that we don't read out of bounds
285
                if lt(buf.length, lengthSize) {
286
                    revert(0, 0)
287
                }
288
                listSize := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
289
                offset := add(lengthSize, 1)
290
            }
291
        }
292
    }
293

294
    function splitBytes(bytes calldata buf)
295
        internal
296
        pure
297
        returns (bytes calldata result, bytes calldata rest)
298
    {
299
        uint256 offset;
300
        uint256 size;
301
        assembly {
302
            // check that we have at least one byte of input
303
            if iszero(buf.length) {
304
                revert(0, 0)
305
            }
306
            let first32 := calldataload(buf.offset)
307
            let kind := shr(248, first32)
308

309
            // ensure it's a not list
310
            if gt(kind, 0xBF) {
311
                revert(0, 0)
312
            }
313

314
            switch lt(kind, 0x80)
315
            case true {
316
                // small single byte
317
                offset := 0
318
                size := 1
319
            }
320
            case false {
321
                switch lt(kind, 0xB8)
322
                case true {
323
                    // short string
324
                    offset := 1
325
                    size := sub(kind, 0x80)
326
                }
327
                case false {
328
                    // long string
329
                    let lengthSize := sub(kind, 0xB7)
330

331
                    // ensure that we don't overflow
332
                    if gt(lengthSize, 31) {
333
                        revert(0, 0)
334
                    }
335
                    // ensure we don't read out of bounds
336
                    if lt(buf.length, lengthSize) {
337
                        revert(0, 0)
338
                    }
339
                    size := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
340
                    offset := add(lengthSize, 1)
341
                }
342
            }
343

344
            result.offset := add(buf.offset, offset)
345
            result.length := size
346

347
            let end := add(offset, size)
348
            rest.offset := add(buf.offset, end)
349
            rest.length := sub(buf.length, end)
350
        }
351
    }
352

353
    function encodeLength(uint256 len, uint8 offset) internal pure returns (bytes memory result) {
354
        if (len < 56) {
355
            result = new bytes(1);
356
                assembly {
357
                    mstore(
358
                        add(result, 32),
359
                        shl(248, add(offset, len))
360
                    )
361
                }
362
        } else {
363
            require(len < 2**32, "lengths exceeding UINT32_MAX are unsupported");
364
            if (len > 2**24) {
365
                result = new bytes(5);
366
                assembly {
367
                    mstore(
368
                        add(result, 32),
369
                        or(
370
                            shl(248, add(offset, 59)),
371
                            shl(216, len)
372
                        )
373
                    )
374
                }
375
            } else if (len > 2**16) {
376
                result = new bytes(4);
377
                assembly {
378
                    mstore(
379
                        add(result, 32),
380
                        or(
381
                            shl(248, add(offset, 58)),
382
                            shl(224, len)
383
                        )
384
                    )
385
                }
386
            } else if (len > 2**8) {
387
                result = new bytes(3);
388
                assembly {
389
                    mstore(
390
                        add(result, 32),
391
                        or(
392
                            shl(248, add(offset, 57)),
393
                            shl(232, len)
394
                        )
395
                    )
396
                }
397
            } else {
398
                result = new bytes(2);
399
                assembly {
400
                    mstore(
401
                        add(result, 32),
402
                        or(
403
                            shl(248, add(offset, 56)),
404
                            shl(240, len)
405
                        )
406
                    )
407
                }
408
            }
409
        }
410
    }
411

412
    function encodeList(bytes[] memory encodedElems) internal view returns (bytes memory result) {
413
        uint256 totalLength;
414
        assembly {
415
            let elemsStart := add(encodedElems, 0x20)
416
            let elemsEnd := add(elemsStart, mul(0x20, mload(encodedElems)))
417
            for {let off := elemsStart} lt(off, elemsEnd) {off := add(off, 0x20)} {
418
                let elem := mload(off)
419
                totalLength := add(totalLength, mload(elem))
420
            }
421
        }
422
        bytes memory encodedLength = encodeLength(totalLength, 0xc0);
423
        unchecked { totalLength += encodedLength.length; }
424
        result = new bytes(totalLength);
425
        assembly {
426
            let ptr := add(result, 0x20)
427
            mstore(ptr, mload(add(encodedLength, 0x20)))
428
            ptr := add(ptr, mload(encodedLength))
429

430
            let elemsStart := add(encodedElems, 0x20)
431
            let elemsEnd := add(elemsStart, mul(0x20, mload(encodedElems)))
432
            for {let off := elemsStart} lt(off, elemsEnd) {off := add(off, 0x20)} {
433
                let elem := mload(off)
434
                let len := mload(elem)
435
                if iszero(staticcall(
436
                    gas(),
437
                    4,
438
                    add(elem, 0x20),
439
                    len,
440
                    ptr,
441
                    len
442
                )) {
443
                    revert(0, 0)
444
                }
445
                ptr := add(ptr, len)
446
            }
447
        }
448
    }
449

450

451
    function encodeBytes(bytes memory elem) internal pure returns (bytes memory) {
452
        return abi.encodePacked(
453
            encodeLength(elem.length, 0x80),
454
            elem
455
        );
456
    }
457

458
    function encodeUint(uint256 value) internal pure returns (bytes memory) {
459
        // allocate our result bytes
460
        bytes memory result = new bytes(33);
461
    
462
        if (value == 0) {
463
            // store length = 1, value = 0x80
464
            assembly {
465
                mstore(add(result, 1), 0x180)
466
            }
467
            return result;
468
        }
469
 
470
        if (value < 128) {
471
            // store length = 1, value = value
472
            assembly {
473
                mstore(add(result, 1), or(0x100, value))
474
            }
475
            return result;
476
        }
477
            
478
        if (value > 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff) {
479
            // length 33, prefix 0xa0 followed by value
480
            assembly {   
481
                mstore(add(result, 1), 0x21a0)
482
                mstore(add(result, 33), value)
483
            }
484
            return result;
485
        }
486
 
487
        if (value > 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff) {
488
            // length 32, prefix 0x9f followed by value
489
            assembly {
490
                mstore(add(result, 1), 0x209f)
491
                mstore(add(result, 33), shl(8, value))
492
            }
493
            return result;
494
        }
495
                 
496
        assembly {
497
            let length := 1
498
            for {
499
                let min := 0x100
500
            } lt(sub(min, 1), value) {
501
                min := shl(8, min)
502
            } {
503
                length := add(length, 1)
504
            }
505
                    
506
            let bytesLength := add(length, 1)
507
                    
508
            // bytes length field
509
            let hi := shl(mul(bytesLength, 8), bytesLength)
510
                    
511
            // rlp encoding of value
512
            let lo := or(shl(mul(length, 8), add(length, 0x80)), value)
513
                    
514
            mstore(add(result, bytesLength), or(hi, lo))
515
        }           
516
        return result;   
517
    }
518
}