fix doc

[lovesh]

Signed-off-by: lovesh harchandani lovesh.bond@gmail.com

[HarryR]

Hi

Thanks for the patch :D

[HarryR]

I should note that this was one of the first files I wrote in the project, so it's not the best and probably has too many constraints than is necessary.

Later on I started using emplace_back for vectors, rather than push_back, as emplace_back does initialisation in-place (it reserves an element on the vector, and passes the arguments directly to the class constructor), which avoids copy constructors etc. Whereas push_back will make a temporary instance of it then copy.

Re:

            auto t = HashT(
                    in_pb, in_IVs[i],
                    {m_selectors[i].left(), m_selectors[i].right()},
                    FMT(this->annotation_prefix, ".hasher[%zu]", i));
            m_hashers.push_back(t);

vs

            m_hashers.emplace_back(in_pb, in_IVs[i],
                    {m_selectors[i].left(), m_selectors[i].right()},
                    FMT(this->annotation_prefix, ".hasher[%zu]", i));

[lovesh]

@HarryR Thanks. If its not too much to ask, can you please tell me if this merkle tree code has extra constraints. Btw, its a great repo and has been very helpful as I have been learning from your gadgets to use with bellman and bulletproofs.

One more comment regarding the one_of_n gadget. I think a simpler approach would be to construct a vector with each element being the difference of the set element at that index and the private input. Now one of the element of this new vector will be 0. Then you constrain the product of all elements of this new vector to be 0. This approach would have less constraints.

[HarryR]

I think this merkle tree code has too many constraints, the left/right selector was very naive.

So you have the selector bit, which you need to ensure is a bit. Then you have two possible values (both variables), and the selector bit chooses which one to use.

See: https://github.com/scipr-lab/libsnark/blob/master/libsnark/gadgetlib1/gadgets/hashes/digest_selector_gadget.tcc#L27

template<typename FieldT>
void digest_selector_gadget<FieldT>::generate_r1cs_constraints()
{
    for (size_t i = 0; i < digest_size; ++i)
    {
        /*
          input = is_right * right + (1-is_right) * left
          input - left = is_right(right - left)
        */
        this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(is_right, right.bits[i] - left.bits[i], input.bits[i] - left.bits[i]),
                                     FMT(this->annotation_prefix, " propagate_%zu", i));
    }
}

However, that only works with bits, so I can't use that constraint when the path is a field element rather than an array of bits. With the libsnark digest_selector_gadget it requires 1 constraint per bit of the digest, but with my implementation uses 6 constraints per path element - and I think it can be reduced further.

See: https://github.com/HarryR/ethsnarks/blob/master/src/gadgets/merkle_tree.cpp#L32

I think it could be simplified to:

a = is_right * right
b = 1 - is_right * left
c = a * right
d = b * left
e = c + d

Where e can be a linear combination

[HarryR]

Also, I really liked your article: https://medium.com/coinmonks/zero-knowledge-proofs-using-bulletproofs-4a8e2579fc82

I added a ticket for my ethsnarks-il project: https://github.com/Ethsnarks/ethsnarks-il/issues/1 for compatibility with bulletproofs.

The idea being that there's a common intermediate language, used by Pinocchio and XJSnark, kinda documented at: https://github.com/Ethsnarks/ethsnarks-il/tree/master/cxx

Which can target both SNARKs and Bulletproofs.

[lovesh]

@HarryR

However, that only works with bits, so I can't use that constraint when the path is a field element rather than an array of bits.

Do you mean the constraint only works if left and right are bits? If yes, i don't understand why not.

a = is_right right b = 1 - is_right left c = a right d = b left e = c + d

What is e constrainted to? If c was defined as a*left and d as b*right, then i see e=left*right.

[HarryR]

With the libsnark digest selector each digest is an array of bits ( see https://github.com/scipr-lab/libsnark/blob/master/libsnark/gadgetlib1/gadgets/hashes/digest_selector_gadget.tcc#L27 ) - so left and right are each an array of bits. So the per-bit constraint is simpler, but there is one constraint per bit.

for i in range(num_bits_in_digest):
    input[i] = (is_right * right[i]) + ((1-is_right) * left[i])

However, the multiplicative complexity of each constraint is two - it requires two constraints, unless you do something like the following.

is_right * (right.bits[i] - left.bits[i]) == (input.bits[i] - left.bits[i])

Hmm, it seems that this can be used for field elements as well as bits. I don't see why I originally did it the way I did, I should've just set the digest length to 1 and used the built-in digest classes from libsnark instead of writing my own.