https://0bin.net/paste/Q5perGCU3+QMVnhz#fNpHXjX0me3Wa-UBItl4hTeK7wjBkl8JlFAmsbTlZVA http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2018-03-05-cross-curve-atomic-swaps/ Equivalent Secret Values Across Curves ------- A common component of scriptless script is a "discrete log hash preimage", in which the map `x -> xG` is used as a hash function, where G is a standard generator of some elliptic curve and `x` is a scalar in the ring Z/nZ isomorphic to . On its domain, this map is collision-resistant (because it is an injective function) and preimage-resistant for random inputs (this is the discrete logarithm assumption) and can therefore be used to hide secret random values. However, given two curves with respective generators G and H with |G|, |H| coprime, we often want to talk about xG and xH with "the same" x. But how can we make sense of this, given that the scalar ring for G has a different order than that of the scalar ring for H? Worse, even if these were sensible, given that there are no algebraically meaningful maps between the two rings, how can we prove this without revealing x? The answer to the first question is: rather than taking x as an element of Z/nZ for any n, treat it as an integer in the range [0, 2^k - 1], where 2^k is less than both |G| and |H|. Then the projection maps Z -> Z/|G|Z and Z -> Z/|H|Z give representations of x as elements of the scalar groups of G and H, which are invertible when restricted to the domain of x. This invertibility lets us talk about either scalar representation of x equivantely to x, and therefore equivalently to each other. In our applications x will be a secret value which therefore needs to be large enough to prevent brute-forcing; say, 128 bits. As our candidate curves (ed25519 and secp256k1) have group orders in excess of 250 bits, we have more than enough room to use this mechanism. To answer the second question, we first decompose the value x into bits b_i such such that sum_{i = 1}^n 2^i*b_i = x, where n is the bitlength of x. For each b_i, we choose Pedersen commitments G_i = b_i*G' + r_i*G and H_i = b_i*H' + s_i*H, where sum_i 2^i*r_i = 0 sum_i 2^i*s_i = 0 This implies sum_i 2^i G_i = x*G sum_i 2^i H_i = x*H For each G_i and H_i, we construct a ring signature proving that these are both Pedersen commitments of the same value, which is 0 or 1. We may further combine all of these ring signatures by sharing one commitment across them, as a Borromean Ring Signature [1]. We construct such a ring signature essentially by creating two separate ring signature over {G_i, G_i - G'} and {H_i, H_i - H'} respectively, but we share both commitments across the signatures. More specifically, if the bit is 0, the prover acts as follows. 1. Choose j_i in the scalar group of G and k_i in the scalar group of H, both uniformly at random. 2. Compute e_0 = H(G_i || H_i || j_i*G || k_i*H), where || denotes concatenation. 3. Compute a_{i,1} and b_{i,1} in the scalar groups of G and H, respectively, again uniformly at random. 4. Compute e_1 = H(G_i || H_i || a_{i_1}*G - e_0*G_i || b_{i,1}*H - e_0*H_i). 5. Compute a_{i,0} = j_1 + e_i*r_i and b_{i, 0} = k_i + e_1*s_i. 6. The final signature is then { e_0, a_{i,0}, a_{i,1}, b_{i,0}, b_{i,1} } If the bit is 0, the prover acts as follows. 1. Choose j_i in the scalar group of G and k_i in the scalar group of H, both uniformly at random. 2. Compute e_1 = H(G_i || H_i || j_i*G || k_i*H), where || denotes concatenation. 3. Compute a_{i,0} and b_{i,0} in the scalar groups of G and H, respectively, again uniformly at random. 4. Compute e_0 = H(G_i || H_i || a_{i_1}*G - e_0*(G_i - G') || b_{i,1}*H - e_0*(H_i - H')). 5. Compute a_{i,1} = j_1 + e_i*r_i and b_{i,1} = k_i + e_1*s_i. 6. The final signature is then { e_0, a_{i,0}, a_{i,1}, b_{i,0}, b_{i,1} } (Observe the difference between the two cases is that we exchanged each of (a_{i,0}, a_{i,1}), (b_{i,0}, b_{i,1}), (G_i, G_i - G'), (H_i, H_i - H') and (e_0, e_1). In all cases the verifier acts as follows, given commitments G_i and H_i, and a signature { e'_0, a_{i,0}, a_{i,1}, b_{i,0}, b_{i,1} }. 1. Compute e_1 = H(G_i || H_i || a_{i_1}*G - e_0*G_i || b_{i,1}*H - e_0*H_i). 2. Compute e_0 = H(G_i || H_i || a_{i_1}*G - e_0*(G_i - G') || b_{i,1}*H - e_0*(H_i - H')). 3. Verification passes if and only if e_0 = e'_0. [1] https://github.com/Blockstream/borromean_paper/blob/master/borromean_draft_0.01_9ade1e49.pdf