LCOV - code coverage report
Current view: top level - src/sapling - incrementalmerkletree.cpp (source / functions) Hit Total Coverage
Test: total_coverage.info Lines: 153 157 97.5 %
Date: 2025-02-23 09:33:43 Functions: 26 49 53.1 %

          Line data    Source code
       1             : // Copyright (c) 2016-2020 The ZCash developers
       2             : // Copyright (c) 2021 The PIVX Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or https://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include <stdexcept>
       7             : 
       8             : #include "crypto/sha256.h"
       9             : #include "sapling/incrementalmerkletree.h"
      10             : 
      11             : #include <librustzcash.h>
      12             : 
      13             : namespace libzcash {
      14             : 
      15     3668040 : PedersenHash PedersenHash::combine(
      16             :     const PedersenHash& a,
      17             :     const PedersenHash& b,
      18             :     size_t depth
      19             : )
      20             : {
      21     3668040 :     PedersenHash res = PedersenHash();
      22             : 
      23     3668040 :     librustzcash_merkle_hash(
      24             :         depth,
      25             :         a.begin(),
      26             :         b.begin(),
      27             :         res.begin()
      28             :     );
      29             : 
      30     3668040 :     return res;
      31             : }
      32             : 
      33           1 : PedersenHash PedersenHash::uncommitted() {
      34           1 :     PedersenHash res = PedersenHash();
      35             : 
      36           1 :     librustzcash_tree_uncommitted(res.begin());
      37             : 
      38           1 :     return res;
      39             : }
      40             : 
      41             : static const std::array<PedersenHash, 65> pedersen_empty_roots = {
      42             :     uint256(std::vector<unsigned char>{
      43             :         0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      44             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      45             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      46             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      47             :     }),
      48             :     uint256(std::vector<unsigned char>{
      49             :         0x81, 0x7d, 0xe3, 0x6a, 0xb2, 0xd5, 0x7f, 0xeb,
      50             :         0x07, 0x76, 0x34, 0xbc, 0xa7, 0x78, 0x19, 0xc8,
      51             :         0xe0, 0xbd, 0x29, 0x8c, 0x04, 0xf6, 0xfe, 0xd0,
      52             :         0xe6, 0xa8, 0x3c, 0xc1, 0x35, 0x6c, 0xa1, 0x55,
      53             :     }),
      54             :     uint256(std::vector<unsigned char>{
      55             :         0xff, 0xe9, 0xfc, 0x03, 0xf1, 0x8b, 0x17, 0x6c,
      56             :         0x99, 0x88, 0x06, 0x43, 0x9f, 0xf0, 0xbb, 0x8a,
      57             :         0xd1, 0x93, 0xaf, 0xdb, 0x27, 0xb2, 0xcc, 0xbc,
      58             :         0x88, 0x85, 0x69, 0x16, 0xdd, 0x80, 0x4e, 0x34,
      59             :     }),
      60             :     uint256(std::vector<unsigned char>{
      61             :         0xd8, 0x28, 0x33, 0x86, 0xef, 0x2e, 0xf0, 0x7e,
      62             :         0xbd, 0xbb, 0x43, 0x83, 0xc1, 0x2a, 0x73, 0x9a,
      63             :         0x95, 0x3a, 0x4d, 0x6e, 0x0d, 0x6f, 0xb1, 0x13,
      64             :         0x9a, 0x40, 0x36, 0xd6, 0x93, 0xbf, 0xbb, 0x6c,
      65             :     }),
      66             :     uint256(std::vector<unsigned char>{
      67             :         0xe1, 0x10, 0xde, 0x65, 0xc9, 0x07, 0xb9, 0xde,
      68             :         0xa4, 0xae, 0x0b, 0xd8, 0x3a, 0x4b, 0x0a, 0x51,
      69             :         0xbe, 0xa1, 0x75, 0x64, 0x6a, 0x64, 0xc1, 0x2b,
      70             :         0x4c, 0x9f, 0x93, 0x1b, 0x2c, 0xb3, 0x1b, 0x49,
      71             :     }),
      72             :     uint256(std::vector<unsigned char>{
      73             :         0x91, 0x2d, 0x82, 0xb2, 0xc2, 0xbc, 0xa2, 0x31,
      74             :         0xf7, 0x1e, 0xfc, 0xf6, 0x17, 0x37, 0xfb, 0xf0,
      75             :         0xa0, 0x8b, 0xef, 0xa0, 0x41, 0x62, 0x15, 0xae,
      76             :         0xef, 0x53, 0xe8, 0xbb, 0x6d, 0x23, 0x39, 0x0a,
      77             :     }),
      78             :     uint256(std::vector<unsigned char>{
      79             :         0x8a, 0xc9, 0xcf, 0x9c, 0x39, 0x1e, 0x3f, 0xd4,
      80             :         0x28, 0x91, 0xd2, 0x72, 0x38, 0xa8, 0x1a, 0x8a,
      81             :         0x5c, 0x1d, 0x3a, 0x72, 0xb1, 0xbc, 0xbe, 0xa8,
      82             :         0xcf, 0x44, 0xa5, 0x8c, 0xe7, 0x38, 0x96, 0x13,
      83             :     }),
      84             :     uint256(std::vector<unsigned char>{
      85             :         0xd6, 0xc6, 0x39, 0xac, 0x24, 0xb4, 0x6b, 0xd1,
      86             :         0x93, 0x41, 0xc9, 0x1b, 0x13, 0xfd, 0xca, 0xb3,
      87             :         0x15, 0x81, 0xdd, 0xaf, 0x7f, 0x14, 0x11, 0x33,
      88             :         0x6a, 0x27, 0x1f, 0x3d, 0x0a, 0xa5, 0x28, 0x13,
      89             :     }),
      90             :     uint256(std::vector<unsigned char>{
      91             :         0x7b, 0x99, 0xab, 0xdc, 0x37, 0x30, 0x99, 0x1c,
      92             :         0xc9, 0x27, 0x47, 0x27, 0xd7, 0xd8, 0x2d, 0x28,
      93             :         0xcb, 0x79, 0x4e, 0xdb, 0xc7, 0x03, 0x4b, 0x4f,
      94             :         0x00, 0x53, 0xff, 0x7c, 0x4b, 0x68, 0x04, 0x44,
      95             :     }),
      96             :     uint256(std::vector<unsigned char>{
      97             :         0x43, 0xff, 0x54, 0x57, 0xf1, 0x3b, 0x92, 0x6b,
      98             :         0x61, 0xdf, 0x55, 0x2d, 0x4e, 0x40, 0x2e, 0xe6,
      99             :         0xdc, 0x14, 0x63, 0xf9, 0x9a, 0x53, 0x5f, 0x9a,
     100             :         0x71, 0x34, 0x39, 0x26, 0x4d, 0x5b, 0x61, 0x6b,
     101             :     }),
     102             :     uint256(std::vector<unsigned char>{
     103             :         0xba, 0x49, 0xb6, 0x59, 0xfb, 0xd0, 0xb7, 0x33,
     104             :         0x42, 0x11, 0xea, 0x6a, 0x9d, 0x9d, 0xf1, 0x85,
     105             :         0xc7, 0x57, 0xe7, 0x0a, 0xa8, 0x1d, 0xa5, 0x62,
     106             :         0xfb, 0x91, 0x2b, 0x84, 0xf4, 0x9b, 0xce, 0x72,
     107             :     }),
     108             :     uint256(std::vector<unsigned char>{
     109             :         0x47, 0x77, 0xc8, 0x77, 0x6a, 0x3b, 0x1e, 0x69,
     110             :         0xb7, 0x3a, 0x62, 0xfa, 0x70, 0x1f, 0xa4, 0xf7,
     111             :         0xa6, 0x28, 0x2d, 0x9a, 0xee, 0x2c, 0x7a, 0x6b,
     112             :         0x82, 0xe7, 0x93, 0x7d, 0x70, 0x81, 0xc2, 0x3c,
     113             :     }),
     114             :     uint256(std::vector<unsigned char>{
     115             :         0xec, 0x67, 0x71, 0x14, 0xc2, 0x72, 0x06, 0xf5,
     116             :         0xde, 0xbc, 0x1c, 0x1e, 0xd6, 0x6f, 0x95, 0xe2,
     117             :         0xb1, 0x88, 0x5d, 0xa5, 0xb7, 0xbe, 0x3d, 0x73,
     118             :         0x6b, 0x1d, 0xe9, 0x85, 0x79, 0x47, 0x30, 0x48,
     119             :     }),
     120             :     uint256(std::vector<unsigned char>{
     121             :         0x1b, 0x77, 0xda, 0xc4, 0xd2, 0x4f, 0xb7, 0x25,
     122             :         0x8c, 0x3c, 0x52, 0x87, 0x04, 0xc5, 0x94, 0x30,
     123             :         0xb6, 0x30, 0x71, 0x8b, 0xec, 0x48, 0x64, 0x21,
     124             :         0x83, 0x70, 0x21, 0xcf, 0x75, 0xda, 0xb6, 0x51,
     125             :     }),
     126             :     uint256(std::vector<unsigned char>{
     127             :         0xbd, 0x74, 0xb2, 0x5a, 0xac, 0xb9, 0x23, 0x78,
     128             :         0xa8, 0x71, 0xbf, 0x27, 0xd2, 0x25, 0xcf, 0xc2,
     129             :         0x6b, 0xac, 0xa3, 0x44, 0xa1, 0xea, 0x35, 0xfd,
     130             :         0xd9, 0x45, 0x10, 0xf3, 0xd1, 0x57, 0x08, 0x2c,
     131             :     }),
     132             :     uint256(std::vector<unsigned char>{
     133             :         0xd6, 0xac, 0xde, 0xdf, 0x95, 0xf6, 0x08, 0xe0,
     134             :         0x9f, 0xa5, 0x3f, 0xb4, 0x3d, 0xcd, 0x09, 0x90,
     135             :         0x47, 0x57, 0x26, 0xc5, 0x13, 0x12, 0x10, 0xc9,
     136             :         0xe5, 0xca, 0xea, 0xb9, 0x7f, 0x0e, 0x64, 0x2f,
     137             :     }),
     138             :     uint256(std::vector<unsigned char>{
     139             :         0x1e, 0xa6, 0x67, 0x5f, 0x95, 0x51, 0xee, 0xb9,
     140             :         0xdf, 0xaa, 0xa9, 0x24, 0x7b, 0xc9, 0x85, 0x82,
     141             :         0x70, 0xd3, 0xd3, 0xa4, 0xc5, 0xaf, 0xa7, 0x17,
     142             :         0x7a, 0x98, 0x4d, 0x5e, 0xd1, 0xbe, 0x24, 0x51,
     143             :     }),
     144             :     uint256(std::vector<unsigned char>{
     145             :         0x6e, 0xdb, 0x16, 0xd0, 0x19, 0x07, 0xb7, 0x59,
     146             :         0x97, 0x7d, 0x76, 0x50, 0xda, 0xd7, 0xe3, 0xec,
     147             :         0x04, 0x9a, 0xf1, 0xa3, 0xd8, 0x75, 0x38, 0x0b,
     148             :         0x69, 0x7c, 0x86, 0x2c, 0x9e, 0xc5, 0xd5, 0x1c,
     149             :     }),
     150             :     uint256(std::vector<unsigned char>{
     151             :         0xcd, 0x1c, 0x8d, 0xbf, 0x6e, 0x3a, 0xcc, 0x7a,
     152             :         0x80, 0x43, 0x9b, 0xc4, 0x96, 0x2c, 0xf2, 0x5b,
     153             :         0x9d, 0xce, 0x7c, 0x89, 0x6f, 0x3a, 0x5b, 0xd7,
     154             :         0x08, 0x03, 0xfc, 0x5a, 0x0e, 0x33, 0xcf, 0x00,
     155             :     }),
     156             :     uint256(std::vector<unsigned char>{
     157             :         0x6a, 0xca, 0x84, 0x48, 0xd8, 0x26, 0x3e, 0x54,
     158             :         0x7d, 0x5f, 0xf2, 0x95, 0x0e, 0x2e, 0xd3, 0x83,
     159             :         0x9e, 0x99, 0x8d, 0x31, 0xcb, 0xc6, 0xac, 0x9f,
     160             :         0xd5, 0x7b, 0xc6, 0x00, 0x2b, 0x15, 0x92, 0x16,
     161             :     }),
     162             :     uint256(std::vector<unsigned char>{
     163             :         0x8d, 0x5f, 0xa4, 0x3e, 0x5a, 0x10, 0xd1, 0x16,
     164             :         0x05, 0xac, 0x74, 0x30, 0xba, 0x1f, 0x5d, 0x81,
     165             :         0xfb, 0x1b, 0x68, 0xd2, 0x9a, 0x64, 0x04, 0x05,
     166             :         0x76, 0x77, 0x49, 0xe8, 0x41, 0x52, 0x76, 0x73,
     167             :     }),
     168             :     uint256(std::vector<unsigned char>{
     169             :         0x08, 0xee, 0xab, 0x0c, 0x13, 0xab, 0xd6, 0x06,
     170             :         0x9e, 0x63, 0x10, 0x19, 0x7b, 0xf8, 0x0f, 0x9c,
     171             :         0x1e, 0xa6, 0xde, 0x78, 0xfd, 0x19, 0xcb, 0xae,
     172             :         0x24, 0xd4, 0xa5, 0x20, 0xe6, 0xcf, 0x30, 0x23,
     173             :     }),
     174             :     uint256(std::vector<unsigned char>{
     175             :         0x07, 0x69, 0x55, 0x7b, 0xc6, 0x82, 0xb1, 0xbf,
     176             :         0x30, 0x86, 0x46, 0xfd, 0x0b, 0x22, 0xe6, 0x48,
     177             :         0xe8, 0xb9, 0xe9, 0x8f, 0x57, 0xe2, 0x9f, 0x5a,
     178             :         0xf4, 0x0f, 0x6e, 0xdb, 0x83, 0x3e, 0x2c, 0x49,
     179             :     }),
     180             :     uint256(std::vector<unsigned char>{
     181             :         0x4c, 0x69, 0x37, 0xd7, 0x8f, 0x42, 0x68, 0x5f,
     182             :         0x84, 0xb4, 0x3a, 0xd3, 0xb7, 0xb0, 0x0f, 0x81,
     183             :         0x28, 0x56, 0x62, 0xf8, 0x5c, 0x6a, 0x68, 0xef,
     184             :         0x11, 0xd6, 0x2a, 0xd1, 0xa3, 0xee, 0x08, 0x50,
     185             :     }),
     186             :     uint256(std::vector<unsigned char>{
     187             :         0xfe, 0xe0, 0xe5, 0x28, 0x02, 0xcb, 0x0c, 0x46,
     188             :         0xb1, 0xeb, 0x4d, 0x37, 0x6c, 0x62, 0x69, 0x7f,
     189             :         0x47, 0x59, 0xf6, 0xc8, 0x91, 0x7f, 0xa3, 0x52,
     190             :         0x57, 0x12, 0x02, 0xfd, 0x77, 0x8f, 0xd7, 0x12,
     191             :     }),
     192             :     uint256(std::vector<unsigned char>{
     193             :         0x16, 0xd6, 0x25, 0x29, 0x68, 0x97, 0x1a, 0x83,
     194             :         0xda, 0x85, 0x21, 0xd6, 0x53, 0x82, 0xe6, 0x1f,
     195             :         0x01, 0x76, 0x64, 0x6d, 0x77, 0x1c, 0x91, 0x52,
     196             :         0x8e, 0x32, 0x76, 0xee, 0x45, 0x38, 0x3e, 0x4a,
     197             :     }),
     198             :     uint256(std::vector<unsigned char>{
     199             :         0xd2, 0xe1, 0x64, 0x2c, 0x9a, 0x46, 0x22, 0x29,
     200             :         0x28, 0x9e, 0x5b, 0x0e, 0x3b, 0x7f, 0x90, 0x08,
     201             :         0xe0, 0x30, 0x1c, 0xbb, 0x93, 0x38, 0x5e, 0xe0,
     202             :         0xe2, 0x1d, 0xa2, 0x54, 0x50, 0x73, 0xcb, 0x58,
     203             :     }),
     204             :     uint256(std::vector<unsigned char>{
     205             :         0xa5, 0x12, 0x2c, 0x08, 0xff, 0x9c, 0x16, 0x1d,
     206             :         0x9c, 0xa6, 0xfc, 0x46, 0x20, 0x73, 0x39, 0x6c,
     207             :         0x7d, 0x7d, 0x38, 0xe8, 0xee, 0x48, 0xcd, 0xb3,
     208             :         0xbe, 0xa7, 0xe2, 0x23, 0x01, 0x34, 0xed, 0x6a,
     209             :     }),
     210             :     uint256(std::vector<unsigned char>{
     211             :         0x28, 0xe7, 0xb8, 0x41, 0xdc, 0xbc, 0x47, 0xcc,
     212             :         0xeb, 0x69, 0xd7, 0xcb, 0x8d, 0x94, 0x24, 0x5f,
     213             :         0xb7, 0xcb, 0x2b, 0xa3, 0xa7, 0xa6, 0xbc, 0x18,
     214             :         0xf1, 0x3f, 0x94, 0x5f, 0x7d, 0xbd, 0x6e, 0x2a,
     215             :     }),
     216             :     uint256(std::vector<unsigned char>{
     217             :         0xe1, 0xf3, 0x4b, 0x03, 0x4d, 0x4a, 0x3c, 0xd2,
     218             :         0x85, 0x57, 0xe2, 0x90, 0x7e, 0xbf, 0x99, 0x0c,
     219             :         0x91, 0x8f, 0x64, 0xec, 0xb5, 0x0a, 0x94, 0xf0,
     220             :         0x1d, 0x6f, 0xda, 0x5c, 0xa5, 0xc7, 0xef, 0x72,
     221             :     }),
     222             :     uint256(std::vector<unsigned char>{
     223             :         0x12, 0x93, 0x5f, 0x14, 0xb6, 0x76, 0x50, 0x9b,
     224             :         0x81, 0xeb, 0x49, 0xef, 0x25, 0xf3, 0x92, 0x69,
     225             :         0xed, 0x72, 0x30, 0x92, 0x38, 0xb4, 0xc1, 0x45,
     226             :         0x80, 0x35, 0x44, 0xb6, 0x46, 0xdc, 0xa6, 0x2d,
     227             :     }),
     228             :     uint256(std::vector<unsigned char>{
     229             :         0xb2, 0xee, 0xd0, 0x31, 0xd4, 0xd6, 0xa4, 0xf0,
     230             :         0x2a, 0x09, 0x7f, 0x80, 0xb5, 0x4c, 0xc1, 0x54,
     231             :         0x1d, 0x41, 0x63, 0xc6, 0xb6, 0xf5, 0x97, 0x1f,
     232             :         0x88, 0xb6, 0xe4, 0x1d, 0x35, 0xc5, 0x38, 0x14,
     233             :     }),
     234             :     uint256(std::vector<unsigned char>{
     235             :         0xfb, 0xc2, 0xf4, 0x30, 0x0c, 0x01, 0xf0, 0xb7,
     236             :         0x82, 0x0d, 0x00, 0xe3, 0x34, 0x7c, 0x8d, 0xa4,
     237             :         0xee, 0x61, 0x46, 0x74, 0x37, 0x6c, 0xbc, 0x45,
     238             :         0x35, 0x9d, 0xaa, 0x54, 0xf9, 0xb5, 0x49, 0x3e,
     239             :     }),
     240             :     uint256(std::vector<unsigned char>{
     241             :         0x25, 0x2e, 0x67, 0x98, 0x64, 0x5f, 0x5b, 0xf1,
     242             :         0x14, 0xe4, 0xb4, 0xe9, 0x0e, 0x96, 0x18, 0x28,
     243             :         0x61, 0x48, 0x98, 0x40, 0xd9, 0xb4, 0xcc, 0xc4,
     244             :         0xc1, 0xfb, 0x5a, 0x46, 0x99, 0x7c, 0xee, 0x14,
     245             :     }),
     246             :     uint256(std::vector<unsigned char>{
     247             :         0x98, 0xb1, 0x90, 0x42, 0xf1, 0xf7, 0xc7, 0xdd,
     248             :         0x11, 0xec, 0x25, 0xea, 0x66, 0xb6, 0xff, 0x74,
     249             :         0xe0, 0x8c, 0xe1, 0x1d, 0x44, 0x7e, 0xd6, 0xf1,
     250             :         0xbf, 0xe8, 0x7e, 0x11, 0x0e, 0x33, 0x1e, 0x11,
     251             :     }),
     252             :     uint256(std::vector<unsigned char>{
     253             :         0xd4, 0x51, 0x30, 0x47, 0x99, 0x57, 0x2b, 0xa9,
     254             :         0xf4, 0x2c, 0x4d, 0xab, 0x6b, 0x07, 0xc7, 0x03,
     255             :         0xbd, 0x2c, 0x12, 0x3a, 0xb9, 0xd6, 0x0f, 0x2a,
     256             :         0x60, 0xf9, 0x95, 0x58, 0x54, 0x91, 0x0b, 0x6a,
     257             :     }),
     258             :     uint256(std::vector<unsigned char>{
     259             :         0x3e, 0xcd, 0x5f, 0x27, 0xac, 0xf0, 0x1b, 0xd3,
     260             :         0x7a, 0x33, 0xe4, 0x51, 0x78, 0x67, 0xef, 0x76,
     261             :         0x47, 0x4c, 0xd8, 0x3f, 0xb3, 0x1c, 0x92, 0x08,
     262             :         0xdc, 0xef, 0x2e, 0xed, 0xce, 0xf3, 0x6c, 0x72,
     263             :     }),
     264             :     uint256(std::vector<unsigned char>{
     265             :         0x26, 0xc3, 0x7d, 0xa6, 0x78, 0x94, 0xa1, 0x3d,
     266             :         0xf8, 0xaa, 0x48, 0x78, 0xd2, 0x51, 0x4a, 0x42,
     267             :         0x12, 0x57, 0x3b, 0x73, 0xec, 0xca, 0xab, 0x16,
     268             :         0xfe, 0x4f, 0xa6, 0x60, 0xe8, 0xfe, 0x27, 0x07,
     269             :     }),
     270             :     uint256(std::vector<unsigned char>{
     271             :         0xb5, 0x45, 0xef, 0x34, 0x48, 0x5e, 0xed, 0x30,
     272             :         0xd4, 0x2b, 0x2c, 0x29, 0x5a, 0x4a, 0x5b, 0x68,
     273             :         0x0d, 0xe8, 0xa9, 0xd5, 0xe3, 0x83, 0x45, 0x78,
     274             :         0x24, 0x62, 0xc0, 0x4f, 0x09, 0xdc, 0x68, 0x51,
     275             :     }),
     276             :     uint256(std::vector<unsigned char>{
     277             :         0x77, 0xfd, 0x20, 0xb3, 0x00, 0x94, 0x67, 0x65,
     278             :         0xa8, 0x7f, 0x24, 0xbd, 0x04, 0x50, 0x73, 0x72,
     279             :         0x9c, 0xbd, 0x7b, 0x66, 0xeb, 0x8f, 0xa1, 0x40,
     280             :         0xb5, 0x83, 0xfa, 0xa9, 0xd1, 0x42, 0x58, 0x01,
     281             :     }),
     282             :     uint256(std::vector<unsigned char>{
     283             :         0xcb, 0xaa, 0x57, 0x6b, 0x17, 0x99, 0xb5, 0x8f,
     284             :         0xf3, 0xa6, 0xde, 0xcb, 0xba, 0x91, 0x9b, 0x0b,
     285             :         0x68, 0xd7, 0xc8, 0x93, 0xe4, 0x6f, 0xde, 0x99,
     286             :         0x87, 0x68, 0xe8, 0x7e, 0x35, 0x0a, 0x07, 0x25,
     287             :     }),
     288             :     uint256(std::vector<unsigned char>{
     289             :         0x45, 0xfe, 0x81, 0xb1, 0x8c, 0xa3, 0x00, 0x74,
     290             :         0xd0, 0x12, 0x0d, 0x2b, 0x1a, 0x0d, 0x10, 0xb3,
     291             :         0xa0, 0x50, 0x93, 0x35, 0x12, 0xdb, 0x8e, 0xe3,
     292             :         0x4e, 0x52, 0x47, 0x3d, 0x4f, 0x08, 0xa2, 0x67,
     293             :     }),
     294             :     uint256(std::vector<unsigned char>{
     295             :         0x0e, 0x60, 0xa1, 0xf0, 0x12, 0x1f, 0x59, 0x1e,
     296             :         0x55, 0x1d, 0x3e, 0xd1, 0x86, 0x5b, 0x50, 0xa7,
     297             :         0x5d, 0x7c, 0xcf, 0xf1, 0x28, 0x9d, 0xf7, 0xc4,
     298             :         0x4d, 0xd4, 0x65, 0xa5, 0x43, 0x17, 0xf5, 0x6a,
     299             :     }),
     300             :     uint256(std::vector<unsigned char>{
     301             :         0xce, 0xdf, 0xb1, 0x84, 0xdd, 0x92, 0xa0, 0xcb,
     302             :         0xfc, 0x11, 0xe8, 0xbe, 0x69, 0x7b, 0x47, 0x69,
     303             :         0x88, 0xed, 0x5f, 0x39, 0x36, 0x9a, 0xbd, 0xd9,
     304             :         0x0c, 0x61, 0x54, 0x49, 0x88, 0x60, 0x1c, 0x0d,
     305             :     }),
     306             :     uint256(std::vector<unsigned char>{
     307             :         0xf3, 0x62, 0x68, 0x66, 0x12, 0x64, 0x9a, 0x31,
     308             :         0x3b, 0xa4, 0x64, 0x43, 0x7a, 0x0c, 0xad, 0x0e,
     309             :         0x7e, 0x3d, 0x7e, 0x1b, 0x4b, 0x37, 0x43, 0xf9,
     310             :         0x0e, 0x05, 0xa2, 0x10, 0x0a, 0x49, 0x5f, 0x42,
     311             :     }),
     312             :     uint256(std::vector<unsigned char>{
     313             :         0x7d, 0xea, 0xe5, 0xf3, 0xbb, 0xde, 0xff, 0xd3,
     314             :         0xf8, 0x52, 0x71, 0xa0, 0x8b, 0x5e, 0xc3, 0x1f,
     315             :         0x16, 0xf9, 0x37, 0x96, 0x4a, 0xe7, 0x08, 0xfd,
     316             :         0xff, 0x7c, 0x13, 0xe5, 0xa4, 0xf3, 0xdf, 0x6b,
     317             :     }),
     318             :     uint256(std::vector<unsigned char>{
     319             :         0x40, 0xcc, 0xf0, 0xfc, 0x1e, 0xab, 0x6d, 0x85,
     320             :         0x02, 0xbd, 0x93, 0xdc, 0x31, 0x34, 0x2d, 0xfd,
     321             :         0x57, 0xdf, 0x5b, 0xbb, 0x5d, 0x70, 0xa1, 0xbf,
     322             :         0x6b, 0x92, 0xef, 0xc6, 0x1e, 0xc9, 0xa2, 0x58,
     323             :     }),
     324             :     uint256(std::vector<unsigned char>{
     325             :         0xd7, 0x80, 0x25, 0x49, 0x1f, 0x1b, 0xca, 0x85,
     326             :         0x07, 0xf6, 0x4f, 0x25, 0x87, 0x2d, 0xd0, 0x23,
     327             :         0x88, 0x47, 0x9a, 0x1a, 0x22, 0x51, 0x26, 0xe4,
     328             :         0x0d, 0x2f, 0xe4, 0x18, 0xb9, 0x8e, 0x0e, 0x2c,
     329             :     }),
     330             :     uint256(std::vector<unsigned char>{
     331             :         0x0d, 0xb7, 0x29, 0x46, 0x85, 0xc8, 0xa0, 0x72,
     332             :         0x5f, 0x15, 0x84, 0x6e, 0xa5, 0x89, 0x9e, 0xa0,
     333             :         0xe9, 0x86, 0xc2, 0x70, 0x7b, 0xd7, 0xb4, 0x12,
     334             :         0x95, 0x44, 0x12, 0xf2, 0x6a, 0xbf, 0x55, 0x0a,
     335             :     }),
     336             :     uint256(std::vector<unsigned char>{
     337             :         0xb7, 0xe2, 0x90, 0xbe, 0x95, 0x55, 0xcf, 0x75,
     338             :         0x54, 0x86, 0x50, 0xda, 0x6d, 0x47, 0xc8, 0x93,
     339             :         0xae, 0xf7, 0xf8, 0xc6, 0xdd, 0x27, 0x35, 0x49,
     340             :         0x94, 0x95, 0xf6, 0x36, 0x59, 0x0d, 0xae, 0x0a,
     341             :     }),
     342             :     uint256(std::vector<unsigned char>{
     343             :         0x2d, 0xd2, 0x53, 0x2a, 0x85, 0x8c, 0x30, 0x01,
     344             :         0x45, 0xa6, 0x5e, 0x35, 0x1f, 0x91, 0xbe, 0x6a,
     345             :         0xfe, 0xab, 0x59, 0x7c, 0x41, 0xef, 0x07, 0x3f,
     346             :         0x50, 0xb6, 0x22, 0xd5, 0x86, 0xff, 0x59, 0x27,
     347             :     }),
     348             :     uint256(std::vector<unsigned char>{
     349             :         0x97, 0x2f, 0x0c, 0x5c, 0x6f, 0x9a, 0xeb, 0x0e,
     350             :         0x38, 0xbf, 0x83, 0x19, 0xf3, 0xa5, 0xfc, 0xdc,
     351             :         0x8f, 0xd8, 0x78, 0x2e, 0x41, 0x88, 0x73, 0x0c,
     352             :         0xd0, 0x82, 0xd9, 0xba, 0xbc, 0x58, 0x98, 0x51,
     353             :     }),
     354             :     uint256(std::vector<unsigned char>{
     355             :         0x00, 0x1e, 0x57, 0x7b, 0x0f, 0x43, 0x90, 0x18,
     356             :         0x2b, 0x4a, 0xe4, 0x3d, 0x32, 0x9b, 0x3a, 0xa8,
     357             :         0x83, 0x5d, 0xae, 0x1b, 0xb7, 0x9e, 0x60, 0x4b,
     358             :         0x7d, 0x2d, 0xa0, 0xe9, 0x0d, 0x06, 0x09, 0x29,
     359             :     }),
     360             :     uint256(std::vector<unsigned char>{
     361             :         0xaa, 0x6e, 0x70, 0xa9, 0x1e, 0xbc, 0x54, 0xee,
     362             :         0xfc, 0xe5, 0xff, 0xd5, 0xb6, 0x75, 0xda, 0xf3,
     363             :         0xf1, 0xd9, 0x40, 0xa8, 0x45, 0x1f, 0xcb, 0x01,
     364             :         0x08, 0x1f, 0xa9, 0xd4, 0xf2, 0x62, 0x43, 0x6f,
     365             :     }),
     366             :     uint256(std::vector<unsigned char>{
     367             :         0xd7, 0x70, 0x38, 0xbf, 0x67, 0xe6, 0x31, 0x75,
     368             :         0x29, 0x40, 0x23, 0x12, 0x51, 0xd7, 0xfe, 0x85,
     369             :         0xaf, 0x52, 0xdb, 0xdd, 0x6a, 0xab, 0x37, 0xc7,
     370             :         0xa5, 0xec, 0x32, 0xb6, 0x5f, 0xe6, 0xde, 0x03,
     371             :     }),
     372             :     uint256(std::vector<unsigned char>{
     373             :         0xd2, 0x27, 0xa1, 0x7a, 0x7e, 0x0c, 0xf9, 0x6d,
     374             :         0xce, 0xdd, 0x9f, 0xc7, 0xbc, 0xe4, 0x3c, 0x6c,
     375             :         0x1d, 0x66, 0xba, 0xdd, 0x75, 0x43, 0xa8, 0x87,
     376             :         0xc8, 0x65, 0x6c, 0x54, 0x7e, 0xcf, 0xb2, 0x4f,
     377             :     }),
     378             :     uint256(std::vector<unsigned char>{
     379             :         0x70, 0xe8, 0xa5, 0x21, 0x95, 0x15, 0x83, 0xe5,
     380             :         0x3f, 0xc0, 0x58, 0x5c, 0x70, 0x7e, 0xce, 0xda,
     381             :         0x89, 0xb7, 0xa7, 0xd1, 0xaf, 0x41, 0xd1, 0xa0,
     382             :         0x15, 0xd7, 0x97, 0xfa, 0x76, 0xc0, 0xf5, 0x69,
     383             :     }),
     384             :     uint256(std::vector<unsigned char>{
     385             :         0xe4, 0x85, 0xa9, 0x68, 0x55, 0xe8, 0x72, 0xfc,
     386             :         0x50, 0x90, 0x15, 0x0e, 0x2c, 0xd2, 0x4e, 0x10,
     387             :         0x59, 0x1d, 0x35, 0x16, 0x6e, 0xb0, 0xeb, 0x30,
     388             :         0xfc, 0xdf, 0xac, 0x93, 0xb0, 0x1d, 0x28, 0x1c,
     389             :     }),
     390             :     uint256(std::vector<unsigned char>{
     391             :         0xe4, 0xa1, 0x9f, 0xeb, 0xdf, 0x2a, 0x86, 0x89,
     392             :         0x6e, 0x41, 0xf2, 0xce, 0xdc, 0xf2, 0xae, 0x58,
     393             :         0x46, 0x71, 0x80, 0x2e, 0x6a, 0x46, 0x7e, 0x84,
     394             :         0x39, 0xca, 0xb5, 0xd6, 0x18, 0x43, 0x41, 0x6b,
     395             :     }),
     396             :     uint256(std::vector<unsigned char>{
     397             :         0xe9, 0x27, 0x83, 0x88, 0x47, 0x80, 0x6a, 0x43,
     398             :         0xbd, 0x6c, 0x60, 0x88, 0xe3, 0x9f, 0x65, 0xb8,
     399             :         0xb3, 0xe5, 0x8b, 0x2d, 0xb5, 0xf7, 0xad, 0x56,
     400             :         0x43, 0xd9, 0x1e, 0x06, 0x59, 0xa2, 0x8a, 0x2a,
     401             :     }),
     402             :     uint256(std::vector<unsigned char>{
     403             :         0x0b, 0xd3, 0xa8, 0x18, 0xe8, 0x3f, 0x9c, 0xd2,
     404             :         0xff, 0x4f, 0x62, 0x01, 0x1a, 0x51, 0x01, 0x76,
     405             :         0xac, 0x32, 0xf5, 0x44, 0x8e, 0x6e, 0x15, 0x45,
     406             :         0x15, 0x04, 0x3c, 0x59, 0x26, 0xd5, 0x1c, 0x6f,
     407             :     }),
     408             :     uint256(std::vector<unsigned char>{
     409             :         0xce, 0x41, 0x34, 0x45, 0xe0, 0x37, 0x90, 0x49,
     410             :         0x8f, 0xe7, 0x2d, 0x8e, 0x01, 0x91, 0x5e, 0x7f,
     411             :         0xf1, 0x20, 0xae, 0x35, 0xb3, 0xb5, 0x90, 0xd2,
     412             :         0x1b, 0x7f, 0x74, 0xde, 0xe1, 0x83, 0x0f, 0x0d,
     413             :     }),
     414             :     uint256(std::vector<unsigned char>{
     415             :         0x60, 0x0e, 0x6f, 0x93, 0xe7, 0x3d, 0x7a, 0xbd,
     416             :         0x4e, 0xe0, 0xa6, 0x5c, 0xb1, 0xb1, 0x9a, 0xa3,
     417             :         0xec, 0xc5, 0x25, 0x68, 0x9d, 0xbf, 0x17, 0x77,
     418             :         0x96, 0x58, 0x74, 0x1b, 0x95, 0xc1, 0x5a, 0x55,
     419             :     }),
     420             : };
     421             : 
     422     3388440 : PedersenHash PedersenHash::EmptyRoot(size_t depth) {
     423     3388440 :     return pedersen_empty_roots.at(depth);
     424             : }
     425             : 
     426          64 : SHA256Compress SHA256Compress::combine(
     427             :     const SHA256Compress& a,
     428             :     const SHA256Compress& b,
     429             :     size_t depth
     430             : )
     431             : {
     432          64 :     SHA256Compress res = SHA256Compress();
     433             : 
     434          64 :     CSHA256 hasher;
     435          64 :     hasher.Write(a.begin(), 32);
     436          64 :     hasher.Write(b.begin(), 32);
     437          64 :     hasher.FinalizeNoPadding(res.begin());
     438             : 
     439          64 :     return res;
     440             : }
     441             : 
     442             : static const std::array<SHA256Compress, 66> sha256_empty_roots = {
     443             :     uint256(std::vector<unsigned char>{
     444             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
     445             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
     446             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
     447             :         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
     448             :     }),
     449             :     uint256(std::vector<unsigned char>{
     450             :         0xda, 0x56, 0x98, 0xbe, 0x17, 0xb9, 0xb4, 0x69,
     451             :         0x62, 0x33, 0x57, 0x99, 0x77, 0x9f, 0xbe, 0xca,
     452             :         0x8c, 0xe5, 0xd4, 0x91, 0xc0, 0xd2, 0x62, 0x43,
     453             :         0xba, 0xfe, 0xf9, 0xea, 0x18, 0x37, 0xa9, 0xd8,
     454             :     }),
     455             :     uint256(std::vector<unsigned char>{
     456             :         0xdc, 0x76, 0x6f, 0xab, 0x49, 0x2c, 0xcf, 0x3d,
     457             :         0x1e, 0x49, 0xd4, 0xf3, 0x74, 0xb5, 0x23, 0x5f,
     458             :         0xa5, 0x65, 0x06, 0xaa, 0xc2, 0x22, 0x4d, 0x39,
     459             :         0xf9, 0x43, 0xfc, 0xd4, 0x92, 0x02, 0x97, 0x4c,
     460             :     }),
     461             :     uint256(std::vector<unsigned char>{
     462             :         0x3f, 0x0a, 0x40, 0x61, 0x81, 0x10, 0x59, 0x68,
     463             :         0xfd, 0xae, 0xe3, 0x06, 0x79, 0xe3, 0x27, 0x3c,
     464             :         0x66, 0xb7, 0x2b, 0xf9, 0xa7, 0xf5, 0xde, 0xbb,
     465             :         0xf3, 0xb5, 0xa0, 0xa2, 0x6e, 0x35, 0x9f, 0x92,
     466             :     }),
     467             :     uint256(std::vector<unsigned char>{
     468             :         0x26, 0xb0, 0x05, 0x26, 0x94, 0xfc, 0x42, 0xfd,
     469             :         0xff, 0x93, 0xe6, 0xfb, 0x5a, 0x71, 0xd3, 0x8c,
     470             :         0x3d, 0xd7, 0xdc, 0x5b, 0x6a, 0xd7, 0x10, 0xeb,
     471             :         0x04, 0x8c, 0x66, 0x02, 0x33, 0x13, 0x7f, 0xab,
     472             :     }),
     473             :     uint256(std::vector<unsigned char>{
     474             :         0x01, 0x09, 0xec, 0xc0, 0x72, 0x26, 0x59, 0xff,
     475             :         0x83, 0x45, 0x0b, 0x8f, 0x7b, 0x88, 0x46, 0xe6,
     476             :         0x7b, 0x28, 0x59, 0xf3, 0x3c, 0x30, 0xd9, 0xb7,
     477             :         0xac, 0xd5, 0xbf, 0x39, 0xca, 0xe5, 0x4e, 0x31,
     478             :     }),
     479             :     uint256(std::vector<unsigned char>{
     480             :         0x3f, 0x90, 0x9b, 0x8c, 0xe3, 0xd7, 0xff, 0xd8,
     481             :         0xa5, 0xb3, 0x09, 0x08, 0xf6, 0x05, 0xa0, 0x3b,
     482             :         0x0d, 0xb8, 0x51, 0x69, 0x55, 0x8d, 0xdc, 0x1d,
     483             :         0xa7, 0xbb, 0xbc, 0xc9, 0xb0, 0x9f, 0xd3, 0x25,
     484             :     }),
     485             :     uint256(std::vector<unsigned char>{
     486             :         0x40, 0x46, 0x0f, 0xa6, 0xbc, 0x69, 0x2a, 0x06,
     487             :         0xf4, 0x75, 0x21, 0xa6, 0x72, 0x5a, 0x54, 0x7c,
     488             :         0x02, 0x8a, 0x6a, 0x24, 0x0d, 0x84, 0x09, 0xf1,
     489             :         0x65, 0xe6, 0x3c, 0xb5, 0x4d, 0xa2, 0xd2, 0x3f,
     490             :     }),
     491             :     uint256(std::vector<unsigned char>{
     492             :         0x8c, 0x08, 0x56, 0x74, 0x24, 0x9b, 0x43, 0xda,
     493             :         0x1b, 0x9a, 0x31, 0xa0, 0xe8, 0x20, 0xe8, 0x1e,
     494             :         0x75, 0xf3, 0x42, 0x80, 0x7b, 0x03, 0xb6, 0xb9,
     495             :         0xe6, 0x49, 0x83, 0x21, 0x7b, 0xc2, 0xb3, 0x8e,
     496             :     }),
     497             :     uint256(std::vector<unsigned char>{
     498             :         0xa0, 0x83, 0x45, 0x0c, 0x1b, 0xa2, 0xa3, 0xa7,
     499             :         0xbe, 0x76, 0xfa, 0xd9, 0xd1, 0x3b, 0xc3, 0x7b,
     500             :         0xe4, 0xbf, 0x83, 0xbd, 0x3e, 0x59, 0xfc, 0x37,
     501             :         0x5a, 0x36, 0xba, 0x62, 0xdc, 0x62, 0x02, 0x98,
     502             :     }),
     503             :     uint256(std::vector<unsigned char>{
     504             :         0x1d, 0xdd, 0xda, 0xbc, 0x2c, 0xaa, 0x2d, 0xe9,
     505             :         0xef, 0xf9, 0xe1, 0x8c, 0x8c, 0x5a, 0x39, 0x40,
     506             :         0x6d, 0x79, 0x36, 0xe8, 0x89, 0xbc, 0x16, 0xcf,
     507             :         0xab, 0xb1, 0x44, 0xf5, 0xc0, 0x02, 0x26, 0x82,
     508             :     }),
     509             :     uint256(std::vector<unsigned char>{
     510             :         0xc2, 0x2d, 0x8f, 0x0b, 0x5e, 0x40, 0x56, 0xe5,
     511             :         0xf3, 0x18, 0xba, 0x22, 0x09, 0x1c, 0xc0, 0x7d,
     512             :         0xb5, 0x69, 0x4f, 0xbe, 0xb5, 0xe8, 0x7e, 0xf0,
     513             :         0xd7, 0xe2, 0xc5, 0x7c, 0xa3, 0x52, 0x35, 0x9e,
     514             :     }),
     515             :     uint256(std::vector<unsigned char>{
     516             :         0x89, 0xa4, 0x34, 0xae, 0x1f, 0xeb, 0xd7, 0x68,
     517             :         0x7e, 0xce, 0xea, 0x21, 0xd0, 0x7f, 0x20, 0xa2,
     518             :         0x51, 0x24, 0x49, 0xd0, 0x8c, 0xe2, 0xee, 0xe5,
     519             :         0x58, 0x71, 0xcd, 0xb9, 0xd4, 0x6c, 0x12, 0x33,
     520             :     }),
     521             :     uint256(std::vector<unsigned char>{
     522             :         0x73, 0x33, 0xdb, 0xff, 0xbd, 0x11, 0xf0, 0x92,
     523             :         0x47, 0xa2, 0xb3, 0x3a, 0x01, 0x3e, 0xc4, 0xc4,
     524             :         0x34, 0x20, 0x29, 0xd8, 0x51, 0xe2, 0x2b, 0xa4,
     525             :         0x85, 0xd4, 0x46, 0x18, 0x51, 0x37, 0x0c, 0x15,
     526             :     }),
     527             :     uint256(std::vector<unsigned char>{
     528             :         0x5d, 0xad, 0x84, 0x4a, 0xb9, 0x46, 0x6b, 0x70,
     529             :         0xf7, 0x45, 0x13, 0x71, 0x95, 0xca, 0x22, 0x1b,
     530             :         0x48, 0xf3, 0x46, 0xab, 0xd1, 0x45, 0xfb, 0x5e,
     531             :         0xfc, 0x23, 0xa8, 0xb4, 0xba, 0x50, 0x80, 0x22,
     532             :     }),
     533             :     uint256(std::vector<unsigned char>{
     534             :         0x50, 0x7e, 0x0d, 0xae, 0x81, 0xcb, 0xfb, 0xe4,
     535             :         0x57, 0xfd, 0x37, 0x0e, 0xf1, 0xca, 0x42, 0x01,
     536             :         0xc2, 0xb6, 0x40, 0x10, 0x83, 0xdd, 0xab, 0x44,
     537             :         0x0e, 0x4a, 0x03, 0x8d, 0xc1, 0xe3, 0x58, 0xc4,
     538             :     }),
     539             :     uint256(std::vector<unsigned char>{
     540             :         0xbd, 0xcd, 0xb3, 0x29, 0x31, 0x88, 0xc9, 0x80,
     541             :         0x7d, 0x80, 0x82, 0x67, 0x01, 0x86, 0x84, 0xcf,
     542             :         0xec, 0xe0, 0x7a, 0xc3, 0x5a, 0x42, 0xc0, 0x0f,
     543             :         0x2c, 0x79, 0xb4, 0x00, 0x38, 0x25, 0x30, 0x5d,
     544             :     }),
     545             :     uint256(std::vector<unsigned char>{
     546             :         0xba, 0xb5, 0x80, 0x09, 0x72, 0xa1, 0x6c, 0x2c,
     547             :         0x22, 0x53, 0x0c, 0x66, 0x06, 0x6d, 0x0a, 0x58,
     548             :         0x67, 0xe9, 0x87, 0xbe, 0xd2, 0x1a, 0x6d, 0x5a,
     549             :         0x45, 0x0b, 0x68, 0x3c, 0xf1, 0xcf, 0xd7, 0x09,
     550             :     }),
     551             :     uint256(std::vector<unsigned char>{
     552             :         0x11, 0xaa, 0x0b, 0x4a, 0xd2, 0x9b, 0x13, 0xb0,
     553             :         0x57, 0xa3, 0x16, 0x19, 0xd6, 0x50, 0x0d, 0x63,
     554             :         0x6c, 0xd7, 0x35, 0xcd, 0xd0, 0x7d, 0x81, 0x1e,
     555             :         0xa2, 0x65, 0xec, 0x4b, 0xcb, 0xbb, 0xd0, 0x58,
     556             :     }),
     557             :     uint256(std::vector<unsigned char>{
     558             :         0x51, 0x45, 0xb1, 0xb0, 0x55, 0xc2, 0xdf, 0x02,
     559             :         0xb9, 0x56, 0x75, 0xe3, 0x79, 0x7b, 0x91, 0xde,
     560             :         0x1b, 0x84, 0x6d, 0x25, 0x00, 0x3c, 0x0a, 0x80,
     561             :         0x3d, 0x08, 0x90, 0x07, 0x28, 0xf2, 0xcd, 0x6a,
     562             :     }),
     563             :     uint256(std::vector<unsigned char>{
     564             :         0x03, 0x23, 0xf2, 0x85, 0x0b, 0xf3, 0x44, 0x4f,
     565             :         0x4b, 0x4c, 0x5c, 0x09, 0xa6, 0x05, 0x7e, 0xc7,
     566             :         0x16, 0x91, 0x90, 0xf4, 0x5a, 0xcb, 0x9e, 0x46,
     567             :         0x98, 0x4a, 0xb3, 0xdf, 0xce, 0xc4, 0xf0, 0x6a,
     568             :     }),
     569             :     uint256(std::vector<unsigned char>{
     570             :         0x67, 0x15, 0x46, 0xe2, 0x6b, 0x1d, 0xa1, 0xaf,
     571             :         0x75, 0x45, 0x31, 0xe2, 0x6d, 0x8a, 0x6a, 0x51,
     572             :         0x07, 0x3a, 0x57, 0xdd, 0xd7, 0x2d, 0xc4, 0x72,
     573             :         0xef, 0xb4, 0x3f, 0xcb, 0x25, 0x7c, 0xff, 0xff,
     574             :     }),
     575             :     uint256(std::vector<unsigned char>{
     576             :         0xbb, 0x23, 0xa9, 0xbb, 0xa5, 0x6d, 0xe5, 0x7c,
     577             :         0xb2, 0x84, 0xb0, 0xd2, 0xb0, 0x1c, 0x64, 0x2c,
     578             :         0xf7, 0x9c, 0x9a, 0x55, 0x63, 0xf0, 0x06, 0x7a,
     579             :         0x21, 0x29, 0x24, 0x12, 0x14, 0x5b, 0xd7, 0x8a,
     580             :     }),
     581             :     uint256(std::vector<unsigned char>{
     582             :         0xf3, 0x0c, 0xc8, 0x36, 0xb9, 0xf7, 0x1b, 0x4e,
     583             :         0x7e, 0xe3, 0xc7, 0x2b, 0x1f, 0xd2, 0x53, 0x26,
     584             :         0x8a, 0xf9, 0xa2, 0x7e, 0x9d, 0x72, 0x91, 0xa2,
     585             :         0x3d, 0x02, 0x82, 0x1b, 0x21, 0xdd, 0xfd, 0x16,
     586             :     }),
     587             :     uint256(std::vector<unsigned char>{
     588             :         0x58, 0xa2, 0x75, 0x3d, 0xad, 0xe1, 0x03, 0xce,
     589             :         0xcb, 0xcd, 0xa5, 0x0b, 0x5e, 0xbf, 0xce, 0x31,
     590             :         0xe1, 0x2d, 0x41, 0xd5, 0x84, 0x1d, 0xcc, 0x95,
     591             :         0x62, 0x0f, 0x7b, 0x3d, 0x50, 0xa1, 0xb9, 0xa1,
     592             :     }),
     593             :     uint256(std::vector<unsigned char>{
     594             :         0x92, 0x5e, 0x6d, 0x47, 0x4a, 0x5d, 0x8d, 0x30,
     595             :         0x04, 0xf2, 0x9d, 0xa0, 0xdd, 0x78, 0xd3, 0x0a,
     596             :         0xe3, 0x82, 0x4c, 0xe7, 0x9d, 0xfe, 0x49, 0x34,
     597             :         0xbb, 0x29, 0xec, 0x3a, 0xfa, 0xf3, 0xd5, 0x21,
     598             :     }),
     599             :     uint256(std::vector<unsigned char>{
     600             :         0x08, 0xf2, 0x79, 0x61, 0x86, 0x16, 0xbc, 0xdd,
     601             :         0x4e, 0xad, 0xc9, 0xc7, 0xa9, 0x06, 0x26, 0x91,
     602             :         0xa5, 0x9b, 0x43, 0xb0, 0x7e, 0x2c, 0x1e, 0x23,
     603             :         0x7f, 0x17, 0xbd, 0x18, 0x9c, 0xd6, 0xa8, 0xfe,
     604             :     }),
     605             :     uint256(std::vector<unsigned char>{
     606             :         0xc9, 0x2b, 0x32, 0xdb, 0x42, 0xf4, 0x2e, 0x2b,
     607             :         0xf0, 0xa5, 0x9d, 0xf9, 0x05, 0x5b, 0xe5, 0xc6,
     608             :         0x69, 0xd3, 0x24, 0x2d, 0xf4, 0x53, 0x57, 0x65,
     609             :         0x9b, 0x75, 0xae, 0x2c, 0x27, 0xa7, 0x6f, 0x50,
     610             :     }),
     611             :     uint256(std::vector<unsigned char>{
     612             :         0xc0, 0xdb, 0x2a, 0x74, 0x99, 0x8c, 0x50, 0xeb,
     613             :         0x7b, 0xa6, 0x53, 0x4f, 0x6d, 0x41, 0x0e, 0xfc,
     614             :         0x27, 0xc4, 0xbb, 0x88, 0xac, 0xb0, 0x22, 0x2c,
     615             :         0x79, 0x06, 0xea, 0x28, 0xa3, 0x27, 0xb5, 0x11,
     616             :     }),
     617             :     uint256(std::vector<unsigned char>{
     618             :         0xd7, 0xc6, 0x12, 0xc8, 0x17, 0x79, 0x31, 0x91,
     619             :         0xa1, 0xe6, 0x86, 0x52, 0x12, 0x18, 0x76, 0xd6,
     620             :         0xb3, 0xbd, 0xe4, 0x0f, 0x4f, 0xa5, 0x2b, 0xc3,
     621             :         0x14, 0x14, 0x5c, 0xe6, 0xe5, 0xcd, 0xd2, 0x59,
     622             :     }),
     623             :     uint256(std::vector<unsigned char>{
     624             :         0xb2, 0x23, 0x70, 0x10, 0x6c, 0x67, 0xa1, 0x72,
     625             :         0x09, 0xf6, 0x13, 0x0b, 0xc0, 0x9f, 0x73, 0x5d,
     626             :         0x83, 0xaa, 0x2c, 0x04, 0xfc, 0x4f, 0xe7, 0x2e,
     627             :         0xa5, 0xd8, 0x0b, 0x21, 0x67, 0x23, 0xe7, 0xce,
     628             :     }),
     629             :     uint256(std::vector<unsigned char>{
     630             :         0x9f, 0x67, 0xd5, 0xf6, 0x64, 0x66, 0x4c, 0x90,
     631             :         0x19, 0x40, 0xee, 0xe3, 0xd0, 0x2d, 0xd5, 0xb3,
     632             :         0xe4, 0xb9, 0x2e, 0x7b, 0x42, 0x82, 0x0c, 0x42,
     633             :         0xfc, 0x51, 0x59, 0xe9, 0x1b, 0x41, 0x17, 0x2a,
     634             :     }),
     635             :     uint256(std::vector<unsigned char>{
     636             :         0xac, 0x58, 0xcd, 0x13, 0x88, 0xfe, 0xc2, 0x90,
     637             :         0xd3, 0x98, 0xf1, 0x94, 0x4b, 0x56, 0x44, 0x49,
     638             :         0xa6, 0x3c, 0x81, 0x58, 0x80, 0x56, 0x6b, 0xd1,
     639             :         0xd1, 0x89, 0xf7, 0x83, 0x9e, 0x3b, 0x0c, 0x8c,
     640             :     }),
     641             :     uint256(std::vector<unsigned char>{
     642             :         0x56, 0x98, 0xea, 0xe7, 0xc8, 0x51, 0x5e, 0xd0,
     643             :         0x5a, 0x70, 0x33, 0x9b, 0xdf, 0x7c, 0x10, 0x28,
     644             :         0xe7, 0xac, 0xca, 0x13, 0xa4, 0xfa, 0x97, 0xd9,
     645             :         0x53, 0x8f, 0x01, 0xac, 0x8d, 0x88, 0x9a, 0xe3,
     646             :     }),
     647             :     uint256(std::vector<unsigned char>{
     648             :         0x2d, 0x49, 0x95, 0x77, 0x0a, 0x76, 0xfb, 0x93,
     649             :         0x31, 0x4c, 0xa7, 0x4b, 0x35, 0x24, 0xea, 0x1d,
     650             :         0xb5, 0x68, 0x8a, 0xd0, 0xa7, 0x61, 0x83, 0xea,
     651             :         0x17, 0x20, 0x4a, 0x8f, 0x02, 0x4a, 0x9f, 0x3b,
     652             :     }),
     653             :     uint256(std::vector<unsigned char>{
     654             :         0x5e, 0x89, 0x92, 0xc1, 0xb0, 0x72, 0xc1, 0x6e,
     655             :         0x9e, 0x28, 0xa8, 0x53, 0x58, 0xfb, 0x5f, 0xb6,
     656             :         0x90, 0x1a, 0x81, 0x58, 0x77, 0x66, 0xda, 0xdb,
     657             :         0x7a, 0xa0, 0xb9, 0x73, 0xde, 0xd2, 0xf2, 0x64,
     658             :     }),
     659             :     uint256(std::vector<unsigned char>{
     660             :         0xe9, 0x5d, 0xb7, 0x1e, 0x1f, 0x72, 0x91, 0xba,
     661             :         0x54, 0x99, 0x46, 0x1b, 0xc7, 0x15, 0x20, 0x3e,
     662             :         0x29, 0xb8, 0x4b, 0xfa, 0x42, 0x83, 0xe3, 0xbb,
     663             :         0x7f, 0x47, 0x0a, 0x15, 0xd0, 0xe1, 0x58, 0x4e,
     664             :     }),
     665             :     uint256(std::vector<unsigned char>{
     666             :         0x41, 0xf0, 0x78, 0xbd, 0x18, 0x24, 0xc8, 0xa4,
     667             :         0xb7, 0x19, 0x64, 0xf3, 0x94, 0xaa, 0x59, 0x50,
     668             :         0x84, 0xd8, 0xeb, 0x17, 0xb9, 0x7a, 0x36, 0x30,
     669             :         0x43, 0x3a, 0xf7, 0x0d, 0x10, 0xe0, 0xef, 0xf6,
     670             :     }),
     671             :     uint256(std::vector<unsigned char>{
     672             :         0xa1, 0x91, 0x3f, 0xe6, 0xb2, 0x01, 0x32, 0x31,
     673             :         0x2f, 0x8c, 0x1f, 0x00, 0xdd, 0xd6, 0x3c, 0xec,
     674             :         0x7a, 0x03, 0xf5, 0xf1, 0xd7, 0xd8, 0x34, 0x92,
     675             :         0xfa, 0x28, 0x4c, 0x0b, 0x5d, 0x63, 0x20, 0xb0,
     676             :     }),
     677             :     uint256(std::vector<unsigned char>{
     678             :         0xba, 0x94, 0x40, 0xc4, 0xdb, 0xfc, 0xf5, 0x5c,
     679             :         0xeb, 0x60, 0x5a, 0x5b, 0x89, 0x90, 0xfc, 0x11,
     680             :         0xf8, 0xef, 0x22, 0x87, 0x0d, 0x8d, 0x12, 0xe1,
     681             :         0x30, 0xf9, 0x86, 0x49, 0x1e, 0xae, 0x84, 0xb3,
     682             :     }),
     683             :     uint256(std::vector<unsigned char>{
     684             :         0x49, 0xdb, 0x2d, 0x5e, 0x22, 0xb8, 0x01, 0x5c,
     685             :         0xae, 0x48, 0x10, 0xd7, 0x5e, 0x54, 0x01, 0x4c,
     686             :         0x54, 0x69, 0x86, 0x27, 0x38, 0xe1, 0x61, 0xec,
     687             :         0x96, 0xec, 0x20, 0x21, 0x87, 0x18, 0x82, 0x8a,
     688             :     }),
     689             :     uint256(std::vector<unsigned char>{
     690             :         0xd4, 0x85, 0x1f, 0xb8, 0x43, 0x1e, 0xdf, 0xbb,
     691             :         0x8b, 0x1e, 0x85, 0xad, 0xa6, 0x89, 0x59, 0x67,
     692             :         0xc2, 0xda, 0xc8, 0x7d, 0xf3, 0x44, 0x99, 0x2a,
     693             :         0x05, 0xfa, 0xf1, 0xec, 0xf8, 0x36, 0xee, 0xc9,
     694             :     }),
     695             :     uint256(std::vector<unsigned char>{
     696             :         0xe4, 0xab, 0x9f, 0x44, 0x70, 0xf0, 0x0c, 0xd1,
     697             :         0x96, 0xd4, 0x7c, 0x75, 0xc8, 0x2e, 0x7a, 0xda,
     698             :         0xf0, 0x6f, 0xe1, 0x7e, 0x04, 0x2e, 0x39, 0x53,
     699             :         0xd9, 0x3b, 0xb5, 0xd5, 0x6d, 0x8c, 0xd8, 0xfb,
     700             :     }),
     701             :     uint256(std::vector<unsigned char>{
     702             :         0x7e, 0x43, 0x20, 0x43, 0x48, 0x49, 0xec, 0xb3,
     703             :         0x57, 0xf1, 0xaf, 0xaa, 0xba, 0x21, 0xa5, 0x44,
     704             :         0x00, 0xef, 0x2d, 0x11, 0xcf, 0xf8, 0x3b, 0x93,
     705             :         0x7d, 0x87, 0xfd, 0xaf, 0xa4, 0x9f, 0x81, 0x99,
     706             :     }),
     707             :     uint256(std::vector<unsigned char>{
     708             :         0x02, 0x0a, 0xdc, 0x98, 0xd9, 0x6c, 0xfb, 0xbc,
     709             :         0xca, 0x15, 0xfc, 0x3a, 0xa0, 0x37, 0x60, 0xed,
     710             :         0x28, 0x66, 0x86, 0xc3, 0x5b, 0x5d, 0x92, 0xc7,
     711             :         0xcb, 0x64, 0xa9, 0x99, 0xb3, 0x94, 0xa8, 0x54,
     712             :     }),
     713             :     uint256(std::vector<unsigned char>{
     714             :         0x3a, 0x26, 0xb2, 0x9f, 0xe1, 0xac, 0xfd, 0xd6,
     715             :         0xc6, 0xa1, 0x51, 0xbc, 0xc3, 0xdb, 0xcb, 0x95,
     716             :         0xa1, 0x0e, 0xbe, 0x2f, 0x05, 0x53, 0xf8, 0x07,
     717             :         0x79, 0x56, 0x9b, 0x67, 0xb7, 0x24, 0x4e, 0x77,
     718             :     }),
     719             :     uint256(std::vector<unsigned char>{
     720             :         0xec, 0x2d, 0x09, 0x86, 0xe6, 0xa0, 0xdd, 0xf4,
     721             :         0x38, 0x97, 0xb2, 0xd4, 0xf2, 0x3b, 0xb0, 0x34,
     722             :         0xf5, 0x38, 0xff, 0xe0, 0x08, 0x27, 0xf3, 0x10,
     723             :         0xdc, 0x49, 0x63, 0xf3, 0x26, 0x7f, 0x0b, 0xfb,
     724             :     }),
     725             :     uint256(std::vector<unsigned char>{
     726             :         0xd4, 0x80, 0x73, 0xf8, 0x81, 0x9f, 0x81, 0xf0,
     727             :         0x35, 0x8e, 0x3f, 0xc3, 0x5a, 0x04, 0x7c, 0xc7,
     728             :         0x40, 0x82, 0xae, 0x1c, 0xb7, 0xee, 0x22, 0xfb,
     729             :         0x60, 0x9c, 0x01, 0x64, 0x93, 0x42, 0xd0, 0xe6,
     730             :     }),
     731             :     uint256(std::vector<unsigned char>{
     732             :         0xad, 0x80, 0x37, 0x60, 0x17, 0x93, 0xf1, 0x72,
     733             :         0x44, 0x1e, 0xcb, 0x00, 0xdc, 0x13, 0x8d, 0x9f,
     734             :         0xc5, 0x95, 0x71, 0x25, 0xec, 0xc3, 0x82, 0xec,
     735             :         0x65, 0xe3, 0x6f, 0x81, 0x7d, 0xc7, 0x99, 0xfb,
     736             :     }),
     737             :     uint256(std::vector<unsigned char>{
     738             :         0xca, 0x50, 0x0a, 0x54, 0x41, 0xf3, 0x6f, 0x4d,
     739             :         0xf6, 0x73, 0xd6, 0xb8, 0xed, 0x07, 0x5d, 0x36,
     740             :         0xda, 0xe2, 0xc7, 0xe6, 0x48, 0x14, 0x28, 0xc7,
     741             :         0x0a, 0x5a, 0x76, 0xb7, 0xa9, 0xbe, 0xbc, 0xe8,
     742             :     }),
     743             :     uint256(std::vector<unsigned char>{
     744             :         0x42, 0x2b, 0x6d, 0xdd, 0x47, 0x32, 0x31, 0xdc,
     745             :         0x4d, 0x56, 0xfe, 0x91, 0x34, 0x44, 0xcc, 0xd5,
     746             :         0x6f, 0x7c, 0x61, 0xf7, 0x47, 0xba, 0x57, 0xca,
     747             :         0x94, 0x6d, 0x5f, 0xef, 0x72, 0xd8, 0x40, 0xa0,
     748             :     }),
     749             :     uint256(std::vector<unsigned char>{
     750             :         0xab, 0x41, 0xf4, 0xec, 0xb7, 0xd7, 0x08, 0x96,
     751             :         0x15, 0x80, 0x0e, 0x19, 0xfc, 0xc5, 0x3b, 0x83,
     752             :         0x79, 0xed, 0x05, 0xee, 0x35, 0xc8, 0x25, 0x67,
     753             :         0x09, 0x55, 0x83, 0xfd, 0x90, 0xff, 0x30, 0x35,
     754             :     }),
     755             :     uint256(std::vector<unsigned char>{
     756             :         0xbb, 0xf7, 0x61, 0x82, 0x48, 0x35, 0x4c, 0xeb,
     757             :         0x1b, 0xc1, 0xfc, 0x9d, 0xbc, 0x42, 0xc4, 0x26,
     758             :         0xa4, 0xe2, 0xc1, 0xe0, 0xd4, 0x43, 0xc5, 0x68,
     759             :         0x3a, 0x92, 0x56, 0xc6, 0x2e, 0xcd, 0xc2, 0x6f,
     760             :     }),
     761             :     uint256(std::vector<unsigned char>{
     762             :         0xe5, 0x0a, 0xe7, 0x14, 0x79, 0xfc, 0x8e, 0xc5,
     763             :         0x69, 0x19, 0x2a, 0x13, 0x07, 0x2e, 0x01, 0x1a,
     764             :         0xfc, 0x24, 0x9f, 0x47, 0x1a, 0xf0, 0x95, 0x00,
     765             :         0xea, 0x39, 0xf7, 0x5d, 0x0a, 0xf8, 0x56, 0xbf,
     766             :     }),
     767             :     uint256(std::vector<unsigned char>{
     768             :         0xe7, 0x4c, 0x0b, 0x92, 0x20, 0x14, 0x7d, 0xb2,
     769             :         0xd5, 0x0a, 0x3b, 0x58, 0xd4, 0x13, 0x77, 0x5d,
     770             :         0x16, 0xc9, 0x84, 0x69, 0x0b, 0xe7, 0xd9, 0x0f,
     771             :         0x0b, 0xc4, 0x3d, 0x99, 0xdb, 0xa1, 0xb6, 0x89,
     772             :     }),
     773             :     uint256(std::vector<unsigned char>{
     774             :         0x29, 0x32, 0x4a, 0x0a, 0x48, 0xd1, 0x16, 0x57,
     775             :         0xa5, 0x1b, 0xa0, 0x8b, 0x00, 0x48, 0x79, 0xbf,
     776             :         0xcf, 0xc6, 0x6a, 0x1a, 0xcb, 0x7c, 0xe3, 0x6d,
     777             :         0xfe, 0x47, 0x8d, 0x26, 0x55, 0x48, 0x4b, 0x48,
     778             :     }),
     779             :     uint256(std::vector<unsigned char>{
     780             :         0x88, 0x95, 0x2e, 0x3d, 0x0a, 0xc0, 0x6c, 0xb1,
     781             :         0x6b, 0x66, 0x52, 0x01, 0x12, 0x22, 0x49, 0x65,
     782             :         0x9a, 0x22, 0x32, 0x5e, 0x01, 0xc8, 0x70, 0xf4,
     783             :         0x9e, 0x29, 0xda, 0x6b, 0x17, 0x57, 0xe0, 0x82,
     784             :     }),
     785             :     uint256(std::vector<unsigned char>{
     786             :         0xcd, 0xf8, 0x79, 0xf2, 0x43, 0x5b, 0x95, 0xaf,
     787             :         0x04, 0x2a, 0x3b, 0xf7, 0xb8, 0x50, 0xf7, 0x81,
     788             :         0x92, 0x46, 0xc8, 0x05, 0x28, 0x58, 0x03, 0xd6,
     789             :         0x7f, 0xfb, 0xf4, 0xf2, 0x95, 0xbe, 0xd0, 0x04,
     790             :     }),
     791             :     uint256(std::vector<unsigned char>{
     792             :         0xe0, 0x05, 0xe3, 0x24, 0x20, 0x0b, 0x4f, 0x42,
     793             :         0x8c, 0x62, 0xbc, 0x33, 0x31, 0xe6, 0x95, 0xc3,
     794             :         0x73, 0x60, 0x7c, 0xd0, 0xfa, 0xa9, 0x79, 0x03,
     795             :         0x41, 0xfa, 0x3b, 0xa1, 0xed, 0x22, 0x8b, 0xc5,
     796             :     }),
     797             :     uint256(std::vector<unsigned char>{
     798             :         0x35, 0x44, 0x47, 0x72, 0x7a, 0xa9, 0xa5, 0x3d,
     799             :         0xd8, 0x34, 0x5b, 0x6b, 0x6c, 0x69, 0x34, 0x43,
     800             :         0xe5, 0x6e, 0xf4, 0xae, 0xba, 0x13, 0xc4, 0x10,
     801             :         0x17, 0x9f, 0xc8, 0x58, 0x9e, 0x77, 0x33, 0xd5,
     802             :     }),
     803             :     uint256(std::vector<unsigned char>{
     804             :         0xda, 0x52, 0xdd, 0xa9, 0x1f, 0x28, 0x29, 0xc1,
     805             :         0x5c, 0x0e, 0x58, 0xd2, 0x9a, 0x95, 0x36, 0x0b,
     806             :         0x86, 0xab, 0x30, 0xcf, 0x0c, 0xac, 0x81, 0x01,
     807             :         0x83, 0x2a, 0x29, 0xf3, 0x8c, 0x31, 0x85, 0xf1,
     808             :     }),
     809             :     uint256(std::vector<unsigned char>{
     810             :         0xc7, 0xda, 0x78, 0x14, 0xe2, 0x28, 0xe1, 0x14,
     811             :         0x44, 0x11, 0xd7, 0x8b, 0x53, 0x60, 0x92, 0xfe,
     812             :         0x92, 0x0b, 0xcd, 0xfc, 0xc3, 0x6c, 0xf1, 0x9d,
     813             :         0x12, 0x59, 0x04, 0x7b, 0x26, 0x7d, 0x58, 0xb5,
     814             :     }),
     815             :     uint256(std::vector<unsigned char>{
     816             :         0xab, 0xa1, 0xf6, 0x8b, 0x6c, 0x2b, 0x4d, 0xb6,
     817             :         0xcc, 0x06, 0xa7, 0x34, 0x0e, 0x12, 0x31, 0x3c,
     818             :         0x4b, 0x4a, 0x4e, 0xa6, 0xde, 0xb1, 0x7d, 0xeb,
     819             :         0x3e, 0x1e, 0x66, 0xcd, 0x8e, 0xac, 0xf3, 0x2b,
     820             :     }),
     821             :     uint256(std::vector<unsigned char>{
     822             :         0xc1, 0x60, 0xae, 0x4f, 0x64, 0xab, 0x76, 0x4d,
     823             :         0x86, 0x4a, 0x52, 0xad, 0x5e, 0x33, 0x12, 0x6c,
     824             :         0x4b, 0x5c, 0xe1, 0x05, 0xa4, 0x7d, 0xee, 0xdd,
     825             :         0x75, 0xbc, 0x70, 0x19, 0x9a, 0x52, 0x47, 0xef,
     826             :     }),
     827             :     uint256(std::vector<unsigned char>{
     828             :         0xea, 0xdf, 0x23, 0xfc, 0x99, 0xd5, 0x14, 0xdd,
     829             :         0x8e, 0xa2, 0x04, 0xd2, 0x23, 0xe9, 0x8d, 0xa9,
     830             :         0x88, 0x83, 0x1f, 0x9b, 0x5d, 0x19, 0x40, 0x27,
     831             :         0x4c, 0xa5, 0x20, 0xb7, 0xfb, 0x17, 0x3d, 0x8a,
     832             :     }),
     833             :     uint256(std::vector<unsigned char>{
     834             :         0x5b, 0x8e, 0x14, 0xfa, 0xca, 0xc8, 0xa7, 0xc7,
     835             :         0xa3, 0xbf, 0xee, 0x8b, 0xae, 0x71, 0xf2, 0xf7,
     836             :         0x79, 0x3d, 0x3a, 0xd5, 0xfe, 0x33, 0x83, 0xf9,
     837             :         0x3a, 0xb6, 0x06, 0x1f, 0x2a, 0x11, 0xbb, 0x02
     838             :     }),
     839             : };
     840             : 
     841          65 : SHA256Compress SHA256Compress::EmptyRoot(size_t depth) {
     842          65 :     return sha256_empty_roots.at(depth);
     843             : }
     844             : 
     845             : template <size_t Depth, typename Hash>
     846      127251 : class PathFiller {
     847             : private:
     848             :     std::deque<Hash> queue;
     849             :     static EmptyMerkleRoots<Depth, Hash> emptyroots;
     850             : public:
     851             :     PathFiller() : queue() { }
     852      127444 :     explicit PathFiller(std::deque<Hash> queue) : queue(queue) { }
     853             : 
     854     3433360 :     Hash next(size_t depth) {
     855     3433360 :         if (queue.size() > 0) {
     856       67995 :             Hash h = queue.front();
     857       67995 :             queue.pop_front();
     858             : 
     859       67995 :             return h;
     860             :         } else {
     861     3433360 :             return emptyroots.empty_root(depth);
     862             :         }
     863             :     }
     864             : 
     865             : };
     866             : 
     867             : template<size_t Depth, typename Hash>
     868             : EmptyMerkleRoots<Depth, Hash> PathFiller<Depth, Hash>::emptyroots;
     869             : 
     870             : template<size_t Depth, typename Hash>
     871        2742 : void IncrementalMerkleTree<Depth, Hash>::wfcheck() const {
     872        2742 :     if (parents.size() >= Depth) {
     873           0 :         throw std::ios_base::failure("tree has too many parents");
     874             :     }
     875             : 
     876             :     // The last parent cannot be null.
     877        2742 :     if (!(parents.empty()) && !(parents.back())) {
     878           0 :         throw std::ios_base::failure("tree has non-canonical representation of parent");
     879             :     }
     880             : 
     881             :     // Left cannot be empty when right exists.
     882        2742 :     if (!left && right) {
     883           0 :         throw std::ios_base::failure("tree has non-canonical representation; right should not exist");
     884             :     }
     885             : 
     886             :     // Left cannot be empty when parents is nonempty.
     887        2742 :     if (!left && parents.size() > 0) {
     888           0 :         throw std::ios_base::failure("tree has non-canonical representation; parents should not be unempty");
     889             :     }
     890        2742 : }
     891             : 
     892             : template<size_t Depth, typename Hash>
     893          33 : Hash IncrementalMerkleTree<Depth, Hash>::last() const {
     894          33 :     if (right) {
     895           8 :         return *right;
     896          25 :     } else if (left) {
     897           8 :         return *left;
     898             :     } else {
     899          17 :         throw std::runtime_error("tree has no cursor");
     900             :     }
     901             : }
     902             : 
     903             : template<size_t Depth, typename Hash>
     904         993 : size_t IncrementalMerkleTree<Depth, Hash>::size() const {
     905         993 :     size_t ret = 0;
     906         993 :     if (left) {
     907         992 :         ret++;
     908             :     }
     909         993 :     if (right) {
     910         476 :         ret++;
     911             :     }
     912             :     // Treat occupation of parents array as a binary number
     913             :     // (right-shifted by 1)
     914        6275 :     for (size_t i = 0; i < parents.size(); i++) {
     915        5282 :         if (parents[i]) {
     916        2905 :             ret += (1 << (i+1));
     917             :         }
     918             :     }
     919         993 :     return ret;
     920             : }
     921             : 
     922             : template<size_t Depth, typename Hash>
     923      204458 : void IncrementalMerkleTree<Depth, Hash>::append(Hash obj) {
     924      204458 :     if (is_complete(Depth)) {
     925           1 :         throw std::runtime_error("tree is full");
     926             :     }
     927             : 
     928      204457 :     if (!left) {
     929             :         // Set the left leaf
     930        3968 :         left = obj;
     931      200489 :     } else if (!right) {
     932             :         // Set the right leaf
     933      101783 :         right = obj;
     934             :     } else {
     935             :         // Combine the leaves and propagate it up the tree
     936      197412 :         Optional<Hash> combined = Hash::combine(*left, *right, 0);
     937             : 
     938             :         // Set the "left" leaf to the object and make the "right" leaf none
     939       98706 :         left = obj;
     940       98706 :         right = nullopt;
     941             : 
     942      186637 :         for (size_t i = 0; i < Depth; i++) {
     943      186637 :             if (i < parents.size()) {
     944      173761 :                 if (parents[i]) {
     945       87931 :                     combined = Hash::combine(*parents[i], *combined, i+1);
     946      175862 :                     parents[i] = nullopt;
     947             :                 } else {
     948       98706 :                     parents[i] = *combined;
     949             :                     break;
     950             :                 }
     951             :             } else {
     952       12876 :                 parents.push_back(combined);
     953             :                 break;
     954             :             }
     955             :         }
     956             :     }
     957      204457 : }
     958             : 
     959             : // This is for allowing the witness to determine if a subtree has filled
     960             : // to a particular depth, or for append() to ensure we're not appending
     961             : // to a full tree.
     962             : template<size_t Depth, typename Hash>
     963      399821 : bool IncrementalMerkleTree<Depth, Hash>::is_complete(size_t depth) const {
     964      399821 :     if (!left || !right) {
     965             :         return false;
     966             :     }
     967             : 
     968      197882 :     if (parents.size() != (depth - 1)) {
     969             :         return false;
     970             :     }
     971             : 
     972       70345 :     for (const Optional<Hash>& parent : parents) {
     973       67471 :         if (!parent) {
     974       32668 :             return false;
     975             :         }
     976             :     }
     977             : 
     978        2874 :     return true;
     979             : }
     980             : 
     981             : // This finds the next "depth" of an unfilled subtree, given that we've filled
     982             : // `skip` uncles/subtrees.
     983             : template<size_t Depth, typename Hash>
     984        4451 : size_t IncrementalMerkleTree<Depth, Hash>::next_depth(size_t skip) const {
     985        4451 :     if (!left) {
     986          22 :         if (skip) {
     987          21 :             skip--;
     988             :         } else {
     989             :             return 0;
     990             :         }
     991             :     }
     992             : 
     993        4450 :     if (!right) {
     994        2469 :         if (skip) {
     995        1974 :             skip--;
     996             :         } else {
     997             :             return 0;
     998             :         }
     999             :     }
    1000             : 
    1001        3955 :     size_t d = 1;
    1002             : 
    1003       16879 :     for (const Optional<Hash>& parent : parents) {
    1004       15208 :         if (!parent) {
    1005        8012 :             if (skip) {
    1006        5728 :                 skip--;
    1007             :             } else {
    1008        2284 :                 return d;
    1009             :             }
    1010             :         }
    1011             : 
    1012       12924 :         d++;
    1013             :     }
    1014             : 
    1015        1671 :     return d + skip;
    1016             : }
    1017             : 
    1018             : // This calculates the root of the tree.
    1019             : template<size_t Depth, typename Hash>
    1020      127251 : Hash IncrementalMerkleTree<Depth, Hash>::root(size_t depth,
    1021             :                                               std::deque<Hash> filler_hashes) const {
    1022      254502 :     PathFiller<Depth, Hash> filler(filler_hashes);
    1023             : 
    1024      127251 :     Hash combine_left =  left  ? *left  : filler.next(0);
    1025      127251 :     Hash combine_right = right ? *right : filler.next(0);
    1026             : 
    1027      127251 :     Hash root = Hash::combine(combine_left, combine_right, 0);
    1028             : 
    1029      127251 :     size_t d = 1;
    1030             : 
    1031      295489 :     for (const Optional<Hash>& parent : parents) {
    1032      168238 :         if (parent) {
    1033      114639 :             root = Hash::combine(*parent, root, d);
    1034             :         } else {
    1035       53599 :             root = Hash::combine(root, filler.next(d), d);
    1036             :         }
    1037             : 
    1038      168238 :         d++;
    1039             :     }
    1040             : 
    1041             :     // We may not have parents for ancestor trees, so we fill
    1042             :     // the rest in here.
    1043     3313105 :     while (d < depth) {
    1044     3185854 :         root = Hash::combine(root, filler.next(d), d);
    1045     3185854 :         d++;
    1046             :     }
    1047             : 
    1048      127251 :     return root;
    1049             : }
    1050             : 
    1051             : // This constructs an authentication path into the tree in the format that the circuit
    1052             : // wants. The caller provides `filler_hashes` to fill in the uncle subtrees.
    1053             : template<size_t Depth, typename Hash>
    1054         209 : MerklePath IncrementalMerkleTree<Depth, Hash>::path(std::deque<Hash> filler_hashes) const {
    1055         209 :     if (!left) {
    1056          16 :         throw std::runtime_error("can't create an authentication path for the beginning of the tree");
    1057             :     }
    1058             : 
    1059         386 :     PathFiller<Depth, Hash> filler(filler_hashes);
    1060             : 
    1061         386 :     std::vector<Hash> path;
    1062         193 :     std::vector<bool> index;
    1063             : 
    1064         193 :     if (right) {
    1065          78 :         index.push_back(true);
    1066          78 :         path.push_back(*left);
    1067             :     } else {
    1068         115 :         index.push_back(false);
    1069         230 :         path.push_back(filler.next(0));
    1070             :     }
    1071             : 
    1072         193 :     size_t d = 1;
    1073             : 
    1074         484 :     for (const Optional<Hash>& parent : parents) {
    1075         291 :         if (parent) {
    1076         191 :             index.push_back(true);
    1077         191 :             path.push_back(*parent);
    1078             :         } else {
    1079         100 :             index.push_back(false);
    1080         200 :             path.push_back(filler.next(d));
    1081             :         }
    1082             : 
    1083         291 :         d++;
    1084             :     }
    1085             : 
    1086        2525 :     while (d < Depth) {
    1087        2332 :         index.push_back(false);
    1088        2332 :         path.push_back(filler.next(d));
    1089        2332 :         d++;
    1090             :     }
    1091             : 
    1092         193 :     std::vector<std::vector<bool>> merkle_path;
    1093        3009 :     for (Hash b : path) {
    1094        5632 :         std::vector<unsigned char> hashv(b.begin(), b.end());
    1095             : 
    1096        5632 :         merkle_path.push_back(convertBytesVectorToVector(hashv));
    1097             :     }
    1098             : 
    1099         193 :     std::reverse(merkle_path.begin(), merkle_path.end());
    1100         193 :     std::reverse(index.begin(), index.end());
    1101             : 
    1102         386 :     return MerklePath(merkle_path, index);
    1103             : }
    1104             : 
    1105             : template<size_t Depth, typename Hash>
    1106       19413 : std::deque<Hash> IncrementalWitness<Depth, Hash>::partial_path() const {
    1107       19413 :     std::deque<Hash> uncles(filled.begin(), filled.end());
    1108             : 
    1109       19413 :     if (cursor) {
    1110       56163 :         uncles.push_back(cursor->root(cursor_depth));
    1111             :     }
    1112             : 
    1113       19413 :     return uncles;
    1114             : }
    1115             : 
    1116             : template<size_t Depth, typename Hash>
    1117      199677 : void IncrementalWitness<Depth, Hash>::append(Hash obj) {
    1118      199677 :     if (cursor) {
    1119      195363 :         cursor->append(obj);
    1120             : 
    1121      195363 :         if (cursor->is_complete(cursor_depth)) {
    1122        5746 :             filled.push_back(cursor->root(cursor_depth));
    1123        2873 :             cursor = nullopt;
    1124             :         }
    1125             :     } else {
    1126        4314 :         cursor_depth = tree.next_depth(filled.size());
    1127             : 
    1128        4314 :         if (cursor_depth >= Depth) {
    1129          16 :             throw std::runtime_error("tree is full");
    1130             :         }
    1131             : 
    1132        4298 :         if (cursor_depth == 0) {
    1133         494 :             filled.push_back(obj);
    1134             :         } else {
    1135        3804 :             cursor = IncrementalMerkleTree<Depth, Hash>();
    1136        3804 :             cursor->append(obj);
    1137             :         }
    1138             :     }
    1139      199661 : }
    1140             : 
    1141             : template class IncrementalMerkleTree<INCREMENTAL_MERKLE_TREE_DEPTH, SHA256Compress>;
    1142             : template class IncrementalMerkleTree<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, SHA256Compress>;
    1143             : 
    1144             : template class IncrementalWitness<INCREMENTAL_MERKLE_TREE_DEPTH, SHA256Compress>;
    1145             : template class IncrementalWitness<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, SHA256Compress>;
    1146             : 
    1147             : template class IncrementalMerkleTree<SAPLING_INCREMENTAL_MERKLE_TREE_DEPTH, PedersenHash>;
    1148             : template class IncrementalMerkleTree<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, PedersenHash>;
    1149             : 
    1150             : template class IncrementalWitness<SAPLING_INCREMENTAL_MERKLE_TREE_DEPTH, PedersenHash>;
    1151             : template class IncrementalWitness<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, PedersenHash>;
    1152             : 
    1153             : } // end namespace `libzcash`

Generated by: LCOV version 1.14