This protocol aims to align the monetary incentives for decentralized file hosting, such as for Nostr relays; or for p2p file sharing networks like BitTorrent; or a decentralized content delivery network (CDN), in the context of concepts to decentralize the web such as web5.
Given a file with identifier file_id. The following scheme allows a client to request file_id from a random untrusted server, which responds with file for a payment in coins. The trade is atomic.
The server encrypts the file such that the client can verify that they can decrypt the file if they learn the secret of key S. The client purchases this decryption key in a smart contract, e.g., a PTLC on the Lightning Network, which makes the trade atomic. A malicious client, that already knows some chunks of the file, should not be able to break the scheme and decrypt the rest of the file without knowing the secret of S. For each request of any client, a unique decryption key S must be chosen for Lightning Payments to be secure.
The scheme described here requires about 𝒪( file_size / 32 bytes ) many curve point operations. Unfortunately, that is still too slow to serve lots of clients at once. However, further optimizations might be possible.
The original scheme is much faster, but it was broken in the sense that a malicious client can decrypt the file if they know any chunk of it.
This scheme is based on the idea that in the prover-verifier setting we can perform operations on an elliptic curve 𝙃 "in the scalar" of another elliptic curve 𝙂.
This is possible because the prover can act as Diffie-Hellman oracle by proving the required multiplications to the verifier in the scalar.
We choose some secure curve 𝙃, defined over 𝔽_n, which is the scalar field of the curve 𝙂. Any point P = (x,y) ∈ 𝙃 can be represented "in the implicit representation" using ❬P❭ := (xG, yG). The crux of being able to perform curve point operations in the implicit representation is to prove multiplications in the scalar. This is possible using a proof of multiplication, as described in the appendix.
When 𝙂 is secp256k1 then an obvious choice for 𝙃 would be secq256k1 (sic!). The equation for secq256k1 is simply
y^2 = x^3 + 7 (mod n)
wheras n is the order of secp256k1. Surprisingly, the order of secq256k1 is p, the order of the base field of secp256k1.
- The author shares the file with the server
- The author splits up the file into 32-byte chunks:
m_1, ..., m_n - The author computes
file_id = Hash( m_1 G | ... | m_n G )and shares it with the client - Choose random generators of group
𝙃:H_1, ..., H_nknown to server and client
The server performs the following steps to convince the client
- Send adaptor point
S = sG - Send public nonces
T_1 = t_1 G, ..., T_n = t_n G - Prove equality of scalar for
S = sGandT_1 = ❬s H_1❭, ..., T_n = ❬s H_n❭in the implicit representation. Sot_1, ..., t_nare x-coordinates of points on𝙃, which are hidden in scalars of points on𝙂 - Send
c_1 = m_1 + t_1, ..., c_n = m_n + t_n
Given T_1, ..., T_n, and c_1, ..., c_n, and S. The client performs the following steps to verify the server's claim
- Compute
m_1 G = c_1 G - T_1, ..., m_n G = c_n G - T_n - Verify
file_id == Hash( m_1 G | ... | m_n G ) - Verify the proof of Equal Scalars for
S = sG, andT_1 = ❬s H_1❭, ..., T_n = ❬s H_n❭in the implicit representation
The client performs the following steps to purchase and decrypt the file
- Buy
sin a PTLC usingS - Compute the points
s H_1, ..., s H_n. These points' x-coordinates are thet_1, ..., t_n - Compute
m_1 = c_1 - t_1, ..., m_n = c_n - t_n
Given G, xG, yG and xyG. The prover wants to prove to the verifier that x and y have been multiplied indeed.
- Chose
rrandomly. - Compute
R_1 = rGandR_2 = r (yG) - Compute
c = Hash( R_1 | R_2 ) - Compute
s = r + c * x
Given R_1, R_2, and s
- Compute
c = Hash( R_1 | R_2 ) - Verify
sG == R_1 + c (xG) - Verify
s (yG) == R_2 + c (xyG)
Given a curve point in the implicit representation ❬P❭ = (xG, yG). The prover wants to convince the verifier that the point is on the curve 𝙃 indeed.
y^2 G == x^3 G + a xG + bG
This requires one proof of multiplication for y*y == y^2 and two to compute x*x*x == x^3.
Given three curve points in the implicit representation
❬P❭ = (x_1G, y_1G)
❬Q❭ = (x_2G, y_2G)
❬R❭ = (x_3G, y_3G)
The prover wants to prove to the verifier in the implicit representation that for these three curve points the equation
❬P❭ + ❬Q❭ == ❬R❭
holds.
For two distinct points we can naively apply the point addition formula:
l = (y_2 - y_1)/(x_2 - x_1)
x_3 = l**2 - x_1 - x_2
y_3 = l*(x_1-x_3) - y_1
This requires one proof of multiplication for each of the three equations. All additions in the equation can be easily performed in the scalar by the verifier.
Proving the inversion in the first equation can be done cheaply. The prover provides the result l as a hint
l = (y_2 - y_1)/(x_2 - x_1)
and then proves the multiplication
l * (x_2 - x_1) == (y_2 - y_1)
It might be possible to batch all three proofs of multiplication into one, because they all multiply with l.
Given generators G and H of two different groups, 𝙂 and 𝙃, and some point xG and xH on each curve. The prover wants to prove to the verifier that the scalar of xG and xH is equal.
- Chose
rrandomly. - Compute
R_1 = rGandR_2 = rH - Compute
c = Hash( R_1 | R_2 ) - Compute
s = r + c * x
Given R_1, R_2, and s.
- Compute
c = Hash( R_1 | R_2 ) - Verify
sG == R_1 + c (xG) - Verify
sH == R_2 + c (xH)
Given generators G and H of two different groups, 𝙂 and 𝙃, and some point xG on one curve and a point in implicit representation, ❬xH❭, on the other curve. The prover wants to prove to the verifier that the scalar of xG and ❬xH❭ is equal. We slightly modify the conventional protocol.
- Chose
rrandomly. - Compute
R_1 = rGand❬R_2❭ = ❬rH❭ - Compute
c = Hash( R_1 | ❬R_2❭ | xG | ❬xH❭ ) - Compute
s = r + c * x - Prove implicitly
❬s H❭ = ❬R_2❭ + c * ❬xH❭( "prove implicitly" means "prove in the implicit representation" )
Given R_1, ❬R_2❭, and s.
- Compute
c = Hash( R_1 | ❬R_2❭ | xG | ❬xH❭ ) - Verify implicitly
sG == R_1 + c * (xG) - Verify implicitly
❬s H❭ == ❬R_2❭ + c * ❬xH❭
This requires the prover to prove a point addition and a scalar multiplication in the implicit representation.
- Using a twisted Edwards curve for
𝙃might be slightly more efficient. - We can batch multiple such proofs into a single
sand public nonces❬R_1❭, ..., ❬R_n❭ - Use a digest size smaller than 32 bytes for
c. This way the scalar multiplication becomes cheaper.
Given generator G of group 𝙂 and a set of independently random generators H_1, ..., H_n of group 𝙃. The input is some point xG and a set of points in implicit representation, ❬xH_1❭, ..., ❬xH_n❭, on the other curve. The prover wants to prove to the verifier that the scalar x of xG and all ❬xH_i❭ are equal. We can batch that to make it more efficient for the prover.
- Compute the sum of the generators
H = H_1 + ... + H_nknown to both prover and verifier
- Chose
rrandomly. - Compute
R_1 = rGand❬R_2❭ = ❬rH❭ - Compute
c = Hash( R_1 | ❬R_2❭ | xG | ❬xH❭ ) - Compute
s = r + c * x - Prove implicitly
❬xH❭ == ❬xH_1❭ + ... + ❬xH_n❭ - Prove implicitly
❬s H❭ == ❬R_2❭ + c * ❬xH❭
Given R_1, ❬R_2❭, and s.
- Compute
c = Hash( R_1 | ❬R_2❭ | xG | ❬xH❭ ) - Verify
sG == R_1 + c * (xG) - Verify implicitly
❬xH❭ == ❬xH_1❭ + ... + ❬xH_n❭ - Verify implicitly
❬s H❭ == ❬R_2❭ + c * ❬xH❭
The batched proving time is linear in the number of points n. In total, the scheme requires n+1 implicit additions, but only a single implicit multiplication.
If it is true that one cannot compute any xH_i from xH, then xH can be public and ❬s H❭ == ❬R_2❭ + c * ❬xH❭ can be proven in the plain setting simply with s H == R_2 + c * xH. This saves the implicit multiplication.
- Can the server precompute a generic encryption for each file once and then derive a specific encryption in a faster way for specific requests?
- We can provably map discrete logarithms between groups. Can we map the problem to a smaller group to make it faster? Can we make security tradeoffs for low-value files?