1  
 2  import std/sequtils
 3  
 4  import goldilocks_hash/types
 5  import goldilocks_hash/poseidon2/compress
 6  import goldilocks_hash/poseidon2/merkle
 7  import goldilocks_hash/poseidon2/sponge
 8  
 9  import ../../types
10  import ../../types/goldilocks
11  
12  #-------------------------------------------------------------------------------
13  
14  func compressWithkey*(key: int, x, y: Digest): Digest = compress(x,y, key=uint64(key))
15  
16  func merkleDigestPoseidon2*(xs: openArray[Digest]): Digest = Merkle.digest(xs)
17  
18  # TODO: move these somewhere else
19  func digestFeltsPoseidon2*(xs: openArray[F]   ): Digest = digestFeltsC( rate=8, xs )
20  func digestBytesPoseidon2*(xs: openArray[byte]): Digest = digestBytesC( rate=8, xs )
21  
22  #-------------------------------------------------------------------------------
23  
24  const KeyNone              : uint64 = 0x00
25  const KeyBottomLayer       : uint64 = 0x01
26  const KeyOdd               : uint64 = 0x02
27  const KeyOddAndBottomLayer : uint64 = 0x03
28  
29  func merkleTreeWorker(xs: openArray[Digest], isBottomLayer: static bool) : seq[seq[Digest]] =
30    let a = low(xs)
31    let b = high(xs)
32    let m = b-a+1
33  
34    when not isBottomLayer:
35      if m==1:
36        return @[ xs.toSeq() ]
37  
38    let halfn  : int  = m div 2
39    let n      : int  = 2*halfn
40    let isOdd : bool = (n != m)
41  
42    var ys : seq[Digest]
43    if not isOdd:
44      ys = newSeq[Digest](halfn)
45    else:
46      ys = newSeq[Digest](halfn+1)
47  
48    for i in 0..<halfn:
49      const key = when isBottomLayer: KeyBottomLayer else: KeyNone
50      ys[i] = compress( xs[a+2*i], xs[a+2*i+1], key = key )
51    if isOdd:
52      const key = when isBottomLayer: KeyOddAndBottomLayer else: KeyOdd
53      ys[halfn] = compress( xs[n], zeroDigest, key = key )
54  
55    var ls : seq[seq[Digest]] 
56    ls = @[ xs.toSeq() ] 
57    ls = ls & merkleTreeWorker(ys, isBottomLayer = false)
58    return ls
59  
60  #-------------------------------------------------------------------------------
61  
62  func merkleTreeGoldilocksPoseidon2*(xs: openArray[Digest]) : MerkleTree[Digest] =
63    return MerkleTree[Digest](layers: merkleTreeWorker(xs, isBottomLayer = true))
64  
65  #-------------------------------------------------------------------------------