Page MenuHomePhabricator

[avalanche] Sort the stakes inside a proof

Authored by Fabien on Wed, Sep 8, 15:56.


Group Reviewers
Restricted Project
Maniphest Tasks
Restricted Maniphest Task
rABC278b300a0620: [avalanche] Sort the stakes inside a proof

This diff computes a stake id and use it to sort the stakes in the proof, so the proof id is deterministic for a set or stakes.

This prevents proofs from conflicting when the same set of UTXO is shuffled inside the proof.

I deliberately did not update the stake hash used for computing the signature so single stake utxos remain valid and I don't have to update all the tests.

Ref T1676.

Test Plan
ninja all check-all

Diff Detail

rABC Bitcoin ABC
Lint Not Applicable
Tests Not Applicable

Event Timeline

Fabien requested review of this revision.Wed, Sep 8, 15:56
PiRK added inline comments.
57 ↗(On Diff #29857)

This is not blocking, but wouldn't it be easier to understand the process of building the proof if this sort was at the beginning of ProofBuilder::build, just before getProofId is called?

Right now, this sorting which affect a class member and the order of the stakes in the serialized proof, is an undocumented side effect of what you would expect to be a simple getter.

57 ↗(On Diff #29857)

This was in fact how I did it initially, but this make it possible to return a wrong value when calling getProofId() which is brittle.
Another solution is do a sorted insert (ensure the stake container is sorted after each call to addUTXO()). This either means I need another type of container and convert it when doing the serialization (to keep the format compatible) or I sort after each UTXO addition. I wanted to avoid that last solution for performance reason but it's maybe not that bad, proof creation is not on a critical path.

Fabien planned changes to this revision.Thu, Sep 9, 09:49

Going to use a std::set of stakes to keep them sorted all the time. This is more complicated to implement (and test) but more robust in the end since it enforces consistency.

Using a set in the proof builder is a better solution but it breaks tests for duplicated inputs, since it's no longer possible to build them with the proof builder and so it requires a bit more test tooling. This is going to happen in a follow-up diff, for now I moved the TestProofBuilder structure to avalanche/test/util.h (will be expanded for duplicate inputs) and added a comment regarding the sorting function that needs to be removed from getProofId().

PiRK accepted this revision.EditedThu, Sep 9, 11:40

Sounds like a good plan. With a sorted container the state of the proof builder will be guaranteed to always be consistent.

This revision is now accepted and ready to land.Thu, Sep 9, 11:40
This revision was automatically updated to reflect the committed changes.