Request for funding / Antioch / Apr-Jun 2020

Governance
21

There is no thread for NRD, most of the discussion has been happening in keybase, mainly the node_dev#research channel.

I’m aiming to get an initial draft of the RFC up in the next couple of days and hopefully that will kick off a more structured discussion around the direction we plan to take this.

My knowledge of the specifics of the Beam approach is pretty limited, but my understanding is that they have implemented an explicit reference back to effectively any previous kernel, referenced by kernel hash. And that any kernel can optionally include this reference.

Without looking too closely this does appear to have a couple of pretty serious issue regarding scalability and is close in terms of design to various early approaches that we considered (and subsequently discarded) -

https://lists.launchpad.net/mimblewimble/msg00548.html

The main issue is the need for all nodes to maintain a full index over all historical kernels, effectively forever. This is clearly undesirable as the set of kernels will only ever get larger.

The other issue is the need to explicitly reference a previous kernel (by kernel hash). This adds (32 bytes?) to every relative lock kernel and these additional bytes need to retained forever.

I believe Beam does not take this into account when determining tx fee (I may be mistaken here though) so this additional storage cost (and network cost) can be forced on all nodes by any participant building transactions (for free).

The use of a hash as the reference also introduces an opportunity to include arbitrary data on the blockchain. A malicious actor can potentially take advantage of this across multiple kernels to include arbitrary data that every node on the network is then forced to store and retain indefinitely.

I suspect Beam approached this in terms of “ticking the box” for the feature with a view to revisiting the implementation specifics at a later date. My understanding is “Laser Beam” (Beam payment channel support) is a proof of concept and not yet production ready (even though it is on mainnet).

Grin is taking a far more conservative approach to this. And we believe NRD has the potential to provide a limited, constrained (yet still useful) solution to relative locks while avoiding the problems listed above.
It has taken a year to get to this point in our understanding of the problem, but hopefully we can avoid releasing a solution prematurely.

4 Likes
22

Antioch, this is Valdo’s (Beam lead dev reply):

  1. Regarding the kernel index.

As for now we indeed maintain the full index of all the kernels that ever existed.

This index was from the very beginning, before we ever thought about relative locks and payment channels.
The reason for this index was that we wanted users to be able to find out if a specific transaction (i.e. kernel) took place in the past, and generate the merkle proof any time. This index, however, was optional. We knew we could remove it in the future once it becomes a problem (and disable the “find kernel height” functionality by default). Still comprehensive blockchain validation was possible.

With introduction of relative locks this index became mandatory. In addition to the relative locks, some of our new features (would be released at HF2) are vulnerable to “transaction repeatability”, and to prevent this yet again we’ll use the kernel index.

We realized that with time we could run into a problem with this index, which can’t be removed any more. So, we found a way to work this out.
Described here:

In short, starting from HF2:

(a) kernel search for the sake of blockchain validation will not “see” kernels beyond specific point in the post, determined by a consensus rule parameter (kernel visibility horizon), probably order of ~1 month.
(b) kernel validity period is implicitly limited by this parameter too. (reminder: beam kernels have optional timelocks from both sides: min/max height). So, even if a kernel doesn’t have an explicit max height, it’s assumed implicitly no more than its min height plus this horizon.

This effectively means that for full blockchain validation a node would only need an index of the most recent kernels. This covers both the relative locks, and transaction repeatability prevention.

  1. Extra 32 bytes in the kernel.

You are right, we didn’t consider to raise the tx fee for using it. Moreover, right now our minimal fees are ridiculously low anyway (and at the very beginning they were not mandatory at all). The idea was that fees would become significant once the blocks are full, but we are not any near it.
Raising the fee may be a good idea. However IMHO right now with today’s prices it’s pretty easy to “spam” the blockchain for the attacker even with “meaningful” fees.

As for encoding extra info: this sounds more like a feature, than a vulnerability. Anyone may embed a 32-byte info into any kernel, due to the degree of freedom within its Schnorr’s signature (random nonce). Additionally you can append arbitrary number of kernels to a tx, to store more auxiliary info.

3 Likes
23

The nonce appears only in committed form k*G, which necessarily looks random (up to brute-force search for a few “vanity” characters).

24

