No package.xml not found despite it is presented

Question

I want to deploy an Apex class via REST API in a "single package" way. The deployment process begins and then fails with "No package.xml found" error. The manifest file is put directly in the root of the archive, however the API tells me that there is no manifest.

My request body looks in the following way

----------------------------BOUNDARY
Content-Disposition: form-data; name="entity_content"
Content-Type: application/json

{
  "deployOptions": {
    "allowMissingFiles": false,
    "autoUpdatePackage": false,
    "checkOnly": false,
    "ignoreWarnings": false,
    "performRetrieve": false,
    "purgeOnDelete": false,
    "rollbackOnError": true,
    "runTests": [],
    "singlePackage": true,
    "testLevel": "NoTestRun"
  }
}
----------------------------BOUNDARY
Content-Disposition: form-data; name="file"; filename="deploy.zip"
Content-Type: application/zip

UEsDBAoAAAAAAM4EL1Zi1oXYuQAAALkAAAALAAAAcGFja2FnZS54bWw8P3htbCB2ZXJzaW9uPSIxLjAiIGVuY29kaW5nPSJVVEYtOCI/PjxQYWNrYWdlIHhtbG5zPSJodHRwOi8vc29hcC5zZm9yY2UuY29tLzIwMDYvMDQvbWV0YWRhdGEiPjx0eXBlcz48bWVtYmVycz5BPC9tZW1iZXJzPjxuYW1lPkFwZXhDbGFzczwvbmFtZT48L3R5cGVzPjx2ZXJzaW9uPjU2LjA8L3ZlcnNpb24+PC9QYWNrYWdlPlBLAwQKAAAAAADOBC9WAAAAAAAAAAAAAAAACAAAAGNsYXNzZXMvUEsDBAoAAAAAAM4EL1aRdfeXigAAAIoAAAAWAAAAY2xhc3Nlcy9BLmNscy1tZXRhLnhtbDw/eG1sIHZlcnNpb249IjEuMCIgZW5jb2Rpbmc9IlVURi04Ij8+PEFwZXhDbGFzcyB4bWxucz0iaHR0cDovL3NvYXAuc2ZvcmNlLmNvbS8yMDA2LzA0L21ldGFkYXRhIj48YXBpVmVyc2lvbj41Ni4wPC9hcGlWZXJzaW9uPjwvQXBleENsYXNzPlBLAwQKAAAAAADOBC9WnojzmRIAAAASAAAADQAAAGNsYXNzZXMvQS5jbHNwdWJsaWMgY2xhc3MgQSB7IH1QSwECFAAKAAAAAADOBC9WYtaF2LkAAAC5AAAACwAAAAAAAAAAAAAAAAAAAAAAcGFja2FnZS54bWxQSwECFAAKAAAAAADOBC9WAAAAAAAAAAAAAAAACAAAAAAAAAAAABAAAADiAAAAY2xhc3Nlcy9QSwECFAAKAAAAAADOBC9WkXX3l4oAAACKAAAAFgAAAAAAAAAAAAAAAAAIAQAAY2xhc3Nlcy9BLmNscy1tZXRhLnhtbFBLAQIUAAoAAAAAAM4EL1aeiPOZEgAAABIAAAANAAAAAAAAAAAAAAAAAMYBAABjbGFzc2VzL0EuY2xzUEsFBgAAAAAEAAQA7gAAAAMCAAAAAA==
----------------------------BOUNDARY--

where Base64-encoded Zip file has the following structure

package.xml
classes/
  A.cls
  A.cls-meta.xml

and those three files look in the following way.

(package.xml)

<?xml version="1.0" encoding="UTF-8"?>
<Package xmlns="http://soap.sforce.com/2006/04/metadata">
  <types>
    <members>A</members>
    <name>ApexClass</name>
  </types>
  <version>56.0</version>
</Package>

(A.cls)

public class A { }

(a.cls-meta.xml)

<?xml version="1.0" encoding="UTF-8"?>
<ApexClass xmlns="http://soap.sforce.com/2006/04/metadata">
  <apiVersion>56.0</apiVersion>
</ApexClass>

I've also tried to set singlePackage to false and use unpackaged folder as a wrapper but I doesn't work, too.

There is a possibility that "No package.xml found" is a catch-all error that makes solving the problem harder than it should be.