| 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
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514 |
16×
14×
14×
12×
12×
12×
12×
12×
12×
30×
30×
30×
30×
30×
28×
26×
24×
164×
164×
164×
164×
132×
130×
130×
29×
162×
160×
158×
18×
18×
23×
17×
17×
15×
13×
11×
9×
9×
9×
9×
9×
7×
7×
4×
7×
120×
120×
120×
268×
268×
158×
110×
10×
4×
2×
2×
3×
2×
1×
2×
2×
2×
6×
1×
5×
1×
2×
10×
10×
10×
8×
6×
4×
2×
2×
2×
2×
1×
2×
2×
10×
11×
1×
10×
10×
10×
10×
10×
86×
10×
10×
86×
22×
22×
6×
5×
17×
16×
15×
14×
12×
12×
12×
12×
11×
9×
7×
2×
1×
1×
13×
1×
1×
1×
1×
5×
| pragma solidity ^0.5.10;
/** @title Relay */
/** @author Summa (https://summa.one) */
import {SafeMath} from "@summa-tx/bitcoin-spv-sol/contracts/SafeMath.sol";
import {BytesLib} from "@summa-tx/bitcoin-spv-sol/contracts/BytesLib.sol";
import {BTCUtils} from "@summa-tx/bitcoin-spv-sol/contracts/BTCUtils.sol";
import {ValidateSPV} from "@summa-tx/bitcoin-spv-sol/contracts/ValidateSPV.sol";
interface IRelay {
event Extension(bytes32 indexed _first, bytes32 indexed _last);
event Reorg(bytes32 indexed _from, bytes32 indexed _to, bytes32 indexed _gcd);
function isMostRecentAncestor(
bytes32 _ancestor,
bytes32 _left,
bytes32 _right,
uint256 _limit
) external view returns (bool);
function getCurrentEpochDifficulty() external view returns (uint256);
function getPrevEpochDifficulty() external view returns (uint256);
function getRelayGenesis() external view returns (bytes32);
function getBestKnownDigest() external view returns (bytes32);
function getLastReorgCommonAncestor() external view returns (bytes32);
function findHeight(bytes32 _digest) external view returns (uint256);
function findAncestor(bytes32 _digest, uint256 _offset) external view returns (bytes32);
function isAncestor(bytes32 _ancestor, bytes32 _descendant, uint256 _limit) external view returns (bool);
function heaviestFromAncestor(
bytes32 _ancestor,
bytes calldata _left,
bytes calldata _right
) external view returns (bytes32);
function addHeaders(bytes calldata _anchor, bytes calldata _headers) external returns (bool);
function addHeadersWithRetarget(
bytes calldata _oldPeriodStartHeader,
bytes calldata _oldPeriodEndHeader,
bytes calldata _headers
) external returns (bool);
function markNewHeaviest(
bytes32 _ancestor,
bytes calldata _currentBest,
bytes calldata _newBest,
uint256 _limit
) external returns (bool);
}
contract Relay is IRelay {
using SafeMath for uint256;
using BytesLib for bytes;
using BTCUtils for bytes;
using ValidateSPV for bytes;
// How often do we store the height?
// A higher number incurs less storage cost, but more lookup cost
uint32 public constant HEIGHT_INTERVAL = 4;
bytes32 internal relayGenesis;
bytes32 internal bestKnownDigest;
bytes32 internal lastReorgCommonAncestor;
mapping (bytes32 => bytes32) internal previousBlock;
mapping (bytes32 => uint256) internal blockHeight;
uint256 internal currentEpochDiff;
uint256 internal prevEpochDiff;
/// @notice Gives a starting point for the relay
/// @dev We don't check this AT ALL really. Don't use relays with bad genesis
/// @param _genesisHeader The starting header
/// @param _height The starting height
/// @param _periodStart The hash of the first header in the genesis epoch
constructor(bytes memory _genesisHeader, uint256 _height, bytes32 _periodStart) public {
require(_genesisHeader.length == 80, "Stop being dumb");
bytes32 _genesisDigest = _genesisHeader.hash256();
require(
_periodStart & bytes32(0x0000000000000000000000000000000000000000000000000000000000ffffff) == bytes32(0),
"Period start hash does not have work. Hint: wrong byte order?");
relayGenesis = _genesisDigest;
bestKnownDigest = _genesisDigest;
lastReorgCommonAncestor = _genesisDigest;
blockHeight[_genesisDigest] = _height;
blockHeight[_periodStart] = _height.sub(_height % 2016);
currentEpochDiff = _genesisHeader.extractDifficulty();
}
/// @notice Adds headers to storage after validating
/// @dev We check integrity and consistency of the header chain
/// @param _anchor The header immediately preceeding the new chain
/// @param _headers A tightly-packed list of new 80-byte Bitcoin headers to record
/// @param _internal True if called internally from addHeadersWithRetarget, false otherwise
/// @return True if successfully written, error otherwise
function _addHeaders(bytes memory _anchor, bytes memory _headers, bool _internal) internal returns (bool) {
uint256 _height;
bytes memory _header;
bytes32 _currentDigest;
bytes32 _previousDigest = _anchor.hash256();
uint256 _target = _headers.slice(0, 80).extractTarget();
uint256 _anchorHeight = _findHeight(_previousDigest); /* NB: errors if unknown */
require(
_internal || _anchor.extractTarget() == _target,
"Unexpected retarget on external call");
require(_headers.length % 80 == 0, "Header array length must be divisible by 80");
/*
NB:
1. check that the header has sufficient work
2. check that headers are in a coherent chain (no retargets, hash links good)
3. Store the block connection
4. Store the height
*/
for (uint256 i = 0; i < _headers.length / 80; i = i.add(1)) {
_header = _headers.slice(i.mul(80), 80);
_height = _anchorHeight.add(i + 1);
_currentDigest = _header.hash256();
/*
NB:
if the block is already authenticated, we don't need to a work check
Or write anything to state. This saves gas
*/
if (previousBlock[_currentDigest] == bytes32(0)) {
require(
abi.encodePacked(_currentDigest).reverseEndianness().bytesToUint() <= _target,
"Header work is insufficient");
previousBlock[_currentDigest] = _previousDigest;
if (_height % HEIGHT_INTERVAL == 0) {
/*
NB: We store the height only every 4th header to save gas
*/
blockHeight[_currentDigest] = _height;
}
}
/* NB: we do still need to make chain level checks tho */
require(_header.extractTarget() == _target, "Target changed unexpectedly");
require(_header.validateHeaderPrevHash(_previousDigest), "Headers do not form a consistent chain");
_previousDigest = _currentDigest;
}
emit Extension(
_anchor.hash256(),
_currentDigest);
return true;
}
/// @notice Adds headers to storage after validating
/// @dev We check integrity and consistency of the header chain
/// @param _anchor The header immediately preceeding the new chain
/// @param _headers A tightly-packed list of 80-byte Bitcoin headers
/// @return True if successfully written, error otherwise
function addHeaders(bytes calldata _anchor, bytes calldata _headers) external returns (bool) {
return _addHeaders(_anchor, _headers, false);
}
/// @notice Adds headers to storage, performs additional validation of retarget
/// @dev Checks the retarget, the heights, and the linkage
/// @param _oldPeriodStartHeader The first header in the difficulty period being closed
/// @param _oldPeriodEndHeader The last header in the difficulty period being closed
/// @param _headers A tightly-packed list of 80-byte Bitcoin headers
/// @return True if successfully written, error otherwise
function addHeadersWithRetarget(
bytes calldata _oldPeriodStartHeader,
bytes calldata _oldPeriodEndHeader,
bytes calldata _headers
) external returns (bool) {
return _addHeadersWithRetarget(_oldPeriodStartHeader, _oldPeriodEndHeader, _headers);
}
/// @notice Adds headers to storage, performs additional validation of retarget
/// @dev Checks the retarget, the heights, and the linkage
/// @param _oldPeriodStartHeader The first header in the difficulty period being closed
/// @param _oldPeriodEndHeader The last header in the difficulty period being closed
/// @param _headers A tightly-packed list of 80-byte Bitcoin headers
/// @return True if successfully written, error otherwise
function _addHeadersWithRetarget(
bytes memory _oldPeriodStartHeader,
bytes memory _oldPeriodEndHeader,
bytes memory _headers
) internal returns (bool) {
/* NB: requires that both blocks are known */
uint256 _startHeight = _findHeight(_oldPeriodStartHeader.hash256());
uint256 _endHeight = _findHeight(_oldPeriodEndHeader.hash256());
/* NB: retargets should happen at 2016 block intervals */
require(
_endHeight % 2016 == 2015,
"Must provide the last header of the closing difficulty period");
require(
_endHeight == _startHeight.add(2015),
"Must provide exactly 1 difficulty period");
Erequire(
_oldPeriodStartHeader.extractDifficulty() == _oldPeriodEndHeader.extractDifficulty(),
"Period header difficulties do not match");
/* NB: This comparison looks weird because header nBits encoding truncates targets */
bytes memory _newPeriodStart = _headers.slice(0, 80);
uint256 _actualTarget = _newPeriodStart.extractTarget();
uint256 _expectedTarget = BTCUtils.retargetAlgorithm(
_oldPeriodStartHeader.extractTarget(),
_oldPeriodStartHeader.extractTimestamp(),
_oldPeriodEndHeader.extractTimestamp()
);
require(
(_actualTarget & _expectedTarget) == _actualTarget,
"Invalid retarget provided");
// If the current known prevEpochDiff doesn't match, and this old period is near the chaintip/
// update the stored prevEpochDiff
// Don't update if this is a deep past epoch
uint256 _oldDiff = _oldPeriodStartHeader.extractDifficulty();
if (prevEpochDiff != _oldDiff && _endHeight > _findHeight(bestKnownDigest).sub(2016)) {
prevEpochDiff = _oldDiff;
}
// Pass all but the first through to be added
return _addHeaders(_oldPeriodEndHeader, _headers, true);
}
/// @notice Finds the height of a header by its digest
/// @dev Will fail if the header is unknown
/// @param _digest The header digest to search for
/// @return The height of the header
function _findHeight(bytes32 _digest) internal view returns (uint256) {
uint256 _height = 0;
bytes32 _current = _digest;
for (uint256 i = 0; i < HEIGHT_INTERVAL + 1; i = i.add(1)) {
_height = blockHeight[_current];
if (_height == 0) {
_current = previousBlock[_current];
} else {
return _height.add(i);
}
}
revert("Unknown block");
}
/// @notice Finds the height of a header by its digest
/// @dev Will fail if the header is unknown
/// @param _digest The header digest to search for
/// @return The height of the header, or error if unknown
function findHeight(bytes32 _digest) external view returns (uint256) {
return _findHeight(_digest);
}
/// @notice Finds an ancestor for a block by its digest
/// @dev Will fail if the header is unknown
/// @param _digest The header digest to search for
/// @return The height of the header, or error if unknown
function _findAncestor(bytes32 _digest, uint256 _offset) internal view returns (bytes32) {
bytes32 _current = _digest;
for (uint256 i = 0; i < _offset; i = i.add(1)) {
_current = previousBlock[_current];
}
require(_current != bytes32(0), "Unknown ancestor");
return _current;
}
/// @notice Finds an ancestor for a block by its digest
/// @dev Will fail if the header is unknown
/// @param _digest The header digest to search for
/// @return The height of the header, or error if unknown
function findAncestor(bytes32 _digest, uint256 _offset) external view returns (bytes32) {
return _findAncestor(_digest, _offset);
}
/// @notice Checks if a digest is an ancestor of the current one
/// @dev Limit the amount of lookups (and thus gas usage) with _limit
/// @param _ancestor The prospective ancestor
/// @param _descendant The descendant to check
/// @param _limit The maximum number of blocks to check
/// @return true if ancestor is at most limit blocks lower than descendant, otherwise false
function _isAncestor(bytes32 _ancestor, bytes32 _descendant, uint256 _limit) internal view returns (bool) {
bytes32 _current = _descendant;
/* NB: 200 gas/read, so gas is capped at ~200 * limit */
for (uint256 i = 0; i < _limit; i = i.add(1)) {
if (_current == _ancestor) {
return true;
}
_current = previousBlock[_current];
}
return false;
}
/// @notice Checks if a digest is an ancestor of the current one
/// @dev Limit the amount of lookups (and thus gas usage) with _limit
/// @param _ancestor The prospective ancestor
/// @param _descendant The descendant to check
/// @param _limit The maximum number of blocks to check
/// @return true if ancestor is at most limit blocks lower than descendant, otherwise false
function isAncestor(bytes32 _ancestor, bytes32 _descendant, uint256 _limit) external view returns (bool) {
return _isAncestor(_ancestor, _descendant, _limit);
}
/// @notice Gives a starting point for the relay
/// @dev We don't check this AT ALL really. Don't use relays with bad genesis
/// @param _ancestor The digest of the most recent common ancestor
/// @param _currentBest The 80-byte header referenced by bestKnownDigest
/// @param _newBest The 80-byte header to mark as the new best
/// @param _limit Limit the amount of traversal of the chain
/// @return True if successfully updates bestKnownDigest, error otherwise
function _markNewHeaviest(
bytes32 _ancestor,
bytes memory _currentBest,
bytes memory _newBest,
uint256 _limit
) internal returns (bool) {
bytes32 _newBestDigest = _newBest.hash256();
bytes32 _currentBestDigest = _currentBest.hash256();
require(_currentBestDigest == bestKnownDigest, "Passed in best is not best known");
require(
previousBlock[_newBestDigest] != bytes32(0),
"New best is unknown");
require(
_isMostRecentAncestor(_ancestor, bestKnownDigest, _newBestDigest, _limit),
"Ancestor must be heaviest common ancestor");
require(
_heaviestFromAncestor(_ancestor, _currentBest, _newBest) == _newBestDigest,
"New best hash does not have more work than previous");
bestKnownDigest = _newBestDigest;
lastReorgCommonAncestor = _ancestor;
uint256 _newDiff = _newBest.extractDifficulty();
if (_newDiff != currentEpochDiff) {
currentEpochDiff = _newDiff;
}
emit Reorg(
_currentBestDigest,
_newBestDigest,
_ancestor);
return true;
}
/// @notice Gives a starting point for the relay
/// @dev We don't check this AT ALL really. Don't use relays with bad genesis
/// @param _ancestor The digest of the most recent common ancestor
/// @param _currentBest The 80-byte header referenced by bestKnownDigest
/// @param _newBest The 80-byte header to mark as the new best
/// @param _limit Limit the amount of traversal of the chain
/// @return True if successfully updates bestKnownDigest, error otherwise
function markNewHeaviest(
bytes32 _ancestor,
bytes calldata _currentBest,
bytes calldata _newBest,
uint256 _limit
) external returns (bool) {
return _markNewHeaviest(_ancestor, _currentBest, _newBest, _limit);
}
/// @notice Checks if a digest is an ancestor of the current one
/// @dev Limit the amount of lookups (and thus gas usage) with _limit
/// @param _ancestor The prospective shared ancestor
/// @param _left A chain tip
/// @param _right A chain tip
/// @param _limit The maximum number of blocks to check
/// @return true if it is the most recent common ancestor within _limit, false otherwise
function _isMostRecentAncestor(
bytes32 _ancestor,
bytes32 _left,
bytes32 _right,
uint256 _limit
) internal view returns (bool) {
/* NB: sure why not */
if (_ancestor == _left && _ancestor == _right) {
return true;
}
bytes32 _leftCurrent = _left;
bytes32 _rightCurrent = _right;
bytes32 _leftPrev = _left;
bytes32 _rightPrev = _right;
for(uint256 i = 0; i < _limit; i = i.add(1)) {
if (_leftPrev != _ancestor) {
_leftCurrent = _leftPrev; // cheap
_leftPrev = previousBlock[_leftPrev]; // expensive
}
if (_rightPrev != _ancestor) {
_rightCurrent = _rightPrev; // cheap
_rightPrev = previousBlock[_rightPrev]; // expensive
}
}
if (_leftCurrent == _rightCurrent) {return false;} /* NB: If the same, they're a nearer ancestor */
if (_leftPrev != _rightPrev) {return false;} /* NB: Both must be ancestor */
return true;
}
/// @notice Checks if a digest is an ancestor of the current one
/// @dev Limit the amount of lookups (and thus gas usage) with _limit
/// @param _ancestor The prospective shared ancestor
/// @param _left A chain tip
/// @param _right A chain tip
/// @param _limit The maximum number of blocks to check
/// @return true if it is the most recent common ancestor within _limit, false otherwise
function isMostRecentAncestor(
bytes32 _ancestor,
bytes32 _left,
bytes32 _right,
uint256 _limit
) external view returns (bool) {
return _isMostRecentAncestor(_ancestor, _left, _right, _limit);
}
/// @notice Decides which header is heaviest from the ancestor
/// @dev Does not support reorgs above 2017 blocks (:
/// @param _ancestor The prospective shared ancestor
/// @param _left A chain tip
/// @param _right A chain tip
/// @return true if it is the most recent common ancestor within _limit, false otherwise
function _heaviestFromAncestor(
bytes32 _ancestor,
bytes memory _left,
bytes memory _right
) internal view returns (bytes32) {
uint256 _ancestorHeight = _findHeight(_ancestor);
uint256 _leftHeight = _findHeight(_left.hash256());
uint256 _rightHeight = _findHeight(_right.hash256());
require(
_leftHeight >= _ancestorHeight && _rightHeight >= _ancestorHeight,
"A descendant height is below the ancestor height");
/* NB: we can shortcut if one block is in a new difficulty window and the other isn't */
uint256 _nextPeriodStartHeight = _ancestorHeight.add(2016).sub(_ancestorHeight % 2016);
bool _leftInPeriod = _leftHeight < _nextPeriodStartHeight;
bool _rightInPeriod = _rightHeight < _nextPeriodStartHeight;
/*
NB:
1. Left is in a new window, right is in the old window. Left is heavier
2. Right is in a new window, left is in the old window. Right is heavier
3. Both are in the same window, choose the higher one
4. They're in different new windows. Choose the heavier one
*/
if (!_leftInPeriod && _rightInPeriod) {return _left.hash256();}
if (_leftInPeriod && !_rightInPeriod) {return _right.hash256();}
if (_leftInPeriod && _rightInPeriod) {
return _leftHeight >= _rightHeight ? _left.hash256() : _right.hash256();
} else { // if (!_leftInPeriod && !_rightInPeriod) {
if (((_leftHeight % 2016).mul(_left.extractDifficulty())) <
(_rightHeight % 2016).mul(_right.extractDifficulty())) {
return _right.hash256();
} else {
return _left.hash256();
}
}
}
/// @notice Decides which header is heaviest from the ancestor
/// @dev Does not support reorgs above 2017 blocks (:
/// @param _ancestor The prospective shared ancestor
/// @param _left A chain tip
/// @param _right A chain tip
/// @return true if it is the most recent common ancestor within _limit, false otherwise
function heaviestFromAncestor(
bytes32 _ancestor,
bytes calldata _left,
bytes calldata _right
) external view returns (bytes32) {
return _heaviestFromAncestor(_ancestor, _left, _right);
}
/// @notice Getter for currentEpochDiff
/// @dev This is updated when a new heavist header has a new diff
/// @return The difficulty of the bestKnownDigest
function getCurrentEpochDifficulty() external view returns (uint256) {
return currentEpochDiff;
}
/// @notice Getter for prevEpochDiff
/// @dev This is updated when a difficulty change is accepted
/// @return The difficulty of the previous epoch
function getPrevEpochDifficulty() external view returns (uint256) {
return prevEpochDiff;
}
/// @notice Getter for relayGenesis
/// @dev This is an initialization parameter
/// @return The hash of the first block of the relay
function getRelayGenesis() public view returns (bytes32) {
return relayGenesis;
}
/// @notice Getter for bestKnownDigest
/// @dev This updated only by calling markNewHeaviest
/// @return The hash of the best marked chain tip
function getBestKnownDigest() public view returns (bytes32) {
return bestKnownDigest;
}
/// @notice Getter for relayGenesis
/// @dev This is updated only by calling markNewHeaviest
/// @return The hash of the shared ancestor of the most recent fork
function getLastReorgCommonAncestor() public view returns (bytes32) {
return lastReorgCommonAncestor;
}
}
|