XOR instead of Sloth? (with some digressions on Blake2s)

[porcuquine]

Replacing Sloth with XOR

This issue is to discuss the possibility of replacing XOR with Sloth and to outline considerations.

Background

Although we originally implemented encoding (during replication) using a tunable VDE, we have moved to using zero iterations for performance reasons (both inside and outside of circuits). This means that in practice we use a single group addition to encode using the key derived by the KDF.

Not only is this somewhat expensive (please paste numbers if you have them or when they become available), but we also incur the cost of converting from binary (Fr32) to field element Fr representation repeatedly during replication — simply in order to perform this addition.

XOR

If we could replace the add_assign with XOR, we could (seemingly) avoid this conversion and group arithmetic, since there would be no need for it. This would come at a cost in the circuits, since XOR will incur significantly more than the one constraint required to check encoding via addition.

On the other hand, if this actually worked as imagined, we could also potentially get rid of preprocessing altogether — since we would never need nodes to be encoded as Fr during replication.

That said, 'doing away with preprocessing' would also add work. It would change assumptions about how sectors are packed, how much data they hold, etc. Certainly as a first step, we could retain preprocessing and still gain the general benefit — if we can conclude that it actually would be a benefit.

Problem?

As it stands, we are guaranteed that the result of encoding can be converted to Fr. That will not be the case if move encoding to use XOR. Is that a problem?

Maybe it's not strictly a problem for merkle tree generation. We already plan to sometimes use blake2s for hashing there, and its output is not necessarily Fr32.

However, this raises issues we need to think through more carefully: since blake2s digest size is 256 bits, which is greater than E::Fr::CAPACITY it seems that we must be incurring an extra Fr allocation when we call compute_multipacking after hashing with blake2s in circuits.

Upon closer inspection, I see that we are discarding the extra two bits. @arielgabizon Can you confirm that it is 'safe' for us to do so? Why is this actually accurate if we don't do the same outside of circuits? Is it possible that our current blake2s circuit implementation will fail when a hash overflows? If so, can we safely solve that by truncating to Fr32 outside the circuits as well?

Assuming the above is fine, can we truncate leaf values to Fr in the same way, when creating merkle proofs in circuits? I'm not confident it's okay to do this. This would appear to make it easy to create hash collisions — which would interfere with reliability of commD and piece inclusion proofs.

If we determine this is safe to do within merkle paths (i.e. to truncate hash output as we currently do!) but not for leaves, the cost of the extra Fr per allocated leaf (private input) might be acceptable.

---

As an aside: it turns out that we are paying the cost of hashing 64 extra bits (I logged the size of the preimage: 576 bits) in order to include the height in blake2s merkle hashes. We can obviously cut this down significantly [TODO: create an issue for this.] This would cut down on constraints and speed up hashing.

I do not believe we need to include the height at all — so in theory we could eliminate the whole 64 bits (and this would be the simplest way to address this issue as well). Can we do this? Should we do this?

---

Back to XOR: once we resolve the questions of above, the question remains whether this is actually worth doing. It's not clear to me that it is because it will add many constraints per challenge.

This issue is not meant to give answers — just to raise (some of) the questions I think we need to think through — both in relation to XOR and also to our use of Blake2s.

I think I may be misunderstanding some details, so please correct me if so. In order to actually make the XOR change, I think we need to first think through the potential problems listed above and either reject them or choose ways around. If we can do that and also get better information about the benefits and costs then we can either accept or reject the change. Some of you may have some of this information already, so please add if so.

@dignifiedquire @nicola @arielgabizon @schomatis

[dignifiedquire]

Upon closer inspection, I see that we are discarding the extra two bits
[..]
Why is this actually accurate if we don't do the same outside of circuits?

we do this discarding outside of the circuit in the conversions as well: https://github.com/filecoin-project/rust-fil-proofs/blob/master/storage-proofs/src/hasher/blake2s.rs#L195

[nicola]

My bet is that doing a bit-wise XOR will be equivalent in constraints to doing the packing.

[porcuquine]

@dignifiedquire Got it, thanks. I was looking in the wrong place. I guess it's fine to truncate the hash output.

Does anyone disagree that we cannot truncate the input, though, which means (I think) that the leaves would have to be hashed specially (larger input) and would either require an extra Fr input or else we would have to try to efficiently pack N leaves into N+m Fr?

[porcuquine]

@nicola What packing are you talking about? Which constraints do you think we will save by using XOR? (I have a guess below.)

It seems to me that currently, the encoding check requires:

• One constraint to prove the data encoding.
• One constraint to prove that the encoding is equal to the replica. Replica, data, and encoding are all Fr.

It seems to me that if we use XOR, the encoding will require:

1. One unpacking to get bits from the data, which must be packed into >1 Fr.
2. Skip packing the bits from the KDF back into FR. (I think this is the savings you mean).
3. One 256-bit XOR (how many constraints is that? 256, 512?) proving the encoding of the data.
4. But we still need 256 constraints to assert equality of the encoded bits and the derived key (from KDF).

If that is correct (maybe it's not), it seems to me that we trade (1.) one packing (of the key) for (2.) one packing (of the data before XOR) — for no net change. Then we add (3., 4.) some multiple of 256 bits for the XOR and equality constraints.

So the way I'm seeing it, this would incur a definite increase in constraints.

[porcuquine]

Also note that if we do use longer (untruncated) leaves, then our merkle paths become non-uniform. That is, the first element will also need to be longer; and we will need to special-case the first swap-and-hash in the PoR circuit (to handle two Fr rather than one).

[nicola]

the output of the hash function will be bits, so you could use them directly, no need to do packing (if we do binary XOR), hence both the packing and the XOR will be about the same number of constraints.

[porcuquine]

So you are talking about 2. in my list above (KDF), right? That's what I thought.

Do you believe we would be able to avoid the other three sets of constraints? If so, how? If not, does this not seem expensive to you?

[nicola]

I did not spend much time into this, your analysis seems correct.
I did miss the first one and the last one, which are pretty annoying.

[porcuquine]

@arielgabizon My comment above contains the analysis of constraint costs if we move to XOR for encoding.

Can you confirm or reject the conclusion that this implies that making this change would increase our constraints and help quantify the increase (if there is one)?

[arielgabizon]

@porcuquine : Regarding dropping two bits in the multi-packing method. It's fine assuming blake2s is collision resistant also when truncated to 254 first bits.
(I confirmed that's what's happening as Fr::CAPACITY is indeed defined to 254 https://github.com/zkcrypto/pairing/blob/183a64b08e9dc7067f78624ec161371f1829623e/src/bls12_381/fr.rs#L950)

Those first 254 bits are then mapped uniquely to an Fr element,
because r=52435875175126190479447740508185965837690552500527637822603658699938581184513
and so log_2(r)>254

Zcash sapling assumes blake2s is collision resistant even when truncated to 251 bits (5.4.1.5 in Zcash spec) so I guess that's fine

[nicola]

I can consider this issue closed for now. The percentage of computation spent in this EC operation (~2%) and it's not a major surface of attack today.

[arielgabizon]

@arielgabizon My comment above contains the analysis of constraint costs if we move to XOR for encoding.

Can you confirm or reject the conclusion that this implies that making this change would increase our constraints and help quantify the increase (if there is one)?

Yes seems pretty clear moving to XOR would add 256 constraints

[nicola]

Closing this issue since, this is not a direction we are considering pursuing at the moment.