Hey, I just double checked to not cause unnecessary confusion:

Crated new user on arch to get empty home:

used same .emacs as before, but without (setq gnutls-algorithm-priority 
"NORMAL:-VERS-TLS1.3"). After refreshing package list i can find 
undo-tree in gnu repos. When i try to install get the same bad request bug.

After adding the line (setq gnutls-algorithm-priority "NORMAL:-VERS-TLS1.3")

use-package downloads the package properly at startup and everything 
works fine.

Can i provide additional debug info?
Still not sure tho if its some dumb mistake in my os.

On 19.07.19 14:09, Tim Cross wrote:
> Yep, checked and it made no difference. Did get a little more wrt 
> error info
>
> gnutls.el: (err=[-50] The request is invalid.) boot: (:priority 
> "NORMAL:-VERS-TLS1.3" :hostname melpa.org <http://melpa.org> :loglevel 
> 0 :min-prime-bits 256 :trustfiles (/etc/ssl/certs/ca-certificates.crt) 
> :crlfiles nil :keylist nil :verify-flags nil :verify-error nil 
> :callbacks nil)
>
> Also tried with TLS 1.2, same error.
>
>
>
> On Fri, 19 Jul 2019 at 22:02, Noam Postavsky <npostavs@gmail.com 
> <mailto:npostavs@gmail.com>> wrote:
>
>     Robert Pluim <rpluim@gmail.com <mailto:rpluim@gmail.com>> writes:
>
>     >     Noam> Does (setq gnutls-algorithm-priority
>     "NORMAL:-VERS-TLS1.3") help?  If
>     >     Noam> yes, this is likely Bug#34341 (should already be fixed
>     already in
>     >     Noam> emacs-26, and the 26.2.90 pretest).
>     >
>     > elpa.gnu.org <http://elpa.gnu.org> uses TLS1.2, not TLS1.3. But
>     emacs-27 has a bunch of
>     > changes in its TLS handling that might improve matters.
>
>     Hmm, it does.  On the other hand, Lennard told me [Lennard, please use
>     "Reply All" next time so your response goes to the bug list] that
>     (setq
>     gnutls-algorithm-priority "NORMAL:-VERS-TLS1.3") did actually help.
>
>     Tim, can you check the gnutls-algorithm-priority workaround too?
>
>
>
> -- 
> regards,
>
> Tim
>
> --
> Tim Cross
>