Ton

1
/*
2
    This file is part of TON Blockchain Library.
3

4
    TON Blockchain Library is free software: you can redistribute it and/or modify
5
    it under the terms of the GNU Lesser General Public License as published by
6
    the Free Software Foundation, either version 2 of the License, or
7
    (at your option) any later version.
8

9
    TON Blockchain Library is distributed in the hope that it will be useful,
10
    but WITHOUT ANY WARRANTY; without even the implied warranty of
11
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
    GNU Lesser General Public License for more details.
13

14
    You should have received a copy of the GNU Lesser General Public License
15
    along with TON Blockchain Library.  If not, see <http://www.gnu.org/licenses/>.
16

17
    Copyright 2017-2020 Telegram Systems LLP
18
*/
19
#include "check-proof.h"
20
#include "block/block.h"
21
#include "block/block-parse.h"
22
#include "block/block-auto.h"
23
#include "block/mc-config.h"
24

25
#include "ton/ton-shard.h"
26

27
#include "vm/cells/MerkleProof.h"
28
#include "openssl/digest.hpp"
29
#include "Ed25519.h"
30

31
namespace block {
32
using namespace std::literals::string_literals;
33

34
td::Status check_block_header_proof(td::Ref<vm::Cell> root, ton::BlockIdExt blkid, ton::Bits256* store_state_hash_to,
35
                                    bool check_state_hash, td::uint32* save_utime, ton::LogicalTime* save_lt) {
36
  ton::RootHash vhash{root->get_hash().bits()};
37
  if (vhash != blkid.root_hash) {
38
    return td::Status::Error(PSTRING() << " block header for block " << blkid.to_str() << " has incorrect root hash "
39
                                       << vhash.to_hex() << " instead of " << blkid.root_hash.to_hex());
40
  }
41
  std::vector<ton::BlockIdExt> prev;
42
  ton::BlockIdExt mc_blkid;
43
  bool after_split;
44
  TRY_STATUS(block::unpack_block_prev_blk_try(root, blkid, prev, mc_blkid, after_split));
45
  block::gen::Block::Record blk;
46
  block::gen::BlockInfo::Record info;
47
  if (!(tlb::unpack_cell(root, blk) && tlb::unpack_cell(blk.info, info))) {
48
    return td::Status::Error(std::string{"cannot unpack header for block "} + blkid.to_str());
49
  }
50
  if (save_utime) {
51
    *save_utime = info.gen_utime;
52
  }
53
  if (save_lt) {
54
    *save_lt = info.end_lt;
55
  }
56
  if (store_state_hash_to) {
57
    vm::CellSlice upd_cs{vm::NoVmSpec(), blk.state_update};
58
    if (!(upd_cs.is_special() && upd_cs.prefetch_long(8) == 4  // merkle update
59
          && upd_cs.size_ext() == 0x20228)) {
60
      return td::Status::Error("invalid Merkle update in block header");
61
    }
62
    auto upd_hash = upd_cs.prefetch_ref(1)->get_hash(0);
63
    if (!check_state_hash) {
64
      *store_state_hash_to = upd_hash.bits();
65
    } else if (store_state_hash_to->compare(upd_hash.bits())) {
66
      return td::Status::Error(PSTRING() << "state hash mismatch in block header of " << blkid.to_str()
67
                                         << " : header declares " << upd_hash.bits().to_hex(256) << " expected "
68
                                         << store_state_hash_to->to_hex());
69
    }
70
  }
71
  return td::Status::OK();
72
}
73

74
td::Result<td::Bits256> check_state_proof(ton::BlockIdExt blkid, td::Slice proof) {
75
  TRY_RESULT(proof_root, vm::std_boc_deserialize(proof));
76
  auto virt_root = vm::MerkleProof::virtualize(std::move(proof_root), 1);
77
  if (virt_root.is_null()) {
78
    return td::Status::Error("account state proof is invalid");
79
  }
80
  td::Bits256 state_hash;
81
  TRY_STATUS(check_block_header_proof(std::move(virt_root), blkid, &state_hash));
82
  return state_hash;
83
}
84

85
td::Result<Ref<vm::Cell>> check_extract_state_proof(ton::BlockIdExt blkid, td::Slice proof, td::Slice data) {
86
  try {
87
    TRY_RESULT(state_hash, check_state_proof(blkid, proof));
88
    TRY_RESULT(state_root, vm::std_boc_deserialize(data));
89
    auto state_virt_root = vm::MerkleProof::virtualize(std::move(state_root), 1);
90
    if (state_virt_root.is_null()) {
91
      return td::Status::Error("account state proof is invalid");
92
    }
93
    if (state_hash != state_virt_root->get_hash().bits()) {
94
      return td::Status::Error("root hash mismatch in the shardchain state proof");
95
    }
96
    return std::move(state_virt_root);
97
  } catch (vm::VmError& err) {
98
    return td::Status::Error(PSLICE() << "error scanning shard state proof: " << err.get_msg());
99
  } catch (vm::VmVirtError& err) {
100
    return td::Status::Error(PSLICE() << "virtualization error scanning shard state proof: " << err.get_msg());
101
  }
102
}
103

104
td::Status check_shard_proof(ton::BlockIdExt blk, ton::BlockIdExt shard_blk, td::Slice shard_proof) {
105
  if (blk == shard_blk) {
106
    if (!shard_proof.empty()) {
107
      LOG(WARNING) << "Unexpected non-empty shard proof";
108
    }
109
    return td::Status::OK();
110
  }
111
  if (!blk.is_masterchain() || !blk.is_valid_full()) {
112
    return td::Status::Error(PSLICE() << "reference block " << blk.to_str()
113
                                      << " for a getAccountState query must belong to the masterchain");
114
  }
115
  TRY_RESULT_PREFIX(P_roots, vm::std_boc_deserialize_multi(std::move(shard_proof)),
116
                    "cannot deserialize shard configuration proof");
117
  if (P_roots.size() != 2) {
118
    return td::Status::Error("shard configuration proof must have exactly two roots");
119
  }
120
  try {
121
    auto mc_state_root = vm::MerkleProof::virtualize(std::move(P_roots[1]), 1);
122
    if (mc_state_root.is_null()) {
123
      return td::Status::Error("shard configuration proof is invalid");
124
    }
125
    ton::Bits256 mc_state_hash = mc_state_root->get_hash().bits();
126
    TRY_STATUS_PREFIX(
127
        check_block_header_proof(vm::MerkleProof::virtualize(std::move(P_roots[0]), 1), blk, &mc_state_hash, true),
128
        "error in shard configuration block header proof :");
129
    block::gen::ShardStateUnsplit::Record sstate;
130
    if (!(tlb::unpack_cell(mc_state_root, sstate))) {
131
      return td::Status::Error("cannot unpack masterchain state header");
132
    }
133
    auto shards_dict = block::ShardConfig::extract_shard_hashes_dict(std::move(mc_state_root));
134
    if (!shards_dict) {
135
      return td::Status::Error("cannot extract shard configuration dictionary from proof");
136
    }
137
    vm::CellSlice cs;
138
    ton::ShardIdFull true_shard;
139
    if (!block::ShardConfig::get_shard_hash_raw_from(*shards_dict, cs, shard_blk.shard_full(), true_shard)) {
140
      return td::Status::Error(PSLICE() << "masterchain state contains no information for shard "
141
                                        << shard_blk.shard_full().to_str());
142
    }
143
    auto shard_info = block::McShardHash::unpack(cs, true_shard);
144
    if (shard_info.is_null()) {
145
      return td::Status::Error(PSLICE() << "cannot unpack information for shard " << shard_blk.shard_full().to_str()
146
                                        << " from masterchain state");
147
    }
148
    if (shard_info->top_block_id() != shard_blk) {
149
      return td::Status::Error(PSLICE() << "shard configuration mismatch: expected to find block " << shard_blk.to_str()
150
                                        << " , found " << shard_info->top_block_id().to_str());
151
    }
152
  } catch (vm::VmError err) {
153
    return td::Status::Error(PSLICE() << "error while traversing shard configuration proof : " << err.get_msg());
154
  } catch (vm::VmVirtError err) {
155
    return td::Status::Error(PSLICE() << "virtualization error while traversing shard configuration proof : "
156
                                      << err.get_msg());
157
  }
158
  return td::Status::OK();
159
}
160

161
td::Status check_account_proof(td::Slice proof, ton::BlockIdExt shard_blk, const block::StdAddress& addr,
162
                               td::Ref<vm::Cell> root, ton::LogicalTime* last_trans_lt, ton::Bits256* last_trans_hash,
163
                               td::uint32* save_utime, ton::LogicalTime* save_lt) {
164
  TRY_RESULT_PREFIX(Q_roots, vm::std_boc_deserialize_multi(std::move(proof)), "cannot deserialize account proof");
165
  if (Q_roots.size() != 2) {
166
    return td::Status::Error(PSLICE() << "account state proof must have exactly two roots");
167
  }
168

169
  if (last_trans_lt) {
170
    last_trans_hash->set_zero();
171
  }
172

173
  try {
174
    auto state_root = vm::MerkleProof::virtualize(std::move(Q_roots[1]), 1);
175
    if (state_root.is_null()) {
176
      return td::Status::Error("account state proof is invalid");
177
    }
178
    ton::Bits256 state_hash = state_root->get_hash().bits();
179
    TRY_STATUS_PREFIX(check_block_header_proof(vm::MerkleProof::virtualize(std::move(Q_roots[0]), 1), shard_blk,
180
                                               &state_hash, true, save_utime, save_lt),
181
                      "error in account shard block header proof : ");
182
    block::gen::ShardStateUnsplit::Record sstate;
183
    if (!(tlb::unpack_cell(std::move(state_root), sstate))) {
184
      return td::Status::Error("cannot unpack state header");
185
    }
186
    vm::AugmentedDictionary accounts_dict{vm::load_cell_slice(sstate.accounts).prefetch_ref(), 256,
187
                                          block::tlb::aug_ShardAccounts};
188
    auto acc_csr = accounts_dict.lookup(addr.addr);
189
    if (acc_csr.not_null()) {
190
      if (root.is_null()) {
191
        return td::Status::Error(PSLICE() << "account state proof shows that account state for " << addr
192
                                          << " must be non-empty, but it actually is empty");
193
      }
194
      block::gen::ShardAccount::Record acc_info;
195
      if (!tlb::csr_unpack(std::move(acc_csr), acc_info)) {
196
        return td::Status::Error("cannot unpack ShardAccount from proof");
197
      }
198
      if (acc_info.account->get_hash().bits().compare(root->get_hash().bits(), 256)) {
199
        return td::Status::Error(PSLICE() << "account state hash mismatch: Merkle proof expects "
200
                                          << acc_info.account->get_hash().bits().to_hex(256)
201
                                          << " but received data has " << root->get_hash().bits().to_hex(256));
202
      }
203
      if (last_trans_hash) {
204
        *last_trans_hash = acc_info.last_trans_hash;
205
      }
206
      if (last_trans_lt) {
207
        *last_trans_lt = acc_info.last_trans_lt;
208
      }
209
    } else if (root.not_null()) {
210
      return td::Status::Error(PSLICE() << "account state proof shows that account state for " << addr
211
                                        << " must be empty, but it is not");
212
    }
213
  } catch (vm::VmError err) {
214
    return td::Status::Error(PSLICE() << "error while traversing account proof : " << err.get_msg());
215
  } catch (vm::VmVirtError err) {
216
    return td::Status::Error(PSLICE() << "virtualization error while traversing account proof : " << err.get_msg());
217
  }
218
  return td::Status::OK();
219
}
220

221
td::Result<AccountState::Info> AccountState::validate(ton::BlockIdExt ref_blk, block::StdAddress addr) const {
222
  TRY_RESULT_PREFIX(true_root, vm::std_boc_deserialize(state.as_slice(), true), "cannot deserialize account state");
223
  Ref<vm::Cell> root;
224

225
  if (is_virtualized && true_root.not_null()) {
226
    root = vm::MerkleProof::virtualize(true_root, 1);
227
    if (root.is_null()) {
228
      return td::Status::Error("account state proof is invalid");
229
    }
230
  } else {
231
    root = true_root;
232
  }
233

234
  if (blk != ref_blk && ref_blk.id.seqno != ~0U) {
235
    return td::Status::Error(PSLICE() << "obtained getAccountState() for a different reference block " << blk.to_str()
236
                                      << " instead of requested " << ref_blk.to_str());
237
  }
238

239
  if (!shard_blk.is_valid_full()) {
240
    return td::Status::Error(PSLICE() << "shard block id " << shard_blk.to_str() << " in answer is invalid");
241
  }
242

243
  if (!ton::shard_contains(shard_blk.shard_full(), ton::extract_addr_prefix(addr.workchain, addr.addr))) {
244
    return td::Status::Error(PSLICE() << "received data from shard block " << shard_blk.to_str()
245
                                      << " that cannot contain requested account");
246
  }
247

248
  TRY_STATUS(block::check_shard_proof(blk, shard_blk, shard_proof.as_slice()));
249

250
  Info res;
251
  TRY_STATUS(block::check_account_proof(proof.as_slice(), shard_blk, addr, root, &res.last_trans_lt,
252
                                        &res.last_trans_hash, &res.gen_utime, &res.gen_lt));
253
  res.root = std::move(root);
254
  res.true_root = std::move(true_root);
255

256
  return res;
257
}
258

259
td::Result<Transaction::Info> Transaction::validate() {
260
  if (root.is_null()) {
261
    return td::Status::Error("transactions are expected to be non-empty");
262
  }
263
  if (hash != root->get_hash().bits()) {
264
    return td::Status::Error(PSLICE() << "transaction hash mismatch: expected " << hash.to_hex() << ", found "
265
                                      << root->get_hash().bits().to_hex(256));
266
  }
267
  block::gen::Transaction::Record trans;
268
  if (!tlb::unpack_cell(root, trans)) {
269
    return td::Status::Error("cannot unpack transaction #");
270
  }
271

272
  if (trans.lt != lt) {
273
    return td::Status::Error(PSLICE() << "transaction lt mismatch: expected " << lt << ", found " << trans.lt);
274
  }
275
  Info res;
276
  res.blkid = blkid;
277
  res.now = trans.now;
278
  res.prev_trans_lt = trans.prev_trans_lt;
279
  res.prev_trans_hash = trans.prev_trans_hash;
280
  res.transaction = root;
281
  return std::move(res);
282
}
283

284
td::Result<TransactionList::Info> TransactionList::validate() const {
285
  if (blkids.empty()) {
286
    return td::Status::Error("transaction list must be non-empty");
287
  }
288
  auto R = vm::std_boc_deserialize_multi(std::move(transactions_boc));
289
  if (R.is_error()) {
290
    return td::Status::Error("cannot deserialize transactions BoC");
291
  }
292
  auto list = R.move_as_ok();
293
  if (list.size() != blkids.size()) {
294
    return td::Status::Error(PSLICE() << "transaction list size " << list.size()
295
                                      << " must be equal to the size of block id list " << blkids.size());
296
  }
297
  size_t c = 0;
298
  Info res;
299
  auto current_lt = lt;
300
  auto current_hash = hash;
301
  res.lt = lt;
302
  res.hash = hash;
303
  for (auto& root : list) {
304
    const auto& blkid = blkids[c++];
305
    Transaction transaction;
306
    transaction.blkid = std::move(blkid);
307
    transaction.lt = current_lt;
308
    transaction.hash = current_hash;
309
    transaction.root = root;
310
    TRY_RESULT(info, transaction.validate());
311
    current_lt = info.prev_trans_lt;
312
    current_hash = info.prev_trans_hash;
313
    res.transactions.push_back(std::move(info));
314
  }
315
  return std::move(res);
316
}
317

318
td::Result<BlockTransaction::Info> BlockTransaction::validate(bool check_proof) const {
319
  if (root.is_null()) {
320
    return td::Status::Error("transactions are expected to be non-empty");
321
  }
322
  if (check_proof && proof->get_hash().bits().compare(root->get_hash().bits(), 256)) {
323
    return td::Status::Error(PSLICE() << "transaction hash mismatch: Merkle proof expects "
324
                                      << proof->get_hash().bits().to_hex(256)
325
                                      << " but received data has " << root->get_hash().bits().to_hex(256));
326
  }
327
  block::gen::Transaction::Record trans;
328
  if (!tlb::unpack_cell(root, trans)) {
329
    return td::Status::Error("cannot unpack transaction cell");
330
  }
331
  Info res;
332
  res.blkid = blkid;
333
  res.now = trans.now;
334
  res.lt = trans.lt;
335
  res.hash = root->get_hash().bits();
336
  res.transaction = root;
337
  return std::move(res);
338
}
339

340
td::Result<BlockTransactionList::Info> BlockTransactionList::validate(bool check_proof) const {
341
  constexpr int max_answer_transactions = 256;
342

343
  TRY_RESULT_PREFIX(list, vm::std_boc_deserialize_multi(std::move(transactions_boc)), "cannot deserialize transactions boc: ");  
344
  std::vector<td::Ref<vm::Cell>> tx_proofs(list.size());
345

346
  if (check_proof) {
347
    try {
348
      TRY_RESULT(proof_cell, vm::std_boc_deserialize(std::move(proof_boc)));
349
      auto virt_root = vm::MerkleProof::virtualize(proof_cell, 1);
350

351
      if (blkid.root_hash != virt_root->get_hash().bits()) {
352
        return td::Status::Error("Invalid block proof root hash");
353
      }
354
      block::gen::Block::Record blk;
355
      block::gen::BlockExtra::Record extra;
356
      if (!(tlb::unpack_cell(virt_root, blk) && tlb::unpack_cell(std::move(blk.extra), extra))) {
357
        return td::Status::Error("Error unpacking proof cell");
358
      }
359
      vm::AugmentedDictionary acc_dict{vm::load_cell_slice_ref(extra.account_blocks), 256,
360
                  block::tlb::aug_ShardAccountBlocks};
361

362
      bool eof = false;
363
      ton::LogicalTime reverse = reverse_mode ? ~0ULL : 0;
364
      ton::LogicalTime trans_lt = static_cast<ton::LogicalTime>(start_lt);
365
      td::Bits256 cur_addr = start_addr;
366
      bool allow_same = true;
367
      int count = 0;
368
      while (!eof && count < req_count && count < max_answer_transactions) {
369
        auto value = acc_dict.extract_value(
370
              acc_dict.vm::DictionaryFixed::lookup_nearest_key(cur_addr.bits(), 256, !reverse, allow_same));
371
        if (value.is_null()) {
372
          eof = true;
373
          break;
374
        }
375
        allow_same = false;
376
        if (cur_addr != start_addr) {
377
          trans_lt = reverse;
378
        }
379

380
        block::gen::AccountBlock::Record acc_blk;
381
        if (!tlb::csr_unpack(std::move(value), acc_blk) || acc_blk.account_addr != cur_addr) {
382
          return td::Status::Error("Error unpacking proof account block");
383
        }
384
        vm::AugmentedDictionary trans_dict{vm::DictNonEmpty(), std::move(acc_blk.transactions), 64,
385
                    block::tlb::aug_AccountTransactions};
386
        td::BitArray<64> cur_trans{(long long)trans_lt};
387
        while (count < req_count && count < max_answer_transactions) {
388
          auto tvalue = trans_dict.extract_value_ref(
389
                trans_dict.vm::DictionaryFixed::lookup_nearest_key(cur_trans.bits(), 64, !reverse));
390
          if (tvalue.is_null()) {
391
            trans_lt = reverse;
392
            break;
393
          }
394
          if (static_cast<size_t>(count) < tx_proofs.size()) {
395
            tx_proofs[count] = std::move(tvalue);
396
          }
397
          count++;
398
        }
399
      }
400
      if (static_cast<size_t>(count) != list.size()) {
401
        return td::Status::Error(PSLICE() << "Txs count mismatch in proof (" << count << ") and response (" << list.size() << ")");
402
      }
403
    } catch (vm::VmError& err) {
404
      return err.as_status("Couldn't verify proof: ");
405
    } catch (vm::VmVirtError& err) {
406
      return err.as_status("Couldn't verify proof: ");
407
    } catch (...) {
408
      return td::Status::Error("Unknown exception raised while verifying proof");
409
    }
410
  }
411

412
  Info res;
413
  for (int i = 0; i < static_cast<int>(list.size()); i++) {
414
    auto& root = list[i];
415
    BlockTransaction transaction;
416
    transaction.root = root;
417
    transaction.blkid = blkid;
418
    transaction.proof = tx_proofs[i];
419
    TRY_RESULT(info, transaction.validate(check_proof));
420
    res.transactions.push_back(std::move(info));
421
  }
422
  return std::move(res);
423
}
424

425
td::Status BlockProofLink::validate(td::uint32* save_utime) const {
426
  if (save_utime) {
427
    *save_utime = 0;
428
  }
429
  if (!(from.is_masterchain_ext() && to.is_masterchain_ext())) {
430
    return td::Status::Error("BlockProofLink must have both source and destination blocks in the masterchain");
431
  }
432
  if (from.seqno() == to.seqno()) {
433
    return td::Status::Error("BlockProofLink connects two masterchain blocks "s + from.to_str() + " and " +
434
                             to.to_str() + " of equal height");
435
  }
436
  if (is_fwd != (from.seqno() < to.seqno())) {
437
    return td::Status::Error("BlockProofLink from "s + from.to_str() + " to " + to.to_str() +
438
                             " is incorrectly declared as a " + (is_fwd ? "forward" : "backward") + " link");
439
  }
440
  if (dest_proof.is_null() && to.seqno()) {
441
    return td::Status::Error("BlockProofLink contains no proof for destination block "s + to.to_str());
442
  }
443
  if (proof.is_null()) {
444
    return td::Status::Error("BlockProofLink contains no proof for source block "s + from.to_str());
445
  }
446
  if (!is_fwd && state_proof.is_null()) {
447
    return td::Status::Error("a backward BlockProofLink contains no proof for the source state of "s + from.to_str());
448
  }
449
  if (is_fwd && signatures.empty()) {
450
    return td::Status::Error("a forward BlockProofLink from "s + from.to_str() + " to " + to.to_str() +
451
                             " contains no signatures");
452
  }
453
  try {
454
    // virtualize Merkle proof roots
455
    auto vs_root = vm::MerkleProof::virtualize(proof, 1);
456
    if (vs_root.is_null()) {
457
      return td::Status::Error("BlockProofLink contains an invalid Merkle proof for source block "s + from.to_str());
458
    }
459
    ton::Bits256 state_hash;
460
    if (from.seqno()) {
461
      TRY_STATUS(check_block_header(vs_root, from, is_fwd ? nullptr : &state_hash));
462
    }
463
    auto vd_root = dest_proof.not_null() ? vm::MerkleProof::virtualize(dest_proof, 1) : Ref<vm::Cell>{};
464
    if (vd_root.is_null() && to.seqno()) {
465
      return td::Status::Error("BlockProofLink contains an invalid Merkle proof for destination block "s + to.to_str());
466
    }
467
    block::gen::Block::Record blk;
468
    block::gen::BlockInfo::Record info;
469
    if (to.seqno()) {
470
      TRY_STATUS(check_block_header(vd_root, to));
471
      if (!(tlb::unpack_cell(vd_root, blk) && tlb::unpack_cell(blk.info, info))) {
472
        return td::Status::Error("cannot unpack header for block "s + to.to_str());
473
      }
474
      if (info.key_block != is_key) {
475
        return td::Status::Error(PSTRING() << "incorrect is_key_block value " << is_key << " for destination block "
476
                                           << to.to_str());
477
      }
478
      if (save_utime) {
479
        *save_utime = info.gen_utime;
480
      }
481
    } else if (!is_key) {
482
      // return td::Status::Error("Zerostate destination block "s + to.to_str() + " does not have is_key_block set");
483
    }
484
    if (!is_fwd) {
485
      // check a backward link
486
      auto vstate_root = vm::MerkleProof::virtualize(state_proof, 1);
487
      if (vstate_root.is_null()) {
488
        return td::Status::Error("backward BlockProofLink contains an invalid Merkle proof for source state "s +
489
                                 from.to_str());
490
      }
491
      if (state_hash != vstate_root->get_hash().bits()) {
492
        return td::Status::Error("BlockProofLink contains a state proof for "s + from.to_str() +
493
                                 " with incorrect root hash");
494
      }
495
      TRY_RESULT(config, block::ConfigInfo::extract_config(vstate_root, block::ConfigInfo::needPrevBlocks));
496
      if (!config->check_old_mc_block_id(to, true)) {
497
        return td::Status::Error("cannot check that "s + to.to_str() + " is indeed a previous masterchain block of " +
498
                                 from.to_str() + " using the presented Merkle proof of masterchain state");
499
      }
500
      return td::Status::OK();
501
    } else {
502
      // check a forward link
503
      // extract configuration from source key block or zerostate
504
      auto cfg_res = from.seqno() ? block::Config::extract_from_key_block(vs_root, block::ConfigInfo::needValidatorSet)
505
                                  : block::Config::extract_from_state(vs_root, block::ConfigInfo::needValidatorSet);
506
      if (cfg_res.is_error()) {
507
        return td::Status::Error("cannot extract configuration from source key block "s + from.to_str() +
508
                                 " of a forward BlockProofLink: " + cfg_res.move_as_error().to_string());
509
      }
510
      auto config = cfg_res.move_as_ok();
511
      // compute validator set
512
      ton::ShardIdFull shard{ton::masterchainId};
513
      auto nodes = config->compute_validator_set(shard, info.gen_utime, info.gen_catchain_seqno);
514
      if (nodes.empty()) {
515
        return td::Status::Error(PSTRING()
516
                                 << "while checking a forward BlockProofLink: cannot compute validator set for block "
517
                                 << to.to_str() << " with utime " << info.gen_utime << " and cc_seqno "
518
                                 << info.gen_catchain_seqno << " starting from previous key block " << from.to_str());
519
      }
520
      // check computed validator set hash
521
      auto vset_hash = compute_validator_set_hash(cc_seqno, shard, nodes);
522
      if (vset_hash != info.gen_validator_list_hash_short) {
523
        return td::Status::Error(
524
            PSTRING() << "while checking a forward BlockProofLink: computed validator set for block " << to.to_str()
525
                      << " with utime " << info.gen_utime << " and cc_seqno " << info.gen_catchain_seqno
526
                      << " starting from previous key block " << from.to_str() << " has hash " << vset_hash
527
                      << " different from " << info.gen_validator_list_hash_short << " stated in block header");
528
      }
529
      // check signatures
530
      auto err = check_block_signatures(nodes, signatures, to);
531
      if (err.is_error()) {
532
        return td::Status::Error("error checking signatures for block "s + to.to_str() +
533
                                 " in a forward BlockProofLink: " + err.to_string());
534
      }
535
      return td::Status::OK();
536
    }
537
  } catch (vm::VmError& err) {
538
    return td::Status::Error("vm error while checking BlockProofLink from "s + from.to_str() + " to " + to.to_str() +
539
                             " : " + err.get_msg());
540
  } catch (vm::VmVirtError& err) {
541
    return td::Status::Error("virtualization error while checking BlockProofLink from "s + from.to_str() + " to " +
542
                             to.to_str() + " : " + err.get_msg());
543
  }
544
}
545

546
td::Status BlockProofChain::validate(td::CancellationToken cancellation_token) {
547
  valid = false;
548
  has_key_block = false;
549
  has_utime = false;
550
  last_utime = 0;
551
  key_blkid.invalidate();
552
  if (!(from.is_masterchain_ext() && to.is_masterchain_ext())) {
553
    return td::Status::Error("BlockProofChain must have both source and destination blocks in the masterchain");
554
  }
555
  if (!link_count()) {
556
    if (from != to) {
557
      return td::Status::Error("BlockProofChain has no links, but its source block "s + from.to_str() +
558
                               " and destination block " + to.to_str() + " differ");
559
    }
560
    valid = true;
561
    return td::Status::OK();
562
  }
563
  ton::BlockIdExt cur = from;
564
  int i = 0;
565
  for (const auto& link : links) {
566
    ++i;
567
    if (link.from != cur) {
568
      return td::Status::Error(PSTRING() << "link #" << i << " in a BlockProofChain begins with block "
569
                                         << link.from.to_str() << " but the previous link ends at different block "
570
                                         << cur.to_str());
571
    }
572
    if (cancellation_token) {
573
      return td::Status::Error("Cancelled");
574
    }
575
    auto err = link.validate(&last_utime);
576
    if (err.is_error()) {
577
      return td::Status::Error(PSTRING() << "link #" << i << " in BlockProofChain is invalid: " << err.to_string());
578
    }
579
    if (link.is_key && (!has_key_block || key_blkid.seqno() < link.to.seqno())) {
580
      key_blkid = link.to;
581
      has_key_block = true;
582
    }
583
    cur = link.to;
584
  }
585
  if (cur != to) {
586
    return td::Status::Error("last link of BlockProofChain ends at block "s + cur.to_str() +
587
                             " different from declared chain destination block " + to.to_str());
588
  }
589
  has_utime = (last_utime > 0);
590
  valid = true;
591
  return td::Status::OK();
592
}
593

594
td::Bits256 compute_node_id_short(td::Bits256 ed25519_pubkey) {
595
  // pub.ed25519#4813b4c6 key:int256 = PublicKey;
596
  struct pubkey {
597
    int magic = 0x4813b4c6;
598
    unsigned char ed25519_key[32];
599
  } PK;
600
  std::memcpy(PK.ed25519_key, ed25519_pubkey.data(), 32);
601
  static_assert(sizeof(pubkey) == 36, "PublicKey structure is not 36 bytes long");
602
  td::Bits256 hash;
603
  digest::hash_str<digest::SHA256>(hash.data(), (void*)&PK, sizeof(pubkey));
604
  return hash;
605
}
606

607
td::Status check_block_signatures(const std::vector<ton::ValidatorDescr>& nodes,
608
                                  const std::vector<ton::BlockSignature>& signatures, const ton::BlockIdExt& blkid) {
609
  if (nodes.empty()) {
610
    return td::Status::Error("empty validator public keys set");
611
  }
612
  if (signatures.empty()) {
613
    return td::Status::Error("empty validator signature set");
614
  }
615
  // compute the string to be signed and its hash
616
  unsigned char to_sign[68];
617
  td::as<td::uint32>(to_sign) = 0xc50b6e70;  // ton.blockId root_cell_hash:int256 file_hash:int256 = ton.BlockId;
618
  memcpy(to_sign + 4, blkid.root_hash.data(), 32);
619
  memcpy(to_sign + 36, blkid.file_hash.data(), 32);
620
  // unsigned char hash[32];
621
  // digest::hash_str<digest::SHA256>(hash, (void*)to_sign, sizeof(to_sign));
622

623
  ton::ValidatorWeight total_weight = 0, signed_weight = 0;
624
  std::vector<std::pair<td::Bits256, unsigned>> node_map;
625
  for (unsigned i = 0; i < nodes.size(); i++) {
626
    total_weight += nodes[i].weight;
627
    node_map.emplace_back(compute_node_id_short(nodes[i].key), i);
628
  }
629
  std::sort(node_map.begin(), node_map.end());
630
  std::vector<unsigned> seen;
631
  for (auto& sig : signatures) {
632
    // lookup node in validator set
633
    auto& id = sig.node;
634
    auto it = std::lower_bound(node_map.begin(), node_map.end(), id,
635
                               [](const auto& p, const auto& x) { return p.first < x; });
636
    if (it == node_map.end() || it->first != id) {
637
      return td::Status::Error("signature set contains unknown NodeIdShort "s + id.to_hex());
638
    }
639
    unsigned i = it->second;
640
    seen.emplace_back(i);
641
    // check one signature
642
    td::Ed25519::PublicKey pub_key{td::SecureString{nodes.at(i).key.as_slice()}};
643
    auto res = pub_key.verify_signature(td::Slice{to_sign, 68}, sig.signature.as_slice());
644
    if (res.is_error()) {
645
      return res;
646
    }
647
    signed_weight += nodes[i].weight;
648
    if (signed_weight > total_weight) {
649
      break;
650
    }
651
  }
652
  std::sort(seen.begin(), seen.end());
653
  for (std::size_t i = 1; i < seen.size(); i++) {
654
    if (seen[i] == seen[i - 1]) {
655
      return td::Status::Error("signature set contains duplicate signature for NodeIdShort "s +
656
                               compute_node_id_short(nodes.at(seen[i]).key).to_hex());
657
    }
658
  }
659
  if (3 * signed_weight <= 2 * total_weight) {
660
    return td::Status::Error(PSTRING() << "insufficient total signature weight: only " << signed_weight << " out of "
661
                                       << total_weight);
662
  }
663
  return td::Status::OK();
664
}
665

666
}  // namespace block
667