It depends on the protocol requirements. If you have 256-bit data elements to reconcile, and want 100% guarantee that reconciliation will succeed with 1 round-t

It depends on the protocol requirements. If you have 256-bit data elements to reconcile, and want 100% guarantee that reconciliation will succeed with 1 round-trip, then you'll indeed need to use sketches with 256-bit elements. However, if you're fine with more roundtrips, or probabilistic reconciliation, you can typically use far smaller elements. Have the parties agree on a random salt, and construct sketches of short salted hashes of your data elements (where the size of these hashes depends on your tolerance for failure due to collisions in your sets). Run the reconciliation algorithm to figure out the difference, and then send/request the real elements based on their short hashes.