Open sethforprivacy opened 2 years ago
kayabaNerve
commented
1 year ago Two questions as I work on my review.
1) How long should it take to recreate the curve with the above specified params? Few hours or a few days?
2) Did you have the x0/x1/y0/y1 values for each curve I can run verify.sage with? I believe this should be the generator, where convention would either be some hash or the lowest valid set of coordinates. I'm sure I can grab one myself, just figured you may have it handy.
tevador
commented
1 year ago How long should it take to recreate the curve with the above specified params? Few hours or a few days?
I'm not sure what exactly you mean, but you can clone my repo:
https://github.com/tevador/pasta
and run
sage amicable.sage --sequential --ignoretwist --anyeqn --montgomery 255 112In about 15 minutes, it will find a total of 3 cycles:
y^2 = x^3 + 97 with p=27488187*2^230+1. This cycle has both gcd(p-1,5)=1 and gcd(q-1,5)=1. Ep has twist security of 102.3 bits. There are no isogenies.y^2 = x^3 + 278 with p=6212163*2^232+1. This is the cycle mentioned above. It has gcd(p-1,5)=1 but gcd(q-1,5)≠1. Ep has twist security 108.8 and both curves have isogenies.y^2 = x^3 + 74 with p=299340363*2^226+1. This cycle has both gcd(p-1,5)=1 and gcd(q-1,5)=1. Ep has twist security of only 50.4 bits. Both curves have isogenies.Since we require twist security on Ep, we can decide between cycle 1 and 2 depending on the importance of having gcd(q-1,5)=1 or having isogenies.
Did you have the x0/x1/y0/y1 values for each curve I can run verify.sage with? I believe this should be the generator
You can choose any point on the curve for the generator, but the convention is to find the point with the smallest value of x. I haven't tried that yet.
kayabaNerve
commented
1 year ago Ah. Thanks for the link to your own repo. I missed that and was running on zcash's with your prior commented discovery command, which I now see is distinct.
Also yes, I was asking for the answer of "15 minutes".
tevador
commented
1 year ago Yeah, the --anyeqn --montgomery commands are specific to my repo. The zcash script will ignore these options and likely won't find anything.
tevador
commented
1 year ago
y^2 = x^3 + 97
Btw, this equation has a non-modular solution of x=18, y=77, so if we use this cycle, I'd recommend using this as the base point because then we could have the same base point on both curves.
tevador
commented
1 year ago Since we require twist security on Ep, we can decide between cycle 1 and 2 depending on the importance of having
gcd(q-1,5)=1or having isogenies.
Isogenies are needed only for efficient hashing onto the curve. I don't think it is needed for our use case (Seraphis has a different key image construction that doesn't invove hashing). Can someone confirm that hash-to-point is not needed for the Merkle tree proof? Note that without isogenies, hashing onto the curve is still possible, just slower.
It would be nice to be able to use Reinforced Concrete for the Merkle tree proof. Can someone confirm we need both gcd(p-1,5)=1 and gcd(q-1,5)=1 for this?
If the above hypotheses are confirmed, I would suggest using the first cycle with the equation y^2 = x^3 + 97.
kayabaNerve
commented
1 year ago From my immediate understanding, algebraic hashes are needed, the only hash to points needed are as parameters (similar to H/Bulletproofs).
ReinforcedConcrete's Bricks function is written a degree 5 polynomial where gcd(p - 1, 5) = 1. They do not describe that as being variable nor say that security analysis holds when it's distinct. Ideally, we only use one hash, yet it may theoretically be possible to use RC on one curve and Poseidon on another?
I'll double check on the usage of hash to point. What's the 2-adicities of the first one?
tevador
commented
1 year ago the only hash to points needed are as parameters
We don't need a fast hash for these as it's a one-off thing.
Ideally, we only use one hash, yet it may theoretically be possible to use RC on one curve and Poseidon on another?
My main question was if both fields need the hash. The Merkle tree only contains points from one curve (the "application" curve where the output keys live).
RC claims to be 15x faster than Poseidon, so it would presumably be beneficial if we can use it.
What's the 2-adicities of the first one?
p = 0x68dbeec000000000000000000000000000000000000000000000000000000001 (bitlength 255, weight 18, 2-adicity 230)
q = 0x68dbeec00000000000000000000000011bc80000000000000000000000000001 (bitlength 255, weight 26, 2-adicity 115)We don't need a fast hash for these as it's a one-off thing.
Agreed.
My main question was if both fields need the hash. The Merkle tree only contains points from one curve (the "application" curve where the output keys live).
Curve trees has both curves perform hashes. They both need a hash. While we could likely do RC on one, and Poseidon on the other, we obviously would be best of simply having a curve which RC works for both. That'd be 1 or 3.
tevador
commented
1 year ago We have a classic case of "pick 2 options out of 3".
Cycle 1 has: twist security, gcd(q-1,5)=1 Cycle 2 has: twist security, isogenies Cycle 3 has: gcd(q-1,5)=1, isogenies
I think isogenies are the least useful option for us, so cycle 1 should be the best choice. If you can confirm that we don't need a fast hash-to-curve function, I will start implementing cycle 1.
kayabaNerve
commented
1 year ago We can eliminate curve 2. I hope to provide my opinion on hash to curve, and put forth my own comment on security, within two days.
DarkWingMcQuack
commented
1 year ago Is it possible to bruteforce a "perfect" curve? If so, i have lots of computing power at hand which i could use to search for such a curve cycle.
sethforprivacy
commented
1 year ago I won't pretend I understand pretty much anything being discussed in here recently, but just wanted to say thank you to @kayabaNerve and @tevador for diving in and trying to make some headway here!
IMO a move to a complete membership proof instead of ring signatures would be the single most needed and most impactful move for the Monero community to make, enabling Monero to both retain it's share of usage among privacy coins and to ensure that all users are protected as much as possible, even against targeted attacks.
As we move into a more and more adversarial environment, the relatively problematic ring signature approach will lead to more and more issues, so I'm happy to see this gaining traction.
tevador
commented
1 year ago Is it possible to bruteforce a "perfect" curve? If so, i have lots of computing power at hand which i could use to search for such a curve cycle.
I updated my script to do an exhaustive search and found two additional cycles with p = c * 2^x + 1 where c < 2^32. Both of these cycles have gcd(q-1,5)=1 and isogenies, but their twist security is poor, so they are equivalent to cycle 3 above.
"Cycle 4"
p = 0x71b50f0300000000000000000000000000000000000000000000000000000001 (bitlength 255, weight 16, 2-adicity 224)
q = 0x71b50f0300000000000000000000000127830000000000000000000000000001 (bitlength 255, weight 24, 2-adicity 112)
Ep/Fp : y^2 = x^3 + 284
Eq/Fq : y^2 = x^3 + 284
gcd(p-1, α) = 1 for α ∊ {5, 7, 11, 13, 17}
gcd(q-1, α) = 1 for α ∊ {5, 11, 13, 17}
Ep security = 126.4, embedding degree = (q-1)/32
Eq security = 126.4, embedding degree = (p-1)/2
Ep twist security = 56.7
Eq twist security = 33.2"Cycle 5"
p = 0x7410694b00000000000000000000000000000000000000000000000000000001 (bitlength 255, weight 14, 2-adicity 224)
q = 0x7410694afffffffffffffffffffffffed5710000000000000000000000000001 (bitlength 255, weight 117, 2-adicity 112)
Ep/Fp : y^2 = x^3 + 41
Eq/Fq : y^2 = x^3 + 41
gcd(p-1, α) = 1 for α ∊ {5, 7, 11, 13, 17}
gcd(q-1, α) = 1 for α ∊ {5, 11, 13, 17}
Ep security = 126.5, embedding degree = (q-1)/2
Eq security = 126.5, embedding degree = (p-1)/146
Ep twist security = 62.8
Eq twist security = 55.8While we could technically continue the search for c >= 2^32, there would be performance impact on some systems (slower modular reduction).
I'm still running a search for 254-bit primes (all the cycles mentioned so far are 255-bit), but it's likely that there are no "perfect" curves and we will have to make compromises (either dropping some requirements or accepting a slower curve).
tevador
commented
1 year ago FYI, I searched all primes of 240-254 bits that would provide a general speed-up and found no other useful cycles.
tevador
commented
1 year ago https://github.com/monero-project/research-lab/issues/100#issuecomment-1423154798
Fund discovery of a curve cycle for Ed25519
We can hope there will eventually be a Ed25519 cycle. While this sticks us with Ed25519, which annoyingly has torsion, it is possible. I'd argue this should be done as soon as possible if we're unwilling to move. That way, we can know if a curve cycle is available and we aren't either dooming ourselves or necessitating yet another migration in the future.
It's not possible to find a cycle.
While there cannot be a direct cycle with Ed25519, there can be an indirect cycle that requires going through an intermediate curve:
---->----
/ \
Ed25519 -> Er -> Eq Ep
\ /
----<----Here Er, Ep and Eq are three new curves such that:
Er is defined over GF(p) and contains a subgroup with order 2^255-19 (its scalar field has the same size as the Ed25519 base field).Eq is defined over GF(q) and has order p (i.e. its scalar field has the same size as the Er base field)Ep is defined over GF(p) and has order q (i.e. it forms a cycle with Eq).These curves exist:
Curve Er: y^2 = x^3 + 4 mod p with order h*(2^255-19)
Curve Ep: y^2 = x^3 + 14 mod p with order q
Curve Eq: y^2 = x^3 + 14 mod q with order p
h = 1407
p = 0x2bf8000000000000000000000000000003053b33f6622b8802b5c85a5af1dadc389
q = 0x2bf80000000000000000000000000000060a7667ecc45710056b90b4b5e3b5bef81This could be a backup solution in case we decided to stick with Ed25519 for whatever reason. The three new curves would be used solely in the membership proof, which could be implemented with Curve Trees using the cycle Ep/Eq with an additional point blinding proof over the curve Er.
While this would be much more efficient than the Bulletproofs solution, there are major drawbacks compared to a native cycle:
UkoeHB
commented
1 year ago @tevador is there a reason you need three curves? Why not just go directly from Ed25519 to Ep?
tevador
commented
1 year ago Going from Ed25519 directly to Ep would imply that q = 2^255-19, so there would have to be a CM curve over GF(2^255-19) such that its order is a prime p.
CM curves over GF(q) only have 6 possible orders:
q + 1 + T
q + 1 - T
q + 1 + (T+3*V)/2
q + 1 + (T-3*V)/2
q + 1 - (T+3*V)/2
q + 1 - (T-3*V)/2where 4*q = T^2 + 3*V^2
For q = 2^255-19 we have
T = 384483085883472032291258361162322087063
V = 167089731525863132650062706797393049103and the 6 possible orders are:
57896044618658097711785492504343953926250509246936809987437533642794242732887
57896044618658097711785492504343953927019475418703754052020050365118886907013
57896044618658097711785492504343953926576599278473223336899327124341636289827
57896044618658097711785492504343953927077868473050812734849515244733815437136
57896044618658097711785492504343953926693385387167340702558256883571493350073
57896044618658097711785492504343953926192116192589751304608068763179314202764None of these is a prime number.
This proves that you cannot have a cycle of CM curves that involves the field GF(2^255-19).
The workaround is to insert a third curve that has a small cofactor h and then search for a prime p such that one if its 6 possible orders is h*(2^255-19) and another one is a prime q. The smallest p I found is with h = 1407.
narodnik
commented
1 year ago Hey guys, I haven't been following the thread but really excited to see this research going forwards!!!
I've been investigating another thread which I was planning to present once more further along, but happy to share details here to find collaborators. If I finish in time, then I'll present it at Monerotopia and happy to discuss more with devs.
Basically with curve trees, the main slowdown is the need for a fast EC inner product proof. I've been looking at a paper by Liam Eagan (who made bulletproofs++ as well) on using the Weil reciprocity trick.
Functions can be represented by divisors (equivalent up to a constant) which tracks the zeros and poles. Weil reciprocity states that $f(\textrm{div}(g)) = g(\textrm{div}(f))$, and we can use this to make a compact proof that a function interpolates some points. Then we can build up a statement about the structure of a point from these proofs. For now the first version will use normal double and add (actually there's 3 states per digit, not 2), but it can be sped up further with addition chains (needs further research).
The code below just constructs the function for a divisor. Here are some additional notes.
# Initialize an elliptic curve
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
r = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Fp = GF(p) # Base Field
Fr = GF(r) # Scalar Field
A = 0
B = 7
E = EllipticCurve(GF(p), [A,B])
assert(E.cardinality() == r)
K.<x> = PolynomialRing(Fp, implementation="generic")
L.<y> = PolynomialRing(K, implementation="generic")
eqn = y^2 - x^3 - A * x - B
# Returns line passing through points, works for all points and returns 1 for O + O = O
def line(A, B):
if A == 0 and B == 0:
return 1
else:
[a, b, c] = Matrix([A, B, -(A+B)]).transpose().kernel().basis()[0]
return a*x + b*y + c
def dlog(D):
# Derivative via partials
Dx = D.differentiate(x)
Dy = D.differentiate(y)
Dz = Dx + Dy * ((3*x^2 + A) / (2*y))
assert D != 0
return Dz/D
P0 = E.random_element()
P1 = E.random_element()
P2 = E.random_element()
Q = -int(Fr(5)^-1) * (P0 + 2*P1 + 3*P2)
assert P0 + 2*P1 + 3*P2 + 5*Q == 0
def div_add(div_f, div_g):
div = div_f.copy()
for P, n in div_g.items():
if P in div:
div[P] += n
else:
div[P] = n
div = dict((P, n) for P, n in div.items() if n != 0)
return div
def div_invert(div):
return dict((P, -n) for P, n in div.items())
def div_sub(div_f, div_g):
inv_div_g = div_invert(div_g)
return div_add(div_f, inv_div_g)
# 2[P₂] + [-2P₂] - 3[∞]
f1 = line(P2, P2)
D1 = {"P2": 2, "-2P2": 1, "∞": -3}
# 2[P₁] + [-2P₁] - 3[∞]
f2 = line(P1, P1)
D2 = {"P1": 2, "-2P1": 1, "∞": -3}
# [P₂] + [-P₂] - 2[∞]
f3 = line(P2, -P2)
D3 = {"P2": 1, "-P2": 1, "∞": -2}
# [P₀] + [-P₀] - 2[∞]
f4 = line(P0, -P0)
D4 = {"P0": 1, "-P0": 1, "∞": -2}
# (2[P₂] + [-2P₂] - 3[∞]
# + 2[P₁] + [-2P₁] - 3[∞]
# + [P₂] + [-P₂] - 2[∞]
# + [P₀] + [-P₀] - 2[∞])
# =
# [P₀] + 2[P₁] + 3[P₂] + [-P₀] + [-2P₁] + [-2P₂] + [-P₂] - 10[∞]
f5 = f1*f2*f3*f4
D5 = div_add(div_add(D1, D2), div_add(D3, D4))
assert D5 == {
"P0": 1,
"P1": 2,
"P2": 3,
"-P0": 1,
"-2P1": 1,
"-2P2": 1,
"-P2": 1,
"∞": -10
}
# [-2P₂] + [-2P₁] + [2(P₁ + P₂)] - 3[∞]
f6 = line(-2*P2, -2*P1)
D6 = {"-2P2": 1, "-2P1": 1, "2P1 + 2P2": 1, "∞": -3}
# [-P₂] + [-P₀] + [P₀ + P₂] - 3[∞]
f7 = line(-P2, -P0)
D7 = {"-P2": 1, "-P0": 1, "P0 + P2": 1, "∞": -3}
# ([P₀] + 2[P₁] + 3[P₂] + [-P₀] + [-2P₁] + [-2P₂] + [-P₂] - 10[∞]
# - [-2P₂] - [-2P₁] - [2(P₁ + P₂)] + 3[∞]
# - [-P₂] - [-P₀] - [P₀ + P₂] + 3[∞])
# =
# [P₀] + 2[P₁] + 3[P₂] - [2(P₁ + P₂)] - [P₀ + P₂] - 4[∞]
f8 = f5/(f6*f7)
D8 = div_sub(D5, div_add(D6, D7))
assert D8 == {
"P0": 1,
"P1": 2,
"P2": 3,
"2P1 + 2P2": -1,
"P0 + P2": -1,
"∞": -4
}
# [P₀ + P₂] + [2(P₁ + P₂)] + [-(P₀ + 2P₁ + 3P₂)] - 3[∞]
f9 = line(P0 + P2, 2*(P1 + P2))
D9 = {"P0 + P2": 1, "2P1 + 2P2": 1, "5Q": 1, "∞": -3}
# ([P₀] + 2[P₁] + 3[P₂] - [2(P₁ + P₂)] - [P₀ + P₂] - 4[∞]
# + [P₀ + P₂] + [2(P₁ + P₂)] + [-(P₀ + 2P₁ + 3P₂)] - 3[∞])
# =
# [P₀] + 2[P₁] + 3[P₂] + [-(P₀ + 2P₁ + 3P₂)] - 7[∞]
# = [P₀] + 2[P₁] + 3[P₂] + [5Q] - 7[∞]
f10 = f8*f9
D10 = div_add(D8, D9)
assert D10 == {
"P0": 1,
"P1": 2,
"P2": 3,
"5Q": 1,
"∞": -7
}
# Now construct 5[Q]
# 2[Q] + [-2Q] - 3[∞]
f11 = line(Q, Q)
D11 = {"Q": 2, "-2Q": 1, "∞": -3}
# [-2Q] + [2Q] - 2[∞]
f12 = line(-2*Q, 2*Q)
D12 = {"-2Q": 1, "2Q": 1, "∞": -2}
# (2[Q] + [-2Q] - 3[∞]) - ([-2Q] + [2Q] - 2[∞])
# ==
# 2[Q] - [2Q] - [∞]
f13 = f11/f12
D13 = div_sub(D11, D12)
assert D13 == {
"Q": 2,
"2Q": -1,
"∞": -1
}
# multiply by 3
# 6[Q] - 3[2Q] - 3[∞]
f14 = f13*f13*f13
D14 = div_add(div_add(D13, D13), D13)
assert D14 == {
"Q": 6,
"2Q": -3,
"∞": -3
}
# 2[2Q] + [-4Q] - 3[∞]
f15 = line(2*Q, 2*Q)
D15 = {"2Q": 2, "-4Q": 1, "∞": -3}
# (6[Q] - 3[2Q] - 3[∞]) + (2[2Q] + [-4Q] - 3[∞])
# ==
# 6[Q] - [2Q] + [-4Q] - 6[∞]
f16 = f14*f15
D16 = div_add(D14, D15)
assert D16 == {
"Q": 6,
"2Q": -1,
"-4Q": 1,
"∞": -6
}
# [2Q] + [-2Q] - 2[∞]
f17 = line(2*Q, -2*Q)
D17 = {"2Q": 1, "-2Q": 1, "∞": -2}
# (6[Q] - [2Q] + [-4Q] - 6[∞]) + ([2Q] + [-2Q] - 2[∞])
# ==
# 6[Q] + [-2Q] + [-4Q] - 8[∞]
f18 = f16*f17
D18 = div_add(D16, D17)
assert D18 == {
"Q": 6,
"-2Q": 1,
"-4Q": 1,
"∞": -8
}
# [-2Q] + [-4Q] + [6Q] - 3[∞]
f19 = line(-2*Q, -4*Q)
D19 = {"-2Q": 1, "-4Q": 1, "6Q": 1, "∞": -3}
# (6[Q] + [-2Q] + [-4Q] - 8[∞]) - ([-2Q] + [-4Q] + [6Q] - 3[∞])
# ==
# 6[Q] - [6Q] - 5[∞]
f20 = f18/f19
D20 = div_sub(D18, D19)
assert D20 == {
"Q": 6,
"6Q": -1,
"∞": -5
}
# [6Q] + [-6Q] - 2[∞]
f21 = line(6*Q, -6*Q)
D21 = {"6Q": 1, "-6Q": 1, "∞": -2}
# (6[Q] - [6Q] - 5[∞]) + ([6Q] + [-6Q] - 2[∞])
# ==
# 6[Q] + [-6Q] - 7[∞]
f22 = f20*f21
D22 = div_add(D20, D21)
assert D22 == {"Q": 6, "-6Q": 1, "∞": -7}
# [Q] + [-6Q] + [5Q] - 3[∞]
f23 = line(Q, -6*Q)
D23 = {"Q": 1, "-6Q": 1, "5Q": 1, "∞": -3}
# (6[Q] + [-6Q] - 7[∞]) - ([Q] + [-6Q] + [5Q] - 3[∞])
# ==
# 5[Q] - [5Q] - 4[∞]
f24 = f22/f23
D24 = div_sub(D22, D23)
assert D24 == {"Q": 5, "5Q": -1, "∞": -4}
# Now combine the result
f = f10*f24
D = div_add(D10, D24)
assert D == {
"P0": 1,
"P1": 2,
"P2": 3,
"Q": 5,
"∞": -11
}
f_numer = f.numerator().mod(eqn)
f_denom = f.denominator().mod(eqn)
# ZeroDivisionError
#DLog = dlog(f_numer)
assert f(x=P0[0], y=P0[1]) == 0
assert f(x=P1[0], y=P1[1]) == 0
assert f(x=P2[0], y=P2[1]) == 0
# Need to modify f because this is 0/0
#assert f(x=Q[0], y=Q[1]) == 0
Please note Zcash transactions have one collective proof for all inputs and outputs
I don't recommend this. Essentially it just merges the input and output proofs together and uses a selector bit to choose which part of the circuit is used. Some parts are reused between both parts, but IMO it doesn't bring much anonymity and complicates things. But this is a minor point if you prefer this technique.
Also I am now suddenly very bullish on Monero. wagmi
I heave to learn why pallas was chosen over vesta in the first place.
@kayabaNerve iirc there is a conversion from vesta is embedded into pasta, and there is a conversion mod_r_p() so pallas Base field values can be imported directly into the scalar field (for use in circuits). It's a trick that can only be used one way but not the other.
I also couldn't find any information about what specific 2-adicity is required for PLONK and the limitations implied. But nevertheless, this curve cycle should work at least as well as Pasta.
@tevador standard circuits in production usually use k = 11 to 13 in my experience. Above 15, it is far far too slow, but big prod circuits like rollups would do weird things like FRI or pairings inside. Unlikely you'll need that though.
You also don't even need 2-adicity. You need a subgroup of a certain size that fully contains your circuit + 5 extra blinding rows. The cosets form the other columns (gates in halo2 terminology). More cosets/columns = more operators in your circuit.
This is in the permutation argument. The original plonk paper used quadratic residues to select distinct cosets of the subgroup (see bottom of page 26). You can look at the halo2 docs for $\delta^i$ which is the coset selector, whereas $\omega^j$ selects the row. This permutation argument is based off the earlier proof of a mixnode mixing by Jens Groth btw if curious (hence why roots of unity is used).
q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
K = GF(q)
P.<X> = K[]
# GENERATOR^{2^s} where t * 2^s + 1 = q with t odd.
# In other words, this is a t root of unity.
generator = K(5)
# There is a large 2^32 order subgroup in this curve because it is 2-adic
t = (K(q) - 1) / 2^32
assert int(t) % 2 != 0
delta = generator^(2^32)
assert delta^t == 1
# The size of the multiplicative group is phi(q) = q - 1
# And inside this group are 2 distinct subgroups of size t and 2^s.
# delta is the generator for the size t subgroup, and omega for the 2^s one.
# Taking powers of these generators and multiplying them will produce
# unique cosets that divide the entire group for q.
def get_omega():
generator = K(5)
assert (q - 1) % 2^32 == 0
# Root of unity
t = (q - 1) / 2^32
omega = generator**t
assert omega != 1
assert omega^(2^16) != 1
assert omega^(2^31) != 1
assert omega^(2^32) == 1
return omega
# Order of this element is 2^32
omega = get_omega()
k = 4
n = 2^k
omega = omega^(2^32 / n)
assert omega^n == 1
# ...
a_1_X = P.lagrange_polynomial((omega^i, A_1_i) for i, A_1_i in enumerate(A1))
a_2_X = P.lagrange_polynomial((omega^i, A_2_i) for i, A_2_i in enumerate(A2))
a_3_X = P.lagrange_polynomial((omega^i, A_3_i) for i, A_3_i in enumerate(A3))
a_4_X = P.lagrange_polynomial((omega^i, A_4_i) for i, A_4_i in enumerate(A4))
# ...
indices = ([omega^i for i in range(n)]
+ [delta * omega^i for i in range(n)]
+ [delta^2 * omega^i for i in range(n)]
+ [delta^3 * omega^i for i in range(n)]
+ [delta^4 * omega^i for i in range(n)])
assert len(indices) == 80
# Permuted indices
sigma_star = [indices[i] for i in permuted_indices]
s = [sigma_star[:n], sigma_star[n:2 * n], sigma_star[2 * n:3 * n],
sigma_star[3 * n:4 * n], sigma_star[4 * n:]]
Monero will become the #1 privacy coin with this upgrade. We believe the return to values agorist narrative will be the next driving force in this cycle.
This video explains why: Lunarpunk and the Dark Side of the Cycle
Original text is here. This was published Feb 2022. Then Tornado Cash happened. The events are unfolding as claimed. We must be prepared to meet the challenge!
kayabaNerve
commented
1 year ago @narodnik A larger 2-adicity offers more options, yet any smaller k value can still be used, right?
Also, do you have a link to the cited paper by Eagen available?
narodnik
commented
1 year ago Yes correct. k = 11, corresponds to the $2^{11}$ subgroup.
Here is the paper: https://eprint.iacr.org/2022/596
If you check the end part, it mentions curve trees.
kayabaNerve
commented
1 year ago It looks like that doesn't put any bounds on the elliptic curve, which is great. It'd also greatly accelerate Pedersen hashes...
Each additional hash adds only two multiplications and one scalar
It does conflict with "SNARKs", yet should work with Bulletproofs, which curve trees are based on. I'm unsure if Halo 2, a Bulletproof inspired protocol, is fit under the former or later category.
@narodnik I can't find any mention of "trees" in the paper nor IACR page. Mind clarifying the section?
tevador
commented
1 year ago I can't find any mention of "trees" in the paper nor IACR page. Mind clarifying the section?
I think §5.1 and §5.2 indirectly relate to Curve Trees, which internally use Pedersen hashes and a recursive construction with a 2-cycle.
narodnik
commented
1 year ago yep apologies, I thought it mentioned curve trees but that's the section.
narodnik
commented
1 year ago Check these slides out for more info on the construction of pallas and vesta curves: https://github.com/daira/halographs/blob/master/deepdive.pdf
Also if you're concerned with efficiency, a more experimental idea would be genus-2 hyperelliptic curves which are known to be secure and are slightly more efficient than usual EC. They are degree 5 curves so each line through them creates 5 points. The group law is constructed using the picard group.
The 2 cycle is mainly for proof composition. The older curve was BLS12-381 which was able to embed jubjub inside. This was a one way embedding.
The halo1 paper describes the amortization strategy which happens in the polynomial commitment proof.
The large 2-adic subgroup means we can do efficient DFFT/lagrange polynomials which is the core of plonk-based protocols.
tevador
commented
1 year ago I'd like to focus on Curve Trees first, because that could work while keeping the Ed25519 curve.
I think the next steps should be:
If step 1 shows that the protocol is infeasible or step 3 shows that the verification performance is insufficient, then we can move to research plonk and decide which new curve to use.
kayabaNerve
commented
1 year ago @tevador
1.
d = -15203, h(d) = 38
p = 2^255 - 19
A_p, B_p = 42133672695493072568592123651119866263416556208894889063239545248024637995649
E_p/F_p : y^2 = x^3 + A_p x + B_p
#E_p = q
q = 57896044618658097711785492504343953926225696987256860989792804023844074237167
A_q, B_q = 29601700755814669423401170136441329018751839114999486207043705707424836093663
E_q/F_q : y^2 = x^3 + A_q x + B_q
#E_q = pThis is from Eagen and is a direct cycle of 2^255-19. The reason we shouldn't use this cycle or an indirect cycle is performance. The curve cycle you noted is directly competitive with Ed25519 and has a high 2-adicity.
narodnik
commented
1 year ago He also kindly sent me these calculations: https://agorism.dev/uploads/ecip_calculations.ipynb
Next week I'll post a longer write up of all the steps with self contained sage code. There's a few helper utilities I need to create, then we can start work on a prototype rust version to benchmark against halo2 merkle proofs. Feel free to poke me on IRC for more info. Happy to explain anything in the paper.
There is a bug in sage so the dlog calculation fails for higher multiplicity functions. The fix is to turn the denominator into a function in x by taking the norm. Observe that every function in the function field can be written as $\frac{a(x) + yb(x)}{c(x) + y d(x)}$, which is the same as
$$\frac{(a(x) + yb(x))(c - yd(x))}{c(x)^2 - y^2 d(x)^2} = \frac{(a(x) + yb(x))(c - yd(x))}{c(x)^2 - (x^3 + Ax + B) d(x)^2} = \frac{(f \circ \bar{g})(x, y)}{N_g(x)}$$
daira
commented
1 year ago @tevador :
@kayabaNerve :
I'll note regarding your second cited source, it has a complexity of O($n^{1.5}$). These curves have a n of $2^{32}$. Pallas's $n$ is 32.
I admit I haven't read the second paper in detail. I was going by a statement from the zcash blog post that claims 2-adicity "may assist in square root performance". If the algorithm is O($n^{1.5}$) then it might actually be slower, which is unfortunate and may negate the other performance benefits.
To explain this: 32 is a multiple of 8, and this facilitates using Sarkar's algorithm with 8-bit tables, which are a convenient size (as done in the https://github.com/zcash/pasta_curves implementation). The benefit is fairly small but measurable when compared to a similar 2-adicity that is not a convenient multiple. In general, a larger 2-adicity does give slower square roots (but not egregiously so, and it really only matters for point decompression).
daira
commented
1 year ago @narodnik :
@kayabaNerve :
Please note Zcash transactions have one collective proof for all inputs and outputs
I don't recommend this. Essentially it just merges the input and output proofs together and uses a selector bit to choose which part of the circuit is used. Some parts are reused between both parts, but IMO it doesn't bring much anonymity and complicates things. But this is a minor point if you prefer this technique.
This description is a bit confused; there are two things is could be referring to:
narodnik
commented
1 year ago Aha right because you want to guarantee that the serial produced by the output is unique and not reused in another output. You do that by merging the spend + output proof, and using the spend nullifier in the output serial. Thanks a lot for clarifying.
str4d
commented
1 year ago I heave to learn why pallas was chosen over vesta in the first place.
@kayabaNerve iirc there is a conversion from vesta is embedded into pasta, and there is a conversion mod_r_p() so pallas Base field values can be imported directly into the scalar field (for use in circuits). It's a trick that can only be used one way but not the other.
Yep. The specific issue is that in a couple of places in the Orchard protocol, we needed to be able to treat a protocol curve point coordinate as a protocol curve scalar, which means treating a circuit curve scalar field element as a circuit curve base field element. Using Pallas as the protocol curve made this easier because its base field is smaller than its scalar field (and correspondingly for Vesta as the circuit curve its scalar field is smaller than its base field).
We could technically have chosen the other way around, but then would have needed to deal with the fact that the mapping would cause a reduction. As it was, we still had some complexity because even though the mapping wouldn't cause a reduction, we still needed to ensure canonical representation of the wrong-field element, so overall the complexity was probably equivalent either way (but the way round we chose meant the complexity was in the circuit implementation, not the protocol).
tevador
commented
1 year ago The reason we shouldn't use this cycle or an indirect cycle is performance.
I don't think performance is a sufficient reason to switch curves unless we can show that the indirect cycles are too slow.
This is from Eagen and is a direct cycle of 2^255-19.
Interesting find, but I'm not convinced it would be faster because there is no endomorphism on these curves and the values of the curve constants require slower formulas to be used.
kayabaNerve
commented
1 year ago @daira @str4d Thank you for chiming in. Your knowledge/experience is greatly appreciated :)
@tevador Regarding the indirect 2-cycle, I just wanted to make it available.
In order to better comment on switching curves, what would be the performance of your tower-cycle compared to Ed25519? The cycle you put forth was directly competitive. This will also be the most expensive proof in Monero, so that will weight it significantly.
tevador
commented
1 year ago This is from Eagen and is a direct cycle of 2^255-19
I think I know how this cycle was discovered.
I was able to reproduce it by following the algorithm described in this paper: https://arxiv.org/abs/0712.2022
Here is a slightly better one I found:
p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
q = 0x7fffffffffffffffffffffffffffffffbb2d703f7a1e51cdf484069145e5f0f7
a_q = 13033894050202716689882839840150569719615712187482288559001333083615467046208
Eq: y^2 = x^3 + a_q*x + a_q
#Eq = p
a_p = 48408044624602722078043330694711161699859898671792113289661329891201103641892
Ep: y^2 = x^3 + a_p*x + a_p
#Ep = qThis one is preferable because 2^256 - 2*q < 2^128, which means the prime supports a competitively fast Barrett reduction (albeit still much slower than 2^255-19).
It is a "short tower-cycle":
---->----
/ \
Ed25519 -> Eq Ep
\ /
----<----Unfortunately, these curves don't have an efficiently computable endomorphism, so while their field arithmetics might be faster than Pallas/Vesta, scalar multiplication will be slower. However, this is much better than the 266-bit primes presented earlier.
Cli5y
commented
1 year ago Commenting due to this forum thread: https://forum.zcashcommunity.com/t/allow-special-exception-to-the-orchard-codebase-for-the-monero-project/41392
The BOSL exemptions for Orchard, as stated by ECC, are:
- Projects that are designed to integrate with Zcash and provide additional functionality or utility to the Zcash network and users of the ZEC coin
- Blockchains that descend from the Zcash blockchain and that are forked within 100 blocks of the current block height at the time of the code fork
I'm curious if Monero could qualify for a permissionless exemption via the first bullet point. It would require development efforts (that also aid Zcash) outside of implementing Halo2/Orchard into Monero, but could give Monero ability to use Orchard.
Not sure if Monero would need to use Orchard code, but gives teams the ability to do this:
- The Monero project could include Orchard code to make a derivative work without needing to license the Monero code under the same BOSL restrictive license.
Just a thought. Could be wrong with my interpretation.
narodnik
commented
1 year ago @esepibito the zcash team are kind enough to make halo2 available. Orchard is a relatively small code and not needed here.
@tevador about lack of endomorpism, another possibility for speedup is addition chains. Also succinct EC multiplication proofs might reduce the cost further. Although I'm not sure how impactful these changes would be (and having a proof means extra data) so ECM is much preferred.
kayabaNerve
commented
1 year ago @esepibito We are not interested Orchard. We have our own transaction protocol, Seraphis.
While their Halo 2 library is of potential interest, it's not a current discussion. The current discussion is on a curve cycle for curve trees. In the future, we may further consider replacing the Bulletproofs used within curve trees with a proof like Halo 2, then leading into a discussion on using the Halo 2 library, that's far out of scope right now.
I'd also further note a complete lack of interest in any non-FOSS usage of code. Exemptions are not FOSS. While the BOSL may be arguable as a FOSS license, it is so restrictive I cannot in good faith ever advocate its usage within Monero. This is comparable to how we cannot, and should not, use GPL code (as it'd require moving to the GPL license).
narodnik
commented
1 year ago I have the core part of the ECIP proof working here:
https://github.com/darkrenaissance/darkfi/blob/master/script/research/zk/ecip/proof.sage
Now I'll generalize it to proving point relations. Then after that's finished, I'll make a writeup/explainer and can start writing a Rust version so we can benchmark its speed.
kayabaNerve
commented
1 year ago @tevador I don't believe an indirect curve cycle will work.
For:
Ed25519 - X - Y <-> Z
We need to perform an EC add for Ed25519 and prove membership. We'd have to prove the addition over X, yet then prove the membership over Y/Z. The entire process has to be done in ZK to be a valid membership proof however.
Any thoughts on this? Am I missing something?
tevador
commented
1 year ago I don't believe an indirect curve cycle will work.
I'm not an expert on ZKP, so CMIIW, but from what I understand, I think it should work.
Consider the tower-cycle:
Ed25519 -> Ep <-> EqIn order to normalize the group law, it's better to convert all keys from Ed25519 to the isomorphic curve Wei25519, which is a short Weierstrass curve.
The Merkle tree would look like this:
Wei25519EpEqEpEp or Eq depending on the number of levels.You have a Wei25519 key K_o you want to prove is in the tree.
The recursive proof construction works exactly as described in the Curve Trees paper. You use the "Select and rerandomize" proof at each tree level. At the leaf level, you get the commitment K_o' = K_o + r G, which is published to be used in the composition proof (after converting it back to Ed25519 using the isomorphism map).
Notice that the leaf-level proof is done on the curve Ep. This means that all the proofs are either in Ep or Eq, so we can merge them into just 2 proofs as it's done in the Curve Trees paper. The only difference will be the constants used in the rerandomization at the leaf level (those will be the Wei25519 curve constants), but I don't think this prevents merging.
If this is confirmed to be possible, I think it's the preferable solution because it avoids the commitment migration that would be needed if we switched curves.
kayabaNerve
commented
1 year ago While that sounds possible, it'd mean we'd always need an additional proof. Not only would we always need an additional proof, if not two for your optimized tower-cycle, the lowest proof(s) would never be SNARKs under current academia due to verification time.
The first proof is also the largest one due to performing the ECC op and the hashes. For that to not be a SNARK would be... extremely detrimental.
tevador
commented
1 year ago The first proof is also the largest one due to performing the ECC op and the hashes.
Curve Trees perform point blinding and hashing on every level. See the paper, section 4.2.1.
kayabaNerve
commented
1 year ago https://github.com/kayabaNerve/full-chain-membership-proofs/
Considerations:
1) It's in Rust. I can comment on the code cleanliness that enables, or on the shared efforts it can bring us with other projects, or on the safety... or we can say that's unacceptable and someone else can rewrite it in C++. Personally, I'd like to see a hybrid approach where most is kept in Rust, yet some (like the tree code) may or may not be rewritten in C++.
2) It's slow. Without a proper vector commitment scheme, it's ~33x slower than Grootle proofs for a 777m membership set. With one, it's only an order of magnitude slower. I see a path of getting it to just 3-5x slower, and the curve trees PoC even beat Grootle (with heavy parallelization). With further work on internal structuring, inspired by the curve trees PoC, I'd hope to end up at 2-3x times slower.
3) I implemented the DLEq proof, and technically implemented tevador's first cycle candidate. My impl of tevador's first cycle candidate is unviable and needs a complete rewrite. I've been testing with the pasta curves. With a proper impl of tevador's first cycle candidate, we're looking at just ~3x slower. I'd also note we do use hash to curve, currently, so we may prefer tevador's second cycle candidate (discussions pending).
4) My presentation at MoneroKon, which has been uploaded to the repo, goes over it briefly (and non-technically). I hope to discuss this at the next MRL meeting to further clarify. After initial understandings are present, I hope to provide a clear path forward of actionable steps with @j-berman.
kayabaNerve
commented
1 year ago I'm still overall working on summaries/exact specifications to refer to, yet to start:
1) Would enable a clean solution to #96 AFAICT 2) Would void #87 and #109 3) Would prevent a remote node from sending a skewed output distribution, nuking privacy (they could only send a historical honest distribution, which can be mitigated by having the block header be binding to the output tree root) 4) #95 is unaffected. The tree root contains all outputs, so any re-org of outputs will provide a different tree root, voiding any TXs reliant on the original tree root
I'd also note #101 becomes more notable. The biggest concern I've heard is over the proof size which BP++ should also reduce. We would need a modified BP++, as we need a modified BP+ though. Modifying BP+ still makes sense as BP++ argues its norm argument is a reduction to BP+'s WIP argument, so modifying BP+ sets applicable groundwork.
EDIT: BP++ will only cause a size reduction of 3.6%. The main benefits would be in greater flexibility regarding circuit layout and verification time.
kayabaNerve
commented
1 year ago Discussing with @jeffro256 and @j-berman, a novel vector applicable to rings came up.
If a coinbase output is swept, rings are effectively null since the received output amount + fees will equal one of the ring members exactly (as the coinbase output has a known amount). This is somewhat mitigated with tail emission normalizing coinbase amounts, yet that reduces the ring to the amount of tail emission coinbases if a tail emission coinbase is swept/"send max"d.
Full chain membership proofs include all tail emission coinbases, and for non-tail-emission coinbases, increases the odds a distinct output with a matching value when including whatever the change output may or may not be as if it was a sweep/"send max" is undetectable was spent.
I'll also note that while DSAs aren't dead, they become limited to light wallets (instead of requesting a single path, doxxing the spent output, a ring of paths would be requested). This greatly reduces their importance and issues raised by implementation faults.
kayabaNerve
commented
1 year ago I believe I made a mistake, and each input proof would only be 2kb, not 4kb as I off hand estimated. Accordingly, 2-in, 2-out TX sizes would be ~5.5kb, not 10kb.
kayabaNerve
commented
1 year ago We can also use one pair of membership proofs for every input, instead of per input. That'd make the second input add a few hundred bytes, not double the entire proof size. Unfortunately, I believe that breaks the flexibility of Seraphis a bit too much, with a notable privacy impact when TX-chaining/doing collaborative TXs (which are also how we start discussing payment channels, so I wouldn't appreciate so harming them).
EDIT: politicalweasel on Twitter suggested pairing each pair of inputs with a single proof. This would have slightly improved verification times, notable space savings, yet still allow collaborative transactions without participants doxxing their memberships to each other. They'd simply need an (unnecessary) 3rd input, with a second proof (handled by the second party).
We could also review MPC proving of BP+ if this is important yet we want to batch all inputs in a TX under a single proof.
The goal of this meta issue is to build a go-to place for links, information, and opportunities for building trustless zk-SNARKs as a potential future protocol building-block for Monero.
Disclaimer: I am not a cryptographer or a dev, so please provide corrections and context if I have missed key details here. I am merely seeking to pull people together who are, provide resources, and ensure we take as close of a look as necessary at zk-SNARKs as a potential upgrade for Monero in the future.
Why zk-SNARKs?
Monero has iterated over the years to continue in leading the way in building out a cryptocurrency that puts user's privacy and security above all else. The Monero community has done this through finding the gaps and flaws in the protocol, watching external projects and researchers work, and implementing both internal and external developments over time to improve the holistic privacy provided to every user of the Monero network.
The weakest aspects of Monero's current approach to privacy is that of ring signatures, the approach that is taken to hide the true spend in each transaction among a set of potential signing inputs. These ring signatures have been an excellent tool for Monero so far, allowing us to build stable, efficient, and trustless privacy into each transaction, and are greatly strengthened by the added privacy of one-time addresses and confidential amounts.
While these three building blocks provide strong privacy today and show no signs of causing broad issues, they have noted weaknesses, especially for targeted threat models or those where multiple entities collude to form a transaction graph via EAE attacks or similar. This key weakness, combined with the ability to build probabilistic transaction graphs with off-chain data, should push us to keep seeking how we can mitigate the issue entirely.
The proposed Seraphis protocol allows us to greatly reduce the chances of successful probabilistic tracing, but is not necessarily a complete solution for targeted attacks or those aided by off-chain metadata. I do not want to prevent the further exploration of Seraphis with this effort, and a migration to Seraphis could even simplify a potential future migration to zk-SNARKs thanks to the modularity of Seraphis approach to the payment protocol.
zk-SNARKs allow us to move from obfuscating the true spend to truly hiding it, a large step forward in preventing even targeted attacks from building a transaction graph, while doing so in a way that remains trustless and efficient.
While it is outside of the scope of this issue, zk-SNARKs can also be used to build out much more advanced protocol features such as colored coins, smart contracts, etc. like currently being built out by DarkFi. This flexibility can pave the way for greater use-cases being built out on Monero in the future, and could be an extremely useful building block.
Why now?
With the advent of trustless and relatively efficient zk-SNARKs via advances like PLONK and implementations of it like Halo 2, zk-SNARKS are finally at a state where we can truly explore what an implementation of them in Monero's broader transaction protocol would look like, the implications it would have, the leg-work required, etc.
While Seraphis will bring much greater per-transaction graph obfuscation, it still provides some attack vectors for targeted attacks. As such, we should keep looking to the future and find ways that we can continue improving the Monero protocol over time.
Proposed efforts
While I know this is a major shift in the approach Monero has taken to output hiding in the past, there are some unique opportunities available to us today thanks to the wealth of effort being poured into zk-SNARKs across the cryptocurrency and privacy ecosystem today.
Open research questions
There are many open questions that we would need to (or should) answer in the process of exploring what an implementation of trustless zk-SNARKs would look like in Monero. If you want to take on one of these open questions, please open a new issue/gist and provide the link so I can update it here.
Extra notes
Helpful links
Educational resources and explainers
Existing implementations and code examples
P.S. -- if you come across helpful research that could be applicable to zk-SNARKs in Monero, please consider submitting it for inclusion on https://moneroresearch.info.