1  pragma circom 2.0.0;
  2  
  3  include "single_cell.circom";
  4  include "poseidon2_hash.circom";
  5  include "extract_bits.circom";
  6  include "log2.circom";
  7  include "misc.circom";
  8  
  9  //------------------------------------------------------------------------------
 10  
 11  //
 12  // calculate the linear index of the k-th cell we want to sample.
 13  // this version return the binary decomposition of the index
 14  // (we need that for the Merkle proof anyway, it's cheaper this way)
 15  //
 16  // the formula for this is:
 17  //
 18  //     idx = H( entropy | slotRoot | counter ) `mod` nCells
 19  //
 20  // NOTE: we assume `nCells` is a power of two.
 21  //
 22  
 23  template CalculateCellIndexBits( maxLog2N ) {
 24  
 25    signal input  entropy;
 26    signal input  slotRoot;
 27    signal input  counter;
 28    signal input  cellIndexBitMask[maxLog2N];      // bit mask for the cell index range
 29  
 30    signal output indexBits[maxLog2N];
 31  
 32    // calculate the hash
 33    component pos = Poseidon2_hash_rate2( 3 );     // input is 3 field elements
 34    signal hash;
 35    pos.inp[0] <== entropy;
 36    pos.inp[1] <== slotRoot;
 37    pos.inp[2] <== counter;
 38    pos.out    ==> hash;
 39  
 40    // extract the lowest `maxLog2N = 32` bits
 41    component md = ExtractLowerBits(maxLog2N);
 42    md.inp <== hash;
 43  
 44    for(var i=0; i<maxLog2N; i++ ) {
 45      indexBits[i] <== cellIndexBitMask[i] * md.out[i];
 46    }
 47  
 48  }
 49  
 50  //------------------------------------------------------------------------------
 51  
 52  //
 53  // sample `nSamples` number of cells; calculate their hashes;
 54  // reconstruct the slot root using the Merkle paths, then
 55  // the dataset root too, and checks if everything is consistent.
 56  //
 57  
 58  template SampleAndProve( maxDepth, maxLog2NSlots, blockTreeDepth, nFieldElemsPerCell, nSamples ) {
 59  
 60    // var maxDepth       = 32;    // maximum depth of the slot Merkle tree (so max `2^maxDepth` cells in a slot)
 61    // var maxLog2NSlots  = 8;     // maximum depth of the dataset-level Merkle tree (so max 2^8 slots per dataset)
 62    // var blockTreeDepth = 5;     // depth of the "network block tree" (= log2(64k / 2k))
 63  
 64    signal input entropy;                                  // public input
 65    signal input dataSetRoot;                              // public input
 66    signal input slotIndex;                                // must be public, otherwise we could prove a different slot
 67  
 68    signal input slotRoot;                                 // can be private input
 69    signal input nCellsPerSlot;                            // can be private input (Merkle tree is safe)
 70    signal input nSlotsPerDataSet;                         // can be private input (Merkle tree is safe)
 71  
 72    signal input slotProof[maxLog2NSlots];                 // path from the slot root the the dataset root (private input)
 73  
 74    signal input cellData[nSamples][nFieldElemsPerCell];   // private input
 75    signal input merklePaths[nSamples][maxDepth];          // private input
 76  
 77    // -------------------------------------------------------
 78    // sanity check for singleton trees
 79    // we don't have to do anything here, it's fixed in `merkle.circom`
 80  
 81    // component eqsing = IsEqual();
 82    // eqsing.A <== nCellsPerSlot;
 83    // eqsing.B <== (1<<blockTreeDepth);     // normally 32
 84    // signal slotTreeIsSingleton <== eqsing.out;
 85  
 86  log("block tree (bottom) is singleton = ", blockTreeDepth == 0 );
 87  log("slot tree (middle)  is singleton = ", nCellsPerSlot == (1<<blockTreeDepth) );
 88  log("dataset tree (top)  is singleton = ", nSlotsPerDataSet == 1 );
 89  
 90    // -------------------------------------------------------
 91    //
 92    // first we prove the inclusion of the slot root in the dataset-level
 93    // (small) Merkle tree
 94  
 95    component tbtp = ToBits( maxLog2NSlots );
 96    component clog = CeilingLog2( maxLog2NSlots );
 97    component mtop = RootFromMerklePath( maxLog2NSlots );
 98  
 99    tbtp.inp        <== slotIndex;
100    clog.inp        <== nSlotsPerDataSet;
101    mtop.leaf       <== slotRoot;
102    mtop.pathBits   <== tbtp.out;
103    mtop.lastBits   <== clog.bits;
104    mtop.maskBits   <== clog.mask;
105    mtop.merklePath <== slotProof;
106  
107  log("top root check = ", mtop.recRoot == dataSetRoot);
108  
109    mtop.recRoot === dataSetRoot;
110  
111    // -------------------------------------------------------
112    //
113    // then we prove the individual sampled cells
114  
115    component lg = Log2_CircomWitnessCalc_Hack(maxDepth);           // we allow at most 2^32 cells per slot
116    lg.inp <== nCellsPerSlot;
117  
118    // NOTE: in general we need for the Merkle prover the binary decomposition
119    // of `nLeaves - 1`. But currently this is in fact a power of two, so we
120    // can reuse the binary mask for this. Later we may change this?
121    //
122    signal lastBits[maxDepth];
123    for(var i=0; i<maxDepth; i++) { lastBits[i] <== lg.mask[i]; }
124  
125    component calci[nSamples];
126    component prove[nSamples];
127  
128    for(var cnt=0; cnt<nSamples; cnt++) {
129  
130      calci[cnt] = CalculateCellIndexBits( maxDepth );
131      prove[cnt] = ProveSingleCell( nFieldElemsPerCell, blockTreeDepth, maxDepth );
132  
133      // calci[cnt].cellIndexBitMask <== lg.mask;
134      for(var i=0; i<maxDepth; i++) { calci[cnt].cellIndexBitMask[i] <== lg.mask[i]; }
135  
136      calci[cnt].entropy          <== entropy;
137      calci[cnt].slotRoot         <== slotRoot;
138      calci[cnt].counter          <== cnt + 1;
139      calci[cnt].indexBits        ==> prove[cnt].indexBits;
140  
141      prove[cnt].slotRoot     <== slotRoot;
142      prove[cnt].lastBits     <== lastBits;
143      prove[cnt].maskBits     <== lg.mask;
144      prove[cnt].data         <== cellData[cnt];
145      prove[cnt].merklePath   <== merklePaths[cnt];
146  
147    }
148  }
149  
150  //------------------------------------------------------------------------------
151