Yes, it “looks” random, unless you derive it deterministically from the visible kernel data and your secret. Then you’ll be able to identify such a kernel during rescan. So that if you add an additional kernel to a transaction (fully built by you), then you actually have 2 degrees of freedom: you choose the kernel blinding factor, and the nonce to sign it. Means you can practically (1) tag your kernel, (2) put arbitrary 32 bytes of data in it

25

Can you explain how to extract the 32 bytes of data from your kernel?

26

For example:

  1. Your 32 bytes “s” is the kernel blinding factor. Add this kernel to to a random tx, and update the tx “offset” to account for this.
  2. Kernel commitment is s*G
  3. Derive your nonce “n” as n = HMac(your_secret, kernel_hash)
  4. Sign it. Reveal N = nG and k = n + schallenge

Now, during the recovery, for each kernel.

  1. Calculate the hash of the kernel.
  2. Derive n = HMac(your_secret, kernel_hash)
  3. Calculate N=n*G. If it’s different from the signature - skip the rest (not recognized).
  4. Reverse-engineer the blinding factor: s = (k - n) * challenge^-1
  5. The blinding factor “s” is our aux data
27

I think you and @tromp are talking about two different things here.
I think you are talking about introducing data in kernels that allows you to identify them at a later point in time. There is no issue “hiding” data in the kernels.
The issue is allowing arbitrary data to be included in kernels “in the clear”, effectively forcing all nodes to store and retain this data indefinitely.

If each kernel allows a 32 byte “hash” to be included, but that hash may not actually reference a prior kernel in the recent history, then it may not actually be a “hash” at all, it can be arbitrary data itself.

If I can take an mp3 (or other piece of media), split it up into 32 byte chunks and force all nodes on the network to download it and store it then we potentially have a problem.

My earlier point about “what Beam is doing” was not intended to kick off a larger discussion around Beam design choices. I just wanted to make it clear that we do not necessarily want to simply copy what Beam is doing.

2 Likes
28

Thanks for explaining. To use more standardized variable names, I would say that your arbitrary data is the 32 byte (private) excess x in a transaction. The signature satisfies s = k + e * x, so if you pick the nonce k as H(your_secret, x*G), then you can recover x as (s - k) * e^{-1}.

So this allows embedding of arbitrary private data, but not of arbitrary public data (potential spam). Is BEAM also spam proof, like Grin is?

29

Oh, so you’re talking about spamming with “public” data, such as leaving graphiti on the city walls. I didn’t think about it.
Specifically our version of the relative locks is not prone to this, because the referenced kernel MUST indeed exist, and it MUST be at least N blocks earlier. So it’s not exactly like NRD/NSKR in grin.
But there is actually another place which can be used for spamming: the “hash lock”, i.e. a kernel may optionally contain an arbitrary 32-byte data (hash preimage), which is hashed, and the result is used in the final kernel hash.

Sorry for a dumb question, but why is this a problem? Because it may be offensive for someone that would try to read it as an ANSI-encoded text string?

P.S. Even without the obvious spam placeholder, virtually everything can be used for spamming. For instance: pick some least significant bits of the fee and height lock, and use them as a morse code for your spam :slight_smile:

1 Like
30

I think:
A few bits :: no problem for plausible deniability.
256 bits : no possible plausible deniability if the 256 bits altogether can be interpreted to something very clear by a well known software.

31

While some graffiti can be quite artful, others are downright ugly.
In real life, the latter can be removed with some effort.
No one likes the idea of child porn embedded in the blockchain.

One can argue whether allowing for permanent storage of public data is a problem or not. It may not be the kind of use you want to incentivize. It may lead to blocks filling up sooner.

To me, it’s somewhat surprising that a blockchain can even be spam-proof, and MW appears to be rather unique in this regard.

I like Grin to have novel properties that set it apart from all other cryptocurrencies. In particular when the value of those properties can only be appreciated in the long term.

Such properties include:

a history of two mysterious creators
constant reward (so simple in its novelty that it’s surprising it took 10 years for someone to try)
ability to dynamically shift rewards between multiple PoW
a memory hard PoW that requires tons of SRAM

and I’m happy to be able to add being spam-proof to that list.

7 Likes