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
|
# Exists in state:
# (i) last committed block
# (ii) chain of uncommitted blocks (linear only)
# (iii) transactions, each tx with an associated block number
#
# Uncommitted block =
# [ numtxs, numkvs, tx1 (N words), tx2 (N words) ..., [k1, v1], [k2, v2], [k3, v3] ... ]
#
# Block checking process
#
# Suppose last committed state is m
# Last uncommitted state is n
# Contested block is b
#
# 1. Temporarily apply all state transitions from
# m to b
# 2. Run code, get list of changes
# 3. Check is list of changes matches deltas
# * if yes, do nothing
# * if no, set last uncommitted state to pre-b
#
# Storage variables:
#
# Last committed block: 0
# Last uncommitted block: 1
# Contract holding code: 2
# Uncommitted map: 3
# Transaction length (parameter): 4
# Block b: 2^160 + b * 2^40:
# + 1: submission blknum
# + 2: submitter
# + 3: data in uncommitted block format above
# Last committed storage:
# sha3(k): index k
# Initialize: [0, c, txlength], set address of the code-holding contract and the transaction
# length
if not contract.storage[2]:
contract.storage[2] = msg.data[1]
contract.storage[4] = msg.data[2]
stop
# Sequentially commit all uncommitted blocks that are more than 1000 mainchain-blocks old
last_committed_block = contract.storage[0]
last_uncommitted_block = contract.storage[1]
lcb_storage_index = 2^160 + last_committed_block * 2^40
while contract.storage[lcb_storage_index + 1] < block.number - 1000 and last_committed_block < last_uncommitted_block:
kvpairs = contract.storage[lcb_storage_index]
i = 0
while i < kvpairs:
k = contract.storage[lcb_storage_index + 3 + i * 2]
v = contract.storage[lcb_storage_index + 4 + i * 2]
contract.storage[sha3(k)] = v
i += 1
last_committed_block += 1
lcb_storage_index += 2^40
contract.storage[0] = last_committed_block
# Propose block: [ 0, block number, data in block format above ... ]
if msg.data[0] == 0:
blknumber = msg.data[1]
# Block number must be correct
if blknumber != contract.storage[1]:
stop
# Deposit requirement
if msg.value < 10^19:
stop
# Store the proposal in storage as
# [ 0, main-chain block number, sender, block data...]
start_index = 2^160 + blknumber * 2^40
numkvs = (msg.datasize - 2) / 2
contract.storage[start_index + 1] = block.number
1ontract.storage[start_index + 2] = msg.sender
i = 0
while i < msg.datasize - 2:
contract.storage[start_index + 3 + i] = msg.data[2 + i]
i += 1
contract.storage[1] = blknumber + 1
# Challenge block: [ 1, b ]
elif msg.data[0] == 1:
blknumber = msg.data[1]
txwidth = contract.storage[4]
last_uncommitted_block = contract.storage[1]
last_committed_block = contract.storage[0]
# Cannot challenge nonexistent or committed blocks
if blknumber <= last_uncommitted_block or blknumber > last_committed_block:
stop
# Create a contract to serve as a map that maintains keys and values
# temporarily
tempstore = create('map.se')
contract.storage[3] = tempstore
# Unquestioningly apply the state transitions from the last committed block
# up to b
b = last_committed_block
cur_storage_index = 2^160 + last_committed_block * 2^40
while b < blknumber:
numtxs = contract.storage[cur_storage_index + 3]
numkvs = contract.storage[cur_storage_index + 4]
kv0index = cur_storage_index + 5 + numtxs * txwidth
i = 0
while i < numkvs:
k = contract.storage[kv0index + i * 2]
v = contract.storage[kx0index + i * 2 + 1]
call(tempstore, [1, k, v], 3)
i += 1
b += 1
cur_storage_index += 2^40
# Run the actual code, and see what state transitions it outputs
# The way that the code is expected to work is to:
#
# (1) take as input the list of transactions (the contract should
# use msg.datasize to determine how many txs there are, and it should
# be aware of the value of txwidth)
# (2) call this contract with [2, k] to read current state data
# (3) call this contract with [3, k, v] to write current state data
# (4) return as output a list of all state transitions that it made
# in the form [kvcount, k1, v1, k2, v2 ... ]
#
# The reason for separating (2) from (3) is that sometimes the state
# transition may end up changing a given key many times, and we don't
# need to inefficiently store that in storage
numkvs = contract.storage[cur_storage_index + 3]
numtxs = contract.storage[cur_storage_index + 4]
# Populate input array
inpwidth = numtxs * txwidth
inp = array(inpwidth)
i = 0
while i < inpwidth:
inp[i] = contract.storage[cur_storage_index + 5 + i]
i += 1
out = call(contract.storage[2], inp, inpwidth, numkvs * 2 + 1)
# Check that the number of state transitions is the same
if out[0] != kvcount:
send(msg.sender, 10^19)
contract.storage[0] = last_committed_block
stop
kv0index = cur_storage_index + 5 + numtxs * txwidth
i = 0
while i < kvcount:
# Check that each individual state transition matches
k = contract.storage[kv0index + i * 2 + 1]
v = contract.storage[kv0index + i * 2 + 2]
if k != out[i * 2 + 1] or v != out[i * 2 + 2]:
send(msg.sender, 10^19)
contract.storage[0] = last_committed_block
stop
i += 1
# Suicide tempstore
call(tempstore, 2)
# Read data [2, k]
elif msg.data[0] == 2:
tempstore = contract.storage[3]
o = call(tempstore, [0, msg.data[1]], 2, 2)
if o[0]:
return(o[1])
else:
return contract.storage[sha3(msg.data[1])]
# Write data [3, k, v]
elif msg.data[0] == 3:
tempstore = contract.storage[3]
call(tempstore, [1, msg.data[1], msg.data[2]], 3, 2)
|
